## Faro-encoding numbers

9th January 2016

I recently had an application in which I wanted to encode two positive integers, a and b, as a single encoded integer, c, with the following constraints:

• Usually the two integers would be small (less than 100), but they could each be as large as a million.
• The encoded integer c should be as small as possible.
• It should be possible to decode the integers without any additional information.

For example, one possible solution is to calculate 1000000 * a + b, but this doesn't satisfy the second condition, because for a=1 and b=2, c will be 1000002.

### The solution

The solution I came up with I've called Faro-Encoding, named after the Faro Shuffle, the technique for interleaving two piles of cards into a single pile. It forms the basis for many card tricks.

The Faro-Encoding works as follows:

• Express the two numbers in binary.
• Interleave the two bitstrings, right-aligned, so their bits alternate.
• Convert the result to a decimal integer.

### Faro-Encode

The Faro-Encode routine encodes two or more numbers:

```(defun faro-encode (&rest numbers)
(let ((n (length numbers))
(base 1)
(result 0))
(loop
(when (every #'zerop numbers) (return result))
(dotimes (i n)
(incf result (* base (logand (nth i numbers) 1)))
(setf (nth i numbers) (ash (nth i numbers) -1))
(setq base (* 2 base))))))```

Here's an example:

```CL-USER> (faro-encode 30 17)
854```

### Faro-Decode

The Faro-Decode routine takes an extra parameter to specify how many numbers have been encoded, and returns an array of the results:

```(defun faro-decode (n encoded)
(let ((a (make-array n :initial-element 0))
(base 1))
(loop
(when (zerop encoded) (return a))
(dotimes (i n)
(multiple-value-bind (d r) (truncate encoded 2)
(when (plusp r) (incf (aref a i) base))
(setq encoded d)))
(setq base (* 2 base)))))```

Here's an example:

```CL-USER> (faro-decode 2 854)
#(30 17)```

Previous: Tweetmaze solution