Sniff is a "Scratch-like" programming language that's designed to help Scratchers move gently from Scratch to more conventional languages. They can start writing programs, without having to learn a new language because Sniff is based on Scratch. They learn a little more about variables, compiling, syntax errors (!), and they can have fun controlling real hardware while they're doing it.

Monday, 4 September 2017

#IBrokeTheCode

We've been keeping a low profile over the summer, and while we were away I saw an activity at Butlin's, which was developed by Bletchley Park. There were three puzzle's, and each puzzle gave a combination which would open one of three safes. One puzzle was a Caesar Cypher, and another one was a sort of word search. The most interesting one was based on binary, and would make a good class exercise for anyone teaching this stuff. I've tried to reproduce it here:



17
5
13

1



?
2



?
4



?
8



?
16



?

4
2
1


We start out with a grid, and mark the squares so that the numbers on the left add up to make the number at the top. So 17 is 16+1, so we mark those two squares:




17
5
13

1
X X X ?
2



?
4

X X ?
8


X ?
16
X


?

4
2
1

Here's the completed grid. Next we read off the rows, to find what the numbers at the bottom add up to for each row. The first row is 4+2+1 which makes 7.



17
5
13

1
X X X
7
2



0
4

X X
3
8


X
1
16
X


4

4
2
1


Once we've done that for all of the rows we get the answer 70314, which would be the combination to the safe.

However that's not really what this post is about. Inside each of the three safe's there's a two digit number, so once you solve all three puzzles you have a 6 digit number, which opens the final safe!

Inside the final safe is a prize card, proving you solved all the puzzles.

However the prize card also has another puzzle on it.

Each of the letters A to F represent a
single digit. But which ones?
These are the rules:
A != B != C != D != E +D
A+B=C and D+E=F
A>B<C>D<E<F



Pretty much immediately I figured writing a Sniff  program to solve it would be the first thing I did when I got home!

A few months ago we wrote a sudoku solver which used backtracking to generate solutions to any puzzle. That would be a good approach to use here, but its a bit overkill - while that style of solution would be much more efficient in terms of computer time, this problem is simple enough that the computer can check every possible solution in seconds. I'm more worried about programmer time. It's also worth noting that while the sudoku solver might be run several times to solve different puzzles, here once the code is working, we're only going to ever run it once, so it really doesn't matter how long it takes - my time is more important than the computer's!


make count number
make word string
make ok boolean


when start
.repeat 1000000 using count
..set word to [ count ]
..broadcast check and wait
..if ok
...say word

The easiest way to solve this is to generate all of the possible values of A-F and see if they're a valid solution. As there are six digits, there are a million combinations, so we just count from one to 1,000,000. Then we turn that number into a string, and run a script to check if the proposed solution is "OK". If it is then we print out the answer we've found.

So far we could be checking for any set of rules, but next we need to fill in the check script to reject any invalid solutions:


when check
.make A number
.make B number
.make C number
.make D number
.make E number
.make F number
.
.set ok to no
.if not length of word = 6
..stop script
.

.set A to value of letter 1 of word
.set B to value of letter 2 of word
.set C to value of letter 3 of word
.set D to value of letter 4 of word
.set E to value of letter 5 of word
.set F to value of letter 6 of word
.
.#More Tests Here
.

.set ok to yes

this is the beginnings of our "check" script. We make 6 variables for the letters A to F, and we set OK to be no. Then we'll add a series of checks. If we make it all the way to the end then we've passed all the tests, and we've found a solution.

So far I've got the first test - if we don't have a 6 digit number to split up, so we bail.  If we do have 6 digits we can set the six variables.

.
.if A=B
..stop script
.if A=C
..stop script
.if A=D
..stop script
.if A=E
..stop script
.if A=F
..stop script
.
.if B=C
..stop script
.if B=D
..stop script
.if B=E
..stop script
.if B=F
..stop script
.
.if C=D
..stop script
.if C=E
..stop script
.if C=F
..stop script
.
.if D=E
..stop script
.if D=F
..stop script
.
.if E=F
..stop script
.

Testing to check that none of the letters are equal is a bit of a pain - we could do something smarter using two nested loops (and would have to if there were more letters involved), but this works for now. Rewriting this to index through the original word with two loop counters is left as a bonus question!

in fact reading the problem again as I write this, I realise its ambiguous. It seems pretty clear that the intention is that no to numbers are the same, but if we read line one, in the same was as we read line 3, then A!=B, but might be allowed to be equal to C (in which case B would be 0).  We've assume that all digits have to be different. Testing the other way is simpler.

The next few rules, while the look more complex are actually easier to implement:

.
.if not A+B=C
..stop script
.if not D+E=F
..stop script
.

Line two says the two additions must be true, so if they're not we bail again.


.
.if A<B
..stop script
.if B>C
..stop script
.if C<D
..stop script
.if D>E
..stop script
.if E>F
..stop script
.

Finally we check that the inequalities hold. We don't have to worry about the digits being equal (cause that's already tested), so we can just stop if A is less than B, or B > C. In fact some of these tests are redundant, as B can't be greater than C, as A+B=C, but there's little to be gained here by not checking again - that way if we do change the rules later on, then this test will still work.

The program generates 49 solutions, the first few of which are:


314257
314268
314279
325167
325178
325189

Once you see a few, its clear that the solution has two parts (which come from the second line). Once you've found a solution to the first 3 digits, there are potentially several solutions to the second three. I won't list all of the answers, as I don't want to give them all away!

1 comment:

  1. Puzzle sure seems tricky. It must have taken time to solve. Despite your experience I might use this puzzle somewhere soon. Brain games are always fun

    ReplyDelete