Algorithms · Lessons

Recipes that last

An algorithm is a recipe for a problem: steps that always reach the answer. Many of the best are old, and work the same in every language. This lesson writes a handful in xTalk, each a pattern you will meet again.

Euclid's algorithm

The greatest common divisor of two numbers, the biggest number that divides both, is what you need to simplify a fraction. Euclid wrote this method down around 300 BC: replace the pair by the smaller number and the remainder of dividing one by the other, until the remainder is 0.

ExampleRun it in the playground

function gcd pA, pB
   local tRemainder
   repeat while pB is not 0
      put pA mod pB into tRemainder
      put pB into pA
      put tRemainder into pB
   end repeat
   return pA
end gcd

put gcd(1071, 462)
put gcd(48, 180)
put 48 / gcd(48, 180) & "/" & 180 / gcd(48, 180)

Output

21
12
4/15

The sieve of primes

To find every prime below a limit, do not test each number. The sieve of Eratosthenes crosses out the multiples of each prime as it finds it; whatever is not crossed out when you reach it is prime. An array marks the crossed-out numbers, and repeat with ... step counts through the multiples:

ExampleRun it in the playground

function primesBelow pLimit
   local tCrossed, tPrimes, tN, tMultiple
   repeat with tN = 2 to pLimit - 1
      if tCrossed[tN] is true then next repeat
      put tN & comma after tPrimes
      repeat with tMultiple = tN * tN to pLimit - 1 step tN
         put true into tCrossed[tMultiple]
      end repeat
   end repeat
   delete the last char of tPrimes
   return tPrimes
end primesBelow

put primesBelow(50)
put the number of items of primesBelow(100000)

Output

2,3,5,7,11,13,17,19,23,29,31,37,41,43,47
9592

Crossing out starts at tN * tN, because the smaller multiples were crossed out already by smaller primes.

Searching: linear and binary

To find a value in a list, a linear search looks at each item in turn. In a list of 100,000 items, that can mean 100,000 looks. If the list is sorted, a binary search does far better: look at the middle item, and you know which half the value must be in; look at the middle of that half, and so on. Each look halves what is left, so 100,000 items take at most 17 looks.

ExampleRun it in the playground

local sLooks

function findLinear pList, pWanted
   local tIndex
   repeat with tIndex = 1 to the number of elements of pList
      add 1 to sLooks
      if pList[tIndex] = pWanted then return tIndex
   end repeat
   return 0
end findLinear

function findBinary pList, pWanted
   local tLow, tHigh, tMiddle
   put 1 into tLow
   put the number of elements of pList into tHigh
   repeat while tLow <= tHigh
      add 1 to sLooks
      put (tLow + tHigh) div 2 into tMiddle
      if pList[tMiddle] = pWanted then return tMiddle
      if pList[tMiddle] < pWanted then
         put tMiddle + 1 into tLow
      else
         put tMiddle - 1 into tHigh
      end if
   end repeat
   return 0
end findBinary

repeat with i = 1 to 100000
   put i * 3 into tNumbers[i]
end repeat

put 0 into sLooks
put "linear found it at" && findLinear(tNumbers, 299997) && "after" && sLooks && "looks"
put 0 into sLooks
put "binary found it at" && findBinary(tNumbers, 299997) && "after" && sLooks && "looks"

Output

linear found it at 99999 after 99999 looks
binary found it at 99999 after 16 looks

Stacks and queues

Two shapes of to-do list come up again and again. A stack is last in, first out, like a pile of plates: you add to the top and take from the top. A queue is first in, first out, like a line at a shop. With lines of text, both are a line or two:

ExampleRun it in the playground

-- a stack: add at the end, take from the end
repeat for each word tPlate in "red green blue"
   put tPlate & return after tStack
end repeat
put line -1 of tStack into tTaken
delete line -1 of tStack
put "from the stack:" && tTaken

-- a queue: add at the end, take from the front
repeat for each word tPerson in "Ada Grace Linus"
   put tPerson & return after tQueue
end repeat
put line 1 of tQueue into tServed
delete line 1 of tQueue
put "from the queue:" && tServed

Output

from the stack: blue
from the queue: Ada

An undo list is a stack: the last change made is the first undone. A list of files to download is a queue: the first asked for is the first fetched. The try-it below uses a stack; the maze uses a queue.

The shortest way through a maze

A breadth-first search finds the shortest path through a maze, a map or a network. Start with a queue holding the start. Take the first cell from the queue, and add each open neighbour not seen before, noting the cell it was reached from. Because the queue is first in, first out, cells are reached in order of distance, so the first time the search reaches the end, it got there by a shortest way. Following the notes back from the end gives the path.

The stage, with a maze of dark grey walls; a violet square marks the start at the top left, an orange square the end at the bottom right, and a line of teal dots shows the shortest path, down the left side, along the bottom, up through a gap in the middle, and over and down to the end.

The maze is lines of text, one character a cell, so a cell is a row and a column: char (column) of line (row). The search never needs to check for the edge of the map, because the map is walled all round. The path holds the cells between the start and the end, so the steps are one more than its lines.

Try it yourself

Use a stack to check brackets: go through the text a character at a time; push each opening bracket ( [ {; at each closing bracket, pop the last opening one and check that the two match. The brackets balance if nothing failed to match and the stack ends empty. Try (a[b]{c}), (a[b)] and ((.

Show a solution

ExampleRun it in the playground

function balanced pText
   local tStack, tChar, tOpen
   repeat for each char tChar in pText
      if tChar is among the chars of "([{" then
         put tChar after tStack
      else if tChar is among the chars of ")]}" then
         if tStack is empty then return false
         put the last char of tStack into tOpen
         delete the last char of tStack
         if tOpen & tChar is not among the items of "(),[],{}" then return false
      end if
   end repeat
   return tStack is empty
end balanced

put balanced("(a[b]{c})")
put balanced("(a[b)]")
put balanced("((")

Output

true
false
false

Here the stack is plain text, a character an item, since each thing pushed is one character.

Words in this lesson

algorithmbinary searchsplitstackqueuebreadth-first searchmodrepeat with step

Each one finds every lesson that uses it. The Dictionary has the whole story of each, with its syntax and more examples.