title: Store eight bits on a punched card

text:
# Question
Title: Store eight bits on a punched card
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
# 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
> 18 votes

# Answer
# 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

```
> 7 votes

# Answer
# 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

```
> 7 votes

# Answer
# 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.
> 7 votes

# Answer
# 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 2nd 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 2nd bit.
* The position of the 3rd bit in the punch card word is:

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

There's no 3rd 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!
> 7 votes

# Answer
# 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

```
> 6 votes

# Answer
# 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

```
> 5 votes

# Answer
# 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\\$.
> 5 votes

# Answer
# 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)

```
> 4 votes

# Answer
# 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`.
> 3 votes

# Answer
# , 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 `b`th 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.
> 3 votes

# Answer
# 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 `0`s and `1`s, 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 `0`s and `1`s to the front. This moves the lists with 3 `1`s in a row as their only `1`s to the back. Sorting on the sum of the length-12 list then brings the lists with 0, 1, 2, or 3 `1`s 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.
> 2 votes

---
Tags: code-golf, binary, encoding
---


title: Fizz Buzz to Text

text:
# Question
Title: Fizz Buzz to Text
# Introduction

I don't *particularly* know where the fizz buzz trend came from. It might just be a meme or something, but it is somewhat popular.

# Challenge

Your job today is to convert Fizz Buzz into binary (0, 1) respectively, and convert that binary to text. Pretty standard stuff.

# How does that work?

FizzBuzzBuzzFizzBuzzFizzFizzFizz FizzBuzzBuzzFizzBuzzFizzFizzBuzz would translate into 01101000 01101001 then that would translate into "hi"

# Constraints

* Input is Fizz Buzz in a binary standpoint (see examples below.)
* Output must be text.
* You can assume the FizzBuzz input is right.
* This is , shortest bytes win.

# Input

> FizzBuzzBuzzFizzBuzzFizzFizzFizz FizzBuzzBuzzFizzBuzzFizzFizzBuzz FizzFizzBuzzFizzFizzFizzFizzBuzz

# Output

"hi!"

# Answer
## C, 59 bytes

```
i;f(char*s){while(*s&3?*s&9||(i+=i+*s%5):putchar(i),*s++);}

```

Magic numbers, magic numbers everywhere!

(Also, C shorter than Python, JS, PHP, and Ruby? Unheard of!)

This is a function that takes a string as input and outputs to STDOUT.

### Walkthrough

The basic structure is:

```
i;           // initialize an integer i to 0
f(char*s){
while(...);  // run the stuff inside until it becomes 0
}

```

Here, the "stuff inside" is a bunch of code followed by `,*s++`, where the comma operater returns only the value of its second argument. Hence, this will run through the string and set `*s` to every character, including the trailing NUL byte (since postfix `++` returns the previous value), before exiting.

Let's take a look at the rest:

```
*s&3?*s&9||(i+=i+*s%5):putchar(i)

```

Peeling away the ternary and short circuiting `||`, this can be expanded to

```
if (*s & 3) {
    if (!(*s & 9)) {
        i += i + *s % 5;
    }
} else {
    putchar(i);
}

```

Where do these magic numbers come from? Here are the binary representations of all the characters involved:

```
F  70  01000110
B  66  01000010
i  105 01101001
z  122 01111010
u  117 01110101
   32  00100000
\0 0   00000000

```

First, we need to separate space and NUL from the rest of the characters. The way this algorithm works, it keeps an accumulator of the "current" number, and prints it whenever it reaches a space or the end of the string (i.e. `'\0'`). By noticing that `' '` and `'\0'` are the only characters to not have any of the two least significant bits set, we can bitwise AND the character with `0b11` to get zero if the character is space or NUL and nonzero otherwise.

Digging deeper, in the first "if" branch, we now have a character that's one of `FBizu`. I chose only to update the accumulator on `F`s and `B`s, so I needed some way to filter out the `izu`s. Conveniently, `F` and `B` both have only the second, third, or seventh least significant bits set, and all the other numbers have at least one other bit set. In fact, they all have either the first or fourth least significant bit. Hence, we can bitwise AND with `0b00001001`, which is 9, which will yield 0 for `F` and `B` and nonzero otherwise.

Once we've determined that we have an `F` or `B`, we can map them to `0` and `1` respectively by taking their modulus 5, because `F` is `70` and `B` is `66`. Then the snippet

```
i += i + *s % 5;

```

is just a golfy way of saying

```
i = (i * 2) + (*s % 5);

```

which can also be expressed as

```
i = (i << 1) | (*s % 5);

```

which inserts the new bit at the least significant position and shifts everything else over 1.

"But wait!" you might protest. "After you print `i`, when does it ever get reset back to 0?" Well, `putchar` casts its argument to an `unsigned char`, which just so happens to be 8 bits in size. That means everything past the 8th least significant bit (i.e. the junk from previous iterations) is thrown away, and we don't need to worry about it.

Thanks to @ETHproductions for suggesting to replace `57` with `9`, saving a byte!
> 55 votes

# Answer
# Jelly, 9 bytes

```
Ḳm€4O%5ḄỌ

```

Try it online!
> 10 votes

# Answer
# Python 3, ~~169~~ ~~101~~ ~~93~~ ~~91~~ ~~85~~ 81 bytes

```
lambda s,j="".join:j(chr(int(j('01'[b<"C"])for b in c[::4]),2))for c in s.split())

```

Try it online!

Explanation:

```
lambda s,j="".join:  # Create a lambda function
    j(  # call "".join, adds characters together with nothing in between
        chr(  # character by int
            int(  # string to int
                j(  # "".join again
                    '01'[b<"C"]  # 1 or 0, based on what character we get
                    for b in c[::4]  # For every first of 4 characters
                ),
                2)  # Base 2
        )
        for c in s.split()  # for every group of Fizz and Buzz with any whitespace character after it
    )

```
> 9 votes

# Answer
# Bash \+ coreutils, ~~61~~ 50 bytes

*(-11 bytes thanks to Doorknob!)*

```
tr -d izu<<<$1|tr FB 01|dc -e'2i?[aPz0<k]dskx'|rev

```

Try it online!
> 9 votes

# Answer
## JavaScript (ES6), ~~80~~ 79 bytes

```
let f =

s=>`${s} `.replace(/.{4} ?/g,m=>m[s=s*2|m<'F',4]?String.fromCharCode(s&255):'')

console.log(f("FizzBuzzBuzzFizzBuzzFizzFizzFizz FizzBuzzBuzzFizzBuzzFizzFizzBuzz FizzFizzBuzzFizzFizzFizzFizzBuzz"))
```
> 8 votes

# Answer
# Japt, ~~26~~ ~~24~~ ~~19~~ 17 bytes

```
¸®ë4 ®c u5Ãn2 dÃq

```

Try it online!

Saved 2 bytes thanks to @Shaggy & 2 bytes thanks to @ETHproductions

### Explanation

```
input: "FizzBuzzBuzzFizzBuzzFizzFizzFizz FizzBuzzBuzzFizzBuzzFizzFizzBuzz FizzFizzBuzzFizzFizzFizzFizzBuzz"

¸®                // ["FizzBuzzBuzzFizzBuzzFizzFizzFizz","FizzBuzzBuzzFizzBuzzFizzFizzBuzz","FizzFizzBuzzFizzFizzFizzFizzBuzz"]
  ë4              // ["FBBFBFFF","FBBFBFFB","FFBFFFFB"]
     ®c           // [[70,66,66,70,66,70,70,70],[70,66,66,70,66,70,70,66],[70,70,66,70,70,70,70,66]]
        u5Ã       // ["01101000","01101001","00100001"]
           n2     // [104,105,33]
              d   // ["h","i","!"]
               Ãq // "hi!"

```
> 7 votes

# Answer
## Ruby, ~~65~~ ~~63~~ 60 bytes

```
->s{s.split.map{|x|x.gsub(/..../){$&.ord%5}.to_i(2).chr}*''}

```

This is an anonymous proc that takes input and gives output as a string.

```
->s{
s.split            # split on whitespace
.map{|x|           # for each word as x,
  x.gsub(/..../){  # replace each sequence of four characters with
    $&.ord%5       # the ASCII value of the first character, mod 5
                   # F is 70, B is 66, so this yields 0 for Fizz and 1 for Buzz
  }.to_i(2)        # interpret as a binary number
  .chr             # the character with this ASCII value
}*''               # join on empty string
}

```
> 6 votes

# Answer
# JavaScript (ES6), ~~95~~ ~~88~~ ~~85~~ 81 bytes

```
s=>s.replace(/..zz/g,m=>m<"F"|0).replace(/\d+ ?/g,m=>String.fromCharCode("0b"+m))

```

---

## Try it

```
f=
s=>s.replace(/..zz/g,m=>m<"F"|0).replace(/\d+ ?/g,m=>String.fromCharCode("0b"+m))
oninput=_=>o.innerText=f(i.value)
o.innerText=f(i.value="FizzBuzzBuzzFizzBuzzFizzFizzFizz FizzBuzzBuzzFizzBuzzFizzFizzBuzz FizzFizzBuzzFizzFizzFizzFizzBuzz")
```

```
*{font-family:sans-serif}
```

```
<input id=i><p id=o>
```
> 6 votes

# Answer
# Python 2, ~~90~~ ~~83~~ ~~82~~ 81 bytes

-1 byte thanks to totallyhuman
-1 byte thanks to Martmists
-1 byte thanks to Jonathan Frech

```
lambda x:''.join(chr(int(`[+(l<'D')for l in b[::4]]`[1::3],2))for b in x.split())

```

Try it online!
> 5 votes

# Answer
# Perl 5, 33 Bytes

```
print(pack'B*',<>=~y/FB -z/01/dr)

```

Replaces 'F' and 'B' in the input with 0 and 1 respectively, and deletes the other characters. It then uses perl's `pack` function to turn this bit string into ASCII characters.
> 5 votes

# Answer
# Octave, ~~59~~ ~~57~~ 53 bytes

```
@(s)['',bi2de(flip(reshape(s(65<s&s<71)<70,8,[]))')']

```

This doesn't work on TIO, since the communication toolbox is not implemented. It works fine if you copy-paste it to Octave-online. It's not even close to be working code in MATLAB.

Managed to save two bytes by transposing the matrix after flipping it, instead of the other way around.

### Explanation:

```
@(s)             % Anonymous function that takes a string as input
    ['',<code>]  % Implicitly convert the result of <code> to its ASCII-characters

```

**Let's start in the middle of `<code>`:**

```
s(65<s&s<71)      % Takes the elements of the input string that are between 66 and 70 (B and F)
                  % This gives a string FBBFFBBFBBBFFFBF...
s(65<s&s<71)<70   % Converts the resulting string into true and false, where F becomes false.
                  % Transformation: FBBFFB -> [0, 1, 1, 0, 0, 1]

```

Let's call the resulting boolean (binary) vector for `t`.

```
reshape(t,8,[])       % Convert the list of 1 and 0 into a matrix with 8 rows, one for each bit
flip(reshape(t,8,[])) % Flip the matrix vertically, since bi2de reads the bits from the wrong end
flip(reshape(t,8,[]))' % Transpose it, so that we have 8 columns, and one row per character
bi2de(.....)'          % Convert the result decimal values and transpose it so that it's horizontal

```
> 3 votes

# Answer
# Whitespace, 123 bytes

Visible representation:

```
SSNNSSNSNSSSNSNSTNTSTTTSSSTSSSSSNTSSTSNSNTSSNSSSTSSTTSNTSSTNTSTNSSSTNTSSSNSSTNSSNSNSSNSTNTSTNTSTNTSTSSSNSNNNSSSNSNTTNSSNSNN

```

Unobfuscated program:

```
    push  0
loop:
    dup
    push  0
    dup
    ichr
    get
    push  32
    sub
    dup
    jz    space
    push  38
    sub
    jz    fizz
    push  1
    add
fizz:
    push  0
    dup
    dup
    ichr
    ichr
    ichr
    add
    jmp   loop
space:
    swap
    pchr
    jmp   loop

```

There's nothing particularly odd about the implementation, the only real golfing is in some strange reuse of temporaries as well as not caring about the unbounded stack growth to skim down some more bytes.
> 3 votes

# Answer
# Perl 5, 28 bytes+4 bytes for flags=32 bytes

Run with the flags `-040pE`

```
$_=chr oct"0b".y/FB -z/01/dr

```

`-040` sets the record separator to a space so that perl sees each group of FizzBuzzes as a separate line, then loops over those lines, changing F to 0, B to 1, deleting everything else, then converting to binary and from there to ascii.
> 3 votes

# Answer
# Jelly, 9 bytes

```
Ḳm€4=”BḄỌ

```

Try it online!

```
Ḳm€4=”BḄỌ  Main Link
Ḳ          Split on spaces
  €        Map
 m 4       Take every fourth letter (F and B)
    =”B    Check if each letter is equal to B (gives the binary representation)
       Ḅ   Binary -> Integer
        Ọ  Unord; gives chr(i)

```

-3 bytes thanks to Erik the Outgolfer
> 2 votes

# Answer
# PHP, 67 Bytes

Limited to 8 letters

```
<?=hex2bin(dechex(bindec(strtr($argn,[Fizz=>0,Buzz=>1," "=>""]))));

```

Try it online!

# PHP, 77 Bytes

```
foreach(explode(" ",strtr($argn,[Fizz=>0,Buzz=>1]))as$v)echo chr(bindec($v));

```

Try it online!
> 2 votes

# Answer
# q/kdb+, ~~41~~ ~~40~~ ~~37~~ 33 bytes

**Solution:**

```
{10h$0b sv'66=vs[" ";x][;4*(!)8]}

```

**Example:**

```
q){10h$0b sv'66=vs[" ";x][;4*(!)8]}"FizzBuzzBuzzFizzBuzzFizzFizzFizz FizzBuzzBuzzFizzBuzzFizzFizzBuzz FizzFizzBuzzFizzFizzFizzFizzBuzz"
"hi!"

```

**Explanation:**

Split the input string on `" "` to give distinct lists of `FizzBuzz...`, index into each of these lists at the first character (ie `0 4 8 ... 28`). Return boolean list determined by whether each character is `"B"` (ASCII `66`). Convert these lists to base 10, and then cast result to string.

```
{10h$0b sv'66=vs[" ";x][;4*til 8]} / ungolfed solution
{                                } / lambda function with x as implicit input
              vs[" ";x]            / split (vs) input (x) on space (" ")
                           til 8   / til 8, the range 0..7 inclusive
                         4*        / vectorised multiplication, 0 1 2 3 => 0 4 8 12
                       [;       ]  / index the 2nd level at these indices (0, 4, 8 ... 28)
           66=                     / 66 is ASCII B, 66="FBBFBFFF" -> 01101000b
     0b sv'                        / join (sv) each row back with 0b (converts from binary)
 10h$                              / cast to ASCII (0x686921 -> "hi!")

```
> 2 votes

# Answer
# Brain-Flak, 107 bytes

```
{(((((()()()()){}){}){})({}[{}])()())((){[()](<{}>)}{}<>)<>{(<{}{}{}{}>)<>({}({}){})<>}{}}<>{({}<>)<>}<>

```

Try it online!

+3 bytes for the `-c` flag.

### Explanation

```
{                                        For each character in input:
 (((((()()()()){}){}){})({}[{}])()())    Push 32-n and 66-n
 ((){[()](<{}>)}{}<>)<>                  If character is B, push 1 on second stack.  Otherwise, push 0
 {                                       If character is not space:
  (<{}{}{}{}>)                           Burn 3 additional characters
  <>({}({}){})<>                         Multiply current byte by 2 and add previously pushed bit
 }                                       (otherwise, the pushed 0 becomes the new current byte)
 {}                                      Remove character from input
}
<>{({}<>)<>}<>                           Reverse stack for output

```
> 2 votes

# Answer
# JavaScript ES6 - 98 bytes

**too many bytes, but at least readable**

Defined as function it is 98 bytes

```
let s=>s.replace(/(F)|(B)|./g,(c,F,B)=>B?1:F?0:'').replace(/.{8}/g,v=>String.fromCharCode('0b'+v))

```

**test:**

```
"FizzBuzzBuzzFizzBuzzFizzFizzFizz FizzBuzzBuzzFizzBuzzFizzFizzBuzz FizzFizzBuzzFizzFizzFizzFizzBuzz"
.replace(/(F)|(B)|./g,(c,F,B)=>F?0:B?1:'').replace(/.{8}/g,v=>String.fromCharCode('0b'+v))

```

### Explanation:

```
/(F)|(B)|./

```

Matches the F and B letters and anything else as Groups

```
(c,F,B)=>F?0:B?1:''

```

is a Function that captures the groups , returns a 0 for F and 1 for B , or ''

c is the character matched
F and B are now Parameters!
the 3rd **.** group is ommitted as parameter

F and B are `undefined` when the 3rd group is matched
B is `undefined` when group F is matched

The resulting 0100.. etc string

is cut in slices of 8 bytes

```
.replace(/.{8}/g,v=>String.fromCharCode('0b'+v))

```

and processed as **0b** *binary* string
> 1 votes

# Answer
## Haskell, 72 bytes

```
(>>= \w->toEnum(foldl1((+).(2*))[mod(fromEnum c)5|c<-w,c<'a']):"").words

```

Try it online!

How it works

```
            words      -- split input string into words at spaces
(>>=      )            -- map the function to each word and flatten the resulting
                       -- list of strings into a single string
   \w->                -- for each word w
       [  |c<-w,c<'a'] -- take chars c that are less than 'a' (i.e. B and F)
     mod(fromEnum c)5  -- take ascii value of c modulus 5, i.e. convert to bit value
    foldl1((+).(2*))   -- convert list of bit to int
  toEnum(   ):""       -- convert ascii to char.  :"" forces toEnum to be of type String
                       -- now we have a list of single char strings, e.g. ["h","i","!"]

```
> 1 votes

# Answer
# shortC, 35 bytes

```
i;AW*@&3?*@&9||(i+=i+*s%5):Pi),*s++

```

Conversions in this program:

* `A` \- `int main(int argc, char **argv){`
* `W` \- `while(`
* `@` \- `argv`
* `P` \- `putchar(`
* Auto-inserted `);}`

Heavily based off of Doorknob's answer.
> 1 votes

# Answer
# APL (Dyalog Classic), 17 bytes

```
{82⎕DR'B'=⍵∩'BF'}

```

## Explanation

```
           ⍵∩'BF'    cut, removes all but 'BF' from ⍵
       'B'=          equals 'B' turns it into binary stream
 82⎕DR              converts into character stream

```

Try it online!
> 1 votes

# Answer
# Japt `-P`, 9 bytes

Or 8 bytes if input can be lowercase.

```
¸Ën"FB" d

```

Try it

```
¸Ën"FB" d     :Implicit input of string
¸             :Split on spaces
 Ë            :Map
  n"FB"       :  Convert from base "FB" to decimal, ignoring all other characters
        d     :  Get the character at that codepoint
              :Implicitly join and output

```
> 1 votes

# Answer
# 05AB1E, 15 bytes

```
#vy„FBÃS'BQ2βçJ

```

Try it online!
> 0 votes

# Answer
# Java 8, ~~117~~ 115 bytes

```
s->{for(String x:s.split(" "))System.out.print((char)Long.parseLong(x.replace("Fizz","0").replace("Buzz","1"),2));}

```

I doubt you can do a lot of the fancy regex replacements in Java like most other answers, mainly because you can't do anything with the captured capture-groups in Java-regexes.. (I.e. `"$1".charAt(...)` or `"$1".replace(...)` aren't possible for example.)

**Explanation:**

Try it here.

```
s->{                          // Method with String parameter and no return-type
  for(String x:s.split(" "))  //  Loop over the input split by spaces:
    System.out.print(         //   Print:
     (char)                   //    Each character
     Long.parseLong(          //    after we've converted each binary-String to a long
      x.replace("Fizz","0").replace("Buzz","1")
                              //    after we've replaced the Fizz/Buzz to 0/1
     ,2));
}                             // End of method

```
> 0 votes

# Answer
# Google Sheets, 94 bytes

```
=ArrayFormula(JOIN("",CHAR(BIN2DEC(SPLIT(SUBSTITUTE(SUBSTITUTE(A1,"Fizz",0),"Buzz",1)," ")))))

```

I'm not familiar with FizzBuzz binary but it seems that they're delineated by spaces so this formula relies on that. The logic is pretty simple:

* Replace `Fizz` with `0` and `Buzz` with `1`
* Split the result into an array using a space as a delimiter
* Convert each element from binary to decimal
* Replace each element with its ASCII equivalent
* Join each element without a delimiter
> 0 votes

# Answer
# , 20 bytes

```
a.{~_8#.\2-.~'FB'i.]

```

Try it online!
> 0 votes

---
Tags: code-golf, binary
---


title: Is this a robbery?

text:
# Question
Title: Is this a robbery?
### Backstory

You own a tiny jewellery shop in the suburbs of the city. The suburbs are too much overpopulated, so your shop has a thickness of *only one character* to fit in the busy streets.

Recently, there has been lots of cases of robbery on the neighborhood, and you fear that robbers will also come to get your bounty.

Therefore, you installed surveillance cameras to take care of the shop. But there is one *big* problem: **The cameras do not beep or alarm**.

---

You decide to program the security alarm by yourself. This will complete the contraptions and (hopefully) make your little shop safe and secure.

# Task

* Your surveillance cameras will map your shop like this:

```
WI  J E W

```

This is your input, which you can take from STDIN or from the command-line arguments. Each of the letters have different meanings.

+ **W** represents a *wall*. Robbers and intruders cannot pass through them.
    + **E** means *employees*. These are the beings that the cameras recognise. If they see an intruder, they will immediately set off the alarm before the robbers can do anything. (They can see an intruder if there is no *wall*, *jewel*, *intruder* or other *employee* in between) They also tend to stand still.
    + **J** means *jewels*. These are the stuff the robbers and intruders are looking for.
    + **I** means *intruder*. They are most likely robbers. Their goal is to steal (at least one of) the jewels of the shop.
    + Of course, you can create your own legend of the map for the sake of saving code bytes.
* Based on the input, you need to write a program (or function) that does the following:

+ If an *intruder* can freely put their hands on a *jewel* OR an *employee* can see an *intruder*:
        - Print a truthy value. ("1", "True", "Alert")
        - **To be completely alert, print the ASCII bell character.** (It has an ASCII code of 7. When printed, it plays a *ting* sound on lots of computers and implementations)
            * In most implementations, there cannot be a *ting* sound, so be carefull!
            * In some cases where the bell *absolutely cannot* be printed, print an exclamation ('!') instead of it. (Printing exclamation marks may be harder to implement in some languages)
    + Else:
        - Print a falsey value. ("0", "False", "Quiet")
* The shop *does not wrap around*.
* Welp, your computer runs slow when you run too much bytes. Try to program your code as short as possible. (`code-golf`)

### Example tests

```
STDIN:        EXAMPLE STDOUT:
WI  J E W     1(BEL)

WIWWJWE W     0

E I J I E     1(BEL)

I   W J E     0

I E W E E     1(BEL)

IIIIEIIII     1(BEL)

JJJJEJJWI     0

```

Note: "(BEL)" refers to the bell character, not the string.

### Good luck!

# Answer
> 9 votes
# Jelly,  ~~10~~  8 bytes

```
ḟ⁶OIA7fỌ

```

A full program which prints an empty string (falsey) if all is well or a bell character if not (a bell character is also truthy).

Input:

```
    Wall W
Employee X
   Jewel J
Intruder Q

```

**Try it online!**

Or see the test-suite (The footer first translates the characters from the example ones and calls the Link for each line).

### How?

```
ḟ⁶OIA7fỌ - Main Link: list of characters in "W QJX"
 ⁶       - a space character
ḟ        - filter-discard (remove any spaces)
  O      - to ordinals (e.g. "WXQJ" -> [87,88,81,74])
   I     - incremental differences (e.g. [87,88,81,74] -> [1,-7,-7])
           ...possible values are: -14 -13 -7 -6 -1 0 1 6 7 13 14
              -7 and 7 indicate an intruder (Q) is next to a jewel (J) or employee (X)
    A    - absolute values
     7   - seven
      f  - filter keep ([7] if any of the values are 7 else [])
       Ọ - cast to characters (bell character in a list or an empty list)
         - implicit print
           ...single-element lists print their element
              while empty lists print an empty string

```

# Answer
> 9 votes
# Brachylog, 17 12 10 bytes

*-5 bytes by not distinguishing between Employees and Jewels*

*-2 bytes using addition, not multiplication, so I get 7 for \a for free*

Empty tiles are `-`, intruders are also `h`umans, jewels are still `J`ewels, the shop employees are `e`, and walls `>` are closing in. In Brachylog a predicate succeeding is the truthy value. So it's either a value as an output (`BEL`) or the unification failed, represented as `false.`.

```
ạ%₉ᵐs+7g~ạ

```

Try it online!

This is all done so the bytes modulo 9 `ạ%₉ᵐ` map `(empty) => 0, I => 5, J => 2, E => 2, W => 8`. With this, we can sum every subset of consecutive elements `s+` and check if one of them is `7` (`I J`, i.e. `5+0+0+2` or `E I`, i.e. `2+0+0+5`). Because empty tiles map to `0`, they don't change the value, and neither does the order. Also 7 cannot be made by other elements. If one subset matches, return convert 7 to a byte `~gạ`, which is `\a`.

# Answer
> 6 votes
# 05AB1E, 7 bytes

```
áÇ¥Ä7Ãç

```

Port of *@JonathanAllan*'s Jelly answer, so make sure to upvote him as well!

Just like his answer, I use `W`=wall; `J`=jewel; `X`=employee; `Q`=intruder.
Outputs one or multiple BEL characters in a list as truthy value or an empty list as falsey value.

Try it online or verify all test cases.

**Explanation:**

```
á        # Only keep the letters of the (implicit) input-string (removes spaces)
 Ç       # Convert each character to its codepoint integer
  ¥      # Get the forward difference between each codepoint pair
         #  (one of: [-14,-13,-7,-6,-1,0,1,6,7,13,14])
   Ä     # Take the absolute value of each difference
    7Ã   # Only keep all 7s in the list
      ç  # And convert those 7s (if any) to an ASCII character with this codepoint
         # (after which the resulting list is output implicitly as result)

```

# Answer
> 5 votes
# Python 3, 52 bytes

Uses `#` instead of  for empty spaces and  instead of `W` for walls. Output is an empty string as a falsey value and the bell character for truthy inputs.

```
lambda s:any({*'I#'}<{*g,'#'}for g in s.split())*''

```

Try it online!

# Answer
> 4 votes
# JavaScript (ES6),  ~~33~~  28 bytes

*Saved 5 bytes thanks to @DomHastings!*

Expects `e` for a jewel, and the characters defined in the challenge for the other items.

The unprintable `BEL` is escaped below.

```
s=>/E *I|I *E/i.test(s)&&'\7'

```

Try it online!

# Answer
> 4 votes
# AWK, ~~47~~ \\$\cdots\\$ ~~27~~ 26 bytes

Saved ~~2~~ ~~3~~ ~~7~~ 8 bytes thanks to Dominic van Essen!!!
Has unprintable bell character in quotes.

```
$0=/[EJ] *I|I *[EJ]/?"":0

```

Try it online! (With printable bell)

If there's possibly danger at hand outputs bell character (truthy) or outputs 0 (falsey) otherwise.

# Answer
> 3 votes
# perl -pl, 26 bytes

```
$_=/I *[EJ]|[EJ] *I/?"^G":0

```

Try it online!

Since it's hard to enter unprintable characters, the bell character is here (and in TIO), represented by the two character combo `^G`. In the real program, this is the character with ASCII code 7 (so, I'm counting it as 1 character).

# How does it work?

All the described cases boil down to an intruder next to either some jewels or an employee. So we use a regexp to detect this case.

# perl -pl, 15 bytes

```
s/E *I|I *E/^G/i

```

Try it online!

Here, "truthy" is taken to "contains a BEL character", and "falsey" as "does not contain a BEL character". And it uses @Dom Hastings suggestion of using `e` as the symbol for jewels.

# perl -F/\[EJ\]\s\*I|I\s\*\[EJ\]/ -pl, 13 bytes

```
$_=@F>1?"^G":0

```

Try it online!

We can offload part of the work to a command line switch, and reduce it to 13 bytes.

# Answer
> 3 votes
# Pip, ~~26~~ 21 bytes

```
3NST(_-BMPaRMs)?o.'!i

```

Try it online!

-5 bytes after Dominic Van Essen's input changes.

Takes inputs as:

```
8 → Wall
4 → intruder
7 → Jewel
1 → Employee

```

Takes the differences, converts to string, checks if there's 3 in the string representation.

# Answer
> 2 votes
# Pyth, 13 bytes

```
*\lf&/TN@GTc

```

Try it online!

### Legend

* `j` \- jewel
* `e` \- employees
* `"` \- intruder
* \- wall
* `#` \- empty

## Explanation

```
*\!lf&/TN@GTc
    f          # filter
            c  # input split on whitespace chars
               # with lambda T:
         @GT   #     some lowercase alphabet in T
     &/TN      #     and '"' in T
*\!l           # output '!' repeated length of results of filter times

```

# Answer
> 2 votes
# , 74 bytes

```
function(x)`if`(grepl('IE|EI|IJ|JI',gsub(' ', '',x)),intToUtf8(c(49,7)),0)

```

Try it online!

# Answer
> 2 votes
# C (gcc), 97 bytes

```
i;j;r;t;f(char*s){for(i=j=r=0;t=*s++;t==87?i=j=0:0)i|=t==73,j|=t==74|t==69,r|=i&j;r&&putchar(7);}

```

Try it online (with exclamation point instead of bell since TIO can't handle it)

# Answer
> 1 votes
# Charcoal, 18 bytes

```
×!⊙⪪EIIEIJJI²№⁻θ ι

```

Try it online! Link is to verbose version of code. Outputs `!` since BEL isn't in Charcoal's code page. Explanation:

```
    EIIEIJJI        Literal string `EIIEIJJI`
   ⪪        ²       Split into 2-character substrings
  ⊙                 Any substring satisfies
             №      (non-zero) Count of
                 ι  Current substring in
               θ    Input string
              ⁻     With spaces deleted
×!                  `!` if the above is true
                    Implicitly print

```

---
Tags: code-golf, string, game, tiling
---


title: Hofstadter H-sequence

text:
# Question
Title: Hofstadter H-sequence
# Definition

* \\$a(0) = 0\\$
* \\$a(n) = n-a(a(a(n-1)))\\$ for integer \\$n \> 0\\$

# Task

Given non-negative integer \\$n\\$, output \\$a(n)\\$.

# Testcases

```
n     a(n)
0     0
1     1
2     1
3     2
4     3
5     4
6     4
7     5
8     5
9     6
10    7
11    7
12    8
13    9
14    10
15    10
16    11
17    12
18    13
19    13
20    14
10000 6823

```

# References

# Answer
## Haskell, ~~23~~ 22 bytes

```
f 0=0
f n=n-f(f$f$n-1)

```

Simply uses the definition of the sequence. `f(f$f$n-1)` is equivalent to `f (f (f (n-1)))`.

Test:

```
main = putStrLn . show $ map f [0..20]
-- => [0,1,1,2,3,4,4,5,5,6,7,7,8,9,10,10,11,12,13,13,14]

```

Thanks to Anders Kaseorg for a byte!
> 20 votes

# Answer
# Jelly, 8 bytes

```
’ßßßạµṠ¡

```

Try it online! or verify the smaller test cases.

### How it works

```
’ßßßạµṠ¡  Main link. Argument: n

     µṠ¡  Execute the preceding chain sign(n) times.
’         Decrement n, yielding n - 1.
 ßßß      Recursively call the main link thrice.
    ạ     Take the absolute difference of n and the result.

```
> 9 votes

# Answer
# J, ~~14~~ 12 bytes

```
-$:^:3@<:^:*

```

Saved 2 bytes thanks to @Leaky Nun.

Computes the result by calling itself recursively when *n* \> 0 three times on *n*-1 and subtracting that result from *n*. There is a different situation for the base case when *n* = 0. There it computes *n*-*n* which equals 0.

```
a(n) = n - n = 0           if n = 0
       n - a(a(a(n-1)))    if n > 0

```

Try it here.

## Explanation

```
-$:^:3@<:^:*  Input: n
           *  Get the sign of n (n = 0 => 0, n > 0 => 1)
         ^:   Execute that many times
                (0 times means it will just be an identity function)
       <:       Decrement n
 $:             Call itself recursively
   ^:3          three times
      @         on n-1
-             Subtract that result from n and return

```
> 9 votes

# Answer
## Mathematica, 20 bytes

Byte count assumes ISO 8859-1 (or compatible) encoding and `$CharacterEncoding` set to a matching value, like the Windows default `WindowsANSI`.

```
±0=0
±n_:=n-±±±(n-1)

```

This defines a unary operator `±`.
> 9 votes

# Answer
# Julia, 16 bytes

```
!n=n>0&&n-!!!~-n

```

Try it online!

### How it works

We redefine the unary operator `!` for our purposes.

If **n = 0**, the comparison `n>0` returns *false* and so does `!`.

Otherwise, the code after `&&` gets executed. `~-n` is equivalent to `(n-1)` in two's complement, `!!!` recursively calls `!` thrice on **n - 1**, and the resulting value is subtracted from **n**.
> 6 votes

# Answer
# Python, 31 bytes

```
a=lambda n:n and n-a(a(a(n-1)))

```

Recursion limit and time constraints make above function impractical, but in theory it should work (and does work for small n).
> 5 votes

# Answer
## JavaScript (ES6), 52 bytes

```
n=>[0,...Array(n)].reduce((p,_,i,a)=>a[i]=i-a[a[p]])

```

I could have been boring and written the recursive version but this version is much faster (easily coping with the last test case) and also uses `reduce` so that's a plus!
> 4 votes

# Answer
## Retina, ~~49~~ 43 bytes

```
.+
$*1:
{`^1(1*):
$1:::-1$1
}`^:*(1*)-\1

1

```

Try it online!
> 4 votes

# Answer
## CJam, ~~13~~ 12 bytes

*Thanks to Dennis for saving 1 byte.*

```
ri0{_(jjj-}j

```

Test it here.
> 3 votes

# Answer
# R, ~~42~~ 41 bytes

```
a=function(n)ifelse(n<1,0,n-a(a(a(n-1))))

```

Usage:

```
> a(1)
1
> a(10)
7

```

This recursive approach doesn't scale well for larger values of `n` though.
> 3 votes

# Answer
# Oasis, 6 bytes

Code:

```
nbaa-0

```

Expanded version:

```
a(n) = nbaa-
a(0) = 0

```

Code:

```
n      # Push n
 b     # Calculate a(n - 1)
  a    # Calculate a(a(n - 1))
   a   # Calculate a(a(a(n - 1)))
    -  # Subtract a(a(a(n - 1))) from n

```

Try it online!
> 3 votes

# Answer
# APL (Dyalog Unicode), ~~18~~ 17 bytes

```
{⍵=0:0⋄⍵-∇⍣3⊢⍵-1}

```

Try it online!

Surprisingly, there's no APL answer to this challenge. This is a literal implementation of the function in the OP.

TIO times out for \\$n\>90\\$.

Saved a byte thanks to @Zacharý.
> 3 votes

# Answer
# Sesos, ~~58~~ 55 bytes

```
0000000: 16e0d7 bdcdf8 8cdf1b e6cfbb 840d3f bf659b 38e187  ..............?.e.8..
0000015: f8639b 39dc37 fc893f 666c05 7e7ed9 b88b3f ae0d3f  .c.9.7..?fl.~~...?..?
000002a: 676ed8 bd9940 7fdc3b 36619e f1                    gn...@..;6a..

```

Handles inputs up to **400** reasonably well, but run time increases dramatically after that point.

Try it online! Check *Debug* to see the generated SBIN code.

### Sesos assembly

The binary file above has been generated by assembling the following SASM code.

```
set numin, set numout

get
jmp
    jmp
        rwd 3, add 1, rwd 1, add 1, fwd 4, sub 1
    jnz
    rwd 3, sub 1
jnz
rwd 3, add 1, fwd 2
jmp
    rwd 1, sub 1, fwd 3, sub 1, fwd 2, add 3
    jmp
        rwd 2
        jmp
            rwd 3
        jnz
        fwd 6, get, rwd 4, sub 1
        jmp
            fwd 1, sub 1
            jmp
                rwd 3
            jnz
            sub 1
            jmp
                fwd 3
            jnz
            rwd 4, sub 1
        jnz
        fwd 1
        jmp
            rwd 1, add 1, fwd 1, add 1
        jnz
        sub 1, fwd 3, sub 1
        jmp
            fwd 3
        jnz
        rwd 1, sub 1
    jnz
    rwd 2, get
    nop
        rwd 3
    jnz
    fwd 3, get, rwd 2
    jmp
        fwd 2, add 1
        jmp
            fwd 3
        jnz
        rwd 1, add 1, rwd 2
        jmp
            rwd 3
        jnz
        fwd 1, sub 1
    jnz
    fwd 2
    jmp
        rwd 2, add 1, fwd 2, sub 1
    jnz
    nop
        get, fwd 3
    jnz
    rwd 1, add 1, fwd 2
jnz
rwd 2, sub 1
jmp
    rwd 1, sub 1, fwd 1, sub 1
jnz
rwd 1, put

```
> 2 votes

# Answer
# LISP, 61 bytes

```
(defun H(N)(if(= N 0)(return-from H 0)(- N(H(H(H(- N 1)))))))

```

Probably not the optimal solution, but it works.
> 2 votes

# Answer
# C, ~~35~~ 32 bytes

*Saved 3 bytes thanks to @PeterTaylor!*

```
a(n){return n?n-a(a(a(n-1))):0;}

```

Try it on Ideone!
> 1 votes

# Answer
# Java 7, 42 bytes

```
int c(int n){return n>0?n-c(c(c(n-1))):0;}

```

**Ungolfed & test cases:**

Try it here.

```
class Main{
  static int c(int n){
    return n > 0
              ? n - c(c(c(n-1)))
              : 0;
  }

  public static void main(String[] a){
    for(int i = 0; i < 21; i++){
      System.out.println(i + ": " + c(i));
    }
    System.out.println("1000: " + c(1000));
  }
}

```

**Output:**

```
0: 0
1: 1
2: 1
3: 2
4: 3
5: 4
6: 4
7: 5
8: 5
9: 6
10: 7
11: 7
12: 8
13: 9
14: 10
15: 10
16: 11
17: 12
18: 13
19: 13
20: 14
 (last case takes too long..)

```
> 1 votes

# Answer
# Ruby, 27 bytes

The obvious implementation.

```
a=->n{n<1?0:n-a[a[a[n-1]]]}

```

This is a longer, faster answer that caches previous entries in the sequence. Both answers only work for versions after 1.9, as that was when `->`, the stabby lambda, was introduced to Ruby.

```
->n{r=[0];i=0;(i+=1;r<<i-r[r[r[i-1]]])while i<n;r[n]}

```
> 1 votes

# Answer
## C#, 35 bytes

```
int a(int n)=>n>0?n-a(a(a(n-1))):0;

```
> 1 votes

# Answer
# Golfscript, ~~26~~ 25 bytes

```
~~~[0]{....,(===\.,@-+}@*)\;~~
~[0]{...)\;==\.,@-+}@*)\;

```

Try it online!

Locally `10000` takes less than half a second.
> 1 votes

# Answer
# Maple, ~~28~~ 26 bytes

```
`if`(n=0,0,n-a(a(a(n-1))))

```

Usage:

```
> a:=n->ifelse(n=0,0,n-a(a(a(n-1))));
> seq(a(i),i=0..10);
0, 1, 1, 2, 3, 4, 4, 5, 5, 6, 7

```
> 1 votes

# Answer
# Javascript ES6, 22 bytes

```
a=n=>n&&n-a(a(a(n-1)))

```

I'll be boring and do the recursive version :P
> 1 votes

# Answer
## VBA, 69 bytes

```
Function H(N):ReDim G(N):For j=1To N:G(j)=j-G(G(G(j-1))):Next:H=G(N)

```

Works in the blink of an eye on the test set, slows down a little above n=1000000, runs into a memory wall a little above n=25 million.
> 1 votes

# Answer
# Pyth, 10 bytes

```
L-WbbyFtb3

```

Defines a function `y`. Try it online: Demonstration

This uses a relative new feature of Pyth. You can apply a function multiple times using the fold-syntax. It doesn't actually save any bytes, I used it just for demonstration purposes.

### Explanation:

```
L-WbbyFtb3
L            define function y(b), that returns:
    b           b
 -Wb            and subtract the following if b>0
     yF  3      y applied three times to
       tb       b - 1

```
> 1 votes

# Answer
# dc, 34 bytes

```
dsn[zdddd1-;a;a;a-r:aln!=L]dsLx;ap

```

Input is taken from the top of the stack. This must be the only item on the stack, because the stack depth is used as a counter. Example of usage:

```
$ dc
10000dsn[zdddd1-;a;a;a-r:aln!=L]dsLx;ap

```

This is a fairly straightforward implementation of the sequence definition:

```
dsn               # Store n as `n', and keep a copy as a depth buffer (see below)
[                 # Open loop definition
 z                # Push stack depth i for i-th term
 dddd             # Duplicate stack depth four times, for a total of five copies
 1-               # Get i-1 for use as index to previous term
                  #   Note that if we hadn't duplicated n above, or left something else
                  #   on the stack, 0-1 would be -1, which is not a valid array index
 ;a;a;a           # Fetch a(a(a(i-1)))
 -                # Calculate i-a(a(a(i-1)))
 r                # Arrange stack to store i-th term: TOS |  i  (i-a(a(a(i-1))))
 :a               # Store i-th term in array `a'
 ln!=L            # Load n. If n!=i, we're not done calculating terms yet, so execute loop
]                 # Close loop definition. Note that we started with five copies of i:
                  #   i-1 was used to get last term
                  #   i-a(...) was used to calculate current term
                  #   ... i :a was used to store current term
                  #   i ln !=L was used to check loop exit condition
                  # One copy of i is left on the stack to increment counter
dsLx              # Duplicate loop macro, store it, and execute copy
;a                # Last i stored on stack from loop will equal n, so use this to get a(n)
p                 # Print a(n)

```

Anyways, it started out straightforward...then the golfing happened.
> 1 votes

# Answer
# Common Lisp, 44 bytes

```
(defun f(x)(if(= x 0)0(- x(f(f(f(1- x)))))))

```

Try it online!
> 1 votes

# Answer
## C++ ( MSVC, mainly ) <br>

### Normal version : 40 bytes

```
int a(int n){return n?n-a(a(a(n-1))):0;}

```

### Template meta programming version : 130 bytes

```
#define C {constexpr static int a(){return
template<int N>struct H C N-H<H<H<N-1>::a()>::a()>::a();}};template<>struct H<0>C 0;}};

```

Usage :

```
std::cout << a(20) << '\n';       // Normal version
std::cout << H<20>::a() << '\n';  // Template version

```

The template version is the fastest code, since there's nothing faster than moving a value into a register =\> with optimization, `H<20>::a()` compile as :

```
mov esi, 14

```

For 10000, the recursive version crashes due to a stack overflow error, and the template version crashes at compile time due to template instantiation depth. GCC goes to 900 ( 614 )
> 1 votes

# Answer
# Japt, 7 bytes

```
©aßßßUÉ

```

Try it or run all test cases (throws an overflow error for 10000)
> 1 votes

# Answer
# , 36 bytes

```
T a(T)(T n){return n?n---n.a.a.a:0;}

```

Try it online!
> 1 votes

# Answer
# Python 3, 72 bytes

```
def f(n):
    a=[0];i=0
    while n:i+=1;a+=[i-a[a[a[i-i]]]];n-=1
    return a[i]

```

Ideone it!
> 0 votes

# Answer
## PowerShell v2+, 56 bytes

```
$a={$n=$args[0];if($n){$n-(&$a(&$a(&$a($n-1))))}else{0}}

```

The PowerShell equivalent of a lambda to form the recursive definition. Execute it via the `&` call operator, e.g. `&$a(5)`. Takes a *long* time to execute -- even `50` on my machine (a recent i5 with 8GB RAM) takes around 90 seconds.

### Faster iterative solution, 59 bytes

```
param($n)$o=,0;1..$n|%{$o+=$_-$o[$o[$o[$_-1]]]};$o[-1]*!!$n

```

Longer only because we need to account for input `0` (that's the `*!!$n` at the end). Otherwise we just iteratively construct the array up to `$n`, adding a new element each time, and output the last one at the end `$o[-1]`. Super-speedy -- calculating `10000` on my machine takes about 5 seconds.
> 0 votes

# Answer
# \>\<\>, 55+2 = 57 bytes

```
^~n;
.~-]{:0$
v>1-}32[
v/  /:1-32[
>$:?/$~]{:0$.
/30@2[

```

The input is expected to be present on the stack at program start, so +2 bytes for the `-v` flag. Try it online!

This is hecka slow, as it uses recursion to calculate the result. Using TIO, `h(50)` takes over a minute. It returns the correct results \<= 30, so I'm confident it would work for `h(10000)`, I just haven't run it to find out!
> 0 votes

# Answer
# RETURN, 17 bytes

```
[$[$1-aaa-][]?]=a

```

`Try it here!`

Recursive operator that leaves result on the stack. Example usage:

```
[$[$1-aaa-][]?]=a 4a

```
> 0 votes

# Answer
# Python 2, ~~54~~ 53 bytes

```
a=r,=0,
exec'r=len(a)-a[a[r]];a+=r,;'*input()
print r

```

Not even close to the recursive solution, but at least it's fast.

Test it on Ideone.
> 0 votes

# Answer
# C#, 156 bytes

Mine is going to be a bit longer than the other C# answer, but my version can compute up to 10,000 (and higher) without a stack overflow, and can do all integers from 0 to 10,000 in a fraction of a second due to addition of a dictionary. Most of the answers here can take hours to do integers in the thousands, so my extra bytes also lead to massive speed increases.

# Golfed

```
Dictionary<int,int> l=new Dictionary<int,int>();int H(int n){int v;if(n==0)return 0;if(l.TryGetValue(n,out v)){}else{v=n-H(H(H(n-1)));l.Add(n,v);}return v;}

```

# Ungolfed (with test program)

```
using System;
using System.Collections.Generic;

namespace HH
{
    class Program
    {
        static Dictionary<int, int> l = new Dictionary<int, int>();

        static int H(int n)
        {
            int v;
            if (n == 0)
                return 0;
            if (l.TryGetValue(n, out v))
            { }
            else
            {
                v = n - H(H(H(n - 1)));
                l.Add(n, v);
            }
            return v;
        }

        static void Main(string[] args)
        {
            for(int i = 0; i <= 10000; i++)
                Console.WriteLine("{0}: {1}", i, H(i));
            Console.ReadLine();
        }
    }
}

```

Edit: The other C# answer can't compute H(10,000) without a stack overflow, mine can print all numbers from H(1) to H(1,000,000) in a few seconds. H(1,000,000) is 682,328 if anyone was wondering :P
> 0 votes

# Answer
## Clojure, ~~44~~ 42 bytes

```
(fn f[n](if(= 0 n)0(- n(f(f(f(dec n)))))))

```

So sad this is sorter than `(fn f[n](if(= 0 n)0(- n((comp f f f dec)n))))`.
> 0 votes

# Answer
# Pyth, 11 bytes

```
L?b-byyytb0

```

Try it online!

The program defines a lambda function.

The link adds `yQ` for I/O
> 0 votes

# Answer
# Brachylog, 11 bytes

```
0|-₁↰↰↰-↙?ȧ

```

Try it online!

10000 times out and I've not yet been able to verify it, nor do I expect to.

```
0|             The input and output are 0, or the input
  -₁           minus 1
    ↰          passed through this same predicate
     ↰         passed through this same predicate
      ↰        passed through this same predicate
       -↙?     minus the input
          ȧ    has an absolute value equal to the output.

```
> 0 votes

# Answer
# GolfScript, 21 bytes

```
~{.{.(a a a-}{}if}:a~

```

Try it online!

```
~                      # Parse input to a number
 {               }:a   # Assign this function to the variable a
  .                    # Copy the number
   {        }{}if      # If it is bigger than 0 execute the first block, if it is 0 execute the second
    .(                 # Copy the number and decrement
      a a a            # a(a(a( n-1 )))
           -           # Subtract from the original number
                    ~  # Execute a

```

If the number is 0 nothing happens because there is already a 0 on top of the stack and we use that as the answer.
> 0 votes

---
Tags: code-golf, sequence, number-theory, recursion
---


title: Display Peter's keyboard pattern

text:
# Question
Title: Display Peter's keyboard pattern
Assume an simple keyboard with this layout:

```
1 2 3 4 5 6 7 8 9 0
A B C D E F G H I J
K L M N O P Q R S T
U V W X Y Z . , ? !

```

Peter's keyboard pattern can be generated by starting at the top left of the keyboard, and displays the first three characters and a newline. It shifts over one character and displays the second, third, and fourth key. Once it reaches the end of a row it continues at the end of the next row and goes backwards, until it reaches the start of that row and then goes forward on the next row, and so on until it reaches the beginning of the last row.

This is Peter's keyboard pattern:

```
123
234
345
456
567
678
789
890
90J
0JI
JIH
IHG
HGF
GFE
FED
EDC
DCB
CBA
BAK
AKL
KLM
LMN
MNO
NOP
OPQ
PQR
QRS
RST
ST!
T!?
!?,
?,.
,.Z
.ZY
ZYX
YXW
XWV
WVU

```

Write a program which accepts no input and displays Peter's keyboard pattern. **The program must be smaller than 152 bytes**, i.e. the size of the string it outputs.

This is code golf, so the shortest solution wins.

# Answer
## Perl, 63 chars

```
say for"1234567890JIHGFEDCBAKLMNOPQRST!?,.ZYXWVU"=~/(?=(...))/g

```

This solution uses the `say` function (available since Perl 5.10.0 with the `-E` switch, or with `use 5.010`). Without it, the best I can do is 67 chars (and an extra newline at the end of the output):

```
print"1234567890JIHGFEDCBAKLMNOPQRST!?,.ZYXWVU"=~/(?=(...))/g,$,=$/

```

---

Earlier 65-char solution:

```
s//1234567890JIHGFEDCBAKLMNOPQRST!?,.ZYXWVU/;s!(?=(...))!say$1!eg

```

Replacing `say$1` with `print$1.$/` lets the code run on older perls, at the cost of 5 extra characters.
> 7 votes

# Answer
## J, 66 62 45 characters

Turns out I was being too clever by half.

```
3]\'1234567890JIHGFEDCBAKLMNOPQRST!?,.ZYXWVU'

```

is all I needed all along.

Previously:

```
_2}.|:>(];1&|.;2&|.)'1234567890JIHGFEDCBAKLMNOPQRST!?,.ZYXWVU'

```

and:

```
38 3$($:@}.,~3$])^:(3<#)'1234567890JIHGFEDCBAKLMNOPQRST!?,.ZYXWVU'

```
> 7 votes

# Answer
## APL, 43 characters

```
⍪3,/(1⌽⎕D),(⌽10↑⎕A),(10↑10⌽⎕A),'!?,.',6↑⌽⎕A

```

This works on Dyalog APL. I managed to save a couple characters by generating the output string (everything after ). I'll write up an explanation when I get some time!

Here's how the output looks:

```
      ⍪3,/(1⌽⎕D),(⌽10↑⎕A),(10↑10⌽⎕A),'!?,.',6↑⌽⎕A
 123
 234
 345
 456
 567
 678
 789
 890
 90J
 0JI
 JIH
 IHG
 HGF
 GFE
 FED
 EDC
 DCB
 CBA
 BAK
 AKL
 KLM
 LMN
 MNO
 NOP
 OPQ
 PQR
 QRS
 RST
 ST!
 T!?
 !?,
 ?,.
 ,.Z
 .ZY
 ZYX
 YXW
 XWV
 WVU

```

Explanation, from right to left:

* First, we construct the string seen in all of the other entries:
    + `6↑⌽⎕A`: `⎕A` gives us a string of the uppercase alphabet, from A to Z. We then reverse it () and take () the first 6 characters of it, giving us `'ZYXWVU'`. (In retrospect, this approach doesn't end up saving any characters, but I'll leave it because it fits in better.)
    + `'!?,.',`: We concatenate (`,`) the string `'!?,.'` with the previous result.
    + `(10↑10⌽⎕A),`: We take the first 10 characters (`10↑`) of the alphabet, which is first rotated ten times (`10⌽`), and concatenate this with the previous result. As an example of rotation, `5⌽'abcdef'` (the string `'abcdef'` rotated 5 times) gives us `'cdefab'`.
    + `(⌽10↑⎕A),`: Take the first 10 characters of the alphabet and reverse them, and concatenate this with the previous string.
    + `(1⌽⎕D),`: `⎕D` gives us the digits as a string, from 0 to 9, inclusive. We then rotate ('⌽') this string by 1, yielding `'1234567890'`. As before, we concatenate this with the previous result.
* Now that we have our string built (which saved us 3 characters from the APL representation, due to surrounding quotes), we do some magic to build our final output:
    + `3,/`: We take the string, in groups of three characters, and concatenate them.
    + To finish it off, we use  to ravel our vector of strings (really a vector of character vectors) along the first dimension. This has the effect of changing its shape from `38` to `38 1` (a 38x1 matrix).
> 6 votes

# Answer
**R (75 characters)**

```
embed(strsplit("1234567890JIHGFEDCBAKLMNOPQRST!?,.ZYXWVU","")[[1]],3)[,3:1]

```

What does this do?

* `strsplit` splits a string into substrings, in this case individual characters
* `embed` is a really useful function that turns a vector into an array of overlapping elements
* The rest is just indexing and sorting columns in the right order.

This produces and prints an array of characters:

```
> embed(strsplit("1234567890JIHGFEDCBAKLMNOPQRST!?,.ZYXWVU","")[[1]],3)[,3:1]
      [,1] [,2] [,3]
 [1,] "1"  "2"  "3"
 [2,] "2"  "3"  "4"
 [3,] "3"  "4"  "5"
 [4,] "4"  "5"  "6"
 [5,] "5"  "6"  "7"
 [6,] "6"  "7"  "8"
 [7,] "7"  "8"  "9"
 [8,] "8"  "9"  "0"
 [9,] "9"  "0"  "J"
[10,] "0"  "J"  "I"
[11,] "J"  "I"  "H"
[12,] "I"  "H"  "G"
[13,] "H"  "G"  "F"
[14,] "G"  "F"  "E"
[15,] "F"  "E"  "D"
[16,] "E"  "D"  "C"
[17,] "D"  "C"  "B"
[18,] "C"  "B"  "A"
[19,] "B"  "A"  "K"
[20,] "A"  "K"  "L"
[21,] "K"  "L"  "M"
[22,] "L"  "M"  "N"
[23,] "M"  "N"  "O"
[24,] "N"  "O"  "P"
[25,] "O"  "P"  "Q"
[26,] "P"  "Q"  "R"
[27,] "Q"  "R"  "S"
[28,] "R"  "S"  "T"
[29,] "S"  "T"  "!"
[30,] "T"  "!"  "?"
[31,] "!"  "?"  ","
[32,] "?"  ","  "."
[33,] ","  "."  "Z"
[34,] "."  "Z"  "Y"
[35,] "Z"  "Y"  "X"
[36,] "Y"  "X"  "W"
[37,] "X"  "W"  "V"
[38,] "W"  "V"  "U"

```
> 4 votes

# Answer
### Scala 70 chars:

```
"1234567890JIHGFEDCBAKLMNOPQRST!?,.ZYXWVU".sliding(3,1).mkString("\n")

```
> 4 votes

# Answer
## Mathematica, 73

I independently arrived at the same method as everyone else:

```
Grid@Partition[Characters@"1234567890JIHGFEDCBAKLMNOPQRST!?,.ZYXWVU",3,1]

```
> 2 votes

# Answer
# C, 98 104 characters

Since no one else has done so yet, I thought I would try actually generating the string on the fly, using some kind of run-length encoding for ascending and descending runs.

EDIT: After a number of iterations, here's finally a "clever" solution that ties with the shortest "dumb" solution in C at 98 characters:

```
char*s="0º.ÿK»Jº ü=ÿ*ø[×",a[99],*p=a,i;main(j){for(;i-=i<8?j=*s++,*s++:8;puts(p++))p[2]=j+=i%4-1;}

```

The code requires an 8-bit Latin-1 encoding (ISO-8859-1 or Windows-1252), which should work fine on all commonly used platforms, but saving the source with some less popular 8-bit code page, or UTF-8 will not work.

The data string was created by the following piece of emacs lisp:

```
(require 'cl)
(apply 'concat
  (let ((last-remainder 0))
    (loop for (begin count step twiddle)
          in '((?1 9 +1 4) (?0 1 +2 4) (?J 10 -1 4) (?K 10 +1 0)
               (?! 1 +1 4) (?? 1 +2 4) (?, 2 +2 4) (?Z 6 -1 8))
          append (prog1 (list (char-to-string (- begin step))
                              (char-to-string
                               (logand 255 (- last-remainder
                                              (+ (* 8 (- count 1)) (+ step 1)
                                                 twiddle)))))
                   (setq last-remainder (+ (logand twiddle 7) step 1))))))

```

The "twiddle" bit is used to avoid unprintable ASCII control characters in the encoded data string, and to ensure that `i==0` only at the end of the output.

## C, 98 characters

However, even in C you can get a short program by simply printing consecutive triplets from the original string:

```
main(){char s[]="12,34567890JIHGFEDCBAKLMNOPQRST!?,.ZYXWVU",*p=s+2;for(;*p=p[1];puts(p-3))*++p=0;}

```
> 2 votes

# Answer
# Groovy, 73

```
(0..37).each{println"1234567890JIHGFEDCBAKLMNOPQRST!?,.ZYXWVU"[it..it+2]}

```

All the clever stuff I tried turned out to be longer than doing it the dumb way.
> 2 votes

# Answer
## Python, 73

```
for i in range(38):print"1234567890JIHGFEDCBAKLMNOPQRST!?,.ZYXWVU"[i:i+3]

```
> 2 votes

# Answer
## Ruby ~~69~~ ~~65~~ 62

Based on Groovy example

```
38.times{|i|p"1234567890JIHGFEDCBAKLMNOPQRST!?,.ZYXWVU"[i,2]}

```
> 2 votes

# Answer
## Haskell, 80

```
mapM_(putStrLn.take 3.(`drop`"1234567890JIHGFEDCBAKLMNOPQRST!?,.ZYXWVU"))[0..37]

```
> 2 votes

# Answer
# Kotlin, ~~140~~ 71 bytes

```
"1234567890JIHGFEDCBAKLMNOPQRST!?,.ZYXWVU".windowed(3).map{println(it)}

```

Try it online!

I just realized it's easier to use the string itself instead of generating it using ranges.
> 2 votes

# Answer
**Javascript, 103**

```
for(a='1234567890JIHGFEDCBAKLMNOPQRST!?,.ZYXWVU';a.length>2;a=a.substring(1))console.log(a.substr(0,3))

```
> 1 votes

# Answer
# Haskell, 94

```
main=putStr.unlines.take 38$take 3`map`iterate tail"1234567890JIHGFEDCBAKLMNOPQRST!?,.ZYXWVU"

```
> 1 votes

# Answer
# Perl, 73 characters:

```
print substr('1234567890JIHGFEDCBAKLMNOPQRST!?,.ZYXWVU',$_,3),$/for 0..37

```

# Perl, 66 characters:

```
say substr"1234567890JIHGFEDCBAKLMNOPQRST!?,.ZYXWVU",$_,3for 0..37

```

when called by:

```
perl -E 'say substr"1234567890JIHGFEDCBAKLMNOPQRST!?,.ZYXWVU",$_,3for 0..37'

```
> 1 votes

# Answer
## D 124 chars

```
import std.stdio;void main(){enum s="1234567890JIHGFEDCBAKLMNOPQRST!?,.ZYXWVU";
foreach(i;3..s.length){writeln(s[i-3..i)]);}}

```
> 1 votes

# Answer
### JavaScript, 83 chars

```
for(i=0;i<38;)console.log('1234567890JIHGFEDCBAKLMNOPQRST!?,.ZYXWVU'.substr(i++,3))

```

Decided to see if I could beat stephencarmody's solution. This is what I came up with.
> 1 votes

# Answer
## Smalltalk ~~102~~ 99

```
1to:38 do:[:i|x:='1234567890JIHGFEDCBAKLMNOPQRST!?,.ZYXWVU'copyFrom:i to:i+2.Transcript cr show:x]

```

I don't know Smalltalk very well so it's a little bit strange to me. It's compiles with `gst` others are not tested.
> 1 votes

# Answer
# Q (66 63 chars)

```
(((!)38),'3)sublist\:"1234567890JIHGFEDCBAKLMNOPQRST!?,.ZYXWVU"

```
> 1 votes

# Answer
## Prolog, 131

This is probably why you never see Prolog entries. The newline is required (actually, any whitespace will do but there has to be whitespace).

```
z(S,L):-append(_,X,L),append(S,_,X),length(S,3).
:-forall(z(X,"1234567890JIHFEDCBAKLMNOPQRST!?,.ZYXWVU"),writef("%s\n",[X])),halt.

```
> 1 votes

# Answer
# ///, 151 bytes

```
123
234
345
456
567
678
789
890
90J
0JI
JIH
IHG
HGF
GFE
FED
EDC
DCB
CBA
BAK
AKL
KLM
LMN
MNO
NOP
OPQ
PQR
QRS
RST
ST!
T!?
!?,
?,.
,.Z
.ZY
ZYX
YXW
XWV
WVU

```

Try it online!

Can't golf it more? This is, in a sense, \<152 bytes.
> 1 votes

# Answer
# Jelly, ~~41~~ 40 bytes

```
ØAḣ⁵Ṛ
ØDṫ2;0;¢;“KLMNOPQRST!?,.ZYXWVU”ṡ3Y

```

Try it online!

Might (still) be golfable...
> 1 votes

# Answer
# Jelly, ~~24~~ 23 bytes

```
ØDṙ1;ØA;“.,?!”s⁵UÐeFṡ3Y

```

Try it online!

Generates the keyboard top to bottom left to right, then boustrophedonizes it afterwards.

```
ØD                         "0123456789"
  ṙ1                       rotated once to the left
    ;                      concatenated with
     ØA                    the uppercase alphabet
       ;“.,?!”             concatenated with ".,?!".
              s            Chop it into slices of length
               ⁵           10,
                U          (vectorized) reverse
                 Ðe        the slices at even 1-indices,
                   F       smash the slices back together,
                    ṡ3     take every contiguous sublist of length 3,
                      Y    and join on newlines.

```
> 1 votes

# Answer
# Brachylog, 26 bytes

```
Ị↺,Ạ,".,?!"ụḍ₄{i↔ⁱ⁾}ᶠcs₃ẉ⊥

```

Try it online!

Essentially a translation of my Jelly answer. A full program which prints the desired output with a trailing newline.

```
Ị                             "0123456789"
 ↺                            rotated once to the left
  ,                           concatenated with
   Ạ                          the alphabet (lowercase)
    ,".,?!"                   concatenated with ".,?!",
           ụ                  uppercased,
            ḍ₄                sliced into quarters.
                     c        Concatenate
              {    }ᶠ         every possible result from
               i              taking a slice with its 0-index
                ↔             and reversing it
                 ⁱ⁾           a number of times equal to the index.
                        ẉ     Print with a newline
                      s₃      a substring of length 3 from the concatenation,
                         ⊥    then try again with a different substring.

```

If a trailing newline is unacceptable:

# Brachylog, 27 bytes

```
Ị↺,Ạ,".,?!"ụḍ₄{i↔ⁱ⁾}ᶠcs₃ᶠ~ṇ

```

Try it online!

Outputs as a function.
> 1 votes

# Answer
# 05AB1E, 24 bytes

```
žhÀAu".,?!"«Tô2Å€R}J«ü3»

```

Try it online.

Minor alternative:

```
Au".,?!"«TôžhÀšεNFR]Jü3»

```

Try it online.

**Explanation:**

```
žh                       # Push builtin "0123456789"
  À                      # Rotate it once to the left: "1234567890"
   Au                    # Push the uppercase alphabet
     ".,?!"«             # Append ".,?!" to it
            Tô           # Split it into parts of size 10:
                         #  ["ABCDEFGHIJ","KLMNOPQRST","UVWXYZ.,?!"]
              2Å€ }      # For every 2nd item (0-based index modulo 2 == 0):
                 R       #  Reverse it
                         #   ["JIHGFEDCBA","KLMNOPQRST","!?,.ZYXWVU"]
                   J     # Join the list together to a single string again:
                         #  "JIHGFEDCBAKLMNOPQRST!?,.ZYXWVU"
                    «    # Merge it to the digits:
                         #  "1234567890JIHGFEDCBAKLMNOPQRST!?,.ZYXWVU"
                     ü3  # Create overlapping triplets
                       » # Join the list by newlines
                         # (after which it is output implicitly with trailing newline)

Au".,?!"«Tô              # Same as above: ["ABCDEFGHIJ","KLMNOPQRST","UVWXYZ.,?!"]
           žhÀ           # Same as above: "1234567890"
              š          # Prepend it to the list:
                         #  ["1234567890","ABCDEFGHIJ","KLMNOPQRST","UVWXYZ.,?!"]
               ε         # Map each string to:
                NF       #  Loop the 0-based map-index amount of times:
                  R      #   Reverse the string every iteration
                   ]     # Close both the loop and map
                    J    # Join the list together to a single string again:
                         #  "1234567890JIHGFEDCBAKLMNOPQRST!?,.ZYXWVU"
                     ü3» # Same as above
                         # (after which it is output implicitly with trailing newline)

```
> 1 votes

# Answer
## Q, 63

```
{(x;3)sublist"1234567890JIHGFEDCBAKLMNOPQRST!?,.ZYXWVU"}'[(!)38]

```
> 0 votes

# Answer
# x86-16 machine code, PC DOS, 64 bytes

Binary:

```
00000000: b409 bb1b 01ba 1801 bf0a 24b1 2687 3fcd  ..........$.&.?.
00000010: 2187 3f42 43e2 f6c3 3132 3334 3536 3738  !.?BC...12345678
00000020: 3930 4a49 4847 4645 4443 4241 4b4c 4d4e  90JIHGFEDCBAKLMN
00000030: 4f50 5152 5354 213f 2c2e 5a59 5857 5655  OPQRST!?,.ZYXWVU

```

Listing:

```
BB 011B     MOV  BX, OFFSET KB+3        ; pointer to end of 3 char substring
BA 0118     MOV  DX, OFFSET KB          ; pointer to beginning of 3 char substring
BF 240A     MOV  DI, 240AH              ; string '$' + 0AH
B1 26       MOV  CL, 38                 ; number of lines
B4 09       MOV  AH, 9                  ; DOS API output string function
        CLOOP:
87 3F       XCHG DI, WORD PTR[BX]       ; swap string term and LF char after 3 chars
CD 21       INT  21H                    ; write substring to console
87 3F       XCHG DI, WORD PTR[BX]       ; swap back
42          INC  DX                     ; increment string start pointer
43          INC  BX                     ; increment string end pointer
E2 F6       LOOP CLOOP                  ; loop until 38 lines
C3          RET                         ; return to DOS
        KB:
            DB  '1234567890JIHGFEDCBAKLMNOPQRST!?,.ZYXWVU'

```

It's a bit of a naïve approach, but still fits well below the spec size (and is a nice power of 2). Loops through the string and swaps the relative 4th and 5th character with a LF followed by a string terminator and then outputs it.

Standalone DOS executable COM program. Output:

Head:

Tail:
> 0 votes

# Answer
# Japt `-R`, 27 bytes

```
;9õ pUB".,?!" ¬ò10 ËzEÑÃ¬ã3

```

Test it

```
;9õ pUB".,?!" ¬ò10 ËzEÑÃ¬ã3
 9õ                             :Range [1,9]
    p                           :Push
     U                          :  0
;     B                         :  Uppercase alphabet
       ".,?!"                   :  String literal
              ¬                 :Join
               ò10              :Partitions of length 10
                   Ë            :Map each string a 0-based index E
                    z           :  Rotate clockwise 90 degrees
                     EÑ         :  E*2 times
                       Ã        :End map
                        ¬       :Join
                         ã3     :Substrings of length 3
                                :Implicit output, joined with newlines

```
> 0 votes

# Answer
# PowerShell 6+, 62 bytes

```
0..37|%{'1234567890JIHGFEDCBAKLMNOPQRST!?,.ZYXWVU'|% s*g $_ 3}

```

Try it online!

where `s*g` is the shorcut for the `Substring` method.
> 0 votes

---
Tags: code-golf, kolmogorov-complexity
---


title: Number Spiral Problem

text:
# Question
Title: Number Spiral Problem
A number spiral is an infinite grid whose upper-left square has number 1. Here are the first five layers of the spiral:

**Your task is to find out the number in row y and column x.**

---

Example:

```
Input: 2 3
Out  : 8
Input: 1 1
Out  : 1
Input: 4 2
Out  : 15

```

---

Note:

1. Any programming language is allowed.
2. This is a challenge so shortest code wins.
3. Best of Luck!

Source: https://cses.fi/problemset/task/1071

# Answer
# Japt, ~~16~~ ~~14~~ 10 bytes

(Originally) Adapted from Doorknob's solution over a few beers.

```
wV
nU²ÒNra

```

Try it

```
wV\nnU²ÒNra     :Implicit input of integers N=[U=y, V=X]
wV              :Maximum of U & V
  \n            :Reassign to U, leaving the value in N unchanged
    n           :Subtract U from
     U²         :  U squared
       Ò        :  Subtract the bitwise NOT of
        Nr      :  N reduced by
          a     :    Absolute difference

```
> 6 votes

# Answer
## C (gcc),  ~~44~~  43 bytes

```
f(x,y,z){z=x>y?x:y;z=z*z-~(z%2?y-x:x-y)-z;}

```

Try it online!

The spiral has several "arms":

```
12345
22345
33345
44445
55555

```

The position \\$(x, y)\\$ is located on arm \\$\max(x, y)\\$ (assigned to variable `z`). Then, the largest number on arm \\$n\\$ is \\$n^2\\$, which alternates between being in the bottom left and top right position on the arm. Subtracting \\$x\\$ from \\$y\\$ gives the sequence \\$-n+1, -n+2, \ldots, -1, 0, 1, \ldots, n-1, n-2\\$ moving along arm \\$n\\$, so we choose the appropriate sign based on the parity of \\$n\\$, adjust by \\$n-1\\$ to get a sequence starting at 0, and subtract this value from \\$n^2\\$.

Thanks to Mr. Xcoder for saving a byte.
> 20 votes

# Answer
## Python,  ~~54~~   ~~50~~  49 bytes

```
def f(a,b):M=max(a,b);return(a-b)*(-1)**M+M*M-M+1

```

-4 bytes thanks to @ChasBrown

-1 bytes thanks to @Shaggy

Try it Online!

First time golfing! I'm more than aware this is not optimal, but whatever.

Essentially runs on the same principle as @Doorknob C code.
> 7 votes

# Answer
# MATL, 15 bytes

```
X>ttq*QwoEqGd*+

```

Try it online!
Collect and print as a matrix

### How?

*Edit: Same technique as @Doorknob's answer, just arrived at differently.*

The difference between the diagonal elements of the spiral is the arithmetic sequence \\$ 0, 2, 4, 6, 8, \ldots \\$. Sum of \\$ n \\$ terms of this is \\$ n(n - 1) \\$ (by the usual AP formula). This sum, incremented by 1, gives the diagonal element at position \\$ (n, n) \\$.

Given \\$ (x, y) \\$, we find the maximum of these two, which is the "layer" of the spiral that this point belongs to. Then, we find the diagonal value of that layer as \\$ v = n(n-1) + 1 \\$. For even layers, the value at \\$ (x, y) \\$ is then \\$ v + x - y \\$, for odd layers \\$ v - x + y \\$.

```
X>        % Get the maximum of the input coordinates, say n
ttq*      % Duplicate that and multiply by n-1
Q         % Add 1 to that. This is the diagonal value v at layer n
wo        % Bring the original n on top and check if it's odd (1 or 0)
Eq        % Change 1 or 0 to 1 or -1
Gd        % Push input (x, y) again, get y - x
*         % Multiply by 1 or -1
          % For odd layers, no change. For even layers, y-x becomes x-y
+         % Add that to the diagonal value v
          % Implicit output

```

---

**Alternate 21 byte solution:**

```
Pdt|Gs+ttqq*4/QJb^b*+

```

Try it online!
Collect and print as a matrix
From the above, we know that the function we want is

$$ f = m * (m - 1) + 1 + (-1)^m * (x - y) $$

where \\$ m = max(x, y) \\$.

Some basic calculation will show that one expression for max of two numbers is

$$ m = max(x, y) = \frac{x + y + abs(x - y)}{2} $$

Plugging one into another, we find that one alternate form for \\$ f \\$ is:

$$ f = (x-y)\cdot i^{k} + \frac{1}{4}((k-2)\cdot k) + 1 $$

where \\$ k = abs(x-y) + x + y \\$.

This is the function the solution implements.
> 7 votes

# Answer
# Pyth, 20 bytes

```
A~Qh.MZQh-+*-GH^_1Q*

```

Test suite

An almost literal translation of Rushabh Mehta's answer.

Explanation:
```
A~Qh.MZQh-+*-GH^_1Q*    | Full code
A~Qh.MZQh-+*-GH^_1Q*QQQ | Code with implicit variables filled
                        | Assign Q as the evaluated input (implicit)
A                       | Assign [G,H] as
 ~Q                     |  Q, then assign Q as
   h.MZQ                |   Q's maximal value.
                        | Print (implicit)
        h-+*-GH^_1Q*QQQ |  (G-H)*(-1)^Q+Q*Q-Q+1

```
> 3 votes

# Answer
# Jelly, 13 bytes

```
»Ḃ-*×_‘+»×’$¥

```

Try it online!

Uses Doorknob's method. Way too long.
> 2 votes

# Answer
# Jelly, ~~13~~ 12 bytes

```
ṀḂḤ’×I+²_’ṀƲ

```

Try it online!

Computes the diagonal term with `²_’Ṁ` and adds/subtracts to the correct index value with `ṀḂḤ’×I`.
> 2 votes

# Answer
# Brain-Flak, 76 bytes

```
((({}<>))<>[(({}))]<{({}[()])<>}>)<>{}((){({}[()])({})<><([{}])><>}{}<>{}<>)

```

Try it online!
> 2 votes

# Answer
# 05AB1E, ~~12~~ 11 bytes

```
ZÐ<*>ŠGR}¥+

```

-1 byte thanks to *@Emigna* changing `Èi` to `G`.

Port of *@sundar*'s MATL answer, so make sure to upvote him!

Try it online or verify all test cases.

**Explanation:**

```
Z              # Get the maximum of the (implicit) input-coordinate
               #  i.e. [4,5] → 5
 Ð             # Triplicate this maximum
  <            # Decrease it by 1
               #  i.e. 5 - 1 → 4
   *           # Multiply it
               #  i.e. 5 * 4 → 20
    >          # Increase it by 1
               #  i.e. 20 + 1 → 21
     Š         # Triple swap the top threes values on the stack (a,b,c to c,a,b)
               #  i.e. [4,5], 5, 21 → 21, [4,5], 5
      G }      # Loop n amount of times
       R       #  Reverse the input-coordinate each iteration
               #   i.e. 5 and [4,5] → [5,4]→[4,5]→[5,4]→[4,5] → [5,4]
         ¥     # Calculate the delta of the coordinate
               #  [5,4] → [1]
          +    # And add it to the earlier calculate value (output the result implicitly)
               #  21 + [1] → [22]

```
> 2 votes

# Answer
# Pascal (FPC), 90 bytes

```
uses math;var x,y,z:word;begin read(x,y);z:=max(x,y);write(z*z-z+1+(1and z*2-1)*(y-x))end.

```

Try it online!

Port of Doorknob's answer, but sundar's answer gave me idea for `z mod 2*2-1` which I transformed into `1and z*2-1` to remove space.
> 0 votes

# Answer
# Mathematica 34 bytes

```
x = {5, 8};

```

so:

```
m = Max[x];
Subtract @@ x (-1)^m + m^2 - m + 1

```

(\*

54

\*)
> 0 votes

# Answer
# Julia 1.0, 35 bytes

```
x\y=(m=max(x,y))*~-m+1+(-1)^m*(x-y)

```

Try it online!
> 0 votes

# Answer
# JavaScript (ES6), 46 bytes

```
f=(r,c,x)=>r<c?f(c,r,1):r%2-!x?r*r-c+1:--r*r+c

```
> 0 votes

# Answer
# Java (JDK 10), 39 bytes

```
x->y->(y-x)*((y=x>y?x:y)%2*2-1)+y*y-y+1

```

Try it online!

## Credits
> 0 votes

# Answer
# Rockstar, ~~127~~ ~~118~~ 115 bytes

Also adapted from Doorknob's solution.

```
listen to Y
listen to X
let M be Y is less than X and X-0 or Y-0
let R be M*M-M
let R be-M-Y and Y-X or X-Y
say R+1

```

Try it here (Code will need to be pasted in, with each input integer on an individual line)
> 0 votes

---
Tags: code-golf, math
---