# Question
Title: Encoder/Decoder for efficient number storage!
**Description**

Inspired by this question, write a program/function to encode a number and a program (possibly the same as the first) to decode a bitstream in variable-length encoding as follows (taken from that question's answer, slightly modified):

> Represent the string x using the following encoding:
>
> $$0, x\_k, \dots, 0, x\_2, 0, x\_1, 1, x\_0$$
>
> where \\$x\_0\\$ is just \\$x\\$, then \\$x\_{i+1} = \mathrm{len}(x\_i)\\$ is a binary representation of the length of \\$x\_i\\$ in bits (namely, \\$\mathrm{len}(x\_i)=\mathrm{ceil}(\log\_2 x\_i)\\$, for \\$i \ge 1\\$), and \\$k\\$ is the smallest \\$k \ge 1\\$ such that \\$x\_k \le 3\\$.
> In particular, you always encode \\$x\_k\\$ with 2 bits, and encode \\$x\_i\\$ with \\$x\_{i+1}\\$ bits.

Some example encodings:

| Decimal | Encoded |
| --- | --- |
| 0 | 00110 |
| 1 | 00111 |
| 2 | 010110 |
| 3 | 010111 |
| 4 | 0111100 |
| 8 | 011010011000 |
| 127 | 011011111111111 |

Note that based on this encoding, the first bit is always 0, and the next 2 bits afterwards always encode the length of the next part.

**Input/Output**

For the encoder, it will take as input a list of non-negative integers, which may be empty (in any list representation you like), and output the string as per the encoding above. When encoding multiple numbers, simply concatenate the encoding. If the input is an empty list, output empty string.

For the decoder, it will take as input a (possibly invalid encoding, but always consists only of 0 and 1) bit string, and output a list of integers it encodes (in the same representation as the input to your encoder). If the string is an invalid encoding, you can output anything that cannot be misconstrued as a valid list of integers. For example, you can just output "INVALID" as the whole output, or you output "X" after outputting partially decoded list of integers (e.g., when the first part of the string is valid, but the later one isn't). As long as your invalid output cannot be read as a list of integers as a whole (in the same representation you use for the encoder input), it's fine. This includes terminating with an exception or a non-zero exit code (since it's also not a valid input to the encoder).

**Scoring**

This is code golf, the score of an answer is the sum of the number of bytes in both programs. If your program can do both in the same program, the length of that program is the score. Lowest score wins. Standard code golf rules apply.

**Test Cases**

Some test cases (input, then output on the next line, separated by a blank line):

**Encoder**

```
2
010110

1 5 3
001110111101010111

0 0 1
001100011000111

8 127 512 987654321
0110100110000110111111111110110100010101100000000001101010111101111010110111100110100010110001

```

The last test case is an empty list as input, and empty string as output

**Decoder**

```
010110
2

001110111101010111
1 5 3

001100011000111
0 0 1

00111011110010111
Invalid (a new number starts with 1)

1
Invalid (a new number starts with 1)

0011000110001
Invalid (not complete)

001100011001101001100
Invalid (not complete)

0011000110011010
Invalid (not complete)

0110100110000110111111111110110100010101100000000001101010111101111010110111100110100010110001
8 127 512 987654321

```

The last test case is an empty string, outputting empty list (which is empty string in this case, but it depends on your list representation)

# Answer
# Charcoal, 115 bytes

## Encoder, 43 bytes

```
ＦＥＡ⟦ι⟧«Ｗ∨⁼¹Ｌι‹³⌊ι⊞ιＬ⍘⌊ι²⪫⮌Ｅι⁺¬λ⁺…0∧λ‹κ²⍘κ²ω

```

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

```
ＦＥＡ⟦ι⟧«

```

Loop over the input list, but wrap each number in its own list.

```
Ｗ∨⁼¹Ｌι‹³⌊ι

```

Repeat until the list has at least two elements and the smallest element is no more than `3`.

```
⊞ιＬ⍘⌊ι²

```

Push the length in binary of the smallest element to the list.

```
⪫⮌Ｅι⁺¬λ⁺…0∧λ‹κ²⍘κ²ω

```

Output the elements in binary in ascending order prefixing the last one with `1` and the rest with `0` or `00` if it is less than `2`.

## Decoder, 72 bytes

```
Ｗ∧θ⁼§θ⁰0«≔²ηＷ∧∧‹ηＬθ⁼§θ⁰0θ«≔Φκ›μηθ≔⍘…κ⊕η²η»¿‹ηＬθ«⟦Ｉ⍘…Φθλη²⟧≔Φθ›ληθ»≔1θ»Ｌθ

```

Try it online! Link is to verbose version of code. Will output at least one `-` at some point if the string is invalid. Explanation:

```
Ｗ∧θ⁼§θ⁰0«

```

Repeat until the string has been processed.

```
≔²η

```

The first block is of length `2`.

```
Ｗ∧∧‹ηＬθ⁼§θ⁰0θ«

```

Repeat while there's a valid bit block starting with `0`...

```
≔Φκ›μηθ

```

... cut the string after the block, and...

```
≔⍘…κ⊕η²η

```

convert the block from binary to give the length of the next block.

```
»¿‹ηＬθ«

```

If there's still a valid bit block, then...

```
⟦Ｉ⍘…Φθλη²⟧

```

... output its value on its own line, and...

```
≔Φθ›ληθ

```

... cut the string after the block.

```
»≔1θ

```

Otherwise set the string to an invalid value.

```
»Ｌθ

```

Output at least one `-` if the string was invalid.
> 1 votes

# Answer
# JavaScript (ES6), 170 bytes

## Encoder, 85 bytes

```
a=>a.map(g=(n,_,i,b=n.toString(2))=>(i=+!!i)|n>3?g(b.length)+i+b:i+=n<2?0+b:b).join``

```

Try it online!

### Commented

```
a =>                // a[] = input array
a.map(g = (         // g is a recursive callback function taking:
  n,                //   n = current integer
  _,                //   the index is ignored
  i,                //   the reference to the array is used as a flag
                    //   (either defined or undefined)
  b = n.toString(2) //   b = binary representation of n
) =>                //
  (i = +!!i) |      //   turn i into either 0 or 1
  n > 3 ?           //   if i = 1 or n is greater than 3:
    g(b.length) +   //     do a recursive call with the length of b
    i + b           //     append i, followed by b
  :                 //   else:
    i +=            //     append i, followed by:
      n < 2 ?       //       if n is less than 2:
        0 + b       //         a leading '0' and b
      :             //       else:
        b           //         just b
).join``            // end of map(); join everything

```

## Decoder, 85 bytes

Throws an error if the input is invalid.

```
f=(s,n=3,S=s.slice(n))=>s?(k='0b'+s.slice(1,n))[n]?s>k?[+k,...f(S)]:f(S,-~k):_:n-3||s

```

Try it online!

### Commented

```
f = (             // f is a recursive function taking:
  s,              //   s = input string
  n = 3,          //   n = length of current bit block
  S = s.slice(n)  //   S = remaining string after the current block
) =>              //
s ?               // if s is not empty:
  ( k =           //   define k as:
    '0b' +        //     the binary prefix followed by
    s.slice(1, n) //     the current bit block without the leading digit
  )[n] ?          //   if k is as long as expected:
    s > k ?       //     if the leading digit is '1':
      [ +k,       //       append k, coerced to an integer
       ...f(S) ]  //       followed by the result of a recursive call with S
    :             //     else:
      f(S, -~k)   //       do a recursive call with S and n = k + 1
  :               //   else:
    _             //     force an error (undefined variable)
:                 // else:
  n - 3 ||        //   force an error if n is not equal to 3
  []              //   otherwise, stop the recursion properly

```
> 3 votes

# Answer
# Python3, 300 bytes

## Encoder, 142 bytes

```
def e(x,l='1'):return''.join(e(s)for s in x)if type(x)is list else '0'+f"{x>>1}{x&1}"if x<4 and l=='0'else e(len(bin(x)[2:]),'0')+l+bin(x)[2:]

```

Try it online!

## Decoder 158 bytes

```
def d(s,l=2,t=0):return''if s==''and t==0else d(s[1+l:],int(s[1:1+l],2),1)if s[0]=='0'else str(int(s[1:1+l],2))+' '+d(s[1+l:],2,0)if s[0]=='1'and t==1else 1/0

```

Try it online!
> 2 votes

# Answer
# Python 3, 117+154 = 271 bytes

Represents a list as space-separated integers.

Each is a full program, taking input from stdin, outputting to stdout.

## Encoder, 117 bytes

```
f=lambda n,s=1:f'{f(len(f"{n:b}"),0)if n>3or s else""}{s}{n:0{2-s}b}'
print(''.join(map(f,map(int,input().split()))))

```

Try it online!

Prints each encoding backward, from the number itself, then consecutively prints the length of the previous number in binary, separated by the right separator. The parameter `s` represent the separator to be output. Recurse when length is still more than 3, or it is the original number (`s=1`).

## Decoder, 154 bytes

```
s=input()
r=[]
def f(i,l,z):
 if len(s)==i:return 1/z
 p=int(s[i]);m=int(s[i+1:i+1+l],2)//(1-z*p);p and r.append(m);f(i+1+l,[m,2][p],p)
f(0,2,1)
print(*r)

```

Try it online!

Interpret the length of the next binary number repetitively, until separator `1` is found, which indicates the final number. Handles invalid encoding by raising `ZeroDivisionError` (if first bit in a number is not 0, or bitstream ended while original number is not yet found) or `ValueError` (trying to interpret empty string as number).

The tricky part is handling the invalid encoding.
> 1 votes

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


# Question
Title: Totally random Catan number distributions
I like to play (*The Settlers of*) *Catan* on Board Game Arena with totally random number tokens. These tokens determine the production rate of the terrain tiles beneath:

There are 18 number tokens, two each of 3, 4, 5, 6, 8, 9, 10, 11 and one each of 2 and 12. A valid arrangement of these tokens on the board (19 hexes in a side-3 hexagon) has each token placed in exactly one hex, leaving one empty hex (the desert), *and none of the 6 and 8 tokens adjacent*. So a 6 cannot be adjacent to the other 6, an 8 cannot be adjacent to the other 8 and a 6 cannot be adjacent to an 8.

## Task

Output a valid random arrangement of the number tokens. Each possible arrangement only needs a nonzero probability of being output.

You may output in any reasonable format, which may be 2D (like the valid and invalid outputs below) or 1D (e.g. mapping the hexes to a 19-character string in a fixed and consistent order). In either case it must be specified how the different positions in the output map to the hexagon. You may use any set of 11 different symbols to denote the number tokens or lack thereof.

This is ; fewest bytes wins.

## Valid outputs

These use `A B C` for `10 11 12` respectively and `.` for the empty desert hex.

```
  6 3 8
 2 4 5 A
5 9 . 6 9
 A B 3 C
  8 4 B

```

```
  B 9 A
 5 6 C 8
6 4 B 5 3
 2 8 9 3
  A . 4

```

```
  B B C
 3 3 A A
2 4 6 . 6
 4 5 9 9
  8 5 8

```

## Invalid outputs

This one has three 5s and only one 4:

```
  6 A 2
 C 5 9 3
8 B 3 6 A
 . 9 4 5
  5 B 8

```

The two 6s are adjacent here:

```
  5 2 4
 3 8 B 4
9 B 3 5 8
 A 6 9 C
  . 6 A

```

A 6 and an 8 are adjacent here:

```
  4 3 A
 . 8 2 5
4 6 A 8 B
 5 C 3 9
  B 6 9

```

# Answer
> 12 votes
# JavaScript (ES6), 162 bytes

```
f=(s=`  . 2 3
 3 4 4 5
5 6 6 8 8
 9 9 A A
  B B C`,a=s.match(e=/\S/g).sort(_=>Math.random()-.5))=>/[68](.|[^]{8,10})[68]/.exec(s)?f(s.replace(e,_=>a.pop())):s

```

Try it online!

### Uniform distribution, 163 bytes

The ways the grid is shuffled in the above version, some patterns have a higher probability than others -- which is fine as per the challenge rules. But getting a uniform distribution just costs one extra byte.

```
f=(s=`  . 2 3
 3 4 4 5
5 6 6 8 8
 9 9 A A
  B B C`,a=s.match(e=/\S/g))=>/[68](.|[^]{8,10})[68]/.exec(s)?f(s.replace(e,_=>a.splice(Math.random()*n--,1),n=19)):s

```

Try it online!

### Commented

```
f = (                    // f is a recursive function taking:
  s = `...`,             //   s = initial 2D grid, with an invalid pattern
  a =                    //   a[] = array of
    s.match(e = /\S/g)   //         non-space characters
    .sort(_ =>           //         shuffled
      Math.random() - .5 //         using a random sort() callback
    )                    //
) =>                     //
/[68](.|[^]{8,10})[68]/  // test the validity of the grid by detecting
.exec(s)                 // 6's or 8's separated by 1, 8 or 10 characters
                         // (line-break included)
?                        // if it's not valid:
  f(                     //   try again with another grid:
    s.replace(           //     replace in s:
      e,                 //       each non-space character with
      _ => a.pop()       //       the next character taken from a[]
    )                    //     end of replace()
  )                      //   end of recursive call
:                        // else:
  s                      //   success: return s

```

# Answer
> 5 votes
# Retina, 79 bytes

```

  . 2 3  ¶ 3 4 4 5 ¶5 6 6 8 8¶ 9 9 A A ¶  B B C
/[68](?s:.|.{8,10})[68]/+O?`\S

```

Try it online! Explanation: Based on @Arnauld's JavaScript answer.

```

  . 2 3  ¶ 3 4 4 5 ¶5 6 6 8 8¶ 9 9 A A ¶  B B C

```

Insert the tokens in an invalid layout.

```
/[68](?s:.|.{8,10})[68]/+`

```

Repeat while the layout is invalid...

```
O?`\S

```

... shuffle the tokens.

# Answer
> 5 votes
# Jelly, 39 bytes

```
ỊTḤ>þ“©©©Çð   ‘S+Ɗạþ`Ff“£µ¿‘
17Ż%⁵⁵;ẊÇ¿

```

A niladic Link that yields a flat list of the tokens to be placed in row-major order.

The mapping from question values to the outputted tokens is:

```
Catan (Question):  2   3   4   5   6   8   9  10  11  12   .
    Token (code):  9   3   4   5   0   1   2   6   7   8  10

```

Try it online! Or see a **formatted version** (translates tokens to Catan values and pretty-prints as a hexagon).

(Also here is version that only prints the sixes and eights.)

### How?

```
ỊTḤ>þ“©©©Çð   ‘S+Ɗạþ`Ff“£µ¿‘ - Helper Link, is invalid?: list of tokens
Ị                            - insignificant? (abs(x)<=1 - i.e. is Catan 6 or 8?) (vectorises)
 T                           - truthy, 1-indexed indices
  Ḥ                          - double (vectorises)
                 Ɗ           - last three links as a monad f(X=that):
     “©©©Çð   ‘              -   code-page indices = [6,6,6,14,24,32,32,32]
    þ                        -   (X) table with (that) using:
   >                         -     greater than?
               S             -   (column-wise) sum
                +            -   add (X) (vectorises)
                    `        - use (that) as both arguments of:
                   þ         -   table using:
                  ạ          -     absolute difference
                     F       - flatten
                       “£µ¿‘ - code-page indices = [2,9,11]
                      f      - filter keep
                               -> nonempty list (truthy) if invalid
                                  empty list (falsey) if valid

17Ż%⁵⁵;ẊÇ¿ - Link, get random Catan Distribution: no arguments
17         - seventeen
  Ż        - zero range -> [0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17]
    ⁵      - ten
   %       - modulo -> [0,1,2,3,4,5,6,7,8,9,0,1,2,3,4,5,6,7]
     ⁵     - ten
      ;    - concatenate ->  [10,0,1,2,3,4,5,6,7,8,9,0,1,2,3,4,5,6,7]
         ¿ - while...
        Ç  - ...condition: call the Helper Link (above)
       Ẋ   - ...action: shuffle

```

# Answer
> 5 votes
# Excel VBA, ~~408~~ ~~361~~ 352 bytes

Saved 9 bytes thanks to Taylor Raine

**Golfed code:** (Note: VBA will autoformat this code by adding spaces in many places and a few other niceties.)

```
Sub z
Set g=[C4:E6,F2:G4,D3:E3,E2,F5]
x:
Set c=New Collection
c.Add 2
c.Add 12
For i=1To 2
For j=3To 11
c.Add j
Next j,i
c.Remove 7
For Each s In g
k=CInt(1+Int(Rnd*c.Count))
s.Value=c(k)
c.Remove k
Next
For Each s In g
u=0
For Each t In Union(s.Offset(-1,0).Resize(2,2),s.Offset(0,-1).Resize(2,2))
If t=6Or t=8Then u=u+1
Next
If u>2GoTo x
Next
End Sub

```

**Formatted and commented code:**

```
Sub z()
    ' Define our game board
    Set g = [C4:E6,F2:G4,D3:E3,E2,F5]

    ' Setup a label so we can loop back here and start over as needed
    ' I know this uses GoTo which is [bad] but it's the shortest way to loop
x:

    ' Create a list of all the numbers we want to populate into the grid
    ' We need to recreate this on each loop because it'll be emptied later in this process
    Set c = New Collection
    c.Add 2
    c.Add 12
    For i = 1 To 2  'Add all the numbers 3-11 twice
        For j = 3 To 11
            c.Add j
        Next
    Next
    c.Remove 7  ' As it happens, the 7th term will be one of the "7" values and we only need one of those.

    ' Populate the grid with a random entry from that list and then remove it from the list.
    For Each s In g
        k = CInt(1 + Int(Rnd * c.Count))
        s.Value = c(k)
        c.Remove k
    Next

    ' Look for more than one instance of 6 or 8 in each set of adjacent hexes
    For Each s In g
        u = 0
        ' Check a rotated hexagonal-ish shape centered on the current cell
        For Each t In Union(s.Offset(-1, 0).Resize(2, 2), s.Offset(0, -1).Resize(2, 2))
            ' This is less bytes than something like "If Abs(s-7)=1Then" because this has more spaces than can be removed
            If t = 6 Or t = 8 Then u = u + 1
        Next
        If u > 2 Then GoTo x     ' Loop if you found more than two (since we check the center cell twice)
    Next
End Sub

```

**Output format:**

Output is in a spaced out grid spanning the range `C2:G6` in the active sheet. The values are 2-12 with 7 being the desert. It is a rotated and compressed version of the hexagonal grid. If you translated the first example in the question into Excel, you may want it to look like image below. I've added colors for clarity later and outlined all the cells that would be considered adjacent to the desert in the middle of the board.

However, that spaced out thing is not very byte-friendly. We're going to rotate it 45° and compress it. Here's the same board with the same colors and the same cells outlined in a border showing they're adjacent to the desert:

To better show how this looks like the original board, I'm going to rotate the text 45°. Tilt your head to the left and you should see a perfectly normal Catan board.

**Example board generation:**

With the colors and borders back in place, here's a video showing the generation of some random boards. The top left board is where the code is outputting data. The bottom left board is full of formulas show it shows the same data as the top left but in the more expanded layout. The diamond shape to the right is a snapshot of the same results (again linked by formulas) but with the text rotated 45° CCW and then the whole snapshot rotated 45° CW so it looks like a normal board. The places where it pauses is where a good board was found, I waited, then ran the script again.

# Answer
> 4 votes
# Charcoal, 73 bytes

```
Ｗ¬ＫＡ«⎚Ｐ→↙×ψ³‖Ｃ‖Ｏ↓≔⟦⟧υＷ⁻…³¦²²υ⊞υ‽κ¤⭆υ⁺§…α¹¹κ Ｆ⁵Ｆ⁹«Ｊ⁻λ²κ¿‹IＫＫ¿‹I⌈⊞ＯＫＭ⊟ＫＤ³→⎚

```

Try it online! Link is to verbose version of code. Uses `A`, `B` and `C` to represent `2`, `12` and the desert, `J` and `K` to represent `6` and `8` and intervening letters for the remaining tokens. Explanation:

```
Ｗ¬ＫＡ«

```

Repeat while the canvas is empty.

```
⎚Ｐ→↙×ψ³‖Ｃ‖Ｏ↓

```

Outline a hexagon. (The extra `Clear();` at the beginning ensures that the cursor is at the origin, as it is not there at the end of the loop.)

```
≔⟦⟧υＷ⁻…³¦²²υ⊞υ‽κ¤⭆υ⁺§…α¹¹κ

```

Shuffle the tokens and fill in the hexagon.

```
Ｆ⁵Ｆ⁹«Ｊ⁻λ²κ

```

Loop over the canvas.

```
¿‹IＫＫ¿‹I⌈⊞ＯＫＭ⊟ＫＤ³→⎚

```

If an adjacent pair of `J` and/or `K` are found then clear the canvas.

# Answer
> 3 votes
# Python, 184 bytes

```
from random import*
f=lambda s=".2C"+2*"345#%9AB":any((x:=(*s[:3],"_",*s[3:-3],"_",*s[-3:],*"___"))[i]<'.'>min(x[i+4:i+6]+~-~-i%5*(x[i+1],))for i in range(20))and f(sample(s,k=19))or s

```

Attempt This Online!

`#` and `$` represent tiles 6 and 8 respectively; the rest of the encoding are the same as in the example.

# Answer
> 3 votes
# 05AB1E, ~~56~~ 54 bytes

```
12L7Kû¨¨[.rD18Ýü2ZÝ3LÌû£ü2εé`δ‚εND>‚è}}˜2ô«èJ€ê68æδÊß#

```

Uses `1` for the empty desert hex. The other numbers are the same.
Outputs as a flat list.

Try it online or try it with pretty-print.

**Explanation:**

```
12L7Kû¨¨  # Get a list of the numbers:
12L       #  Push a list in the range [1,12]
   7K     #  Remove the 7
     û    #  Palindromize it
      ¨¨  #  Remove the trailing [2,1]
[         # Start an infinite loop:
 .r       #  Randomly shuffle the list
   D      #  Duplicate this list
 18Ýü2ZÝ3LÌû£ü2εé`δ‚εND>‚è}}˜2ô«èJ€ê68æδÊß#
          #  Pop the copy, and check whether it's valid (see below)
  #       #  If it is valid: stop the infinite loop
          #  (after which the valid shuffled list is output implicitly as result)

```

```
18Ý       # Push a list in the range [0,18]
   ü2     # Get its overlapping pairs: [[0,1],[1,2],...,[16,17],[17,18]]
Z         # Push its flattened maximum (18), without popping the list
 Ý        # Push a list in the range [0,18] again
  3L      # Push list [1,2,3]
    Ì     # Increase each by 2 to [3,4,5]
     û    # Palindromize it to [3,4,5,4,3]
      £   # Split the [0,18] list into parts of those sizes
ü2        # Get overlapping pairs of these lists
  ε       # Map over each pair of lists:
   é      #  Sort the lists by length
    `     #  Pop and push both lists separated to the stack
     δ    #  Apply double-vectorized:
      ‚   #   Pair values together
   ε      #  Inner map over these lists of pairs:
    N  ‚  #   Pair the current index
     D>   #   With the index+1
        è #   Use this [index,index+1] to get the pairs at those indices
  }}      # Close the nested maps
    ˜2ô   # Flatten it two levels down to a single list of pairs:
    ˜     #  Flatten the list of lists of pairs
     2ô   #  Split the flattened list back into parts of size 2
«         # Merge it to the list of overlapping pairs of [0,18]
 è        # Get the values at those indices from the shuffled list
  J       # Join each inner pair together to a string
   €ê     # Sorted-uniquify the digits of each inner string
68        # Push 68
  æ       # Pop and push its powerset: ["",6,8,68]
   δ      # Apply double-vectorized:
    Ê     #  Not equals check
     ß    # Get the flattened minimum to verify none are falsey

```

The index-pairs to check each adjacent hex, generated by `18Ýü2ZÝ3LÌû£ü2εé`δ‚εND>‚è}}˜2ô«`, are:

```
[[0,1],[1,2],[2,3],[3,4],[4,5],[5,6],[6,7],[7,8],[8,9],[9,10],[10,11],[11,12],[12,13],[13,14],[14,15],[15,16],[16,17],[17,18],[0,3],[0,4],[1,4],[1,5],[2,5],[2,6],[3,7],[3,8],[4,8],[4,9],[5,9],[5,10],[6,10],[6,11],[7,12],[8,12],[8,13],[9,13],[9,14],[10,14],[10,15],[11,15],[12,16],[13,16],[13,17],[14,17],[14,18],[15,18]]

     0   1   2
   3   4   5   6
 7   8   9  10  11
  12  13  14  15
    16  17  18

```

Try it online.

# Answer
> 2 votes
# Python 3, 391 bytes:

```
from random import*
R=range
P=lambda i:' '*int((9-(i*2-1))/2)
def b():
 while 1:
  t=[*'2C.'+'345689AB'*2];shuffle(t)
  B,f=[P(i)+' '.join(t.pop(0)for _ in R(i))+P(i)for i in[3,4,5,4,3]],1
  for x in R(5):
   for y in R(9):
    for X,Y in[(1,1),(-1,1),(1,-1),(-1,-1),(0,2),(-2,0)]:
     if 0<=(j:=x+X)<5 and 0<=(k:=y+Y)<9 and {'6','8'}&{B[x][y],B[j][k]}=={B[x][y],B[j][k]}:f=0
  if f:yield B

```

Try it online!

# Answer
> 1 votes
# JavaScript (ES6), 157 bytes

The output format for this version was inspired by Jonathan Allan's answer.

Returns a flat array with the following mapping:

```
-1 0 1 2 3 4 5 6 7 8 9
 . 6 8 9 3 4 5 A B C 2

```

```
f=_=>(a=[...s="8889999_____0000111"].map((_,i)=>~-i%10).sort(_=>Math.random()-.5)).some((v,i)=>227259>>i&(g=k=>3>>a[i+k]&3>>v&1)(1)|g(q=s[i]-5)|g(q+1))?f():a

```

Try it online!

# Answer
> 0 votes
# Ruby, 132 bytes

```
f=->{a=([*0..10]*2)[i=0,q=19].shuffle
"&&X,,,^1,,,]+&&WKK".bytes{|b|q&&=a[i]/2+[a[i+=1]|b&64,a[b/5%5+i],a[b%5+i]].min/2>0}
q ?a:f[]}

```

Try it online!

Outputs a flat array. Uses the same tokenization as Jonathan Allen. (the footer of the TIO link converts `10` to hexadecimal `A` for better presentation.)

```
Catan (Question):  2   3   4   5   6   8   9  10  11  12   .
    Token (code):  9   3   4   5   0   1   2   6   7   8  10

```

**Explanation**

We generate a flat array of all 11 tokens, duplicate it to 22 elements, truncate to 19 elements to discard the extra `8 9 10`, then shuffle. We check if the arrangement is valid, and if so, return it. Otherwise we call recursively to try again.

For each element (except the last one) we check if any of the (up to 3) adjacent elements following it are incompatible. The elements to be checked (to the right, below, and diagonally) are shown as an offset in the table below.

```
134 134 .34
145 145 145 .45
1.5 145 145 145 .4.
    1.4 134 134 .3.
        1.. 1.. ...

```

This was encoded in a magic string as follows. For the below and diagonal offsets, we subtract 1 from each and encode as a two-digit base 5 number. Thus `.45` becomes `34` becomes 3x5 + 4 = decimal 19. If a below or diagonal check is NOT required, we pick a number that gives a duplicate check in one of the other directions.

We then add a multiple of 25 to it to bring it into the printable ASCII range. If checking of an element to the right is NOT required, we add a further multiple of 25 to increase the value above 64.

Decoding should be apparent from the code, but I will add commented code later when I have time.

---
Tags: code-golf, random, board-game, hexagonal-grid
---


title: Draw diagonal lines of text

text:
# Question
Title: Draw diagonal lines of text
Given an input of a list of words, output the words with their letters arranged diagonally:

```
p
 r
  o
p  g
 u  r
  z  a
a  z  m
 n  l  m
  d  e  i
c     s  n
 o        g
  d
g  e
 o
  l
   f

```

(The above should be the output for the input `programming puzzles and code golf`.)

To be precise, each word starts on the first column and three rows below the previous word, and each successive letter moves one column to the right and one row down.

The input may be provided as either a single string of words, separated by exactly one space, or a list/array of words. The words will only be composed of lowercase letters, `a-z`, and will always be at least one character long.

The output may be a single string, an array of lines, or an array of arrays of characters. Leading or trailing whitespace is not allowed, except for a single trailing newline.

Further test cases:

`a bcd efgh i j`

```
a

b
 c
  d
e
 f
  g
i  h

j

```

`x`

```
x

```

`verylongword short`

```
v
 e
  r
s  y
 h  l
  o  o
   r  n
    t  g
        w
         o
          r
           d

```

Since this is , the shortest code in bytes will win!

# Answer
# Vim, ~~85, 76, 66~~, 52 keystrokes/bytes

When I first looked at this challenge, I thought "This is perfect for vim!" And then when I tried it everything went wrong. Here it is, in all of it's messy hacky glory:

```
:se ve=all|s/ /\r\r\r/g
qqGo<esc>?\<.\S
lDjP@qq@qG?.
jdG

```

Try it online, thanks to the (mostly) backwards compatible V interpreter.

# Explanation:

At first I thought I could do this beautifully simple 37 byte version:

```
:se ve=all
qq:g/\S\S/norm ^lDjP
@qq@q

```

Unfortunately, it's not that simple. Let's take it line by line:

```
:se ve=all

```

This enables a feature called 'virtual editing'. It allows the cursor to move to columns that don't exist yet. This answer would be basically impossible without it.

Now we need to separate out the words onto different lines. So we'll replace each space with 3 newlines. Since this is an ex command we can run it simultaneously with our last ex command `:se ve=all` by seperating the two with a bar.

```
|s/ /\r\r\r/g

```

Now the buffer looks like this:

```
Programming

Puzzles

and

code-golf

```

Here's where the fun begins. We set up the traditional recursive macro with: `qq`, and then call this:

```
G               " Move to the last line
 o<esc>         " Append an extra newline

?               " Search backwards for
 \<.            " Any character at the beginning of a word
    \S          " Followed by a non-space character
l               " Move one character to the right
 D              " Delete eveything until the end of this line
  j             " Move down one line
   P            " Paste what we just deleted

```

Then we finish the recursive macro with `@qq@q`. At this point, we have all of the diagonals, we just need to do a little clean up.

```
G                   " Move to the last line
 ?.                 " Search backwards for any character
j                   " Move down one line
 dG                 " Delete until the end of the buffer

```
> 18 votes

# Answer
# Turtlèd, ~~28~~ 26 bytes

Oh my, I appear to be beating a language specifically designed for golfing. this is a great day.

```
!_4[*.[ rd+.]ul[ ul]r;_+]_

```

### Try it online!

## Explanation

(write means writing to the cell on the grid, pointed char means char in input the string pointer points to)

```
!                         Take string input into variable
 _                        Normally conditional, with >1 input (there will be), write ' '
  4                       set register to 4
   [*                   ] until the current cell is *
     .                    Write pointed char, initially first char
      [     ]             Until space is written on cell
        rd+.              move right, down, string pointer++, write pointed char
             ul[ ul]      Move back up to the top of the word
                    r;    Move right, down 4 (because this is register value)
                      _+  write * if end of input, else ' ', increment string pointer
                        _ will always write ' ', since it will always point at start char

```

note trailing space.

Input also needs trailing space. seeing as python can take a list, this is a lot like taking a list in Turtlèd
> 7 votes

# Answer
# MATL, 28 bytes

```
c!t&n:q3_*ts_b+5M4$XdZ!cZ{Zv

```

Input is a cell array of strings, with commas as optional separators:

```
{'programming' 'puzzles' 'and' 'code' 'golf'}

```

or

```
{'programming', 'puzzles', 'and', 'code', 'golf'}

```

Try it online! Or verify all test cases: , , , .

### Explanation

Consider the following input as an example:

```
{'aaaa' 'bb' 'ccc'}

```

You can view the partial results (stack contents) inserting the comment symbol `%` at any point in the code. For example, view the stack contents after the fourth function (`&n`).

```
c        % Input cell array of strings implicitly. Convert to 2D char array,
         % right-padding with spaces
         % STACK: ['aaaa'; 'bb  '; 'ccc']
!        % Transpose
         % STACK: ['abc'
                   'abc'
                   'a c'
                   'a  ']
t        % Duplicate
         % STACK: ['abc'
                   'abc'
                   'a c'
                   'a  '],
                  ['abc'
                   'abc'
                   'a c'
                   'a  '],
&n       % Number of rows and of columns
         % STACK: ['abc'
                   'abc'
                   'a c'
                   'a  '], 4, 3
:q       % Range, subtract 1
         % STACK: ['abc'
                   'abc'
                   'a c'
                   'a  '], 4, [0 1 2]
3_*      % Multiply by -3
         % STACK: ['abc'
                   'abc'
                   'a c'
                   'a  '], 4, [0 -3 -6]
ts_      % Duplicate, sum, negate
         % STACK: ['abc'
                   'abc'
                   'a c'
                   'a  '], 4, [0 -3 -6], 9
b        % Bubble up in stack
         % STACK: ['abc'
                   'abc'
                   'a c'
                   'a  '], [0 -3 -6], 9, 4
+        % Add
         % STACK: ['abc'
                   'abc'
                   'a c'
                   'a  '], [0 -3 -6], 13
5M       % Push second input of last function again
         % STACK: ['abc'
                   'abc'
                   'a c'
                   'a  '], [0 -3 -6], 13, 4
4$Xd     % Buld numerical sparse matrix from the above four arguments. The
         % columns of the first input argument will be the diagonals of the
         % result, with indices given bu the second input (negative is below
         % main diagonal). The matrix size is the third and fourth arguments
         % STACK: [97  0  0  0
                    0 97  0  0
                    0  0 97  0
                   98  0  0 97
                    0 98  0  0
                    0  0 32  0
                   99  0  0 32
                    0 99  0  0
                    0  0 99  0
                    0  0  0 32
                    0  0  0  0
                    0  0  0  0
                    0  0  0  0]
Z!c      % Convert from sparse to full, and then to char. Character 0 is
         % displayed as space
         % STACK: ['a   '
                   ' a  '
                   '  a '
                   'b  a'
                   ' b  '
                   '    '
                   'c   '
                   ' c  '
                   '  c '
                   '    '
                   '    '
                   '    '
                   '    ']
Z{       % Split into cell array, with each row in a cell
         % STACK: {'a   ', ' a  ', '  a ', 'b  a', ' b  ', '    ', 'c   ', ' c  ', '  c ', '   ', '   ', '   ', '   '}
Zv       % Deblank: remove trailing space from each string. Implicitly display,
         % each string on a different line. Empty strings do not generate
         % a newline
         % STACK: {'a   ', ' a', '  a', 'b  a', ' b', '', 'c', ' c', '  c', '', '', '', ''}

```
> 6 votes

# Answer
## JavaScript (ES6), ~~118~~ ~~109~~ 84 bytes

Takes input as an array of words. Returns an array of arrays of characters.

```
s=>s.map((w,y)=>[...w].map((c,x)=>(a[p=y*3+x]=a[p]||Array(x).fill(' '))[x]=c),a=[])&&a

```

### Alternative version, 109 bytes

Returns a string.

```
let f =

s=>s.map((w,y)=>[...w].map((c,x)=>(a[p=y*3+x]=a[p]||Array(x).fill` `)[x]=c),a=[])&&a.map(s=>s.join``).join`
`

console.log(f(["programming", "puzzles", "and", "code", "golf"]))
```
> 5 votes

# Answer
# Japt `-Rx`, ~~17~~ ~~16~~ 13 bytes

Takes input as an array of words. If trailing whitespace on each line were allowed then the last 4 characters could be removed to tie with the Charcoal solution.

```
yÈmú3)iYçÃmx1

```

Try it or run all test cases

---

## Explanation

```
y                 :Transpose
 È                :Map each word at 0-based index Y
  m               :  Map each character
   ú3             :    Right pad with spaces to length 3
     )            :  End mapping
      i           :  Prepend
       Yç         :   Space repeated Y times
         Ã        :End mapping and transpose
          m       :Map
           x1     :  Trim right
                  :Implicitly join with newlines, trim and output

```
> 4 votes

# Answer
# Common Lisp, ~~673~~ ~~668~~ 597 bytes

Terrible solution, I know. I'll probably edit this more after some sleep.

```
(defun f(&rest z)(let((l)(a 0)(s)(o)(b)(c 0))(loop(setf b(length l))(setf l"")(loop for w in z for i from 0 do(if(>(+(length w)(* i 3))c)(setf c(+(length w)(* i 3))))(setf s(+(* i -3)a))(when(and(>= s 0)(< s(length w)))(setf o(format nil"~v@{~a~:*~}"s" "))(if(and(>=(- s 3)0)(not(equal i(-(length z)1))))(setf o(subseq o(- s 2))))(setf l(concatenate'string o(string(char w s))l)))(when(>= s(length w))(setf l(concatenate'string"   "l))))(if(<=(length l)b)(setf l(concatenate'string(format nil"~v@{~a~:*~}"(- b(length l)-1)" ")l)))(print(string-right-trim" "l))(if(>= b c)(return))(setf a(1+ a)))))

```

Usage:

```
* (f "ppcg" "is" "pretty" "ok")

"p"
" p"
"  c"
"i  g"
" s"
""
"p"
" r"
"  e"
"o  t"
" k  t"
"     y"
""
NIL

```

This loops over every word in the provided list and adds appropriate characters to the current line. Appropriate padding is provided by my subpar usage of `format`.

Note: I'm new to Common Lisp, but I know enough to realize that this could use a lot of improvement.
> 3 votes

# Answer
# Python 2, 146 bytes

```
s=input()
k=max(map(len,s))
a=[k*[' ']for x in range(k+len(s)*3+3)]
for x in range(len(s)):
 for y in range(len(s[x])):a[x*3+y][y]=s[x][y]
print a

```

Note: the indentations for the last two lines are `<space>` and `<tab>`, which saves one byte since I don't need to double-indent.

Input is to be entered as an array of strings like so: `["hello", "world"]` or `['hello', 'world']`. Output is an array of arrays of characters.

There's probably a better way to do this...

**EDIT** Thanks to Doorknob for pointing out a missing close square bracket. I placed it before the `*k...` in the third line.
> 3 votes

# Answer
# C#, 336 Bytes:

Golfed:

```
string D(string[]s){int x=0,y=0,r=0,q=2*(s.Max().Length+s.Length)+1;var a=new char[q, q];for(int i=0;i<s.Length;i++){y=r;for(int j=0;j<s[i].Length;j++){a[y,x]=s[i][j];x+=1;y+=1;}x=0;r+=3;}var o="";for(x=0;x<q;x++){var t="";for(y=0;y<q;y++)t+=a[x,y];o+=t==string.Join("",Enumerable.Repeat('\0',q))?"":(t.TrimEnd('\0')+"\r\n");}return o;}

```

Ungolfed:

```
public string D(string[] s)
{
  int x = 0, y = 0, r = 0, q = 2 * (s.Max().Length + s.Length) + 1;
  var a = new char[q, q];
  for (int i = 0; i < s.Length; i++)
  {
    y = r;
    for (int j = 0; j < s[i].Length; j++)
    {
      a[y, x] = s[i][j];
      x += 1;
      y += 1;
    }
    x = 0;
    r +=3;
  }
  var o = "";
  for (x = 0; x < q; x++)
  {
    var t = "";
    for (y = 0; y < q; y++)
      t += a[x, y];
    o += t == string.Join("", Enumerable.Repeat('\0', q)) ? "" : (t.TrimEnd('\0') + "\r\n");
  }
  return o;
}

```

Testing:

```
  var codeGolf = new DrawDiagonalLinesOfText();
  Console.WriteLine(codeGolf.E(new string[] { "programming", "puzzles", "and", "code", "golf" }));
  Console.WriteLine(codeGolf.E(new string[] { "a", "bcd", "efgh", "i", "j" }));
  Console.WriteLine(codeGolf.E(new string[] { "verylongword", "short" }));

p
 r
  o
p  g
 u  r
  z  a
a  z  m
 n  l  m
  d  e  i
c     s  n
 o        g
  d
g  e
 o
  l
   f

a
b
 c
  d
e
 f
  g
i  h
j

v
 e
  r
s  y
 h  l
  o  o
   r  n
    t  g
        w
         o
          r
           d

```
> 3 votes

# Answer
# Charcoal, ~~18~~ 11 bytes

<sup>~~16~~ 9 bytes if trailing whitespaces were allowed: try it online.</sup>

```
ＵＴＷＳ«Ｐ↘ιＭ³↓

```

My first Charcoal answer. Thanks to *@DLosc* for suggestion  and  instead of using  and  (Jump) to go back to the start of the line (and three down).

Try it online (verbose) or Try it online (pure).

**Explanation:**

Disable trailing spaces in the output:

```
ToggleTrim();
ＵＴ

```

Loop while there is still a next input-string:

```
While(InputString()){ ... }
ＷＳ« ...

```

Print this string without moving the cursor in a down-right direction:

```
Multiprint(:DownRight, i);
Ｐ↘ι

```

And then move three positions down for the next iteration:

```
Move(3, :Down);
Ｍ³↓

```
> 3 votes

# Answer
# Vyxal, 21 bytes

```
ʁ2꘍∑374f?vLz4jø^↵vøR⁋

```

Try it Online!

```
              ø^      # Using the canvas, draw...
ʁ                     # Text: Palindromise each
 2꘍                   # Append two spaces to each
   ∑                  # Concatenate into a single string
    374f              # Directions: [3, 7, 4] - down-left, up-right, down
        ?vL           # Lengths: Lengths of each word in input
           z          # Zip with self
            4j        # Join with 4s
                ↵vøR⁋ # Strip trailing whitespace (ugh)

```
> 3 votes

# Answer
# q/kdb+, ~~130~~ ~~109~~ ~~94~~ ~~90~~ ~~86~~ 84 bytes

**Solution:**

```
f:{-1(+)a rtrim(til(#)E){raze(x#" "),y,\:"  "}'E:(+)(a:{(max(#:)each x)$x})" "vs x;}

```

**Examples:**

```
q)f "programming puzzles and code golf"
p
 r
  o
p  g
 u  r
  z  a
a  z  m
 n  l  m
  d  e  i
c     s  n
 o        g
  d
g  e
 o
  l
   f
q)f "a bcd efgh i j"
a

b
 c
  d
e
 f
  g
i  h

j
q)f (),"x"
x
q)f "verylongword short"
v
 e
  r
s  y
 h  l
  o  o
   r  n
    t  g
        w
         o
          r
           d

```

**Explanation (ungolfed):**

The basic gist is to create a bunch of equal length strings from the input string, flip (rotate) them, then add appropriate whitespace to get something that looks like this:

```
"p  p  a  c  g   "
" r  u  n  o  o  "
"  o  z  d  d  l "
"   g  z     e  f"
"    r  l        "
"     a  e       "
"      m  s      "
"       m        "
"        i       "
"         n      "
"          g     "

```

which is flipped again, and printed to stdout.

Here's a line-by-line breakdown of the concept:

```
A:"programming puzzles and code golf"; // original input
B:" " vs A;                            // split on " "
C:max count each B;                    // find length of the longest string
D:C$B;                                 // pad each string to this length
E:flip D;                              // flip (rotate) string
F:{raze(x#" "),y,\:"  "};              // appends each char with "  " and prepends an increasing number of " "
G:(til count E)F'E;                    // execute function F with each pair of 0..n and item in list E
H:max count each rtrim G;              // find longest string (ignoring right whitespace)
I:H$G;                                 // pad each of the strings to this length
J:flip I;                              // flip to get result
-1 J;                                  // print to stdout, swallow return value

```

**Notes:**

A few ways to shave off some (11) easy bytes if we *really* wanted to:

* Could save 2 bytes by dropping the `f:` and leaving as an anonymous function
* Could save 3 bytes by dropping the `-1` and `;` and returning a list of strings rather than printing to stdout
* Could save 6 bytes if we passed in a list of strings rather than space-separated string

**Edits:**

* -11 bytes, use `rtrim` to find max length to pad, removed need for storing `C` variable
* -15 bytes, switching out the `max count each` for a lambda function `a` which is created once and used twice
* -4 bytes, moving the `raze` into the lambda function to save a `raze each`
* -4 bytes, simplified the core lambda function that adds the whitespace
* -2 bytes, use `(+)` as shorthand for `flip`
> 2 votes

# Answer
# Mathematica, 146 bytes

```
P=PadRight;T=Transpose;R=Riffle;Select[Rest@T@P@MapIndexed[""~Table~#2~Join~#1&,T@P@R[Characters/@#~R~{},{},3]]//.{0->"",{x__,""}->{x}},#!={""}&]&

```

I'm disappointed by this bytecount, but oh well.

Defines an anonymous function that takes a list of words (e.g. `{"this","that","these"}`) and returns a two-dimensional array of characters. To view in grid form, add a `//Grid` at the end.

Converts the strings to an array, adds extra lines, transposes the array, prepends the necessary shifts, then transposes again.

Example result (formatted as grid):
> 1 votes

# Answer
# Jelly, 24 bytes

```
z⁶j€⁾  µJ’⁶ẋ;"z⁶œr€⁶Yœr⁷

```

**Try it online!**

### How?

```
z⁶j€⁾  µJ’⁶ẋ;"z⁶œr€⁶Yœr⁷ - Main link: a list of strings
z                        - transpose with filler...
 ⁶                       -     space character
  j€                     - join €ach with
    ⁾                    -     two spaces
       µ                 - monadic chain separation, call the result x
        J                - range(length(x)) [1,2,...,x]
         ’               - decrement (vectorises) [0,1,...x-1]
           ẋ             - repeat (vectorises)
          ⁶              - a space ['', ' ',...,'x spaces']
             "           - zip with
            ;            - concatenation (prefixes with the space strings)
              z          - transpose with filler...
               ⁶         -     space character
                œr€⁶     - trim spaces from the right of €ach
                    Y    - join with line feeds
                     œr⁷ - trim line feeds from the right
                         - implicit print

```
> 1 votes

# Answer
# Python 2, 182 bytes

```
def f(s):
 M=max(map(len,s));p=' '*M;L=[p]+s+M*[p];r='';k=0
 while k/M<len(s)*3+M:
  i=k%M;w=k/M-i+1;r+=(L[(w/3+1)*(w%3==1)]+p)[i];k+=1
  if i==M-1:r=r.rstrip()+'\n'
 return r.strip()

```

A bit long, but on the positive side, it returns a string with no trailing white space on each line, and no trailing white space or returns at the end; constraints that some other entries don't obey.

A list of words is passed into the function; some 'blanks' are aded to this list and then the algorithm maps a row,column pair to a wordNumber, characterNumber in the expanded list. (This is a bit of the inverse of the usual strategy seen in other solutions).

If we allow trailing white space on all lines except the last, we can do a bit better (163 bytes):

```
def f(s):
 M=max(map(len,s));p=' '*M;L=[p]+s+M*[p];r='';k=0
 while k/M<len(s)*3+M:i=k%M;w=k/M-i+1;r+=(L[(w/3+1)*(w%3==1)]+p)[i]+'\n'*(i==M-1);k+=1
 return r.strip()

```
> 1 votes

# Answer
# K4, 58 bytes

**Solution:**

```
+(|/{0+/|\|~^x}@'x)$x:(2-(!c)+3*#x)$"  "/:'$+(c:|/#:'x)$x:

```

**Examples:**

```
q)k)+(|/{0+/|\|~^x}@'x)$x:(2-(!c)+3*#x)$"  "/:'$+(c:|/#:'x)$x:("programming";"puzzles";"and";"code";"golf")
"p          "
" r         "
"  o        "
"p  g       "
" u  r      "
"  z  a     "
"a  z  m    "
" n  l  m   "
"  d  e  i  "
"c     s  n "
" o        g"
"  d        "
"g  e       "
" o         "
"  l        "
"   f       "
q)k)+(|/{0+/|\|~^x}@'x)$x:(2-(!c)+3*#x)$"  "/:'$+(c:|/#:'x)$x:(,"a";"bcd";"efgh";,"i";,"j")
"a   "
"    "
"    "
"b   "
" c  "
"  d "
"e   "
" f  "
"  g "
"i  h"
"    "
"    "
"j   "
q)k)+(|/{0+/|\|~^x}@'x)$x:(2-(!c)+3*#x)$"  "/:'$+(c:|/#:'x)$x:("verylongword";"short")
"v           "
" e          "
"  r         "
"s  y        "
" h  l       "
"  o  o      "
"   r  n     "
"    t  g    "
"        w   "
"         o  "
"          r "
"           d"

```

**Explanation:**

Right-pad strings so they are the same length, transpose, join with `" "`, left-pad to generate diagonals, then right-pad to correct lengths and transpose back. Takes a list of strings and returns a list of strings. Probably golfable but still shorter than my q/kdb+ solution.

```
+(|/{0+/|\|~^x}@'x)$x:(2-(!c)+3*#x)$"  "/:'$+(c:|/#:'x)$x:
                                                        x:      / save as variable x
                                                       $        / pad
                                             (        )         / do this together
                                                  #:'x          / count (#:) each (') x
                                                |/              / max
                                              c:                / save as variable c
                                            +                   / flip / transpose
                                           $                    / string ($)
                                    "  "/:'                     / join each with "  "
                                   $                            / pad
                      (           )                             / do this together
                                #x                              / count (#) x
                              3*                                / multiply by 3
                             +                                  / add to
                         (  )                                   / do this together
                          !c                                    / range 0..c
                       2-                                       / subtract from 2
                    x:                                          / save as x:
                   $                                            / pad
 (                )                                             / do all this together
    {         }@'x                                              / apply (@) lambda {} to each x
            ^x                                                  / null (^) x (" " is considered null)
           ~                                                    / not
          |                                                     / reverse
        |\                                                      / max (|) scan (\), maxs
     0+/                                                        / sum (+) over (/) starting with 0
  |/                                                            / max (|) over (/), max
+                                                               / transpose

```
> 1 votes

# Answer
# 05AB1E, 17 bytes

<sup>12 bytes if trailing whitespaces were allowed: try it online.</sup>

```
ζε2úíJNúS}ζJðδÜõÜ

```

Port of *@Shaggy*'s Japt answer.

Input as a list of list of characters; output as a list of lines.

Try it online.

**More interesting answer using the Canvas builtin (~~27~~ 25 bytes):**
<sup>~~20~~ 19 bytes if trailing whitespaces were allowed: try it online.</sup>

```
€gDø4.ý˜I€ûðºý374S.Λ¶¡ðδÜ

```

-2 bytes thanks to *@emanresuA*.

Input as a list of words; output as a list of lines.

Try it online.

**Explanation:**

```
ζ         # Zip/transpose; swapping rows/columns of the (implicit) input-list of lists
          # of characters, with a space " " as filler for shorter lists
 ε        # Map over each inner lists of characters:
  2ú      #  Pad each inner character with 2 leading spaces
    í     #  Reverse each inner string, so the spaces are trailing
     J    #  Join this list together to a single string
      Nú  #  Pad the 0-based map-index amount of leading spaces
        S #  Convert the string back to a list of characters
 }ζ       # After the map: Zip/transpose back again with " " filler
   J      # Join each inner list together to a single string
     δ    # Map over each inner line:
    ð Ü   #  Trim trailing spaces
       õÜ # Trim trailing empty strings from the list
          # (after which the list of lines is output implicitly)

```

```
€gDø4.ý˜I€ûðºý374S.Λ¶¡ðδÜ

€g        # Get the length of each word of the (implicit) input-list
  Dø      # Convert each value to a pair of this value with a Duplicate + Zip/transpose
    4.ý   # Intersperse this list of pairs with 4 as delimiter
       ˜  # Flatten it to a single list
I         # Push the input-list of words again
 €û       # Palindromize each word
   ðºý    # Join this list with "  " (2 spaces) delimiter
ŽDā       # Push 374
   S      # Convert it to a list of digits: [3,7,4]
.Λ        # Use the modifiable Canvas builtin with these three arguments
  ¶¡      # Split it on newlines
     δ    # Map over each inner line:
    ð Ü   #  Trim trailing spaces
          # (after which the list of lines is output implicitly)

```

*Additional information about the Canvas builtin `Λ`/:*

It takes 3 arguments to draw an ASCII shape:

1. Length of the lines we want to draw
2. Character/string to draw
3. The direction to draw in, where each digit represents a certain direction:

```
7   0   1
  ↖ ↑ ↗
6 ← X → 2
  ↙ ↓ ↘
5   4   3

```

`€gDø4.ý˜I€ûðºý374S` creates the following Canvas arguments:

* Lengths (`€gDø4.ý˜`): e.g. `[11,11,4,7,7,4,3,3,4,4,4,4,4,4]` for input `["programming","puzzles","and","code","golf"]`
* Characters (`I€ûðºý`): e.g. `"programmingnimmargorp puzzleselzzup andna codedoc golflog"` for input `["programming","puzzles","and","code","golf"]`
* Directions (`374S`): `[3,7,4]`, which translates to \\$\[↘,↖,↓\]\\$

Because we have a list of lengths, those are leading here.

Step 1: Draw 11 characters (`"programming"`) in direction `3` (\\$↘\\$):

```
p
 r
  o
   g
    r
     a
      m
       m
        i
         n
          g

```

Step 2: Draw 11-1 characters (`"nimmargorp"`) in direction `7` (\\$↖\\$):

```
p
 r
  o
   g
    r
     a
      m
       m
        i
         n
          g

```

Step 3: Draw 4-1 characters (`" p"`) in direction `4` (\\$↓\\$):

```
p
 r
p o
   g
    r
     a
      m
       m
        i
         n
          g

```

Step 4: Draw 7-1 characters (`"uzzles"`) in direction `3` (\\$↘\\$):

```
p
 r
p o
 u g
  z r
   z a
    l m
     e m
      s i
         n
          g

```

etc.

See this 05AB1E tip of mine for an in-depth explanation of the Canvas builtin.

`€gDø4.ý˜` could alternatively be `εgD4)}˜¨` or `€gDø€4¦˜`, but I've been unable to find anything shorter.
> 1 votes

# Answer
# Perl 6, 73 bytes

```
{my@t;for .kv ->\i,\w{for w.comb.kv {@t[3*i+$^a][$^a]=$^b}};@t »||»" "}

```

Try it online!

The input argument is a list of words. The output is an array of array of characters.
> 0 votes

# Answer
# PHP, 100 bytes

```
<?foreach($_GET as$k=>$v)for($x=0;$y=$v[$x];$t[$x++]=$y)($t=&$s[$k*3+$x])?:$t=" ";echo join("
",$s);

```

Try it online!
> 0 votes

# Answer
# , 54 bytes

```
[:+/@,:&.(_32+3&u:)&.>/]({.-@#\<@{."0])&>~#&>-@+3*i.@#

```

Try it online!

This was a surprisingly good challenge -- deceptively simple but with a lot of depth, and many paths to a solution. Normally I dislike "no trailing whitespace" constraints, but here it was key to the problem's complexity.

After many different approaches, I finally found one which feels like it works with J rather than against it. I will add a detailed explanation another time.

Note: This returns a boxed list of lines, but in the TIO I open and echo each box so that correctness is easier to see.
> 0 votes

---
Tags: code-golf, string
---


title: Divide one number by another

text:
# Question
Title: Divide one number by another
## Challenge

Given two numbers, output their quotient. In other words, integer divide one number by another.

Both divisor/dividend will be under 10001. Division must be performed using integer division, rounding down.

Here are some example inputs and outputs:

```
5       1       5
-4      2       -2
4       -2      -2
6       2       3
16      4       4
36      9       4
15      2       7
17      3       5
43      5       8
500     5       100
500     100     5
10000   2       5000

```

Or as CSV:

```
5,1,5
-4,2,-2
4,-2,-2
6,2,3
16,4,4
36,9,4
15,2,7
17,3,5
43,5,8
500,5,100
500,100,5
10000,2,5000

```

## Rules

* Standard loopholes not allowed
* You must use integer division, not floating point division
* This is . Shortest answer wins, but will not be selected.
* The second input (denominator) will never be equal to `0`.

## Why?

I'm interested in seeing answers in esoteric languages, like Brainfuck and Retina. Answers in regular languages will be trivial, however I would really like to see answers in these languages.

I will be giving a bounty of **+50** reputation to a Retina answer.

# Answer
# JavaScript, 11 bytes

JavaScript doesn't have integers but using a bitwise or parses a float as a signed 32 bit integer.

```
a=>b=>a/b|0

```

# Try it online

```
const f = a=>b=>a/b|0
alert(f(prompt())(prompt()))
```
> 3 votes

# Answer
# Mathematica, 8 bytes

```
Quotient

```

Thanks to @JungHwanMin for reminding me there's a builtin.
> 3 votes

# Answer
# Python 2, ~~14~~ 11 bytes

```
int.__div__

```

**Try it online**
> 2 votes

# Answer
# C (GCC), 13 bytes

Doesn't work on *all* implementations, but that's OK.

```
f(a,b){a/=b;}

```

Try it on TIO!
> 2 votes

# Answer
# QBIC, 8 bytes

```
::?a'\`b

```

# Explanation:

```
::    get a and b from the cmd line
?     Print
a \ b the backslash does integer division, (opposed to the forward slash / for float div)
  ' ` however, the same symbol is used for ELSE. We need to escape it with ' and `

```

---

Note that the latest version of QBIC allows for an inline use of the `:` function, saving two bytes:

```
?:'\`:

```
> 2 votes

# Answer
# Pip, 4 bytes

```
a//b

```

Try it online!

Explanation:

```
      A and B are read implicitly from the cmd line
a//b  Calculate the int div of a and b (double slash == int div)
      Results of the last expression are printed implicitly.

```
> 2 votes

# Answer
# CJam, 3 bytes

```
q~/

```

Try it online!
> 2 votes

# Answer
# 아희(Aheui), 15 bytes

```
방방나망희

```

Try it here! (please copy and paste the code manually)
> 2 votes

# Answer
# Bash, ~~25~~ ~~22~~ 15 bytes

```
echo $(($1/$2))

```

Save to script, input numbers given at command line

Saved 3 bytes thanks to @betseg
> 2 votes

# Answer
# Aceto, 6 bytes

```
riri/p

```

```
ri takes input as integer
/ does integer division
p prints it
```

Try it online!
> 2 votes

# Answer
# PHP, 23 Bytes

```
<?=$argv[1]/$argv[2]^0;

```

or

```
<?=$argv[1]/$argv[2]|0;

```

and for 29 Bytes

```
<?=intdiv($argv[1],$argv[2]);

```
> 1 votes

# Answer
# Jelly, 1 byte

```
:

```

Try it online!
> 1 votes

# Answer
# 05AB1E, 3 bytes

`II÷`

Try online

If you can reverse the input, it would work in 1 byte: `÷`
> 1 votes

# Answer
# Decimal, 12 bytes

```
81D81D44D301

```

Ungolfed:

```
81D   ; builtin 1 - read INT to stack
81D   ; builtin 1 - read INT to stack
44D   ; math divide (postfix /)
301   ; print from stack to output

```

Try it online!
> 1 votes

# Answer
# Triangular, 6 bytes

```
$.$%_<

```

Try it online!

Formats into this triangle:

```
  $
 . $
% _ <

```

Without directionals and no-ops, the code looks like this: `$$_%`

* `$` \- read input as integer
* `_` \- divide
* `%` \- print
> 1 votes

# Answer
# Retina, 28 bytes

```
\d+
*
~`(_+) (_+)
K`$1$nC`$2

```

Try it online!

I'm quite new to Retina; I probably could have golfed this more.

**Explanation:**

Let's start with an input: `38 4`

```
\d+
*

```

This turns the numbers into unary, so 4 is represented as \____, and 38 with 38 underscores.

```
~`...

```

This marks a stage that generates code to run afterwards

```
(_+) (_+)
K`$1$nC`$2

```

This is a replace stage to generate the division code; Firstly, it splits the string into the dividend (referenced as $1) and divisor (referenced as $2). Then, it returns the string:

```
K`{dividend as unary}
C`{divisor as unary}

```

The returned string is evaluated and the answer implicitly printed. It sets the working string to the dividend, and counts the matches of the divisor in it.
> 1 votes

# Answer
## Keg, 3 bytes

```
¿¿/

```

Simply 2 nice inputs and then divides them.

TIO
> 1 votes

# Answer
## Batch, 16 bytes

```
@cmd/cset/a%1/%2

```

`set/a` doesn't print its output inside a batch script, so we have to fake it out by starting a new copy of the command processor.
> 0 votes

# Answer
# GML, 30 bytes

```
return argument0 div argument1

```
> 0 votes

# Answer
# TI-Basic, 6 bytes

```
Input :iPart(X/Y

```
> 0 votes

# Answer
# Retina, ~~40~~ 38 bytes

```
\d+
*
(-?)(_+);(-?)(\2)*_*
$1$3$#4
--

```

Takes input in the format `denominator;numerator`. Also works for negative integers after the specs got changed, unlike the existing Retina answer.

-2 bytes thanks to *@FryAmTheEggman* thanks to a golf suggested in another Retina answer of mine.

Try it online.

**Explanation:**

Convert all numbers in the input to unary, replacing them with that amount of underscores:

```
\d+
*

```

Integer divide the two unary numbers (but with a decimal numbers as result), and filter all `-` to the front at the same time:

```
(-?)(_+);(-?)(\2)*_*
$1$3$#4

```

Remove any `--` if present:

```
--

```
> 0 votes

# Answer
# J-uby, 2 bytes

```
:/

```

Attempt This Online!
> 0 votes

# Answer
## Ruby, 10 bytes

```
->i,j{i/j}

```

Extremely simple. Lambda function that returns the value `i/j`.
> -1 votes

---
Tags: code-golf, number, arithmetic
---


title: CGAC2022 Day 2: Self-trapping Elf

text:
# Question
Title: CGAC2022 Day 2: Self-trapping Elf
Part of **Code Golf Advent Calendar 2022** event. See the linked meta post for details.

---

An Elf is hopping on a chessboard which extends infinitely in all four directions. They move like a generalized chess Knight: on each step, they move `X` units horizontally and `Y` units vertically, or `Y` units horizontally and `X` units vertically. (`(X,Y) = (1,2)` would give regular Knight's moves.)

The Elf plays the game "Self-trapping Elf". In this game, the Elf starts at position `(0,0)` and hops around. They cannot hop into any cell already hopped on, including the starting cell. The objective is to trap themselves in the fewest number of steps possible.

**Task:** Given the values of `X` and `Y` (`0 < X < Y`), output the sequence of coordinates that the Elf should visit, so that they can trap themselves in exactly **15** moves.

Standard rules apply. The shortest code in bytes wins.

Some explanation can be found in this Puzzling post. There are many ways to achieve this: (the worked out examples are for `(X, Y) = (1, 2)`)

* Choose any position (X) one move away from the origin (O). We will step all 8 cells reachable from X and then move into it.

```
. O . A .
G . . . B
. . X . .
F . . . C
. E . D .

```
* For almost any pair of cells out of `OABCDEFG`, there is exactly one way to move from one cell to the other in 2 steps without going through X.

The following are valid solutions to the problem:

```
. . . . 1 . . . .
. . . . . . . 3 .
. . . 0 . 2 . . .
. . e . . . 4 . .
d . . . f . . . 5
. . c . . . 6 . .
. . . a . 8 . . .
. b . . . . . 7 .
. . . . 9 . . . .

. 0 b 6 .
a 5 . 1 c
. . f . 7
4 9 . d 2
. e 3 8 .

```

The actual output for the first answer would be

```
[(1, 2), (2, 0), (4, 1), (3, -1), (5, -2), (3, -3), (4, -5), (2, -4),
 (1, -6), (0, -4), (-2, -5), (-1, -3), (-3, -2), (-1, -1), (1, -2)]

```

You may include or exclude the starting position of `(0, 0)`.

# Answer
> 4 votes
# Charcoal, 50 bytes

```
Ｆ²⊞υＮ≔⟦υ⮌υ⟧θ≔⁺θ±θθ≔⁺θＥθＥι⎇μλ±λθＩΦΣＥθ⟦Ｅ§θ⊖κ⁺λ§ιμι⟧κ

```

Attempt This Online! Link is to verbose version of code. Explanation:

```
Ｆ²⊞υＮ

```

Input `X` and `Y`.

```
≔⟦υ⮌υ⟧θ≔⁺θ±θθ≔⁺θＥθＥι⎇μλ±λθ

```

Generate all of the positions one step away from the origin.

```
ＩΦΣＥθ⟦Ｅ§θ⊖κ⁺λ§ιμι⟧κ

```

Output the positions and in between each pair of positions also output the other position one step away from both.

If string input and complex output is acceptable, then for ~~38~~ 36 bytes:

```
Ｆ+-Ｆ⁴⊞υ×Ｉ⪫⟦θιηj⟧ωＸＩ1jκΦΣＥυ⟦⁺ι§υ⊖κι⟧κ

```

Attempt This Online! Link is to verbose version of code. Explanation:

```
Ｆ+-Ｆ⁴⊞υ×Ｉ⪫⟦θιηj⟧ωＸＩ1jκ

```

Generate all positions one step away from the origin.

```
ΦΣＥυ⟦⁺ι§υ⊖κι⟧κ

```

Output the positions and in between each pair of positions also output the other position one step away from both.

# Answer
> 4 votes
# JavaScript (ES6), 79 bytes

Expects `[Y, X]`. The path is hardcoded.

```
V=>[p=[0,0],..."763145621057234"].map(d=>p=p.map((v,k)=>v+V[d&1^k]*~-(d>>k&2)))

```

Try it online!

Or **78 bytes** if we don't output the starting position.

### Encoding

The directions are encoded with 3-bit values, using the following scheme:

```
 d | as binary | (dx,dy)
---+-----------+---------
 0 |   0 0 0   | (-Y,-X)
 1 |   0 0 1   | (-X,-Y)
 2 |   0 1 0   | (+Y,-X)
 3 |   0 1 1   | (+X,-Y)
 4 |   1 0 0   | (-Y,+X)
 5 |   1 0 1   | (-X,+Y)
 6 |   1 1 0   | (+Y,+X)
 7 |   1 1 1   | (+X,+Y)
       | | |
       | | +--> if set, use X for |dx| and Y for |dy|
       | |      (if cleared, do it the other way around)
       | +----> sign of dx (positive if set)
       +------> sign of dy (positive if set)

```

### Commented

```
V =>                 // V[] = input vector [ Y, X ]
[ p = [0,0],         // p[] = current position, initialized to [ 0, 0 ]
  ...                //       this is also the 1st direction (zero'ish)
  "763145621057234"  // <-- = the directions for the next 15 moves
]                    //
.map(d =>            // for each direction d:
  p =                //   update the position:
    p.map((v, k) =>  //     for each coordinate v at index k:
      v +            //       add to v
      V[d & 1 ^ k] * //       either V[0] or V[1] according to bit #0
      ~-(d >> k & 2) //       multiplied by either -1 or +1
                     //       according to bit #1 or bit #2
    )                //     end of inner map()
)                    // end of outer map()

```

# Answer
> 4 votes
# Jelly,  ~~23~~  17 bytes

-3 by using  \- I really should know to use this since I actually implemented this atom! \>.\<
-1 altering valid move generation code.
-2 compressing in a way so as not to need valid move construction.

```
;N“©Ȯṅ!ı|⁺⁸’ṃs2+\

```

A monadic Link that accepts the pair `[Y, X]` and yields a list of coordinates.

**Try it online!** Or try it with a formatted output.

### How?

```
;N“©Ȯṅ!ı|⁺⁸’ṃs2+\ - Link: pair of integers, [Y, X] (1 < X < Y)
 N                - negate -> [-Y, -X]
;                 - concatenate -> [-Y, -X, Y, X]
  “©Ȯṅ!ı|⁺⁸’      - base 250 number = 477042125414097387
            ṃ     - (that) base decompress ([-Y, -X, Y, X])
                    -> convert to base 4 using [-Y, -X, Y, X] as digits [1, 2, 3, 0]
             s2   - split into twos
                \ - cumulative reduce by:
               +  -   addition (vectorises)

```

# Answer
> 3 votes
# PARI/GP, 63 bytes

```
t->Vec(((u=conj(s=t/(I-x^2)%y=x^8)+s*y)*x^3-u+t)/(1-x)%y^2+u%x)

```

Attempt This Online!

Takes a complex number (`X+Y*I`) and outputs a list of complex numbers.

Implements the algorithm in @Neil's Charcoal answer using polynomial magics.

```
. . d . 1 . .
. . 0 . c . .
. e . . . 2 b
. . . f . . .
. 6 . . . a 3
. . 8 . 4 . .
7 . 5 . 9 . .

```

---

# PARI/GP, 71 bytes

```
t->s=0;[s+=a|a<-[-v=I*t,t,t,v,v,-t,-u=conj(t),-v,w=I*u,u,u,-w,-w,-u,w]]

```

Attempt This Online!

Gives the same result as above, but the directions are hardcoded.

# Answer
> 3 votes
# Python NumPy, 93 bytes (@alephalpha)

```
lambda p:cumsum(kron([p,-p,*conj([p,-p])],[1,-1,1j,-1j])[-(r_[:14,15]^1)])
from numpy import*

```

Attempt This Online!

### Python NumPy, 96 bytes

```
lambda p:cumsum(kron([p,q:=p-2*p.real,-q,-p],[1,-1,1j,-1j])[-(r_[:14,15]^1)])
from numpy import*

```

Attempt This Online!

Uses complex numbers.

This works essentially by hopping from the trapping square to each of the eight reachable squares and back an then swapping moves 2 and 3, 4 and 5, 6 and 7 (1-based) and so on. Unfortunately not very short.

# Answer
> 2 votes
# APL(Dyalog Unicode), 37 bytes SBCS

```
{-∘⊃⍨{,⍉↑⍵(2+/⍵)}{∊⍵,¨2⌽⌽+⍵}⍵×0j1*⍳4}

```

Try it on APLgolf!

Input a complex number `yJx`.

# Answer
> 0 votes
# 05AB1E, 20 bytes

```
(ì•Ct-V₂‹Sθ•sÅв2ôÅ»+

```

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

Try it online or try it online pretty-printed.

**Explanation:**

```
(            # Negate the values in the (implicit) input-pair: [-Y,-X]
 ì           # Prepend it in front of the (implicit) input-pair: [-Y,-X,Y,X]
  •Ct-V₂‹Sθ• # Push compressed integer 856559820693157436
   s         # Swap so earlier quadruplet is on top again
    Åв       # Convert 856559820693157436 to custom base [-Y,-X,Y,X],
             # which basically converts it to base 4, and indexes into the quadruplet
             # (unlike Jelly, 05AB1E uses 0-based indexing, so [-Y,-X,Y,X] → [0,1,2,3])
      2ô     # Then split this list into pairs
        Å»   # Cumulative left-reduce it, keeping all intermediate results:
          +  #  Add the values at the same positions in the pair together
             # (after which the result is output implicitly)

```

See this 05AB1E tip of mine (section *How to compress large integers?*) to understand why `•Ct-V₂‹Sθ•` is `856559820693157436`.

---
Tags: code-golf, grid
---


# Question
Title: CGAC2022 Day 4: Can Santa fit down the chimney?
Part of **Code Golf Advent Calendar 2022** event. See the linked meta post for details.

---

Christmas is coming up, and Santa hasn't kept to his diet very well this year. Due to his size, he is getting the elves to collect a list of all the chimneys he will be able to fit down. Unfortunately, chimneys these days are a bit of a maze, and he can't just drop straight down like he used to.

**Task:** Given Santas width as an integer and a binary matrix representing the chimney, output whether or not Santa will be able to fit down the chimney.

**Rules**

* Santa is able to "fit" down the chimney if he can enter it at the top and exit at the bottom, while only moving downwards or sideways through the cavity sections of the chimney.
* Santa cannot move up
* Assume Santa's height is always 1
* There will only be one entrance to the chimney, and one exit from the chimney
* The matrix representing the chimney should consist of two values, one for brick (which Santa can't move through) and one for cavities (which Santa can move through). These can be of type `integer`, `string`, `float` or any other type, as long as a distinction can be made between the two.
* The format of the matrix is flexible - any standard subsitution for a matrix (list of strings, list of lists etc) is allowed
* The output can be any valid truthy/falsy output, or two values/states chosen to represent the truthy falsy output (i.e output `1`/`None`, `1`/`Error`)

Standard rules apply. The shortest code in bytes wins.

## Test Cases

**Truthy**

```
Width = 1

Chimney=[
"101",
"101",
"101"
]

```

```
Width = 2

Chimney = [
"110011",
"110011",
"100011",
"100111",
"100001",
"110001",
"111001",
"111001",
]

```

**Falsy**

```
Width = 1

Chimney=[
"101",
"010",
"101"
]

```

```
Width = 2

Chimney = [
"100111"
"100110"
"100110"
"100010"
"111010"
"111010"
"111010"
"111010"
]

```

```
Width = 1

Chimney = [
"0111",
"1110",
"1110",
]

```

```
Width = 1

Chimney = [
"1011111",
"1011111",
"1010001",
"1000101",
"1111101",
"1111101",
"1111101",
"1111101",
]

```

# Answer
> 7 votes
# Vyxal, ~~18~~ 16 bytes

```
vlvṠλĠ~•vA⋎f;RA¬

```

Try it online! or Test suite.

Takes input as width and a matrix of 0's and 1's, in either order.

## Explanation

Since Santa cannot move up the chimney, we can iterate through each chimney's row until we arrive into a result. To check if we can move down then sideways to the 0's: (Assuming width 1)

```
[1 0] [0 1 1] [1] [1] [1] => previous (molded to current)
  0      0     1   1   1  =>   are all of them true?
  OR     OR    OR  OR  OR  (bitwise)
[1 1] [0 0 0] [1] [0] [1] => current
  =      =     =   =   =
[1 1] [0 0 0] [1] [1] [1] => new

```

#### Commented code

```
vl               # cumulative groups (vectorise)
  vṠ             # sum (doubly vectorise)
                 # - this is "any?" as truthy/falsy only matters in this case
             R   # reduce by
    λ       ;    # a lambda taking two elements:
     Ġ           #   group the current consecutively
       •         #   mold the previous
      ~          #   do not pop the items
        vA       #   all? (vectorise)
          ⋎      #   bitwise or (vectorises)
           f     #   flatten
              A¬ # is not all true?

```

# Answer
> 5 votes
# JavaScript (ES7), 105 bytes

Expects `(width)(chimney)`.

```
w=>g=([v,...a],m=2**w-1,c,r='0b1'+v,h=(k,M=m,q=r&M)=>M%1||M>r|c*q?0:g(a,M,1)&!q|h(k,M*k))=>v?h(2)|h(.5):1

```

Try it online!

### Commented

```
w =>              // outer function taking the width w
g = (             // inner recursive function taking:
  [ v,            //   v = next row of the chimney
    ...a          //   a[] = array of remaining rows
  ],              //
  m = 2 ** w - 1, // m = bit mask for Santa
  c,              // c = flag telling if horizontal collisions
                  //     must be taken into account
  r = '0b1' + v,  // r = the row with the binary prefix and an
                  //     extra leading '1'
  h = (           // h = recursive search function taking:
    k,            //   k = direction as a multiplier (2 or 1/2)
    M = m,        //   M = copy of m
    q = r & M     //   q = collision mask of Santa with the chimney
  ) =>            //
  M % 1 ||        //   if Santa is too far to the right
  M > r |         //   or too far to the left
  c * q ?         //   or c is set and there's a collision:
    0             //     abort
  :               //   else:
    g(a, M, 1)    //     do a recursive call to g with the
                  //     collision flag enabled
    & !q          //     ignore the result if q was not 0
    | h(k, M * k) //     do a recursive call to h with M updated
) =>              //
v ?               // if v is defined:
  h(2) |          //   try to move Santa to the left
  h(.5)           //   try to move Santa to the right
:                 // else:
  1               //   success

```

# Answer
> 4 votes
# , 67 47 bytes

```
1 e.[([*&;]<@(##+./);.1~2~:/\_,[)/@|.@E.~0$~1,]

```

Try it online!

-20 based on approach from u-ndefined's answer

## original graph theory approach, 67 bytes

```
*/@(0{+./ .*^:_~)@(1&~:*1>:|)@([:-/~$j./@#:I.@,)@(1,~1,])@E.~1&,$0:

```

Try it online!

Convert to adjacency matrix, transitive closure, check if first row is all ones.

# Answer
> 4 votes
# 05AB1E, 18 bytes

```
Å»γD€gŠr£P~˜}θJÎ×å

```

Port of *@u-ndefined*'s Vyxal answer, so make sure to upvote him/her as well!

Chimney as first input as an integer-matrix, width as second input-integer.

Try it online or verify all test cases.

**Explanation:**

```
Å»           # Cumulative left-reduce the rows of the first (implicit) input-matrix,
             # keeping all intermediate steps (unfortunately)
  γ          #  Split the row into groups of the same adjacent values
   D         #  Duplicate this list of groups of 1s/0s
    €g       #  Pop the copy, and get the length of each group
      Šr     #  Change the stack order from a,b,c, to b,a,c (triple-swap and reverse stack)
        £    #  Split the previous rows into groups of those lengths
         P   #  Get the product of each inner group to check if all are truthy
          ~  #  Bitwise-OR these values with the groups of the current row
           ˜ #  Flatten it for the next iteration
 }θ          # After the cumulative left-reduce with intermediate steps: keep the last result
   J         # Join this list of 0s/1s together to a string
    Î        # Push 0 and the second input-integer
     ×       # Repeat the "0" that many times as string
      å      # Check if it's a substring in the left-reduced result
             # (after which this is output implicitly)

```

# Answer
> 3 votes
# Python3, 274 bytes:

```
V=lambda b,w,X,Y:0<=Y and Y+w<len(b[0])and sum(b[X][Y:Y+w])==0
def f(b,w):
 q,S=[(0,i)for i,a in enumerate(b[0])if V(b,w,0,i)],[]
 while q:
  x,y=q.pop(0)
  if x==len(b)-1:return 1
  for X,Y in[(x,y+1),(x,y-1),(x+1,y)]:
   if V(b,w,X,Y)and(X,Y)not in S:q+=[(X,Y)];S+=[(X,Y)]

```

Try it online!

# Answer
> 3 votes
# Charcoal, 65 bytes

```
Ｎθ≔⪫11Ｓη≔⌕Ａη×0θζＷＳ«≔⪫11ιι≔Φζ¬Σ✂ικ⁺κθ¹ζＦζＦ⁻⟦⊖κ⊕κ⟧ζ¿¬Σ✂ιλ⁺λθ¹⊞ζλ»¬ζ

```

Try it online! Link is to verbose version of code. Takes input as an integer followed by a list of newline-terminated binary strings and outputs a Charcoal boolean, i.e. `-` if Santa sets stuck, nothing if he can drop down. Explanation:

```
Ｎθ

```

Input Santa's width.

```
≔⪫11Ｓη

```

Input the top of the chimney, but ensure that the edges are solid.

```
≔⌕Ａη×0θζ

```

Find all of the places where Santa could start lowering himself down.

```
ＷＳ«

```

Loop through the rest of the chimney.

```
≔⪫11ιι

```

Ensure that the edges are solid.

```
≔Φζ¬Σ✂ικ⁺κθ¹ζ

```

Keep only the positions that are wide enough in the new row.

```
ＦζＦ⁻⟦⊖κ⊕κ⟧ζ

```

Loop through the neighbours of the found positions, without repeating a position.

```
¿¬Σ✂ιλ⁺λθ¹⊞ζλ

```

If Santa can move sideways then add this position.

```
»¬ζ

```

Output whether Santa got stuck.

# Answer
> 3 votes
# APL(Dyalog Unicode), 30 bytes SBCS

```
{0∊↑(∊∨(∧/¨∧⊢)⍤⊂⍨1,2≠/⊣)/↓⍵}∨/

```

Try it on APLgolf!

Input width on the left and a binary matrix representing the chimney on the right.

# Answer
> 2 votes
# Python NumPy, 133 bytes

```
def f(w,A):
 while w>1:A=A[:,1:]|A[:,:-1];w-=1
 p=~A.T@~A
 for a in A:b=p^p;b[range(len(p)),-a.cumsum()]=~a;p=p@b@b.T
 return p.any()

```

Attempt This Online!

# Answer
> 1 votes
# PARI/GP, 101 bytes

```
f(c,w)=a=[1..#c-w--];[while(j=0;b-a=[[s,j&&a[j],j++<#a&&a[j+1]]&&!r[j..j+w]|s<-t],b=a)|r<-c~,t=b=a];a

```

Attempt This Online!

---
Tags: code-golf, decision-problem
---


title: Find the box by its corners

text:
# Question
Title: Find the box by its corners
Given a matrix of integers \\$M\\$ and a list of four integers \\$L\\$, find the sub-matrix \\$N\\$ whose corners are given by \\$L\\$ and return the sum of its elements.

Suppose you're given the list \\$L = \[-8, -3, 2, 9\]\\$ and the following matrix \\$M\\$. The numbers in the list are highlighted in blue to illustrate:

$$ \begin{bmatrix}0 & 2 & -7 & -5 & -6\\ 6 & \boldsymbol{\color{blue}{-3}} & 4 & -2 & \boldsymbol{\color{blue}{9}}\\ -9 & 1 & 8 & -1 & -8\\ 3 & \boldsymbol{\color{blue}{2}} & -4 & 2 & \boldsymbol{\color{blue}{-8}} \end{bmatrix} $$

Your task is to sum the elements in the sub-matrix \\$N\\$ described by those four corners, in other words the sum of all of the blue numbers below:

$$ \begin{bmatrix}0 & 2 & -7 & -5 & -6\\ 6 & \boldsymbol{\color{blue}{-3}} & \color{blue}{4} & \color{blue}{-2} & \boldsymbol{\color{blue}{9}}\\ -9 & \color{blue}{1} & \color{blue}{8} & \color{blue}{-1} & \color{blue}{-8}\\ 3 & \boldsymbol{\color{blue}{2}} & \color{blue}{-4} & \color{blue}{2} & \boldsymbol{\color{blue}{-8}} \end{bmatrix} $$

In this case the sum (by sheer coincidence) is \\$0\\$.

## Input

Input will consist of a matrix \\$M\\$ and a list \\$L\\$ in any convenient format. The matrix may contain duplicate numbers and may even have duplicates of the numbers in \\$L\\$ but there will be only one sub-matrix whose corners are the numbers in \\$L\\$.

The numbers in \\$L\\$ may be in any order and will not necessarily correspond to the order of the corners of \\$N\\$. The numbers in \\$L\\$ might not be unique.

\\$M\\$ will always have at least two rows and two columns. \\$N\\$ will also always be at least \\$2 \times 2\\$.

## Output

The output should be a single integer—the sum of the elements of \\$N\\$—in any convenient format.

## Rules

## Test cases

```
Input:

M =  6  9 -7  3
     8 -1 -6 -4
     2 -7  7 -7
    -1  4  7  9

L = -1  8 -7  2

Output: 2

```

```
Input:

M =  2  5 -7  4 -6
    -4 -2  2  0 -6
     1 -4  5  7  6
     3  2 -7 -6 -4

L =  6 -6  2  5

Output: 14

```

```
Input:

M =  9  6  4  7
     5  0 -3 -2
     8 -4 -7  9

L =  7  8  9  9

Output: 32

```

```
M =  1  2  3
     2  3  2
     3  2  1

L =  1  3  3  1

Output: 19

```

# Answer
> 8 votes
# R 4.1, ~~188 bytes~~ ~~120 bytes~~ 97 bytes

I have wanted to answer a code golf question for a while and this seemed perfect for trying in R. These approaches are both functions which expect a matrix and a vector as arguments.

## v2.1, 97 bytes entirely thanks to Giuseppe

Attempt this online.

```
\(m,l,`+`=sort,`-`=sample){while(!all(+l==+m[i<-nrow(m)-2,j<-ncol(m)-2]))1
sum(m[i:i[2],j:j[2]])}

```

### How?

I can't take any credit for this awesome set of improvements posted in the comments but I will try to explain them - hopefully I will do them justice. The most significant changes seem to be:

1. Replacement of `s=sort,e=sample` with  ``+`=sort,`-`=sample`. It would never have occurred to me to try this and I am amazed and slightly horrified that R allows it, but obviously these operators don't require brackets meaning we can do `nrow(m)-2` rather than `s(nrow(m),2)` (and the same for `ncol`). The backticks in the definition cost 4 bytes but it saves us 3 bytes each time. Total: -2 bytes.
2. Doing the assignment when we subset `m`, allowing us to replace the verbose `{i=e(nrow(m),2);j=e(ncol(m),2);!all(s(l)==s(m[i,j]))}` with `!all(+l==+m[i<-nrow(m)-2,j<-ncol(m)-2])` (which makes my head hurt because `-` now means `sample()`. This is this trick - assigning a variable to the environment while using it in a function (in this case the function being ``[``). -15 bytes.
3. Replacing `m[i[1]:i[2],j[1]:j[2]]` (ugh so many square brackets) with `m[i:i[2],j:j[2]]`. This generates a warning that it will only use the first element (which is what we want), and the output is the same. -6 bytes.

Great improvements which I will try to get my brain to store in the code golf part and not allow to leak into the writing R code for work part... Thanks Gisuseppe :).

## v2.0, 120 bytes

Attempt this online.

```
f=\(m,l,s=sort,e=sample){while({i=e(nrow(m),2);j=e(ncol(m),2);!all(s(l)==s(m[i,j]))})m[i,j]
sum(m[i[1]:i[2],j[1]:j[2]])}

```

### How?

Inspired by Jonah's excellent approach in J, I realised it was unnecessary to start with the apparently reasonable step of subsetting the matrix to those indices which match the input list. This method just randomly picks four corners, checks if when sorted they match the sorted input vector, and if so takes the sum of the "box" bounded by the corners. Once again, highly inefficient and will scale horrendously. But it is shorter than my original approach.

Both answers use the `do-while` loop trick set out by Giuseppe to evaluate `i` and `j` in the loop condition, so we can refer to them in the `while` condition without having to define them both before the loop and in the loop body.

## v1.0, 188 bytes

Attempt this online

```
f=\(m,l){z=arrayInd(which(m%in%l),dim(m))
a=apply
while({i=sample(nrow(z),4);any(colSums((z[i,]*c(1,-1))))|is.list(a(z[i,],2,unique))})0
r=a(z[i,],2,range)
sum(m[r[1,1]:r[2,1],r[1,2]:r[2,2]])
}

```

### How?

This is a highly computationally inefficient approach that does one reasonable thing and then is based on random guessing. Initially, it creates a 2-column matrix of the indices of the values in the input matrix which match the input list.

Then it randomly selects four rows from that matrix (each of which is an `x,y` coordinate) until the following conditions are satisfied:

1. The second two coordinates subtracted from the first two coordinates give (0,0).
2. There are exactly 2 unique x and y values.

This means (as we started with indices which match the input) that we have the bounds of the "box" - at which point we can select the desired values and sum them.

This is my first response to a code golf question ever. I am sure the answer can be improved and am keen for suggestions. Also if I have made a mistake - whether a fatal error of logic or how the input is allowed -- please let me know.

# Answer
> 5 votes
# MATL, ~~53~~ 52 bytes

```
xZyXH:2XN!"@XJxHP:2XN!"&GJ@3$)leSwS=?2GJ@,wX{:]3$)ss

```

Try it online! Or verfy all test cases.

# Answer
> 5 votes
# Brachylog, 20 bytes

```
⟨{szs}{⟨hzt⟩ⁱ²cp}⟩c+

```

Try it online!

Takes a list `[M, L]` through the input variable and yields the box sum through the output variable.

```
    s                   Take a substring of
   z                    a transposed
  s                     substring
⟨{   }{         }⟩      of the matrix, for which
         z              zipping
       ⟨h t⟩            the first element with the last element
            ⁱ²          twice results in a list
              c         which concatenated
               p        is a permutation of L.
                  c+    Concatenate the rows, and sum.

```

# Answer
> 4 votes
# JavaScript (ES6), 152 bytes

Expects `(L)(M)`.

```
L=>M=>(g=(x,y,X,Y)=>M.map((r,j)=>r.map((v,i)=>1/Y?j<y|j>Y|i<x|i>X?0:t+=v:X?[X[x],v,X[i],r[x]].sort()+''==L.sort()&i>x&j>y&&g(x,y,i,j):g(i,j,r))))(t=0)|t

```

Try it online!

### How?

In order to limit the number of `map()` loops, we use just two of them within a recursive function which processes up to 3 passes:

1. We unconditionally consider each cell as a possible top-left corner.
2. We test whether we've found the 4 requested corners.
3. We compute the sum of the sub-matrix.

### Commented

```
L => M =>                 // L[] = corner list, M[] = matrix
( g = (x, y, X, Y) =>     // g is a recursive function
  M.map((r, j) =>         // for each row r[] at position j in M[]:
    r.map((v, i) =>       //   for each value v at position i in r[]:
      1 / Y ?             //     if Y is defined, this is the 3rd pass:
        j < y | j > Y |   //       if j is invalid
        i < x | i > X ?   //       or i is invalid:
          0               //         do nothing
        :                 //       else:
          t += v          //         add v to t
      :                   //     else:
        X ?               //       if X is defined, this is the 2nd pass:
          [ X[x],         //         build a vector
            v,            //         consisting of the 4 corners
            X[i],         //         (note that we have X = M[y])
            r[x]          //
          ].sort()        //         sort this vector
          + ''            //         and coerce it to a string
          == L.sort()     //         if it's equal to L[] (also sorted)
          & i > x & j > y //         and the sub-matrix is at least 2x2,
          &&              //         then:
            g(x, y, i, j) //           process the 3rd pass
        :                 //       else:
          g(i, j, r)      //         it's the 1st pass: process the 2nd one
    )                     //   end of inner map()
  )                       // end of outer map()
)(t = 0)                  // initial call to g(); start with t = 0
| t                       // return t

```

# Answer
> 3 votes
# Python3, 222 Bytes:

```
from itertools import*
S=sorted
R=range
def f(B,e):
 for x,X,y,Y in product(*[R(len(B))]*2,*[R(len(B[0]))]*2):
  if S([B[x][y],B[x][Y],B[X][y],B[X][Y]])==S(e)and x<X and y<Y:return sum(map(sum,[i[y:Y+1]for i in B[x:X+1]]))

```

Try it online!

# Answer
> 3 votes
# , 75 72 71 70 68 66 bytes

```
+/@,@;@((-:&(/:~)"1(;/-#:i.4)&{&>)#])&,[:g@|:&>g=.[:;@,<@(1}.<\)\.

```

Try it online!

This takes all submatrices, filters them based on whether their 4 corners sorted matches the target sorted, and returns the sum.

The two parts that required the most experimentation to golf were:

* `(;/-#:i.4)&{` The phrase to pull the 4 corners from a matrix. It generates the numbers 0 through 3 in binary, negates the ones, and uses those as a 2d index for "take" `{`:
    + `0 0` top left corner
    + `0 _1` top right corner
    + `_1 0` bottom left corner
    + `_1 _1` bottom right corner
* `[:g@|:&>g=.[:;@,<@(1}.<\)\.` The phrase to generate all submatrixes. It has two parts:
    + `<@(1}.<\)\.` First we generate all possible heights for valid full width rectangles. We do this by calculating all prefixes of all suffixes, deleting the first element of each prefix list, because it has dimension 1. `[:;@,` is a technicality required to keep the list flat. Note that we also save this phrase as `g`...
    + `[:g@|:&>` We now reapply `g` to the *transpose* of every result from the first step, generating all the possible widths for each possible height. Together, these step generate all possible widths for every possible height rectangle, accounting for all possible submatrices.

# Answer
> 3 votes
# Python 3, 134 bytes

```
f=lambda m,l,n=4,s=sorted:m*n>[]and[f(m[1:],l)|f([*zip(*m[::-1])],l,n-1),sum(sum(m,()))][s(m[x][y]for x in(0,-1)for y in(0,-1))==s(l)]

```

Try it online!

Recursively removes edges from the matrix until a solution is found.

# Answer
> 2 votes
# Charcoal, 60 bytes

```
ＦＬθＦιＦＬ⌊θＦλ«≔⟦⟧ζＦ⟦ικ⟧Ｆ⟦λμ⟧⊞ζ§§θνξ¿⬤⁺ζη⁼№ζν№ηνＩΣＥ✂θκ⊕ι¹Σ✂νμ⊕λ

```

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

```
ＦＬθＦι

```

Loop over all possible row ranges.

```
ＦＬ⌊θＦλ«

```

Loop over all possible column ranges.

```
≔⟦⟧ζＦ⟦ικ⟧Ｆ⟦λμ⟧⊞ζ§§θνξ

```

Get the corners of the submatrix.

```
¿⬤⁺ζη⁼№ζν№ην

```

If this multiset equals the input list, then...

```
ＩΣＥ✂θκ⊕ι¹Σ✂νμ⊕λ

```

Output the sum of the submatrix.

57 bytes using the newer version of Charcoal on ATO:

```
ＦＬθＦιＦＬ⌊θＦλ«≔ΣＥ⟦ικ⟧Ｅ⟦λμ⟧§§θνπζ¿⬤⁺ζη⁼№ζν№ηνＩΣＥ✂θκ⊕ι¹Σ✂νμ⊕λ

```

Attempt This Online! Link is to verbose version of code. Saves 3 bytes by being able to flatten the nested array obtained when extracting the corners of `N`.

# Answer
> 2 votes
# Jelly, 20 bytes

```
ẆZẆ$€ẎØ.p¤œịœ|ƑɗƇṪFS

```

Try it online!

Dyadic link taking \\$M\\$ on the left and \\$L\\$ on the right.

```
Ẇ                       Get all contiguous sublists of the matrix,
  Ẇ                     get all contiguous sublists of
 Z                      the transpose of
   $€                   each sublist,
     Ẏ                  and concatenate into a single list of submatrices.
               ɗƇ       Filter by:
          œị            Multidimensional-index into the submatrix with
        p               the Cartesian product of
      Ø.                [0, 1]
         ¤              with itself;
              Ƒ         is it unchanged by
            œ|          multiset union with L?
                 Ṫ      Keep only the largest passing submatrix,
                  FS    and flatten and sum it.

```

# Answer
> 2 votes
# 05AB1E, 38 bytes

```
U˜āãε`"€üÿø€üÿ".V}€`€`ʒÁ2£øÁ2£˜{X{Q}˜O

```

Inputs in the order \\$L,M\\$.

Try it online or verify all test cases.

**Explanation:**

```
U             # Pop the first (implicit) input-list and store it in variable `X`
˜             # Flatten the second (implicit) input-matrix
 ā            # Push a list in the range [1,length] (without popping the list)
  ã           # Create all possible pairs of this list with the cartesian product
ε             # Map over each pair:
 `            #  Pop and push them both separated to the stack
  "€üÿø€üÿ"   #  Push this string, where both `ÿ` are filled with the two values
           .V #  Evaluate and execute it as 05AB1E code:
   €          #   Map over each row of the (implicit) input-matrix
    üA        #    Convert it into overlapping lists of size A
      ø       #   Zip/transpose; swapping rows/columns
       €      #   Map over each the list of lists
        üB    #    Convert it into overlapping lists of size B
}             # Close the map
 €`€`         # Flatten two levels down so we have a list of blocks of various sizes
ʒ             # Filter this list of AxB blocks by:
 Á2£øÁ2£      #  Convert the current AxB block to a 2x2 block of its corners:
 Á            #   Rotate the rows once towards the right
  2£          #   Then only keep the first two rows
    ø         #   Zip/transpose; swapping rows/columns
     Á        #   Rotate the list of pairs towards the right again
      2£      #   Keep the first two pair
 ˜            #  Flatten this block of corners
  {           #  Sort it from lowest to highest
   X          #  Push the first input from variable `X`
    {         #  Sort it as well
     Q        #  Check if these two lists are the same
}˜            # After the filter: flatten the only remaining block to a single list
  O           # Sum its values together
              # (after which this sum is output implicitly as result)

```

Some minor notes:

1. `ā` leaves the flattened list on the stack, which will affect the first iteration of the map. But since this is the 1x1 block anyway, it doesn't affect the final result.
2. The `üN` builtin will result in an empty list if `N` exceeds the list's length, so it doesn't matter that `˜ā` will also try to make blocks of 20x20 for a 4x5 input matrix.
3. Because we use `Á2£øÁ2£` to get our 2x2 block of corners from an AxB block, it doesn't matter that there are 1x1 or 3x1 blocks among (which could for example have caused issues for the final test case).

---
Tags: code-golf, matrix
---