Fun with Goats

I was chatting with some kids at the weekend, and they were asking each other riddles. However these were more interesting than the usual puns and trick questions. Rather they were logic puzzles - "This statement is false" type of thing. Interestingly the kids were figuring them out faster than some of the adults...

Which got me thinking about the Monty Hall Problem.  You may or may not know that Monty Hall was an American game show host, and while he may be pretty famous for being on TV, he is immortalised in the maths puzzle named after him. Mythbusters studied it, and its even been explain  in movies.

You have three doors. Behind 1 is a car and the other two are goats. Pick a door and the prize is yours... but wait... Before you open the door let me show you another door. Behind this other door is a goat. Maybe there's a goat behind your door too! It's not too late to change your mind? Stick with your door, or switch to the final unopened door?

Stick you say? Thought you might. Most people do. So lets open then door and see what you won!

Now of course there's an element of luck in here - you might have picked correctly, or you could be wrong. The interesting question is should you have switched?

Well let's write a program to find out!

Let's start by setting up some variables:

make doorCount number 3

make switch boolean no

make prizes list of strings

make open list of boolean

make pickedDoor number

We've got a couple of lists - prizes which tells us what's behind each door and open which tells us if the door is open yet. PickedDoor is going to be the number of our selection. I've also set up a couple of constants - we have 3 doors, and we're not going to switch.

Now lets bring out some prizes:

when hideCar

.delete all of prizes

.delete all of open

.repeat doorCount

..add "goat" to prizes

..add no to open

.replace item pick random 1 to doorCount of prizes  with "car"

when showDoors

.make counter number

.repeat length of prizes using counter

..if item counter of open

...say join "Door" join [counter] join ":" item counter of prizes

..else

...say join "Door" join [counter] join ":" "Closed"

.say ""

hideCar, clears out the lists (just in case), puts a goat behind every door, and sets the door to closed. It then picks a random door and replaces the goat with a car. Next we have showDoors which goes through the doors and either prints out that the door is closed or (if its open) then it prints the prize that was behind it.

Now we can write a start script to begin putting these together.

when start

.broadcast hideCar and wait

.set pickedDoor to pick random 1 to doorCount

.say join "you pick door number  " [ pickedDoor ]

.replace item pickedDoor of open with yes

.broadcast showDoors and wait

In this simplified version we hide the car, pick a random door, then open that door and show the results. It's pretty obvious that with three doors we should win about 1/3 of the time.

Now lets start opening some doors.

when openRandom

.make counter number

.forever

..set counter to pick random 1 to doorCount

..if not counter=pickedDoor and not item counter of open

...if item counter of prizes="goat"

....replace item counter of open with yes

....

....say join "Behind door " join [counter] join " is a " item counter of prizes

....stop script

This script tries to open a random door. Except its not totally random. The gameshow host never opens the door you picked, or the door with the car - he always shows an unpicked door with a goat. Therefore, having picked a random door we check that its not the one picked, its not already open, and it does have a goat behind it. Only when all those conditions are true can the door be opened to reveal a goat.

You might note that this code is a little more complex than it needs to be. If we only open one random door then we don't actually need to check  that the door is closed (they all are), and when we print out the prize behind the door its always a goat. However its worth writing the code this way as it actually represents what's going on in the real world, and it provides a double check that what we're going is correct.

The final piece of code we need is to switch doors:

when switchDoors

.make counter number

.forever

..set counter to pick random 1 to doorCount

..if not counter = pickedDoor and not item counter of open

...set pickedDoor to counter

...stop script

To switch, we pick a random door, and check that its different to our current pick, and that its currently closed. Again this is more complex that we need, but it accurately represents the puzzle. It means it will keep working if we start adding extra doors or playing with the other parameters.

when start

.say "New Game:"

.broadcast hideCar and wait

.set pickedDoor to pick random 1 to doorCount

.say join "you pick door number  " [ pickedDoor ]

.say ""

.broadcast openRandom and wait

.say ""

.broadcast showDoors and wait

.if switch

..broadcast switchDoors and wait

..say join "You switch to door " [pickedDoor]

.else

..say join "You Stick with door " [pickedDoor]

.say join "You won a " item pickedDoor of prizes

Here's the whole game put together. Remember switch is set to no, so we're never switching, and when I run it I get:

you pick door number  2

Behind door 1 is a goat

Door1:goat

Door2:Closed

Door3:Closed

You stick with door 2

You won a car

Yay for me!!! I win a car!

But wait - maybe I was just lucky. What if we played 100 games:

make score number

when start

.repeat 100

..say "New Game:"

..broadcast hideCar and wait

..set pickedDoor to pick random 1 to doorCount

..say join "you pick door number  " [ pickedDoor ]

..say ""

..repeat doorCount-2

...broadcast openRandom and wait

..say ""

..broadcast showDoors and wait

..if switch

...broadcast switchDoors and wait

...say join "You switch to door " [pickedDoor]

..else

...say join "You Stick with door " [pickedDoor]

..say join "You won a " item pickedDoor of prizes

..say ""

..say ""

..if item pickedDoor of prizes ="car"

...change score by 1

.say join "You won " join [ score ] " times"

You won 33 times

That's not so good. I won 33 times out of 100, which is exactly(ish) 1/3 of the time. I guess with three doors that's about as good as it gets.

Or maybe not - lets set switch to yes.

You won 65 times

Wow! Thats a lot more interesting. Now we're winning about 2/3 of the time! But how come? We still get to take home one prize from three, and all three doors have an equal change of being a good prize, so why should we be better at picking the wrong door first time and the right door second? 

Well actually you just summed it up... On your first pick you're probably going to pick the wrong door because there are three doors - you get the right one 1/3 and wrong one 2/3. If you stick then that's what you end up with - probably wrong, but it you switch then being wrong the first time means you'll definitely be right the second.

The way I like to think about it is to image there are 100 doors, and I open 98 of them (in fact I've already tweaked the code so the number of doors opened is the total-2).

make doorCount number 100

make switch boolean no

What happens when we run this:

New Game:

you pick door number  23

Behind door 30 is a goat

Behind door 73 is a goat

Behind door 42 is a goat

Behind door 74 is a goat

Behind door 47 is a goat

lots of goats...

Behind door 21 is a goat

Behind door 19 is a goat

Behind door 10 is a goat

Behind door 4 is a goat

Behind door 69 is a goat

Behind door 72 is a goat

Behind door 50 is a goat

Behind door 44 is a goat

Door1:goat

Door2:goat

Door3:goat

Door4:goat

Door5:goat

Door6:goat

Door7:Closed

Door8:goat

Door9:goat

Door10:goat

Door11:goat

Door12:goat

lots of goats...

Door22:goat

Door23:Closed

Door24:goat

lots of goats...

Door96:goat

Door97:goat

Door98:goat

Door99:goat

Door100:goat

you stick with door 23

you won a goat

Think about it - what was the chances that the goat was behind door 23? Well 1 in 100, so its pretty obvious we're probably not going to win. Now look at all those doors I opened for you - do you really think I can open 98 doors and accidentally only find goats? every time? I know something you don't - where the car is! and I mysteriously avoided door number 7. As the number of doors goes up it becomes pretty obvious that switching is a good deal.

Yet it turns out most people don't switch. Even mathematicians who should know better fall for it. Unless you've seen the trick before you'll probably stick, because there's doesn't seem to be an obvious reason to switch, and people don't like to change their mind. I picked door 23, and its as good as any other door, so I'll stay with 23... and probably take home a goat.

Release 30 - at last!

It's been a while since the last release, and while there's not to much in the way of major changes there are a lot of tweaks on fixes. Most importantly the documentation is much improved - check out the "doc" folder for both an improved/updated manually and separate documentation for a lot of the different devices (as both Pages, and PDF's). This is still a work in progress, but it should make things a lot easier for everyone.

We've also made some tweaks to SniffPad that you'll appreciate if you're running on a laptop - its now a LOT less CPU intensive, which means it won't hog your battery, and it a little more responsive on slower machines.

When reworking the documentation we also made a few tweaks to the compiler - a few odds and ends had been missed, which should now work. We also changed the error message so instead of things like "syntax error" it now says things like "oops" and "I don't understand". Hopefully its a bit less intimidating (and clearer for people who don't actually know what a syntax error is yet!).

There's also the usual updates of devices and examples. We added support for cheer lights - just cause they're fun. There's a cheerlight demo for flotilla, plus code to bridge cheer light to MQTT.

Check it out on the downloads page.

Girls Like Robots

I don't play a lot of games, but when I read about the Humble Bundle Freedom Bundle is seemed like an easy buy - lots of games and all the money goes to a good cause. So far the game that's taken up the most of my time is a little puzzler called "Girls Like Robots". It only takes a few hours to play through the whole game, but its a lot of fun.

The premise of the game is easy enough: place cards on the grid so that they all get along with their neighbours: Girls like Robots, and Robots like Girls. Nerds like girls (and robots) too, but they also like being on their own, so they like being on the edge of the board, and they don't like other Nerds. Of course Girls don't like Nerds (while Robots just ignore Nerds).

Here's a typical level (from around the point where its starts go get a little interesting). The grid is 4x3, and the level starts with a Nerd in the top left hand corner. We have to place 4 Girls, 4 Robots, and 3 more Nerds to score as many points as possible. Around 20 will pass the level, 22 to get a "Good" rating, and 26 is the perfect score.

It's the sort of problem that's really easy to solve with a little code - while we could do something clever, the easiest thing to do is just generate random placements and keep track of which is the best one. So lets give it a go!

The first problem is that Sniff only has a List which stores things in order - there's no easy way to obvious represent a 2D grid. We could make a list of strings, with each character representing a grid slot, and each string representing a row, but replacing individual letters would be fiddley.

Instead I made a list of numbers. Each number represents one square, along each row and then on to the next. We use a couple of other variables to store the height and width.

make arena list of numbers

make width number 4

make height number 3

make  empty number 0

make girl number 1

make robot number 2

make nerd number 3

make edge number 99

Now we can just make up a number to represent each card type, and use that number but its going to be much clearer if we use a constant. I've declared empty, girl, robot, and nerd so I can put them in the list without having to remember what actual values I used. I've also declared edge, which will come in handly later.

when print

.make message string

.make counter number

.make card number

.set counter to 1

.repeat height

..set message to ""

..repeat width

...set card to item counter of arena

...if card=empty

....set message to join message "."

...if card=girl

....set message to join message "G"

...if card=robot

....set message to join message "R"

...if card=nerd

....set message to join message "N"

...change counter by 1

..say message

The first script I wrote was to print out the game status. We go along each of the rows, checking the square, and depending what it is we add a suitable letter to the message. When we reach the end of the line we print out the message and go around again.

The next thing I wrote was something to place a card somewhere in the grid:

make card number

when placeRandom

.make x number

.make y number

.make counter number

.forever

..set x to pick random 1 to width

..set y to pick random 1 to height

..#say join [x] join "," [y]

..set counter to (y-1)*width+x

..if item counter of arena =empty

...replace item counter of arena with card

...stop script

I generate a random x,y coordinate and then calculate the index of that square in the list. This is a bit tricky but basically each step in Y moves us down the grid one square, which moves us on by width steps through the list.

If the square us currently empty then we place the card in the square and we're done. Otherwise we go around again and try another square. With that in place its pretty trivial to fill up an entire grid with a random layout:

when fillArena

.broadcast makeEmpty and wait

.replace item 1 of arena with nerd

.repeat 4

..set card to girl

..broadcast placeRandom and wait

.repeat 4

..set card to robot

..broadcast placeRandom and wait

.repeat 3

..set card to nerd

..broadcast placeRandom and wait

Or at least almost random: As per the level above, I've placed a Nerd in the top left, then placed 4 girls, 4 robots and 3 nerds randomly. Of course I've been testing all of this as we go along using something like this:

when start

.repeat 10

..broadcast fillArena and wait

..broadcast calcScore and wait

..broadcast print and wait

..say ""

Which simply prints out 10 random card layouts.

Now for the hard part - we need to calculate a score for a card layout.

when calcScore

.make counter number

.make x number

.make y number

.set score to 0

.set counter to 1

.repeat height using y

..repeat width using x

...set card to item counter of arena

...

...if x>1

....set neighbour to item counter-1 of arena

...else

....set neighbour to edge

...broadcast calcCompatability and wait

...

...if x<width

....set neighbour to item counter+1 of arena

...else

....set neighbour to edge

...broadcast calcCompatability and wait

...

...if y>1

....set neighbour to item counter-width of arena

...else

....set neighbour to edge

...broadcast calcCompatability and wait

...

...if y<height

....set neighbour to item counter+width of arena

...else

....set neighbour to edge

...broadcast calcCompatability and wait

...

...change counter by 1

So to do that we go through the grid one square at a time, and calculate its happiness score. First we get the card thats in the square itself (item counter of arena). Then we check each of its neighbours starting with its left hand neighbour at counter-1.  If course that won't work if we're on the left hand edge (x=1), so we check that x>1 and if its not we set the neighbour to be an edge (in other games we might be able to use empty, but remember Nerds like being on an edge). 

Having set card and neighbour we then call calcCompatablity to actually work out that pairings contribution.

when calcCompatability

.if card=girl

..if neighbour=robot

...change score by 1

..if neighbour=nerd

...change score by -1

.

.if card=robot

..if neighbour=girl

...change score by 1

.

.if card=nerd

..if neighbour=girl

...change score by 1

..if neighbour=robot

...change score by 1

..if neighbour=edge

...change score by 1

..if neighbour=nerd

...change score by -1

This is where the "game logic" really lives. Here you can specifically see that girls like robots and don't like Nerds. As you can see Nerds are by far the most complex, as they have a reaction to pretty much every other card.

Finally all we have to do is generate lots of random layouts and see which is best:

make hiScore number

when start

.repeat 10000

..broadcast fillArena and wait

..broadcast calcScore and wait

..if score>hiScore

...set hiScore to score

...say [score]

...broadcast print and wait

...say ""

And when we do something strange happens... it suggests the solution:

NRNG

RGRG

NRGN

Which it thinks will score 27 points on a level where the "perfect" score is 26... 

And there it is!!! 27 points!!!

In later levels we get to add in new cards - Pies (pie makes every one happy, except robots) and baby seals (everyone loves baby seals, but they hate girls), fish and cows. There's also the rule that robots can get too excited and panic if they're surrounded by 4 girls. Some of these are a bit more tricky to implement as they don't just apply to a single pair of cards, but with the framework in place its fairly simple to add these extra features.

Check out the Humble Bundle, and Girls Like Robots. They're almost as much fun as writing the solution!

Round and Round (rotary encoder)

Pots are fun, but they have two limitations - firstly they have a position, which is great feedback, but if it gets out of sync with the "real" value because you've changed it for some other reason then you need a motorised pot (as we saw list time) to get it back to the correct position. The second issue is that they have limited travel - when you reach the end, then you can't go any further.

Both of these are easily fixed using a rotary encoder (which also have the advantage of being digital, so you don't need an analog input, so on a Pi they're ideal).

Our encoder has 5 pins: Gnd and +ve are obvious. SW refers to an inbuilt switch, you can press down separately from the actual rotation. The other two are clk and dt, which are the interesting ones.

make dt digital input D5

make clk digital input D6

when start

.forever

..wait until clk

..say [clk]

..wait until not clk

..say [clk]

Clock will go from high to low and back repeatedly as you turn the shaft, so to get started we wait for it to change.

when start

.forever

..wait until clk

..wait until not clk

..say [dt]

The next thing to do is to check "dt" - direction of turn. Here I've set the code up to check dt whenever the clock goes low and we conveniently find that it is true when we turn clockwise and false when we turn anticlockwise.

All that's left is to add something to keep track of the number of times we turn in each direction:

make counter number

when start

.forever

..wait until clk

..wait until not clk

..if dt

...change counter by 1

..else

...change counter by -1

..say [counter]

This works perfectly well but we can do a little better. For the encoder I got we get 15 clocks per full turn, but we can look a little closer, and get 30 half clocks by checking dt when clock goes high as well as when it goes low. When we check this we see that when we check dt at this point in the cycle it has the opposite value - its low when we go clockwise, and high anti-clockwise. Adding this in doubles the resolution of our encoder:

make counter number

when start

.forever

..wait until clk

..if not dt

...change counter by 1

..else

...change counter by -1

..say [counter]

..wait until not clk

..if dt

...change counter by 1

..else

...change counter by -1

..say [counter]

This works really well and reliably, with one gotcha. It assumes that we're actually running this code regularly. If we go off and run another script at the same time we might miss a clock change. We will spot it eventually, but by that time DT may have changed to an incorrect value - its important to check DT immedialtly the clock changes. If you're running a lot of other code at the same time, then you may need to switch back to the other version which is a little more reliable.