Forth Solution to Grecian Computer Puzzle

Grecian Computer Puzzle (Product of Project Genius)

I got this puzzle a while ago as a present. It is a wooden puzzle made up of rotating discs of numbers. The goal is to line up the discs so that all the numbers add up to 42. What makes this especially complicated is that most of the discs have gaps in them, and therefore propagate numbers up from below depending on their position.

As an exercise, I wanted to see if I could write a memory-space efficient Forth program which would solve this puzzle.

In principle, this seemed like a simple idea, as I only need to represent the discs in memory and rotate them methodically, checking along the way for the solution. The trickiest part, however, was figuring out how to represent these discs in memory, while preserving their holes, and figuring out how to overlay them properly.

In the approach I took, there is one 48 byte memory space representing the board as a composite of the discs:

create board 48 allot

The first disc, the bottom one, is easy because it has no holes. This is represented by another 48 byte array.

create disc0
 2 c,  5 c, 10 c,  7 c, 16 c,  8 c,  7 c,  8 c,  8 c,  3 c,  4 c, 12 c,
 3 c,  3 c, 14 c, 14 c, 21 c, 21 c,  9 c,  9 c,  4 c,  4 c,  6 c,  6 c,
 8 c,  9 c, 10 c, 11 c, 12 c, 13 c, 14 c, 15 c,  4 c,  5 c,  6 c,  7 c,
14 c, 11 c, 14 c, 14 c, 11 c, 14 c, 11 c, 14 c, 11 c, 11 c, 14 c, 11 c,

For the other discs, I will also use byte arrays. However, I have to represent the holes some how. The most practical choice is to use the number zero, which is not used anywhere on the actual board, and conveniently maps to the boolean false value in Forth. So, I create disc1, disc2, and so on. You see that my number of rows shrinks with each disc.

create disc1
 1 c,  0 c,  9 c,  0 c, 12 c,  0 c,  6 c,  0 c, 10 c,  0 c, 10 c,  0 c,
 3 c, 26 c,  6 c,  0 c,  2 c, 13 c,  9 c,  0 c, 17 c, 19 c,  3 c, 12 c,
 9 c, 20 c, 12 c,  3 c,  6 c,  0 c, 14 c, 12 c,  3 c,  8 c,  9 c,  0 c,
 7 c,  0 c,  9 c,  0 c,  7 c, 14 c, 11 c,  0 c,  8 c,  0 c, 16 c,  2 c,

create disc2
 5 c,  0 c, 10 c,  0 c,  8 c,  0 c, 22 c,  0 c, 16 c,  0 c,  9 c,  0 c,
21 c,  6 c, 15 c,  4 c,  9 c, 18 c, 11 c, 26 c, 14 c,  1 c, 12 c,  0 c,
 9 c, 13 c,  9 c,  7 c, 13 c, 21 c, 17 c,  4 c,  5 c,  0 c,  7 c,  8 c, 

create disc3
14 c,  0 c,  9 c,  0 c, 12 c,  0 c,  4 c,  0 c,  7 c, 15 c,  0 c,  0 c,
11 c,  6 c, 11 c,  0 c,  6 c, 17 c,  7 c,  3 c,  0 c,  6 c,  0 c, 11 c,

create disc4
 3 c,  0 c,  6 c,  0 c, 10 c,  0 c,  7 c,  0 c, 15 c,  0 c,  8 c,  0 c,

Now, how to manipulate the board? The computationally simple and space-efficient approach is to simple rotate the bytes in place. So, here is my row rotation function, followed by one that rotates a whole disc. (Please forgive some of my inconsistent parameter descriptions…)

: rot-row ( addr -- )
    dup 11 + c@ swap ( c a )
    11 0 u+do
        dup 10 + i - c@ swap ( c c a )
        dup 11 + i - ( c c a a )
        rot ( c a a c )
        swap c! ( c a )

: rot-disc ( addr n )
    0 u+do
        dup 12 i * +
        rot-row loop

Having all the discs, and a way to rotate each of them, eventually I would need a procedure to stack them onto the board:

: overlay ( a a u -- )
    12 * 0 u+do ( a1 a2 )
        dup i + c@ ( a1 a2 c )
        dup 0<> if
            2 pick ( a1 a2 c a1 )
            i + c! ( a1 a2 )
        else drop
    drop drop

: overlay-all
    board disc0 4 overlay
    board disc1 4 overlay
    board 12 + disc2 3 overlay
    board 24 + disc3 2 overlay
    board 36 + disc4 1 overlay

We are pretty close now. I need a function to check for a solution, which is simple addition of the columns on the board:

: solved? ( -- bool )
    12 0 u+do
        board i + c@
        board 12 i + + c@
        board 24 i + + c@
        board 36 i + + c@
        + + +
        42 <> if drop false leave then

Now, I’ve got to walk through rotating all the discs, checking for a solution in each case. I chose to do this with five nested procedures, which each handle their disc with the appropriate minor variations. (A nested loop would have worked also.)

: solve4 ( -- bool )
    12 0 u+do
        solved? if drop true leave else disc4 1 rot-disc then

: solve3 ( -- bool )
    12 0 u+do
        solve4 if drop true leave else disc3 2 rot-disc then

: solve2 ( -- bool )
    12 0 u+do
        solve3 if drop true leave else disc2 3 rot-disc then

: solve1 ( -- bool )
    12 0 u+do
        solve2 if drop true leave else disc1 4 rot-disc then
: solve ( -- bool )
    12 0 u+do
        solve1 if drop true leave else disc0 4 rot-disc then

Now, I just need to run the solve procedure. It should return -1 (true) and then I can print the board with the command board 48 dump, which prints the board memory.

Unfortunately, I did this, and after a few seconds, the program instead return 0 (false) meaning there is no solution. Naturally, I expected there was some fault in my coding, and I dived into debugging. After an hour of carefully checking code, and inserting debugging code here and there, I was still getting the same result, and getting discouraged.

At one point, I inserted some code that would, at least, allow me to see the closest solution. I found one solution that had all columns adding up to 42, and one column adding up to 47. I did a quick Internet search, and found this revelation on the Project Genius website!

Notice from Project Genius Inc of a defective early Grecian Computer product.

Yes, indeed, I happened to own one of the defective early models, which had a misprint. I edited my disc0 array to read 3 instead of 8 in that location (already corrected above). The edited program found the solution quickly.

christopher@nightshade ~/Repos/grecian-computer$ gforth grecian-computer.fs
Gforth 0.7.3, Copyright (C) 1995-2008 Free Software Foundation, Inc.
Gforth comes with ABSOLUTELY NO WARRANTY; for details type `license'
Type `bye' to exit
solve . board 48 dump -1 
7F1CC5748238: 01 05 09 07  0C 08 06 08 - 0A 03 0A 0C  16 1A 10 0E  ................
7F1CC5748248: 09 0D 05 09  0A 13 08 0C - 0B 04 0E 07  0F 0D 15 0E  ................
7F1CC5748258: 0F 09 09 0C  08 07 03 0E - 06 08 0A 0B  07 0B 0F 06  ................

One must translate between hexidecimal to decimal, and then map the four arrays of twelve bytes onto the board, which gives you the solution (SPOILER WARNING!)

The Forth code above is provided under the GPLv3+ license:

    Copyright 2020 Christopher Howard

    This program is free software: you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation, either version 3 of the License, or
    (at your option) any later version.

    This program is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    GNU General Public License for more details.

    You should have received a copy of the GNU General Public License
    along with this program.  If not, see <>.

CKOUT: 328P as clock source

Left: Nano serving as fuse bit programmer. Middle: Uno with 328P CKOUT fuse bit programmed. Right, 16Mhz signal coming out of pin 8 (PB0) of Uno.

Wanting to work with an AD9833 signal generator chip, which needs an external master clock source, I was wondering if I could somehow tap into the 16 Mhz clock already feeding the 328P. The answer was yes, it is possible on the 328P to feed this to pin PB0 (a.k.a., digital pin 8).

328P datasheet: Clock Output Buffer

The only tricky part is you have to program a fuse bit on the chip, which can not be done through self-programming, the way you normally upload code through the arduino bootloader. You need to set bit 6 (CKOUT) in the lfuse byte to 0:

So, you have to have a separate programmer, and also you must write the whole byte, meaning you want to be careful to preserve the other bit settings. Fortunately, through the ArduinoISP sketch, you can use another Arduino to program it.

This is fairly straightforward to wire up. However, somebody on #arduino IRC had to explain to me that it is necessary to put a 60 Ohm resistor across VCC and rst pins on the programmer, if using an Uno or Nano for the programmer. I didn’t catch that reading the tutorial.

Once wired up, you can use avrdude to write the lfuse byte. In my case.

avrdude -c stk500v1 -p m328p -P /dev/ttyUSB0 -b 19200 -U lfuse:w:0xBF:m

The last part of the command instructs avrdude to write byte 0xBF to the lfuse byte. A few things that might not be obvious about that: (1) in 328P fuse bytes, a “0” is considered the “programmed” state, the opposite of what you would intuitively expect; (2) I had to look at the boards.txt file in the arduino ide could to figure out that the “standard” byte value (for an MC used on an Arduino Uno board) is 0xFF. So, if I’m just changing bit 6 to zero, 0xFF needs to become 0xBF.

Screen photo of writing 0xBF to lfuse using avrdude

The fuse change was successful, and I was able to measure 16 Mhz out of PB0 (normally digital pin 8).

Forth SPI on Arduino

One byte (0xa6) transmitted from master out SPI pin using Forth

Arduino-FVM comes with only a few Arduino-function words, basically just a few for working with the digital pins. So the test for Forth was going to be: how difficult is it to access other microchip functionality using memory reads and writes? An encouraging first step was to implement SPI TX, using the information in the 328 datasheet.

C Code Example from 328 datasheet of SPI Master TX

First I needed some constants for the register addresses and bit numbers:

0x24 constant DDR_SPI
0x3 constant DD_MOSI
0x5 constant DD_SCK
0x2 constant DD_SS
0x4c constant SPCR
0x6 constant SPE
0x4 constant MSTR
0x0 constant SPR0
0x4e constant SPDR
0x4d constant SPSR
0x7 constant SPIF

Next I needed to set up the data direction bits for the MOSI, SCK, and SS pins, as well as set some bits in the SPCR register to control mode and communication frequency:

: setup-master-spi ( -- )
1 DD_MOSI lshift
1 DD_SCK lshift
1 DD_SS lshift
or or
1 SPE lshift
1 MSTR lshift
1 SPR0 lshift
or or

And here is a function for transmitting a single byte, after dropping the byte on the stack:

: tx-master ( ch -- )
SPSR c@ 1 SPIF lshift and

And here is a demo procedure for sending byte 0xA6 repeatedly:

: spi-demo

Now we can see that byte on the oscilloscope, from MOSI pin 11:

SPI signal for byte 0xA6

Byte 0xA6 equals 10100110, which you can understand from the signal image if you know that (1) signal low represents “1” and high represents “0”; (2) the X-scale is 2 microseconds, with one bit per microsecond; and (3) the first bit is the one microsecond of low signal just to the left of the Y axis.

Arduino FORTH: Register Access

Edit after more research: the approach below might not be best possible approach when working with GPIO pins, as it might not be taking advantage of special opcodes for this purpose. Also, due to the two byte FVM cell size, I think there might be some potential for strange effects in nearby registers of a different type (like, the PINC register being after the PORTB register). Heading back to the data sheets…

Edit 2: It looks like FORTH (including Arduino-FVM) has the C@ and C! commands which are single-byte (char) versions of @ and !.

The Atmel specific keywords that come with Arduino-FVM are rather limited – basically just PINMODE, DIGITALREAD, and DIGITALWRITE. So, to do much of interest you would want to start playing around with the atmel microprocessor registers. This is mostly straightforward, however, as the registers are accessible simply as locations in ram, meaning you just write or read bits to ram to get what you want. Doing this in FORTH, you need a few tools

  • @ word: read from a memory location
  • ! word: write to a memory location
  • HEX word: switch to hexidecimal interpretation of the stack input/output (DECIMAL to switch back).
  • Pinout for your arduino board (available on the internet)
  • Data sheet for your specific microcontroller (available on the internet)

Here is a quick example of lighting up the LED through a register write. First, we need to know our pin number and also which register we are dealing with, available from the pinout.

Arduino Nano Pinout

There we have pin number 13 (decimal) for the LED, and register PB5. First, to keep this post a bit shorter, we we simply use the PINMODE keyword to set pin 13 to output mode:

true 13 pinmode

Now we look at the datasheet to get the memory location for register PB5.

A page from 328P Datasheet

So, PORTB register is at 0x25 (hex) and bit five is what we want. Now, let’s see what is already in that memory location. On my chip, I got:

0x25 @ . 0

Just keep in mind however, as you can see using the CELL command, that you have actually read in two bytes. So, if you get something like 0x2000, you are only interested in the first byte (the right-most 00).

As a general practice, I only want to write to the bit of interest, preserving other bit states. So, I drop a 1 for that bit on the stack, and use an OR to light up just that bit. A 1 in bit 5 is hex 0x20.

0x25 @ 0x20 or 0x25 ! 

And the LED lights up. We can see now what we have in register memory:

0x25 @ . 20

That is a trivial example, but I think you would need to go into this memory “peeking” and “poking” in order to do more advanced things like control the interrupt system or special purpose pins. At least, I find the idea more appealing than having to write C interface functions on the backend. Of course, you would want to hide the details inside nice forth functions.

Functions as parameters in FORTH

I was looking for something like the lambda in FORTH. It turns out there is the single quote operator which puts the “execution token” of a word on the stack, which you can EXECUTE later.

To give a practical example of such use, here is a maparray function:

: maparray ( xt a- n -- )
        dup 0 >
            -rot ( n1 xt a- )
            dup @ ( n1 xt a- n2 )
            swap ( n1 xt n2 a- )
            -rot ( n1 a- xt n2 )
            swap ( n1 a- n2 xt )
            dup >r ( n1 a- n2 xt, xt )
            execute ( n1 a- n3, xt )
            over ( n1 a- n3 a-, xt )
            >r ( n1 a- n3, xt a- )
            swap ( n1 n3 a-, xt a- )
            ! ( n1, xt a- )
            1 - ( n4, xt a- )
            r> ( n4 a-, xt )
            cell + ( n4 a2-, xt )
            swap ( a2- n4, xt )
            r> ( a2- n4 xt )
            -rot ( xt a2- n4 )
    drop drop drop

With this function, I can pass in the execution token, an array address, and the length of the array (in cells) and the execution token is executed on each array element, with the results stored back in the array.

christopher@nightshade ~/Repos/forth-learning$ gforth func.fs
Gforth 0.7.3, Copyright (C) 1995-2008 Free Software Foundation, Inc.
Gforth comes with ABSOLUTELY NO WARRANTY; for details type `license'
Type `bye' to exit
create a 1 , 2 , 3 , 4 , 5 , .s <0>  ok
a 5 cells dump                 
7FCF3CC56378: 01 00 00 00  00 00 00 00 - 02 00 00 00  00 00 00 00  ................
7FCF3CC56388: 03 00 00 00  00 00 00 00 - 04 00 00 00  00 00 00 00  ................
7FCF3CC56398: 05 00 00 00  00 00 00 00 -                           ........
: foo 1 + ;  ok                
' foo a 5 maparray  ok         
a 5 cells dump                 
7FCF3CC56378: 02 00 00 00  00 00 00 00 - 03 00 00 00  00 00 00 00  ................
7FCF3CC56388: 04 00 00 00  00 00 00 00 - 05 00 00 00  00 00 00 00  ................
7FCF3CC56398: 06 00 00 00  00 00 00 00 -                           ........

So, basically, the maparray function takes a function that acts on one element, and foo here is a function that adds one to an element, and I pass foo into maparray.