Recreational puzzles require only elementary knowledge. It should be easy to understand and it shouldn’t be trivial to solve. Sometimes these problems can be solved analytically. This short entry is about how might computers help us.
Puzzle 1
The string a1 ^ a2 ^ a3 is ambiguous because it could mean (a1 ^ a2) ^ a3 or a1 ^ (a2 ^ a3). There are two different formulas from that string. How many different formulas can the string a1 ^ a2 ^ … ^ an produce?
How might we use the computer to help us?
- Naïve way of modelling enumerating the possibilities and keeping track of which has been seen.
- Find a pattern and abstract the problem away.
Einstein problem
How might we use the computer to help us?
- Enumerate all possibilities and eliminate them. We can prune the possibility tree early.
The language perfect for this is prolog. http://swish.swi-prolog.org/example/houses_puzzle.pl
Weighing problem
Simple version: 9 balls, one is lighter, how can we find in 2 weighings which ball is the lighter one? Another version: 9 balls, one counterfeit is either lighter or heavier. How can we find in 3 weighings which ball is it?
Perhaps to way to approach this is to define what a sensible output is.
- Do we expect the program to be interactive, where the user has to tells it the output of the weighing? This might require the solution to already be solved in the first place
- Output a
Regex puzzle
Link: http://www.bbc.co.uk/programmes/articles/5LCB3rN2dWLqsmGMy5KYtBf/puzzle-for-today
Given the puzzle above, can we write a program that solves this?