#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!

Pokemon TCG: Greedy Dice

Pokemon have been quite a thing in the Sniff household for the last year or two (before "Go" and Sun and Moon made them trendy again), but a recent expansion has been into the Trading Card Game. For those who haven't played, its a card game played with Pokemon cards. However while the basic game is reasonably fun, what makes it interesting is that you can choose what cards make up a your deck. When you get ripped off at Asda's for a "booster pack" it provides 10 new cards, which you can use to replace  cards previously in your deck. Generally you can think of it as a giant game of rock paper scissors, where some cards are better than others, but even some of the weaker ones can come into their own under the right circumstances, so picking the right cards to use is critical.

One card such card is called "Greedy Dice". Within the game there is a pile of 6 "prize" cards, dealt randomly from your deck at the start of the game. Each time you knock out an opponent you get a prize card from your own pile, and if you get all 6 you win! The rule for greedy dice is, if its drawn from the prize pile, you toss a coin and if its heads you get to take another prize card! Two for the price of one!

However once you actually think about it, is it really such a great card to have in your deck? You're limited to 60 cards, so if you put a GD card in, you need to take something out, so you need to be pretty sure its worth it.

So lets do the maths... from 60 cards you have a 1 in 10 chance that one of the 6 prize cards is the GD card. So you'll get something good 1 game in 10? Well not so fast... there are six prize cards, but GD is only useful if one of the first 5. Getting to take an extra prize card does'nt' really help if you've already won. Worst, we forgot about the coin toss, so we get a benefit less than 1 game in 20.

OK that's a bit pointless, but what if we go for it! You're allowed to have up to 4 of each card in your deck, so what happens if we put 4 of them in. That's a big chunk of deck space, but hopefully we'll start to get something out of it...

Now the maths gets a bit more complex, so lets write a program:

make cardsInDeck number 60

make cardsInPrizes number 6

make greedy number 4

make cards list of boolean

make prizes list of boolean

So here we've got 60 cards in a deck, 6 of them are placed as prizes, and of the whole deck 4 of them are greedy dice. To represent the deck and the prizes I've made two lists of booleans - we don't actually care what the cards are, so I'm simply going to store yes or no to record if its a GD.

when game

.delete all of cards

.delete all of prizes

.

.repeat cardsInDeck

..add no to cards

.

.repeat greedy

..delete item 1 of cards

..add yes to cards

So here we go setting up a game. We clear out the cards, and the prizes, and then add 60 regular cards to the list. Then we replace 4 of those with greedy dice. Now we're ready to play!

The game starts when we deal our 6 prizes:

.

.repeat cardsInPrizes

..set deal to pick random 1 to length of cards

..add item deal of cards to prizes

..delete item deal of cards

.

Here we pick six random cards from the deck and place them in the prizes. Finally we just need to see you many of the first 5 prizes are GD:

.

.repeat cardsInPrizes-1

..if item 1 of prizes = yes

...if pick random 1 to 2 = 1

....change found by 1

..delete item 1 of prizes

We pick up the first prize card and if its a GD we toss a coin. If its heads then we've found (and successfully used) a Greedy Dice card. If its tails then we actually loose out in the game, as normally we'd get a useful card as a prize - GD is useless except to win a second prize. We keep track of the number of times we benefit.

make games number 1000000

when start

.set found to 0

.repeat games

..broadcast game and wait

.say join  "found "  join [found]  join " in "  join [games ] " games"

.say [found/games]

Now all we need to do is play a million games! A fraction of a second later, we discover we got an extra prize 167360 times in 1 million games. Thats 16.7% or about once every 6 games.

Of course I'm not the first person to figure this out:  Here some one comes up with the number: 15.83% That's a little but lower than our result, but you read closely you'll see that he's calculated the probability that you'll get one or more useful GD in any game, whereas we've counted the number of times GD's help - sometime more than one per game.

To make the two calculations match, we need to change our scoring:

.

.repeat cardsInPrizes-1

..if item 1 of prizes = yes

...if pick random 1 to 2 = 1

....change found by 1

....stop script

..delete item 1 of prizes

Now when we get a good GD card we call it a win for that match, and stop searching. Doing that we get an exact match up.

So not looking good, and about 1 game in 6 to see any benefit. However if you're new to TCG you might want to try the half deck variant - 30 cards and 3 prizes makes the games a little quicker, and its much easier to build a deck from the the cards you happen to have, rather than having to buy extras to make up a sensible 60. If we have 4 GD from 30 we're more likely to pick them for each prize slot (at the cost of taking up a greater proportion of deck space), which should help... except now we only draw 2 useful prize cards instead of 5, bringing the gain down to a useless 13%.

Either way you can probably do something more interesting with those 4 card slots than GD. Maybe in some future expansion they'll add a trainer card which lets you do something more useful with the GD card, but for now its just a dead card!

S^3 (Sniff Soduku Solver)

We've had a few sunny days recently - the sort of days where some people might sit on the balcony with a drink and maybe relax doing a crossword puzzle. Trouble is I'm rubbish at crosswords. Soduku looks more interesting, but it just seems like mental busywork. Filling in those boxes seems like the sort of thing you should get a computer to do... So... Sitting out, with a drink and writing a program to solve puzzles! That's more the thing.

Much as we did for some some of the other puzzle solving programs we start by trying to represent the problem on the computer (while code is the exiting part of programming - its the verbs, the doing, its the "nouns" are at least as important).

make fixed list of strings

when loadFixed

.delete all of fixed

.add"800000000" to fixed

.add"003600000" to fixed

.add"070090200" to fixed

.add"050007000" to fixed

.add"000045700" to fixed

.add"000100030" to fixed

.add"001000068" to fixed

.add"008500010" to fixed

.add"090000400" to fixed

Here I've encoded a puzzle as a list of strings - just as in the recent barcode examples, though Soduku looks like a game about numbers its actually a game about symbols. It could just as easily by rebranded to use the letters a-i and would work exactly the same. However its worth noting that there are two kinds of symbols on a soduku board - the ones that are fixed, and the ones you can change. We want to leave the fixed ones as they are so we make a copy that we can change:

make board list of strings

when loadBoard

.make counter number

.delete all of board

.repeat 9 using counter

..add item counter of fixed to board

We're also going to need a way to print out the board. Initially I just did something simple:

when showBoard

.make row number

.repeat 9 using row

..say  item row of board

but then at the end I made it a bit more pretty:

when showBoard

.make row number

.make col number

.make text string

.repeat 9 using row

..if row = 4 or row = 7

...say "---+---+---"

..set text to ""

..repeat 9 using col

...if col=4 or col=7

....set text to join text "|"

...set text to join text letter col of item row of board

..say text

.say ""

.wait 0.1 secs

Now at some point we're going to need to write a value into a square, so lets write the code to do that:

make x number

make y number

make val number

make boardOK boolean

when replaceLetter

.make counter number

.make newLine string

.set newLine to ""

.repeat x-1 using counter

..set newLine to join newLine letter counter of item y of board

.set newLine to join newLine [val]

.repeat 9-x  using counter

..set newLine to join newLine letter counter+x of item y of board

.replace item y of board with newLine

Here we replace letter x of item y of board with [val]. Unfortunately Scratch/Sniff don't support that operation directly (it would be rather neat if it it did, and I may consider quietly adding it...), so we copy the line a letter at a time into newLine, substituting val for the appropriate square.

Now its time to actually start thinking about how to solve the problem! What we've done so far is "bottom up" programming. I've built a load of useful things I'm pretty sure I'm going to need, so now I can use them to express the rest of the problem using those tools. The alternative is top-down. Build the program assuming the tools you need exist, then once the whole thing is written go back and fill in the missing operations.

The advantage of top down is that you know what tools you need to build, but the neat thing about bottom-up is that you start running the code that you have to do things immediately, even if you're not ready to solve the whole problem. A smart programmer uses both "as appropriate".

We're going to go through the board one square at a times and write a value in that square. Then we check if the board is valid. If it is we'll move on to the next square. If not we'll try a different value in this square. If there's no valid number that can go in this square, then we need to go back and change the previous square (which in turn may require going back to the previous square!).

This is exactly what a human player would do, but they would use skill and judgement to pick a square with only one or two possible values, so that they never have to go back too far. As we're doing this on a computer which has no skill and judgement then we'll just work through the square from top left to bottom right. This will mean we have to try a lot more combinations that a human would, but foruntatly the computer is super good at that!

If we consider what that looks like at the top level:

when start

.make counter number

.broadcast loadFixed and wait

.broadcast loadBoard and wait

.broadcast showBoard and wait

.set x to 1

.set y to 1

.repeat until y =10

..set val to value of letter x of item y of board

..broadcast checkBoard and wait

..if boardOK

...broadcast advance and wait

..else

...if val=9

....broadcast retreat and wait

...else

....change val by 1

....broadcast replaceLetter and wait

.broadcast showBoard and wait

After some running the initialisation, and printing the initial board (which we've already done - bottom up), we start at the top left and loop until we've covered the whole board. Each time round the loop we pull out the value of the current square, and check if the its a valid move. If it is OK then we move on to the next square. If its not OK then we need to fix that. The easiest way to fix that is to add one to the value in the current square and go round again to see if that fixes things. Unfortunately that's not always possible - if we've already tried all 9 values in that square and none of them have worked, then we need to retreat.

If the board is solvable then eventually we'll reach the bottom, and we can print out the completed results (of course during testing we can use the showBoard script a lot more to check the progress, but I've removed those as they're not needed in this final version).

Now we've switched to a top-down approach - I need to work out how to write checkBoard, advance and retreat, but once I do this should just start working.

when advance

.change x by 1

.if x=10

..set x to 1

..change y by 1

Here you can see advance is pretty simple - we just increment x, and if we've reached the end of the line, move on to the next line. However there's an implicit trick in this code... we don't have to worry about fixed positions on the board. Ideally we should skip over them, because we're not allowed to change them, but when we advance we're actually safe to advance to a fixed square, because when we test that its OK the next time round the loop we know that is will succeed because if it wasn't OK, then we'd already have noticed. We will never change fixed squares, so if we advance to a fixed square it must be OK.

This isn't the case when we retreat - we're moving back to the previous modifiable square, which makes this a bit more complex:

when retreat

.forever

..if value of letter x of item y of fixed = 0

...set val to 0

...broadcast replaceLetter and wait

..change x by -1

..if x=0

...set x to 9

...change y by -1

..

..if value of letter x of item y of fixed = 0

...set val to value of letter x of item y of board

...if val < 9

....change val by 1

....broadcast replaceLetter and wait

....stop script

If the square we're retreating from isn't fixed, then we set it to zero on the main board. Then we move back a square by subtracting 1 from x, and then checking if we need to move up a line.

Now we're on the new square we need to check if its fixed. If it's not fixed then we incremented it, to get the new value for that square, and stop the sciprt. On the other hand if it is fixed, or its already reached 9, then we need to retreat further, so we go back around until we find a previous square that we can increment.

The only thing left to add it the code to check if a current board position is legal. However we don't need to check the whole board - just that the current square doesn't make the new position illegal:

when checkBoard

.make dx number

.make dy number

.

.if val = 0

..set boardOK to no

..stop script

.

.set boardOK to yes

.repeat 9 using dx

..if not dx=x

...if value of letter dx of item y of board = val

....set boardOK to no

....stop script

.

.repeat 9 using dy

..if not dy=y

...if value of letter x of item dy of board = val

....set boardOK to no

....stop script

.

There are 4 steps to doing that, and the first three shown above are pretty easy: if the current square is 0 (empty) then that's not OK. Then we go along the line - if it contains the current value of the test square at a location other than the current square then that's not allowed either. Similarly for the column.

.set baseX to x-((x-1) mod 3)-1

.set baseY to y-((y-1) mod 3)-1

.repeat 3 using dx

..repeat 3 using dy

...if not (baseX+dx=x and baseY+dy=y)

....if value of letter baseX+dx of item baseY+dy of board = val

.....set boardOK to no

.....stop script

The final check is to make sure that each 3x3 group is valid. The tricky part of this is figuring out which square we're in without writing a ton of code. Unfortunatly to make things worse, Scratch/Sniff are "index from 1" languages. There's nothing wrong with that, and it makes some things much clearer, but this particular bit of code is much more complex. Basically we're dividing by 3 and keeping the remainder to find out where we are in the square. Then we subtract that from the position to find the top left corner of the square. The extra -1's are needed to make it work properly, so that when we access square 1,1 of the group we get the right position.

Once we have the origin of the 3x3 group we just loop over the rows/columns checking each square. If we find a cell other than the one we're testing which contains the value, then we have a bad square again.

And that's it! Now we have all the parts, when we run it, it prints out the initial board:

800|000|000

003|600|000

070|090|200

---+---+---

050|007|000

000|045|700

000|100|030

---+---+---

001|000|068

008|500|010

090|000|400

and about a second later it prints out the answer:

812|753|649

943|682|175

675|491|283

---+---+---

154|237|896

369|845|721

287|169|534

---+---+---

521|974|368

438|526|917

796|318|452

To get there the code considers over half a million possible board positions! But that's OK, because that's what computers are good for.