Teaching programming with Lua: bisection

Some things we know without being taught and it looks like the bisection is one of them. It appears to be an algorithm built into humans much like the magical pattern of three found in most folk tales or the Chomsky’s “is the man who is tall happy?” example that any child will get right even though the tightly semantically connected words appear quite distant from each other in the sentence.

When we (my wife and I, that is) asked our 8-year-old daughter to guess the number between 1 and 100 with “less” or “more” hints, she, of course, throught that it’s impossible (or, rather, will take so boringly long that she doesn’t want to even try). At first. After being promised that there’s a trick and she’ll get it much sooner than in 100 tries, she agreed and did it in 7 tries, much to her surprise.

When we asked how she did it, she couldn’t tell. Just did. After being slightly pushed in the right direction, she “invented” the bisection algorithm and, while she was still excited about it, we took a little time to code it.

Guessing game

Here’s the program, it’s quite short, but uses a loop, some comparisons and branching.

-- this part I explained to be a magic trick to kick-start 
-- the random number generator
math.randomseed(os.time())
x=math.random(0,100)
i=0
y=x+1
print ("Guess the number from 0 to 100")
while x~=y do
  print ("Input your guess: ")
  y=io.read()
  y=tonumber(y)
  i=i+1
  if x>y then print ("My number's greater than that")
  elseif x<y then print ("My number's smaller than that")
  end
end
i=tostring(i)
finish="Hurray! You guessed in "..i.." tries!"
print (finish)

She was so proud that she can guess a number between 0 and 100 in 6 or 7 guesses that she showed it to all her friends and extended family for at least a month. This turned out to be one of the best excercises in programming so far!

References

• Very dense Lua reference that I used to learn the language myself.