Here’s the code and a solution.
Below is a detailed explanation of the approach.
Multiple Encodings for Letters
If we choose this representation for A:
[ ] [ ] [ ] [ ] [ ] [X] [X] (A)
And this for B:
[ ] [ ] [X] [ ] [ ] [X] [X] (B)
We can then change an A to a B on a punch card by punching an additional
hole. But we can’t transition from B to A since that would require
unpunching a hole, which isn’t allowed.
Since we must be able to transition from A to B and from B to A, we
must have an encoding of A with less holes than an encoding of B, and
also an encoding of A with more holes than an encoding of B.
Therefore, each letter must have multiple encodings.
First Pass Always Uses the Same Hole Pattern
The first punch encoding for a letter is the pattern we punch for that letter when we are presented with a blank row.
It may be possible to use multiple encodings of the same letter each time we wish to punch it on a blank row; however, if a solution exists which has multiple first-punch encodings for the same letter, then a solution which uses only one first-punch encoding for each letter also exists.
Proof: Take any solution which has multiple first-punch encodings, and simply restrict the encoder to use one of the first-punch encodings. This solution still allows us to encoding all of the letters, and it still allows us to repunch once to any other letter, by virtue of the original solution having had this property for each encoding.
First Pass Uses Fewest Holes Possible
Since we cannot unpunch, the more holes we punch on the first pass, the fewer we can punch on the second pass.
Imagine we choose 1101101 as the first-punch representation for "A". We
only have two spaces left to punch, which means we can only transition to
three other encodings: 1111101, 1101111, and 1111111. We have shot
ourselves in the foot because we need to be able to transition to at least 25
other encodings.
Therefore, we want our first-pass encodings to use as few hole punches as possible. It turns out that we do not need to make more than two punches among seven spaces to encoding 26 letters, and so the first-pass encodings are:
0000000 A 0001000 H 0010100 O 0110000 V 0000001 B 0001001 I 0011000 P 1000000 W 0000010 C 0001010 J 0100000 Q 1000001 X 0000011 D 0001100 K 0100001 R 1000010 Y 0000100 E 0010000 L 0100010 S 1000100 Z 0000101 F 0010001 M 0100100 T 0000110 G 0010010 N 0101000 U
The Bit-Pattern Representation
Seven bits can represent 128 values (from zero through 127). We can make use of computers' internal representation of integers with a loop that looks like so:
for (int v = 0; v < 128; ++v) {
// code here
}The function __builtin_popcount is a GCC extension that returns the number
of set (1) bits in an integer, e.g.:
assert(__builtin_popcount(0) == 0);
assert(__builtin_popcount(9) == 2);
assert(__builtin_popcount(127) == 7);This allows us to find all patterns with no more than two bits set like so:
for (int v = 0; v < 128; ++v) {
if (__builtin_popcount(v) > 2) continue;
// code here
}Further, given an initial encoding first and a proposed encoding second,
we can determine if it’s possible to reach second from first only by
punching new holes in this way:
if ((first & second) == first) {
// we can reach second from first
}& in this context is a bitwise-and; the result of the operation is a number
where a bit is set only if it is set in both the left and right operands.
This also gives us a convenient way of mapping encodings to values:
signed char mapping[128];In this case, mapping[v] provides the letter (0-25) for the encoding v.
The value -1 indicates that v hasn’t been mapped.
The Transition Grid
Imagine a 26 by 26 grid where each row (the i index) is labelled with the letter first punched on a row of a card and each column (j) is labelled with the second letter desired. Each box can contain an encoding, with the following rules:
-
It must be possible to reach the encoding in the box from the first-pass encoding of the letter on that role.
-
An encoding cannot appear in boxes in two different columns.
Approach
The final solution is pretty simple. I think it’s more complicated than it needs to be, honestly.
