Fizz Buzz Sniff

A while back I came across an interesting blog post on what's become known as the Fizzbuzz test. The interesting idea is that despite claiming to be trained and qualified, many job applicants for programming jobs are bad. What makes this interesting is that it doesn't sugguest that they're bad but rather that they're BAD. Not just that they can't write production standard, bug free code on a commercial scale code (projects I worked on as a professional programmer were in the order of a million lines of code), but that they can't write the most trivial of code.

In the fizz buzz test, you're asked to write code (in the language of your choice) to count from 1 to 100, replacing any number divisible by 3 with fizz, divisible by 5 with buzz, and if its divisible by both use fizzbuzz. We only say the number if none of these apply. It's actually in interesting (trivial) problem, as it doesn't fit easily into an if/then/else, and actually requires a little thought, but any programmer can code it easily.

The hypothosis is that asking job applicants to write a trivial piece of code weeds out the ones who are wasting your time just as well as a more extended coding test. Part of the idea is that it will trivial to anyone who has a clue, so you don't waste their time either - it takes them 2 minutes and you move on to something else.

It's important to remember that the point of the test is to weed out terrible programmers. There are several ways to factor the answer, and some may be more efficient than others. Other's may be "clever", or shorter. But it's actually important not to judge the quality of correct answers - real world problems have context, which might dictate a fast solution, a low memory solution, or a maintainable solution. Dumb tests have no context, so making the correct design choices is impossible, so don't judge them.

I thought it might be interesting to see how I'd code it in Sniff. You should probably code it yourself first before reading mine, but here it is:

make counter number

make message string

when start

.repeat 100 using counter

.. set message to ""

..

..if counter mod 3 = 0

...set message to join message "fizz"

..

..if counter mod 5 = 0

...set message to join message "buzz"

..

..if message =""

...set message to [counter]

..

..say message

There are couple of places where I've coded it in ways that make sense to me. I can see several variations that some people might prefer (if I were interviewing me I'd ask about a couple of choices because I think the answers would be interesting, but then I think most things I have to say are interesting), but I think this is clean and maintainable, which I consider the "default" priorities in any code.

Of course you might think that as the test becomes widely known it looses its value - after all, now you've seen it you won't be tripped up. However the sort of person the test is designed to trip up probably doesn't read programming blogs: imagine interviewing someone, you propose the test, and they immediately tell you about how they've read all about it, and proceed to discuss its viability - they already have a tick in the right column. Even if someone did see it and learn a solution, it would be totally clear they were receiving a previous solution, rather than coding it from scratch.

It would be interesting to see how students (and staff!) at various stages of progression handle this. Maybe try it on your programming class (I know I will at some point!), or maybe at your next CDP session.

DIY Square Roots

Everyone knows how to calculate a square root: you press the button with the funny squiggly/V shape  on your calculator! And of course Sniff has a "sqrt of" function built in, but what if it didn't. Someone has to know how to actually do the maths, otherwise how did the code get written to actually implement those functions?

I like to set calculating a square root (without using any builtin functions - no cheating and using powers or log's either!) as a programming exercise to older students. Its fun because there's a relatively simple solution, that can be coded up in a single lesson, but chances are that the students will have no idea what that solution is. They have to research (google!) an algorithm, but there are several to choose from, and while one is easy to implement its not obvious which one that is.

Of course there's always a couple of "clever" students who decide they can just copy and paste the code they find during this research. I really love it when they do this, because most of the examples out there don't work! This is pretty obvious if you know what's going on, but if you've just downloaded the code then you've got some thinking to do after all! Teaching moment: most code online sucks! Or at least you should evaluate it carefully before just grabbing it.

Here's some code that does (almost!) work:

make x number

make guess number

make otherGuess number

when start

.ask "give me a number:" and wait

.set x to value of answer

.set guess to x/2

.repeat 20

..set otherGuess to x/guess

..set guess to (guess+otherGuess)/2

.say join "Square root is:" [guess]

We start with a number "x" that we want to find the square root of. We then need to make a guess. This is where many implementations come unstuck, and try to use some kind of linear search to find a good starting point. Given a big enough value of x they break! It turns out that the initial value of guess really doesn't matter - the rest of the code will turn any guess into a better guess so even a terrible guess is perfectly good enough.

If you think about square roots, guesses come in pairs: for each value of guess, theres another value "otherGuess" which would give us x if we multiplied guess by otherGuess. So given guess we can find otherGuess.

Now if guess is too small (< sqrt of x), then otherGuess will be too big (after all they multiply to give x). If we have an upper bound and a lower bound then we can make a better guess by picking a value in the middle (technically we're approximating the geometric mean, with the arithmetic mean, but that's not important).

If we repeat this a few times, then for each guess we get a better guess, until we decide we're close enough. What's surprising is how well this actually works. Here we go round the loop 20 times, but for most regular small-medium size numbers it gets as accurate as we're likely to need far more quickly.

One interesting aspect of square roots is that they're a tricky to calculate, but their inverse is easy. If we x=y*y, then calculating x from y is far easier than finding y given x. That means we can check our answer to see how good it is. Rather than looping a fixed number of times we could loop until our answer is close enough by checking guess*guess against x. Functions like these are actually pretty common, and are a good way to test/debug code. Sorting a list is hard, while checking that a list is sorted is easy, so you can add code to your sort function to check that its worked without signifigantly affecting performance.

One final aspect to note is that the code behaves very badly for negative numbers. Here's not the place to get into what the sqrt of -1 is, but its not whatever this code prints. This is bad. The code really needs a test in to prevent negative numbers getting in. It's better to bail out and fail than silently produce a wrong answer. This is another "extra" you can throw in for students who get a working solution quickly.

Finding the value of Pi

If you're interested in statistics or probability, then you'll probably love the Count Bayesie blog. In one of its recent posts gave a bunch of examples of Monte Carlo simulation. While that sounds complex its really just fancy maths talk for generating random numbers, and using them to test something. If we test something in a bunch of random ways, then the results will be representitive of the thing we're testing.

It's a pretty fundamental idea when it comes to solving difficult maths using a computer, and represents a fundamental shift from the way we used to do things "in the old days". While once upon a time we might have tried to solve a complex problem by converting it into a single equation which we could evaluate to give us an answer, once we have a computer its often quicker/easier to just let it do the work and run millions of simple tests rather than one bigger one.

Lets take a basic example: Imagine a square, entered at the origin which is 2 units on each side. It has an area of 4. Now imagine a circle of radius one. It sits in the middle of the square and just touches each side. It has an area of Pi r^2, or (since r=1) simply pi.

If we pick a random point inside the square it might fall inside the circle or not. What's the probability of that? Well the points are spread over an area of 4, but we only catch those that and in the cenral area of size Pi so we catch Pi/4 of them.

So if we generate n points, then we should catch nPi/4 of them in the circle as "hits". Jiggle that around and we see that Pi=4h/n. What's the point of that? It means you can calculate Pi by doing the experiment and dropping pins randomly onto a piece of paper. However this is actually harder do do than it sounds, and takes ages so this stuff really only took off once we got computers. Here's the code in Sniff:

make hits number
make iterations number
make x number
make y number
when start
.set iterations to 10000
.set hits to 0
.repeat iterations
..set x to (pick random -1000000 to 1000000)/1000000
..set y to (pick random -1000000 to 1000000)/1000000
..if x*x+y*y<1
...change hits by 1

.say [hits/iterations * 4 ]

This prints out 3.1444 which isn't too bad. The great thing is that the more times we go around the loop the better it gets. 10 million iterations gives 3.14141 which is getting pretty close (to 3.14159265...). Trying to go past 10,000,000 iterations runs into a problem - regular computers need special code to handle such big numbers correctly, and Sniff isn't set up for it, so this is about as accurate as we can get with this simple approach. Going the other way, if we want the answer faster 100 iterations gives an answer of 3.08 (bonus question: plot the error against iterations, to see how quickly we get the right answer).

This approach can be applied to all sorts of problems (including lots in computer graphics used for movies), but its generally used for "hard" problems that mathematicians can't solve any other way, so some of the examples can get a bit tricky. However the basic idea is simple enough its worth trying out.

Adventures in Minecraft (ch5 - the one with the hardware)

We've been going through the excellent Adventures in Minecraft book and reworking the examples from Python to Sniff. Partly because Minecraft is a fun thing to do, but also as a set of examples of how Python and Sniff differ in their approaches. Generally the Python code is shorter, but depends on more "features" that you have simply remember, or look up rather then actually coding.

In chapter 5, things get a little more interesting as it deals with hooking up real hardware so you can interact with Minecraft from outside the computer. This is a lot of fun, but can be tricky to set up, and it behaves differently if you have a Mac or PC, so we'll just stick to using the Pi (I really want to get the Minecraft libs running natively on Arduino!). To use Sniff with GPIO on the Pi you first need to install WiringPi, and then it should "just work".

Here's the first Python program from the book, which simply flashes an LED:

import time
import RPi.GPIO as GPIO

LED = 15

GPIO.setmode(GPIO.BCM)
GPIO.setup(LED, GPIO.OUT)

def flash(t):
  GPIO.output(LED, True)
  time.sleep(t)
  GPIO.output(LED, False)
  time.sleep(t)

try: # Try to run this code, jump to "finally" if it fails
  while True:
    flash(0.5)
    
finally: # always gets here if your code fails (e.g. you CTRL-C the program)
  GPIO.cleanup()

There's a LOT of stuff there that isn't friendly... Here's the direct equivalent in Sniff:

make led digital output 15

make delay number

when flash

.set led to on
.wait delay secs
.set led to off
.wait delay secs

when start
.forever
..set delay to 0.5
..broadcast flash and wait

For once the Sniff code is actually shorter! This is mainly because Sniff treats GPIO pins like variables - we can simple declare outputs (to give them names) and then assign to them - it just works.

Once we can flash the LED, we can add that to the "doormat" example from previous chapters which used to print "welcome home" when you arrived at a specific location, so that the LED flashes when you get there.

make world minecraft device
make networkPeer string
make mcX number
make mcY number
make mcZ number
make blockType number
make blockData number

make led digital output 15
make delay number

when flash
.set led to on
.wait delay secs
.set led to off
.wait delay secs

when start
.set delay to 0.5
.
.set mcX to 10
.set mcZ to 10
.tell world to "getHeight"
.set blockType to 35
.set blockData to 15
.tell world to "setBlock"
.
.forever
..tell world to "getPos"
..if mcX>10 and mcX<11 and mcZ>10 and mcZ<11
...broadcast flash and wait

This version behaves slightly different to the Python version, as it uses the "getHeight" operation to place a wool block on the ground, even if that is higher or lower than 0. It then checks the position of the player and compares it to the position of the block.

7 Segment Display

The next exercise uses a 7 segment display which will ultimately count down from 9 to 0, before detonating an explosion in Minecraft. However first we have to get it wired up and tested.

This is both a little easier and a little harder in Sniff. It handles the GPIO pins more easily, but you can't have a list of io pins, or io pin numbers. Instead we need to access them individually. This is little more long winded, but its easy enough (and probably a little easier to understand):

make A digital output 10
make B digital output 22
make C digital output 25
make D digital output 8
make E digital output 7
make F digital output 9
make G digital output 11
make P digital output 15

make pattern list of booleans
when display
.set A to item 1 of pattern
.set B to item 2 of pattern
.set C to item 3 of pattern
.set D to item 4 of pattern
.set E to item 5 of pattern
.set F to item 6 of pattern
.set G to item 7 of pattern
.set P to item 8 of pattern

The corresponding Python fragment is:

LED_PINS = [10,22,25,8,7,9,11,15]

for g in LED_PINS:

  GPIO.setup(g, GPIO.OUT)

pattern = [True, True, True, True, True, True, True, False] # ABCDEFG No Dp

for g in range(8):
  if pattern[g]:
    GPIO.output(LED_PINS[g], ON)
  else:
    GPIO.output(LED_PINS[g], not ON)

This is perfectly good code for production use (and scales better - what if we had 100pins?), but the Sniff version is easier to understand.

In the Sniff version we still need to load up the list "pattern" which holds Boolean values (on/off, or if you prefer you can use yes/no or true/false - they all mean the same things in Snff) to indicate which parts of the 7 segment display we want to be lit up and/or turned off, so the main "start" script might be:

when start
.add on to pattern
.add on to pattern
.add on to pattern
.add on to pattern
.add on to pattern
.add on to pattern
.add on to pattern
.add off to pattern
.
.broadcast display and wait

Now to make the display count from 1 to 10 we need to create patterns for each digit, and display that. In the Python than means using a library with makes the code short, but hides what's actually going in. In Sniff lets keep building on what we've already made. Rather than just storing 8 booleans in the list "pattern", lets store 80: 8 for each of the ten digits:

make pattern list of booleans
when loadPatterns
.#0
.add on to pattern
.add on to pattern
.add on to pattern
.add on to pattern
.add on to pattern
.add on to pattern
.add off to pattern
.add off to pattern
.
.#1
.add off to pattern
.add on to pattern
.add on to pattern
.add off to pattern
.add off to pattern
.add off to pattern
.add off to pattern
.add off to pattern
.
.#2
.add on to pattern
.add on to pattern
.add off to pattern

etc

Then we can modify the display script to use not the first 8 values, but use the variable digit to calculate an offset into the list:

make digit number
make base number
when display
.set digit to digit mod 10
.set base to 8*digit
.set A to item base+1 of pattern
.set B to item base+2 of pattern
.set C to item base+3 of pattern
.set D to item base+4 of pattern
.set E to item base+5 of pattern
.set F to item base+6 of pattern
.set G to item base+7 of pattern
.set P to item base+8 of pattern

Now to make it count, just set digit, and broadcast display:

when start
.broadcast loadPatterns
.
.repeat 10 using digit
..broadcast display and wait
..wait 1 secs

(note I've used the "new" repeat using syntax, which executes the block 10 times using digit as a counter - its not necessary but its much neater than just using the Scratch notation).

The final example combines this counter with a button to start a countdown, and then destroy a large area of the world. Most of this is stuff we've covered, so lets just look at the button code:

BUTTON = 4 

GPIO.setup(BUTTON, GPIO.IN)

try: 

  while True:

    time.sleep(0.1)

    if GPIO.input(BUTTON) == False:

      pos = mc.player.getTilePos()

      bomb(pos.x, pos.y, pos.z)

      

finally: 

  GPIO.cleanup()

In Sniff this becomes:

make button digital input 4

.forever
..wait until not button
..tell world to "getPos"
..broadcast bomb and wait

Here we're creating an input, which (like outputs) we can use wherever we would use a boolean, so we can use it in Sniff/Scratch's "wait until" block.  This is a fairly unusual construct as it does nothing until a condition is met. In most languages that would mean wait forever, but Sniff has the same model of doing lots of things at the same time that Scratch does - other scripts may be running, which change the result of the test. It's also very handy when interacting with the outside world.

The code for chapter 5 repeats many of the things we learnt in comparing Python and Sniff in the first few chapters: Python code is generally shorter, but that's due to its more dense syntax, and reliance on external code/modules. However in this case Sniff's good support for GPIO means that the Sniff code is especially clear. Code for all these examples is in the current Sniff distribution.

Race Control

I've been running an Arduino robot workshop for the last few weekends, and next week is the final session. So far the kids have done a great job, and have build and coded IR controlled robots similar to SniffBot Jr. This design is well suited to the task, as its cheap enough that the cost of the session can cover the components, and everyone gets to take their robot home at the end (I've seen ads for some pretty expensive workshops where the students projects go back in the parts bin at the end of the week - I think the kids would be devastated to have to give their creations back!).

For the final week I want to set them some challenges so they can race their robots against each other. However as they've all got the same IR controllers the events will have to be time trials: a salom/obstacle course, sumo against some smaller bots, and finally an all out race around a track. I could just time each event on a stopwatch (phone!), but I thought I'd so something more fun.

I happened to have an Arduino Uno and some Neo Pixels attached to a sheet of perspex, so I realised I could turn that in to a great "race control"/starting mechanism and timer. In motor racing, races are started by 5 lights lighting up red one at a time. The lights then hold for a few seconds (randomised) before turning off to signify the start of the race.

That would be pretty easy to build, but I had a lot more neoPixels and just lighting them up red would be a bit boring, so I chose to light them yellow to signify the ready state. I'd then press a button, and the yellow lights would turn red in sequence. Once they were all red, they'd hold for a random time before turning green to start the race. That would also start the timer. On pressing the button again the timer would stop and the lights would display something colourful to celebrate the end of the race.

To code that we start by defining the hardware:

make neoPixel ws2811 device A1
make neoColor list of number
make neoShade list of number

make lcd device
make displayFlush boolean

make message string

make button analog input A0

make ledCount number
make startTime number
make index number

The NeoPixels are attached to A1 using a sensor shield. Depending on the version you have, one of the neat features is that it breaks out A0-5 around the edge, so that even when you have another shield on top you can still get to the Analog pins.

For the timer display I use an "LCD Shield". These are available everywhere, and there are dozens of different brands, but they're all the same. They're support cheap, and are far easier than wiring up a regular LCD (which I've never even tried - either use a shield or get an i2c LCD which just uses two pins but is slower to refresh). The only gotcha is that there's a design fault on many of them - just never use pin 10 for anything and you'll be fine! There are 5 buttons plus a reset, but rather than using 5 pins they're attached via resistor network to A0. Each button returns a different analog value. 

I could have used something like an Embedded Adventures 7 segment display, or even one of their larger displays, but then it would have needed a bit more "construction". the LCD shield just plugs in and is pretty robust.

when start
.set ledCount to 16
.repeat ledCount
..add 60 to neoColor
..add 50 to neoShade
.tell neoPixel to "show"
.
.tell lcd to "clear"
.set message to "ready"
.tell lcd to "show"
.
.wait until button< 0.8

Step 1 is to load up the neoPixel colour and shade array with 60 to mean yellow and a brightness of 50 which means full brightness/saturated colour. For testing you can drop this down to around a 10 - it's easier on the eyes! Once loaded we call "show" to write the values to the pixels.

.wait until button< 0.8
.
.tell lcd to "clear"
.set message to "set"
.tell lcd to "show"
.
.repeat ledCount using index
..replace item index of neoColor with 0
..tell neoPixel to "show"
..wait 0.2 secs

Now we wait for a button to be pressed. We don't care which button so just wait till the value drops below 0.8. Then clear the LCD and display the message "set".

We now need to turn each pixel red in turn. I've used the "new" repeat using syntax as I find it really helpful - the code is the equivalent of:

.set index to 1

.repeat ledCount

..replace item index of neoColor with 0
..tell neoPixel to "show"

..wait 0.2 secs

..change index by 1

But its a little clearer once you're up to speed with it. For younger children just transitioning from Scratch you should probably stick with the version they recognise, and then once they've got the idea of it you can introduce the "short cut".

.wait (pick random 5 to 30)*0.2  secs

.

.delete all of neoColor

.repeat ledCount

..add 120 to neoColor

.tell neoPixel to "show"

Once all the lights are red we wait for a random time between 1 and six seconds before switching the lights to green. We could have done this as we did for the previous code with an index counter, but its easier to throw them all away and replace them all.

.set startTime to timer

.

.repeat until button < 0.8

..tell lcd to "clear"

..set message to [timer - startTime]

..tell lcd to "show"

..wait 0.1 secs

.

So now we're racing, so record the start time, and loop until the button is pressed again to finish the race. Each time around the loop we update the screen with the new elapsed time. We need a bit of a delay so that the screen isn't too flickery - we don't want to clear it just after we've displayed the message! 0.1 seconds is faster than I can press the stop button so don't mind the timing error this might introduce.

The LCD screen will already be displaying the final time, so there's no need to update it any more. All that's left is do make the neoPixels look pretty:

.

.forever

..set index to timer*10

..delete all of neoColor

..repeat ledCount

...add ((index mod ledCount)*2/ledCount)*360 to neoColor

...change index by 1

..tell neoPixel to "show"

Potentially we could put all this code in a loop to time multiple races, but there's a reset button on the shield which starts the program again, so its easier to just use that.

This was never meant to be example code, or used as a classroom exercise - it was just something cool that I thought would make the robot race more fun, but now its done I realise that actually it's a pretty great project for a short workshop. It would also run really well (without the timer) on the 4tronix smart badge I just got...

Release 16: Now with extra Syntax

One of the "rules" when we designed Sniff was that it would be Scratch written down. We didn't want to change anything unless we had to. While we say that Sniff is a "language" its probably more accurate to say that Sniff and Scratch are different implementations of the same language.

We therefore think very carefully before changing anything, so this release is a bit unique. We've added a couple of features to the language! These are things we feel are really necessary due to the extended scale of Sniff projects - we've now got programs like the Sniff IDE written in Sniff which is over 1000 lines of code.

repeat times using numvar

Scratch doesn't have a "for" loop. If you want to count you need to use a repeat loop:

.set x to 1
.repeat 10
..say [x]
..change x by 1

The problem is that the "change" at the end of the loop is essential to the loops operation, but is physically separated from it, which means its easy to loose track of it (or forget it all together). We struggled to work out a suitable "block" that would meaningfully express the problem, but the problem is that while its simple enough to get over the idea of iteration, its harder to succinctly express the idea of iteration with in index. The traditional programming phrase is a for...next loop, but that means absolutely nothing to non-programmers.

However when working on the recently posted OCR exemplars, and having written the above code five or six times we realised who it could be done:

.repeat 10 using x
..say [x]

We're going to go around 10 times, using x as the counter! Simple, clear, and importantly: a lot like the loop we already have.

It's not as versatile as the C for loop which confuses every new programmer, but it handles the basic case very clearly. We've started using it, and have when updating a couple of the examples to use it have found it pretty handy. You can always fall back on repeat until if you need something more complex.

Local Variables

When writing larger programs the biggest worry is that you have to make sure that the variables used by one script aren't being used by another:

make counter number

when doIt

.repeat 2 using counter

..say [ counter ]

when start

.repeat to using counter

..broadcast doIt and wait

..say [counter]

Instead of printing out 

1,2,1,1,2,2,1,2,3,1,2,4...

This will print 

1,2,2,1,2,2,1,2,2,1,2,2...

When we run doIt it changes counter. That means when we're writing start we need to check that doIt doesn't use counter (or check that it does it thats what we want). In a large program this becomes a nightmare, as calling any other script could mess with any of your variables.

when doIt

.make counter number

.repeat 2 using counter

..say [ counter ]

when start

.make counter number

.repeat to using counter

..broadcast doIt and wait

..say [counter]

Here we've made counter a local variable. It only exists inside the functions and each function has its own version so they can't mess each other up. This isn't something you need to learn straight away - in fact its probably best to just get on, use regular global variables, until you get yourself in such a mess that you understand why local is such a good idea.

There are a couple of restrictions - variables need to be declared immediately after the "when", so that your whole script sees them. You can can't create input, outputs or devices - this would make no sense (or little sense, most of the time - yes there are cases where it might be slightly useful, but you can't do it, so get over it). Generally the "device" is something that actually exists - a piece of hardware, so it doesn't make sense for it to pop in and out of existence as your program runs. You also need to make sure that variables used by a device are global. The device can't see your local copy!

New Names for List data types

As we were working on the code that handles variable declarations anyway, we thought we'd finally fix something that's been niggling for a while. Now instead of creating a "list of number" you can make a "list of numbers". List data types are now plural!

For now we'll be supporting both the old singular version and the new plural version, and see how it goes, but we may phase out the old singular version in the future.

We don't take these changes lightly, but they come after over a year of experience programming in Sniff. In that time we've learnt what the language should feel like, and the size of our examples have grown by a factor of 100 (10 lines of Sniff can do quite a lot - we never expected to write 1000!). We think these are a step in the right direction.

Other Features of Release 16

Ethernet and Minecraft now work on Windows

Wedo supports raw access for homebrew hardware like the thermometer

OS X Windowing is MUCH faster

Support for 32bit OSX.

Additonal fixes and updates

Download

The new versions of Sniff, Release 16 are available on the downloads page. As usual there's a Windows, and Unix (Mac/Linux/Pi) version.