title: Too Fast, Too Fourier: FFT Code Golf

text:
# Question
Title: Too Fast, Too Fourier: FFT Code Golf
Implement the Fast Fourier Transform in the fewest possible characters.

Rules:

* Shortest solution wins
* It can be assumed that the input is a 1D array whose length is a power of two.
* You may use the algorithm of your choice, but the solution must actually be a Fast Fourier Transform, not just a naive Discrete Fourier Transform (that is, it must have asymptotic computation cost of \\$O(N \log N)\\$)
* the code should implement the standard forward Fast Fourier Transform, the form of which can be seen in equation (3) of this Wolfram article,

$$F\_n = \sum\_{k=0}^{N-1}f\_ke^{-2\pi ink/N}$$

* Using an FFT function from a pre-existing standard library or statistics package is not allowed. The challenge here is to succinctly *implement* the FFT algorithm itself.

# Answer
> 12 votes
# Mathematica, 95 bytes

Another implementation of the Cooley–Tukey FFT with help from @chyaong.

```
{n=Length@#}~With~If[n>1,Join[+##,#-#2]&[#0@#[[;;;;2]],#0@#[[2;;;;2]]I^Array[-4#/n&,n/2,0]],#]&

```

### Ungolfed

```
FFT[x_] := With[{N = Length[x]},
  If[N > 1,
    With[{a = FFT[ x[[1 ;; N ;; 2]] ],
          b = FFT[ x[[2 ;; N ;; 2]] ] * Table[E^(-2*I*Pi*k/N), {k, 0, N/2 - 1}]},
      Join[a + b, a - b]],
    x]]

```

# Answer
> 9 votes
# Python, 166 151 150 characters

This uses the radix-2 Cooley-Tukey FFT algorithm

```
from math import*
def F(x):N=len(x);t=N<2or(F(x[::2]),F(x[1::2]));return N<2and x or[
a+s*b/e**(2j*pi*n/N)for s in[1,-1]for(n,a,b)in zip(range(N),*t)]

```

Testing the result

```
>>> import numpy as np
>>> x = np.random.random(512)
>>> np.allclose(F(x), np.fft.fft(x))
True

```

# Answer
> 9 votes
# J, 37 bytes

```
_2&(0((+,-)]%_1^i.@#%#)&$:/@|:]\)~1<#

```

An improvement after a few years. Still uses the Cooley-Tukey FFT algorithm.

Saved 4 bytes using *e*<sup>*πi*</sup> = -1, thanks to @Leaky Nun.

Try it online!

## Usage

```
   f =: _2&(0((+,-)]%_1^i.@#%#)&$:/@|:]\)~1<#
   f 1 1 1 1
4 0 0 0
   f 1 2 3 4
10 _2j2 _2 _2j_2
   f 5.24626 3.90746 3.72335 5.74429 4.7983 8.34171 4.46785 0.760139
36.9894 _6.21186j0.355661 1.85336j_5.74474 7.10778j_1.13334 _0.517839 7.10778j1.13334 1.85336j5.74474 _6.21186j_0.355661

```

## Explanation

```
_2&(0((+,-)]%_1^i.@#%#)&$:/@|:]\)~1<#  Input: array A
                                    #  Length
                                  1<   Greater than one?
_2&(                            )~     Execute this if true, else return A
_2                            ]\         Get non-overlapping sublists of size 2
    0                       |:           Move axis 0 to the end, equivalent to transpose
                          /@             Reduce [even-indexed, odd-indexed]
                       &$:               Call recursively on each
                   #                     Get the length of the odd list
                i.@                      Range from 0 to that length exclusive
                    %#                   Divide each by the odd length
             _1^                         Compute (-1)^x for each x
           ]                             Get the odd list
            %                            Divide each in that by the previous
       +                                 Add the even values and modified odd values
         -                               Subtract the even values and modified odd values
        ,                                Join the two lists and return

```

# Answer
> 6 votes
## Python 3: 140 134 113 characters

Short version - short and sweet, fits in a tweet (with thanks to miles):

```
from math import*
def f(v):
 n=len(v)
 if n<2:return v
 a,b=f(v[::2])*2,f(v[1::2])*2;return[a[i]+b[i]/1j**(i*4/n)for i in range(n)]

```

(In Python 2, `/` is truncating division when both sides are integers. So we replace `(i*4/n)` by `(i*4.0/n)`, which bumps the length to 115 chars.)

Long version - more clarity into the internals of the classic Cooley-Tukey FFT:

```
import cmath
def transform_radix2(vector):
    n = len(vector)
    if n <= 1:  # Base case
        return vector
    elif n % 2 != 0:
        raise ValueError("Length is not a power of 2")
    else:
        k = n // 2
        even = transform_radix2(vector[0 : : 2])
        odd  = transform_radix2(vector[1 : : 2])
        return [even[i % k] + odd[i % k] * cmath.exp(i * -2j * cmath.pi / n) for i in range(n)]

```

# Answer
> 5 votes
### R: 142 ~~133~~ ~~99~~ 95 bytes

Thanks to @Giuseppe for helping me shaving down ~~32~~ 36 bytes!

```
f=function(x,n=sum(x|1),y=1:(n/2)*2)`if`(n>1,f(x[-y])+c(b<-f(x[y]),-b)*exp(-2i*(y/2-1)*pi/n),x)

```

An additional trick here is to use the main function default arguments to instantiate some variables.
Usage is still the same:

```
x = c(1,1,1,1)
f(x)
[1] 4+0i 0+0i 0+0i 0+0i

```

**4-year old version at 133 bytes:**

```
f=function(x){n=length(x);if(n>1){a=Recall(x[seq(1,n,2)]);b=Recall(x[seq(2,n,2)]);t=exp(-2i*(1:(n/2)-1)*pi/n);c(a+b*t,a-b*t)}else{x}}

```

With indentations:

```
f=function(x){
    n=length(x)
    if(n>1){
        a=Recall(x[seq(1,n,2)])
        b=Recall(x[seq(2,n,2)])
        t=exp(-2i*(1:(n/2)-1)*pi/n)
        c(a+b*t,a-b*t)
        }else{x}
    }

```

It uses also Cooley-Tukey algorithm. The only tricks here are the use of function `Recall` that allows recursivity and the use of R vectorization that shorten greatly the actual computation.

Usage:

```
x = c(1,1,1,1)
f(x)
[1] 4+0i 0+0i 0+0i 0+0i

```

# Answer
> 4 votes
## Python, 134

This borrows heavily from jakevdp's solution, so I've set this one to a community wiki.

```
from math import*
F=lambda x:x*(len(x)<2)or[a+s*b/e**(2j*pi*n/len(x))for s in(1,-1)for n,(a,b)in
enumerate(zip(F(x[::2]),F(x[1::2])))]

```

Changes:

-12 chars: kill `t`.

```
def F(x):N=len(x);t=N<2or(F(x[::2]),F(x[1::2]));return ... in zip(range(N),*t)]
def F(x):N=len(x);return ... in zip(range(N),F(x[::2]),F(x[1::2]))]

```

-1 char: exponent trick, `x*y**-z == x/y**z` (this could help some others)

```
...[a+s*b*e**(-2j*pi*n/N)...
...[a+s*b/e**(2j*pi*n/N)...

```

-2 char: replace `and` with `*`

```
...return N<2and x or[
...return x*(N<2)or[

```

+1 char: `lambda`ize, killing `N`

```
def F(x):N=len(x);return x*(N<2)or[a+s*b/e**(2j*pi*n/N) ... zip(range(N) ...
F=lambda x:x*(len(x)<2)or[a+s*b/e**(2j*pi*n/len(x)) ... zip(range(len(x)) ...

```

-2 char: use `enumerate` instead of `zip(range(len(`

```
...for(n,a,b)in zip(range(len(x)),F(x[::2]),F(x[1::2]))]
...for n,(a,b)in enumerate(zip(F(x[::2]),F(x[1::2])))]

```

# Answer
> 4 votes
# C, 259

```
typedef double complex cplx;
void fft(cplx buf[],cplx out[],int n,int step){
if(step < n){
fft(out, buf,n, step * 2);
fft(out+step,buf+step,n,step*2);
for(int i=0;i<n;i+=2*step){
cplx t=cexp(-I*M_PI*i/n)*out[i+step];
buf[i/2]=out[i]+t;
buf[(i+n)/2]=out[i]-t;
}}}

```

The problem is, such implementations are useless, and straightforward algorithm is MUCH faster.

# Answer
> 3 votes
# Matlab, ~~128~~ ~~118~~ ~~107~~ ~~102~~ ~~101~~ ~~94~~ 93 bytes

EDIT6: thanks @algmyr for another byte!

```
function Y=f(Y);
n=numel(Y);
k=2:2:n;
if k;
   c=f(Y(k-1));
   d=f(Y(k)).*i.^(2*(2-k)/n);
   Y=[c+d;c-d];
end

```

EDIT5: Still getting shorter:) thanks to @sanchises

```
function Y=f(Y)
n=numel(Y);
k=2:2:n;
if k;
   c=f(Y(k-1));
   d=f(Y(k)).*(-1).^((2-k)/n);
   Y=[c+d;c-d];
end

```

EDIT4: Yay, -1 character more (could aslo have done without the `k`):

```
function Y=f(Y)
n=numel(Y);
if n>1;
   k=2:2:n;
   c=f(Y(k-1));
   d=f(Y(k)).*(-1).^((k/2-1)*2/n)';
   Y=[c+d;c-d];
end

```

EDIT2/3: Thanks for @sanchises for further improvements!

```
function Y=f(Y)
n=numel(Y);
if n>1;
   c=f(Y(1:2:n));
   d=f(Y(2:2:n)).*(-1).^(-(0:n/2-1)*2/n).';
   Y=[c+d;c-d];
end

```

EDIT: Could make some improvements, and noticed that the scaling constant is not required.

This is the expanded version, character count is valid if you remove the newlines/spaces. (Works only for column vectors.)

```
function y=f(Y)
n=numel(Y);
y=Y;
if n>1;
   c=f(Y(1:2:n));
   d=f(Y(2:2:n));
   n=n/2;
   d=d.*exp(-pi*i*(0:n-1)/n).';
   y=[c+d;c-d];
end

```

# Answer
> 2 votes
# Jelly, ~~31~~ ~~30~~ ~~28~~ 26 bytes

```
LḶ÷$N-*×,N$+ḷF
s2Zß€ç/µ¹Ṗ?

```

This uses the Cooley-Tukey radix-2 recursive algorithm. For an un-golfed version, see my answer in Mathematica.

Try it online or Verify multiple test cases.

## Explanation

```
LḶ÷$N-*×,N$+ḷF  Helper link. Input: lists A and B
L               Get the length of A
   $            Operate on that length
 Ḷ                Make a range [0, 1, ..., length-1]
  ÷               Divide each by length
    N           Negate each
     -          The constant -1
      *         Compute -1^(x) for each x in that range
       ×        Multiply elementwise between that range and B, call it B'
          $     Operate on that B'
         N        Negate each
        ,         Make a list [B', -B']
            ḷ   Get A
           +    Add vectorized, [B', -B'] + A = [A+B', A-B']
             F  Flatten that and return

s2Zß€ç/µ¹Ṗ?  Main link. Input: list X
         Ṗ   Curtail - Make a copy of X with the last value removed
          ?  If that list is truthy (empty lists are falsey)
       µ       Parse to the left as a monad
s2             Split X into sublists of length 2
  Z            Transpose them to get [even-index, odd-index]
   ß€          Call the main link recursively on each sublist
     ç/        Call the helper link as a dyad on the sublists and return
             Else
        ¹      Identity function on X and return

```

# Answer
> 2 votes
# C (gcc), ~~188 186 184~~ 183 bytes

```
#define d(a,b,c)f(a,b,c,1,0)
f(a,b,c,n,k)_Complex*a,*b;{_Complex z[c];*b=*a;if(n<c)for(f(a,z,c,n*2),f(a+n,z+n,c,n*2);k<c;k+=n*2)b[k+c>>1]=z[k]*2-(b[k/2]=z[k]+z[k+n]/cpow(1i,2.*k/c));}

```

Try it online!

Slightly golfed less

```
#define d(a,b,c)f(a,b,c,1,0)
f(a,b,c,n,k)_Complex*a,*b;{
  _Complex z[c];
  *b=*a;
  if(n<c)
    for(f(a,z,c,n*2),f(a+n,z+n,c,n*2);k<c;k+=n*2)
      b[k+c>>1]=z[k]*2-(b[k/2]=z[k]+z[k+n]/cpow(1i,2.*k/c));
}

```

# Answer
> 1 votes
# Pari/GP, 76 characters

```
X(v)=my(t=-2*Pi*I/#v,s);vector(#v,k,s=t*(k-1);sum(n=0,#v-1,v[n+1]*exp(s*n)))

```

Usage

```
X([1,1,1,1])
%2 = [4.000000000000000000000000000, 0.E-27 + 0.E-28*I, 0.E-28 + 0.E-27*I, 0.E-27 + 0.E-28*I]

```

# Answer
> 1 votes
# Octave, ~~109 103 101~~ 100 bytes

```
f(f=@(f)@(x,n=rows(x)){@(d=f(f)(x(k=2:2:n)).*i.^((k*2-4)/n)')[d+(c=f(f)(x(k-1)));c-d],x}{1+(n<2)}())

```

Try it online!

Ooooo do my eyes bleed from this ~~recursive~~ accursed lambda. Large parts of this were lifted from @flawr's answer.

```
f(                                          % lambda function
  f=@(f)                                    % defined in its own argument list,
                                            % accepts itself as parameter (for recursion)
    @(x,n=rows(x)){                         % calls another lambda,
                                            % 2nd parameter is just to define a variable
      @(d=f(f)(x(k=2:2:n)).*i.^((k*2-4)/n)')% 1/4 of FFT (argument just defines a variable)
        [d+(c=f(f)(x(k-1)));                % 2/4 of FFT
         c-d                                % 4/4 of FFT
        ],                                  % This is in a @()[] to inhibit evaluation
                                            % unless actually called
      x                                     % FFT of length 1
    }{1+(n<2)}                              % if len(x)==1, return x
                                            % else return [d+c;c-d]
  ()                                        % this is probably important too
)

```

# Answer
> 1 votes
# APL(NARS), 58 chars, 116 bytes

```
{1≥k←≢⍵:⍵⋄(∇⍵[y∼⍨⍳k])(+,-)(∇⍵[y←2×⍳t])×0J1*t÷⍨2-2×⍳t←⌊k÷2}

```

test

```
  f←{1≥k←≢⍵:⍵⋄(∇⍵[y∼⍨⍳k])(+,-)(∇⍵[y←2×⍳t])×0J1*t÷⍨2-2×⍳t←⌊k÷2}
  f 1 1 1 1
4J0 0J0 0J0 0J0
  f 1 2 3 4
10J0 ¯2J2 ¯2J0 ¯2J¯2
  f 1J1 2 ¯2J1  9
10J2 3J7 ¯12J2 3J¯7
  f 5.24626,3.90746,3.72335,5.74429,4.7983,8.34171,4.46785,0.760139
36.989359J0 ¯6.211855215J0.3556612739 1.85336J¯5.744741 7.107775215J¯1.133338726 ¯0.517839J0
  7.107775215J1.133338726 1.85336J5.744741 ¯6.211855215J¯0.3556612739

```

# Answer
> 0 votes
# Axiom,  ~~259~~, ~~193~~, ~~181~~, 179 bytes

```
L(g,n,f)==>[g for i in 1..n|f]
h(a)==(n:=#a;n=1=>a;c:=h(L(a.i,n,odd? i));d:=h(L(a.i,n,even? i));n:=n/2;t:=1>0;v:=L(d.i*%i^(-2*(i-1)/n),n,t);append(L(c.i+v.i,n,t),L(c.i-v.i,n,t)))

```

Even if h(a) could pass all the test and would be ok as entry for this 'competition' one has to call h() or hlp() thru fft() below, for *checking arguments*. I don't know if this software can be ok because i only had seen what other wrote, and search the way it could run in Axiom for return some possible right result. Below ungolfed code with few comments:

```
-- L(g,n,f)==>[g for i in 1..n|f]
-- this macro L, build one List from other list, where in g, there is the generic element of index i
-- (as a.i, or a.i*b.i or a.i*4), n build 1..n that is the range of i, f is the condition
-- for insert the element in the list result.

hlp(a)==
    n:=#a;n=1=>a
    -- L(a.i,n,odd? i)  it means build a list getting "even indices i of a.i as starting from index 0" [so even is odd and odd is even]
    -- L(a.i,n,even? i) it means build a list getting "odd  indices i of a.i as starting from index 0"
    c:=hlp(L(a.i,n,odd? i));d:=hlp(L(a.i,n,even? i))
    n:=n/2;t:=1>0
    v:=L(d.i*%i^(-2*(i-1)/n),n,t)
    append(L(c.i+v.i,n,t),L(c.i-v.i,n,t))

-- Return Fast Fourier transform of list a, in the case #a=2^n
fft(a)==(n:=#a;n=0 or gcd(n,2^30)~=n=>[];hlp(a))

(5) -> h([1,1,1,1])
   (5)  [4,0,0,0]
                                    Type: List Expression Complex Integer
(6) -> h([1,2,3,4])
   (6)  [10,- 2 + 2%i,- 2,- 2 - 2%i]
                                    Type: List Expression Complex Integer
(7) -> h([5.24626,3.90746,3.72335,5.74429,4.7983,8.34171,4.46785,0.760139])
   (7)
   [36.989359, - 6.2118552150 341603904 + 0.3556612739 187363298 %i,
    1.85336 - 5.744741 %i, 7.1077752150 341603904 - 1.1333387260 812636702 %i,
    - 0.517839, 7.1077752150 341603904 + 1.1333387260 812636702 %i,
    1.85336 + 5.744741 %i,
    - 6.2118552150 341603904 - 0.3556612739 187363298 %i]
                                      Type: List Expression Complex Float
(8) -> h([%i+1,2,%i-2,9])
   (8)  [10 + 2%i,3 + 7%i,- 12 + 2%i,3 - 7%i]
                                    Type: List Expression Complex Integer

```

in the few i had seen h() or fft() would return exact solution, but if the simplification is not good as in:

```
(13) -> h([1,2,3,4,5,6,7,8])
   (13)
                    +--+                                   +--+
        (- 4 + 4%i)\|%i  - 4 + 4%i             (- 4 - 4%i)\|%i  - 4 + 4%i
   [36, --------------------------, - 4 + 4%i, --------------------------, - 4,
                    +--+                                   +--+
                   \|%i                                   \|%i
            +--+                                   +--+
    (- 4 + 4%i)\|%i  + 4 - 4%i             (- 4 - 4%i)\|%i  + 4 - 4%i
    --------------------------, - 4 - 4%i, --------------------------]
                +--+                                   +--+
               \|%i                                   \|%i
                                    Type: List Expression Complex Integer

```

than it is enought change the type of only one element of list, as in below writing 8. (Float) for find the approximate solution:

```
(14) -> h([1,2,3,4,5,6,7,8.])
   (14)
   [36.0, - 4.0000000000 000000001 + 9.6568542494 923801953 %i, - 4.0 + 4.0 %i,
    - 4.0 + 1.6568542494 92380195 %i, - 4.0, - 4.0 - 1.6568542494 92380195 %i,
    - 4.0 - 4.0 %i, - 4.0 - 9.6568542494 923801953 %i]
                                      Type: List Expression Complex Float

```

I wrote it, seen all other answers because in the link, the page it was too much difficult so I don't know if this code can be right. I'm not one fft expert so all this can (it is probable) be wrong.

---
Tags: code-golf, math, complex-numbers
---


# Question
Title: Injection from two strings to one string
## Challenge

Write a program that applies an injective function which takes an ordered pair of strings as input and one string as output. In other words, each input must map to a unique output.

## Specifics

* The input may be *any* two strings of arbitrary length, but will consist only of printable ASCII characters (codes \\$\[32, 126\]\\$).
* Similarly, the output string has no length restriction, but it must consist only of printable ASCII characters.
* If your language can't handle arbitrary-length strings, the program may merely work *theoretically* for strings of any size.
* The mapping from inputs to outputs should be consistent between executions of the program. Otherwise, the mapping you use is completely up to you, as long as it is an injection.
* The input is ordered. If the two input strings are different, they should produce a different output than if they were swapped. \\$s \neq t \implies f(s, t) \neq f(t, s)\\$
* Not every string needs to be a possible output.
* The shortest answer in each language wins!

## Test cases

The following inputs should all result in different outputs. To avoid confusion, strings are surrounded by guillemets («») and separated by single spaces.

```
«hello» «world»
«lelho» «drowl»
«diffe» «_rent»
«notth» «esame»

«Code» «Golf»
«Co» «deGolf»
«CodeGolf» «»

«» «»
«» « »
« » «»
« » «  »
«  » « »

«abc", » «def»
«abc» «, "def»
«abc' » «'def»
«abc'» « 'def»

«\» «"»
«\\» «\"»

```

# Answer
## brainfuck, ~~30~~ ~~29~~ ~~27~~ 23 bytes

```
,[-[+.>]-[>+<---]>.-.,]

```

Try it online!

Inputs are separated by a `0x01` byte.

This turns `["foo", "bar"]` into `fUToUToUTUTbUTaUTrUT`. To recover the original two strings, take groups of 3 characters, find the one where the second letter isn't `U`, and split there.
> 18 votes

# Answer
# JavaScript (ES6), 14 bytes

Takes input as an array of 2 strings. Inspired by Luis' answer.

```
JSON.stringify

```

Try it online!

---

# JavaScript (ES6),  ~~21~~  20 bytes

Takes input as `(a)(b)`.

```
a=>b=>[a.length,a]+b

```

Try it online!

Returns the length of \\$a\\$, followed by a comma, followed by the concatenation of \\$a\\$ and \\$b\\$.
> 17 votes

# Answer
## jq -c, 0 bytes

Try it online!

This definitely feels like cheating...? But it seems to comply with the rules of the challenge.

By default, `jq` will output its input in a human-readable JSON format. The `-c` (compact) flag tells `jq` to output in "compact" style, which removes the newlines (since the challenge forbids non-printable ASCII).
> 15 votes

# Answer
# Python 3, 3 bytes

```
str

```

A (built-in) function which, given a list of the two strings, gives a string representation of the list

**Try it online!**
> 7 votes

# Answer
# Japt `-S`, 3 bytes

I *still* feel I must be missing something here ...

```
®mc

```

Try it

Possibly 2 bytes:

```
mq

```

Try it

Or stretching it with this 1-byter:

```
U

```

Try it

The first version maps each string in the array to its codepoints and outputs them joined with a space.

The second version splits each string to a character array and outputs them joined with a space.

And the third version, which feels like cheating, just outputs the input with the `-Q` flag doing the heavy lifting of `srringify`ing it.
> 5 votes

# Answer
# Pyth, 4 bytes

```
jNmC

```

Try it online!

This converts each string to base 256 and then joins them in order with a `"`. Since the results are each numbers the `"` unambiguously separates them and the original strings can be recovered with `mCsdczN`.
> 5 votes

# Answer
## Haskell, 4 bytes

```
show

```

The Haskell built-in to turn things into strings. The input is taken as a pair of strings.

Try it online!
> 5 votes

# Answer
# T-SQL, 38 bytes

```
SELECT QUOTENAME(a)+QUOTENAME(b)FROM i

```

Input is taken from a pre-existing table \\$i\\$ with `varchar` fields \\$a\\$ and \\$b\\$, per our IO rules.

Uses `QUOTENAME`, which surrounds the strings with `[]` and also escapes any internal brackets. Should map to a unique output.
> 4 votes

# Answer
# Zsh, 7 bytes

```
<<<$@:q

```

Try it online!

Implicitly joins the arguments on spaces. The `q` modifier tells zsh to quote the arguments, which crucially escapes spaces, ensuring an unescaped space unambiguously separates the two arguments.

(Without `q`, `"a " "b"` and `"a" " b"` would both yield `"a b"`.)
> 4 votes

# Answer
# MATL, 1 byte

```
j

```

The code takes an array of two strings as input, and outputs a string representation of that array.

Try it online!

### Explanation

The code simply reads the input as a string, unevaluated.
> 3 votes

# Answer
# Jelly, 2 bytes

```
ŒṘ

```

A monadic Link accepting a list of two lists of characters as its argument which yields a single list of characters.

**Try it online!**

### How?

It's a built-in to get Python's string representation, simples.
> 3 votes

# Answer
# C# with 26 bytes (thanks to Lukas Lang, Kevin Cruijssen and Jo King)

```
a=>b=>$"{a.Length}.{a}{b}"

```

tio.run lambda
> 3 votes

# Answer
# 05AB1E, 2 bytes

```
₁ö

```

Try it online! Interprets each string as a base-256 integer, then prints the two in the form `[1, 2]`.

---

## 05AB1E, 1 byte (unknown validity)

```
â

```

Try it online!

Takes the cartesian product of the input with itself. Quotes in the input are not escaped, which could cause confusion. I brute-forced all combinations of up to 12 `", "` and `"], ["` and didn’t find any collision; however, I can’t prove there aren’t any collisions for longer strings. If anybody can come up with a proof or counter-example, I’d highly appreciate it!

The trivial 0-byter fails because of quotes not being escaped: inputs (`", "`, empty string) and (empty string, `", "`) both yield the output `["", "", ""]`.

The 1-byter `º` (mirror each input string) also fails because of this: inputs (`", "" ,"`, empty string) and (empty string, `" ,"", "`) both yield the output `["", "" ,"", "" ,"", ""]`.
> 3 votes

# Answer
# Charcoal, 12 bytes

```
⪫Ｅ²⭆⪪Ｓ"⪫""λ,

```

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

```
 Ｅ²             Repeat twice
     Ｓ          Input a string
    ⪪ "         Split it on `"`s
   ⭆            Map over each piece and join
       ⪫""λ     Wrap each piece in `"`s
⪫          ,    Join the two results with a `,`
                Implicitly print

```
> 2 votes

# Answer
# PowerShell, 22 bytes

Many fixes thanks to mazzy

```
"$($args|% le*)"+$args

```

Try it online!

Take five, oh my.
> 2 votes

# Answer
# , 4 bytes

```
dput

```

Try it online!

A built-in function which returns the string representation of the input (inspired by Jonathan Allan's answer )
> 2 votes

# Answer
# Wolfram Language (Mathematica), 8 bytes

```
Compress

```

Try it online!
> 1 votes

# Answer
# Perl 6, ~~6~~ 3 bytes

```
&dd

```

Try it online!

Outputs the object representation to STDERR.
> 1 votes

# Answer
# CSS + HTML, 55 + 20 = 75 bytes

Provide the inputs in the HTML after `<code>` tags. Visually injects letters one by one from each input into the output. When an input is longer than the other one, visual spaces are shown for missing letter(s) of the shorter input. Also one comma is added in HTML to force visual output uniqueness (I hope).

```
*{position:absolute;letter-spacing:9px}code>code{left:9px
```

```
<code>abcdefg<code>hijklmn</code>,
```
> 1 votes

# Answer
# C# (Visual C# Interactive Compiler), 5 bytes

```
Print

```

Try it online!
> 1 votes

# Answer
# Lua, 27 bytes

```
print(('%q%q'):format(...))

```

Try it online!

Full program, take input as arguments.

Inspired by zsh answer, as it also use `%q` modifier to use internal safe-string engine.

Also, I can think of just

```
('%q%q'):format

```

but I'm not sure if this is acceptable answer.
> 1 votes

# Answer
# sed, 19 bytes

```
N
s/ /. /g
s/\n/: /

```

Try it online!

```
N          # append the second string into the pattern space
s/ /. /g   # prefix all spaces with ".". Now ": " will not occur in the stiring
s/\n/: /   # replace the newline with ": "

```
> 1 votes

# Answer
# JavaScript (SpiderMonkey), 6 bytes

```
uneval

```

Try it online!

Input array of strings, output a single string.

Inspired by Arnauld's JSON.stringify answer.
> 1 votes

# Answer
# C (gcc), 59 bytes

Thanks to Grimy for the suggestion.

Takes an array of input strings (of which "2" is the correct number for this challenge) and prints their character values, including the trailing `NUL`. Technically, the `%p` formatter used by `printf` is for pointers, but it works fine for displaying hex values of arbitrary integers if you're not picky about how they look!

```
f(s,t)char**s,*t;{for(;t=*s++;)for(;printf("%p",*t++)^5;);}

```

Try it online!
> 1 votes

# Answer
# Brachylog, 0 bytes

Input as an array of 2 strings, output in the format: `Z = ["{{string 1 stringified}}","{{string 2 stringified}}"]`

Inspired by Arnauld's JSON.stringify answer and Doorknob's empty jq answer

Try it online!
> 1 votes

# Answer
# PHP, 9 bytes

```
serialize

```

Try it online!

Input is an array of 2 strings like this: `['abc', 'def']`. Uses PHP's serialize to serialize the input into a string.
> 0 votes

# Answer
# Bash, 11 bytes

```
echo ${@@Q}

```

Try it online!

`${parameter@Q}` quotes the parameter for reuse as input. In the case of an array, it quotes each element.
> 0 votes

# Answer
# Ruby, 12 bytes

```
->*a{a.to_s}

```

Try it online!
> 0 votes

---
Tags: code-golf, string, open-ended-function
---


# Question
Title: List where pinballs would exit a grid of bumpers from different entrance points
Inspired by this lumosity mini game, Pinball Recall

We start with a rectangular grid (viewed from above) with several bumpers as follows. Entrances/exits are numbered counter-clockwise starting from the leftmost of the bottom of the grid, as number 0.

```
   24 23 22 21 20 19 18 17 16 15
25  .  .  .  .  .  /  .  .  .  . 14
26  .  .  .  .  .  .  .  .  .  . 13
27  .  /  \  .  .  \  .  .  \  . 12
28  .  .  .  .  .  .  .  .  .  . 11
29  .  .  .  .  .  .  /  .  .  . 10
    0  1  2  3  4  5  6  7  8  9

```

Pinballs can be fired from each entrance into the grid at a direction perpendicular to the grid wall, e.g. in the above example:

* 0 to 9: fired upwards
* 10 to 14: fired to the left
* 15 to 24: fired downwards
* 24 to 29: fired to the right

The pinballs will move in a straight line until they reach an exit, or a bumper, in which case the ball will bounce off the bumper and change direction. So in above diagram,

* from 0, ball goes straight to 24
* from 1, ball goes up to / and bounces off to reach \\, then bounces off again and ends up at 2
* from 10, ball goes left to / and bounces off to 6

**Inputs**

Program shall receive the grid width and height. Then program receives the bumper orientation (represented as / or \\) followed by coordinates, which also start from 0 from bottom left, e.g.

```
 4  .  .  .  .  .  .  .  .  .  .
 3  .  .  .  .  .  .  .  .  .  .
 2  .  .  .  .  .  .  .  .  .  .
 1  .  .  .  .  .  .  .  .  .  .
 0  .  .  .  .  .  .  .  .  .  .
    0  1  2  3  4  5  6  7  8  9

```

"done" keyword used to indicate end of input

*edit:* as suggested by ngn, program may receive list of bumper coordinates instead so the "done" keyword is not needed

**Output**

Program should print out the exit locations of a pinball if they are fired from 0 to the last entrance of grid, in above case, 0 to 29

**Sample input and output**

Input

```
10 5
/ 1 2 / 5 4 / 6 0 \ 2 2 \ 5 2 \ 8 2
done

```

Output

```
24 2 1 21 20 22 10 17 14 15 6 28 16 26 8 9 12 7 29 25 4 3 5 27 0 19 13 23 11 18

```

**Leaderboard (as of 20Oct2019)**

1. Neil, Charcoal, 133 bytes
2. Arnauld, JavaScript (ES6), 212 bytes
3. Embodiment of Ignorance, C# (Visual C# Interactive Compiler), 277 bytes
4. Chas Brown, Python 2, 290 bytes

*edit:* FryAmTheEggman points out a similar question to try

# Answer
> 7 votes
# JavaScript (ES6),  ~~218 215 213~~  212 bytes

Takes input as `(w,h,o)` where \\$o\\$ is an object whose keys are the coordinates of the bumpers in `'x,y'` format and whose values are either `'/'` or `'\'`.

```
(w,h,o)=>(A=[...Array(w+h<<1)].map((_,n)=>(p=n-w)<0?[n,-1,3]:p<h?[w,p]:(p-=w)<h?[h+~p,h,1]:[-1,2*h+~p,2])).map(g=([x,y,d])=>A.every(([X,Y])=>X-x|Y-y&&++i,(c=o[[x+=~-d%2,y+=~-~-d%2]])?d^=c<{}||3:i=0)?g([x,y,d]):i)

```

Try it online!

### Commented

We first create an array \\$A\[\\:\]\\$ of tuples \\$\[x, y, d\]\\$ where \\$(x, y)\\$ is the starting position along the borders of the playfield and \\$d\\$ is the initial direction.

```
( A = [...Array(w + h << 1)]  // create an array A[] of (w + h) * 2 items
  .map((_, n) =>              // for each item at position n in A[]:
    (p = n - w) < 0 ?         //   set p = n - w; if this is the bottom side:
      [n, -1, 3]              //     start at (n, -1) in direction 3
    :                         //   else:
      p < h ?                 //     if this is the right side:
        [w, p]                //       start at (w, p) in direction 0 (implicit)
      :                       //     else:
        (p -= w) < h ?        //       subtract w from p; if this is the top side:
          [h + ~p, h, 1]      //         start at (h + ~p, h) in direction 1
        :                     //       else (left side):
          [-1, 2 * h + ~p, 2] //         start at (-1, 2 * h + ~p) in direction 2
  )                           // end of map()
)                             //

```

We then simulate the trajectory of the ball, starting at each position defined above, until it reaches another starting position.

```
.map(g = ([x, y, d]) =>       // for each tuple [x, y, d] in A[]:
  A.every(([X, Y]) =>         //   for each tuple [X, Y] in A[]:
    X - x | Y - y             //     break if (x, y) = (X, Y)
    && ++i,                   //     otherwise, increment i
    ( c =                     //     define c as
        o[[                   //       the bumper character at
          x += ~-d % 2,       //         (x, y), once updated according to d
          y += ~-~-d % 2      //         (0 = West, 1 = South, 2 = East, 3 = North)
        ]]                    //
    ) ?                       //     if c is set:
      d ^= c < {} || 3        //       XOR d with 1 (for '/') or 3 (for '\')
    :                         //     else:
      i = 0                   //       initialize i to 0
  ) ?                         //   end of every(); if truthy:
    g([x, y, d])              //     do a recursive call to move the ball further
  :                           //   else:
    i                         //     we've reached a starting position: yield i
)                             // end of map()

```

# Answer
> 2 votes
# Python 2, ~~317~~ ~~300~~ ~~298~~ 290 bytes

```
def f(w,h,B):
 A=[w*[-1]for c in' '*h];p=w+h
 for x,y,c in B:A[y][x]=c<'0'
 for i in range(2*p):
	x,y,d=[[[(0,2*p+~i,0),(w+p+~i,h-1,1)][i<w+p],(w-1,i-w,3)][i<p],(i,0,2)][i<w]
	while w>x>=0<=y<h:d^=1+A[y][x];x+=[1,0,0,-1][d];y+=[0,-1,1,0][d]
	print[[y+w,2*p+~y][x<0],[w+p+~x,x][y<h]][0<d<3],

```

Try it online!

Takes the bumpers as a list of tuples `(x,y,c)`where `x` and `y` are the coordinates of the bumper and `c` is either `\` or `/`.

# Answer
> 2 votes
# C# (Visual C# Interactive Compiler), 277 bytes

```
(w,h,d)=>{var z=new int[w+h<<1].Select((_,i)=>i<w?(i,-1,3):i<w+h?(w,i-w,0):(i-=w+w)<h?(h+~i,h,1):(-1,h+h+~i,2)).ToList();z.ForEach(x=>{var(a,b,c)=x;do{try{c^=d[(a,b)]<48?1:3;}catch{}a+=~-c%2;b+=(c-2)%2;}while(a>=0&a<w&b>=0&b<h);Print(z.FindIndex(l=>l.Item1==a&l.Item2==b));});}

```

Try it online!

# Answer
> 1 votes
# Charcoal, 133 bytes

```
ＮθＮηＵＯθη.ＷＳ«ＪＮＮι»≔⟦⟧ζＦθ⊞ζ⟦²ι±¹⟧Ｆη⊞ζ⟦⁰θι⟧Ｆθ⊞ζ⟦⁶⁻θ⊕ιη⟧Ｆη⊞ζ⟦⁴±¹⁻η⊕ι⟧Ｆζ«Ｊ§ι¹§ι²≔﹪⁺⁴§ι⁰¦⁸δＭ✳δＷ¬№ζ⟦δⅈⅉ⟧«≡ＫＫ/≦⁻⁶δ\≔﹪⁻χδ⁸δＰωＭ✳δ»⊞υ⌕ζ⟦δⅈⅉ⟧»⎚Ｉυ

```

Try it online! Link is to verbose version of code. Takes input on separate lines with a blank trailing line but for convenience the test case uses spaces instead of newlines. Explanation:

```
ＮθＮηＵＯθη.

```

Input the width and height and draw a box of `.`s of that size. I'm drawing with the origin at the top left but I'm flipping the vertical co-ordinate in all of my calculations so the results will be correct.

```
ＷＳ«ＪＮＮι»

```

Loop over the input list and print the `\` or `/` characters at the relevant positions.

```
≔⟦⟧ζＦθ⊞ζ⟦²ι±¹⟧Ｆη⊞ζ⟦⁰θι⟧Ｆθ⊞ζ⟦⁶⁻θ⊕ιη⟧Ｆη⊞ζ⟦⁴±¹⁻η⊕ι⟧Ｆζ«

```

Build up a list for all of the entry/exit points giving the direction of exit and the coordinates and loop over the list.

```
Ｊ§ι¹§ι²≔﹪⁺⁴§ι⁰¦⁸δＭ✳δ

```

Jump to the exit point, calculate the direction of entry and take a step in that direction.

```
Ｗ¬№ζ⟦δⅈⅉ⟧«

```

Until an exit point is found...

```
≡ＫＫ/≦⁻⁶δ\≔﹪⁻χδ⁸δＰω

```

... adjust the direction if the cursor is over a `/` or `\`...

```
Ｍ✳δ»

```

... and take a step in the current direction.

```
⊞υ⌕ζ⟦δⅈⅉ⟧

```

Remember the found exit point.

```
»⎚Ｉυ

```

Clear the grid and output the list of exit points.

---
Tags: code-golf, number, game
---


title: Solve a System of Linear Equations

text:
# Question
Title: Solve a System of Linear Equations
Write a program to solve a series of linear equations as short as possible. It must solve arbitrary number of equations problems. They can inputted however you like, coefficients of augmented matrix is probably the easiest. The program doesn't have to handle non-integer coefficients or solutions. No degenerate or invalid cases will be tested. The program must output the value of each variable or reduced row echelon form.

No equation solving libraries, matrix functions, or any way to automatically solve is allowed. You can simulate matrices with arrays or lists.

Example input (or equivalent):

```
m={{2,1,-1,8},{-3,-1,2,-11},{-2,1,2,-3}}

```

This represents `2x+y-z=8, -3x-y+2z=-11, -2x+y+2z=-3`

Example output (or equivalent):

```
{2,3,-1}

```

This represents `x=2, y=3, z=-1`

# Answer
> 3 votes
## Python 169 166

**Implementation**

```
def s(a):
 if a:b=a[0];r=s([[x-1.*y*b[0]/r[0]for x,y in zip(b[1:],r[1:])]for r in a[1:]]);return[round((b[-1]-sum(x*y for x,y in zip(b[1:-1],r)))/b[0])]+r
 return[]

```

**Demo**

```
>>> arr=[[2, 1, -1, 8], [-3, -1, 2, -11], [-2, 1, 2, -3]]
>>> s(arr)
[2.0, 3.0, -1.0]

```

**Note**

If you are OK with the float approximation, then you can remove the round function call and further golf to *159* characters

# Answer
> 9 votes
# APL, 1 char

I know it doesn't fit the (revised) requirements, but it's too good not to post:

Symbol "domino"  (division `÷` inside a rectangle) performs matrix division, therefore it can solve any system of linear equations. You just have to put it between the constant term vector and the matrix with the other terms:

```
      8 ¯11 ¯3 ⌹ ⊃(2 1 ¯1)(¯3 ¯1 2)(¯2 1 2)
2 3 ¯1

```

(if you want to try it on TryApl,  is )

# Answer
> 4 votes
## Javascript (284 181) - Gauss Elimination method

```
function f(A){l=A.length;d=1;for(i=0;i+1;i+=d){v=A[i][i];for(k=0;k<l+1;k++)A[i][k]/=v;for(j=i+d;A[j];j+=d)for(k=0,w=A[j][i];k<l+1;k++)A[j][k]-=w*A[i][k];if(i==l-d)d=-1,i=l}return A}

```

**Test**

```
f([[2,1,-1,8],[-3,-1,2,-11],[-2,1,2,-3]]);

=> [[1,0,0,2],[0,1,0,3],[-0,-0,1,-1]]

```

The returned array combine the identity matrix and the solution.

# Answer
> 3 votes
*This answer no longer fits the question after the rule change as it uses a matrix function.**

**Sage, 32**

```
~matrix(input())*vector(input())

```

Sample input:

```
[[2, 1, -1], [-3, -1, 2], [-2, 1, 2]]
[8, -11, -3]

```

Sample output:

```
(2, 3, -1)

```

<sub>\*Arguably, `matrix()` is a typecast, not a function (running `import types; isinstance(matrix, types.FunctionType)` gives `False`). Also, the `~` and `*` are *operators*, not functions.</sub>

# Answer
> 3 votes
# Java - 522 434 228 213 chars

Solves by systematically checking all possible integer n-tuples by direct multiplication until one is found that works.

Function takes augmented matrix, A, trial solution vector, x, and dimension, n, as input - outputs solution vector, x. Note that the vector x is actually one larger than the dimension to help step through possible solutions. (If I declared variables A,x,n,j,k,s as instance variables, the function would be 31 chars shorter - for a total of 182, but that feels like bending the rules too far.)

```
int[]Z(int[][]A,int[]x,int n){int j,k,s;for(;;){for(j=0;j<n;j++){for(k=s=0;k<n;s+=A[j][k]*x[k++]);if(s!=A[j][n])j+=n;}if(j==n)return x;for(j=0;j<=n;j++)if(x[j]!=x[n]||j==n){x[j]++;for(k=0;k<j;x[k++]=-x[n]);j=n;}}}

```

Program for testing (somewhat ungolfed):

```
import java.util.*;
class MatrixSolver{
    public MatrixSolver() {
        Scanner p=new Scanner(System.in); //initialize everything from stdin
        int j,k,n=p.nextInt(),A[][]=new int[n][n+1],x[]=new int[n+1];
        for(j=0;j<n;j++)for(k=0;k<=n;A[j][k++]=p.nextInt());
        x=Z(A,x,n); //call the magic function
        for(j=0;j<n;j++) System.out.print(x[j]+" "); //print the output
    }
    public static void main(String[]args){
        new MatrixSolver();
    }

    int[]Z(int[][]A,int[]x,int n){
        int j,k,s;
        for(;;){
            for(j=0;j<n;j++){ //multiply each row of matrix by trial solution and check to see if it is correct
                for(k=s=0;k<n;s+=A[j][k]*x[k++]);
                if(s!=A[j][n])j+=n;
            }
            if(j==n)return x; //if it is correct return the trial solution
            for(j=0;j<=n;j++)if(x[j]!=x[n]||j==n){//calculate the next trial solution
                x[j]++;
                for(k=0;k<j;x[k++]=-x[n]);
                j=n;
            }
        }
    }
}

```

Program takes input from stdin as space separated integers as follows: first, the dimension of the problem, second, the entries of the augmented matrix by row.

Sample run:

```
$java -jar MatrixSolver.jar
3 2 1 -1 8 -3 -1 2 -11 -2 1 2 -3
2 3 -1

```

I shaved several characters by following Victor's advice about loops and "public", storing the RHS in the augmented matrix instead of separately, and adding an extra entry to my trial solution to simplify the generation of each new trial solution. The OP also said that a function is enough - no need to count the entire program.

# Answer
> 1 votes
# JavaScript (ES6),  ~~152~~  151 bytes

Implementation of Cramer's rule.

Takes input as `(m)(v)`, where \\$m\\$ is the matrix of variable coefficients and \\$v\\$ is the vector of constant terms.

```
m=>v=>m.map((_,i)=>(D=m=>m+m?m.reduce((s,[v],i)=>s+(i&1?-v:v)*D(m.map(([,...r])=>r).filter(_=>i--)),0):1)(m.map((r,y)=>r.map((k,x)=>x-i?k:v[y])))/D(m))

```

Try it online!

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


title: KILL ALIENS NOW!

text:
# Question
Title: KILL ALIENS NOW!
The world has been invaded by aliens. They are everywhere killing people and taking over the world. You are hiding with your friend.

They have one weakness - the **high pitched sounds**.

You can't go yell at them, because you'd get caught before, so you remember the state had a conveniently made machine that emits a high pitched sound all over the earth, which will get rid of the aliens. The only problem is the aliens are guarding the place where the machine is and you can't possibly go there.

As your friend is an hacker, they created a program that activates the machine if you type the string `KILL ALIENS NOW!`. While they were about to type it, an alien discovered and caught 'em, throwing the **querty** keyboard on the floor. The keyboard is as show in the picture.

Somehow it still works!...well, kinda...when you type a character, the character on its right also types. So if you type 5, it will type 56. The keyboard arrows work normally and all the keys in the numpad and meta keys (print screen, etc) also work well and do nothing else.

The **delete** and **backspace** keys don't work.

Typing `shift left arrow` for example, will delete a character of code and replace it with a `z`.

Typing `j` does **not** type k, for example (this behaviour is the same for the other borbidden keys).

If you type `right shift` you will click in the `up arrow` too, for example.

The letters `k`, `i`, `l`, `a` and `n` don't work (how convenient, huh). You decide to program the `KILL ALIENS NOW!` output, but if you do it in a lot of bytes the aliens will discover that someone is trying to break into the machine.

How will you type the string with that stupid keyboard?

# Summary of the rules

Make a program with any programming language you wish without the letters `k`, `i`, `l`, `a` and `n`, but if you type a character, it will type the one on the right too, that outputs the string `KILL ALIENS NOW!` with the least size of **bytes** possible for it to not appear in the alien's database as the current top action.

# Answer
# Befunge-98 (PyFunge), 92 bytes

```
1290/zx:"())_QWCV*(P[CVNM	QRTUI*(RTRT	QAS:"cv'
1290/zx#$J:"12-=!@!@j!@780-m,45hjvbvbvbvbvb<>

```

`1``9``/` (the `Shift`key that results from this can be ignored since shift by itself does nothing) `z``Right Shift``Down Arrow` (to deselect anything that may have been selected by `Shift` and its implicit `Up Arrow`)`;``9``0``q``c``8``p``c``n``Tab``r``u``8``r``r``Tab``a``;`(release `Shift`)`c``'``1``9``/``z``Right Shift``Down Arrow``3``j`(`k` is a forbidden character so is not generated)`;`(release `Shift`)`1``-``Right Shift``Down Arrow``1``1`(release `Shift`)`j``Right Shift``Down Arrow``1`(release `Shift`)`7``0``m``4``h``v``v``v``v``v``Right Shift``Down Arrow``,`

Note the literal tab characters on the first line.

Try it online!
> 1 votes

# Answer
# Brainfuck, ~~538~~ 221 byte

```
++++++++++[z>?+++++++>?++++++++++>?+++>?+<z<z<z<z-]\>?+++++./-=-=./+++././<z++++++++++++++++++++++++++++++++./>?-=-=-=-=-=-=-=-=-=-=-=./+++++++++++./-=-=-=./-=-=-=-=./+++++++++./+++++./<z./>?-=-=-=-=-=./+./++++++++./<z+./

```

Try it online!

I hope it is correct...
> 2 votes

---
Tags: code-golf, string, restricted-source
---


title: Fermat's polygonal number theorem

text:
# Question
Title: Fermat's polygonal number theorem
Fermat's polygonal number theorem states that every positive integer can be expressed as the sum of at most \\$n\\$ \\$n\\$-gonal numbers. This means that every positive integer can be expressed as the sum of up to three triangle numbers, four square numbers, five pentagonal numbers etc. Your task is to take a positive integer \\$x\\$, and an integer \\$s \ge 3\\$, and to output the \\$s\\$-gonal integers which sum to \\$x\\$.

The \\$n\\$-th \\$s\\$-gonal integer, where \\$n \ge 1\\$ and \\$s \ge 3\\$, can be defined in a couple of ways. The non-math-y way is that the \\$n\\$th \\$s\\$-gonal number can be constructed as a regular polygon with \\$s\\$ sides, each of length \\$n\\$. For example, for \\$s = 3\\$ (triangular numbers):

See here for examples with a larger \\$s\\$.

The math-y definition is by using the formula for \\$P(n, s)\\$, which yields the \\$n\\$-th \\$s\\$-gonal number:

$$P(n, s) = \frac{n^2(s-2) - n(s-4)}{2}$$

which is given in the Wikipedia page here.

## Input

Two positive integers, \\$s\\$ and \\$x\\$, with the condition \\$s \ge 3\\$. You may input these integers in the most natural representation in your language (decimal, unary, Church numerals, integer-valued floating point numbers etc.).

## Output

A list of integers, \\$L\\$, with a maximum length of \\$s\\$, where the sum of \\$L\\$ is equal to \\$x\\$ and all integers in \\$L\\$ are \\$s\\$-gonal integers. Again, the integers may be outputted in the natural representation in your language, with any distinct, consistent separator (so non-decimal character(s) for decimal output, a character different from that used for unary output etc.)

## Rules

* The inputs or outputs will never exceed the integer limit for your language
* \\$L\\$ does not have to be ordered
* In case of multiple possible outputs, any or all are acceptable
* This is so the shortest code in bytes wins

## Test cases

```
   x,  s => L
   1,  s => 1
   2,  s => 1, 1
   5,  6 => 1, 1, 1, 1, 1
  17,  3 => 1, 6, 10
  17,  4 => 1, 16
  17,  5 => 5, 12
  36,  3 => 36
  43,  6 => 15, 28
 879, 17 => 17, 48, 155, 231, 428
4856, 23 => 130, 448, 955, 1398, 1925

```

# Answer
> 7 votes
# Haskell, 55 bytes

```
n%s=[l|l<-mapM(\_->scanl(+)0[1,s-1..n])[1..s],sum l==n]

```

Try it online!

Outputs all possible solutions. Defines the s-gonal numbers as the cumulative sum of the arithmetic progression

```
1, s-2, 2*s-3, 3*s-4, ...

```

# Answer
> 6 votes
# Haskell, ~~78 80~~ 77 bytes

We compute the cartesian product of the first \\$n\\$ s-gonal numbers, and then find the first entry that sums to \\$n\\$.

```
s#n=[x|x<-mapM(map(\n->s*(n^2-n)`div`2+n*(2-n)))([0..n]<$[1..s]),sum x==n]!!0

```

Try it online!

# Answer
> 6 votes
# JavaScript (ES6),  ~~83~~  80 bytes

A fast recursive search which maximizes the smallest term of the output.

Takes input as `(s)(x)`.

```
s=>g=(x,n=0,a=[],y=~n*(~-n-n*s/2))=>x<y?x|a[s]?0:a:g(x,n+1,a)||g(x-y,n,[...a,y])

```

Try it online!

### Formula

It turns out to be shorter to use a 0-based formula to compute the \\$s\\$-gonal numbers in JS, i.e. to start with \\$n=0\\$ and to compute \\$P(n+1,s)\\$:

$$\begin{align}P(n+1,s)&=((n+1)^2(s-2)-(n+1)(s-4))/2\\ &=(n^2(s-2)+ns+2)/2\\ &=-(n+1)((n-1)-ns/2) \end{align}$$

which can be written in 14 bytes:

```
~n*(~-n-n*s/2)

```

### Commented

```
s =>                         // main function taking s
  g = (                      // recursive function g
    x,                       // taking x
    n = 0,                   // start with n = 0
    a = [],                  // a[] = list of s-gonal numbers
    y =                      // y = P(n + 1, s)
      ~n * (~-n - n * s / 2) //   = -(n + 1) * ((n - 1) - n * s / 2)
  ) =>                       //
    x < y ?                  // if x is less than P(n + 1, s):
      x | a[s] ?             //   if x is not equal to 0 or a[] is too long:
        0                    //     failed: return 0
      :                      //   else:
        a                    //     success: return a[]
    :                        // else:
                             //   process recursive calls:
      g(x, n + 1, a) ||      //   preferred: try to increment n
      g(x - y, n, [...a, y]) //   fallback : try to use the current s-gonal number

```

# Answer
> 4 votes
# 05AB1E, ~~14~~ 13 bytes

*Port of Jonathan Allan's Jelly answer.*

```
ÍIÝ*>.¥¹ã.ΔOQ

```

Try it online!

# Answer
> 3 votes
# Jelly,  ~~17~~  15 bytes

-2 thanks to caird coinheringaahing

```
x’2;’ÄÄx⁸ŒPS⁼¥Ƈ

```

A (very very inefficient) dyadic Link accepting `s` on the left and `x` on the right which yields a list of many possible `L` lists, with repeats.

**Try it online!** \- not much point trying it for much higher values!

### How?

```
x’2;’ÄÄx⁸ŒPS⁼¥Ƈ - Link: s, x                    e.g.  5, 17
x               - repeat (s) (x) times                [5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5]
 ’              - decrement (vectorises)              [4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4]
  2;            - prepend a two                       [2, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4]
    ’           - decrement (vectorises)              [1, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3]
     Ä          - cumulative sums                     [1, 4, 7, 10, 13, 16, 19, 22, 25, 28, 31, 34, 37, 40, 43, 46, 49, 52]
      Ä         - cumulative sums                     [1, 5, 12, 22, 35, 51, 70, 92, 117, 145, 176, 210, 247, 287, 330, 376, 425, 477]
       x⁸       - repeat (each of those) (s) times    [1, 1, 1, 5, ..., 425, 477, 477, 477]
         ŒP     - power-set                           [[], [1], [1], ..., [1, 1], ..., [5, 22, 70], ... etc]
                    (this has 2^(x(s+1)) entries ...this example would have 2^(17(5+1)) = 2^102 = 5070602400912917605986812821504 entries!)
                    (Note: the lengths increase left to right)
              Ƈ - filter keep if:
             ¥  -   last two links as a dyad:
           S    -     sum
            ⁼   -     equals (x)?                     [[5,12], ... , [5,12], [1, 1, 5, 5, 5], ... , [1, 1, 5, 5, 5], [1, 1, 1, 1, 1, 12], ...]

```

# Answer
> 3 votes
# Ruby, 79 bytes

Computes the first \\$n\\$ \\$s\\$-gonal numbers and zero, gets the cartesian product of itself \\$s\\$ times, and finds the first entry that matches. Later test cases run out of memory on TIO but theoretically work.

\\$\frac{n^2(s-2)-n(s-4)}{2}\\$ is reorganized into \\$\frac{n(ns-2n-s+4)}{2}\\$ because it saves bytes in Ruby.

```
->n,s{a=(0..n).map{|i|i*(i*s-2*i-s+4)/2};a.product(*[a]*~-s).find{|a|a.sum==n}}

```

Try it online!

# Answer
> 3 votes
# Retina, 111 bytes

```
\d+
*
~(`$
$"
0%["^_+ "|""]'$L$`\G_(?<=(?=___(_*))_+)
((_(?($.(2*$>`))$1\$.(2*$>`)))$*)
1%|' L$`\G_
$$.$.($`$>`

```

Try it online! Link includes test cases. Takes input in the order `s n`. Explanation:

```
\d+
*

```

Convert to unary.

```
~(`

```

After processing the remaining stages, treat them as a Retina program and execute them on the same input.

```
$
$"

```

Duplicate the line.

```
0%["^_+ "|""]'$L$`\G_(?<=(?=___(_*))_+)
((_(?($.(2*$>`))$1\$.(2*$>`)))$*)

```

Replace the first copy with a regular expression that skips over the first number and then matches `s` `s`-gonal numbers. The numbers themselves are captured in odd capture groups and the even capture groups are used to ensure that all of the numbers are `s`-gonal.

```
1%|' L$`\G_
$$.$.($`$>`

```

Replace the second copy with a space-separated list of the odd capture groups.

As an example, the generated code for an input of `5 17` is as follows:

```
^_+ ((_(?(2)__\2))*)((_(?(4)__\4))*)((_(?(6)__\6))*)((_(?(8)__\8))*)((_(?(10)__\10))*)$
$.1 $.3 $.5 $.7 $.9

```

# Answer
> 3 votes
# Python 3, 105 bytes

```
def f(s,x,n=0,a=[]):y=~n*(~-n-n*s/2);return(x<1)*a*(len(a)<=s)if x<y else f(s,x,n+1,a)or f(s,x-y,n,a+[y])

```

Try it online!

*Port of Arnauld's JavaScript answer, so make sure to upvote him!*

# Answer
> 1 votes
# C++ (clang), 198 bytes

```
#import<vector>
using V=std::vector<int>;V f(int n,int s){V _{0};int z=1,a=0,b=1,i,t;for(;a<n;b+=s-2)_.push_back(a+=b),++z;V o;for(t=a=0;t-n;b=++a)for(o=V(s),t=i=0;b;b/=z)t+=o[i++]=_[b%z];return o;}

```

Try it online!

```
V=vector<int>
V _{0}; // initialized with one element =0
int z=1, // vector size
a=0,b=1,i,t;for(;a<n;b+=s-2)_.push_back(a+=b),++z;
// pushes polygons in V
V o; // vector to be returned
for(t=a=0;t-n;b=++a) // ends when t=n
// loop to generate multi-dimension indexes
// for example a=1234 z=10
// a%z->4 , a/=z , a%z-> 3 , ... 2 , 1
for(o=V(s),t=i=0;b;b/=z)// loop to extract indexes
t+=o[i++]=_[b%z]; // put the sum in t and values in o
return o

```

# Answer
> 1 votes
# APL(NARS), 149 chars, 298 bytes

```
r←f w;n;s;i;k
(n s)←w⋄r←⍬⋄→0×⍳s<3⋄i←1
→0×⍳n<k←2÷⍨(i×i×s-2)-i×s-4⋄r←r,k⋄i+←1⋄→2

h←{0=≢b←((v←↑⍵)=+/¨a)/a←{0=≢⍵:⊂⍬⋄m,(⊂1⌷⍵),¨m←∇1↓⍵}f⍵:v⍴1⋄k←↑⍋≢¨b⋄k⊃b}

```

if not find solutions "0=≢b" than return for (n s) input, n times 1; else it would return the sum of s numbers that has less addend...

test:

```
  h 1 3
1
  h 2 8
1 1
  h 5 6
1 1 1 1 1
  h 17 3
1 6 10
  h 17 4
1 16
  h 17 5
5 12
  h 36 3
36
  h 43 6
15 28
  h 879 17
17 48 155 231 428
  h 4856 23
321 448 596 955 2536
  +/h 4856 23
4856

```

The problem of this: It not find some solution has some number repeat in the sum...

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


title: How wavy is an array?

text:
# Question
Title: How wavy is an array?
A *wave* of power \\$k\\$ is an infinite array that looks like \\$1,2,\dots,k,k-1,\dots,1,\dots,k,\dots,1,\dots\\$, and so on. For example, a wave of power 3 starts with \\$1,2,3,2,1,2,3,2,1,...\\$, and repeats indefinitely. A wave of power 1 is an infinite array of ones. They happen to be beautifully expressed as $$w\_k\[t\] = k - |(t - 1)\bmod(2k - 2) - k + 1|\text{, 1-indexed}$$

In this challenge, all waves are trimmed to their first \\$n\\$ elements, where \\$n\\$ is the length of the input array.

A *decomposition of an array into waves* is an array of coefficients of length \\$n\\$ such that the original array equals the sum of the waves multiplied by their corresponding coefficients. Formally, if the original array is \\$A\\$, the decomposition is an array \\$B\\$ such that for any \\$i\\$ (\\$1 \le i \le n\\$) the following equality holds: $$A\[i\] = \sum\_{j=1}^\infty B\[j\] \cdot w\_j\[i\]\text{, 1-indexed}$$

The *waviness* of an array is the index of the last non-zero value in its decomposition into waves.

The task is, given a positive integer array of length \\$n\\$, to calculate its waviness. Note that the decomposition can still include non-integer and negative numbers.

## Test cases

All test cases below are 1-indexed. Your solution may use 0-indexing instead.

```
[1, 1, 1] -> 1                 (decomposition: [1, 0, 0])
[1, 2, 1] -> 2                 (decomposition: [0, 1, 0])
[1, 2, 3] -> 3                 (decomposition: [0, 0, 1])
[1, 1, 2] -> 3                 (decomposition: [1, -0.5, 0.5])
[1, 3, 3, 3, 1] -> 3           (decomposition: [-1, 1, 1, 0, 0])
[1, 2, 2, 4] -> 4              (decomposition: [0, 0.5, -0.5, 1]
[4, 6, 9, 1, 4, 3, 5] -> 7     (decomposition: [2, -0.5, 5, -5, 6.5, -1, -3]
[4, 6, 9, 1, 4, 3, 5, 7] -> 8  (decomposition: [2, -0.5, 5, -5, 6.5, -1, -10.5, 7.5])

```

This is tagged an uncommon justification, so the shortest answer wins.

# Answer
> 3 votes
# APL (Dyalog Unicode), ~~34~~ ~~33~~ 27 bytes

```
⊢{⊢/⍋0≠⍺⌹⍉↑(1+⍵⍴⍳,⊢-⍳)¨⍳⍵}≢

```

Try it online!

Lots of golfing thanks to ngn.

### How it works

```
g←⊢{⊢/⍋0≠⍺⌹⍉↑(1+⍵⍴⍳,⊢-⍳)¨⍳⍵}≢  Accept a vector V of length N
  ⊢{                       }≢  Call the inner function with ⍺=V, ⍵=N
                         ⍳⍵    Make 0..N-1
             (    ⍳,⊢-⍳)¨      For each i of above, make 0..i-1,i..1 and
              1+⍵⍴               repeat/truncate to length N and +1
         ⍺⌹⍉↑                  Reform above as matrix and solve equations
       0≠                      Test nonzero on each item (nonzero→1, zero→0)
    ⊢/⍋                        Find the last index of 1

```

---

# APL (Dyalog Unicode), ~~34~~ 33 bytes

```
⍴-0(⊥⍨=)⊢⌹∘⍉∘↑1+⍴⍴¨(⊢,1+⌽)∘⍳¨∘⍳∘⍴

```

Try it online!

Uses `⎕IO←0` and an alternative way to generate the matrix W.

```
g←⍴-0(⊥⍨=)⊢⌹∘⍉∘↑1+⍴⍴¨(⊢,1+⌽)∘⍳¨∘⍳∘⍴  Accept a vector of length n
                                ⍳∘⍴  Make a vector 0..n-1
                     (⊢,1+⌽)∘⍳¨      For each k of above, chain 0..k-1 and k..1
                  ⍴⍴¨                  and repeat or truncate to length n
                                     The first row has 0 elements, repeat gives n zeros
                1+                   Increment all elements
  ⍴-0(⊥⍨=)⊢⌹∘⍉∘↑                     The rest is the same as the previous answer

```

---

# APL (Dyalog Unicode), 34 bytes

```
⍴-0(⊥⍨=)⊢⌹∘⍉∘↑⍴⍴¨(⊢,1↓¯1↓⌽)∘⍳¨∘⍳∘⍴

```

Try it online!

A monadic train that accepts a numeric vector.

### How it works

```
g←⍴-0(⊥⍨=)⊢⌹∘⍉∘↑⍴⍴¨(⊢,1↓¯1↓⌽)∘⍳¨∘⍳∘⍴  Accept a vector of length n
                                 ⍳∘⍴  Make a vector 1..n
                   (⊢,1↓¯1↓⌽)∘⍳¨      For each k of the above, generate one unit of wave of power k (1..k..2)
                ⍴⍴¨                   Repeat or truncate each row to length n (result is nested vector)
             ⍉∘↑                      Convert nested vector to matrix, and transpose it
          ⊢⌹                          Solve the linear equation
    0(⊥⍨=)                            Count trailing zeros
  ⍴-                                  Subtract from n

```

Basically, this solution uses the same W matrix as Arnauld's submission, solves the linear equation, and then finds the index of the last nonzero entry using the good old "count trailing ones" `⊥⍨`.

# Answer
> 10 votes
# JavaScript (ES6),  ~~172 171~~  169 bytes

The output is 0-indexed.

```
a=>a.map((_,i)=>(D=m=>+m||m.reduce((s,[v],i)=>s+(i&1?-v:v)*D(m.map(([,...r])=>r).filter(_=>i--)),0))(a.map((v,y)=>a.map((_,x)=>x-i?x-~-Math.abs(y%(2*x)-x):v)))&&(j=i))|j

```

Try it online!

### How?

This is essentially an implementation of Cramer's rule, except that the denominator is not computed.

Given the input vector of length \\$n\\$, we define \\$W\_n\\$ as the matrix holding the waves, stored column-wise.

*Example:*

$$W\_5=\begin{pmatrix} 1&1&1&1&1\\ 1&2&2&2&2\\ 1&1&3&3&3\\ 1&2&2&4&4\\ 1&1&1&3&5\end{pmatrix}$$

We compute all values \\$v\_i=\det(M\_i)\\$ with \\$0\le i\<n\\$, where \\$M\_i\\$ is the matrix formed by replacing the \\$i\\$-th column of \\$W\_n\\$ with the input vector.

*Example:*

For the 5th test case and \\$i=3\\$, this gives:

$$v\_3=\det(M\_3)=\begin{vmatrix} 1&1&1&\color{red}1&1\\ 1&2&2&\color{red}3&2\\ 1&1&3&\color{red}3&3\\ 1&2&2&\color{red}3&4\\ 1&1&1&\color{red}1&5\end{vmatrix}=0$$

We return the highest index \\$j\\$ such that \\$v\_j\neq0\\$.

### Commented

The helper function \\$D\\$ uses Laplace expansion to compute the determinant:

```
D = m =>                     // m[] = matrix
  +m ||                      // if the matrix is a singleton, return it
  m.reduce((s, [v], i) =>    // otherwise, for each value v at (0, i):
    s                        //   take the previous sum s
    + (i & 1 ? -v : v)       //   based on the parity of i, add either v or -v
    * D(                     //   multiplied by the result of a recursive call:
      m.map(([, ...r]) => r) //     pass m[] with the 1st column removed
      .filter(_ => i--)      //     and the i-th row removed
    ),                       //   end of recursive call
    0                        //   start with sum = 0
  )                          // end of reduce()

```

The matrix \\$M\_i\\$ is computed with:

```
a.map((v, y) =>         // for each value v at position y in the input vector a[]:
  a.map((_, x) =>       //   for each value at position x in the input vector a[]:
    x - i ?             //     if this is not the i-th column:
      x -               //       compute the wave of power x+1 at position y:
      ~-Math.abs(       //         x - (|y mod (2*x) - x| - 1)
        y % (2 * x) - x //         (where y mod 0 is coerced to 0)
      )                 //
    :                   //     else:
      v                 //       append the value a[y] of the input vector
  )                     //   end of inner map()
)                       // end of outer map()

```

# Answer
> 1 votes
# MATLAB, 111 bytes

```
function w=f(A)
n=length(A)
W=ones(n,1)
for k=2:n
W(1:n,k)=k-abs(mod(0:n-1,2*k-2)-k+1)
end
w=max(find(W\A))
end

```

I'm new to this, do MATLAB answers have to be in a `function`, or can we assume `A` is set implicitly?

The code is straight-forward. The sum in the OP can be replaced with a simple matrix multiplication, `A = W*B`. The code computes `B = inv(W)*A` and finds the index of the last non-zero entry in `B`. `mod(x,0)` isn't well-defined, so the first row has to be set manually.

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


title: Make a haystack (with a needle)

text:
# Question
Title: Make a haystack (with a needle)
*(Essentially the inverse of Find the needle in the haystack)*

Given two tuples, `(w, h)` and `(x, y)`, generate a haystack composed of a single random printable ASCII character of `w` width and `h` height with a needle made of a different random printable ASCII character at `(x, y)` when measured from the upper-left.

For example, when given `(5,4)` for the width and height, and `(3,1)` (zero-indexed) for the location of the needle, a possible haystack could be the following:

```
#####
###N#
#####
#####

```

Another possibility could be

```
*****
***$*
*****
*****

```

among hundreds of others.

### Rules and Clarifications

* Input and output can be given by any convenient method. This means you can take input as a list of list of integers, as a single string, as two integers via command-line and a tuple via function argument, etc.
* You can print the result to STDOUT or return it as a function result.
* Either a full program or a function are acceptable.
* You can choose whether the `(x, y)` tuple is zero-indexed or one-indexed, but please specify in your solution which you're using.
* You do *not* get to pick which characters to use. That's part of the challenge - randomly selecting the characters.
* Every possible output for a given input must have a non-zero chance of appearing, but the randomness doesn't need to be uniform.
* The haystack is guaranteed to be at least 2x2 in size, so it's unambiguous which is the needle and which is the hay.
* There is only ever one needle, and it's only ever one character in size, and it's guaranteed to be within the boundaries of the haystack.
* Standard loopholes are forbidden.
* This is so all usual golfing rules apply, and the shortest code (in bytes) wins.

# Answer
# JavaScript (Node.js),  ~~122 120 106~~  103 bytes

Recursively builds the output character by character. The coordinates are 0-indexed.

```
(w,h,x,y)=>(s=new Date%9023,g=X=>Y<h?Buffer([X-w?(x-X|y-Y?s+1:s%96)%95+32:13])+g(X<w?X+1:!++Y):'')(Y=0)

```

Try it online!

## How?

### Problem

To generate the haystack and the needle, we could either:

* generate a random haystack and process some loop to generate a random needle until it's different from the haystack
* shuffle the whole range of printable characters and pick the first 2 of them

Unfortunately, both approaches are rather lengthy in JS.

### Solution

We use instead a method that guarantees to generate 2 distinct characters with a single random number and without any loop.

We pick a random seed \\$s\\$ in \\$\[0..9022\]\\$ and define the haystack \\$h\\$ and needle \\$n\\$ as:

$$\begin{align}&h=(s+1)\bmod 95\\ &n=(s\bmod 96)\bmod 95\end{align}$$

(we then need to add \\$32\\$ to turn them into printable ASCII codes)

Basically, \\$h\\$ follows the pattern:

$$1,2,3,...,94,0,1,2,3,...$$

while \\$n\\$ follows the pattern:

$$0,1,2,3,...,94,\color{red}0,0,1,2,3,...$$

The sequences are progressively shifted relative to each other because of the extra \\$0\\$ in the needle pattern.

This code shows that it does eventually lead to all possible pairs \\$(h,n)\\$ with \\$h\neq n\\$ (there are \\$95\times 94=8930\\$ of them).

And because we need only one random number, we can afford to use the current timestamp in milliseconds as our entropy source with `new Date%9023` instead of the longer `Math.random()*9023`.

## Commented

```
(w, h, x, y) => (      // w = width, h = height, (x, y) = coordinates
  s = new Date % 9023, // s = random seed in [0..9022]
  g = X =>             // g = recursive function taking X
    Y < h ?            //   if we've not reached the end of the grid:
      Buffer([         //     append the next character:
        X - w ?        //       if we haven't reached the end of the line:
          ( x - X |    //         if this is not the position of the needle:
            y - Y ?    //
              s + 1    //           append the haystack character
            :          //         else:
              s % 96   //           append the needle character
          ) % 95 + 32  //
        :              //       else:
          13           //         append a linefeed
      ]) +             //
      g(X < w ? X + 1  //     append the result of a recursive call
              : !++Y)  //     with either (X+1, Y) or (0, Y+1)
    :                  //   else:
      ''               //     stop recursion
)(Y = 0)               // initial call to g with X = Y = 0

```
> 12 votes

# Answer
# Jelly, ~~14~~ 13 bytes

```
p/⁼€ịØṖẊ¤s⁸Ḣ¤

```

Try it online!

-1 byte thanks to Unrelated String

Returns a list of lines. The last line in the Footer section displays it as a square. Takes input as `[w, h]` and `[y, x]`, where `x` and `y` are 0-indexed.

## How it works

```
p/⁼€ịØṖẊ¤s⁸Ḣ¤ - Main link. Takes [w, h] on the left and [y, x] on the right
p/            - Reduce Cartesian product over the arguments.
                This yields a list of co-ordinates from (1, 1) to (h, w)
   €          - Over each list:
  ⁼           -   Is it equal to [x, y]?
              - This yields a list where every element except 1 is 0
        ¤     - Create a nilad:
     ØṖ       -   Printable ASCII characters
       Ẋ      -   Shuffled
    ị         - Index into the shuffled characters, replacing 1 with the first char in the shuffled list and 0 with the last. Therefore, the two characters will be distinct
            ¤ - Create a nilad:
          ⁸   -   Yield [w, h]
           Ḣ  -   Extract w
        s     - Split the list of characters into rows of length w
              - Implicitly output

```
> 6 votes

# Answer
# Excel VBA, ~~128~~ ~~118~~ ~~106~~ ~~94~~ 96 bytes

*-12 bytes inspired by agtoever*
*-12 bytes thanks to Taylor Scott, VBA extraordinaire*
*+2 bytes and -1 bug thanks to Taylor's unnecessary, intimidating, and much appreciated work*

```
Sub n(w,h,x,y)
a=94*Rnd
[A1].Resize(h,w)=Chr(a+32)
Cells(y,x)=Chr(32+(a+93*Rnd+1)Mod 95)
End Sub

```

Input and output are one-indexed. Output is to the top left cell range of the active sheet.

`a=94*Rnd+32`: `(126-32)*Rnd+32` gives a number between 32 and 126, inclusive.

`Range(~)=Chr(a)`: Fills all the cells with the ASCII character.

`Cells(y,x)=Chr(~)`: Fills just that one cell with the other ASCII character.

`(a+62*Rnd)Mod 95+32`: `{(a+[94-32]*Rnd) Mod (126-32+1)}+32` gives a random number between 32 and 126 inclusive that is *not* the same as `a`. (I can't prove that mathematically but 100 million tests showed no collisions.)

Example output:
> 6 votes

# Answer
# Python 2, ~~134~~ ~~133~~ ~~120~~ ~~112~~ 111 bytes

```
lambda w,h,x,y:zip(*[iter(chr(r[x+y*w==i]+32)for i in range(w*h))]*w)
from random import*
r=sample(range(95),2)

```

Try it online!
> 5 votes

# Answer
# PowerShell v6, ~~102~~ 96 bytes

```
param($x,$y,$a,$b)$j,$k=' '..'~'|random -C 2
-join((,$j*$x+++'
')*$y|%{"$_$k"[$i++-eq$b*$x+$a]})

```

Try it online!

This answer, thanks to mazzy, uses the character range feature added in v6 to save several bytes over the more flexible answer below.

# PowerShell, ~~119~~..~~105~~ 102 bytes

-16 bytes thanks to mazzy
-1 byte thanks to AdmBorkBork

```
param($x,$y,$a,$b)$j,$k=32..126|random -C 2
-join((,$j*$x+++'
')*$y|%{[char]($_,$k)[$i++-eq$b*$x+$a]})

```

Try it online!

Gets two ints in the range of \[32,126\]. We first make a 1D array out of the first value, appending a new line after every `$x`chars. Doing this means we also have to increment `$x` so that our index math isn't affected. We then iterate through the array, and either yield a char-ified first value or the needle. Finally, we join all the yielded values and output it.

Answer is 0-indexed by the way.
> 5 votes

# Answer
# Jelly, 11 bytes

```
QŒṬƤSḂịØṖẊ¤

```

A monadic Link accepting a list of lists, `[[height, width], [row, column]]` (1-indexed), which yields a list of lists of characters.

**Try it online!** (The footer calls the link and joins with newlines.)

### How?

```
QŒṬƤSḂịØṖẊ¤ - Link: [[h, w], [r, c]]
Q           - de-duplicate (i.e. [[h, w]] if [r, c] == [h, w] else [[h, w], [r, c]])
   Ƥ        - for prefixes (of that list):
 ŒṬ         -   get a 2D array with ones at the coordinates specified
    S       - sum (vectorises) (giving us an h*w matrix with zeros almost everywhere,
                                except a 1 at our needle and, if [h, w] != [r,c], a 2 at
                                the bottom-right)
     Ḃ      - modulo two (replacing the 2 with a zero if it exists)
          ¤ - nilad followed by link(s) as a nilad:
       ØṖ   -   list of printable characters
         Ẋ  -   shuffled
      ị     - (left) index into (right) (vectorises)

```
> 5 votes

# Answer
# Dyalog APL, ~~24~~ ~~23~~ 21 bytes

```
⎕UCS(32+2?95)[⎕∘≡¨⍳⎕]

```

Try it online! 0-indexed.

-1 thanks to ngn, -2 thanks to Adám suggesting to use a different I/O format.
> 4 votes

# Answer
# Python 2, 133 bytes

```
from random import*
r=range
def f(h,w,x,y):
 p=sample(r(32,127),2)
 for i in r(h):
	print ''.join(chr(p[i==y and j==x])for j in r(w))

```

Try it online!

-12 thanks to Value Ink for suggesting using a loop comprehension. -2 thanks to Unrelated String for suggesting python 2 instead of python 3 to get rid of parenthesis in the print function!
> 4 votes

# Answer
# Python 2, 110 bytes

```
from random import*
w,h,x,y=input()
m,n=sample(map(chr,range(32,127)),2)
l=eval(`[[m]*w]*h`)
l[x][y]=n
print l

```

Try it online!

I copied TFeld's solution and managed to golf a char using list assignment. The `eval()` trick is used to make a mutable matrix to avoid the list mutation applying to every row.

**111 bytes**

```
lambda w,h,x,y:[[chr(r[x^i<1>y^j]+32)for i in R(w)]for j in R(h)]
from random import*
R=range
r=sample(R(95),2)

```

Try it online!

A smaller change that only tied. Calling the function multiple times always give the same random choices, which I hope is OK.

**109 bytes**

```
lambda w,h,x,y:[m*w]*y+[m*x+n+m*(w+~x)]+[m*w]*(h+~y)
from random import*
m,n=sample(map(chr,range(32,127)),2)

```

Try it online!

A shorter function making the list of lines via multiplication. Also generates the characters just once.
> 3 votes

# Answer
# Perl 5, 86 bytes

```
($,,$b)=keys%{{map{chr,1}33..126}};$_=($,x$F[0].$/)x$F[1];s;(.*
){$F[3]}.{$F[2]}\K.;$b

```

Try it online!
> 2 votes

# Answer
# Julia 1.0, 71 bytes

```
f(w,h,x,y)=(z=unique(rand(' ':'~',9));g=fill(z[1],(h,w));g[y,x]=z[2];g)

```

`x,y` are one indexed. Returns a 2d array of characters, I spent the extra bytes to make sure the default printing has the right orientation (`'` for transpose no longer works because they stick to a strict mathematical meaning). Getting two distinct randoms is surprisingly verbose, this has about a 1e-18 chance of failing to do so, one more byte could make it 1e-196.

Try it online!
> 2 votes

# Answer
# , 21 bytes

```
u:@(32+2?95){~#.=i.@[

```

Try it online!

Inspired by dzaima's APL answer.

Thanks to Galen and Adam for the randomize fix.
> 2 votes

# Answer
# Octave with Statistics Package, 45 bytes

```
@(x)randsample(' ':'~',2)(sparse(x{:},0:1)+1)

```

The input is a cell array of 2 numeric vectors of length 2: `{[h y] [w x]}`, with `x`,`y` 1-based.

Try it online!
> 2 votes

# Answer
# Ruby, 62 bytes

```
->w,h,x,y{a,b=[*?\s..?~].sample 2;r=[a*w]*h*$/;r[y*-~w+x]=b;r}

```

Try it online!
> 2 votes

# Answer
# Excel + CSV, 104 bytes

```
,,,,=94*RAND()+32,=REPLACE(REPT(REPT(CHAR(E1),A1)&"
",B1),D1*A1+D1+C1+1,1,CHAR(MOD(E1+62*RAND(),95)+32))

```

Save as CSV, add input as `A1` \- `D1`. Output will be in `F1`.

Using @Engineer Toast's solutoin for generating 2 unique characters.

Needle position is 0-indexed, which is curious, as Excel itself if 1-indexed. Changing to 1-indexed input adds 3 bytes (`(D2-1)*(A2+1)+C2` instead of `D1*A1+D1+C1+1`).
> 2 votes

# Answer
# Pyth, 56 50 48 41 bytes

```
JEKE=TE=Yrd\~=Zh.SYVJVQ ?qHK?qNTpeYpZpZ)d

```

I'm somewhat struggling to golf Pyth, but posting this to force myself to learn.

Edit 1: Golfed it down a bit, and made it an actual solution -6 bytes

Edit 2: Looked at it after posting it and realized a few bytes save by ignoring space. -2 bytes

Edit 3: Today I learned about character ranges, which shortens things significantly. -7 bytes
> 2 votes

# Answer
# PHP, ~~113~~ 109 bytes

```
for([,$w,$h,$x,$y]=$argv,$a=range(' ','~'),shuffle($a);$i++<$h;print"
")for(;$$i++<$w;)echo$a[$i-$y||$$i-$x];

```

Try it online!

Pass inputs as command arguments (`$argv`) in order of `w`, `h`, `x` and `y`. The `x` and `y` are one-indexed.

```
for(
  [,$w,$h,$x,$y]=$argv, // put inputs from $argv array into 4 short named variables
  $a=range(' ','~'),    // create $a array containing printable ASCII characters
  shuffle($a);          // shuffle the array
  $i++<$h;              // loop $h times (rows)
  print"\n"             // print a newline after every row
)
  for(;$$i++<$w;)       // loop $w times (columns)
    echo                // print
      $a[               //   a character from $a (1st char for needle and 2nd for heystack)
        $i-$y ||        //   when row and y don't match
        $$i-$x          //   or when col and x don't match (will be false only for needle)
      ];

```
> 1 votes

# Answer
# Add++, 65 bytes

```
D,g,?!,
L,c95Rdb[€BXd¦=BFV#@G+b[95€Ω%31€+€CA€RbU‽g$€=$€Ω:A$pbUp$T

```

Try it online!

Takes input as `[y x]` and `[w h]`. `x` and `y` are 1-indexed. Outputs a list of lines.

Added 17 bytes to make sure the needle is distinct.

## How it works

We start by generating two ranges from \\$1\\$ to \\$95\\$ inclusive, before choosing a random value from each. If the two values are equal, we add one to the one of them. We then add \\$31\\$ to each, yielding two characters ord points in the ASCII range. Finally, we convert them to characters.

Next, we generate a list of all co-ordinates in the grid, and compare them with `[y x]`. If the co-ordinates match, we yield \\$1\\$, otherwise \\$0\\$. Next, we index each of these \\$1\\$s and \\$0\\$s into the two characters, creating a grid of \\$0\\$ characters with 1 \\$1\\$ character in it at `[y x]`. Finally, we retrieve the width and split the grid into that many rows.
> 1 votes

# Answer
# SOGL, 18 bytes

```
 ~Δψ] ~Δψ⁴⁴=}A*∙až

```

Try it here! 1-indexed.
> 1 votes

# Answer
# C# (Visual C# Interactive Compiler), 145 bytes

```
(a,b,c,d)=>{int l=0;for(var j=Enumerable.Range(32,95).OrderBy(k=>Guid.NewGuid()).ToList();l<a*b;)Write((char)j[l==c*a+d?1:0]+(++l%a<1?"\n":""));}

```

Try it online!
> 1 votes

# Answer
# Icon, 119 bytes

```
procedure f(w,h,x,y)
until m:=char(32+?95)&n:=char(32+?95)&m~==n
t:=[];1to h&put(t,repl(m,w))&\z
t[y,x]:=n
return t
end

```

Try it online!

`x`and `y`are 1-indexed
> 1 votes

# Answer
# Python 3, 137 bytes

```
lambda w,h,x,y,c=chr:"\n".join([c(a)*w,c(a)*x+c(n)+c(a)*(w-x-1)][r==y]for r in range(h));a,n=__import__("random").sample(range(32,127),2)

```

Try it online!

Uses zero-based indexing for the needle position.
> 1 votes

# Answer
# Perl 6, 57 bytes

```
{(' '..'~').pick(2)[0 xx$^a*$^b-1,1;*].pick(*).rotor($a)}

```

Try it online!
> 1 votes

# Answer
# Charcoal, 17 bytes

```
ＵＯＮＮ‽γＪＮＮ‽Φγ¬⁼ιＫＫ

```

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

```
ＵＯＮＮ‽γ

```

Draw a rectangle of the given width and height using a random printable ASCII character.

```
ＪＮＮ

```

Jump to the 0-indexed position of the needle.

```
‽Φγ¬⁼ιＫＫ

```

Print a random printable ASCII character, but filtering out the character under the cursor.
> 1 votes

# Answer
# K (oK), ~~27~~ 23 bytes

-4 bytes thanks to ngn!

```
{`c$(32+-2?95)x#&/y=!x}

```

Try it online!

0-indexed `x` and `y`

Similar to Dzaima's APL and Jonah's J solutions.
> 1 votes

# Answer
# Red, 156 bytes

```
func[w h x y][c: :collect p: take/part random c[repeat i 95[keep to sp 32 + i]]2
c[repeat i h[keep/only c[repeat j w[keep pick p i * w + j
=(y * w + x)]]]]]

```

Try it online!

`x` and `y` are 1-indexed. Returns a list of strings.

## Readable:

```
f: func [w h x y] [
    c: take/part random collect [
        repeat i 95 [
            keep to sp 32 + i
        ]
    ] 2
    collect[
        repeat i h [
            keep/only collect [
                repeat j w [
                    keep pick c i * w + j = (y * w + x)
                ]
            ]
        ]
    ]
]

```
> 1 votes

# Answer
# Python 2, ~~144~~ ~~132~~ 131 bytes

```
from random import*
i,j,k,l=input()
n,h=sample(range(32,127),2)
for x in range(j):a=[chr(n)]*i;a[k]=chr((n,h)[x==l]);print`a`[2::5]

```

Try it online!

Corrected the problem with the guaranteed uniqueness of the characters and saved 12 bytes along the way.
> 1 votes

# Answer
# Forth (gforth), 140 bytes

```
include random.fs
: x 95 random 32 + ;
: f x -rot 0 do cr dup 0 do 2over i j d= >r over r> if begin x 2dup - until nip then emit loop loop ;

```

Try it online!

0-indexed

### Code Explanation

```
include random.fs        \ import the random library

\ Generate a random number in range 32 to 126 inclusive
: x                      \ start a new word definition
  95 random              \ generate a random number between 0 and 94
  32 +                   \ add 32
;                        \ end word definition

: f                      \ start a new word definition
  x -rot                 \ generate a random number for the haystack, then move it
  0 do                   \ loop from 0 to h-1 (inclusive)
    cr                   \ output a newline
    dup 0 do             \ loop from 0 to w-1 (inclusive)
      2over i j d=       \ check if this is the needle square
      >r over r>         \ hide result, grab a copy of the haystack char, then grab result back
      if                 \ if it is a needle
        begin            \ begin indefinite loop
          x 2dup -       \ generate a new random number and compare to haystack char
        until            \ only end loop when values differ
        nip              \ drop haystack char
      then               \ end if block
      emit               \ output ascii char for value on top of stack
    loop                 \ end row loop
  loop                   \ end column loop
;                        \ end word definition

```
> 1 votes

# Answer
# C (clang), 87 bytes

```
f(w,h,x,y){x+=y*w;h*=++w;for(y=time(0)%9023;h--;)putchar(h%w?(x--?y+1:y%96)%95+32:10);}

```

Try it online!

Stealing from @Arnauld answer
> 1 votes

# Answer
# Japt `-R`,~~34~~ ~~30~~ ~~29~~ 24 bytes

```
;E=öx)ÎpU*V hW*U+XEg1)òU

```

Try it

5 Bytes saved thanks to @Shaggy.

Inputs are U,V =\> size , W,X =\> needle coords 0 indexed

```
 ;E=   // set of printable characters
     öx) // random permutation
 Î // => g0  pU*V    repeats U*V times first element of set
           hW*U+XEg1) // overwrite at W,X with 2nd element
                      òU // split

```
> 1 votes

# Answer
# 05AB1E, 15 bytes

```
žQΩIP×žQΩIPǝ¹нô

```

Coordinates are 1-indexed. Outputs as a list of lines.

Try it online (`»` in the footer joins the list of strings by newlines to pretty-print, feel free to remove it to see the actual output).

**Explanation:**

```
žQ              # Push all printable ASCII characters
  Ω             # Pop and push a random character
   IP           # Push the first input (rectangle-size), and take its product
     ×          # Repeat the random character that many times as string
      žQΩ       # Push a random character again
         IP     # Push the second input (1-based coordinate), and take its product as well
           ǝ    # Insert the random character at this (0-based) index into the string
            ¹н  # Push the first input again, and only leave its first value (width)
              ô # Split the string into parts of that size
                # (after which the resulting list of strings it output implicitly as result)

```
> 1 votes

# Answer
# C (clang), ~~130~~ ~~117~~ ~~116~~ ~~109~~ 106 bytes

```
c[2];f(w,h,x,y){x+=y*w;for(h*=++w;y++<h|*c==c[1];)c[y%2]=time(0)%94+33;for(;h--;)printf(h%w?c+!x--:"\n");}

```

Try it online!

Saved 13 thanks to @ceilingcat Didn't thought using just only time() was enough And also didn't thought printf accepted a int pointer as a format string!

Needle is 0 indexed

```
c[2]; // needle and hay stored in array
f(w,h,x,y){
 x+=y*w; // sets counter for needle (x no more needed)
 for(
     h*=++w; // while incrementing w for newline sets counter for haystack
     y++<h  // more than 2 iterations to fill array
     |*c==c[1]; // until they're different
     )
     c[y%2]=time(0)%94+33; // assign value to array (I've excluded spaces )
 for( ;h--; ) printf(h%w?c+!x--:"\n")
 // output: on h%w =0 => newline
 //              if  x != 0 => hay
 //              when x=0 => needle
 //              and continue to finish haystack

```
> 0 votes

# Answer
# Zsh, 108 bytes

Needle location is 1-indexed

```
repeat $2 : $[h=r++?h:RANDOM%95]&&(repeat $1 s+=${(#)$((n=r-$4||++c-$3?h:(n=RANDOM%94)+(n>=h),32+n))};<<<$s)

```

Try it online!

```
repeat $2
  # set hay when row is 0 (shorter than setting it before due to the cost of "(( ))")
  # ": $[  ]" always exits true. "((  ))" would exit false if hay == 0
  : $[hay = row++ ? hay : RANDOM % 95] && (
    # inner loop in (subshell), $str and $col will be empty every time
    repeat $1
      # ${(#)$((x))} expands to the Unicode character at codepoint $x
      str+=${(#)$((offset =
        row - $4 || ++col - $3
        ? hay
        : (offset = RANDOM % 94) + (offset >= hay),
        32 + offset
      ))}
      <<< $str
  )

```

Proof of correctness by exhaustion, for all combinations of `RANDOM%95` and `RANDOM%94`.
> 0 votes

---
Tags: code-golf, ascii-art, random
---


# Question
Title: Output integer given a digital clock style input
Input

```
    _  _     _  _  _  _  _  _
  | _| _||_||_ |_   ||_||_|| |
  ||_  _|  | _||_|  ||_| _||_|

```

output

```
1234567890

```

**Rules**

Code golf - shortest code wins.

Input will be given as a 3-line string with each line separated by a newline, or as 3 separate strings. Each line is guaranteed to be a multiple of 3 characters long with no additional whitespace, and all lines will be the same length.

Each digit is represented as a 3x3 block of characters as above. Note that the `1` digit has two leading spaces in order to fill the 3x3 block.

# Answer
> 8 votes
# JavaScript (ES6),  ~~105~~  104 bytes

Takes input as an array of 3 strings. Returns an array of digit characters.

```
a=>a.map(s=>s.match(/.../g).map(([a,b,c],n)=>'3789465021'[(o[n]=~~o[n]+[++a|7*++b^44*++c])%13]),o=[])[2]

```

Try it online!

## How?

### Finding a concise way to process the input

A common trick to turn an input string into an identifier is to use `parseInt()`. But it only works with alphanumeric strings and is therefore pointless here. Other than that, JS is not very good at processing ASCII codes in few bytes, so we'd better find another trick.

We can notice that each digit in this font can still be uniquely identified if we replace each character with a binary value: \\$1\\$ for *space*, \\$0\\$ for *not space*:

```
  0  |  1  |  2  |  3  |  4  |  5  |  6  |  7  |  8  |  9
-----+-----+-----+-----+-----+-----+-----+-----+-----+-----
  _  |     |  _  |  _  |     |  _  |  _  |  _  |  _  |  _
 | | |   | |  _| |  _| | |_| | |_  | |_  |   | | |_| | |_|
 |_| |   | | |_  |  _| |   | |  _| | |_| |   | | |_| |  _|
-----+-----+-----+-----+-----+-----+-----+-----+-----+-----
 101 | 111 | 101 | 101 | 111 | 101 | 101 | 101 | 101 | 101
 010 | 110 | 100 | 100 | 000 | 001 | 001 | 110 | 000 | 000
 000 | 110 | 001 | 100 | 110 | 100 | 000 | 110 | 000 | 100

```

That looks like a good golfing start: it means that we can abuse the fact that a space is coerced to \\$0\\$ and can be turned into a \\$1\\$ by applying the pre-increment operator to it, while it will result in `NaN` for the other characters.

Hence the idea to implement something along these lines:

```
s.match(/.../g)        // split each line into groups of 3 characters
.map(([a, b, c], n) => // for each group (a, b, c) of characters at position n:
  ???                  //   do some bitwise magic with ++a, ++b and ++c
                       //   and use it to update an identifier for the n-th digit
)                      // end of map()

```

### Bitwise magic

After some experiments and brute-forcing, it turned out that a pretty short and efficient formula is:

```
o[n] = ~~o[n] + [++a | 7 * ++b ^ 44 * ++c]

```

*Step-by-step example:*

* The 1st line of a `"0"` is `" _ "`. Therefore, we have `++a -> 1`, `++b -> NaN` and `++c -> 1`.

So, `++a | 7 * ++b ^ 44 * ++c` evaluates to `1 | 7 * NaN ^ 44 * 1`, which is \\$45\\$.

Because `o[n]` is initially undefined, `~~o[n]` evaluates to \\$0\\$. And because \\$45\\$ is coerced to a string, `o[n]` is updated to `"045"`.
* The 2nd line of a `"0"` is `"| |"`. This time, we have `++a -> NaN`, `++b -> 1` and `++c -> NaN`. The bitwise expression evaluates to \\$7\\$ and `o[n]` is updated to `"457"`. (Note that the leading `0` is thrown away by `~~o[n]`.)
* The 3rd line of a `"0"` is `"|_|"`, leading to `++a -> NaN`, `++b -> NaN` and `++c -> NaN`. The bitwise expression evaluates to \\$0\\$ and the final value of `o[n]` is `"4570"`.

### Minimal perfect hash function

Of course, the parameters of the bitwise formula were not chosen at random (well ... at least no completely): by coercing the final identifier of a digit back to an integer and applying a modulo \\$13\\$, we get a unique value in \\$\[0..9\]\\$.

The following table summarizes the results for all digits:

```
  digit |   0   |   1   |   2   |   3   |   4   |   5   |   6   |   7   |   8   |   9
--------+-------+-------+-------+-------+-------+-------+-------+-------+-------+-------
     ID |  4570 |  4377 | 45144 |  4511 |  4307 | 45441 | 45440 |  4577 |  4500 |  4501
--------+-------+-------+-------+-------+-------+-------+-------+-------+-------+-------
 mod 13 |   7   |   9   |   8   |   0   |   4   |   6   |   5   |   1   |   2   |   3

```

Hence the 10-byte lookup table: `'3789465021'`.

# Answer
> 4 votes
# , 55 bytes

```
(0 3,:3 3)(6 7 8 11 4 2 13 14 5 9 i.15|[:#.@,' '&=);.3]

```

Try it online!

J has a primitive `;.3` called Subarrays that let's you process a multi-dimensional "sliding window". Here we have a 3x3 window moving 3 steps to the right each time, which grabs exactly 1 digit.

We convert each 3x3 matrix to a boolean mask `' '&=`, flatten it `,`, and convert that binary number to decimal `#.`. After a little experimenting, I found that modding it by 15 `15|` returned a unique list of small numbers, and we just find the index within that.

More brute forcing could likely find an even more efficient encoding.

# Answer
> 2 votes
# 05AB1E, 25 bytes

```
€S3δôøðQε˜JC15%•#/ι®ˆ¼•sè

```

Input as a list of lines, output as a list of digits. If we could take the input as a 2D list of characters, the first 2 bytes can be removed.

Try it online.

**Explanation:**

```
€S                        # Convert each line in the (implicit) input-list of strings to
                          # an inner list of characters
   δ                      # Convert each inner list of characters to:
  3 ô                     #  Split it into blocks of size 3
     ø                    # Zip/transpose; swapping rows/columns
      ðQ                  # Check which characters are spaces (1 if truthy; 0 if falsey)
        ε                 # Map each 3x3 block to:
         ˜                #  Flatten it to a single list
          J               #  Join it together to a single string
           C              #  Convert it from binary to an integer
            15%           #  Take modulo-15
               •#/ι®ˆ¼•   #  Push compressed integer 105048012903067
                       s  #  Swap to take the earlier integer
                        è #  And (0-based) index it into this to get the resulting digit
                          # (after the map, the result is output implicitly)

```

See this 05AB1E tip of mine (section *How to compress large integers?*) to understand why `•#/ι®ˆ¼•` is `105048012903067` (NOTE: the leading `1` and all the `0`s except for the 3rd (7th digit) are fillers.

# Answer
> 2 votes
# Python 3, 105 bytes

```
f=lambda p,q,r:p and'5498136207'[int(''.join(map(str,p[:2]+q[:3]+r[:2])))%49%11]+f(p[3:],q[3:],r[3:])or''

```

Try it online!

Takes input as three bytestrings. It considers the following sections in a digit, which gives a unique combination:

```
 _     12
|_  => 345
 _|    67

```

In this order, the base-10 ascii values for each character are converted into a string, concatenated, and converted back into an integer. In the example above this would be `'32'+'95'+'124'+'95'+'32'+'32'+'95' => 329512495323295`. This integer is reduced with a double modulo `%49%11`. This results in a unique value from `0` to `9` for each digit, hence the string map `'5498136207'`.

# Answer
> 1 votes
# Charcoal, 57 bytes

```
Ｅ³ＳＦ÷Ｌθ³«Ｊ⊕×³ι¹⊞υ÷⌕”{“→✂⌕Ｑ¤αA？=¹⧴Ｚb⁻e⁵ηπ⪫Q¡”⁺ＫＫ⪫ＫＭω⁹»⎚⪫υω

```

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

```
Ｅ³Ｓ

```

Copy the three lines of input to the canvas.

```
Ｆ÷Ｌθ³«

```

Loop over the digits...

```
Ｊ⊕×³ι¹

```

... jump to the middle of the digit...

```
⊞υ÷⌕”{“→✂⌕Ｑ¤αA？=¹⧴Ｚb⁻e⁵ηπ⪫Q¡”⁺ＫＫ⪫ＫＭω⁹

```

... and concatenate the nine characters of the digit and look it up in a compressed string, dividing the index by 9.

```
»⎚⪫υω

```

Clear the canvas and output the detected digits.

# Answer
> 1 votes
# PHP, ~~104~~ 102 bytes

-2 bytes thanks to Arnauld

```
for(;!$i||$d&&print'6930274581'[crc32($d)%63%10];$i++)for($d=0;$a=$argv[++$$i];$d.=substr($a,$i*3,3));

```

Try it online!

Takes input as 3 separate strings.

### How?

I create a single line string for each digit with a leading "0" (10 in total for each digit), this is basically 3 lines of 3 characters for each digit concatenated to each other without new lines and a "0" at start of them. For string of each digit I get the cyclic redundancy checksum polynomial of 32-bit lengths (crc32) and then do a mod 63 and mod 10 on it to get unique values for each digit. Then using the unique values and a mapping I simply output the actual digit. Look at the table below for a visual demonstration:

```
| Digit | Single line string | CRC32      | %63 | %10 |
|-------|--------------------|------------|-----|-----|
| 0     | "0 _ | ||_|"       | 4018184249 |  23 |   3 |
| 1     | "0     |  |"       |  750606692 |  59 |   9 |
| 2     | "0 _  _||_ "       | 2375221876 |  34 |   4 |
| 3     | "0 _  _| _|"       | 2330511487 |  52 |   2 |
| 4     | "0   |_|  |"       |  745793270 |  26 |   6 |
| 5     | "0 _ |_  _|"       | 1887416553 |  57 |   7 |
| 6     | "0 _ |_ |_|"       |  366569277 |  60 |   0 |
| 7     | "0 _   |  |"       | 1506663000 |  45 |   5 |
| 8     | "0 _ |_||_|"       | 2483214119 |   8 |   8 |
| 9     | "0 _ |_| _|"       | 4054057203 |  21 |   1 |

```

### Commented

```
for(;                     // outer loop, iterates on digits
  !$i||                   // this allows the first iteration of loop to happen
  $d&&                    // $d is the single line string of each digit
                          //   continue the loop as long as $d is not empty
  print                   // and if $d is not empty, print
    '6930274581'          //   a character from mapping string
    [crc32($d)%63%10];    //   at index of CRC32 of the digit's single line string % 63 % 10
  $i++                    // increment $i by one, $i indicates which digit we are reading now
)
  for(                    // inner loop to get single line string of each digit
                          //   this loop iterates 3 times as we have 3 separate inputs
    $d=0;                 // set $d to "0" on start of each loop
    $a=$argv[++$$i];      // set $a to appropriate input (input 1 or 2 or 3)
    $d.=substr($a,$i*3,3) // concatenate a sub string of current digit from $a to $d
  );

```

# Answer
> 1 votes
# Jelly, 26 bytes

```
s€3=⁶ZF€Ḅ%15“pŻḣṾ:’b⁴¤iⱮ’Ḍ

```

Try it online!

A monadic link taking a list of three Jelly strings and returning an integer. Converts each input into a binary list where 1 is space and 0 anything else, converts back from binary, takes mod 15 (lowest divisor that yields unique output for each digit) and then looks these up in a list of 10 values to extract the relevant digit. Finally converts from a list of decimal digits to an integer.

# Answer
> 0 votes
# Jelly, 21 bytes

<sup>20 if a list of digits is acceptable -- remove trailing
...or if we may print with any leading zeros -- remove trailing  and replace the `D` with a </sup>

```
ZOḅ3/ḅ⁹%129ị“ȯṂṾ;’D¤Ḍ

```

A monadic Link accepting a list of the three lines which yields an integer.

**Try it online!**

### How?

*Magic...*

```
ZOḅ3/ḅ⁹%129ị“ȯṂṾ;’D¤Ḍ - Link: list of lists of characters
Z                     - transpose
 O                    - to ordinals
   3/                 - three-wise reduce using:
  ḅ                   -   (left list) from base (right) (vectorises)
      ⁹               - literal 256
     ḅ                - (left list) from base (256)
        129           - literal 129
       %              - (left) modulo (129) (vectorises)
                   ¤  - nilad followed by link(s) as a nilad:
            “ȯṂṾ;’    -   base 250 integer = 3792546810
                  D   -   to digits = [3,7,9,2,5,4,6,8,1,0]
           ị          - (left) index into (right) 1-indexed & modular (vectorises)

```

***Huh?...***

After `ZO` we have a list of columns of `32`s, `95`s, and `124`s where there were spaces, underscores, and pipes, respectively. For example:

```
 _  _
 _||_   -> [[32,32,32],[95,95,95],[32,124,124],[32,124,124],[95,95,95],[32,32,124]]
 _||_|

```

The three-wise reduce using base conversion with vectorisation effectively takes each group of three lists (i.e. an input-digit), first converting the left-most to each base defined by the middle list and then converts that resulting list to each base defined by the right-most list:

```
[32,32,32]ḅ95 = 32×95²+32×95+32 = 291872
->
[32,32,32]ḅ[95,95,95] = [291872,291872,291872]

[291872,291872,291872]ḅ32 = 291872×32²+291872×32+291872 = 308508704
and
[291872,291872,291872]ḅ124 = 291872×124²+291872×124+291872 = 4524307872
->
[291872,291872,291872]ḅ[32,124,124] = [308508704,4524307872,4524307872]

similarly
([32,124,124]ḅ[95,95,95])ḅ[32,32,124] = [317844128,317844128,4661212704]

so  applying ZOḅ3/ we have:
 _  _
 _||_   -> [[308508704,4524307872,4524307872],[317844128,317844128,4661212704]]
 _||_|

```

This gives a unique triples for each input-digit which we convert to unique integers by conversion from base 256 (`ḅ⁹`) and modulo by 129 (`%129`) to find unique integers which remain unique if modulo-ed by ten.

```
   ZOḅ3/                              ḅ⁹              %129  (implicit %10 of ị)
0  [309401120,4628496048,4628496048]  21466435284656  110   0
1  [ 35751968, 524305824, 524305824]   2477787571616  119   9
2  [308605948,4525733964, 308605948]  21383695908860  104   4
3  [308508704,4524307872,4524307872]  21381173548448   41   1
4  [ 47306784, 602657424, 602657424]   3255180354192    6   6
5  [317746884, 317746884,4659786612]  20909862778740   15   5
6  [317844128, 317844128,4661212704]  20916262082080   97   7
7  [299993120,4492051872,4492051872]  20814806443424   92   2
8  [317844128,4661212704,4661212704]  22028164437536    8   8
9  [317746884,4659786612,4659786612]  22021424949108   93   3

```

(256 was chosen because it is a short literal in Jelly, `ḅ14%67` is the same length and also works but the lookup integer, `5987203416`, takes an extra base 250 digit - `“¡⁴,>ʠ’`.)

```
 _  _      ZOḅ3/ḅ⁹                            %129       (implicit %10 of ị)
 _||_   -> [21381173548448,20916262082080] -> [41,97] -> [1,7]
 _||_|

and the 1st and seventh elements of “ȯṂṾ;’D = [3,7,9,2,5,4,6,8,1,0]
...are three and six -> [3,6]

```

---
Tags: code-golf, number, ascii-art, parsing
---