:strip_exif()/u/18993/logo.gif?f=community){kind=logo}
Om heel eerlijk te zijn ben ik er door tijdsgebrek niet in geslaagd een goede oplossing neer te zetten.Ik ben tot diep in de nacht bezig geweest maar zie net het kleine foutje niet 
Ik ben er bijna. Niet dat jullie daar een boodschap aan hebben maar ja 
, Ik ben 2 keer opnieuw begonnen omdat ik zoals gezegd door de code het algoritme niet meer zag. Ik heb natuurlijk wel een algoritme bedacht en zal dat met jullie bespreken. Als jury hebben we natuurlijk de nodige oplossingen gezien en ook de nodige verschillende uitvoer, wat erg leuk was soms. Ik zal ook de jury invoer & uitvoer bespreken. Ik hoop dat de gene die de opgave goed hadden hun strategie en algoritme uit willen leggen.
Zoals jullie allemaal wel gemerkt hebben was het een pittige opgave, die vooral door de vele mogelijkheden niet bruteforce, recht toe recht aan, of recursief op te lossen was. Ook met de jury input hebben we daar natuurlijk rekening mee gehouden.
De strategie die ik gevolgd heb, en volgens mij velen met mij is de volgende:
Als je goed naar een rij kijkt. Is dat een rij van blokjes die aan of uit kunnen zijn. In het voorbeeld hebben we expres een lengte van 8 genomen om de overeenkomst met een byte nog beter op te laten vallen. (max van 30 is ook niet willekeurig aangezien er vaak 32 bits in een integer passen 
)Deze puzzel lijkt dan ook erg sterk op een bitpatroon en zo heb ik het ook benaderd. Ik heb natuurlijk een aantal van zulke puzzels opgelost en gekeken wat de beste taktiek is. Wat je in het begin doet is kijken welke blokjes je zeker in kunt vullen. En deze blokjes vul je dan ook in. Dan ga je kijken welke blokjes zeker leeg moeten blijven en je zorgt dat deze ook leeg blijven
Wat ik heb gedaan. Ik heb van alle mogelijkheden (als een veld 8 breed is passen er in de breedte 2 tot de 8-ste macht verschillende patronen) die ik met een simpel for loopje bereken. Het aantal enen bepaald en geordend op dit aantal opgeslagen. Als ik nu een patroon heb heb ik al ruim 60% procent van de mogelijke invoeren gefilterd. Van de mogelijkheden die dan nog over blijven bereken ik het patroon. Als dat berekende patroon overeenkomt met het patroon wat het moet zijn. Sla ik dat op bij de mogelijken voor die rij. Uiteindelijk heb ik dus een beperkte lijst met mogelijkheden over voor die rij. (sneller als dat het met bruteforcen zou lukken ) Van deze lijst ga ik kijken welke blokjes overal aan zijn. Om dat ik deze mogelijkheden in integers heb opgeslagen is een simpele AND operatie genoeg. Het bitpatroon wat nu overblijft sla ik op met waarde 2. Dan doe ik op de mogelijkheden nog een OR om te kijken welke eventuele gevuld kunnen en belangrijker welke zeker niet.
Voordat ik aan de kolommen begin. Normaliseer ik die eerst. Ik ga kijken of een bepaalde column al aan het patroon voldoet en zo ja dan zet ik alle eventuele (met de waarde 1) op 0.
Dan ga ik alle mogelijkheden voor de kolommen af en volg hetzelfde patroon, mogelijkheden berekenen, normaliseren etc.
Als je geluk hebt ben je nu klaar, als je geen geluk hebt niet.
En natuurlijk hadden we een dergelijke ingewikkelde testcase dat het met deze taktiek niet altijd mogelijk was.
wat ik dan deed is nogmaals de mogelijkheden bepalen maar dan niet alleen van het vooraf gegeven patroon maar ook van de blokjes die al zeker zijn. Dat doe je weer met normaliseren, zowel rijen en kolommen etc.
Ik weet (bijna) zeker dat deze tacktiek werkt ik heb alleen geen tijd meer gehad om het te bewijzen. Maar het feit dat we een aantal goede inzendingen binnen hebben gehad bewijst dat de opgave zeker te doen was
JRobert zal de testset bespreken
succes met opgave 2
Ik ben er bijna. Niet dat jullie daar een boodschap aan hebben maar ja , Ik ben 2 keer opnieuw begonnen omdat ik zoals gezegd door de code het algoritme niet meer zag. Ik heb natuurlijk wel een algoritme bedacht en zal dat met jullie bespreken. Als jury hebben we natuurlijk de nodige oplossingen gezien en ook de nodige verschillende uitvoer, wat erg leuk was soms. Ik zal ook de jury invoer & uitvoer bespreken. Ik hoop dat de gene die de opgave goed hadden hun strategie en algoritme uit willen leggen.Zoals jullie allemaal wel gemerkt hebben was het een pittige opgave, die vooral door de vele mogelijkheden niet bruteforce, recht toe recht aan, of recursief op te lossen was. Ook met de jury input hebben we daar natuurlijk rekening mee gehouden
.De strategie die ik gevolgd heb, en volgens mij velen met mij is de volgende:
Als je goed naar een rij kijkt. Is dat een rij van blokjes die aan of uit kunnen zijn. In het voorbeeld hebben we expres een lengte van 8 genomen om de overeenkomst met een byte nog beter op te laten vallen
. (max van 30 is ook niet willekeurig aangezien er vaak 32 bits in een integer passen )Deze puzzel lijkt dan ook erg sterk op een bitpatroon en zo heb ik het ook benaderd. Ik heb natuurlijk een aantal van zulke puzzels opgelost en gekeken wat de beste taktiek is. Wat je in het begin doet is kijken welke blokjes je zeker in kunt vullen. En deze blokjes vul je dan ook in. Dan ga je kijken welke blokjes zeker leeg moeten blijven en je zorgt dat deze ook leeg blijven Wat ik heb gedaan. Ik heb van alle mogelijkheden (als een veld 8 breed is passen er in de breedte 2 tot de 8-ste macht verschillende patronen) die ik met een simpel for loopje bereken. Het aantal enen bepaald en geordend op dit aantal opgeslagen. Als ik nu een patroon heb heb ik al ruim 60% procent van de mogelijke invoeren gefilterd. Van de mogelijkheden die dan nog over blijven bereken ik het patroon. Als dat berekende patroon overeenkomt met het patroon wat het moet zijn. Sla ik dat op bij de mogelijken voor die rij. Uiteindelijk heb ik dus een beperkte lijst met mogelijkheden over voor die rij. (sneller als dat het met bruteforcen zou lukken
) Van deze lijst ga ik kijken welke blokjes overal aan zijn. Om dat ik deze mogelijkheden in integers heb opgeslagen is een simpele AND operatie genoeg. Het bitpatroon wat nu overblijft sla ik op met waarde 2. Dan doe ik op de mogelijkheden nog een OR om te kijken welke eventuele gevuld kunnen en belangrijker welke zeker niet.Voordat ik aan de kolommen begin. Normaliseer ik die eerst. Ik ga kijken of een bepaalde column al aan het patroon voldoet en zo ja dan zet ik alle eventuele (met de waarde 1) op 0.
Dan ga ik alle mogelijkheden voor de kolommen af en volg hetzelfde patroon, mogelijkheden berekenen, normaliseren etc.
Als je geluk hebt ben je nu klaar, als je geen geluk hebt niet.
En natuurlijk hadden we een dergelijke ingewikkelde testcase dat het met deze taktiek niet altijd mogelijk was.
wat ik dan deed is nogmaals de mogelijkheden bepalen maar dan niet alleen van het vooraf gegeven patroon maar ook van de blokjes die al zeker zijn. Dat doe je weer met normaliseren, zowel rijen en kolommen etc.
Ik weet (bijna) zeker dat deze tacktiek werkt ik heb alleen geen tijd meer gehad om het te bewijzen
. Maar het feit dat we een aantal goede inzendingen binnen hebben gehad bewijst dat de opgave zeker te doen was JRobert zal de testset bespreken
succes met opgave 2
. Door de breedte van 2, werkt je algoritme alleen op randvoorwaarden, bovendien is het een invoer die niet snel door de programmeur gebruikt zou worden. In het begin van de week liepen de meeste programma's hierop vast en ook werd hier meestal duidelijk als de assen waren verwisseld.
)
).
. Bovendien zaten hier voor het eerst 3 lengtes per rij in.:strip_icc():strip_exif()/u/854/tmp18467.jpg?f=community)
x en y omgekeert 
:strip_icc():strip_exif()/u/13964/crop66d0a93a33207_cropped.jpg?f=community)
/u/9716/ninja%2520duck.png?f=community)
:strip_exif()/u/14220/tweakers_na_rotate.gif?f=community)
:strip_icc():strip_exif()/u/7418/the_hat_icon.jpg?f=community){kind=icon}