⌛
Headphones
recommended
Full screen mode (F11) recommended
Click or tap anywhere to start
An exercise by Jonathan Gärtner. Based on an exercise by Felix Freiberger, with special thanks to Yannick Forster and Janine Lohse.
Lightning:
AndreasF, Blitz bei Nacht 003, CC BY-SA 2.5
Headphone symbol:
Original uploader was Gamma-aspirin at ru.wikipedia
SVG autoconverted by Inkscape by George Shuklin, Zvuk-001, CC BY-SA 3.0
Fireplace:
David Boozer, CC0
Flame:
Ryan Mahle from Sherman Oaks, CA, USA, Fireplace-RM, Farbgebung angepasst von Felix Freiberger, CC BY 2.0
Lamp:
Pexels, CC0
Parchment:
ArtsyBee, CC0
Dieter Schlau:
Joaquim Alves Gaspar, The Photographer, CC BY-SA 3.0
Dark-Dieter-Avatar:
Emoji artwork by EmojiOne, CC BY 4.0
Jenna Sue:
Jenna Sue Design Co.
Zombie Holocaust:
Sinister Fonts
This kNobel exercise is provided in the form of a radio play.
Make sure your audio setup is working, and then you're ready to go!
Alternatively, you can look at the written version.
It's getting late again, and you're sitting with your prospective past best friend Dieter Schlau in front of the fireplace, browsing through the Programming 1 book. While you ponder the difference between static and dynamic semantics, sleep overcomes you.
You are awakened by a soft buzzing.
When you open your eyes, you see that Dieter Schlau has grabbed your laptop and is experimenting with the interpreter – and of course, he is pushing all the wrong buttons! Horrified, you run to your laptop, but it is too late: All previously declared functions have been deleted (yes, even your beloved functions iter
, first
, and forall
are gone)!
Still half asleep, you can barely type
let rec fortytwo (f : 'a -> ('a * bool)) (s : 'a) = let (n, b) = f s in if b then fortytwo f n else n
into your interpreter before Dieter's actions have made the rec
keyword permanently unusable.
Shocked, you look at Dieter. But just as you are about to confront him, he quickly mumbles something that roughly resembles “gotta go” and runs for the door. After briefly giving chase, you give up: Dieter has escaped.
Unfortunately, you must now solve the following tasks without rec
and any auxiliary function except fortytwo
.
After you've realized that fortytwo
now is your only way to use recursion, take a closer look at this function. What is its type scheme? What does it do? How can it help you write recursive functions?
Familiarize yourself with fortytwo
: Write a function fac : int -> int
such that fac n
computes the factorial
n!
by repeated multiplication.
Remember the restrictions given above!
Make yourself feel at home in your interpreter again! Declare your favorite functions iter
, first
, and forall
anew.
Tired, but somewhat content with your work, you put your Programming 1 book back on the table in front of the fireplace and finally go to bed. As your head sinks into the pillow, sleep overcomes you…
When you wake up again, you hardly recognize your room: it is way too cold, and somehow, the light is flickering…
Dieter seems to be back in your room and is sitting by the fireplace with his back turned to you. You get up and sleepily mutter, “Dieter, why is it so cold? Did you put out the fire?” In lieu of answering, Dieter slowly gets up and turns to face you. The room somehow seems to get colder and colder. “I am not Dieter”, Dieter says, now looking straight into your eyes. And he seems to be right: The figure standing there looks surprisingly like your friend Dieter Schlau, but it is paler, thinner, and for some reason you cannot fathom, looking at him sends shivers down your spine. “I am Dark Dieter. Your dear friend Dieter Schlau is…” and at that moment Dark Dieter's lips curl into a devilish grin, “…lost forever.” You inhale sharply and your knees suddenly soften. “Dieter? Lost?”, you gasp.
“There is only one way to save him. Implement this function before the sun rises again:
If you do not succeed, your friend Dieter will never return. An impossible task, given the mischief your little friend has caused already. He has triggered his own demise.”
With these words, and roaring laughter, Dark Dieter throws your Programming 1 book into the fireplace and disappears from the room. Page by page, any hope of rescue is consumed by the flames.
Since Dark Dieter has left the room, it has become noticeably warmer. Drenched in cold sweat, you sit down by the fireplace again.
It can't be that tricky to implement the function. Or can it?
Is Dark Dieter right? Are there any functions that you cannot implement in your interpreter anymore?
If yes: Specify such a function and explain briefly why it can no longer be implemented.
If no: Explain briefly why.
In both cases, only a short, intuitive explanation is required.
Now solve the ghost's challenge.
Under the known constraints, declare a function f : int -> int -> int -> int
with the behavior given above.
Use only fortytwo
and auxiliary functions that you have already declared with fortytwo
.
You might be able to mild-manner the ghost by using only constructs introduced in the first chapter of the book (in particular by not using lists). Mild-mannered spirits tend to be generous in giving bonus Dieters!
With the last of your strength, you type the last closing parenthesis of your implementation into the interpreter, and slowly drift away…
The sun is shining. A loud “Ding Dong!” startles you awake. Was that the doorbell? Still tired, you shuffle to the door, open it – and in front of you stands your friend Dieter, smiling at you. With a happy “I must have broken something yesterday, but we'll fix that!” he hops into your apartment. He does not seem to remember the night's adventures. As you follow Dieter back to the couch, you begin to wonder whether Dark Dieter was just a dream.
The table by the fireplace lies empty.
Please submit your OCaml programs in a .ml
file so that they are directly executable in an interpreter.
In addition, please always provide an explanation of your code.
You may choose to write the explanations and answers in a separate .txt
or .pdf
file. Finally, please submit all files in compressed form as one .zip
file. Alternatively, you may submit your explanations in the form of an audio drama, which you include as an .mp3
or .m4a
file with the .zip
file. Good solutions whose explanations are submitted as an audio drama will be rewarded with bonus Dieters!
Test your solutions before submitting them. Submissions that do not execute may be awarded 0 points.
If you think you have found a particularly nice solution, you can try to explain why your solution is particularly nice for a chance to be awarded bonus Dieters.
Upload your proposed solution to your personal status page no later than 7.11.2024 um 23:59 Uhr at your personal status page. If you have any questions, please contact Dark Dieter in the forum. If you have not formed a kNobel team yet, or wish to make changes to your kNobel team, please contact Timo Treitz or Edouard Müller.
Terms and conditions apply. Relatives and employees of Dieter Schlau and Dark Dieter cannot participate. Offer not valid for permanent residents of Schleswig-Holstein.
The task and related advanced topics from different areas of computer science will be discussed in a kNobel tutorial, the date and time of which will be announced in the forum.