Full screen mode (F11) recommended

Click or tap anywhere to start

Programming

An Introduction to Computer Science with Dieter Schlau

let rec fortytwo (f : 'a -> ('a * bool)) (s : 'a) = 
 let (n, b) = f s
 in  if b then fortytwo f n
         else n
Kaminfeuer
Flamme
Glühbirne
I am Dark Dieter
Dieter Schlau
Pergament
f x y = y + 1 if x = 0
f x y = f (x - 1) 1 if x > 0 and y = 0
f x y = f (x - 1) (f (x, y - 1)) else
Dark Dieter Rises
Exercise Felix Freiberger
Special Thanks Yannick Forster Janine Lohse
Music
The Thunderstorm Karstenholymoly
They're coming... Zapac
Never Heard a Rhyme Like This Before Scott Altham
Narrator Felix Freiberger
Web Developement Felix Freiberger
with thanks to Gregory Stock
Images
Blitz bei Nacht AndreasF Headphone symbol George Shuklin
Kaminfeuer David Boozer Flamme Ryan Mahle
Lampe Pexels Pergament ArtsyBee
Dieter Schlau Joaquim Alves Gaspar
Fonts 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.

Programming – An Introduction to Computer Science with Dieter Schlau

Part 1


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 procedures have been deleted (yes, even your beloved procedures 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 procedure except fortytwo.

  1. After you've realized that fortytwo now is your only way to use recursion, take a closer look at this procedure. What is its type scheme? What does it do? How can it help you write recursive procedures?

  2. Familiarize yourself with fortytwo: Write a procedure fac : int -> int such that fac n computes the factorial n! by repeated multiplication. Remember the restrictions given above!

  3. Make yourself feel at home in your interpreter again! Declare your favorite procedures iter, first, and forall anew.

Part 2


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 procedure 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 procedure. Or can it?

  1. 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.

  2. Now solve the ghost's challenge.

    Under the known constraints, declare a procedure f : int -> int -> int with the behavior given above. Use only fortytwo and auxiliary procedures that you have already declared with fortytwo.

    You might be able to mild-manner the ghost by using only constructs introduced in the first three chapters of the book (in particular by not using lists). Mild-mannered spirits tend to be generous in giving bonus Dieters!

Part 3


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.

Formalities

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. Your team may consist of 1-4 members. You can see how to register teams here in the forum. Finally, please submit all files in compressed form as one .zip file. Alternatively, you may submit your explanations in the form of a radio play, which you include as an .mp3 or .m4a file with the .zip file. Good solutions whose explanations are submitted as a radio play will be rewarded with bonus Dieters!

Test your solutions before submitting them. Submissions that do not compile 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 24.11.2020 um 23:59 Uhr at your personal status page. If you have any questions, please contact Dark Dieter in the forum.

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 time of the kNobel tutorial for this task will be coordinated with the participants.

All tasks solved? Great, then we can continue.