Robot Unlock levels 40-44

[Soultaker]

Robot Unlock is een programmeerspel (Windows-only, helaas, en ik kreeg het ook onder Wine niet aan de praat op Linux), een beetje als Manufactoria, TIS-100 of Human Resource Machine, maar dan wat primitiever.

De spelregels zijn een beetje op Befunge gebaseerd; ik zou ze hier kunnen herhalen maar als je het spel niet kent kun je het beter even installeren en zelf uitproberen.

Er zijn in totaal 44 levels. De eerste 39 heb ik zelf opgelost, maar nu wordt het lastig. Voor de volgende drie heb ik eigenlijk geen idee hoe ik ze moet aanpakken,omdat de vrije ruimte voor programmacode heel beperkt is (level 40 & 42) of ik geheugencellen tekort kom (level 41 & 42).

Level 40	Level 41	Level 42

Heeft iemand tips/nuttig inzicht voor deze levels?

[ard1998]

ik hoop dat deze spoilers je helpen gaan.

uitleg van de uitleg:

spoiler:

voor de uitleg
getal 1 = x
getal 2 = y
getal 3 = z
getal 4 = a (zet de waarde hiervan op 0 bij opdracht 41 en 42)

test 40:

spoiler:

Wikipedia: Bubblesort

test 41:

spoiler:

41: maak een loop die y aantal keer z optelt bij x (ongeveer zelfde principe als ik bij 42 opgeschreven heb)

test 42:

spoiler:

aangezien dat dit soort spellen over het algemeen geen hogere wiskunde zijn ga ik er van uit dat alle getallen netjes deelbaar zijn. x is je antwoord en y is je doel en z is de grootte van de stap. wanneer je z bij a optelt voeg je 1 aan x toe. herhaal dit totdat a gelijk staat aan y

Niet klakkeloos overnemen, maar denk na over hoe dit werkt. ik heb het vermoeden dat je het nodig hebt bij de laatste tests.

[ Voor 26% gewijzigd door ard1998 op 16-10-2017 10:51 ]

[Soultaker]

Hee Ard; bedankt voor de tips! Helaas denk ik dat de opgaven lastiger zijn dan je denkt (of je hebt nog een aantal trucs in gedachten die ik niet ken).

Voor level 40: bij een normale bubblesort heb je twee loop-indices, maar die heb je hier niet. Hoe bepaal je waar je de pointers plaatst? Hoe eindig je überhaupt de lus als je nergens state kan opslaan?

Bij een eerdere opgave (met een groter grid) heb ik wel kunnen sorteren door vijf vergelijkingen na elkaar te doen (eerste twee vergelijken, en als de eerste groter is dan de tweede, ze omwisselen; dan laatste twee vergelijken, etc.) De state wordt dan impliciet gecodeerd in je locatie op het grid. Daar lijkt hier geen ruimte voor te zijn, tenzij ik een enkele conditional-swap in een blok van 2x3 kan coderen, maar dat lijkt me sterk.

Overigens lijkt een Gnome sort me iets geschikter in deze situatie, juist omdat 'ie minder state nodig heeft. Nu ik er nog eens over nadenk past dat misschien wel; dan zijn er namelijk maar drie states in plaats van vijf, en heb ik ongeveer 2x5 instructies per state. Die ga ik nog eens proberen!

Voor level 41: dat is inderdaad de aanpak die ik wilde uitvoeren en dat zou prima lukken als ik een vijfde geheugencel zou hebben, maar met precies vier zie ik niet hoe ik 'y' bij 'x' kan optellen zonder 'y' kwijt te raken. In Brainfuck zou ik dat oplossen door y eerst naar een tijdelijk cel (hier: a) te verplaatsen, en daarna bij het terugverplaatsen ook x op te hogen. Maar dat werkt hier niet, omdat ik 'a' leeg moet laten om tegen te vergelijken. Alternatief kan ik van 'y' naar 'a' verplaatsen zolang 'a' < 'y'; dan eindig je met de helft in 'y' en de helft in 'a', maar hoe reconstrueer je daarna 'y'? Daar zit ik klem. (Ook moeten oneven getallen speciaal behandeld worden, maar dat is een bijzaak.)

Ik had het idee om dit ook te hardcoden, aangezien y en z relatief klein zijn (maximaal 20). Je kunt dan detecteren welke van 20 waarden y heeft, en afhankelijk daarvan zowel y herstellen als het getal bij x optellen. Maar het leek me dat dat vrij veel ruimte in beslag zou nemen. Aan de andere kant heb je bij die opgave ook veel ruimte (~270 vakjes), dus misschien is dat wel de bedoeling. Ik zal er nog eens over nadenken...

Voor level 42: helaas is het niet gegarandeerd dat y een veelvoud van x is (zie ook het voorbeeld onderaan de screenshot: 179/11=16). Maar al zou ik de aanname doen dat het wel zo is, dan zie ik nog steeds niet in hoe ik 'm op moet lossen. De opgave lijkt op 41 maar de beschikbare ruimte is heel beperkt. Ik denk dat ik deze nog even uitstel tot ik de andere opgaven opgelost heb.

[ard1998]

Soultaker schreef op maandag 16 oktober 2017 @ 21:52:
Voor level 40: bij een normale bubblesort heb je twee loop-indices, maar die heb je hier niet. Hoe bepaal je waar je de pointers plaatst? Hoe eindig je überhaupt de lus als je nergens state kan opslaan?

Soultaker schreef op maandag 16 oktober 2017 @ 21:52:
Hee Ard; bedankt voor de tips! Helaas denk ik dat de opgaven lastiger zijn dan je denkt (of je hebt nog een aantal trucs in gedachten die ik niet ken).

Voor level 40: bij een normale bubblesort heb je twee loop-indices, maar die heb je hier niet. Hoe bepaal je waar je de pointers plaatst? Hoe eindig je überhaupt de lus als je nergens state kan opslaan?

volgende keer aub spoiler tags gebruiken
ik ga het proberen iets gedetaileerder uit te schrijven

heb je genoeg geheugencellen om te hardcoden? je hoeft slechts drie maal 3 keer een velelijkling van 2 nummers te doen (eerst 1 en 2 dan 2 en 3 tenslotte 3 en 4) na 3 interaties heb je gegarandeerd de gesorteerde uitvoer zonder state nodig te hebben.

Soultaker schreef op maandag 16 oktober 2017 @ 21:52:
Voor level 41: dat is inderdaad de aanpak die ik wilde uitvoeren en dat zou prima lukken als ik een vijfde geheugencel zou hebben, maar met precies vier zie ik niet hoe ik 'y' bij 'x' kan optellen zonder 'y' kwijt te raken. In Brainfuck zou ik dat oplossen door y eerst naar een tijdelijk cel (hier: a) te verplaatsen, en daarna bij het terugverplaatsen ook x op te hogen. Maar dat werkt hier niet, omdat ik 'a' leeg moet laten om tegen te vergelijken. Alternatief kan ik van 'y' naar 'a' verplaatsen zolang 'a' < 'y'; dan eindig je met de helft in 'y' en de helft in 'a', maar hoe reconstrueer je daarna 'y'? Daar zit ik klem. (Ook moeten oneven getallen speciaal behandeld worden, maar dat is een bijzaak.)

Ik had het idee om dit ook te hardcoden, aangezien y en z relatief klein zijn (maximaal 20). Je kunt dan detecteren welke van 20 waarden y heeft, en afhankelijk daarvan zowel y herstellen als het getal bij x optellen. Maar het leek me dat dat vrij veel ruimte in beslag zou nemen. Aan de andere kant heb je bij die opgave ook veel ruimte (~270 vakjes), dus misschien is dat wel de bedoeling. Ik zal er nog eens over nadenken...

je hebt vier geheugencellen waarvan drie in gebruik de mogelijke procedure ziet er alsvolgt uit

1. verhoog x met z
2. verlaag y met 1
3. test of y groter is dan 0

(in dit voorbeeld gebruik je slechts drie geheugencellen)

Soultaker schreef op maandag 16 oktober 2017 @ 21:52:
Voor level 42: helaas is het niet gegarandeerd dat y een veelvoud van x is (zie ook het voorbeeld onderaan de screenshot: 179/11=16). Maar al zou ik de aanname doen dat het wel zo is, dan zie ik nog steeds niet in hoe ik 'm op moet lossen. De opgave lijkt op 41 maar de beschikbare ruimte is heel beperkt. Ik denk dat ik deze nog even uitstel tot ik de andere opgaven opgelost heb.

ik denk dat dit jouw loop word als det lukt om een loop te maken met zo weinig ruimte

1. verhoog x met z
2. verlaag y met z
3. test of y groter is dan 0

(Ook hier weer 3 geheugencellen nodig)

voor de loop hoop ik dat je een goto kan uitvoeren na een vergelijking (ga naar het begin van de loop als de conditie in stap 3 waar is)

Veel succes gewenst.

[NMe]

ard1998 schreef op maandag 16 oktober 2017 @ 22:53:
[...]

volgende keer aub spoiler tags gebruiken

Lijkt me nergens voor nodig in een topic waar zowel de titel als de topicstart al heel duidelijk aangeven dat er spoilers in staan.

[ard1998]

NMe schreef op dinsdag 17 oktober 2017 @ 13:52:
[...]

Lijkt me nergens voor nodig in een topic waar zowel de titel als de topicstart al heel duidelijk aangeven dat er spoilers in staan.

voor degene die hulp nodig heefd met 40 maar opgave 41 en 42 nog niet lezen wilt

ik geef toe dat dit een "als de wind uit de juiste hoek komt terwijl de zon en de maan in de juiste positie staan" reactie is

[Soultaker]

ard1998 schreef op maandag 16 oktober 2017 @ 22:53:
heb je genoeg geheugencellen om te hardcoden? je hoeft slechts drie maal 3 keer een velelijkling van 2 nummers te doen (eerst 1 en 2 dan 2 en 3 tenslotte 3 en 4) na 3 interaties heb je gegarandeerd de gesorteerde uitvoer zonder state nodig te hebben.

3x3 keer wordt te krap; ik had dacht ik 5x2 ruimte nodig per conditional-swap. Ik denk dat de gnome-sort aanpak meer succes heeft.

De pseudo-code daarvoor ziet er zo uit (met cellen gelabeld a, b, c, d):

1. if (a > b) { swap(a, b); };
2. if (b > c) { swap(b, c); goto 1; }
3. if (c > d) { swap(c, d); goto 2; }

(Op de laatste stap zou goto 1 in plaats van goto 2 ook kunnen). Deze moet ik nog uitproberen, maar het lijkt me simpel genoeg. Ik zal nog even laten weten of het me lukt.

Voor probleem 41:

1. verhoog x met z
2. verlaag y met 1
3. test of y groter is dan 0
(in dit voorbeeld gebruik je slechts drie geheugencellen)

Dat high-level plan lijkt me prima. De vraag is dus hoe je stap 1 kunt implementeren. De +-operator is bij deze opgave niet beschikbaar; je hebt alleen ++/-- (increment en decrement), en om met 0 te kunnen vergelijken heb je een cel nodig die je op 0 laat staan.

Anders geformuleerd: stel dat je drie cellen hebt, x y z. In het begin bevatten x en y willekeurige getallen, en z = 0. De vraag is dan: kun je 'y' bij 'x' optellen, en 'y' en 'z' met hun oorspronkelijke waarde laten eindigen? Bijvoorbeeld: (2 3 0) -> (5 3 0), of (4 1 0) -> (5 1 0).

Ik denk dat als dat probleem op te lossen is, ik er voor de rest ook wel uitkom. Maar dat is nu juist een lastig probleem. Als je één extra cel hebt (die op 0 begint), is het natuurlijk makkelijk.

[ard1998]

Soultaker schreef op dinsdag 17 oktober 2017 @ 21:22:
[...]

De pseudo-code daarvoor ziet er zo uit (met cellen gelabeld a, b, c, d):

1. if (a > b) { swap(a, b); }
2. if (b > c) { swap(b, c); goto 1; }
3. if (c > d) { swap(c, d); goto 2; }

kleine correctie in jouw pseudo-code

1. if (a > b) { swap(a, b); }
2. if (b > c) { swap(b, c); goto 1; }
3. if (c > d) { swap(c, d); goto 1; }

dat is zodat wanneer het laagste getal in d zit dat het nog steeds omlaag kan gaan naar positie a

Soultaker schreef op dinsdag 17 oktober 2017 @ 21:22:
[...]
Voor probleem 41:

Dat high-level plan lijkt me prima. De vraag is dus hoe je stap 1 kunt implementeren. De +-operator is bij deze opgave niet beschikbaar; je hebt alleen ++/-- (increment en decrement), en om met 0 te kunnen vergelijken heb je een cel nodig die je op 0 laat staan.

Ik denk dat als dat probleem op te lossen is, ik er voor de rest ook wel uitkom. Maar dat is nu juist een lastig probleem. Als je één extra cel hebt (die op 0 begint), is het natuurlijk makkelijk.

in dat geval kan je de vierde geheugen cel gebruiken om 0 in te bewaren en daarmee vergelijken.

(nu besef ik pas hoeveel werk de compiler en/of assembler van mij over nemen)

[Soultaker]

ard1998 schreef op woensdag 18 oktober 2017 @ 08:12:
kleine correctie in jouw pseudo-code

1. if (a > b) { swap(a, b); }
2. if (b > c) { swap(b, c); goto 1; }
3. if (c > d) { swap(c, d); goto 1; }

dat is zodat wanneer het laagste getal in d zit dat het nog steeds omlaag kan gaan naar positie a

Nee, dat is niet nodig. Op regel 2 vergelijk je immers b en c weer. In z'n algemeenheid hoef je alleen van de huidige positie naar de volgende/vorige te gaan.

Direct naar 1 gaan mág wel, zoals ik ook concludeerde:

Soultaker schreef op dinsdag 17 oktober 2017 @ 21:22:
(Op de laatste stap zou goto 1 in plaats van goto 2 ook kunnen).

Re: problem 40:

in dat geval kan je de vierde geheugen cel gebruiken om 0 in te bewaren en daarmee vergelijken.

Juist, en daar zit 'm de kneep: die extra geheugencel heb je bij dit probleem niet, vandaar de moeilijkheid.

[ard1998]

heh, ik dacht op de afbeelding echt 4 geheugencellen te zien. ik denk dat ik je dan niet verder kan helpen.