Store eight bits on a punched card

Question

A little while back, data was frequently stored on punched card. A typical card would have 80 columns of 12 possible 'punch' positions. A plethora of encodings was used, each for their own specific purpose.

These days we like to think of a byte as 8 bits. In this challenge, you're tasked to convert an 8-bit byte to a 12-bit word so that it may be stored on a punched card. Since too many holes per column would weaken a punched card considerably, your encoding must adhere to the following rules,

• No more than 3 holes punched per column (i.e., no more than 3 bits set per 12-bit word)
• No more than 2 holes punched consecutively in the same column (i.e., no more than 2 consecutive bits set in each word)

There are 289 valid 12-bit punch cards, of which 1 has 0 holes, 12 have 1 hole, 66 have 2 holes, and 210 have 3 holes. Compare this to 256 8-bit sequences.

You must create two programs/functions: one of which takes a 8-bit byte and converts it to a 12-bit word according to an encoding of your choice that follows the above rules; and one of which takes a 12-bit word according to your encoding and converts it back to an 8-bit byte. The latter program may exhibit undefined behaviour for any input which is not contained in your encoding.

Input and output is flexible according to the defaults for I/O, and may even differ between your programs. Your score is the sum of the bytecount of both programs. The programs must work independently, so they may not 'share' code between them.

Answer 1

JavaScript (ES6),  103  100 bytes

See also my other answer for less bitwise operations, more maths, and a closed-form expression

Both functions expect and return an integer.

8-bit → 12-bit ( 56  53 bytes)

f=n=>n&&(w=f(n-1),w+=(x=w&w-1)&x-1?w-x:1)+(w&w/2&w/4)

Try it online!

How?

This is a recursive function that computes the next valid 12-bit word \$w_{n+1}\$ directly from the previous valid word \$w_n\$.

Step 1: Update w according to the total number of bits set

Given w from the previous iteration we first compute:

x = w & (w - 1)

which is w without its least significant bit.

Likewise, we remove the least significant bit from x by doing:

x & (x - 1)

If the result is zero, we just increment w.

If the result is non-zero, it means that there are already 3 bits set in w and we are not allowed to insert a 4th one. In that case, we add the least significant bit of w (which is w - x) to w. This results in at most as many bits set in the updated value than in the original one, or less in case of carry propagation.

Examples:

110010 +  10 -> 110100
101100 + 100 -> 110000

Step 2: Update w according to the number of consecutive bits set

We now have to make sure that there are not 3 consecutive bits set in w. We do that by adding the result of a bitwise AND between w, w / 2 and w / 4.

Example:

01110 + (01110 & 00111 & 00011) -> 01110 + 10 -> 10000

12-bit → 8-bit (47 bytes)

f=w=>w&&!(w&w/2&w/4|(y=(x=w&--w)&x-1)&y-1)+f(w)

Try it online!

How?

In this version, we decrement w at each iteration and increment the final result whenever w is a valid 12-bit word. We stop when w = 0.

We use the following methods to test the validity of w. They are similar to the ones used above.

• we compute w & w / 2 & w / 4 to make sure that there are not 3 consecutive bits set
• we compute a chain of three w & (w - 1) to make sure that there are no more than 3 bits set

Answer 2

APL (Dyalog Unicode), 21 + 22 = 62 43 bytes

⎕⌷⍋(+/+3∊3+/⊢)¨,⍳12/2

and

⎕⍳⍨⍋(+/+3∊3+/⊢)¨,⍳12/2

Try it online!

Pretty much the same programs, with indexing into an array (⌷) of valid punch cards for the encoder and finding the index (⍳⍨) for the decoder. Both the encoder and the decoder take a number and output a number.

Explanation

                ,⍳12/2     ⍝ Create every combination of 12 bits
    (         )¨           ⍝ Map each to
          3+/⊢             ⍝ Does the sum of each consecutive group of three bits
        3∊                 ⍝ Contain a 3 (1 if so, else 0)
     +/+                   ⍝ Add that to the total digit sum
   ⍋                       ⍝ And grade this list ascending
                           ⍝ This outputs the indexes (which are the same as parsing the original bits in base 2) in order of the smallest value to the largest

⎕⌷                         ⍝ Finally we either index the input into the list
⎕⍳⍨                        ⍝ Or find the index of the input in the list

Answer 3

Jelly, 13 + 12 = 25 bytes

8-bit byte (integer) -> 12-bit word (list of 1-indexed set bits):

3Ḋ12œcẎIÞṚị@‘

Try it online!

12-bit word (list of 1-indexed set bits) -> 8-bit byte (integer):

3Ḋ12œcẎIÞṚḊi

Try it online!

Here is a map (byte-integer word-as-12-bits word-as-1-indexed-set-bits) using the first Link.

How?

Both Links create a list of all (\$286\$) ways to punch either two or three holes as lists of 1-indexed holes (e.g. [3,7] represents 001000100000), sorts these by the incremental differences between those indices (i.e. [3,7] (001000100000) maps to [4] while [2,3,4] (011100000000) maps to [1,1]), and reverses that result (placing the \$11\$ of the form 0*110* at the very end, preceded by the \$10\$ (invalid ones) of the form 0*1110*, with \$265\$ usable patterns at the start).

The first Link finds the 0-indexed entry, while the second finds the 1-indexed index of the representation of a word in a dequeued version of the list (this then gives us a 0 when the input is not found).

3Ḋ12œcẎIÞṚ - niladic chain
3          - three
 Ḋ         - dequeued -> [2,3]
  12       - twelve
    œc     - combinations (vectorises)
             -> [[[1,2]…[1,12],[2,3]…[11,12]],[[1,2,3],[1,2,4]…[10,11,12]]]
      Ẏ    - tighten
             -> [[1,2]…[1,12],[2,3]…[11,12],[1,2,3],[1,2,4]…[10,11,12]]
        Þ  - sort by:
       I   -   incremental differences
               -> [[1,2]…[11,12],[1,2,3]…[10,11,12],[1,2,4]…[1,12]]
         Ṛ - reverse
               -> [[1,12]…[1,2,4],[10,11,12]…[1,2,3],[11,12]…[1,2]]
                  <- 265 valid -> <-   10 invalid  -> <- 11 valid->

ị@‘ - rest of Link 1: byte (integer), b
  ‘ - increment -> b+1
 @  - with swapped arguments:
ị   -   (b+1) 1-indexed index into (the list above)

Ḋi  - rest of Link 2: word (list of hole indexes), w
Ḋ   - dequeue (the list above) - remove the first word (representing the zero byte)
 i  - index of (w) (in that) - yields zero if not found

Answer 4

Python 3, 160 bytes

---

Python 3, 82 bytes

f=lambda b,n=0:0**b*f'{n:012b}'or f(b-(sum(map(bin(~n).count,('111','1')))<4),n+1)

Try it online!

Python 3, 78 bytes

[f'{i:012b}'for i in range(2181)if sum(map(bin(i).count,('111','1')))<4].index

Try it online!

The first function (8-to-12-bit) increments numbers resursively until the binary representation satisfies all criteria. The second function (12-to-8-bit) uses the index method of a filtered list.

The list in the second function has a __getitem__ method which could replace the first function, but this is 2 bytes longer.

Thanks to ovs and xnor for saving 6 bytes in total.

Answer 5

JavaScript (ES7),  167 144  143 bytes

8-bit → 12-bit ( 120 97  96 bytes)

This answer is definitely not very competitive, but I was curious to see how the conversion could be done without any recursion nor trial-and-error.

So here is a closed-form expression!

Expects and returns an integer.

n=>n<5?n:1<<(k=(54*n-166)**.333/2.1+.17)|2**(q=((n+=~~k*~k*~-k/6-3)*8)**.5-1>>1)|2**(n+q*~q/2-2)

Try it online!

How?

This is based on the observation that the positions of the bits in a valid 12-bit word are correlated to tetrahedral and triangular numbers.

If \$n\$ is less than \$5\$, we just return \$n\$. Otherwise, we go through the following steps:

• We first figure out what is the lowest \$k\$ such that \$T(k-1)\ge n-3\$, where \$T(k)\$ is the \$k\$-th tetrahedral number, defined as:

  $$T(k)=\frac{k(k+1)(k+2)}{6}$$

  \$k\$ is the real root of the following cubic equation, rounded towards \$0\$:

  $$x^3 + 3x^2 + 2x - 6(n-3) = 0$$

  Once solved with WolframAlpha's Cubic Equation Solver and after a few approximations (safe for our operating range), we end up with:

  $$\cases{ t=\left(\sqrt{\strut729(n-3)^2-3}+27(n-3)\right)^{1/3}\\ k = \left\lfloor\dfrac{t}{2.08} + \dfrac{0.694}{t}\right\rfloor }$$

  Fortunately, we don't need so much precision and it can be simplified to the following JS expression, which gives the correct result for \$4<n<256\$:

  k = ~~((54 * n - 166) ** 0.333 / 2.1 + 0.17)
  

• \$k\$ is the 0-indexed position of the leading bit in the punch card word.

• We define:

  $$p=n-3-T(k-1)$$

• If \$p>0\$, the position of the 2^nd bit in the punch card word is given by:

  $$q=\left\lfloor\dfrac{\sqrt{8p}-1}{2}\right\rfloor$$

  which is based on the reverse formula for triangular numbers.

  The JS implementation uses a right-shift. It means that we actually get \$-1\$ if \$p=0\$, in which case there's no 2^nd bit.

• The position of the 3^rd bit in the punch card word is:

  $$r=p-\frac{q(q+1)}{2}-2$$

  There's no 3^rd bit if \$r<0\$.

We use … | 2 ** expr rather than … | 1 << expr so that negative bit positions are ignored as expected.

Hybrid version (90 bytes)

For the record, below is my first attempt which was still using a limited number of recursive calls (up to 12) to compute \$k\$.

n=>n<4?n:(k=0,g=n=>n<0?2**~-k|2**(q=(p*8)**.5-1>>1)|2**(p+q*~q/2-2):g(n-k*++k/2,p=n))(n-3)

Try it online!

---

12-bit → 8-bit (47 bytes)

I didn't write a specific 12-bit to 8-bit converter for this answer. But because the sequence is exactly the same, we can just use the one we already have.

f=w=>w&&!(w&w/2&w/4|(y=(x=w&--w)&x-1)&y-1)+f(w)

Try it online!

Answer 6

Brachylog, 27 + 27 = 54 bytes

∧{ḃs₃ᵇ+ᵐ≤ᵛ2&ḃ+≤3&≜}ᶠ²⁵⁶;?∋₎

Try it online!

It's the same program! To decode 2240, give it as an argument and set the input to Z like here.

How it works

∧{ḃs₃ᵇ+ᵐ≤ᵛ2&ḃ+≤3&≜}ᶠ²⁵⁶;?∋₎
∧{                }ᶠ²⁵⁶     get the first 256 values of …
  ḃ                          in the base 2 representation …
   s₃ᵇ                        every 3 consecutive elements …
      +ᵐ≤ᵛ2                   has a sum ≤ 2
           &ḃ+≤3             and the base representation has a sum ≤ 3
                &≜           turn the constraints to a number
                       ;?∋₎ the number at index (input) is the output

Answer 7

Charcoal, 21 + 21 = 42 bytes

Encoder:

Ｉ§Φ׳φ››⁴Σ⍘ι²№⍘ι²111Ｎ

Try it online! Link is to verbose version of code.

Decoder:

Ｉ⌕Φ׳φ››⁴Σ⍘ι²№⍘ι²111Ｎ

Try it online! Link is to verbose version of code.

The only difference between the two programs is the second byte, which is § (AtIndex) for the encoder and ⌕ (Find) for the decoder. Explanation:

     φ                  Predefined variable 1000
   ׳                   Multiplied by 3
  Φ                     Filter on implicit range
        ⁴               Literal `4`
       ›                Is greater than
           ι            Current index
          ⍘ ²           Convert to a binary string
         Σ              Digital sum
      ›                 And not
               ι        Current index
              ⍘ ²       Convert to a binary string
             №          Count (contains)
                 111    Literal string `111`
                    Ｎ   Input as a number
 §                      Index into filtered results
 ⌕                      Find index in filtered results
Ｉ                       Cast to string
                        Implicitly print

Answer 8

C (gcc), 64 + 64 = 128 bytes

Saved 2 6 bytes thanks to Dominic van Essen!!!
Saved 9 bytes thanks to the man himself Arnauld!!!
Saved 2 bytes thanks to ceilingcat!!!

Encode \$8\$-bit to \$12\$-bit ^{85 \$\cdots\$ 66} 64 bytes

i;e(n){for(i=1;n;)n-=__builtin_popcount(++i)<4&i/(i&-i)!=7;n=i;}

Try it online!

Decode \$12\$-bit to \$8\$-bit ^{85 \$\cdots\$ 68} 64 bytes

j;d(n){for(j=0;--n;)j+=__builtin_popcount(n)<4&n/(n&-n)!=7;n=j;}

Try it online!

Explanation

Sequentially goes through integers starting at \$1\$ only counting ones with valid bit patterns and returns the \$n^{th}\$ valid integer from \$1\$ for encoding, \$e(n)\$, \$8\$-bit to \$12\$-bit. Counts the number of valid integers from \$1\$ up to \$n\$ for decoding, \$d(n)\$, \$12\$-bit to \$8\$-bit.

GCC builtins used

__builtin_popcount(n) returns the number of 1-bits in \$n\$.

Answer 9

Japt, 17 + 19 17 = 36 34 bytes

I'm not sure I've fully understood the challenge, but let's give it a go ...

8-bit to 12-bit, 17 bytes

Input as an integer, output as a binary string.

gI²o¤fÈè1 §3«Xø#o

Try it or run all test cases

12-bit to 8-bit, 19 17 bytes

Input as a binary string, output as an integer.

nI²o¤fÈè1 §3«Xø#o

Try it or run all test cases

Explanation

gI²o¤fÈè1 §3«Xø#o     :Implicit input of integer (first programme)
nI²o¤fÈè1 §3«Xø#o     :Implicit input of binary string (second programme)
g                     :Index into (first programme)
n                     :Convert from base (second programme)
 I                    :64
  ²                   :Squared
   o                  :Range [0,I²)
    ¤                 :To binary strings
     f                :Filter by
      È               :Passing each X through the following function
       è1             :  Count the "1"s
          §3          :  Less than or equal to 3
            «         :  AND NOT
             Xø       :  X contains
               #o     :  111
                 Ã    :End filter (second programme)
                  bU  :First 0-based index of U (second programme)

Answer 10

05AB1E, 36 (18 + 18) bytes

8-bit (integer) to 12-bit (string of 0s/1s) (18 bytes):

T12ãʒ1¢4‹}ʒƵAå≠}Iè

Try it online or verify all test cases.

12-bit (string of 0s/1s) to 8-bit (integer) (18 bytes):

T12ãʒ1¢4‹}ʒƵAå≠}Ik

Try it online or verify all test cases.

The only difference is the last byte (è vs k).

Explanation:

T           # Push 10
 12ã        # Take the cartesian product of "10" and 12:
            #  ["111111111111","111111111110","111111111101",...,"000000000000"]
    ʒ       # Filter it by:
     1¢     #  Count the amount of 1s
       4‹   #  And check that this count is smaller than 4
    }ʒ      # Filter again:
      ƵA    #  Push compressed integer 111
        å≠  #  And check that the string does NOT contain "111" as substring
     }I     # After the second filter: push the input
       è    # (8-bit to 12-bit) Get the string at the 0-based input index
       k    # (12-bit to 8-bit) Get the 0-based index of the input-string
            # (after which it is output implicitly as result)

See this 05AB1E tip of mine (section How to compress large integers?) to understand why ƵA is 111.

Answer 11

R, 42 + 61 = 103 bytes

Encoder

(a=combn(13,3)-1)[,a[1,]+2<a[3,]][,scan()]

Try it online!

Input as decimal number; outputs 3 positions to punch holes, with zero indicating no hole to punch.

Decoder

which(colSums(!((a=combn(13,3)-1)[,a[1,]+2<a[3,]]-scan()))>2)

Try it online!

Input as 3 positions of punched holes, in ascending order, prefixed with zero if only two holes are punched; outputs as decimal number.

How?

a=combn(13,3) generates all picks of 3 integers from 1..13, without repetitions, in ascending order. We subtract 1 to get all 2- and 3-hole combinations.
a=a[a[1,]+2<a[3,]] keeps only combinations where the lowest minus the highest position is less than 2, thereby removing any sets of 3 holes in a row.
To encode b, we choose the bth combination. To decode w, we subtract w from each combination: the correct combination is now all-zero, so its logical inverse is all-TRUE, so we select the combination that sums to 3.

Answer 12

Pyth, 14 + 14 = 28 bytes

Encoding:

@sDoS.+N^U2 12

Decoding:

xsDoS.+N^U2 12

Try encoding online! Try decoding online!

Both programs rely on the snippet sDoS.+N^U2 12, which creates a list of all possible length-12 lists of 0s and 1s, whose first 256 entries are all valid punch cards. This can be verified with this program: Verify it online!.

How the snippet works:

sDoS.+N^U2 12
       ^U2 12    Generate all length-12 lists of 0s and 1s.
  o              Sort by
    .+N            The deltas of the length-12 list
   S               sorted
sD               Sort by the sum of the length-12 list.

Sorting on the sorted deltas of the length-12 list moves lists with more alternations between runs of 0s and 1s to the front. This moves the lists with 3 1s in a row as their only 1s to the back. Sorting on the sum of the length-12 list then brings the lists with 0, 1, 2, or 3 1s to the front. Pyth's sort is stable, so this ends up with the valid punch sequences at the front.

I'm unsatisfied with the ^U2 12 part of the program to generate the base length-12 lists. If the rest of the program could handle strings, ^`T12 would save a character. If anyone can figure out how to save a character, I'd love to hear about it.