Keeping up the tradition I started last year with A small collection of uLisp challenges, here is a collection of amusing uLisp problems to challenge your brain cells at this festive time of year. I’ll give the answers in ten days’ time.
A number trick
Here’s a hexadecimal number trick you can try with a 32-bit copy of uLisp, such as the versions for ARM, ESP32, or STM32 boards (or a copy of Common Lisp).
- Think of any three-digit hexadecimal number.
To demonstrate the trick we’ll use #xABC, but you should choose a different one.
- Write it twice; so our number now becomes: #xABCABC.
- Set it to a variable, with a command such as:
> (defvar n #xABCABC) n
- Divide it by #x11, using truncate to ignore any remainder:
> (setq n (truncate n #x11)) 662268
- Now divide it by #xF1, again ignoring any remainder:
> (setq n (truncate n #xF1)) 2748
The final result is 2748.
Now see what the decimal value of your original hex number was:
> #xABC 2748
Amazingly it’s the same result! How does this work?
A strange recursive function
This unusual recursive function r is defined as follows for non-negative values of n:
r(n) = n + (n & r(n-1))
where & is the bitwise logical AND operation.
Its behaviour is quite erratic; for example:
r(336) is 672, but r(337) is 337.
How can you implement the function in Lisp?
A deceptively simple maze
This is a more difficult variant of the Tweetmaze I described in the uLisp examples:
In this “Offset Tweetmaze” you start from the ‘+3’ on the left, and the aim is to find a route to the ‘0’ on the right in the smallest number of left or right jumps.
The number on each square tells you how the size of your jump changes. The starting number is +3, so initially the length of your jumps is 3, and your only choice is to jump three cells to the right.
You land on a cell marked -2 so now the length of your jumps is reduced to 1, and you have a choice of jumping one cell to the left or one cell to the right from that cell. Note that negative jumps aren’t allowed.
Continue in this way and find the smallest number of jumps that will take you to the rightmost cell.
Try and solve this maze by hand. Then check your solution by writing a uLisp (or Common Lisp) program to solve it; you might find the original Tweetmaze program useful as a starting point.
Converting kilometers to miles
Suppose you are developing a GPS-based program in uLisp that will display the distance travelled, in km or miles, on a 7-segment display. The kilometer display will handle up to 32767 km. However, we also want the option of displaying the distance in miles, which involves dividing this value by 1.609344. The problem is that you’re using an 8/16-bit platform, which only handles signed 16-bit integers in the range -32768 to +32767.
The task is to write a function km-miles that will convert its argument from km to miles using 16-bit integer arithmetic, and get the result accurate within a mile over the whole range 0 to 32767 km.
For example, your function should convert 23456 km as follows:
> (km-miles 23456) 14575
Hint: a good approximation to 1.609344 is 103/64.
Interpreting a 16-bit value as signed
There are versions of uLisp running with both 16-bit signed integers and 32-bit signed integers.
Suppose you have a 16-bit value representing a signed integer. On a 16-bit version of uLisp the value will automatically be interpreted as a signed integer; for example:
> #xFFFF -1
However, on a 32-bit version of uLisp it will be interpreted as a 32-bit signed integer:
> #xFFFF 65535
In this case you can use the following function to convert it:
(defun s16 (d) (- (logand d #x7FFF) (logand d #x8000)))
> (s16 #xFFFF) -1
However, this function gives arithmetic overflow on an 8/16-bit platform.
What if you want a routine that will work identically, irrespective of whether it’s running on an 8/16-bit or 32-bit platform? This is a common problem when interpreting the values from peripherals, such as sensors.
Design a uLisp function that treats its argument as a 16-bit signed integer, independently of the platform it’s running on. In other words:
should return -1 on both 8/16-bit platforms and 32-bit platforms.