brhfl.com

A while back, I got an idea stuck in my head. If one wanted to, say, scratch a series of tick-marks into small bits of metal to serialize and identify them, how would one do this? Small is key here; easily printing decimal numbers may not be possible, and something like a binary number may be limited in length. The obvious solution, to me, is a flexible, two-dimensional binary grid. But what happens when you make a mark like this:

Expecting a human to perfectly line up a series of marks is rather unreasonable. This example is probably 3x2, but that last column is far enough away from the second that… maybe there’s an empty column in between? We have plenty of numbering systems that are wasteful, they don’t actually represent as many numbers as the most efficient use of that radix would allow (binary-coded decimal is probably the most common example). Why not waste bits to remove ambiguity? Put in place a requirement that every row and every column contain at least one tick. Under this system, we know that the above grid is 3x2. Even if we push the third column far, far away, we only have ticks in three columns and we only have ticks in two rows:

…and it remains a 3x2 grid for our purposes. There are other solutions – explicitly indicate the dimensions somewhere near the grid, or use two different sorts of markings to indicate 1/0 states. But I was interested in my original idea, and it proved to be a bit of a white whale for me as I thought about it on-and-off over the past month. For illustrative purposes, I will use 0s and 1s from this point forward in this post.

The first step was figuring out just how many values could be encoded in a given grid size. If, for a 3x2 grid, we allowed all combinations of 0s and 1s, we’d have 64 possible values. But we’ve added a pretty strong restriction:

Through a combination of Excel and Vim, I manually generated valid state counts for 2x2, 3x2, 3x3, and 4x2 (7, 25, 265, 79 respectively). A quick trip to the OEIS brought up a few sequences, including A183109, “Triangle read by rows: T(n,m) = number of n X m binary matrices with no zero rows or columns (n >= 1, 1 <= m <= n).” Read out as a triangle, we can glean the total number of valid states for a grid of any size. Once I knew what I was looking for, this was a pretty simple part of the puzzle to crack. Could I, however, devise a system that would make this human-readable and human-generable¹?

This proved much trickier, and while I’m satisfied with my conclusion so far, it may be possible to improve upon. I also will only be speaking in terms of 3x2 from this point forward, as I have not put any effort into generalizing the process yet². Coming up with something even remotely practical has frustrated me to all hell over the past month. There are things that are definitely known: mainly that we have at maximum six and at minimum 3 ticks. There are different numbers of possibilities for each of these: grids with 3 and 5 ticks have 6 valid states each, 4 ticks has 12, and 6 ticks has only 1. Let’s define some positions:

Initially, it seemed like position a was a good place to start, and that if a was alone row- and column-wise, than e and f have to be set. This felt like a good state for 1. Likewise, if b is alone row- and column-wise, d and f need to be set, which we can call 2.

…but now what? With one isolated tick, it’s easy to identify it as a key and use its position to determine our value. But how do we make 7 just as easy? We can’t simply repeat a similar process if both a and b are set. Among other problems, we’ve already used one of those states for 6. This became a recurring issue as I experimented with methods – I would hit a point where a value collided with an earlier value, and I’d have to try to add rules to avoid such collisions. Adding rules quickly made the process too difficult to mentally sort out. I set the concept aside for a week or so.

Then I dreamt about a fantastical mathematical machine. A giant orb with pronged arms, very similar to the mechanical binary-coded arms of an IBM Selectric. These, however, were notched in ternary. The orb interfaced with the world around it in an incredible display of cogwork, effortlessly decoding values and spitting out numbers. I got to thinking about the problem again.

Whereas before I had largely been thinking about ways to count, to indicate adding and carrying a value through multiple passes, I began to think about different ways of composing values. I thought about pairing up neighboring elements to make 7 2-bit states. I thought about powers of two. I realized I likely needed subtractive positions since there are a minimum of three ticks. Then it occurred to me that I needed to invert the grid first, use the empty (0) values as indicators. There can’t be only one tick, but there can be only one empty spot. This makes 1 a possible value without any subtractive elements. Mapping things out this way, I thought about diagonally bouncing 1-3 and 5-7 (1+2+3+5+6+7=24, so that felt plausible). I thought about powers of two, again, with 1, 2, 2, 4, 8, and 16. I somehow landed on 1, 1, 3, 6, 6, 11 and 1, 1, 2, 3, 6, 11 as magical, hopeful sequences.

None of these worked. Two things would happen: I would run into duplicates, and I would get stuck at a value much lower than 24. As an example:

What I ultimately stumbled upon came of the defining rule of positioning, whether we’re talking about binary, ternary, decimal, or any other radix. In a four-bit binary number, the positions are 8 4 2 1. Each position represents the lowest number that we can’t yet compose. 1+2=3, so our next position must be 4. Our grid works the same way, the rules just aren’t as simple. Again, using the zeroes or empty spaces as our ‘bits’ instead of the ones or ticks, we end up with this decoding pattern:

This is not perfect. It’s obvious that the only way to construct 20 is 17+3, which is an invalid state. So, if incremented values are important, this maxes out at 19. There are, however, no duplicates, which means we do still have five more valid values (since we’re using the empty states as indicators, a full grid of ones represents our first value, zero). We end up with 0-19, 23-25, 28, and 30.

I’m fairly happy with these results, and I think it’s the most effective solution that’s human-readable, and has a key that’s easily human-generable. Generation is basically a spiral of what we are thus unable to compose. We can’t add 1+2 in a valid state, so the next value must be 3. From here we can make 1, 2, 3, 4, 5, but we can’t make 1+5, so our next value must be 6. That row can’t be summed up, so our next value must be 11. And we can’t add 11+6, so our final value must be 17.

I mentioned in an earlier footnote that I have played with a 4x2 grid, which maxes out at 42³ continuous values. This is intended to be the first post in a series, the next of which will hopefully have some insight as to generalizing the process. If I can figure out how to set Sentient on the problem, I wouldn’t mind seeing what it comes up with as well.