Lucky Machine Corp needs your help again.

One of our biggest customers (a crypto-analysis organization that can't be named) has been using our Punch-22 paper tape machines for almost five decades to record textual data from all manner of sources, for later analysis, on rolls of standard 7-hole paper tape.

The nature of the task only requires tabulating uppercase letters A–Z. No lowercase nor any symbols are used. For historical reasons they've been coding the letters using an old 5-bit code, as shown below, but they are willing to completely abandon this encoding going forward, as long as we provide the necessary firmware changes to the Punch-22.

Once the data from a roll has been read and processed the tape is of no further use and is thrown away. But because of recent budget cuts, they want to know if there's some way to reuse the roll.

It is a requirement that each 7-bit row on the tape represent one character, i.e. each character on the tape is independent of all the others. Any character can be read from the tape in isolation.

The Punch-22 is a read/write device and can examine the holes currently under the punch head before punching additional holes and advancing to the next row.

An example should give the flavor of the task. The figure shows an encoding for a four-character alphabet on a 3-hole tape, which allows the tape to be reused. There are two different ways to encode each character.

Let's say a B is recorded on the tape during its first use. The machine punches   ●. On the second use, if the character to be written is a B, then we leave it as   ●; there's no way to use the other code for B (●● ) anyway. If, however, we now need to overwrite an A on top of the B, we can use ●●●. Simlarly a C can now be punched as ● ●, and a D as  ●●.

Your task is to come up with a 7-bit code for the symbols A–Z that similarly allows one overwrite. Thank you, and remember: Get Lucky!

Solution checker in Haskell: here