# Question
Title: Help me accelerate linear recurrence relation!
## Background

A **linear recurrence relation** is a description of a sequence, defined as one or more initial terms and a linear formula on last \\$k\\$ terms to calculate the next term. (For the sake of simplicity, we only consider *homogeneous* relations, i.e. the ones without a constant term in the formula.)

A formal definition of a linear recurrence relation looks like this, where \\$y\_n\\$ is the desired sequence (1-based, so it is defined over \\$n\ge 1\\$) and \\$x\_i\\$'s and \\$a\_i\\$'s are constants:

$$ y\_n = \begin{cases} x\_n, & 1\le n\le k \\ a\_1y\_{n-1}+a\_2y\_{n-2}+\cdots+a\_ky\_{n-k}, & k\<n \end{cases} $$

In this challenge, we will accelerate this sequence by converting it to a matrix form, so that the \\$n\\$-th term can be found by repeated squaring of the matrix in \\$O(\log n)\\$ steps, followed by inner product with the vector of initial terms.

For example, consider the famous Fibonacci sequence: its recurrence relation is \\$y\_n=y\_{n-1} + y\_{n-2}\\$ with \\$k=2\\$, and let's use the initial values \\$x\_1=x\_2=1\\$. The recurrence relation can be converted to a matrix form:

$$ \begin{bmatrix} y\_{n-1} \\ y\_{n} \end{bmatrix} = \begin{bmatrix} y\_{n-1} \\ y\_{n-1}+y\_{n-2} \end{bmatrix} = \begin{bmatrix} 0 & 1 \\ 1 & 1 \end{bmatrix}\begin{bmatrix} y\_{n-2} \\ y\_{n-1} \end{bmatrix} $$

So multiplying the matrix once advances the sequence by one term. Since this holds for any \\$n\\$, it can be extended all the way until we reach the initial terms:

$$ \begin{bmatrix} y\_{n-1} \\ y\_{n} \end{bmatrix} = \begin{bmatrix} 0 & 1 \\ 1 & 1 \end{bmatrix}\begin{bmatrix} y\_{n-2} \\ y\_{n-1} \end{bmatrix} = \begin{bmatrix} 0 & 1 \\ 1 & 1 \end{bmatrix}^2\begin{bmatrix} y\_{n-3} \\ y\_{n-2} \end{bmatrix} \\ = \cdots = \begin{bmatrix} 0 & 1 \\ 1 & 1 \end{bmatrix}^{n-2}\begin{bmatrix} y\_{1} \\ y\_{2} \end{bmatrix} = \begin{bmatrix} 0 & 1 \\ 1 & 1 \end{bmatrix}^{n-2}\begin{bmatrix} 1 \\ 1 \end{bmatrix} $$

In general, one way to construct such a matrix is the following:

$$ \begin{bmatrix} y\_{n-k+1} \\ y\_{n-k+2} \\ \vdots \\ y\_{n-1} \\ y\_{n} \end{bmatrix} = \begin{bmatrix} 0 & 1 & 0 & \cdots & 0 \\ 0 & 0 & 1 & \cdots & 0 \\ & \vdots & & & \vdots \\ 0 & 0 & 0 & \cdots & 1 \\ a\_k & a\_{k-1} & a\_{k-2} & \cdots & a\_1 \end{bmatrix}\begin{bmatrix} y\_{n-k} \\ y\_{n-k+1} \\ \vdots \\ y\_{n-2} \\ y\_{n-1} \end{bmatrix} $$

Note that, if you reverse the vectors and the matrix in every dimension, the equation still holds, retaining the property of "advancing a term by matmul-ing once". (Actually any permutation will work, given that the rows and columns of the matrix are permuted in the same way.)

## Challenge

Given the list of coefficients \\$a\_1,\cdots,a\_k\\$, construct a matrix that represents the recurrence relation (so that its powers can be used to accelerate the computation of \\$n\\$-th term of the sequence).

You can take the coefficients in reverse order, and you can optionally take the value \\$k\\$ as a separate input. \\$k\\$ (the number of terms) is at least 1.

Standard rules apply. The shortest code in bytes wins.

## Test cases

In all cases, any other matrix that can be formed by permuting rows and columns in the same way is also valid.

```
Input
[1,1]
Output
[[0, 1],
 [1, 1]]

Input
[5]
Output
[[5]]

Input
[3, -1, 19]
Output
[[0,  1,  0],
 [0,  0,  1],
 [19, -1, 3]]
or reversed in both dimensions:
[[3, -1, 19],
 [1, 0,  0],
 [0, 1,  0]]
or cycled once in both dimensions:
[[3, 19, -1],
 [0, 0,  1],
 [1, 0,  0]]
etc.

```

# Answer
# MATL, ~~8~~ 7 bytes

-1 byte thanks to @LuisMendo

```
Xy4LY)i

```

Takes the coefficients in reverse order

Try it online!

## Explanation

```
Xy4LY)i
Xy        : Create an identity matrix of size equal to input
  4LY)    : Remove the first row
      i   : Insert input onto the stack

```
> 8 votes

# Answer
# , 10 8 bytes

Returns the matrix reversed in both dimensions.

```
,}:@=@/:

```

Try it online!

### How it works

```
 ,}:@=@/:   input:             3 _1 19
       /:   indices that sort: 1 0 2
            (just to get k different numbers)
     =@     self-classify:     1 0 0
                               0 1 0
                               0 0 1
  }:@       drop last row:     1 0 0
                               0 1 0
 ,          prepend input:     3 _1 19
                               1  0  0
                               0  1  0

```
> 6 votes

# Answer
# JavaScript (ES6), 36 bytes

```
a=>a.map((_,i)=>i?a.map(_=>+!--i):a)

```

Try it online!

Returns:

$$ \begin{bmatrix} a\_1 & a\_2 & a\_3 & \cdots & a\_{k-1} & a\_k \\ 1 & 0 & 0 & \cdots & 0 & 0 \\ 0 & 1 & 0 & \cdots & 0 & 0 \\ \vdots & \vdots & \vdots & & \vdots & \vdots \\ 0 & 0 & 0 & \cdots & 1 & 0 \end{bmatrix} $$
> 5 votes

# Answer
# Io, 56 bytes

```
method(a,a map(i,v,if(i<1,a,a map(I,v,if(I==i-1,1,0)))))

```

Try it online!

## Explanation

```
method(a,                                              )   // Input an array.
         a map(i,v,                                   )    // Map. i = index, v = value
                   if(i<1,                           )     //     If the indice is 0,
                          a,                               //         Return the inputted list
                            a map(I,v,              )      //     Otherwise, map: (I is the current index)
                                      if(I==i-1,   )       //     If I == i-1,
                                                1,         //         Return 1,
                                                  0        //     Otherwise 0

```
> 2 votes

# Answer
# APL (Dyalog Unicode), 10 bytes

```
⊢⍪¯1↓⍋∘.=⍋

```

Try it online!

Tacit function taking the list of coefficients on the right.

## Explanation

```
⊢⍪¯1↓⍋∘.=⍋
     ⍋   ⍋  ⍝ Grade up to obtain a list of k distinct values
      ∘.=   ⍝ Outer product with operation `equals` (identity matrix)
  ¯1↓       ⍝ Drop the last row
⊢⍪          ⍝ Prepend the list of coefficients

```
> 2 votes

# Answer
# Python 2, 46 bytes

```
lambda l,k:[l]+zip(*[iter(([1]+[0]*k)*~-k)]*k)

```

Try it online!

Takes input as a tuple `l` and number of terms `k`, and outputs with both rows and columns reversed.

The idea is to use the zip/iter trick to create an identity-like matrix by splitting a repeating list into chunks. The is similar to my solution to construct the identity matrix but changed to have one fewer row by changing the inner multiplier `k` to `k-1` (written `~-k`).
> 2 votes

# Answer
# Python 3, ~~60~~ 58 bytes

-2 bytes thanks to @JonathanAllan

```
lambda a,k:[map(i.__eq__,range(k))for i in range(1,k)]+[a]

```

Try it online!

Takes the coefficients in reverse order
> 1 votes

# Answer
# Charcoal, 12 bytes

```
ＩＥθ⎇κＥθ⁼⊖κμθ

```

Try it online! Link is to verbose version of code. Produces the "reversed in both directions" output. Works by replacing the first row of a shifted identity matrix with the input. Explanation:

```
 Ｅθ             Map over input list
   ⎇κ           If this is not the first row then
     Ｅθ         Map over input list
       ⁼⊖κμ     Generate a shifted identity matrix
           θ    Otherwise replace the first row with the input
Ｉ               Cast to string for implicit print

```
> 1 votes

# Answer
# , 34 bytes

```
function(r,k)rbind(diag(k)[-1,],r)

```

Try it online!

Takes the length as well; the TIO link has a `k=length(r)` argument so you can just input the recurrence relation.
> 1 votes

# Answer
# 05AB1E, 7 bytes

```
āDδQ`\)

```

Outputs reversed in both dimensions.

Try it online or verify all test cases.

**Explanation:**

```
ā        # Push a list in the range [1,length] (without popping the implicit input-list)
 D       # Duplicate it
  δ      # Apply double-vectorized:
   Q     # Check if it's equal
         # (this results in an L by L matrix filled with 0s, with a top-left to
         #  bottom-right diagonal of 1s; where `L` is the length of the input-list)
    `    # Pop and push all rows of this matrix separated to the stack
     \   # Discard the last row
      )  # And wrap all list on the stack into a list
         # (after which the matrix is output implicitly as result)

```
> 1 votes

# Answer
# Jelly, 8 bytes

```
W;J⁼þṖ$$

```

A monadic Link accepting a list which yields a list of lists in the reversed rows & columns permutation.

**Try it online!**

### How?

```
W;J⁼þṖ$$ - Link: list A                    e.g. [5,2,5,4]
W        - wrap (A) in a list                   [[5,2,5,4]]
       $ - last two links as a monad - f(A):
  J      -   range of length (A)                [1,2,3,4]
      $  -   last two links as a monad - f(J):
     Ṗ   -     pop                              [1,2,3]
    þ    -     (J) outer product (that) with:
   ⁼     -       equals?                        [[1,0,0,0],[0,1,0,0],[0,0,1,0]]
 ;       - (W) concatenate (that)               [[5,2,5,4],[1,0,0,0],[0,1,0,0],[0,0,1,0]]

```
> 0 votes

# Answer
# C (gcc), ~~90~~ ~~89~~ 80 bytes

Saved 9 bytes thanks to ceilingcat!!!

```
i;j;f(a,k)int*a;{for(i=k;i--;puts(""))for(j=k;j--;)printf("%d ",i?i-1==j:a[j]);}

```

Try it online!

Inputs an array of coefficients (in forward order) along with its length.
Prints a matrix that represents the recurrence relation.
> 0 votes

# Answer
# Google Sheets, 52

Closing Parens discounted.

* Input cells is Row `1`, starting in column `B`.
* `A2` \- `=COUNTA(1:1)`. Rules say that we can take this as input too, so I have discounted this as well. (Our "k")
* `A3` \- `=ArrayFormula(IFERROR(0^MOD(SEQUENCE(A2-1,A2)-1,A2+1)))`

The output matrix starts in `B1`.

## How it works

1. Since this is a spreadsheet, the input cells give us free output too. As long is it's the first row and we end up with a square set of cells, we're good. If this didn't count, we'd have to do this with Column 1 instead to use `TRANSPOSE()` to copy the input. (Because it's smaller than `ArrayFormula()`)
2. Cache the number of columns in A2
3. Generate a **k-1** x **k** matrix using `SEQUENCE`. Values are `MOD` number of columns + 1. (Diagonals are 0, otherwise something else).
4. Since `0^0` is `1` in Sheets, that means this effectively is a Boolean `NOT()` converted to an integer.
5. `IFERROR` handles input size of 1. (Output a Blank)
> 0 votes

# Answer
# Pari/GP, 29 bytes

```
a->matcompanion(x^#a-Pol(a))~

```

Try it online!
> 0 votes

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


title: AoCG2021 Day 3: Say-Look-Say

text:
# Question
Title: AoCG2021 Day 3: Say-Look-Say
Part of **Advent of Code Golf 2021** event. See the linked meta post for details.

Related to AoC2015 Day 10.

*Here's why I'm posting and not Bubbler*

---

The Elves are playing a variation of the game called look-and-say. In plain look-and-say, they take turns making sequences by reading aloud the previous sequence and using that reading as the next sequence. For example, 211 is read as "one two, two ones", which becomes 1221 (1 2, 2 1s).

But this time it's somewhat different. Given a sequence written on a piece of paper, an Elf reads the sequence, and for each chunk of digits, they write the *count* on the *left* side and the *digit* on the *right* side. And the next Elf does the same on the entire sequence of digits!

For example, if the current sequence is `211333`:

```
Original sequence    : 211333
Read 2 (one two)     : 1(211333)2
Read 1 (two ones)    : 21(211333)21
Read 3 (three threes): 321(211333)213

```

So the next sequence would be `321211333213`.

If the Elves start with the single digit of `1`, what will the sequence look like on the paper after `n` turns?

**Input:** The non-negative integer `n`. (Or a positive integer, if you choose to treat `1` as the 1st iteration.)

**Output:** The resulting list of digits. Can be in any acceptable format, such as a list of numbers or a single string. Be sure to handle multi-digit numbers that appear since iteration 7 - if you're returning a list of digits, make sure that these multi-digit numbers have been split into single digit numbers.

The sequence goes on like this:

```
1
111
31111
413111131
114111413111131413131
111111114111312114111413111131413131141413131413131
1111111111111121111111411131211131811111111411131211411141311113141313114141313141313114131214141313141313141413131413131
11111111111111111111111111111111112111111111111121111111411131211131811131113171141111111111111121111111411131211131811111111411131211411141311113141313114141313141313114131214141313141313141413131413131121413121318141312141413131413131414131314131314131214141313141313141413131413131
11111111111111111111111111111111111111111111111111111111111111111111111111111111211111111111111111111111111111111121111111111111211111114111312111318111311131711412111313111311131711313411111111111111111111111111111111112111111111111121111111411131211131811131113171141111111111111121111111411131211131811111111411131211411141311113141313114141313141313114131214141313141313141413131413131121413121318141312141413131413131414131314131314131214141313141313141413131413131121214131213181313171412141312131814131214141313141313141413131413131413121414131314131314141313141313121413121318141312141413131413131414131314131314131214141313141313141413131413131
1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111121111111111111111111111111111111111111111111111111111111111111111111111111111111211111111111111111111111111111111121111111111111211111114111312111318111311131711412111313111311131711313411112111313111311121113131113111317113133180111111111111111111111111111111111111111111111111111111111111111111111111111111112111111111111111111111111111111111211111111111112111111141113121113181113111317114121113131113111317113134111111111111111111111111111111111121111111111111211111114111312111318111311131711411111111111111211111114111312111318111111114111312114111413111131413131141413131413131141312141413131413131414131314131311214131213181413121414131314131314141313141313141312141413131413131414131314131311212141312131813131714121413121318141312141413131413131414131314131314131214141313141313141413131413131214131213181413121414131314131314141313141313141312141413131413131414131314131311212121413121318131317141213131313171313412121413121318131317141214131213181413121414131314131314141313141313141312141413131413131414131314131312141312131814131214141313141313141413131413131413121414131314131314141313141313121214131213181313171412141312131814131214141313141313141413131413131413121414131314131314141313141313121413121318141312141413131413131414131314131314131214141313141313141413131413131

```

Standard rules apply. The shortest code in bytes wins.

# Answer
> 7 votes
# 05AB1E, 9 bytes

```
$FDÅγRŠ)S

```

Outputs as a list of digits (except for \\$n=0\\$ resulting in `1` instead of `[1]`).

Try it online or verify the test cases in the range \\$\[0,10\]\\$.

**Explanation:**

```
$          # Push 1 and the input-integer
 F         # Pop and loop the input amount of times:
  D        #  Duplicate the current list (or 1 in the first iteration)
   Åγ      #  Pop and run-length encode it, pushing the list of digits and list
           #  of lengths separately to the stack
     R     #  Reverse the list of lengths at the top
      Š    #  Triple-swap the stack: a,b,c to c,a,b
       )   #  Wrap all three values into a list
        S  #  And convert it to a flattened list of digits
           # (after the loop, the result is output implicitly)

```

# Answer
> 5 votes
# JavaScript (ES6),  ~~67~~  62 bytes

*Saved 3 bytes thanks to @MarcMush*

0-indexed.

```
f=n=>s=n?f(n-1).replace(/(.)\1*/g,q=>s=q.length+s+q[0])&&s:"1"

```

Try it online!

# Answer
> 5 votes
# Jelly, 12 bytes

```
1ŒrUj@ƒƊDFƊ¡

```

Try it online!

Fixed thanks to pxeger

```
1         Ɗ¡    Repeatedly apply the given number of times, starting from 1:
 Œr             Encode as a list of [digit, run length] pairs,
   U            reverse each pair,
    j@ƒƊ        join each of them around the original value in sequence,
        D       decompose the elements of their results into digits,
         F      and flatten them.

```

# Answer
> 5 votes
# Rust (1.53+), 124 bytes

```
|s:&str|{let(mut r,mut x)=(s.into(),0);s.chars().chain([' ']).reduce(|a,b|{x+=1;if a!=b{r=format!("{}{}{}",x,r,a);x=0}b});r}

```

Try it online!

This only works on Rust 1.53 and newer as older Rust versions did not implement `IntoIterator` for arrays, but only for array references. This can be fixed by adding a single `&` to `[' ']`, in which case this might run on 1.51+ since that's when `reduce` was stabilized.

In the future if `group_by` is stabilized, this can go down to 96 bytes.

# Answer
> 4 votes
# Retina, 49 bytes

```
K`1
"$+"{`$
¶$`¶$`
2%`(.)\1*
$1
0%^`(.)\1*
$.&
¶

```

Try it online! No test suite due to the way the program uses history. Explanation:

```
K`1

```

Replace the input with `1`.

```
"$+"{`

```

Repeat the originally input number of times.

```
$
¶$`¶$`

```

Triplicate the current string.

```
2%`

```

Only in the third copy...

```
(.)\1*
$1

```

... remove all adjacent duplicates.

```
0%`

```

Only in the first copy...

```
^`

```

... reversing the list results before reinserting them...

```
(.)\1*
$.&

```

... count the runs of repeated digits.

Join everything together.

# Answer
> 4 votes
# Wolfram Language (Mathematica), ~~65~~ 55 bytes

```
Nest[Join[Length/@Reverse[s=Split@#],#,#&@@@s]&,{1},#]&

```

Try it online!

-10 bytes from @att

# Answer
> 3 votes
# BQN, 43 bytes

```
{({∾•Fmt¨(≠¨∘⌽∾∾⊑¨)⊔˜+`»≠«}-⟜'0')⍟"1"}

```

Try It!

does some heavy lifting here.

# Answer
> 3 votes
# Python 3.8 (pre-release), 113 bytes

```
g=lambda c,o,r:r and g(1+c-c*(b:=r[1:2]!=r[0]),b*str(c)+o+r[:b],r[1:])or o
f=lambda n:n and g(1,*2*[f(n-1)])or'1'

```

Try it online!

Very loosely based on @tsh's answer.

# Answer
> 3 votes
# Ruby, 55 bytes

```
->n{a=?1;n.times{a.scan(/(.)\1*/){a=[$&.size,$1]*a}};a}

```

Try it online!

# Answer
> 3 votes
# APL (Dyalog Unicode), ~~32~~ 29 bytes

Thanks to Razetime for -3 bytes!

```
{∊⍕¨(≢¨∘⌽,⍵,⊃¨)⍵⊂⍨1,2≠/⍵}⍣⎕⍕1

```

Try it online!

`{ ... }⍣⎕⍕1`: Starting with `'1'`, iterate the function input times.

`1,2≠/⍵`: Binary vector with 1's at the start of runs of equal items.
`⍵⊂⍨`: Using that boolean mask split the current value into chunks.
`( ... )`: Apply inner function to the nested list: `≢¨∘⌽`: The lengths of each run, reversed, : the current value, `⊃¨`: and the first value in each run.
`⍕¨`: Format each value as a string.
: Join into a single string.

# Answer
> 2 votes
# Jelly, 15 bytes

```
1ŒrZṚU1¦$jƲDFƊ¡

```

Try It Online!

fixed for +3 bytes thanks to Unrelated String, and I can't be bothered to golf or re-explain it anymore

# Answer
> 2 votes
# Pari/GP, 89 bytes

```
f(n)=if(n,s=f(n-1);c=k=0;[if(c==d,k++,k&&s=Str(k,s,c);c=d;k=1)|d<-Vec(s)];Str(k,s,c),"1")

```

Try it online!

# Answer
> 2 votes
# Python 2, 124 bytes

```
g=lambda s,c,t,l=0:t and(t[0]==s[:1]and g(s[1:],c,t,l+1)or g(s,`l`+c+t[0],s))or c
f=lambda n,s='1':n and f(n-1,g(s,s,s))or s

```

Try it online!

# Answer
> 2 votes
# TypeScript Types, ~~302~~ 271 bytes

```
//@ts-ignore
type I<S,D,T=S,N=[0]>=S extends `${D}${infer S}`?I<S,D,T,[...N,0]>:S extends`${infer C}${infer S}`?I<S,C,`${N["length"]}${T}${D}`>:`${N["length"]}${T}${D}`;type M<N,C=[],S="1">=N extends C["length"]?S:S extends `${infer A}${infer B}`?M<N,[...C,0],I<B,A,S>>:0

```

Try it online!

# Ungolfed / Explanation

```
type Iterate<
  Str, // the remainder of the string
  Char, // the current char being counted
  Out = Str, // the output string being worked on
  Count = [0], // the current count of the characterChar
> =
  Str extends `${Char}${infer Rest}`
    // If Str starts with Char, add one to Count and continue
    ? Iterate<Rest, Char, Out, [...Count,0]>
    : Str extends`${infer NewChar}${infer Rest}`
          // Otherwise, if Str is non-empty, add Count and Char to Out, reset Count, and continue
      ? Iterate<Rest, NewChar, `${Count["length"]}${Out}${Char}`>
      // Otherwise, add Count and Char to Out and return it
      :`${Count["length"]}${Out}${Char}`

type Main<
  N, // the inputted number
  Counter = [], // how many times the string has been operated on
  Str = "1", // the current string
> =
  N extends Counter["length"]
    // If N == Counter, return Str
    ? Str
    // Otherwise, iterate on Str
    : Str extends `${infer FirstChar}${infer Tail}` ? Main<N, [...Counter,0], Iterate<Tail, FirstChar, Str>> : never

```

# Answer
> 2 votes
# Pip, 24 bytes

```
LaLR`(.)\1*`ooPU#$0PB$1o

```

0-indexed. Try it online!

### Explanation

```
LaLR`(.)\1*`ooPU#$0PB$1o
                          a is command-line arg; o is 1 (implicit)
La                        Loop a times:
  LR`      `               Loop over each regex match of
     (.)                    a character
        \1*                 followed by the same character 0 or more times
            o              in o:
             oPU            Push to the front of o
                #$0         the number of characters in the match
                   PB       and push to the back of o
                     $1     the first character in the match
                       o  After the loop, output the final value of o

```

# Answer
> 1 votes
# Jelly, 15 bytes

```
ŒrZU2¦ṚżWDF
1Ç¡
```

Attempt This Online!

Explanation:

```
ŒrZU2¦ṚżWDF  inner link

Œr           run-length encode (list of pairs of [element, frequency])
  Z          zip (produces [[list of elements], [list of corresponding frequencies]])
   U2¦       reverse the second element
      Ṛ      flat-reverse (changes to [list of corresponding frequencies], [list of elements])
       żW    interleave with the input, producing [[[elements], [input]], [frequencies]]
                NB: due to a bit of a quirk with Jelly's interleave function and vectorisation,
                    this makes [[a, b], c] not [a, b, c] as one would expect
         D   get digits of each item (in case an item has >=10 consecutive occurrences)
          F  flatten (smooths out both the oddity with interleave, and flattens the lists of digits)

1Ç¡          main link

1            starting with 1,
  ¡          repeatedly apply
 Ç           the above link

```

A naïve translation of the question description

# Answer
> 1 votes
# Python3, 162 bytes:

```
from itertools import*
lambda n,c=['1']:c if n<2 else f(n-1,c+[''.join((k:=[*zip(*[(a,str(len([*b])))for a,b in groupby(c[-1])])])[1][::-1])+c[-1]+''.join(k[0])])

```

Try it online

# Answer
> 1 votes
# Charcoal, 47 bytes

```
≔1ηＦＮ«≔⟦⟧υＵＭη⊞Ｏυ⎇∧λ⁼κ§η⊖λ⁺⊟υκκ≔⁺⁺⭆⮌υＬκη⭆υ§κ⁰η»η

```

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

```
≔1η

```

Start with the string `1`.

```
ＦＮ«

```

Repeat `n` times.

```
≔⟦⟧υ

```

Start collecting runs of digits.

```
ＵＭη⊞Ｏυ⎇∧λ⁼κ§η⊖λ⁺⊟υκκ

```

For each digit, push a new run if the digit differs but concatenate it to the last run if it's the same.

```
≔⁺⁺⭆⮌υＬκη⭆υ§κ⁰η

```

Get the run lengths in reverse order, concatenate that with the previous string, and finally append just the digits without repeats.

```
»η

```

Output the final string.

# Answer
> 1 votes
# , ~~91~~ 90 bytes

Or **\>=4.1, 83 bytes** by replacing the word `function` with `\`.

```
function(n,s=49){while(n<-n-1)s=c(unlist(Map(utf8ToInt,c(rev((r=rle(s))$l),""))),s,r$v);s}

```

Try it online!

Outputs a vector of character codes for the digits. Add 3 bytes (`-48` at the end) for vector of digits.

See also @Dominic van Essen's (shorter) solution.

# Answer
> 1 votes
# , ~~88~~ ~~87~~ 83 bytes

*Edit: thanks to pajonk for bug-spotting and then for -4 bytes!*

```
g=function(n,x="1")`if`(n,g(n-1,unlist(strsplit(c(rev((y=rle(x))$l),x,y$v),""))),x)

```

Try it online!

Recursive + character-based alternative to pajonk's iterative R approach using ASCII codes.

Each recursive call gets the lengths & values of the run-length encoding (`rle`), splits any multi-digit lengths into individual characters (`unlist(strsplit(...,""))`), before wrapping these around the last previous iteration.

# Answer
> 1 votes
# Burlesque, 19 bytes

```
1{XXf:([-)scFLim}C~

```

Try it online!

```
1        # Needed by C~
{
 XX      # Explode to digits
 f:      # Count frequencies
 ([-)sc  # Sort by comparing the digit (tail)
 FLim    # Flatten and implode back to number
}C~      # Continue forever

```

# Answer
> 1 votes
# Julia 1.0, 73 bytes

```
!n=n<2 ? "1" : (s=!~-n;replace(s,r"(.)\1*"=>m->s="$(length(m))$s"m[1]);s)

```

Try it online!

Similar to Arnauld's JS answer

# Answer
> 0 votes
# Japt, 22 bytes

```
_+ó¥ ÕÎ iZó¥ cÊ¬w}g'1q

```

Try it

```
_...}g'1q  - run f(Z) input times starting with ["1"]

+     - append to Z:
ó¥ ÕÎ   * first column of Z splitted on different char
i     - then prepend:
Zó¥ cÊ¬w * lengths reversed

```

---
Tags: code-golf, sequence
---


# Question
Title: Tips for golfing with numpy, scipy, or pylab
There's already a comprehensive list of tips for python here, so what I'm asking for are tips that specifically apply to using the `numpy`, `scipy` or `pylab` libraries.

These can be either ways to shorten code already using `numpy`, or ways to shorten common python operations by using these libraries.

One tip per answer, please.

# Answer
> 8 votes
# Make use of Numpy's broadcasting

Broadcasting means replicating a multidimensional array along some of its singleton dimensions to match the size of another array. This happens automatically for Numpy arrays when arithmetic operators are applied to them.

For example, to generate a 10×10 multiplication table you can use

```
import numpy
t=numpy.arange(1,11)
print(t*t[:,None]) # Or replace t[:,None] by [*zip(t)]

```

Try it online!

Here `t` is created as the Numpy array `[1, 2, ..., 10]`. This has shape (10,), which is equivalent to (1,10). The other operand array, `t[:,None]`, has size (10,1). Multiplying the two arrays implicitly replicates them, so they behave as if they both had shape (10,10). The result, which also has shape (10,10), contains the products for all pairs of entries in the original arrays.

# Answer
> 6 votes
# Use r\_\[...\] instead of range(...)

Numpy provides matlab like syntax for array creation using `r_[...]`. Any slice notation in between the brackets is interpreted as an array with the range indicated. So, for instance

```
r_[:30:4]

```

is equivalent to

```
arange(0,30,4)

```

and for most uses can replace

```
range(0,30 4)

```

It can also handle more complex expressions. For example to get indices from 0 up to 10 and back down again,

```
r_[:10,10:-1:-1]

```

# Answer
> 4 votes
# The shorter than shortest infinite for comprehension

If numpy is \*-imported then using this "feature" of `numpy.r_`/`numpy.c_` an infinte counter is as cheap as:

```
for[i]in r_:print(i)

```

This is significantly shorter than this pure Python trick and has the added benefit of actually creating a proper counter.

This can also be used for a cheaper `enumerate`:

```
S="abcde"
for x,[i]in zip(S,r_):print(i,x)

```

If you can live with a "boxed" counter, i.e. \[0\],\[1\],\[2\],... rather than 0,1,2,... then you can save the brackets around `i`.

The boxes can even be useful: For example, if we have set up a loop anyway, then we can as a byproduct create a reversed "range" of the same length as the looped over sequence S:

```
C=[]
for e,C[:0]in zip(S,r_):f(e)

```

If for some reason you need double boxes \[\[0\]\],\[\[1\]\],\[\[2\]\],... use `c_` instead of `r_`.

# Answer
> 3 votes
# Don't forget the matrix class

It may be aesthetically challenged and semi-deprecated since all but forever but it can be useful for golfing.

Here is an example How to solve the LCM in 50 bytes of Python where on a non numpy specific challenge it allows us to outgolf @dingledooper's extremely clever pure Python approach by ~10%. And that's counting the numpy import and without requiring us to be particularly smart:

```
from numpy import*
print(lcm(*mat(input()).A1))

```

Try it online!

This shows off three useful features:

1. Short constructor name `mat` although not as short as `r_` or `c_`
2. Hilariously graceful input parser. For example, it will accept

```
mat("""[1 2]\t[3,4];5  6 7
8""")

```

without complaint.

3. a handful of very short-named attributes, viz. `A,A1,T,H,I` which are the underlying array object,the same flattened,the transpose,the conjugate transpose and the pseudo inverse.

Finally, there is one more useful feature that we didn't use in the example:

4. Overloaded `*` operator. That in itself doesn't gain us much over the `@` operator for standard numpy arrays but for example taking the matrix power can be done using `**` much shorter than `linalg.matrix_power`.

---
Tags: code-golf, tips, python
---


title: Are these the basis vectors?

text:
# Question
Title: Are these the basis vectors?
A basis of a vector space \\$V\\$ is a set of vectors \\$B\\$ such that every vector \\$\vec v \in V\\$ can be uniquely written as a linear combination of the vectors in \\$B\\$. In other words, let \\$B = \\{\vec b\_1, \dots, \vec b\_n\\}\\$ be a basis of some vector space \\$V\\$. For every possible \\$\vec v \in V\\$, we can say that

$$\vec v = \lambda\_1 \vec b\_1 + \lambda\_2 \vec b\_2 + \cdots + \lambda\_n \vec b\_n$$

for some **unique** real numbers \\$\lambda\_1, \lambda\_2, \dots, \lambda\_n\\$. Note that this requires the vectors in \\$B\\$ to be linearly independent (i.e., you cannot write a vector in \\$B\\$ as a linear combination of other vectors in \\$B\\$).

For example, let \\$V = \mathbb R^2\\$ i.e. the set of all 2 dimensional vectors. We can see that \\$B = \left\\{ \begin{pmatrix} 1 \\ 0 \end{pmatrix}, \begin{pmatrix} 0 \\ 1 \end{pmatrix} \right\\}\\$ is a basis of \\$V\\$, as any 2 dimensional vector \\$\vec v = \begin{pmatrix} x \\ y \end{pmatrix}\\$ can be written as

$$\vec v = \begin{pmatrix} x \\ y \end{pmatrix} = \begin{pmatrix} 1 \\ 0 \end{pmatrix}x + \begin{pmatrix} 0 \\ 1 \end{pmatrix}y$$

Furthermore, examine \\$B = \left\\{ \begin{pmatrix} 1 \\ 1 \end{pmatrix}, \begin{pmatrix} -1 \\ 2 \end{pmatrix} \right\\}\\$. As the two vectors are linearly independent, they must form a basis of \\$\mathbb R^2\\$, and so we can write any 2-dimensional vector as a combination of the two. For example,

$$\begin{pmatrix} 2 \\ -10 \end{pmatrix} = -2\begin{pmatrix} 1 \\ 1 \end{pmatrix} + -4\begin{pmatrix} -1 \\ 2 \end{pmatrix}$$

However, note that if we have \\$B = \left\\{ \begin{pmatrix} 1 \\ 0 \\ 1 \end{pmatrix}, \begin{pmatrix} 0 \\ 1 \\ 2 \end{pmatrix} \right\\}\\$, then this does not form a basis for all 3 dimensional vectors. There exists no such \\$\lambda\_1, \lambda\_2\\$ such that

$$\begin{pmatrix} 4 \\ 6 \\ 10 \end{pmatrix} = \begin{pmatrix} 1 \\ 0 \\ 1 \end{pmatrix}\lambda\_1 + \begin{pmatrix} 0 \\ 1 \\ 2 \end{pmatrix}\lambda\_2$$

and so \\$B\\$ is not a basis for \\$\begin{pmatrix} 4 \\ 6 \\ 10 \end{pmatrix}\\$.

---

You are to take a vector \\$\vec v \in \mathbb Z^m\\$ of \\$m\\$ integers, and a list of \\$n\\$ vectors \\$B = \\{\vec b\_1, \dots, \vec b\_n\\}\\$. You should then output two distinct consistent values to indicate whether or not \\$B\\$ forms a basis for \\$\vec v\\$ (more precisely, whether \\$B\\$ forms a basis for some space containing \\$\vec v\\$). That is, whether or not there exists a unique set of numbers \\$\lambda\_1, \lambda\_2, \dots, \lambda\_n\\$ such that

$$\vec v = \lambda\_1 \vec b\_1 + \lambda\_2 \vec b\_2 + \cdots + \lambda\_n \vec b\_n$$

You may assume that \\$\vec b\_i \in \mathbb Z^m\\$ for all vectors \\$b\_i \in B\\$ \- that is, they all have the same number of elements as \\$\vec v\\$, and they are all integer vectors.

You may take the inputs in any reasonable, convenient format and method, including a list of lists of \\$B\\$, or a list of numbers for \\$\vec v\\$ etc. The output may be any two distinct, consistent values to indicate whether or not \\$B\\$ is a basis. You may freely choose these values.

This is , so the shortest code in bytes wins

## Test cases

```
B
v
Output (λ1, λ2, ..., λn or reason)

[[8, 1, 2], [-7, -8, -9], [-1, 9, -5]]
[12, 36, -4]
True (1, -1, 3)

[[-9, -3]]
[3, 1]
True (-1/3)

[[1, 0, 1], [0, 1, 2]]
[1, -1, -1]
True (1, -1)

[[1, 0, 1], [0, 1, 2]]
[4, 6, 10]
False (shown above)

[[7, -2], [-10, -6], [-4, 9]]
[1, -21]
False (too many unknowns, an infinite number of solutions exist)

[[-1, 8, 1, 6, 3], [8, -6, -5, -10, 6], [-8, -3, -3, -4, 5], [-6, -6, 0, 3, 9], [2, 2, 0, -1, -3]]
[1, 1, 1, 1, 1]
False ([-6, -6, 0, 3, 9] and [2, 2, 0, -1, -3] are linearly dependent, so any way of writing the sum is not unique)

```

# Answer
# Octave, ~~43~~ ~~41~~ 39 bytes

```
@(B,v)(r=rank(B))-rows(B)|r-rank([B;v])

```

Anonymous function that inputs the set of vectors as a matrix **B** with each vector in a row, and **v** as a row vector. The output is `true` (displayed as `1`) if `B` is not a basis for `v`, and `false` (displayed as `0`) if it is.

Try it online!

### How it works

The set of vectors defined by the rows of **B** is a basis for **v** if and only if the rank of the matrix **B** equals its number of rows (i.e. the rows of **B** are linearly independent) *and* the rank of the extended matrix with `v` as last row is the same (i.e. **v** is in the linear span of the rows of **B**).

To save bytes, the code checks if *either* of those conditions is *not* satisfied; that is, if the rank of **B** minus its number of rows is nonzero *or* if the rank of **B** minus that of the extended matrix is nonzero.
> 14 votes

# Answer
# JavaScript (ES6), 218 bytes

Expects `(matrix)(vector)`. Returns \\$0\\$ or \\$1\\$.

```
m=>v=>!(g=m=>m.reduce(o=>m.some((r,y)=>r.some((_,x)=>m[y+w]&&(D=m=>+m||m.reduce((s,[v],i)=>v*D(m.map(([,...r])=>r).filter(_=>i--))-s,0))(m.slice(y,y-~w).map(r=>r.slice(x,x-~w)))/r[x+w]))*++w||o,w=0)-w)(m)&!~g([...m,v])

```

Try it online!

### How?

The method is the same as the one used by Luis.

To compute the rank of a matrix, we look for the largest sub-matrix of size \\$n\times n\\$ whose determinant is not equal to \\$0\\$. This is most probably not the shortest way of doing it.
> 3 votes

# Answer
# JavaScript (Node.js), 93 bytes

```
f=B=>1/B[0][p=B.find(t=>t[0]),1]?!!p&&f(B.map(q=>q.map((v,i)=>v*p[0]-q[0]*p[i]).slice(1))):!p

```

Try it online!

For testcase `[[8, 1, 2], [-7, -8, -9], [-1, 9, -5]], [12, 36, -4]` it input as `f([[8, -7, -1, 12], [1, -8, 9, 36], [2, -9, -5, -4]])`. Extra 47 bytes may be needed if we have to input as matrix B and vector V as two parameters.

This function simply reduce the array using Gaussian elimination.
> 3 votes

# Answer
# Pari/GP, 46 bytes

```
f(a,b)=#a==matrank(a)&&#matintersect(a,Mat(b))

```

Try it online!

Takes a matrix and a column vector as input.
> 2 votes

# Answer
# Wolfram Mathematica, ~~51~~ 41 bytes

```
Tr[1^#]&@@Solve[i=0;s@++i&/@#.#==#2]===i&

```

-10 (!) bytes due to @att

Try it online!
> 2 votes

# Answer
# , 61 bytes

Or **\>=4.1, 54 bytes** by replacing the word `function` with `\`.

```
function(B,v,`+`=Matrix::rankMatrix)+B-nrow(B)|+rbind(B,v)-+B

```

Try it online!

Port of Luis Mendo's answer.
> 2 votes

# Answer
# Charcoal, 43 bytes

```
⊞θηＷ∧θ⌈Φ§θ⁰κ≔ＥΦθλＥκ⁻×μι×§§θ⁰ν§κ⌕§θ⁰ιθ⁼θ⟦Ｅη⁰

```

Try it online! Link is to verbose version of code. Explanation: Port of @tsh's JavaScript answer.

```
⊞θη

```

Append the vector to the basis.

```
Ｗ∧θ⌈Φ§θ⁰κ

```

Repeat until the basis becomes degenerate...

```
≔ＥΦθλＥκ⁻×μι×§§θ⁰ν§κ⌕§θ⁰ιθ

```

... perform Gaussian elimination on the basis, dropping the first row.

```
⁼θ⟦Ｅη⁰

```

Check whether the result is a zero vector.
> 1 votes

---
Tags: code-golf, math, decision-problem, linear-algebra
---


# Question
Title: AoCG2021 Day 1: Automated delivery frenzy
Originally from caird coinheringaahing's idea, I (Bubbler) am hosting **Advent of Code Golf 2021**.

On each day from today (Dec 1) until Christmas (Dec 25), a challenge will be posted at UTC midnight, just like an Advent calendar. It is a free-for-all and just-have-fun-by-participation event, no leaderboards and no prizes for solving them fast or solving them in the shortest code. More details can be found in the link above.

For this year's event, the challenge ideas were drawn from the previous AoC events (2015 - 2020).

---

The story continues from AoC2015 Day 3, Part 2.

---

Santa is delivering presents to an infinite two-dimensional grid of houses. He begins by delivering a present to the house at the starting location, and then follows the commands written as a sequence of moves `^>v<` (moving to the neighboring house to the north, east, south, or west respectively), delivering a present at the house after each move.

Next year, Santa brings up a Robo-Santa for faster delivery. Santa and Robo-Santa start at the same location (giving two presents to the same house), and take turns to move based on the commands.

Assume the command is `^v^v^v^v^v`. Santa alone would deliver a bunch of presents to only two houses (the start and its north neighbor), but with a Robo-Santa, they would deliver presents to 11 different houses (Santa moving north 5 times and Robo-Santa moving south 5 times).

Now Santa wonders: Given a sequence of instructions, how many Santas (Santa and any Robo-Santas) are needed to deliver presents to the maximum number of houses? If two or more Robo-Santas are present, Santa and the Robo-Santas will take turns cyclically to follow the commands, everyone stopping when the commands run out (the number of commands does not have to be divisible by the number of Santas). If multiple options are available, choose the smallest number of Robo-Santas (it takes time and money to build them).

**Input:** A nonempty string of `^>v<` instructions.

**Output:** The minimum number of Santas in total for maximum delivery.

Standard rules apply. The shortest code in bytes wins.

## Test cases

```
>>>>> -> 1
(everyone moving to the same house is surely a loss)
^v^v^v^v^v -> 2
(one additional Robo-Santa will deliver to 11 different houses, the possible maximum)
v>^>v<^< -> 5
(5 Santas will deliver to 7 distinct houses;
 1, 3, 4, or 7 Santas will deliver to 6 distinct houses
 and other choices to fewer houses)
vv>^<^^<v> -> 1
(Any of 1, 4, 6, or 7 Santas will deliver to 8 distinct houses,
 but 1 is the best choice out of them)

```

# Answer
# TypeScript Types, 670 bytes

```
// @ts-ignore
type c<T,A=[]>=(((T extends T?(t:0)=>T:0)extends infer U?(U extends U?(u:U)=>0:0)extends(v:infer V)=>0?V:0:0)extends(_:0)=>infer W?c<Exclude<T,W>,[...A,0]>:A);type i<T>=T extends[0,infer X]?X:[1,T];type d<T>=T extends[1,infer X]?X:[0,T];type m<P,C>={"^":[i<P[0]>,P[1]],v:[d<P[0]>,P[1]],"<":[P[0],i<P[1]>],">":[P[0],d<P[1]>]}[C];type n<P,C>=[P[0]|m<P[1],C>,m<P[1],C>];type s<S,I>=I extends`${infer C}${infer I}`?S extends[infer A,...infer B]?s<[...B,n<A,C>],I>:0:c<S[number][0]>;type q=[[[],[]],[[],[]]];type M<S,K=S,B=[],BN=[],N=[q]>=K extends`${infer _}${infer K}`?B extends[...s<N,S>,...infer _]?M<S,K,B,BN,[...N,q]>:M<S,K,s<N,S>,N,[...N,q]>:BN["length"]

```

Try it online!
> 11 votes

# Answer
# Pari/GP, 89 bytes

```
s->vecsort([-#Set(Vec(Ser([I^c|c<-Vec(Vecsmall(s))%11])/(1-x^i),#s+1))|i<-[1..#s]],,1)[1]

```

Try it online!

The ASCII codes of `<^>v` are`[60, 94, 62, 118]`, which become `[5, 6, 7, 8]` when modulus 11.

After that, it is the usual power series tricks:

$$(a\_0+a\_1x+\cdots)/(1-x^k)=a\_0+a\_1x+\cdots+(a\_0+a\_k)x^k+(a\_1+a\_{k+1})x^{k+1}+\cdots$$
> 7 votes

# Answer
# Rust, 239 234 bytes

```
|i|{let mut r=vec![];for l in 1..i.len(){let(mut s,mut v)=(vec![0;l*2],vec![(0,0)]);for c in i.bytes(){s[c as usize%3&1]+=1-(c as i64%5&2);v.push((s[0],s[1]));s.rotate_left(2);}v.sort();v.dedup();r.push((!v.len(),l));}r.sort();r[0].1}

```

Try it online!

Ungolfed:

```
    |i| {
        let mut r = vec![];
        for l in 1..i.len() {
            let (mut s, mut v) = (vec![0; l * 2], vec![(0, 0)]);
            for c in i.bytes() {
                s[c as usize % 3 & 1] += // %3 - bit 1 flips, s[0] or s[1]
                    1 - (c as i64 % 5 & 2); // %5 - bit 2 flips, 0 or 2
                v.push((s[0], s[1]));
                s.rotate_left(2);
            }
            v.sort();
            v.dedup();
            r.push((!v.len(), l)); // dirty negation to reverse tuple sort order
        }
        r.sort();
        r[0].1
    };

```

History:

* -5 by removing the type annotation for `i` (thanks @Aiden4)
> 6 votes

# Answer
# Charcoal, 43 bytes

```
ＦＬθ«Ｆ⊕ι«Ｊ⁰¦⁰Ｆ✂θκＬθ⊕ι✳⊗⌕^>vλ¹*»⊞υＬＫＡ⎚»Ｉ⊕⌕υ⌈υ

```

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

```
ＦＬθ«

```

Loop over the length of the string, representing the number of Robo-Santas.

```
Ｆ⊕ι«

```

Loop over Santa and his Robo-Santas.

```
Ｊ⁰¦⁰Ｆ✂θκＬθ⊕ι✳⊗⌕^>vλ¹*

```

Draw the route this (Robo-)Santa takes, starting at the origin. (Would be -5 bytes for input in `urdl` format. Interestingly giving PolygonHollow its preferred `urdl` format would be 39 bytes, so slightly longer.)

```
»⊞υＬＫＡ

```

Save the count of all visited houses.

Clear the canvas ready for the next possible number of Robo-Santas or to output the result.

```
»Ｉ⊕⌕υ⌈υ

```

Find how many Robo-Santas are needed for the maximum possible count and add one for Santa himself.
> 4 votes

# Answer
# Python 3.8 (pre-release), 111 bytes

```
lambda s:(L:=range(len(s)))[-max((len({0}|{sum(1j**(ord(d)%11)for d in s[j::~i])for j in L}),~i)for i in L)[1]]

```

Try it online!

Use `%11` trick from alephalpha's answer.
> 4 votes

# Answer
# APL (Dyalog Unicode), 39 bytes

```
⊃⍒{≢∪0,∊+⍀n ⍵⍴y↑⍨n×⍵}¨⍳n←≢y←0J1*'^<v'⍳⍞

```

Try it online!

`y←0J1*'^<v'⍳⍞`: Take character input and map the characters to complex numbers, storing the resulting vector in j.

```
 < >   ^    v
¯1 1 0J1 0J¯1

```

`⍳n←≢y`: Store the length of y in n and create a range from 1 to n (possible number of Santas)
`{ ... }¨`: For each number of Santas evaluate the a function which returns the number of houses visited.
`⊃⍒`: The first index of the maximal value. (Indices that would sort the vector descendingly; take the first one)

For the inner function  is the number of Santas to test and the other variables are still accessible.
`y↑⍨n×⍵`: Pad y to length `n×⍵` by appending 0's.
`n ⍵⍴`: Reshape into a matrix with n columns and  rows.
`+⍀`: Get cumulative sums of the columns.
`0,∊`: Flatten and prepend a 0.
`≢∪`: Count the number of unique values.
> 4 votes

# Answer
# 05AB1E, 37 bytes

```
āει8ìS"^>v<"6ÅÈ‡D8Ê>∞₆+çNè©sr.Λ®¢}Zk>

```

Try it online or verify all test cases.

**Explanation:**

```
ā                # Push a list in the range [1,input-length]
 ε               # Map over each of these integers:
  ι              #  Uninterleave the (implicit) input-string into this many parts,
                 #  resulting in the route of each individual (Robo-)Santa
   8ì            #  Prepend an 8 in front of each string
     S           #  Then convert it to a flattened list of characters
      "^>v<"     #  Push string "^>v<"
            6ÅÈ  #  Push list [0,2,4,6]
               ‡ #  Transliterate all "^" to 0; ">" to 2; etc.
  D              #  Duplicate this list of digits
   8Ê            #  Check for each that it's NOT equal to 8 (0 if 8; 1 otherwise)
     >           #  Increase each by 1 (1 if 8; 2 otherwise)
  ∞              #  Push an infinite positive list: [1,2,3,...]
   ₆+            #  Add 36 to each: [37,38,39,...]
     ç           #  Convert each to a character with this codepoint:
                 #  ["%","&","'",...]
      Nè         #  Index the map-index into this list
        ©        #  Store the character in variable `®` (without popping)
  sr             #  Rearrange the three values on the stack from a,b,c to b,c,a
    .Λ           #  Use the modifiable Canvas builtin with these three arguments
      ®¢         #  Count the amount of character `®` in the Canvas-string
 }Z              # After the map: push the max (without popping the list)
   k             # Get the first (0-based) index of this max
    >            # Increase it by 1 to make it 1-based
                 # (after which it is output implicitly as result)

```

**In-depth step-by-step explanation:**

(Uses input `v>^>v<^<` as example.)

1) `āει`: the `ā` results in the amount of (Robo-)Santas we want to check per iteration, and the `ει` will map this to routes per individual (Robo-)Santa:
Try just this step online.

2) `8ìS"^>v<"6ÅÈ‡` will convert these routes to something usable by the Canvas builtin.

The Canvas Builtin uses three arguments to draw a shape:

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

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

```

And in addition there are a couple of special directions (`+×8`), for which we'll only use `8` in this program. `8` will reset the Canvas starting point.

So something like `["v>^",">v<","^<"]` (three (Robo-)Santa routes) will with `8ìS"^>v<"6ÅÈ‡` translate to: `[8,4,2,0,8,2,4,6,8,0,6]`.

Try the first two steps online.

3) Using what we created in step 2 as the directions-argument, `D8Ê>` for our lengths-argument, and `∞₆+çNè` for the character we want to draw, we use the modifiable Canvas builtin .

With the example of the three (Robo-)Santa routes above, it'll have the following three arguments:

* Lengths: `[1,2,2,2,1,2,2,2,1,2,2]` (1 for every `8`, 2 for every actual movement)
* Character: `"'"`
* Directions: `[8,4,2,0,8,2,4,6,8,0,6]`

Step 3.1: Draw 1 character at starting point `8`:

```
'

```

Step 3.2: Draw 2-1 character in direction 4/:

```
'
'

```

Step 3.3: Draw 2-1 character in direction 2/:

```
'
''

```

Step 3.4: Draw 2-1 character in direction 0/:

```
''
''

```

Step 3.5: Draw 1 character at starting point `8` again.

Step 3.6: Draw 2-1 character in direction `2`/:

```
''
''

```

Step 3.7: Draw 2-1 character in direction 4:/:

```
''
''

```

Step 3.8: Draw 2-1 character in direction 6/:

```
''
''

```

Step 3.9: Draw 1 character at starting point `8` again.

Step 3.10: Draw 2-1 character in direction 0/:

```
'
''
''

```

Step 3.11: Draw 2-1 character in direction 6/:

```
''
 ''
 ''

```

The reason we draw a different character every time and also have a leading `8` to reset to the starting point, is because there isn't any way to clear the Canvas. The next iteration we use the , it'll basically continue where it left off in the previous iteration. We therefore have to do an initial reset, and we draw all the characters on top of each other, which can be seen in the TIO below:

Try the first three steps online.

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

4) `®¢}`: count (`¢`) how many distinct houses all the (Robo-)Santa have visited, by checking how many times the current character (which we've saved in variable `®`) is in the resulting Canvas-string.

Try the first four steps online.

5) `Zk>`: now that we have the amount of houses that can be visited depending on the amount of (Robo-)Santa going around doing their routes, we can get the maximum (`Z`) amount of houses visited, and get the first (1-based) index of this maximum (`k>`) to get the lowest amount of (Robo-)Santa necessary to achieve this maximum amount of visited houses, which will be output as our result.
> 3 votes

# Answer
# Java, 349 bytes

```
s->{var p=new HashSet<String>();for(int i=s.length();i>0;i--){for(int j=0;j<i;j++){int x=0,y=0;p.add(i+","+x+","+y);for(int k=j;k<s.length();k+=i){int c=s.charAt(k)%11;var t=c==6?y++:(c==7?x++:(c==8?y--:x--));p.add(i+","+x+","+y);}}}int[]n=new int[s.length()];p.stream().map(a->a.substring(0,a.indexOf(','))).map(Integer::parseInt).forEach(i->n[i-1]++);int m=0,i=0;for(;i<n.length;i++){m=n[i]>n[m]?i:m;}return m+1;}

```

Try it online.

**Explanation:**

```
    s -> {
            var p = new HashSet<String>();                                  // using Hash-Set for built in distinct elements
            int h = s.length(), i = h, j, x, y, k, c, n[] = new int[h];     // setting up variables
            for (; i > 0; i--)                                              // loop for possible Santas
                for (j = 0; (k = j++) < i;)                                 // loop every Santa
                    for (p.add(i + ",0," + (x = y = 0)); k < h; k += i) {   // add starting position and loop Santa over moves
                        c = (c = s.charAt(k) % 11) == 6 ? y++ : c == 7 ? x++ : c == 8 ? y-- : x--;
                        p.add(i + "," + x + "," + y);                       // change position and add it
                    }
            for (p.stream()                                                 //
                    .map(a -> a.substring(0, a.indexOf(44)))                // only look at Santas number for each house
                    .map(Integer::parseInt)                                 //
                    .forEach(I -> n[I - 1]++); h-- > 0;)                    // add visited Houses together
                i = n[h] > n[i] ? h : i;                                    // finding the index of the greatest element
            return -~i;                                                     // negate and bit-flip
        }

```

Improvements:

* -37 bytes: Using `var` where possible and changing `switch-case` statement to tenary operators
* -1 byte: treating chars as int and using alephalpha's modulo-trick
* -2 bytes: spaces
* -66 bytes: thanks to ceilingcat (learned some java magic I wasn't aware of)

What I learned (as I never coded a challenge befor nor golfed code):

* Java is a horrible language to golf (but I'm not good enough in other languages... so ¯\*(ツ)*/¯ )
* I am far to slow to be competetiv in this AoCG-thing...
> 3 votes

# Answer
# Python, 134 bytes

```
k,*t,x=input(),1
for _ in k:
    p=[0]*x;q={0}
    for c in k:n=p.pop(0)+1j**(ord(c)%11);p+=n,;q|={n}
    t+=(-len(q),x),;x+=1
print(min(t)[1])
```

Attempt This Online!

-21 bytes by stealing alephalpha's codepoint mapping trick.
-11 bytes thanks to pxeger
> 2 votes

# Answer
# Ruby, ~~121 ...~~ 93 bytes

```
->s{a=0;q=s.bytes;q.map{[-((*w=[0i]*a+=1)|q.map{|y|w.rotate![0]+=1i**y%=19}).size,a]}.min[1]}

```

Try it online!
> 2 votes

# Answer
# Wolfram Language (Mathematica), 98 bytes

-5 bytes thanks to @att.

```
Ordering[i=1;s=I^ToCharacterCode@#~Mod~11;0Union@@Accumulate@Partition[s,i,i++,{i,1},0]-i&/@s,-1]&

```

Try it online!
> 2 votes

# Answer
# , 44 bytes

```
1+0{[:\:[:([:#@~.@,+/\)"2-@#\]\0j1^'>^<v'&i.

```

Try it online!

*-3 after stealing a trick from ovs's APL answer. Explanation is similar to ovs's.*

My other attempt used key rather than column sums for simulating the multiple robots:

```
1+0{[:\:[:#@~.@,"2(#\|/#\)+/\/."#.0j1^'>^<v'&i.

```
> 2 votes

# Answer
# BQN, 56 bytes

```
{1+⊑⍒((∾⟜-1∾≠)⊏˜">v<"⊐)⊸{≠⍷∾{+`0∾}¨⊔˜(≠)⥊↕}¨1+↕≠}

```

Try It!

BQN is the Language of The Month for December!
> 2 votes

# Answer
# Jelly, 19 bytes

```
O%11sJµZı*Ż€ÄFQL)MḢ

```

A monadic Link accepting a list of characters which yields an integer, the optimal number of Santas.

**Try it online!**
> 2 votes

# Answer
# Clojure, 259 bytes

```
(let[s(read-line)](print(first(reduce(fn[[a b][c d]](if(< b d)[c d][a b]))(for[i(range 1(inc(count s)))][i(count(set(mapcat #(reductions(fn[[x y]m](case m\^[x(dec y)]\>[(inc x)y]\v[x(inc y)]\<[(dec x)y]))[0 0]%)(for[j(range i)](take-nth i(drop j s))))))])))))

```

Try it online!

Ungolfed:

```
(let [s (read-line)]
  (print
   (first
    (reduce
     (fn [[a b] [c d]] (if (< b d) [c d] [a b]))
     (for [i (range 1 (inc (count s)))]
       [i (count
           (set
            (mapcat
             #(reductions
               (fn [[x y] m]
                 (case m
                   \^ [x (dec y)]
                   \> [(inc x) y]
                   \v [x (inc y)]
                   \< [(dec x) y]))
               [0 0] %)
             (for [j (range i)]
               (take-nth i (drop j s))))))])))))

```

Commented, slightly longer version using threading:

```
(let [s (read-line)]
  (->>
   (for [i (range 1 (inc (count s)))]  ; Create a list of number of houses covered by 1..n (Robo-)Santas (n = length of instruction):
     [i (->>                           ;  for example, for ">>>>>" => ([1 6] [2 4] [3 3] [4 3] [5 2])
         (for [j (range i)]            ;  - split commands for i (Robo-)Santas:
           (take-nth i (drop j s)))    ;    for example, for "^v^v^v^v^v" with 2 (Robo-Santas) => ((\^ \^ \^ \^ \^) (\v \v \v \v \v))
         (mapcat                       ;  - provide a list of all houses covered with a command (splitted to commands for each (Robo)-Santa):
          #(reductions                 ;    for example, for "^v^v^v^v^v" with 2 (Robo-Santas) => ([0 0] [0 -1] [0 -2] [0 -3] [0 -4] [0 -5] [0 0] [0 1] [0 2] [0 3] [0 4] [0 5])
            (fn [[x y] m]              ;      - given a house of position [x y] and move command m:
              (case m \^ [x (dec y)]   ;         move to [x y-1]
                      \> [(inc x) y]   ;         move to [x+1 y]
                      \v [x (inc y)]   ;         move to [x y+1]
                      \< [(dec x) y])) ;         move to [x-1 y]
            [0 0] %))                  ;      - start from house [0 0] and work moves from there
         set                           ;  - convert the list to a set to remove duplicate houses
         count)])                      ;  - count number of houses in the set
   (reduce                             ; From the list created above, pick the best option
    (fn [[a b] [c d]]                  ;  for example, for ">>>>>", the list ([1 6] [2 4] [3 3] [4 3] [5 2]) => [1 6]
      (if (< b d) [c d] [a b])))       ;  - compare number of houses, returning first if the number is same (less (Robo-)Santas is better)
   first                               ; Extract number of (Robo-)Santas from the best option
   print))

```
> 2 votes

# Answer
# JavaScript (ES6), 130 bytes

Expects an array of characters.

This is using `reduce()` ... because why not.

```
a=>a.reduce(r=>(n++,v=new Set(a.map(o=(c,i)=>o[i%=n]=~~o[i]+({'>':1,'<':-1,v:q=a.length}[c]||-q))).add(0).size)>m?(m=v,n):r,n=m=0)

```

Try it online!

### Commented

```
a =>                          // a[] = array of characters
a.reduce(r =>                 // reduce a[] using r as the accumulator:
  (                           //
    n++,                      //   increment n
    v = new Set(              //   define v as the size of this set:
      a.map(o = (c, i) =>     //     for each char. c at position c in a[]:
        o[i %= n] =           //       reduce i modulo n
          ~~o[i] + (          //       coerce o[i] to an integer and add:
            { '>': 1,         //         +1 if c = '>'
              '<': -1,        //         -1 if c = '<'
              v: q = a.length //         +a.length if c = 'v'
            }[c]              //
            || -q             //         -a.length if c = '^'
          )                   //
      )                       //     end of map()
    )                         //   end of Set()
    .add(0)                   //   add the starting position 0
    .size                     //   get the final size of the set
  ) > m ?                     //   if v is greater than m:
    (m = v, n)                //     update m to v and r to n
  :                           //   else:
    r,                        //     leave r unchanged
  n = m = 0                   //   start with r = n = m = 0
)                             // end of reduce()

```
> 1 votes

# Answer
# , 134 bytes

```
function(v)which.max(Map(function(x)sum(unique(c(0,unlist(Map(function(i)cumsum(d[y==i]),y<-1:x))))|T),seq(d<-1i^(utf8ToInt(v)%%11))))

```

Try it online!
> 1 votes

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


# Question
Title: How many elves does Santa need to deliver gifts?
Santa needs some help determining how many elves he will need to help him deliver gifts to each house.

Coal is considerably heavier than presents, so santa will need three elves for every naughty person in the house. Only two elves are needed to help santa carry presents.

On santa's map, a house is represented by a `*`, and each house is split by a `+`.

There will be a number on either side of the house - the one on the left representing the number of naughty people in the house, and the one on the right representing the number of nice people in the house. If there is no number on one side it is interpreted as a 0.

Santa doesn't visit those who are not in the christmas spirit (they don't even deserve coal), so sometimes, a house may not have a number on either side of it. In this case, santa doesn't need help from any elves

For example, one of santa's maps may look like this

```
1*3+2*2+1*+*2

```

In the first house there is **1** naughty and **3** nice, santa will need **nine** elves. In the second, there are **2** naughty and **2** nice, santa will need **ten** elves. In the third house there is **1** naughty and **0** nice, santa will need **three** elves, and in the last house there are **0** naughty and **2** nice, santa will need **four** elves.

This is an over-simplified version of one of santa's maps, though. Normally, santa's maps have multiple lines, and are in a square shape as to better fit on his list. A normal map might look something like this (a `\n` at the end of each line)

```
1*2+*+*4+1*
2*4+3*+1*6+*
*+*+4*2+1*1
*4+*3+1*+2*3
3*10+2*+*5+*

```

In this map, santa needs `((1 + 0 + 0 + 1 + 2 + 3 + 1 + 0 + 0 + 0 + 4 + 1 + 0 + 0 + 1 + 2 + 3 + 2 + 0 + 0) * 3) + ((2 + 0 + 4 + 0 + 4 + 0 + 6 + 0 + 0 + 0 + 2 + 1 + 4 + 3 + 0 + 3 + 10 + 0 + 5 + 0) * 2)` = **151** elves

## Challenge

Help santa determine how many elves he needs to deliver goods to each house!

**Houses**

* A house is represented by a `*`
* Houses are split by `+`
* The number on the left of the house symbolizes the number of naughty people (no number means 0)
* The number on the right symbolizes the number of nice people (no number means 0)
* There may be newlines (`\n`) in the input, which should also be handled as a split

**Elves**

* Santa needs help from *three* elves for naughty people (coal is much heavier than presents)
* Santa needs help from **two** elves for nice people
* If there is no number on either side, santa will not visit that house, and therefor does not need any elves

**What to do**

Print the number of elves santa needs to help him deliver presents to the houses to. Because all Santa needs to know is how many elves to bring, you only need to print the added number of elves he needs for the list of houses

## Test Cases

```
1*1 => 5
1*2 => 7
2*1 => 8
1* => 3
*1 => 2
* => 0

1*1+1*1 => 10
1*2+2*1 => 15
1*+*1 => 5
1*1+*+1*1 => 10
*+*+*+* => 0

```

## Rules

* The input can be either taken as an argument in a function, or from **STDIN** or equivalent
* The output can either be the return value of a function, or printed to **STDOUT** or equivalent
* The input will only contain numbers, `+`, `*`, and newlines `\n`
* The output should be only the total number of elves that Santa needs help from to deliver on Christmas
* Standard loopholes apply

## Scoring

Santa's sleigh is full of gifts giving him less space to run code, so he needs the shortest code he can get (don't worry if this doesn't make sense. If you question Santa's logic you'll end up on the naughty list). Due to Santa's ***CORRECT*** reasoning, the shortest submission in bytes wins!

## Leaderboard

This is a Stack Snippet that generates both a leaderboard and an overview of winners by language.

To ensure your answer shows up, please start your answer with a headline using the following Markdown template

```
## Language Name, N bytes

```

Where N is the size, in bytes, of your submission

If you want to include multiple numbers in your header (for example, striking through old scores, or including flags in the byte count), just make sure that the actual score is the *last* number in your header

```
## Language Name, <s>K</s> X + 2 = N bytes

```

```
var QUESTION_ID=67600;var OVERRIDE_USER=20634;function answersUrl(e){return"http://api.stackexchange.com/2.2/questions/"+QUESTION_ID+"/answers?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+ANSWER_FILTER}function commentUrl(e,s){return"http://api.stackexchange.com/2.2/answers/"+s.join(";")+"/comments?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+COMMENT_FILTER}function getAnswers(){jQuery.ajax({url:answersUrl(answer_page++),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){answers.push.apply(answers,e.items),answers_hash=[],answer_ids=[],e.items.forEach(function(e){e.comments=[];var s=+e.share_link.match(/\d+/);answer_ids.push(s),answers_hash[s]=e}),e.has_more||(more_answers=!1),comment_page=1,getComments()}})}function getComments(){jQuery.ajax({url:commentUrl(comment_page++,answer_ids),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){e.items.forEach(function(e){e.owner.user_id===OVERRIDE_USER&&answers_hash[e.post_id].comments.push(e)}),e.has_more?getComments():more_answers?getAnswers():process()}})}function getAuthorName(e){return e.owner.display_name}function process(){var e=[];answers.forEach(function(s){var r=s.body;s.comments.forEach(function(e){OVERRIDE_REG.test(e.body)&&(r="<h1>"+e.body.replace(OVERRIDE_REG,"")+"</h1>")});var a=r.match(SCORE_REG);a&&e.push({user:getAuthorName(s),size:+a[2],language:a[1],link:s.share_link})}),e.sort(function(e,s){var r=e.size,a=s.size;return r-a});var s={},r=1,a=null,n=1;e.forEach(function(e){e.size!=a&&(n=r),a=e.size,++r;var t=jQuery("#answer-template").html();t=t.replace("{{PLACE}}",n+".").replace("{{NAME}}",e.user).replace("{{LANGUAGE}}",e.language).replace("{{SIZE}}",e.size).replace("{{LINK}}",e.link),t=jQuery(t),jQuery("#answers").append(t);var o=e.language;/<a/.test(o)&&(o=jQuery(o).text()),s[o]=s[o]||{lang:e.language,user:e.user,size:e.size,link:e.link}});var t=[];for(var o in s)s.hasOwnProperty(o)&&t.push(s[o]);t.sort(function(e,s){return e.lang>s.lang?1:e.lang<s.lang?-1:0});for(var c=0;c<t.length;++c){var i=jQuery("#language-template").html(),o=t[c];i=i.replace("{{LANGUAGE}}",o.lang).replace("{{NAME}}",o.user).replace("{{SIZE}}",o.size).replace("{{LINK}}",o.link),i=jQuery(i),jQuery("#languages").append(i)}}var ANSWER_FILTER="!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe",COMMENT_FILTER="!)Q2B_A2kjfAiU78X(md6BoYk",answers=[],answers_hash,answer_ids,answer_page=1,more_answers=!0,comment_page;getAnswers();var SCORE_REG=/<h\d>\s*([^\n,]*[^\s,]),.*?(-?\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/,OVERRIDE_REG=/^Override\s*header:\s*/i;
```

```
body{text-align:left!important}#answer-list,#language-list{padding:10px;width:290px;float:left}table thead{font-weight:700}table td{padding:5px}
```

```
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script> <link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b"> <div id="answer-list"> <h2>Leaderboard</h2> <table class="answer-list"> <thead> <tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr></thead> <tbody id="answers"> </tbody> </table> </div><div id="language-list"> <h2>Winners by Language</h2> <table class="language-list"> <thead> <tr><td>Language</td><td>User</td><td>Score</td></tr></thead> <tbody id="languages"> </tbody> </table> </div><table style="display: none"> <tbody id="answer-template"> <tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table> <table style="display: none"> <tbody id="language-template"> <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table>
```

# Answer
# Pyth, 21 bytes

```
ssMs*VCcR\*scR\+.z_S3

```

Multi-line example

Single-line test suite

```
ssMs*VCcR\*scR\+.z_S3
                .z        Take a input, as a list of lines.
            cR\+          Chop each line on '+'.
           s              Flatten into list of strings.
       cR\*               Chop each line on '*'.
      C                   Transpose, into a list of naughty and nice.
    *V            _S3     Vectorized multiplication with [3, 2, 1]. This replicates
                          the naughty list 3 times and the nice list 2 times.
   s                      Flatten.
 sM                       Convert each string to an int.
s                         Sum.

```
> 2 votes

# Answer
# JavaScript (ES6), 52 bytes

```
s=>eval(s.replace(/\D|$/g,m=>`.0*${m=="*"?3:2}+`)+0)

```

## Explanation

Converts the input into a valid JavaScript statement. Replaces all `*` with `.0*3+` and all other (non-digit) symbols with `.0*2+`. For example `8*9+*10` becomes `8.0*3+9.0*2+.0*3+10`. Finally it appends `.0*2` to the end for the last nice count. This works because `n.0` = `n` and `.0` = `0`.

```
s=>
  eval(                      // execute the formed equation
    s.replace(/\D|$/g,       // replace each symbol (and also add to the end) with:
      m=>`.0*${m=="*"?3:2}+` // case * = ".0*3+", else replace with ".0*2+"
    )
    +0                       // add "0" to the end for the trailing "+"
  )

```

## Test

```
var solution = s=>eval(s.replace(/\D|$/g,m=>`.0*${m=="*"?3:2}+`)+0)
```

```
<textarea id="input" rows="6" cols="30">1*2+*+*4+1*
2*4+3*+1*6+*
*+*+4*2+1*1
*4+*3+1*+2*3
3*10+2*+*5+*</textarea><br />
<button onclick="result.textContent=solution(input.value)">Go</button>
<pre id="result"></pre>
```
> 13 votes

# Answer
## Flex+C, ~~112~~ 90 bytes

```
 m=3,t;
%%
[0-9]+ t+=m*atoi(yytext);
\* m=2;
[+\n] m=3;
%%
main(){yylex();printf("%d",t);}

```

The first character is a space. Compile with:

```
flex -o santa.c santa.l
cc santa.c -o santa -ll

```

Reads from STDIN, writes to STDOUT. Input is terminated by EOF (Ctrl+D in console).
> 3 votes

# Answer
## Mathematica, 70 bytes

```
a=Tr[FromDigits/@StringExtract[#,"
"|"+"->;;,"*"->#2]]&;3#~a~1+2#~a~2&

```

Uses `StringExtract` to extract the individual numbers.
> 2 votes

# Answer
## CJam, 23 bytes

```
q'+NerN/{'*/3*5<:~~}%1b

```

Test it here.

### Explanation

```
q      e# Read all input.
'+Ner  e# Replaces all "+" with linefeeds.
N/     e# Split the string around linefeeds (i.e. into houses).
{      e# Map this block over the list of house...
  '*/  e#   Split the string around the "*".
  3*   e#   Repeat the times.
  5<   e#   Truncate to 5 elements, keeping 3 copies of the naughty number and 2 copies of
       e#   the nice number.
  :~   e#   Evaluate each number (which may be an empty string which pushes nothing).
  ~    e#   Dump the list of numbers on the stack.
}%
1b     e# Sum all the numbers.

```
> 2 votes

# Answer
## Seriously, ~~38~~ 30 bytes

```
'*Ws`'0+'*@s'≈£M4rR*`MΣ+'+,WXX

```

Hex Dump:

```
272a57736027302b272a407327f79c4d3472522a604de42b272b2c575858

```

This new version breaks the online interpreter, but works fine locally. Here's an example run:

```
$ python2 seriously.py -f elves.srs
1*2+*+*4+1*
2*4+3*+1*6+*
*+*+4*2+1*1
*4+*3+1*+2*3
3*10+2*+*5+*

151

```

Explanation:

```
'*                              Push a "*" to make the stack truthy
  W                        W    Repeat while the top of stack is truthy
                                  (A whole bunch of instructions just turn the "*" into a
                                  zero on the first pass, so I'll list them here in the
                                  order they actually accomplish useful things:)
                          ,     Read in a line of input
   s                    '+      Split it on occurrence of "+"
    `               `M          Map this function over the list of strings.
     '0+                        Prepend a "0" to ensure a naughty number exists
        '*@s                    Split the string on "*"
            '≈£M                Map over the string with int() to convert it to int
                4rR             Push [3,2,1,0]
                   *            Dot product
                      Σ+        Sum all the houses, and add it to the results
                                  from the previous line of input
                            XX  Pop the "" and '+ from the stack, leaving only the
                                result to be implicitly output.

```

### Old Version:

```
'+ε'*`+'++,`╬Xs`≈`╗`'0+'*@s╜M[3,2]*`MΣ

```

Hex Dump:

```
272bee272a602b272b2b2c60ce587360f760bb6027302b272a4073bd4d5b332c325d2a604de4

```

Try It Online

Explanation:

```
  ε'*                                   Initialize with two strings so the first + works
     `+'++,`╬                           Read in strings and compile them until "" is read
             X                          Throw away the ""
'+            s                         Split on +
               `≈`╗                     Chuck int function into reg0 to use within function
                   `               `M   Map this function over the list of houses
                    '0+                 Prepend a "0" to ensure a naughty number exists
                       '*@s             Split on *
                           ╜M           Convert the resulting list to ints with stored func
                             [3,2]*     Dot product with [3,2]
                                     Σ  Sum all houses

```

This maybe could be shorter if I just converted each line separately and summed them all at the end. I'll look into it later.
> 2 votes

# Answer
## PowerShell, 52 bytes

Using variation of user81655's `.0` trick

```
$OFS='+';"$("$args"-replace'\*','.0*3+2*0'|iex)"|iex

```

### Ungolfed version

```
$OFS='+' # Set Output Field Separator to '+'
         # So if $arr = 1,2,3 then "$arr" will output 1+2+3

" # Cast result of subexpression to string using $OFS

    $( # Subexpression

        "$args" # Input is an array of arguments. Casting it to string using "$args"
                # is shorter then acessing the first element using $args[0]
                # $OFS wouldn't affect this, because input has only 1 element.

        -replace '\*' , '.0*3+2*0' # Replace every * with .0*3+2*0
                                   # Example: 1*+*1 becomes 1.0*3+2*0+.0*3+2*01

    ) | Invoke-Expression # Execute a result of subexpression as PS code.
                          # This will execute resulting multiline string line-by line
                          # and return an array of values, e.g.: 18,38,21,29,45

" Cast the aray above to string using '+' as Output Field Separator, e.g: 18+38+21+29+45

| Invoke-Expression # Execute the string above as PS code to get final result.
                    # E.g.: 18+38+21+29+45 = 151

```

### Usage example

```
$Map = @'
1*2+*+*4+1*
2*4+3*+1*6+*
*+*+4*2+1*1
*4+*3+1*+2*3
3*10+2*+*5+*
'@

PS > .\SantaMap.ps1 $Map
151

```
> 2 votes

# Answer
# Vyxal `Dad`, 12 bytes

```
ƛ‛\Wṡ⌊:ż∷2+*

```

Try it Online!

```
ƛ            # Map (multiline input) to...
 ‛\Wṡ        # Split on non-word chars
     ⌊       # parse an integer from each
      :ż     # 1...x.length
        ∷2+  # Modulo 2, + 1 results in array of 2s and 3s
           * # Multiply these
             # (d flag) deep sum of result

```

`D` makes sure the backslash in `‛\W` doesn't get removed, `a` is necessary for multiline input and `d` takes the deep sum of the result.
> 2 votes

# Answer
## Swift 2, ~~283~~ 211 Bytes

```
func f(s:String)->Int{var r=0;for p in(s.characters.split{$0=="\n"}.map(String.init)){for v in p.utf8.split(43){let k="0\(v)".utf8.split(42);r+=(Int("\(k[0])")!)*3;r+=(k.count<2 ?0:Int("\(k[1])")!)*2}};return r}

```

This can be tested on SwiftStub, here

### Ungolfed

```
func f(s: String) -> Int{
    var r = 0

    //for every value in the input, split every "\n" and mapped
    //to a String array
    for p in (s.characters.split{$0=="\n"}.map(String.init)){

        //for every value in the split input, split again at every + (Decimal 43)
        for v in p.utf8.split(43){
            //change the value to "0" + v, which doesn't change the
            //input, but in the event that there is no input on the
            //left side, a "0" will be used
            //
            //then split on every * (Decimal 42)
            let k = "0\(v)".utf8.split(42)

           //add to the total count of elves the number on the left * 3
            r+=(Int("\(k[0])")!) * 3

            //add to the total count of elves the number on the left * 2
            r+=(k.count < 2 ? 0 : Int("\(k[1])")!) * 2
        }

        //return the number of elves
        return r
    }
}

```
> 1 votes

# Answer
# Python 3, ~~141~~ ~~114~~ 112 bytes

Takes multi-line inputs like this `c("1*2+*+*4+1*\n2*4+3*+1*6+*\n*+*+4*2+1*1\n*4+*3+1*+2*3\n3*10+2*+*5+*")`

```
lambda s:sum(a and(3-z)*int(a)or 0for j in s.split("\n")for i in j.split("+")for z,a in enumerate(i.split("*")))

```

**Ungolfed:**

```
def c(s):
    t = 0
    for j in s.split("\n"):
        for i in j.split("+"):
            for z,a in enumerate(i.split("*"))
                if a == "":
                    a = 0
                else:
                    a = int(a)
                t += (3-z) * a  # alternate a*3 and a*2
    return t

```
> 1 votes

# Answer
I'm super late, but I wanted to give it a shot anyways.

# Ruby, ~~84~~ 55 bytes

I found this question again after so many years and was thinking up a fresh answer before I realized I'd already answered this before. Whoops! Anyways, here's a drastically improved answer.

```
->m{m.scan(/(\d*)\*(\d*)/).sum{|a,b|3*a.to_i+2*b.to_i}}

```

Try it online!

Old 84-byte answer from when I first answered this 2 years ago:

```
->m{m.split(/[+\n]/).map{|h|b,g=h.split(?*).map &:to_i
3*(b||0)+2*(g||0)}.inject :+}

```

Try it online!
> 1 votes

# Answer
# Python 3, 96 bytes

```
lambda s:sum(int('0'+n)*(3-i%2)for i,n in enumerate(re.sub('[*\s]','+',s).split('+')));import re

```

Try it online!

101 bytes without regex

```
lambda s:sum(int('0'+n)*(3-i%2)for i,n in enumerate(s.replace('*','+').replace('\n','+').split('+')))

```

Try it online!
> 1 votes

# Answer
# JavaScript (ES6), 47 bytes

```
x=>x.split(/\W/).reduce((y,x,i)=>y+x*(3-i%2),0)

```

Try it online!

Beats the winning JS answer!

## How does it work?

```
x =>            // Defining a function taking an argument x
  x.split(      // Split x on...
    /\W/        // The regex \W, matching non-word characters
  )
  .reduce((     // Reduce by a function taking...
      y,        // y - current total value
      x,        // x - value of this one
      i         // i - index in input
    ) =>        // and returning
    y + x *     // y, plus x times...
    (3 - i % 2) // 3 if index is even (naughty) otherwise 2
  , 0)          // With initial value 0.

```
> 0 votes

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


title: Simulate weathering of a rock

text:
# Question
Title: Simulate weathering of a rock
*Inspired by my geography class*, *Sandboxed*

Simulate weathering / erosion.

### Input

Input will be given as a string of any 2 characters (or see below) you like in the shape of the rock (here i use spaces and hashes):

```
   ###
  ####
 #####
#######
#######
########

```

Or if your language doesn't support strings, a square matrix of 1s and 0s, a matrix of chars, whatever makes your answer more golfier.

# Process

The rock will erode until it disappears completely. Lets take example of input:

```
    ##
 ## ### #
#########
###########

```

First we find which part of the rock is exposed (that is there is no rock particle directly above / below / left / right) to the air (i use @ to show such particles here):

```
    @@
 @@ @#@ @
@##@###@@
@########@@

```

NOTE: The bottom most rock particles are touching the ground and they are not touching air, hence we don't count these particles.

Then we randomly (50% chance individually for each particle) remove the rock particles (here #) (apply gravity similar to this challenge that are exposed to the air:

```
    #
    ##
 ## ### #
##########

```

And be repeat the process until the rock disappears and output the rock in between each iteration (including the original input). In this case we output:

```
    ##
 ## ### #
#########
###########
    #
    ##
 ## ### #
##########

 ## ##
 #########

 #  #
 ## #### #

 #
 #  # # #

 #    #

```

This is code-golf, answer in the shortest amount of bytes wins.

# Answer
> 4 votes
# Charcoal, 58 bytes

```
≔Ｅθ⁰ηＷＳＵＭη⁺κ⁼#§ιλ⊞η⁰Ｗ⌈η«Ｍι↓↑Ｅη×#κ⸿ＵＭη↨¹Ｅκ∨‹μ⌊⟦§η⊖λ⊖κ§η⊕λ⟧‽

```

Try it online! Link is to verbose version of code. Assumes input is a rectangular newline-terminated list of strings. Explanation:

```
≔Ｅθ⁰ηＷＳＵＭη⁺κ⁼#§ιλ

```

Calculate the height of each column of the rock.

```
⊞η⁰

```

Add a padding entry to prevent wrapping.

```
Ｗ⌈η«

```

Repeat until the rock has been eroded away.

```
Ｍι↓

```

Leave space to display the rock.

```
↑Ｅη×#κ

```

Output the rock.

```
⸿

```

Leave a blank line between rocks. (Otherwise they just crash into each other making the output impossible to interpret.)

```
ＵＭη↨¹Ｅκ∨‹μ⌊⟦§η⊖λ⊖κ§η⊕λ⟧‽

```

For each column, for each particle, check whether it's exposed, and add up all of the unexposed particles and randomly the exposed particles.

# Answer
> 4 votes
# 05AB1E (legacy), 42 bytes

```
0ì€Ć[ø€{ø=ÐSO_#ø‚εεDTÂ‚00.:ø}}`ø‚øεøεSÚΩ}J

```

I/O as a list of equal-sized strings, with digits `0` for spaces and `1` for rocks. The output will be two wider than the input, due to a leading/trailing column of spaces/`0`s.

Try it online or try it online pretty-printed.

Uses the legacy version of 05AB1E, because `ø` works on lists of strings. In the new 05AB1E version, most of the `ø` should be `€SøJ` instead.

**Explanation:**

```
0ì€Ć                   # Add a leading/trailing 0 to each line of the (implicit)
                       # input-list:
0ì                     #  Prepend a 0 in front of each line
  €                    #  Map over each line:
   Ć                   #   Enclose it, appending its own head
[                      # Then start an infinite loop:
 ø€{ø                  #  Apply gravity:
 ø                     #   Zip/transpose; swapping rows/columns
  €{                   #   Sort each row
    ø                  #   Zip/transpose back
     =                 #  Print the result with newline (without popping)
     Ð                 #  Triplicate the current result
      S                #  Convert the top one to a flattened list of digits
       O               #  Sum this list
        _              #  If it's 0:
         #             #   Stop the infinite loop
      ø                #  Zip/transpose the top; swapping rows/columns
       ‚               #  Pair it with its untransposed list
        ε              #  Map over this pair:
         ε             #   Map over each row:
          D            #    Duplicate the current row
           T           #    Push 10
            Â          #    Bifurcate it; short for Duplicate & Reverse copy
             ‚         #    Pair them together: [10,"01"]
              00.:     #    Replace all "10" and "01" in the copy with "00"
                  ø    #    Create cell-pairs of the row and modified row
        }}             #  Close both maps
          `            #  Pop and push both separated to the stack
           ø           #  Transpose the top copy back
            ‚          #  Pair them back together
             ø         #  Transpose this pair of matrices
              ε        #  Map over each pair of rows
               ø       #   Zip/transpose to pair together cell-pairs
                ε      #   Map over each pair of cells-pairs:
                 S     #    Convert it to a flattened list of four digits
                  Ú    #    Uniquify it
                   Ω   #    Pop and push a random value from this list
                }      #   Close the inner map
                 J     #   Join the list of characters back to a string-line

```

I'm not happy with `}}`ø‚øεøεSÚΩ}J` at all, but I'm unable to find something shorter to concat the values of two matrices. Adding values of two matrices together is no problem, since that is just `+`, but concatenation on the other hand.. (An equal-bytes alternative for this portion could be `}}`øδ+εNèεÚΩ}J`.)
Feel free to try and find something shorter here.

# Answer
> 2 votes
# Python 3, 356 bytes

```
import random as r,re
y=lambda _:[' ','#'][r.choice([0,1])]
g=lambda x:[*map(''.join,zip(*[(' '*(len(x)-i.count('#')))+('#'*i.count('#'))for i in zip(*x)]))]
f=lambda x:[w:=g([re.sub('#' if not i else'#(?=[^#])|(?<=[^#])#',y,a)for i,a in enumerate(x)])]+(f(w)if any(i.strip()for i in w)else[])
h=lambda x:[*map('\n'.join,f([f' {i} 'for i in x.split('\n')]))]

```

# Answer
> 2 votes
# Perl 5 \+ `-n0`, 99 bytes

I'm hoping to continue working on this tonight, but this is a start (which I *think* covers the requirements?)

Accepts a rectangular multi-line string of `1`s and `0`s which are transliterated from `#` and space in the link.

```
while(/1/){say;/
/;($-)=@-;s/1(?!1)|(?<!1)1|(?<=0.{$-})1/0|rand 2/ges;1while s/1(.{$-})0/0${1}1/gs}

```

Try it online!

---
Tags: code-golf, grid, random, matrix
---


title: Write a number in overflowed binary

text:
# Question
Title: Write a number in overflowed binary
We all know how binary conversion works: the sequence of bits

$$ b\_1, b\_2, ..., b\_{n-1}, b\_n $$

encodes the number

$$ b\_1 \times 2^{n-1} + b\_2 \times 2^{n-2} + ... + b\_{n-1} \times 2^1 + b\_n \times 2^0 $$

This gives an unambiguous representation when we limit all bits \\$ b\_i \\$ to be only `0` or `1`.

...but what if we allow digits outside that range? How about also allowing the "bits" `2` and `3`?

The normal representation of 18 in binary would be `10010`, but since `10` is \\$ 1 \times 2^1 + 0 \times 2^0 = 1 \times 2 + 0 = 2 \\$, we could also write it as `02` (\\$ 0 \times 2^1 + 2 \times 2^0 = 2 \\$), we could also write \\$ 18 \\$, in an "overflowed" binary, as `10002`.

But we can also see that `10000` (\\$ 16 \\$) could be `02000`, so \\$ 18 \\$ could be `02002`. We can repeat this process and get a whole list of possible "overflowed binary" encodings for our number \\$ 18 \\$ (which includes \\$ 18 \\$'s normal binary encoding):

```
10010
10002
02010
02002
01210
01202
01130
01122
00330
00322

```

## Task

Given a number \\$ n \\$ and a maximum digit value \\$ c \\$, output all possible lists of digits between \\$ 0 \\$ and \\$ c \\$ (inclusive) which encode \\$ n \\$ in overflowed binary.

## Rules

* You may assume \\$ n \\$ and \\$ c \\$ will both be integers with \\$ n \ge 0 \\$ and \\$ c \ge 1 \\$
* You may output lists with any (finite) number of leading zeroes, but you not output duplicate lists that differ only by leading zeroes; for example, you may not output both `[0, 1, 3]` and `[1, 3]`
* You must output in a way that clearly separates digits, even when they are greater than \\$ 9 \\$. For example, `[13, 2]` must be distinguishable from `[1, 3, 2]`
* You may use any reasonable I/O method
* Standard loopholes are forbidden
* This is , so the shortest code in bytes wins

## Test cases

These test outputs are padded with leading zeroes such that all output lists are the same length.

```
n   c   output
--------------
0   1   [[0]]
0   5   [[0]]
1   1   [[1]]
4   7   [[0,0,4],[0,1,2],[0,2,0],[1,0,0]]
18  3   [[0,0,3,2,2],[0,0,3,3,0],[0,1,1,2,2],[0,1,1,3,0],[0,1,2,0,2],[0,1,2,1,0],[0,2,0,0,2],[0,2,0,1,0],[1,0,0,0,2],[1,0,0,1,0]]
12  12  [[0,0,0,12],[0,0,1,10],[0,0,2,8],[0,0,3,6],[0,0,4,4],[0,0,5,2],[0,0,6,0],[0,1,0,8],[0,1,1,6],[0,1,2,4],[0,1,3,2],[0,1,4,0],[0,2,0,4],[0,2,1,2],[0,2,2,0],[0,3,0,0],[1,0,0,4],[1,0,1,2],[1,0,2,0],[1,1,0,0]]
14  10  [[0,0,2,10],[0,0,3,8],[0,0,4,6],[0,0,5,4],[0,0,6,2],[0,0,7,0],[0,1,0,10],[0,1,1,8],[0,1,2,6],[0,1,3,4],[0,1,4,2],[0,1,5,0],[0,2,0,6],[0,2,1,4],[0,2,2,2],[0,2,3,0],[0,3,0,2],[0,3,1,0],[1,0,0,6],[1,0,1,4],[1,0,2,2],[1,0,3,0],[1,1,0,2],[1,1,1,0]]
429 3   [[0,1,2,3,2,3,3,3,3],[0,1,2,3,3,1,3,3,3],[0,1,2,3,3,2,1,3,3],[0,1,2,3,3,2,2,1,3],[0,1,2,3,3,2,2,2,1],[0,1,2,3,3,2,3,0,1],[0,1,2,3,3,3,0,1,3],[0,1,2,3,3,3,0,2,1],[0,1,2,3,3,3,1,0,1],[0,1,3,1,2,3,3,3,3],[0,1,3,1,3,1,3,3,3],[0,1,3,1,3,2,1,3,3],[0,1,3,1,3,2,2,1,3],[0,1,3,1,3,2,2,2,1],[0,1,3,1,3,2,3,0,1],[0,1,3,1,3,3,0,1,3],[0,1,3,1,3,3,0,2,1],[0,1,3,1,3,3,1,0,1],[0,1,3,2,0,3,3,3,3],[0,1,3,2,1,1,3,3,3],[0,1,3,2,1,2,1,3,3],[0,1,3,2,1,2,2,1,3],[0,1,3,2,1,2,2,2,1],[0,1,3,2,1,2,3,0,1],[0,1,3,2,1,3,0,1,3],[0,1,3,2,1,3,0,2,1],[0,1,3,2,1,3,1,0,1],[0,1,3,2,2,0,1,3,3],[0,1,3,2,2,0,2,1,3],[0,1,3,2,2,0,2,2,1],[0,1,3,2,2,0,3,0,1],[0,1,3,2,2,1,0,1,3],[0,1,3,2,2,1,0,2,1],[0,1,3,2,2,1,1,0,1],[0,1,3,3,0,0,1,3,3],[0,1,3,3,0,0,2,1,3],[0,1,3,3,0,0,2,2,1],[0,1,3,3,0,0,3,0,1],[0,1,3,3,0,1,0,1,3],[0,1,3,3,0,1,0,2,1],[0,1,3,3,0,1,1,0,1],[0,2,0,3,2,3,3,3,3],[0,2,0,3,3,1,3,3,3],[0,2,0,3,3,2,1,3,3],[0,2,0,3,3,2,2,1,3],[0,2,0,3,3,2,2,2,1],[0,2,0,3,3,2,3,0,1],[0,2,0,3,3,3,0,1,3],[0,2,0,3,3,3,0,2,1],[0,2,0,3,3,3,1,0,1],[0,2,1,1,2,3,3,3,3],[0,2,1,1,3,1,3,3,3],[0,2,1,1,3,2,1,3,3],[0,2,1,1,3,2,2,1,3],[0,2,1,1,3,2,2,2,1],[0,2,1,1,3,2,3,0,1],[0,2,1,1,3,3,0,1,3],[0,2,1,1,3,3,0,2,1],[0,2,1,1,3,3,1,0,1],[0,2,1,2,0,3,3,3,3],[0,2,1,2,1,1,3,3,3],[0,2,1,2,1,2,1,3,3],[0,2,1,2,1,2,2,1,3],[0,2,1,2,1,2,2,2,1],[0,2,1,2,1,2,3,0,1],[0,2,1,2,1,3,0,1,3],[0,2,1,2,1,3,0,2,1],[0,2,1,2,1,3,1,0,1],[0,2,1,2,2,0,1,3,3],[0,2,1,2,2,0,2,1,3],[0,2,1,2,2,0,2,2,1],[0,2,1,2,2,0,3,0,1],[0,2,1,2,2,1,0,1,3],[0,2,1,2,2,1,0,2,1],[0,2,1,2,2,1,1,0,1],[0,2,1,3,0,0,1,3,3],[0,2,1,3,0,0,2,1,3],[0,2,1,3,0,0,2,2,1],[0,2,1,3,0,0,3,0,1],[0,2,1,3,0,1,0,1,3],[0,2,1,3,0,1,0,2,1],[0,2,1,3,0,1,1,0,1],[0,2,2,0,0,3,3,3,3],[0,2,2,0,1,1,3,3,3],[0,2,2,0,1,2,1,3,3],[0,2,2,0,1,2,2,1,3],[0,2,2,0,1,2,2,2,1],[0,2,2,0,1,2,3,0,1],[0,2,2,0,1,3,0,1,3],[0,2,2,0,1,3,0,2,1],[0,2,2,0,1,3,1,0,1],[0,2,2,0,2,0,1,3,3],[0,2,2,0,2,0,2,1,3],[0,2,2,0,2,0,2,2,1],[0,2,2,0,2,0,3,0,1],[0,2,2,0,2,1,0,1,3],[0,2,2,0,2,1,0,2,1],[0,2,2,0,2,1,1,0,1],[0,2,2,1,0,0,1,3,3],[0,2,2,1,0,0,2,1,3],[0,2,2,1,0,0,2,2,1],[0,2,2,1,0,0,3,0,1],[0,2,2,1,0,1,0,1,3],[0,2,2,1,0,1,0,2,1],[0,2,2,1,0,1,1,0,1],[0,3,0,0,0,3,3,3,3],[0,3,0,0,1,1,3,3,3],[0,3,0,0,1,2,1,3,3],[0,3,0,0,1,2,2,1,3],[0,3,0,0,1,2,2,2,1],[0,3,0,0,1,2,3,0,1],[0,3,0,0,1,3,0,1,3],[0,3,0,0,1,3,0,2,1],[0,3,0,0,1,3,1,0,1],[0,3,0,0,2,0,1,3,3],[0,3,0,0,2,0,2,1,3],[0,3,0,0,2,0,2,2,1],[0,3,0,0,2,0,3,0,1],[0,3,0,0,2,1,0,1,3],[0,3,0,0,2,1,0,2,1],[0,3,0,0,2,1,1,0,1],[0,3,0,1,0,0,1,3,3],[0,3,0,1,0,0,2,1,3],[0,3,0,1,0,0,2,2,1],[0,3,0,1,0,0,3,0,1],[0,3,0,1,0,1,0,1,3],[0,3,0,1,0,1,0,2,1],[0,3,0,1,0,1,1,0,1],[1,0,0,3,2,3,3,3,3],[1,0,0,3,3,1,3,3,3],[1,0,0,3,3,2,1,3,3],[1,0,0,3,3,2,2,1,3],[1,0,0,3,3,2,2,2,1],[1,0,0,3,3,2,3,0,1],[1,0,0,3,3,3,0,1,3],[1,0,0,3,3,3,0,2,1],[1,0,0,3,3,3,1,0,1],[1,0,1,1,2,3,3,3,3],[1,0,1,1,3,1,3,3,3],[1,0,1,1,3,2,1,3,3],[1,0,1,1,3,2,2,1,3],[1,0,1,1,3,2,2,2,1],[1,0,1,1,3,2,3,0,1],[1,0,1,1,3,3,0,1,3],[1,0,1,1,3,3,0,2,1],[1,0,1,1,3,3,1,0,1],[1,0,1,2,0,3,3,3,3],[1,0,1,2,1,1,3,3,3],[1,0,1,2,1,2,1,3,3],[1,0,1,2,1,2,2,1,3],[1,0,1,2,1,2,2,2,1],[1,0,1,2,1,2,3,0,1],[1,0,1,2,1,3,0,1,3],[1,0,1,2,1,3,0,2,1],[1,0,1,2,1,3,1,0,1],[1,0,1,2,2,0,1,3,3],[1,0,1,2,2,0,2,1,3],[1,0,1,2,2,0,2,2,1],[1,0,1,2,2,0,3,0,1],[1,0,1,2,2,1,0,1,3],[1,0,1,2,2,1,0,2,1],[1,0,1,2,2,1,1,0,1],[1,0,1,3,0,0,1,3,3],[1,0,1,3,0,0,2,1,3],[1,0,1,3,0,0,2,2,1],[1,0,1,3,0,0,3,0,1],[1,0,1,3,0,1,0,1,3],[1,0,1,3,0,1,0,2,1],[1,0,1,3,0,1,1,0,1],[1,0,2,0,0,3,3,3,3],[1,0,2,0,1,1,3,3,3],[1,0,2,0,1,2,1,3,3],[1,0,2,0,1,2,2,1,3],[1,0,2,0,1,2,2,2,1],[1,0,2,0,1,2,3,0,1],[1,0,2,0,1,3,0,1,3],[1,0,2,0,1,3,0,2,1],[1,0,2,0,1,3,1,0,1],[1,0,2,0,2,0,1,3,3],[1,0,2,0,2,0,2,1,3],[1,0,2,0,2,0,2,2,1],[1,0,2,0,2,0,3,0,1],[1,0,2,0,2,1,0,1,3],[1,0,2,0,2,1,0,2,1],[1,0,2,0,2,1,1,0,1],[1,0,2,1,0,0,1,3,3],[1,0,2,1,0,0,2,1,3],[1,0,2,1,0,0,2,2,1],[1,0,2,1,0,0,3,0,1],[1,0,2,1,0,1,0,1,3],[1,0,2,1,0,1,0,2,1],[1,0,2,1,0,1,1,0,1],[1,1,0,0,0,3,3,3,3],[1,1,0,0,1,1,3,3,3],[1,1,0,0,1,2,1,3,3],[1,1,0,0,1,2,2,1,3],[1,1,0,0,1,2,2,2,1],[1,1,0,0,1,2,3,0,1],[1,1,0,0,1,3,0,1,3],[1,1,0,0,1,3,0,2,1],[1,1,0,0,1,3,1,0,1],[1,1,0,0,2,0,1,3,3],[1,1,0,0,2,0,2,1,3],[1,1,0,0,2,0,2,2,1],[1,1,0,0,2,0,3,0,1],[1,1,0,0,2,1,0,1,3],[1,1,0,0,2,1,0,2,1],[1,1,0,0,2,1,1,0,1],[1,1,0,1,0,0,1,3,3],[1,1,0,1,0,0,2,1,3],[1,1,0,1,0,0,2,2,1],[1,1,0,1,0,0,3,0,1],[1,1,0,1,0,1,0,1,3],[1,1,0,1,0,1,0,2,1],[1,1,0,1,0,1,1,0,1]]

```

# Answer
# Jelly, ~~10~~ 8 bytes

```
Żṗ‘}Ḅ=¥Ƈ

```

Try it online!

Takes `c` on the left, `n` on the right

Brute-force approach. Generates all lists of length \\$n+1\\$ containing the numbers \\$0\\$ to \\$c\\$, meaning that it times out for \\$n \> 7\\$ on TIO. For a *much* faster version, see the revision history.

-2 bytes thanks partially to a suggestion by hyper-neutrino

## How it works

```
Żṗ‘}Ḅ=¥Ƈ - Main link. Takes c on the left, n on the right
Ż        - Generate the range [0, ..., c]
   }     - To n:
  ‘      -   Yield n+1, to account for n = 0
 ṗ       - Cartesian power. Yield all lists of length n+1 of the elements of [0, ..., c]
      ¥Ƈ - Keep those for which the following is true:
    Ḅ    -   When converting from binary,
     =   -   they equal n

```
> 7 votes

# Answer
# , ~~97~~ ~~81~~ ~~78~~ ~~73~~ 68 bytes

Or **\>=4.1, 61 bytes** by replacing the word `function` with `\`.

*-11 bytes and another -3 thanks to @Giuseppe.*
*-5 bytes thanks to @Dominic van Essen.*

```
function(n,c,g=t(expand.grid(rep(list(0:c),n+1))))g[,2^(n:0)%*%g==n]

```

Try it online!

Brute-force solution.
Multiple vectors are output column-wise. Outputs additional leading zeros.
~~Deals with the `0` case in a rather ugly manner.~~ No `if` thanks to @Dominic van Essen.

### Explanation

```
function(n,c,   # a function taking n and c as arguments
 g=             # we use another argument to compute g
                # - all combinations of digits 0..c of length n+1
  t(            # transpose (converts from data frame to matrix)
   expand.grid( # all combinations of
   rep(         # repeat...
    list(0:c),  # ...a list of digits 0..c
                # (list to repeat whole object not just append to vector) ...
    n+1         # n+1 times (to handle 0 edge case)
))))
g[,             # get all rows of g
                # and columns where ...
 2^(n:0)        # ...powers of 2: 2^n to 2^0...
  %*%g          # ...matrix-multplied by g
                # (the vector of powers is promoted to a column matrix)
                # - this resuts in a row matrix of corresponding overflowed binary numbers - ...
 ==n]           # ... equal input n

```

---

Longer but faster and without additional leading zeros:

### , 93 bytes

Or **\>=4.1, 86 bytes** by replacing the word `function` with `\`.

```
function(n,c,g=t(expand.grid(rep(list(0:c),b<-log2(n)%/%1+1))))"if"(n,g[,2^(b:1-1)%*%g==n],0)

```

Try it online!
> 7 votes

# Answer
# , 26 24 bytes

```
]((=#.)#])((##:i.@^~)>:)

```

Try it online!

Brute force. In this case, the idea is simple -- just try all possible combos and filter the ones which match `n` -- but the J mechanics are kind of fun: The whole thing is fork, made up of nested forks and dyadic hooks:
> 6 votes

# Answer
# Wolfram Language (Mathematica), 52 bytes

```
Cases[FrobeniusSolve[2^Range[#,0,-1],#],s_/;s#2]&

```

Try it online!

-3 bytes thanks to @att.
> 5 votes

# Answer
# Charcoal, 20 bytes

```
ＩΦＥ↨↨⊕θ²⊕η↨ι⊕η⁼Ｉθ↨ι²

```

Try it online! Link is to verbose version of code. Output removes all leading zeros even for an output of zero (which is simply empty). Uses brute force but easily manages the last test case on TIO. Explanation:

```
      θ                 First input `n`
     ⊕                  Incremented
    ↨                   Converted to base
       ²                Literal `2`
   ↨                    Interpreted as base
         η              Second input `c`
        ⊕               Incremented
  Ｅ                     Map over implicit range
           ι            Current value
          ↨             Converted to base
             η          Second input `c`
            ⊕           Incremented
 Φ                      Filtered where
                  ι     Current base `c+1` value
                 ↨      Interpreted as base
                   ²    Literal `2`
              ⁼         Equals
                θ       First input `n`
               Ｉ        Cast to integer
Ｉ                       Cast to string
                        Implicitly print

```

Technically it would be more efficient to convert `n` into base `2` and from base `c+1` first before incrementing but this is code golf.
> 3 votes

# Answer
# Python 3.8 (pre-release), 92 bytes

```
f=lambda n,a,*i:n and f(n//2,a,n%2,*i)+(()<i<(a-1,)and f(n-1,a,i[0]+2,*i[1:])or[])or[[0,*i]]

```

Try it online!

Straight-forward recursion.
> 3 votes

# Answer
# Vyxal `RM`, 7 bytes

```
›ÞẊ'B¹=

```

Try it Online!

The `R` flag automatically converts ranges to digits. The `M` flag changes the default range from 1...n to 0...n.

```
›ÞẊ     # Cartesian power - 0...c combinations to length n
   '    # Filtered by...
    B   # Binary
      = # Equal to
     ¹  # n?

```

Luckily, Vyxal has the same ~~bug~~ feature as Jelly of automatically converting overflowed binary.
> 3 votes

# Answer
# JavaScript (SpiderMonkey), 80 bytes

```
c=>g=(n,t,i=c-(c+n&1))=>n?n*i<0?[]:g(n-i>>1,t?i+[,t]:[i])+g(n,t,i-2):print(t||0)

```

Try it online!

---

# JavaScript (Node.js), 79 bytes

```
c=>g=(n,t=[],i=c-(c+n&1))=>n?n*i<0?[]:[...g(n-i>>1,[i,...t]),...g(n,t,i-2)]:[t]

```

Try it online!
> 3 votes

# Answer
# 05AB1E, 7 bytes

```
Ýsãʒ2βQ

```

Try it online!
> 3 votes

# Answer
# JavaScript (V8), 84 bytes

Expects `(c)(n)` and prints all solutions as space-separated strings.

```
c=>g=(n,j,o,h=i=>~i&&g(n-(i<<j),-~j,i+' '+[o])|h(i-1))=>(n>>j)>0?h(c):n||print(o||0)

```

Try it online!
> 2 votes

# Answer
# Python 3, ~~81~~ 79 bytes

```
f=lambda a,b:[[]][a:]or[d+[i]for i in range(a,-1,-2)for d in(i<=b)*f(a-i>>1,b)]

```

Try it online!

Outputs without leading zeroes.
> 2 votes

---
Tags: code-golf, number, combinatorics, binary, base-conversion
---