Trädvy Permalänk
Medlem
Plats
Sthlm
Registrerad
Okt 2001

ETt programmeringspuzzel

Surfade runt och hittade det här problemet i ett inlägg på lambda-the-ultimate som jag tänkte att någon kanske skulle tycka var kul att fundera över:

Citat:

Your stair-climbing robot has a very simple low-level API: the "step" function takes no argument and attempts to climb one step as a side effect. Unfortunately, sometimes the attempt fails and the robot clumsily falls one step instead. The "step" function detects what happens and returns a boolean flag: true on success, false on failure. Write a function "step_up" that climbs one step up (by repeating "step" attempts if necessary). Assume that the robot is not already at the top of the stairs, and neither does it ever reach the bottom of the stairs. How small can you make "step_up"? Can you avoid using variables (even immutable ones) and numbers?

Inte så jättelurigt kanske, men det finns ett par fällor att akta sig för om roboten är riktigt klumpig

AK47s for everyone! - Angry mob
Since NaN /= NaN, I think, we should decipher 'NaN' as 'Not a NaN' - Miguel Mitrofanov
(Varför är människan så benägen att tro på Gud?) Antagligen har det lönat sig och evolutionen har drivit fram sådana hjärnor. - Anon

Trädvy Permalänk
Medlem
Plats
Nord-Trøndelag
Registrerad
Jul 2003

Jag tror jag har en lösning, PM:ar så jag inte sabbar för de andra.

Trädvy Permalänk
Medlem
Plats
Singapore
Registrerad
Okt 2003

Kan ge ett litet tips:

tänk rekursivt. funktionen kan skrivas på en rad

Dold text
Trädvy Permalänk
Medlem
Plats
Göteborg
Registrerad
Jan 2007
Citat:

Ursprungligen inskrivet av ChristofferC
Kan ge ett litet tips:

tänk rekursivt. funktionen kan skrivas på en rad

Dold text

Tänk om roboten är så klumpig att funktionen ger stack overflow?

Dold text
Trädvy Permalänk
Medlem
Plats
Singapore
Registrerad
Okt 2003
Citat:

Ursprungligen inskrivet av You

Tänk om roboten är så klumpig att funktionen ger stack overflow?

Dold text

Då är roboten defekt och det spelar ingen roll om det blir stack overflow.

Dold text
Trädvy Permalänk
Medlem
Plats
Sthlm
Registrerad
Okt 2001

Humm, blir en ganska trist tråd om alla PMar mig Bra att ni började med [spoiler.]-taggen istället även om det oxå börjar bli lite onödigt, inte direkt så att man läser hela tråden om man inte är ute efter att se hur andra löst det eller problem man kan få ändå?

You:

Det går utmärkt att skriva en enradare utan stackoverflow om man gör det i ett språk med tailcall-optimering

Dold text

AK47s for everyone! - Angry mob
Since NaN /= NaN, I think, we should decipher 'NaN' as 'Not a NaN' - Miguel Mitrofanov
(Varför är människan så benägen att tro på Gud?) Antagligen har det lönat sig och evolutionen har drivit fram sådana hjärnor. - Anon

Trädvy Permalänk
Medlem
Plats
Singapore
Registrerad
Okt 2003

Skippar spoiler nu...

Utan rekursion så kan vi inte komma undan en räknare som håller koll på vilket trappsteg vi står på. Med tail call-optimering så måste alltså en räknare introduceras. Can't have your cake and eat it...

Trädvy Permalänk
Medlem
Plats
Sthlm
Registrerad
Okt 2001

Nej, du har givetvis rätt i att någon form av räknare kommer att behövas, men det gäller alla lösningar skulle jag påstå. Misslyckas step 20 ggr i rad, så måste man givetvis hålla rätt på det, antingen genom att ha stackat upp 20 anrop på sin stack som då blivit en form av en räknare, med en vanlig variabel eller på något annat vis.

Eller så drar man gränsen vid vad man faktiskt skriver, och då går det utmärkt att göra det utan variabler och siffror i många språk.

AK47s for everyone! - Angry mob
Since NaN /= NaN, I think, we should decipher 'NaN' as 'Not a NaN' - Miguel Mitrofanov
(Varför är människan så benägen att tro på Gud?) Antagligen har det lönat sig och evolutionen har drivit fram sådana hjärnor. - Anon