Tonights theme is Logic Puzzles. We have here two logic problems found in section 4.3.2 of "The Structure and Interpretation of Computer Programs" (SICP).
Please code and share your solution online at: http://www.scalapuzzle.com/dojo/index/550154DC80 Click "Enter" to be asigned an avatar.
While these puzzles can likely each be solved in about 15 minutes by hand, the goal tonight is to write a program in such a way that it leaves us confident in it's correctness. This should be an interesting way to explore scala's expressive capability. Can we construct or evnision a convenient scala DSL for working with logic puzzles?
More Information:
-
SICP has treatments on logic programming and nondeterministic computing available online. See chapter 4 sections 2 and 3: https://mitpress.mit.edu/sicp/full-text/book/book-Z-H-25.html#%_chap_4
-
I personally recommend using "The Reasoned Schemer" as an introduction to Logic Programming: https://mitpress.mit.edu/index.php?q=books/reasoned-schemer
The following is exercise 4.43 from SICP. It was first published by Hubert Phillips in "Problematical Recreations" by Litton Industries.
Mary Ann Moore's father has a yacht and so has each of his four friends: Colonel Downing, Mr. Hall, Sir Barnacle Hood, and Dr. Parker. Each of the five also has one daughter and each has named his yacht after a daughter of one of the others. Sir Barnacle's yacht is the Gabrielle, Mr. Moore owns the Lorna; Mr. Hall the Rosalind. The Melissa, owned by Colonel Downing, is named after Sir Barnacle's daughter. Gabrielle's father owns the yacht that is named after Dr. Parker's daughter. Who is Lorna's father?
Extensions: How many solutions are there if we are not told that Mary Ann's last name is Moore?
The following is exercise 4.42 from SICP. It was first published by Hubert Phillips in 1934. Learn more about Lie Detection puzzles at: http://mathlair.allfunandgames.ca/liedetection.php
Five schoolgirls sat for an examination. Their parents -- so they thought -- showed an undue degree of interest in the result. They therefore agreed that, in writing home about the examination, each girl should make one true statement and one untrue one. The following are the relevant passages from their letters:
Betty: "Kitty was second in the examination. I was only third."
Ethel: "You'll be glad to hear that I was on top. Joan was second."
Joan: "I was third, and poor old Ethel was bottom."
Kitty: "I came out second. Mary was only fourth."
Mary: "I was fourth. Top place was taken by Betty."
What in fact was the order in which the five girls were placed?
Extensions:
A) As it happens, one of these letters is redundant. That is to say, you come to exactly the same conclusion is logically inferred without this letter. Which one is it?
B) The girls later realize that it's actually quite trivial to deduce their rankings. To remedy this, Betty and Ethel tweaked their statements:
Betty: "Kitty was first in the examination. I was only second."
Ethel: "You'll be sad to hear that I placed last. Joan was third."
How many consistent orderings are possible now? Were they successful -- can any girls' position be definitely inferred?