title: Are you a probabilist or a physicist?

text:
# Question
Title: Are you a probabilist or a physicist?
Hermite polynomials refer to two sequences of polynomials:

* The **"probabilist's Hermite polynomials"**, given by

$${He}\_n(x) = (-1)^n e ^ \frac {x^2} 2 \frac {d^n} {dx^n} e ^ {-\frac {x^2} 2}$$

where \\$\frac {d^n} {dx^n} f(x)\\$ refers to the \\$n\\$th derivative of \\$f(x)\\$
* The **"physicist's Hermite polynomials"**, given by

$$H\_n(x) = (-1)^n e ^ {x^2} \frac {d^n} {dx^n} e ^ {-x^2}$$

The first few terms are

| \\$n\\$ | \\$He\_n(x)\\$ | \\$H\_n(x)\\$ |
| --- | --- | --- |
| \\$0\\$ | \\$1\\$ | \\$1\\$ |
| \\$1\\$ | \\$x\\$ | \\$2x\\$ |
| \\$2\\$ | \\$x^2 - 1\\$ | \\$4x^2 - 2\\$ |
| \\$3\\$ | \\$x^3 - 3x\\$ | \\$8x^3 - 12x\\$ |
| \\$4\\$ | \\$x^4 - 6x^2 + 3\\$ | \\$16x^4 - 48x^2 + 12\\$ |
| \\$5\\$ | \\$x^5 - 10x^3 + 15x\\$ | \\$32x^5 - 160x^3 + 120x\\$ |

Both sequences can be expressed via recurrence relations:

$$ He\_{n+1}(x) = xHe\_n(x) - nHe\_{n-1}(x) \\ H\_{n+1}(x) = 2xH\_n(x) - 2nH\_{n-1}(x) $$

with the base cases

$$ He\_0(x) = 1, He\_1(x) = x \\ H\_0(x) = 1, H\_1(x) = 2x $$

---

You should write a polyglot program that works in at least 2 languages. In one language, it should take a non-negative integer \\$n\\$ as input and output the polynomial \\$H\_n(x)\\$, and in the second, it should take a non-negative integer \\$n\\$ and output the polynomial \\$He\_n(x)\\$.

Your programs should be true polyglots, so are the same bytes, rather than the same characters. For example, if your program is `g)ʠẹṁ` in the Jelly code page, the bytes are `67 29 A5 D6 EF`, and the same program in the 05AB1E code page would be `g)¥Öï`.

You may output the polynomial in any reasonable format, such as a list of coefficients (little- or big-endian) (e.g. \\$x^4 - 6x^2 + 3\\$ as `[1,0,-6,0,3]`), a list of pairs of coefficients and powers (e.g. `[[1,4], [-6,2], [3,0]]`), or a string such as `x^4-6x^2+3`.

Different versions of languages (e.g. Python 2 and 3) are considered the same language. As a general rule, if 2 languages are considered to be versions of each other (e.g. Seriously and Actually), they may not both be used. Additionally, using command line flags, in this case, does not count as different languages.

This is , so the shortest code in bytes wins.

---

## Test cases

The polynomials here are represented in little-endian format

```
n -> He(x)                                 H(x)
0 -> [1]                                   [1]
1 -> [0, 1]                                [0, 2]
2 -> [-1, 0, 1]                            [-2, 0, 4]
3 -> [0, -3, 0, 1]                         [0, -12, 0, 8]
4 -> [3, 0, -6, 0, 1]                      [12, 0, -48, 0, 16]
5 -> [0, 15, 0, -10, 0, 1]                 [0, 120, 0, -160, 0, 32]
6 -> [-15, 0, 45, 0, -15, 0, 1]            [-120, 0, 720, 0, -480, 0, 64]
7 -> [0, -105, 0, 105, 0, -21, 0, 1]       [0, -1680, 0, 3360, 0, -1344, 0, 128]

```

# Answer
> 7 votes
# Wolfram Language (Mathematica) \+ Python 3, 63 bytes

```
#+HermiteH[#,x]-#&(*
import scipy.special as s;s.hermitenorm#*)

```

Try it online! (Mathematica)

Try it online! (Python)

Boring solution with built-ins... Gives physicists' version for Mathematica and probabilists' version for Python. There will be floating errors for Python though. The following eliminates that for 102 bytes

```
#+HermiteH[#,x]-#&(*
f=lambda n:n<2 and[0]*n+[1]or[a-~-n*b for a,b in zip([0]+f(n-1),f(n-2)+[0,0])]#*)

```

with the Python solution outputting a coefficient list in ascending power

# Answer
> 4 votes
# Ruby/Crystal, 84 bytes

```
def f(n)n<1?[1]:([0]+f(n-1)).zip(f(n-2)+[0,0]).map{|i,j|('a'=="a"?1:2)*(i+j-n*j)}end

```

Try it online in Ruby! (probabilist)

Try it online in Crystal! (physicist)

Outputs in little-endian format, as in provided test cases.

This may look similar to a loophole of using different versions of the same language, but Crystal **is** a different language that just shares most of its syntax with Ruby. The languages are distinguished by their approach to quotes:

* In Ruby, both single and double quotes denote string literals
* In Crystal, single quotes denote chars, which do not pass equality check with analogous strings

# Answer
> 4 votes
# Using calculus package (for R)

## Jelly, probabilist, 51 bytes

```
\(n)calculus::hermite(n)[[n+1]]$t$c#¶1W¤Ż_×‘ɼ_Ɗ}Ḥʋ¡

```

Try it online!

## \>= 4.1, physicist, 51 bytes

```
\(n)calculus::hermite(n)[[n+1]]$t$c#1WÒ_ü¦_}¯©

```

Try it at RDRR

Try both online (sort of - no calculus package on tio so produces link to RDRR)

---

# No external packages

## Jelly, probabilist, 81 bytes

```
\(n){a=1[-1];for(i in seq_len(n))T=-c(a,0,0)*(i-1)+c(0,a<-T);T+0}#¶1W¤Ż_×‘ɼ_Ɗ}Ḥʋ¡

```

Try it online!

## \>= 4.1, physicist, 81 bytes

```
\(n){a=1[-1];for(i in seq_len(n))T=-c(a,0,0)*(i-1)+c(0,a<-T);T+0}#1WÒ_ü¦_}¯©

```

Try it online!

A full program in Jelly and a function in R both of which take an integer; the Jelly one takes it via STDIN. Note this is the same code for both, but in the Jelly codepage for Jelly and latin1 codepage for R. Both return the polynomial as the coefficients starting with the coefficient for \\$x^0\\$.

Python script to try both online

# Answer
> 4 votes
# Gol\>\<\> and  (902), 86 bytes

```
60.]{{'01IF00}L:2+F:}*$:@-{@@}}|{$2+F$}}||LFN~|h'
{{2*-/(0,p=:y),:p*#p}}^:y,1[p=:0$0}}

```

Try it online in Gol\>\<\>!

Try the equivalent code in J 806!

A full program in Gol\>\<\> that outputs He(n) in big endian, and a function in J that outputs H(n) in little endian.

## Gol\>\<\> path

Gol\>\<\> operates on a single stack of numbers, and the challenge requires zipping two lists and maintaining two previous states. So I decided to interleave the two coefficient lists on the stack.

```
60.    01IF00}L:2+F:}*$:@-{@@}}|{$2+F$}}||LFN~|h
60.    Jump into the main code
01     Push 0, 1  (-1th and 0th polynomial, respectively)
IF..|  Take n from input and repeat n times (L: 0..n-1)
       Example: 2nd iteration
       The stack content is 1 0 0 1, which represents two polynomials
       1   0     -> 1 (0th polynomial; P)
         0   1   -> x (1st polynomial; Q)
00}    Push a 0 at the top and another 0 at the bottom
         1   0   0   -> 1
       0   0   1     -> x^2
L:2+F..|    Push L, and then iterate L+2 times (L+2 is the number of pairs)
                   L
         1   0   0
       0   0   1
:}     Put a copy of L to the bottom of the stack
       L             L
           1   0   0
         0   0   1
*$:@-  Multiply L to the current coef of P, and subtract from that of Q
       L
           1   0   1-0*L
         0   0   1
{@@}}  Pull the copy of L back to the top, and rotate the two coefs to the bottom
                       L
         1-0*L   1   0
       1       0   0
       At the end of this loop:
                               L
         0-1*L   0-0*L   1-0*L
       0       0       1
{$2+F$}}|    Rotate once, consume L, and swap the positions for P and Q
       0       1       0         -> new P
         0-1*L   0-0*L   1-0*L   -> new Q
LFN~|h    Print Q from top to bottom and halt

```

## J path

A multi-line function evaluates each line sequentially, and returns the last line evaluated. So the relevant part is this (with `y` being the argument and `p` being a scratch global variable):

```
{{2*-/(0,p=:y),:p*#p}}^:y,1[p=:0$0

```

Within the inner function, `p` stores the previous polynomial, and the return value is the next polynomial. All polynomials are stored in little endian. As in the Gol\>\<\> part, `P` denotes the second-to-last polynomial and `Q` denotes the last polynomial.

```
{{2*-/(0,p=:y),:p*#p}}^:y,1[p=:0$0    y: value of n in H(n)
                            p=:0$0    Initialize P to zero polynomial
{{                  }}^:y,1[    Iterate inner func n times to [1]...
                p*#p    each item of P times length of P
      (0,p=:y),:    Zip two arrays Q*x and the above, and update p to Q
  2*-/    Subtract the 2nd row from 1st, and double

```

---

Just for fun and more golfiness, replacing J with the Mathematica built-in:

# Gol\>\<\> and Wolfram Language (Mathematica), 57 bytes

```
(*1IF00}L:2+F:}*$:@-{@@}}|{$2+F$}}||LFN~|h*)#~HermiteH~x&

```

Try it online in Gol\>\<\>!

Try it online in Mathematica!

These combine smoothly because the comment starter in Mathematica `(*` pushes a single 0 in Gol\>\<\>.

# Answer
> 1 votes
# Mathics \+ Wolfram Language (Mathematica), 44 bytes

```
Expand[s=Sqrt@Depth@{};HermiteH[#,x/s]/s^#]&

```

Try it online (Mathics physicist)!

Try it online (Mathematica probabilist)!

Mathics and Mathematica are two different implementations of the Wolfram Language. According to this meta post, they are considered different languages.

`Depth@{}` returns `1` in Mathics, `2` in Mathematica.

I'm not sure if `Expand` is necessary. Without it the Mathematica probabilist answer would return unsimplified results like `(-6*Sqrt[2]*x + 2*Sqrt[2]*x^3)/(2*Sqrt[2])`.

---
Tags: code-golf, polyglot, polynomials
---


title: Find the number of paths in a n×n grid

text:
# Question
Title: Find the number of paths in a n×n grid
### Information

* Given a **non-negative odd** integer (let's call it \\$n\\$), find the **number of all** possible paths which covers all squares and get from the start to end on a grid.
* The grid is of size \\$n\\$×\\$n\\$.
* The start of the path is the **top left** corner and the end is the **bottom right corner**.
* You have to count the number of all paths which go from the start to end which covers all squares exactly once.
* The allowed movements are up, down, left and right.
* In other words compute A001184, but numbers are inputted as grid size.

### Scoring

This is code-golf, write the shortest answer in bytes.

### Test cases

```
1  → 1
3  → 2
5  → 104
7  → 111712
9  → 2688307514
11 → 1445778936756068
13 → 17337631013706758184626

```

# Answer
# Python 3, 109 bytes

```
f=lambda n,x=0,*s:1-(x in s)and(x==n*n-1==len(s)or sum(f(n,x+a,x,*s)for a in(~x%n>0,x%n//-n,n,-n)if-1<x<n*n))

```

Try it online!

Port of my answer to Find the shortest route on an ASCII road. Brute forces all paths and returns the number of valid ones. Slow as molasses, though.

*-4 bytes thanks to Jakque*

*-8 bytes thanks to att*
> 5 votes

# Answer
# Jelly, 21 bytes

```
æịþḶFµḢ;ⱮṖŒ!;€ṪƲIỊẠ€S

```

Try it online!

Takes forever for `n>3` because it tries to generate all permutations of `n**2-2` items.

```
æịþḶFµḢ;ⱮṖŒ!;€ṪƲIỊẠ€S    Monadic link. Input: n
æịþḶF                    Generate complex numbers (1..n)+(0..n-1)i
     µḢ;ⱮṖŒ!;€ṪƲ         Generate all permutations with 1st and last fixed:
      Ḣ;Ɱ                  Chain 1st to each of...
         ṖŒ!;€               Permutations of the middle with...
              ṪƲ               The last chained to the end of each
                IỊẠ€S    Count those whose pairwise distances are all 1

```
> 4 votes

# Answer
# Python 3, 185 bytes

```
def f(n):k=range(n);v=[-~x+y*1j for x in k for y in k];return sum(all(abs(z-y)<=1for y,z in zip(x,x[1:]))for x in[[1]+[*q]+[v[-1]]for q in permutations(v[1:-1])])
from itertools import*

```

Try it online!

@Bubbler's Jelly answer port

-3 thanks to @KevinCruijssen
> 3 votes

# Answer
# 05AB1E, 27 bytes

```
LD<â©¨¦œε®нš®θªü2€øÆnOtΘP}O

```

Try it online!

Basic idea is like Bubblers, represent the grid as complex numbers, jumble all the intermediate cells between the first and last, and compute their distances and check if they are adjacent

a byte save thanks to @KevinCruijssen

**Explanation (pseudo-code)**

```
range
dup
decrement
cartesian product
copy to register (no pop)
cut tail
behead
permutations
map
  push register
  head
  prepend
  push register
  tail
  append
  cumulative pairs
  map
    zip
  deltas
  square
  sum
  square root
  equals 1?
  product
end map
sum

```
> 3 votes

# Answer
# Wolfram Language (Mathematica), 58 bytes

-3 bytes thanks to @att.

```
Length@FindPath[GridGraph@{#,#},1,#^2,{#^2-1},All]/. 0->1&

```

`n = 7` takes 3 minutes on my computer.

Try it online!
> 3 votes

# Answer
# 05AB1E, ~~36~~ 33 bytes

```
nÍLœε0šZ>ªü2εDI÷ËiÆëI‰ø`ËsÆ*]ÄPΘO

```

Brute-force approach generating permutations of the grid (minus first and last item), so times out for anything \\$n\>3\\$ (\\$n=3\\$ takes about 5 seconds).

Try it online.

**Explanation:**

Step 1: Generate all permutations of the list \\$\[1,n^2-2\]\\$, and prepend a leading \\$0\\$ and trailing \\$n^2-1\\$ to each:

```
n                 # Push the square of the (implicit) input-integer
 Í                # Decrease it by 2
  L               # Push a list in the range [1,n²-2]
   œ              # Pop and push all permutations of this list
    ε             # Map each permutation-list to:
     0š           #  Prepend a leading 0
       Z          #  Push the maximum (without popping the list)
        >         #  Increase it by 1
         ª        #  And append it as trailing item

```

Try just the first step.

Step 2: Check for each list whether it's a valid path:

```
ü2               #  Create overlapping pairs of the current list
  ε              #  Inner map the list of pairs to:
   D             #   Duplicate the current pair
    I÷           #   Integer-divide both integers in this copy by the input-integer
      Ëi         #   If both are the same (they're in the same row of the grid):
        Æ        #    Reduce the current pair by subtracting
       ë         #   Else:
        I‰       #    Divmod both integers in the current pair by the input-integer
          ø      #    Zip/transpose; swapping rows/columns
           `     #    Pop and push both pairs separated to the stack
            Ë    #    Check if the top pair (the [a%input,b%input]) are both the same
             s   #    Swap to get the other pair (the [a//input,b//input])
              Æ  #    Reduce it by subtracting
               * #    Multiply it to the a%input==b%input check
]                # Close the if-else statement and nested maps
 Ä               # Take the absolute value of each innermost integer
  P              # Taking the product of each inner list
   Θ             # Check for each if it's equal to 1 (1 if 1; 0 if not)

```

The `I÷Ë` checks if the integers in the current pair are in the same row of the grid, and with `Æ` \+ `Ä` it checks if their absolute difference is 1.
For any remaining pair that are not in the same row, the `I‰ø`ËsÆ*` \+ `Ä` checks if the two integers are in the same column and their absolute (vertical) difference is also 1.
The `P` after the map then checks if this was truthy for all of the pairs in the list.

Try the first two steps.

Step 3: Check how many valid paths were valid after the map, and output it as result:

```
O                 # Pop and sum to get the amount of valid paths
                  # (which is output implicitly as result)

```
> 2 votes

# Answer
# Charcoal, 82 bytes

```
ＮθＵＯθ#Ｊ⊖θ⊖θＰ0⊞υ⌕ＡＫＶ#≔⁰ηＷυ«≔⊟υι¿ι«⊞υι≔⊟ιιＭ✳⁻χ⊗ιＰＩι⊞υ⌕ＡＫＶ#»«≧⁺¬∨∨ⅈⅉ№ＫＡ#η✳⁻⁶⊗ＫＫ#»»⎚Ｉη

```

Try it online! Link is to verbose version of code. Will do `n=5` on TIO but larger numbers are probably too slow. Explanation: Works by counting the paths from the bottom right corner back to the top left corner of an `n×n` square drawn on the canvas.

```
Ｎθ

```

Input `n`.

```
ＵＯθ#

```

Draw an `n×n` square of `#`s.

```
Ｊ⊖θ⊖θＰ0

```

Start at the bottom right corner. (Any digit works here, it's just a placeholder showing that the square has been visited.)

```
⊞υ⌕ＡＫＶ#

```

Start with the possible moves from the corner. (This is empty for `n=1` of course.)

```
≔⁰η

```

Start with `0` paths found.

```
Ｗυ«

```

Repeat until all paths have been attempted.

```
≔⊟υι

```

Pop the remaining moves to try from the current cell from the stack.

```
¿ι«

```

If there are any moves left, then:

```
⊞υι

```

Push the moves back to the stack again.

```
≔⊟ιι

```

Pop the next move to try.

```
Ｍ✳⁻χ⊗ι

```

Move in that direction.

```
ＰＩι

```

Overwrite the current cell with the direction, so that we can find our way back, and also so that we don't try to re-enter the cell.

```
⊞υ⌕ＡＫＶ#

```

Push the available moves from this cell to the stack.

```
»«

```

Otherwise:

```
≧⁺¬∨∨ⅈⅉ№ＫＡ#η

```

If the current cell is at the top left and there are no `#`s left indicating that we've covered all of the squares, then increment the count of paths found.

```
✳⁻⁶⊗ＫＫ#

```

Overwrite the current cell with a `#` and move back to the previous cell.

```
»»⎚Ｉη

```

Clear the canvas and output the number of paths found.
> 2 votes

# Answer
# Python 3, 138 bytes

```
f=lambda n,a={0},x=0,y=0:n==len(a)/n<x+2<y+3or sum(f(n,a|{(x,y)},i,j)for i in range(n)for j in range(n)if(x-i)**2+(y-j)**2==1and{(i,j)}-a)

```

Try it online!

returns `True` for `f(1)`

## How it works :

take as input :

* `n` the size of the grid
* `a={0}` the set of all visited positions initialized with a `0` to avoid typing `set()`
* `x=0,y=0` the current position in the grid

then :

* `n==len(a)/n<x+2<y+3` verify if we visited all positions and if we are in the bottom right of the grid
* `f(n,a|{(x,y)},i,j)for i in range(n)for j in range(n) if`  recursively call `f` with all the position verifying

+ `(x-i)**2+(y-j)**2==1` the position is at distance `1` of `(x,y)`
    + `{(i,j)}-a` the position is unvisited
> 2 votes

---
Tags: code-golf, sequence, grid, matrix, path-finding
---


title: Sort by custom alphabet

text:
# Question
Title: Sort by custom alphabet
The challenge is to make a program that sorts a list of words, only that the words need to be in the order of a random given alphabet.

Your program will accept a string of comma-separated words and a new alphabet.
Your program will output every word in the same way in the new sorted order.

## Example:

Input:

```
home,oval,cat,egg,network,green bcdfghjklmnpqrstvwxzaeiouy

```

Output:

```
cat,green,home,network,egg,oval

```

This is a , so the winner is the person with the shortest program.

This is my first challenge so any improvements to the question/challenge are appreciated.

# Answer
> 2 votes
# CJam, ~~26~~ ~~19~~ 17 bytes

```
rr:A;',/{Af#}$',*

```

Try it online.

### Test case

```
$ cjam sort.cjam <<< 'home,oval,cat,egg,network,green bcdfghjklmnpqrstvwxzaeiouy'
cat,green,home,network,egg,oval

```

### How it works

```
rr                    " Read two whitespace-separated tokens from STDIN. ";
  :A;                 " Save the second token (the alphabet) in A.       ";
     ',/              " Split the remaining token at commas.             ";
        {Af#}$        " Sort by the chunks' characters' indexes in A.    ";
               ',*    " Join, separating by commas.                      ";

```

# Answer
> 4 votes
# Bash+coreutils, 37 bytes

```
tr ,$2 \\na-z<<<$1|sort|tr \\na-z ,$2

```

### Output:

```
$ ./alphasort.sh home,oval,cat,egg,network,green bcdfghijklmnpqrstvwxyzaeiouy
cat,green,home,network,egg,oval, $

```

# Answer
> 2 votes
# Pyth, 19 characters

```
j\,o_mx_zdNchczd\,

```

**Test:**

```
$ pyth -c "j\,o_mx_zdNchczd\," <<< 'home,oval,cat,egg,network,green bcdfghjklmnpqrstvwxzaeiouy'
cat,green,home,network,egg,oval

```

**Explanation:**

```
                            Implicit: d=" "
                            Implicit: z=input()
j\,                         ",".join(
   o                                 order_by(lambda N:
    _                                                  rev(
     m                                                     map(lambda d:
      x_zd                                                              rev(z).index(d),
      N                                                                 N),
    chczd\,                                            z.split(" "[0].split(",")

```

Essentially, it sorts the chunks, with a key of the list of indexes of the characters in the string, then joins them on commas. The reversal businesses is shorter than spliting the string again.

# Answer
> 2 votes
# , 49 bytes

```
function(w,a,`[`=chartr)"a-z"[a,sort(a["a-z",w])]

```

Try it online!

Translates words from given alphabet to `a-z`, then sorts and then translates back.

Uses flexible I/O rules (vector of words and alphabet as string).

---

With strict I/O rules it goes up by a lot ( is not very good with strings):

### , 112 bytes

```
function(s,`/`=strsplit,t=el(s/" "))paste(chartr("a-z",t[2],sort(chartr(t[2],"a-z",el(t[1]/",")))),collapse=",")

```

Try it online!

Here we do the splitting of the input string inside the function.
First, we redefine `/` to be `strsplit`. It always returns a list, so we will need to extract the first element (which is shortest done by `el`). We split the words from the alphabet on  and then the words themselves on `,`.
Then we do the same trick as in the main answer.
At the end we collapse the whole vector with `,` using `paste`.

---

With many strange function redefinitions:

### , 111 bytes

```
function(s,`?`=el,`[`=chartr,`/`=strsplit,t=?s/" ")paste("a-z"[t?2,sort((t?2)["a-z",?(t?1)/","])],collapse=",")

```

Try it online!

Here we also redefine `[` to be `chartr`, so we cannot use `[` to subscript `t` anymore, but we can use `el` for this purpose.
This leads us also to redefining `?` to be `el` (after some trial and error with operator precedence). It is worth noting, that `?` can act as binary and unary operator and has the lowest precedence of all.

# Answer
> 2 votes
# K (ngn/k), 23 bytes

```
{","/x@<y?x:","\x}." "\

```

Try it online!

Takes input as outlined in question.

* `" "\` split input on the space, into the list of comma-delimited words and the (shuffled) alphabet
* `{...}.` call the function with the list of words as the first arg (`x`) and the alphabet as the second arg (`y`)
* `x:","\x` split the string of comma-delimited words into a list of the words themselves, updating the `x` variable
* `y?x` look up the index of each character in each word in the shuffled alphabet
* `x@<` grade the resulting list of lists of indices, and apply the sort order to the list of words
* `","/` join the individual words with commas

# K (ngn/k), 8 bytes

```
{x@<y?x}

```

Try it online!

Assumes more lenient input/output format; a first arg `x` of a list of words, and a second arg `y` containing the shuffled alphabet. A list of strings is returned instead of a comma-delimited string.

# Answer
> 1 votes
## Ruby, ~~53~~ 50 bytes

```
a,b=$*
$><<a.split(?,).sort_by{|w|w.tr b,'a-z'}*?,

```

I'm using Ruby's `tr` to replace the custom alphabet with `a-z` before sorting. Input is via command-line argument.

# Answer
> 1 votes
## Clojure, ~~115~~ 50 bytes

Oh, an edit five years later :D And actually in the past I out-golfed myself, now I used `(map char(range 97 123))` to generate the `a - z` sequence but my original answer just re-uses the alphabet input via `(sort %2)`. Well this new answer requires a more liberal input format, namely the first argument is a list of words.

```
#(map(fn[i](str(mapv(zipmap %2(sort %2))i)))%)

```

I had to re-discover that vectors don't sort neatly, but this can be avoided by casting them to strings. And not by using `clojure.string/join` or `apply str`, they sort just fine as string representations of the vector! Change the `sort-by` to `map` and you get:

```
(def f #(map(fn[i](str(mapv(zipmap %2(sort %2))i)))%))

(f ["home", "oval", "cat", "egg", "network", "green"] "bcdfghjklmnpqrstvwxzaeiouy")

("[\\f \\x \\j \\v]"
 "[\\x \\q \\u \\i]"
 "[\\b \\u \\p]"
 "[\\v \\e \\e]"
 "[\\k \\v \\p \\r \\x \\n \\h]"
 "[\\e \\n \\v \\v \\k]")

```

TIO

**Original answer:**

```
#(apply str(butlast(interleave(sort-by(fn[w](apply str(map(zipmap(sort %2)%2)w)))(re-seq #"[a-z]+"%))(repeat \,))))

```

Wow, this started of well with `(sort-by(fn[w](mapv(zipmap(sort %2)%2)w)))` but then I realized `vec` don't get sorted the same way as strings, and interleaving those commas takes significant amount of code as well.

# Answer
> 1 votes
# 05AB1E, 15 bytes

```
#`U',¡ΣXsSk}',ý

```

Try it online.

With less restricted I/O rules, this could have been **2 (or 3) bytes**:

**Explanation:**

```
#            # Split the (implicit) input-string by spaces
 `           # Pop and push both strings separated to the stack
  U          # Pop the alphabet-string, and store it in variable `X`
   ',¡      '# Split the words-string on ","
      Σ      # Sort this list of words by:
       X     #  Push the alphabet-string `X`
        s    #  Swap so the current word is at the top of the stack again
         S   #  Convert it to a list of characters
          k  #  Get the index of each character in the alphabet-string
      }',ý  '# After the sort-by: join this list of words with "," delimiter
             # (after which this string is output implicitly as result)

Σ            # Sort the first (implicit) input-list of character-lists by:
 k           #  Index each character into the second (implicit) alphabet-string
             # (after which the sorted list of character-lists is output implicitly)

```

# Answer
> 0 votes
# JavaScript (E6) 102 ~~119~~

Sort with a mapping function 'M' based on the alphabet in variable 'a'
*With IO using popup (prompt + alert)*

```
x=prompt().split(/[ ,]/),
a=x.pop(),
M=w=>[10+a.search(c)for(c of w)]+'',
alert(x.sort((a,b)=>M(a)>M(b)))

```

*As a (testable) function with 1 string parameter, returning a string array (92)*

```
F=x=>(
  M=w=>[10+a.search(c)for(c of w)],
  x=x.split(/[ ,]/),
  a=x.pop(),
  x.sort((a,b)=>M(a)>M(b))
)

```

**Test** In FireFox/FireBug console

```
F('home,oval,cat,egg,network,green zyxwvtsrqpnmlkjhgfdcbaeiou')

```

*Output*

```
["network", "home", "green", "cat", "egg", "oval"]

```

# Answer
> 0 votes
# Python, 131

```
w,a=input().split()
print(",".join(sorted(w.split(","),key=lambda s:"".join(["abcdefghijklmnopqrstuvwxyz"[a.find(c)]for c in s]))))

```

There should be plenty of room for improvement.

# Answer
> 0 votes
# Pip, 15 bytes

```
b@?^_SKa^',J:',

```

Takes the two inputs as command-line arguments. Try it online!

### Explanation

```
b@?^_SKa^',J:',
       a         ; First command-line arg (list of words)
        ^',      ; Split on commas
     SK          ; Sort by the following key function:
   ^_            ;   Split the word into a list of letters
 @?              ;   Get the index of each letter in
b                ;   The second command-line arg (alphabet)
           J:',  ; Join the resulting list on commas

```

# Answer
> 0 votes
# Japt, 12 bytes

```
¸Îq, nU¸Ì q,

```

Try it

# Answer
> 0 votes
# Zsh, 24 bytes

```
tr $1 a-z|sort|tr a-z $1
```

Attempt This Online!

If we must use the OP's inane I/O format, 37 bytes:

```
tr $2, a-z\\n<<<$1|sort|tr a-z\\n $2,
```

Attempt This Online!

If a trailing comma is not allowed either, append `|head -c-1` for +10 bytes.

# Answer
> 0 votes
# Python 3, 50 bytes

With flexible input :

```
lambda w,a:sorted(w,key=lambda s:[*map(a.find,s)])

```

Try it online!

# Python 3, 71 bytes

With strict input format :

```
lambda x:sorted(x[:-27].split(","),key=lambda s:[*map(x[-26:].find,s)])

```

Try it online!

Both can be shortened by 3 bytes in python 2 by removing `[* ]` arround the `map`

---
Tags: code-golf, sorting
---


title: Is This Scrabble Board Valid?

text:
# Question
Title: Is This Scrabble Board Valid?
#### Background

*Scrabble* is a word game in which players collaboratively build a board consisting of letter tiles that spell words. Each word must be connected to another word, and players gain points based on the letters they use and where they are placed. Words can be spelled either from left-to-right or top-to-bottom, and their validity is determined via the Scrabble Dictionary. Each contiguous set of more than one letter in a row or column must be a valid word.

#### The Challenge

Your challenge is to write a function that accepts a 2D grid of letters and determines whether or not it consitutes a valid Scrabble board. A board is valid if every word in every column and row is a valid word according to this text file containing a Scrabble Dictionary.

Your function should take a 2D grid of characters and a list of valid words as input. The board is assumed to be contiguous (every word is connected to the board) and padded with spaces to be rectangular. Your function must return a truthy value of your choice if the board is valid, and a falsey one otherwise. The board is assumed to contain at least 2 letters. This is Code Golf, so the shortest answer wins, and the usual rules/loopholes apply.

#### Test Cases

All boards' validity is determined according to this list of Scrabble words.

Valid boards:

```
MAP
O APP
NEW O
T EEL
HAD E

```

---

```
DANCING
  A
  SEEING
  A    O
  LAZY T

```

---

```
SORDID
O U
LEEWAY
E
L
YESTERDAY
       A

```

Invalid boards:

```
MOLAR
A
RATS
CR
HC
 H

```

---

```
RASCAL
A
BAKING
B   OO
ISLAND
T

```

---

```
JOYFUL
  OFFER

```

# Answer
# Jelly, ~~12~~ 9 bytes

-3 bytes thanks to Jonathan Allan

A dyadic function taking a list of lines on the left and a list of words on the right.

```
Z;⁸KḲḊƇfƑ

```

Try it online!

```
Z;⁸         -- concatenate list of columns and list of rows
   KḲ       -- join on spaces and split on spaces to get list of words
      Ƈ     -- keep words that are truthy (non-empty)
     Ḋ      --   when the first character is removed
         Ƒ  -- is this resulting word list invariant when
        f   --   all words not in the dictionary are removed?

```
> 12 votes

# Answer
# Ruby, ~~60~~ 57 bytes

```
->b,d{(b+b.transpose).all?{|c|d==d|c.join.scan(/\w\w+/)}}

```

Try it online!

Takes the board as a list of lists of characters. Returns `true` for valid boards, `false` otherwise.

The board is valid if for every word on the board, the union of that word with the dictionary is equal to the dictionary.
> 7 votes

# Answer
# Python 3, ~~138~~ \\$\cdots\\$ ~~86~~ 79 bytes

```
lambda b,d:all(i in d+[*s]for s in[*map(''.join,zip(*b))]+b for i in s.split())

```

Try it online!

*Saved a whopping ~~27~~ 33 bytes thanks to Bubbler!!!*
*Saved 7 bytes thanks to Jonathan Allan!!!*
*TIO testing now works thanks to ovs and Bubbler!!!*

Inputs the boards as a list of strings (space padded so they're all the same length) and the dictionary as a list of strings.
Returns `True` for a valid board or `False` otherwise.
> 4 votes

# Answer
# Gaia, 8 bytes

Basically the same as my Jelly answer, but Gaia has a superset builtin.

```
:t+ṡṡḥ⁇⊃

```

Try it online!

```
:t+ṡṡḥ⁇⊃     -- function that expects a 2d-list character above the dictionary as a list of strings
:t           -- duplicate the grid on the stack and transpose the copy
  +          -- append transpose to original grid
   ṡ         -- join list by spaces
    ṡ        -- split resulting string on spaces
     ḥ⁇      -- keep words that are truthy when the first character is removed
       ⊃     -- is the dictionary a superset of this word list

```

only considers unique item and a list is a superset of itself ( might've been a more accurate symbol). Almost all operators in Gaia are overloaded for different types, which is why  can both split and join.
> 3 votes

# Answer
# 05AB1E (legacy), 12 bytes

```
Dø«ðý#ʒ¦Ā}åP

```

First input is the board as a list of string lines; second is a list of words.

Uses the legacy version of 05AB1E, because it can zip/transpose lists of strings, where in the new version zip/transpose can only be done on character-matrices.

Try it online.

**Explanation:**

```
D          # Duplicate the first (implicit) input-list
 ø         # Zip/transpose; swapping rows/columns
  «        # Merge the two lists together
   ðý      # Join the strings with space delimiter
     #     # Then split the entire string by spaces
      ʒ    # Filter this list of strings:
       ¦   #  Remove the first character
        Ā  #  And check if it's non-empty
      }    # After the filter: we have a list of the words
       å   # Check for each word if it's in the second (implicit) input-list
        P  # Check if this is truthy for all of them
           # (after which the result is output implicitly)

```

I came up with it independently, but I noticed it's basically a port of *@ovs*' Jelly answer, with just larger builtins / stack management. (For convenient I also copied their test case to my TIO.)
> 2 votes

# Answer
# Kotlin, ~~159~~ 129 bytes

```
{d,b->(b+b[0].indices.map{c->b.indices.joinToString(""){"${b[it][c]}"}}).all{r->r.split(" ").filter{it.length>1}.all{w->w in d}}}

```

-30 bytes thanks to using lambda and type inference (Parlor Trick)

Try it online!

**Explanation:**

First, merge the original and transposed board. In each row, find all words longer than 1 letter and for all of them, check their presence in the dictionary.
> 1 votes

# Answer
# Japt, 12 bytes

```
cUy)¸¸fÅe!øV

```

Try it
> 1 votes

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


title: Alphabet Reconstruction

text:
# Question
Title: Alphabet Reconstruction
You are a historian studying a long forgotten language. You have just discovered a clay tablet which seems to list all known words in the language, in alphabetical order. Your task is to find this alphabet's order, if it exists.

## The Task

Given an ordered list of words, try to output an ordered list of characters such that:

1. Every character of the words in the word list appears exactly once in the character list.
2. The word list as given is sorted "alphabetically" according to the character list.

If (and *only* if) no character list is able to satisfy these requirements, output a falsy/fail value of your choice. You must specify in your answer the value you have chosen.

Notably, it is possible that more than one alphabet ordering is valid for a given list of words; If we have the words Cod, Com, and Dy, all that can be assumed is that C comes before D, and d comes before m. The letters o and y have various valid positions in the generated alphabet. For more clarity, here are some (but not all) valid outputs for that word list:

```
Input: Cod Com Dy
Output: CDdmoy
Output: CDdmyo
Output: CDdomy
Output: CoDdym
Output: dmCDoy
Output: dCmDoy
Output: CdoymD
Output: dyCoDm
Output: yodmCD

```

If there are multiple valid character lists, your code must output either *one* valid answer or *all* valid answers, consistently.

## Rules

* Your input is a list of words, which may be input in any reasonable format. Output only languages are allowed to include this word list in their initial data/program at no additional byte cost.
* The word list will contain at least two words, and no two words will be identical.
* Any alphanumeric character `[A-Za-z0-9]` may be included as a character in the wordlist.
* Words are read from left to right, and are alphabetized first by leftmost character, then by the next character, etc.
* Two words which begin with the same substring are only alphabetized if the shorter of the two comes first (e.g. "CAR" must come before "CARP").
* Uppercase and lowercase forms of the same character are considered to be different characters, i.e. the alphabet is case sensitive.
* You may output each alphabet in any reasonable format, but each must contain every character present in the word list exactly once, and no other characters. (This requirement, of course, does not apply to falsy/fail outputs)

## Examples

Your correct outputs may not match all these, as any given wordlist may have more than one proper alphabet. Some may only have one valid answer.

```
Input: bob cat chat dog hat hot guy
Output: tuybcdaohg

Input: A Aa AA Bb Ba
Output: baAB

Input: 147 172 120 04 07
Output: 14720

```

### Falsy output examples

These *should* all be falsy outputs, and can be used as test cases.

```
Input: GREG HOUSE ROCK AND ROLL
Output: [falsy]

Input: b5OtM bb5O MO Mtt 5
Output: [falsy]

Input: a aa aaa aaaaa aaaa
Output: [falsy]

```

## Scoring

This is , shortest code wins. :)

# Answer
> 5 votes
# Vyxal, 21 bytes

```
∑UṖ'→?µ←:₃[nL|β];?⁼;h

```

Try it Online!

Outputs a single possible alphabet. Times out for inputs with larger alphabets because it checks all permutations of the character set of the input. Exits with an error if falsey.

14 if `a aa aaa aaaaa aaaa` wasn't falsey. Much shorter if base conversion wasn't so janky.

## Explained (in theory if base conversion wasn't so janky)

```
∑UṖ'→?µ←ðpβ;?⁼;h
∑U                # Get all unique characters of the input
  Ṗ               # and then all permutations of that.
   '              # From that, keep only items (n) where
    →?µ←ðp;       #    the input sorted by conversion to bijective base n with a space prepended to make everything non-zero
            ?⁼   #    equals the original input (⁼ is non-vectorising equals)
              ;h # and get the first from that

```

I actually got to use the ghost variable and variable scoping for once.

# Answer
> 4 votes
# Jelly, 11 bytes

Returns all valid alphabets and the empty list as a falsy value.

```
FQŒ!iⱮⱮṢƑ¥Ƈ

```

Try it online!

```
F            -- flatten the word list into a single string
 Q           -- get the unique characters
  Œ!         -- get all permutations of those characters
          Ƈ  -- keep the permutation that return a truthy value for:
         ¥   --   group the last two links into dyad
             --   which is called with the permutation on the left and the word list on the right
    iⱮⱮ      --   for each character of each word get its index in the permutation
       ṢƑ    --   is the resulting list invariant under sorting?

```

# Answer
> 4 votes
# Charcoal, ~~92~~ 76 bytes

```
ＷＳ⊞υι≔⟦⟧θ≔ ηＷ⌈⁻⪪⪫υω¹θ«⊞θι≔⭆⪪ηＬθ⭆κ⭆κ⁺ξ⎇⁼νπιωη»ＥΦ⪪η⊕Ｌθ⬤υ⬤υ⁼‹μξ‹⍘◨λＬνι⍘◨νＬλιΦιμ

```

Try it online! Link is to verbose version of code. Takes input as a newline-terminated list of words (space-terminated works, but it's easy to forget the trailing space) and outputs all orderings (the orderings themselves are output in ASCII order). Even slower now for larger character sets. Explanation:

```
ＷＳ⊞υι

```

Input the list of words.

```
≔⟦⟧θ

```

Start with no characters processed.

```
≔ η

```

Start with a space-prefixed list of one element, the empty string.

```
Ｗ⌈⁻⪪⪫υω¹θ«

```

Repeat until all distinct characters have been processed.

```
⊞θι

```

Mark this character has having been processed.

```
≔⭆⪪ηＬθ⭆κ⭆κ⁺ξ⎇⁼νπιωη

```

Generate all permutations of the characters so far.

```
»ＥΦ⪪η⊕Ｌθ⬤υ⬤υ⁼‹μξ‹⍘◨λＬνι⍘◨νＬλιΦιμ

```

Filter those permutations which are valid orderings, removing the space prefix. Words are compared by padding them to the same length, then performing custom base conversion with the space-prefixed permutation.

# Answer
> 3 votes
# JavaScript (Node.js), 146 bytes

```
a=>(g=s=>s[0]?g(s.filter(c=>a.some(w=>s.includes((r=/(.*)(.?).*,\1(.)/.exec([p,p=w]))[2])&&r[3]==c,p='')||!(q+=c))):q)([...new Set(a.join(q=''))])

```

Try it online!

# Answer
> 3 votes
# 05AB1E, 11 bytes

```
˜ÙœʒIkðýD{Q

```

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

I/O as a list of character-lists. Outputs all possible alphabet-lists.

Should have been **9 bytes** without the `ðý`, but there is a weird bug when sorting after we've just indexed apparently..

Try it online or verify most test cases (two of them are removed because they time out).

**Explanation:**

```
˜          # Flatten the (implicit) input-list of character-lists
 Ù         # Uniquify this list of characters
  œ        # Get all its permutations
   ʒ       # Filter this list of lists by:
    Ik     #  Get the index of each character of the input-list of lists
      ðý   #  (Bug workaround: join each inner list by spaces)
      D    #  Duplicate the list
       {   #  Sort the copy
        Q  #  And check if it's still the same
           # (after which the resulting list of character-lists is output implicitly)

```

# Answer
> 3 votes
# Japt v2.0a0, 11 bytes

Returns `undefined` for inputs without a solution.

```
¬â á æ@eUnX

```

Try it

# Answer
> 1 votes
# \+ gtools, 162 bytes

```
function(w,a=unique(unlist(strsplit(w,""))),l=length(a))for(x in apply(gtools::permutations(l,l,a),1,Reduce,f=paste0))if(!is.unsorted(chartr(x,"a-z",w)))return(x)

```

Try it online!

Iterates through all permutations (calculated by gtools package as I didn't have the heart to do it myself) of used alphabet and checks whether sorting by it gives desired result. This is done by translating the characters to `a-z` and using built-in `is.unsorted`.

Returns nothing as falsy.

---
Tags: code-golf
---


# Question
Title: Make S + S + ... + S as Large as Possible!
Let \\$S \subset \mathbb N\_{\geq0}\\$ be a subset of the nonnegative integers, and let $$ S^{(k)} = \underbrace{S + S + \dots + S}\_{k\ \textrm{times}} = \\{ a\_1 + a\_2 + \dots + a\_k : a\_i \in S\\}. $$

For example, $$\begin{align} \\{1,2,3\\}^{(2)} &= \\{1+1, 1+2, 1+3, 2+1, 2+2, 2+3, 3+1, 3+2, 3+3\\}\\ &=\\{2,3,4,5,6\\} \end{align}$$

If \\$S\\$ contains \\$n\\$ elements, then \\$S^{(k)}\\$ contains at most \\$\binom{n+k-1}{k} = \frac{(n + k - 1)!}{(n-1)!k!}\\$ distinct elements. If \\$S^{(k)}\\$ contains this number of distinct elements, we call it \\$k\\$-maximal. The set \\$S = \\{1,2,3\\}\\$ given in the example above is *not* \\$2\\$-maximal because \\$1 + 3 = 2 + 2\\$.

## Challenge

Given a positive integer `k`, your task is to return the lexicographically earliest infinite list of nonnegative integers such that for every \\$n\\$ the set consisting of the first \\$n\\$ terms of \\$S\\$ is \\$k\\$-maximal.

You can return a literal (infinite) list/stream, you can provide function that takes a parameter `i` and returns the \\$i\\$th element of the list, or you can give any other reasonable answer.

This is so shortest code wins.

### Test Data

```
 k | S^(k)
---+------------------------------------------------------------
 1 | 0, 1, 2,  3,   4,   5,    6,    7,     8,     9,    10, ...
 2 | 0, 1, 3,  7,  12,  20,   30,   44,    65,    80,    96, ...
 3 | 0, 1, 4, 13,  32,  71,  124,  218,   375,   572,   744, ...
 4 | 0, 1, 5, 21,  55, 153,  368,  856,  1424,  2603,  4967, ...
 5 | 0, 1, 6, 31, 108, 366,  926, 2286,  5733, 12905, 27316, ...
 6 | 0, 1, 7, 43, 154, 668, 2214, 6876, 16864, 41970, 94710, ...

```

For \\$k=2\\$ , this should return OEIS sequence A025582.

For \\$k=3\\$ , this should return OEIS sequence A051912.

# Answer
# Jelly, 15 bytes

```
»*@Żœcḷœċ§QƑɗƇḢ

```

Try it online!

Takes `i` and `k` and returns the first `i` elements of the `k`th sequence. Extremely slow.

The `i`th term (1-indexed) cannot exceed `1+k+..+k**(i-2)` since the `k`-combinations without replacement of the set `0, 1, 1+k, 1+k+k**2, ..., 1+k+...+k**(i-2)` has distinct sums (because each added term is strictly larger than the previously existing maximum sum) and, as the terms strictly smaller than the bound emerge, the bound for the next term will only go lower. This bound can be relaxed to `max(i, k**i)` by considering the cases where `k=1` and `k>=2`.

```
»*@Żœcḷœċ§QƑɗƇḢ    Dyadic link. Left = i (#terms to return), Right = k
»*@                bound = max(i, k**i)
   Żœcḷ            All i-combinations of 0..bound
             ƇḢ    Filter and take the first sequence satisfying...
       œċ§QƑɗ        All k-combinations without replacement have distinct sums

```
> 3 votes

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

```
(k,a=[],n=-1,g=_=>(h=(c,u,p)=>c?a.every(v=>v<p||h(c-1,v+u,v)):h[u]^=1)(k,a.push(++n))?n:g(a.pop()))=>g

```

Try it online!

Invoke `f(k)`, it returns a function `g`. Each time you invoke `g()`, you will get the next value of `k`-th sequence.
> 4 votes

# Answer
# JavaScript (ES6), 113 bytes

Expects `(k)(n)` and returns the first \\$n\\$ terms of \\$S^{(k)}\\$ in reverse order.

```
k=>n=>(g=a=>(h=(a,k,s)=>k?a.every((v,i)=>h(a.slice(i),k-1,v-~s)):h[s]^=1)(a,k)?n--?g([0,...a]):a:g(a,a[0]++))([])

```

Try it online!
> 3 votes

# Answer
# Python 3.8, ~~130~~ ~~106~~ 105 bytes

Thanks to Neil for pointing out a mistake.

Saved a lot of bytes by looking at @AZTECCO's Haskell answer and realizing I don't need to keep track of the maximum number of unique sums.

```
def f(k):
 r=1,*[0]*k;j=-1
 while 1:
  j+=1;d=0;w=[d:=i|d<<j for i in r]
  if r[k]&w[-2]<<j<1:yield j;r=w

```

Try it online!
> 3 votes

# Answer
# Charcoal, 70 bytes

```
ＮθＮη≔⁰ζＷ‹Ｌυη«⊞υζ≦⊕ζ≔ＥΦＥＸＬυθ﹪Ｅθ÷κＸＬυνＬυ¬⊙κ∧ν›μ§κ⊖νΣＥκ§υμε¿⊙ε⊖№εκ≔⊟υε»Ｉυ

```

Try it online! Link is to verbose version of code. Takes `k` and `n` as input and outputs the first `n` terms. Explanation:

```
ＮθＮη

```

Input `k` and `n`.

```
≔⁰ζ

```

Start with a first trial term of `0`.

```
Ｗ‹Ｌυη«

```

Repeat until enough terms have been collected.

```
⊞υζ

```

Push the next trial term to the list of terms.

```
≦⊕ζ

```

Increment the trial value.

```
≔ＥΦＥＸＬυθ﹪Ｅθ÷κＸＬυνＬυ¬⊙κ∧ν›μ§κ⊖νΣＥκ§υμε

```

Calculate all of the sums of combinations with replacement of the terms including the trial term.

```
¿⊙ε⊖№εκ≔⊟υε

```

If there are any duplicates then remove the trial term from the list.

```
»Ｉυ

```

Output the resulting list.

63 bytes by porting @ovs's Python answer:

```
ＮθＮη≔±¹ζ≔Ｅ⊕θ¬κεＷ‹ⅉη«≦⊕ζ≔⟦⟧δＦε⊞δ｜κ×∨⌈δ⁰Ｘ²ζ¿¬＆§ε±¹×§δ±²Ｘ²ζ«≔δε⟦Ｉζ

```

Try it online! Link is to verbose version of code. Takes `k` and `n` as input and outputs the first `n` terms. Explanation:

```
ＮθＮη

```

Input `k` and `n`.

```
≔±¹ζ

```

Start the trial term at `-1` so that `0` can be considered with an initial increment on the first pass.

```
≔Ｅ⊕θ¬κε

```

Start with a list of `1` and `k` `0`s, which are bitmasks representing the sets of sums of `i` elements of the empty set; the first set is the set of sums of zero elements which is always `{0}` while the others are empty sets.

```
Ｗ‹ⅉη«

```

Loop until `n` terms have been printed.

```
≦⊕ζ

```

Increment the next trial term.

```
≔⟦⟧δＦε⊞δ｜κ×∨⌈δ⁰Ｘ²ζ

```

Using the bitmasks from the terms so far, calculate the bitmasks for the sets of sums of `i` elements from them plus the current trial term.

```
¿¬∧ζ＆§ε±¹×§δ±²Ｘ²ζ«

```

If there are no collisions between the sums of `k` elements excluding the current trial term and the sums of `k` elements including the current trial term at least once, then...

```
≔δε

```

... save the new bitmasks, and...

```
⟦Ｉζ

```

... output the current trial term on its own line.
> 3 votes

# Answer
# 05AB1E, 18 bytes

```
m‚àÝI.Æ.Δ¹ã€{ÙODÙQ

```

Port of *@Bubbler*'s Jelly answer, but lacking a `k-combinations without replacement` builtin.

First input is \\$k\\$, second input is \\$i\\$. Outputs the first \\$i\\$ elements of the \\$k^{th}\\$ sequence.

Try it online.

**Explanation:**

```
m                  # Push the first (implicit) input to the power of the second
                   # (implicit) input: k**i
 ‚                 # Pair it together with the second (implicit) input: [i,k**i]
  à                # Pop and push the maximum
   Ý               # Pop and push a list in the range [0,max(i,k**i)]
    I.Æ            # Pop and get all i-element combinations of this list
       .Δ          # Find the first list which is truthy for:
                   #  Get all k-combinations without replacement:
         ¹ã        #   Take the current list to the cartesian power of the first input k
           €{      #   Sort each inner list
             Ù     #   Uniquify this list of lists
              O    #  Get the sum of each inner list
                   #  Check that all sums are unique:
               D   #   Duplicate the list of sums
                Ù  #   Uniquify the copy
                 Q #   Check if both lists are still equal
                   # (after which the result is output implicitly)

```
> 2 votes

# Answer
# Haskell, ~~109~~ 103 bytes

```
s#k=sum<$>mapM(\_->s)[1..k]
f=([0]!)
(n:s)!k|any(`elem`s#k)$map(+n)$s#(k-1)=(n+1:s)!k|1>0=n:(n+1:n:s)!k

```

Try it online!

* thanks to @Ovs for suggesting using sum\<$\>.. instead of map(sum)..

Essentially we search next term by checking if the sums with it creates only new sums.

* f returns an infinite list of *k* using an initial set \[0\] applied to (!)
* (n:s)!k finds all next terms indefinitely
*|any(`elem`s#k)$...* if any of ... Are in s#k try next *n*
... *map(+n)$s#(k-1)* permutations of k-1 + n
else we add *n* to the set and we search next terms
* s#k returns all permutations of *s* of length *k* summed.
Stolen from this answer of Laikoni

Try k=5

Try k=6
> 2 votes

---
Tags: code-golf, math, sequence, arithmetic, combinatorics
---


title: Self-referential triangle sequence

text:
# Question
Title: Self-referential triangle sequence
Output the flattened version of the sequence A297359, which starts like the following:

```
1, 1, 1, 1, 2, 1, 1, 3, 3, 1, 2, 4, 6, 4, 2, 1, 6, 10, 10, 6, 1,
1, 7, 16, 20, 16, 7, 1, 3, 8, 23, 36, 36, 23, 8, 3, 3, 11, 31, 59,
72, 59, 31, 11, 3, 1, 14, 42, 90, 131, 131, 90, 42, 14, 1,...
----------------
                  1,
                1,   1,
              1,  2,   1,
            1,  3,   3,  1,
          2,  4,  6,   4,  2,
        1,  6,  10, 10,  6,  1,
      1, 7,  16,  20,  16,  7, 1,
    3, 8,  23,  36, 36,  23,  8, 3,
  3, 11, 31, 59,  72,  59, 31, 11, 3,
1, 14, 42, 90, 131, 131, 90, 42, 14, 1,
...

```

The defining property of the sequence is that

* the entire triangle is generated like the Pascal's triangle (i.e. each entry inside the triangle is the sum of the two numbers above it), and
* the left and right boundaries are identical to the entire triangle read by rows.

Standard rules and I/O methods apply. See https://codegolf.stackexchange.com/tags/sequence/info and https://codegolf.stackexchange.com/tags/code-golf/info.

The shortest code in bytes wins.

# Answer
# Haskell, 61 bytes

```
1:t
r!b=b:zipWith(+)r(tail r)++[b]
t=1:tail(scanl(!)[]t>>=id)

```

Try it online!

Feels a bit clunky, and frankly I'm not entirely sure I understand what I've done with both of those explicit leading ones.
> 8 votes

# Answer
# 05AB1E, ~~14~~ 13 bytes

```
λε=Dˆ}ü+¯Nè.ø

```

Infinitely outputs each integer on a separated line.

-1 byte thanks to *@ovs*.

Try it online.

**Explanation:**

```
λ          # Create a recursive environment,
           # starting with a(0)=1 by default
           # And we calculate every following a(n) as follows:
 ε         #  Map over the integers in the current list (or the digit(s) of the 1):
  =        #   Print the current integer with trailing newline (without popping)
   Dˆ      #   Add a copy of the integer to the global array
 }ü        #  After the map: map over the overlapping pairs:
   +       #   And sum them together
    ¯Nè    #  Index `n` of the recursive environment into the global array
       .ø  #  And surround the list with this integer as leading/trailing item

```
> 4 votes

# Answer
# Python 3, 94,93(@xnor),88(use infinite generator),83(smarter buffering),79(obvious saving),67 bytes(@dingledooper)

```
*P,z=p=1,1
for x in P:print(z);z,*q=p;p=x,*map(sum,zip(p,q)),x;P+=p

```

Try it online!

I doubt this is competitive, but there is only one way to find out...Beginning to get the hang of it.

The code works row-by-row (the computation, output is element by element) and is pretty straight-forward, the only mildly tricky thing being that the for loop actually sees the intermittent updates of the P list (This relies on `+=` actually being equivalent to `.extend` which also allows us to be a bit cavalier with list vs tuple). And perhaps the backwards-in-time order of assignments towards the yieldprint statement whose effect is a two-cycle-buffering (z is the x from two iterations ago).

Old version

Old version

Old version

Old version
> 4 votes

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

```
f=(n,l=0,a=[],x)=>a[n]||(n<2?1:f(n-l,a.push(x),a.map(m=>x+(x=m)||f(l))))

```

Try it online!

---

# JavaScript (Node.js), 74 bytes

```
f=(n,q=(n*8+1)**.5,r=q-1>>1)=>n>1?(n*8+9)**.5%1&&q%1?f(n+~r)+f(n-r):f(r):1

```

Try it online!

I have no idea whether following 70 byte version works or not. If you can prove its correctness or find out failed testcases, please leave a comment here:

```
f=(n,q=(n*8+1)**.5,r=--q>>1)=>n>1?q%2<2-2/r&&q%2?f(n+~r)+f(n-r):f(r):1

```

Try it online!
> 2 votes

# Answer
# Appleseed, 127 bytes

```
(def T(q(((R(q(1)))(S(concat(q(1 1 1))(drop 4(T)))))(concat R(T(cons(head S)(insert-end(head S)(zip-with add(tail R)R)))(tail S

```

Defines a function `T` that takes no arguments and returns the sequence as an infinite list. Try it online!

### Ungolfed + explanation

```
(def TriSeq
  (lambda
    ((Row (q (1)))
     (Seq (concat (q (1 1 1)) (drop 4 (TriSeq)))))
    (concat Row
      (TriSeq
        (cons (head Seq)
          (insert-end (head Seq)
            (zip-with add (tail Row) Row)))
        (tail Seq)))))

```

`TriSeq` builds the sequence one triangle row at a time. It takes two optional arguments: `Row`, the current row, and `Seq`, the sequence up to this point. The first row is the default value for `Row`, `(q (1))`, a list containing a single 1. After that, the interior portion of the next row is calculated from `Row` by `(zip-with add (tail Row) Row)`. The exterior numbers come from the next element in the sequence, `(head Seq)`. `Seq` is initialized by its default value, `(concat (q (1 1 1)) (drop 4 (TriSeq)))`. Conceptually, this is:

```
(1 1 1 1 2 1 1 3 3 ...)   ; (TriSeq) (a recursive call with lazy evaluation)
(2 1 1 3 3 ...)           ; (drop 4 (TriSeq))
(1 1 1 2 1 1 3 3 ...)     ; (concat (q (1 1 1)) (drop 4 (TriSeq)))

```

We don't need the first 1 in the sequence because it's supplied by the default value for `Row`. We have to do the `drop`/`concat` routine because the first few values of the sequence are self-referential, and Appleseed will get into an infinite recursion trying to calculate them unless we specify them explicitly.
> 2 votes

# Answer
# Ruby, ~~85..~~ 72 bytes

```
*l=1
1.step{|i|p *l[-i,i]
l+=[m=l[i]||1,*(-i..-2).map{|j|l[j,2].sum},m]}

```

Try it online!

* Thanks to @Dingus for the 5 Bytes saved!

Full program, outputs the sequence indefinitely vertically.

```
*l=1       # we start with [1]
1.step{|i| # iterate i starting from 1(i is the boundary position == triangle line length)
p *l[-i,i] # puts last i elements
l+=[...]   # append new triangle line :
[m=l[i]||1   #[ m=boundary || 1 because initially not available
*            #, splat inner elements :
(-i..-2).map{  #* range of last i pos.
|j|l[j,2].sum} #* take 2 and sum
m            # right bound]
} repeat indefinitely

```
> 2 votes

# Answer
# Charcoal, 47 bytes

```
ＮθＦ³⊞υ¹≔…υ²ηＷ‹Ｌυθ«⊞η⁻§υＬη§υ⊖ＬηＵＭη⁺κ§η⊖λ≔⁺υηυ»Ｉυ

```

Try it online! Link is to verbose version of code. Outputs the first `n` terms. Explanation:

```
Ｎθ

```

Input `n`.

```
Ｆ³⊞υ¹

```

Start the flattened list with the first three terms.

```
≔…υ²η

```

This corresponds to having already generated the second row.

```
Ｗ‹Ｌυθ«

```

Repeat until sufficient terms have been collected.

```
⊞η⁻§υＬη§υ⊖Ｌη

```

Push the difference between the next two terms to the row. (Normally Pascal's Triangle just needs `0` pushed here, but this makes the row ends follow the sequence itself.)

```
ＵＭη⁺κ§η⊖λ

```

Generate the next row of the triangle.

```
≔⁺υηυ

```

Accumulate it to the flattened list.

```
»Ｉυ

```

Output the first `n` terms.
> 1 votes

# Answer
# , ~~89~~ 85 bytes

*-4 bytes thanks to @Giuseppe*

```
function(n){s=r=!!1:2
for(i in 2:n)s=c(s,r<-c(s[i],r[-1]+head(r,-1),s[i]))
c(1,s)[n]}

```

Try it online!

Function returning 1-indexed element of the sequence. Uses simple loop to create consecutive rows of the triangle.
> 1 votes

# Answer
# Raku, 60 bytes

```
my@a=flat(1,<1 1>,{@a[++$+1],|(.[1..*]Z+@$_),@a[++$+1]}...*)

```

Try it online!

This is a lazy, self-referential, infinite list, stored in the variable `@a`. The expression inside the `flat` is a sequence of rows, where `.[1..*] Z+ @$_` generates the inside sums (by addition-zipping the row with itself without its first element), and the endpoints are taken from the flattened outer array `@a`. The two lone `$`s are anonymous state variables that start off undefined/zero, so the first time the generator block is entered for the third row, the endpoints `@a[++$+1]` are `@a[2]`, when the fourth row is generated the endpoints are `@a[3]`, etc.
> 1 votes

---
Tags: code-golf, math, sequence, integer
---


title: Print Gobar Primes

text:
# Question
Title: Print Gobar Primes
Gobar primes (A347476) are numbers which give a prime number when 0's and 1's are interchanged in their binary representation.

For example, \\$10 = 1010\_2\\$, and if we flip the bits, we get \\$0101\_2 = 5\\$ which is prime. Therefore, 10 is a Gobar prime

As simple as that: print the series with any delimiter. Shortest code wins.

# Answer
# Vyxal `5`, 6 bytes

```
∞'b⌐Bæ

```

Try it Online!

this just times out, so not sure if it is valid

```
∞   # All positive integers
'       # filter by
b      # binary
⌐      # Minus from 1, (1-1=0, 1-0=1, genius)
B     # decimal
æ    # is prime?

```

# Vyxal `5`, 8 bytes

```
∞ƛb⌐Bæß,

```

Try it Online!

This one actually prints everything (remove the 5 flag to run for more time)

pseudo code

```
all positive integers
map
  binary representation
  subtract each bit from 1 aka complement
  back to decimal
  is prime
  if truthy
    print
  (implicit else)
    (implicit continue)
(implicit end map)

```
> 4 votes

# Answer
# C (gcc), <sup>~~96~~</sup> 94 bytes

```
k;i;d;p;f(n){for(i=5;n;n-=p)for(k=i++^(1<<32-__builtin_clz(i))-1,d=p=k>1;++d<k;)p=p&&k%d;--i;}

```

Try it online!

Returns the zero-based \\$n^\text{th}\\$ Gobar prime.
> 4 votes

# Answer
# JavaScript (V8), 48 bytes

```
for(i=k=j=0;;)j%k%++i?1:~i?i=++k-(j|=k):print(k)

```

Try it online!
> 3 votes

# Answer
# Ruby, ~~46~~ 45 bytes

Outputs the sequence indefinitely.

```
1.step{|n|(2..$.|=n).one?{|x|$.%n%x<1}&&p(n)}

```

Try it online!
> 3 votes

# Answer
# 05AB1E, 9 (or 8?) bytes

```
[NbTÂ‡Cp–

```

Outputs with newline delimiter.

Try it online.

If outputting as an infinite list is allowed it could be 1 byte less:

```
∞ʒbTÂ‡Cp

```

Try it online.

**Explanation:**

```
[          # Start an infinite loop:
 N         #  Push the 0-based loop-index
  b        #  Convert it to a binary string
   T       #  Push 10
    Â      #  Bifurcate it; short for Duplicate & Reverse copy
     ‡     #  Transliterate the 1s to 0s and vice versa in the binary string
      C    #  Convert it back from a binary string to an integer
       p   #  Check if this integer is a prime number
        –  #  If it is: Print the loop-index `N` with trailing newline

∞          # Push an infinite positive list
 ʒ         # Filter it by:
  bTÂ‡Cp   #  Same as above
           # (after which the resulting list is output implicitly)

```

`bTÂ‡C` could alternatively be `2в_2β` for the same byte-count in both programs: try it online.

```
  2в       #  Convert the integer to a base-2 list
    _      #  Check for each if it's equal to 0: 1 if 0; 0 otherwise
     2β    #  Convert it from a base-2 list back to an integer

```
> 2 votes

# Answer
# Jelly, 6 bytes

```
BCḄẒƲ#

```

Try it online!

Takes an input `n` from STDIN and outputs the first `n` Gobar numbers. If we have to output all Gobar numbers, the following works for 9 bytes

```
ṄBCḄẒƲ¡‘ß

```

Try it online!
> 2 votes

# Answer
# MathGolf, 10 bytes

```
òî_â┌ä¶╛p∟

```

Try it online.

**Explanation:**

```
ò        ∟  # Do while true without popping,
ò           # using the following eight characters as inner code-block:
 î          #  Push the 1-based loop-index
  _         #  Duplicate it
   â        #  Pop and convert it to a binary-list
    ┌       #  Invert each boolean
     ä      #  Convert it from a binary-list back to an integer
      ¶     #  Check if it's a prime number
       ╛    #  If it is:
        p   #   Pop and print the 1-based loop-index with trailing newline

```
> 2 votes

# Answer
# , ~~81~~ 73 bytes

*-8 bytes thanks to @Giuseppe*.

```
while(T<-T+1)(k=(p=2^(0:log2(T)))%*%!T%/%p%%2)<2|sum(!k%%1:k)>2||print(T)

```

Try it online!
> 2 votes

# Answer
# Vyxal, 7 bytes

```
λb†Bæ;ȯ

```

Try it Online!

Takes a number n and returns the first n numbers.

```
λ    ;ȯ # First n numbers where...
 b      # Binary
  †     # Vectorised logical not (Vyxal uses 1/0 for booleans)
   B    # When converted back to a number
    æ   # Is prime?

```
> 2 votes

# Answer
# Python 3, 77, 70(@ovs), 65, 64 bytes

```
*p,x,z,P=5*[1]
while[p[z^x]or print(x)]:P*=x;x+=1;p+=-~P%x,;z|=x

```

Try it online!

Old version

Old version

Old version
> 2 votes

# Answer
# JavaScript (V8), 75 bytes

Prints the sequence "forever" (i.e. until call stack overflow).

```
for(k=0;f=d=>x%--d?f(d):x>1&d<2;)f(x=++k^~-(1<<32-Math.clz32(k)))&&print(k)

```

Try it online!

Or  **~~77~~  76 bytes** without `Math.clz32()`:

```
for(k=0;f=d=>x%--d?f(d):x>1&d<2;)f(x=++k^(g=k=>k&&1|2*g(k>>1))(k))&&print(k)

```

Try it online!
> 1 votes

# Answer
# Pari/GP, 50 bytes

```
for(i=1,oo,if(isprime(2^#binary(i)-i-1),print(i)))

```

Try it online!
> 1 votes

# Answer
# Charcoal, 38 bytes

```
Ｎθ≔¹ηＷ‹ⅉθ«≦⊕η≔↨Ｅ↨η²¬κ²ζ¿∧‹¹ζ⬤…²ζ﹪ζκ⟦Ｉη

```

Try it online! Link is to verbose version of code. Outputs the first `n` Gobar primes. Explanation:

```
Ｎθ

```

Input `n`.

```
≔¹η

```

Start at `1` (arbitrary, just has to be between `0` and `3` inclusive).

```
Ｗ‹ⅉθ«

```

Repeat until `n` Gobar primes have been printed.

```
≦⊕η

```

Try the next integer.

```
≔↨Ｅ↨η²¬κ²ζ

```

Convert it to base `2`, flip the bits, then convert back.

```
¿∧‹¹ζ⬤…²ζ﹪ζκ

```

If the result is at least `2` and has no nontrivial proper factors, then...

```
⟦Ｉη

```

Print the Gobar prime on its own line.

The above algorithm appears to be O(n²) in complexity, taking 20 seconds to calculate the first 1400 Gobar primes and probably 20 minutes to calculate the first 7708. I've implemented a faster algorithm for ~~66~~ 56 bytes that can calculate the first 7708 Gobar primes in ~~20~~ seconds (although it does start to slow down after that point due to using a memory-inefficient method of generating primes):

```
Ｎθ≔²η≔υζＷ‹Ｌυθ«≔Φζ‹×κκ⊗ηε≔⁺Φ⮌…η⊗η⬤ε﹪κμζζ≦⊗η≔⁺υ⁻⊖⊗ηζυ»Ｉ…υθ

```

Try it online! Link is to verbose version of code. Outputs the first `n` Gobar primes, although it actually works by calculating the primes up to the next power of 2. Explanation:

```
Ｎθ

```

Input `n`.

```
≔²η≔υζ

```

Start with the primes up to (but not including) 2, i.e. no primes at all.

```
Ｗ‹Ｌυθ«

```

Repeat until enough Gobar primes have been obtained.

```
≔Φζ‹×κκ⊗ηε

```

Get the primes up to the square root of the next power of 2.

```
≔⁺Φ⮌…η⊗η⬤ε﹪κμζζ

```

Calculate all the primes between the current and next power of 2 by trial division by all of those primes. (Sieving them would probably be even faster.)

```
≦⊗η

```

Double the current power of 2.

```
≔⁺υ⁻⊖⊗ηζυ

```

Complement the bits in all of the primes up to the current power of 2 with respect to that number of bits e.g. primes up to 4 have three bits complemented resulting in `4, 5` while primes up to 128 would have eight bits complemented. (Note that the list of primes is in reverse order so the complements are in ascending order as desired.)

```
»Ｉ…υθ

```

Output the first `n` Gobar primes.
> 1 votes

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

```
n=1
while 1:(k:=int(bin((n^~-2**~-len(bin(n))))[3:],2))>1and all(k%m for m in range(2,k))and print(n);n+=1

```

Try it online!

Infinite output
> 0 votes

# Answer
# Ruby, ~~71~~ 70 bytes

```
require'prime'
1.step{|n|n.to_s(2).tr('01','10').to_i(2).prime?&&p(n)}

```

Try it online!

* Saved 1 thanks to @ovs

Full program, prints the sequence indefinitely on new lines.

```
1.step{|n|     # each n>0
n.to_s(2)      # convert to binary string
.tr('01','10') # swap '01'
.to_i(2)       # reconvert to int
.prime?&&p(n)  # put n if prime

```
> 0 votes

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


title: Fibonacci Encoding

text:
# Question
Title: Fibonacci Encoding
Fibonacci coding is a universal code, which can encode positive integers of any size in an unambiguous stream of bits.

To encode an integer \\$ n \\$:

* Find the largest Fibonacci number less than or equal to \\$ n \\$; subtract this number from \\$ n \\$, keeping track of the remainder
* If the number subtracted was the \\$ i \\$th Fibonacci number \\$ F(i) \\$, put a \\$ 1 \\$ at index \\$ i−2 \\$ in the code word (counting the left most digit as index \\$ 0 \\$)
* Repeat the previous steps, substituting the remainder for \\$ n \\$, until a remainder of \\$ 0 \\$ is reached
* Append a final \\$ 1 \\$

Alternately explained:

* Find the Zeckendorf representation of \\$ n \\$ (the list of unique non-consecutive Fibonacci numbers which sum to it)
* For all the Fibonacci numbers up to and including \\$ n \\$, excluding \\$ 0 \\$ and the first \\$ 1 \\$, append a bit \\$ 0 \\$ or \\$ 1 \\$ according to whether or not they appear in \\$ n \\$'s Zeckendorf representation
* Strip any trailing \\$ 0 \\$s and append a final \\$ 1 \\$

Your task is to, given a positive integer, output the bits of its Fibonacci coding.

## Test Cases

```
Input    Output
-------------------------------------------
1        11
2        011
3        0011
4        1011
11       001011
12       101011
13       0000011
14       1000011
65       0100100011
610      000000000000011
8967     00001010101010010011
8039213  0010010010100010001001001000001011

```

(if your code cannot compute this high in reasonable time, that is fine)

## Rules

* Output should be as a string or array of \\$ 1 \\$s-and-\\$ 0 \\$s or booleans (but not just any truthy or falsey value)
* You may output the bits in reverse if that is more convenient (although this behaviour must be consistent)
* You may use any sensible I/O format
* Standard loopholes are forbidden
* This is , so the shortest code in bytes wins

# Answer
# Japt, 13 bytes

```
@!X¤øB}iU
¤ÔÄ

```

Explanation:

```
@!X¤øB}iU
@     }iU // Get the U-th (input) number
 !        // which doesn't have
    øB    // "11" in its
  X¤      // binary representation

¤ÔÄ
¤         // Take that number's binary representation,
 Ô        // reverse it
  Ä       // and add one to the end.

```

Try it here.
> 20 votes

# Answer
# C (gcc), ~~51~~ 50 bytes

```
k;f(n){for(k=0;n-=!(++k&k/2););n=log2(k);k+=2<<n;}

```

Try it online!

Uses the formula from Etheryte's Japt answer.
Returns the Fibonacci code word for input \\$n\\$ in reversed binary.

### Explanation

```
k;f(n){                           // function taking an integer n > 0
       for(k=0;             ;);   // loop over values of integer k
                                  // starting at 1 (because of the bump)
               n                  // until n is zero
                -=!(       )      // subtracting 1 from n when...
                    ++            // (bump k at the start of each loop)
                      k&k/2       // ...there's no 2 consecutive 1 bits in k
                                  // k is now the nth integer without
                                  // any 2 consecutive 1 bits
       n=log2(k);                 // get the number of bits in k by
                                  // converting  its log2 to an int
       k+=2<<n;                   // add a 1 bit just above k's most
                                  // significant bit and return k
}

```
> 8 votes

# Answer
# Jelly,  ~~21~~  12 bytes

Using Etheryte's observation from their Japt answer is much terser and more efficient to boot (it may be possible in even less, let's see...)

```
1BSƝỊẠƲ#ṪB1;

```

A monadic Link accepting a positive integer that yields a list of `1`s and `0`s (in reversed order as allowed in the rules).

**Try it online!**

---

A faster 12 byter:

```
1Ḥ^:3ƲƑ#ṪB1;

```

Try it online!

### How?

```
1Ḥ^:3ƲƑ#ṪB1; - Link: positive integer, n
1      #     - set k=1 and increment to collect the first n ks for which:
      Ƒ      -   (k) is invariant under?:
     Ʋ       -     last four links as a monad, f(k):
 Ḥ           -       double (k)
  ^          -       (2k) bitwise-XOR with k -> x
    3        -       three
   :         -       (x) integer divide (3)
        Ṫ    - tail
         B   - to binary
          1  - one
           ; - (1) concatenate with (the binary list)

```

---

Original 21:

This is (a) extremely inefficient and (b) almost certainly not the right way to get the tersest code, so I~~'ll~~ was planning to come back to it after work...

```
‘ÆḞ€ḊðŒPS⁼¥Ƈ⁹Ḣ⁸iⱮðṬ;1

```

A monadic Link accepting a positive integer that yields a list of `1`s and `0`s.

Try it online!
> 6 votes

# Answer
# Haskell, 76 bytes

```
1#2
(u#v)x|x<v=["11"|x==u]|z<-u+v=map('0':)(v#z$x)++map("10"++)(z#(z+v)$x-u)

```

Try it online!

Outputs a string of `0`'s and `1`'s wrapped in a singleton list (e.g. `["001011"]`).

## How?

* `(u#v)x`: we want this function to return a list of all the possible Fibonacci encodings for `x` using only Fibonacci numbers greater or equal than `u`; we further assume that `u` and `v` are consecutive fibonacci numbers (with `u<v`). It is well known that, if such an encoding exists, than it is unique (this follows from the uniqueness of the Zeckendorff representation), so the length of the list `(u#v)x` will be at most 1. For instance, `(3#5)11==["1011"]`, since `11=3+8`.
* `|x<v=["11"|x==u]`: if `x<v` then the encoding only exists if `x==u`. If this is the case we return `["11"]`, otherwise we return the empty list.
* `|z<-u+v=`: otherwise, let `z=u+v` be the next Fibonacci number. We have two choices.
    + `map('0':)(v#z$x)`: we try to encode `x` without using `u`. In this case, the encoding will be contained in `(v#z)x`, and we prepend a `'0'` to denote the fact that we didn't take `u`.
    + `++map("10"++)(z#(z+v)$x-u)`: we try to encode `x` using `u`. In this case, `"10"` denotes that we take `u` and we don't take `v`. For this choice to be valid, we must also find an encoding of `x-u` using only Fibonacci numbers from `z` onwards (notice that `z+v` is the Fibonacci number after `z`).
> 6 votes

# Answer
# JavaScript (ES6),  ~~46~~  44 bytes

*Based on @Etheryte's insight.*

Returns a string of bits in reverse order.

```
f=(n,k)=>k&k/2||n--?f(n,-~k):1+k.toString(2)

```

Try it online!

### Commented

```
f = (             // f is a recursive function taking:
  n,              //   n = input
  k               //   k = counter, initially undefined (coerced
) =>              //       to 0 for bitwise operations)
  k & k / 2 ||    // yield a truthy value right away if there are
                  // at least 2 consecutive bits set in k
    n--           // otherwise, yield n and decrement it afterwards
  ?               // if either statement above is truthy:
    f(n, -~k)     //   do a recursive call with k + 1
  :               // else:
    1 +           //   stop and return a leading '1'
    k.toString(2) //   followed by the binary representation of k

```

---

# JavaScript (Node.js),  ~~109~~  105 bytes

*Based on the challenge description.*

Expects a BigInt. Returns a string of bits in reverse order.

```
f=(n,k=m=0n)=>n?(g=(i,x=0n,y=1n)=>i?g(~-i,z=y,x+y):y)(k)>n?f(n-z,0n,m|=1n<<k-2n):f(n,-~k):1+m.toString(2)

```

Try it online!
> 5 votes

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

Another based on Etheryte's Japt answer

```
f=lambda n,k=0:-n*f'1{k-1:b}'or f(n-(k&k//2<1),k+1)

```

**Try it online!**
> 4 votes

# Answer
# Stax, 16 bytes

```
âî}g♥▼«zΩ╥;QbB]╔

```

Run and debug it

Based on Etheryte's observation, which shaved a off a ton of bytes. Check out their answer!

## Explanation

```
Z{|B.11#!}{ge|B'1s+
Z                   push 0 under the input(counter)
           ge       generator: find the first n elements, return the last
          {         empty block: get the next element by incrementing
 {       }          filter:
  |B                base2 string
    .11#!           has 0 occurrences of "11"?
               '1s+ prepend a 1 to it(r'1+ also works for valid output)

```

# Stax, 29 bytes

```
é½Æ½┼≥╦◘½}○└╩►à«ôæ→¢ûU«½*≈ø»▀

```

Run and debug it

Pretty big.
> 3 votes

# Answer
# Scala, 69 bytes

Based on Etheryte's amazing answer

```
"1"+Stream.from(0).map(_.toBinaryString).filter(!_.contains("11"))(_)

```

Try it online!

Outputs a String (reversed)

## Original answer, 123 bytes

```
n=>(f.takeWhile(n>=_):\(n,1::Nil)){case(x,n->c)=>if(x>n)(n,0::c)else(n-x,1::c)}._2
def f:Stream[Int]=1#::f.scanLeft(2)(_+_)

```

Try it online!
> 3 votes

# Answer
# 05AB1E, 14 bytes

```
∞ʒb11å>}s<èb1ì

```

Try it online!

```
∞ʒb11å>}s<èb1ì  # full program
         <è     # push the...
        s       # implicit input...
         <è     # -th...
∞               # natural number...
 ʒ     }        # which...
      >         # does not...
     å          # contain...
   11           # literal...
  b             # in binary...
           b    # converted to binary...
            1   # with literal...
             ì  # prepended
                # implicit output

```
> 3 votes

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

```
n=>(g=p=>n<p||2*g(p+q,q=p)+(n>(n%=p)))(q=1)

```

Try it online!

It returns an integer whose binary form is reversed Fibonacci Encoding.

```
// I have a code for base 2 convention
n=>(g=p=>n<p  2*g(       )+(n>(n%=p)))(   )
// I have a code for Fibonacci sequence
n=>(g=p=>       g(p+q,q=p)           )(q=1)
// Boom, Fibonacci base convention
n=>(g=p=>n<p||2*g(p+q,q=p)+(n>(n%=p)))(q=1)

```
> 3 votes

# Answer
# jq (74 bytes)

Since shortness is the goal ...

```
def f:def i:.,(i|[0]+.,[1]+.);nth(.-1;[1]|i|select(index([1,1])|not))+[1];

```

Example:

```
65|f #=> [0,1,0,0,1,0,0,0,1,1]

```

Try it online
> 3 votes

# Answer
# Japt, 12 bytes

Based off Etheryte's solution, posted with permission.

```
_øB ªU´}f¤ÔÄ

```

Try it
> 3 votes

# Answer
# Wolfram Language (Mathematica), 127 bytes

```
(f@n_:=(k=1;While[(F=Fibonacci)[++k]<=n];k-1);s=Table[0,f[t=#]];(s[[#]]=1)&/@(f/@NestWhileList[#-F@f@#&,t,#>0&]);RotateLeft@s)&

```

Try it online!
> 2 votes

# Answer
# Haskell (GHC), ~~118~~ 104 bytes

```
x@(_:v)=1:scanl(+)1x
f n=snd(foldr(\v(x,l)->if v<=x then(x-v,1:l)else(x,0:l))(n,[])$fst$span(<=n)v)++[1]

```

Try it online!

## Original:

Outputs a list of reversed bits.

```
import Data.List
x@(_:v)=1:scanl(+)1x
f n=1:snd(mapAccumL(\a b->if b<=a then(a-b,1)else(a,0))n$reverse$fst$span(<=n)v)

```

Try it online!
> 2 votes

# Answer
# Red, ~~135~~ 124 bytes

```
func[n][i: k: 0 until[i: i + 1 unless find do
b:[enbase/base to#{01}i 2]"11"[k: k + 1]n = k]reverse
rejoin["1"find do b"1"]]

```

Try it online!

Uses @Etheryte's method

### As an excercise - the step by step method:

## Red, 153 bytes

```
func[n][c: charset 1 until[k: 0 a: 0 b: 1 until[k: k + 1
t: a a: b b: t + b b > n]c/(k - 2): 1 0 = n: n - a]replace
enbase/base to#{01}c 2[any"0"end]"1"]

```

Try it online!

More readable:

```
f: func[n][
    c: charset 1
    until [
        k: 0
        set [a b] [0 1]
        until [
            k: k + 1
            set [a b] reduce [b a + b]
            b > n
        ]
        c/(k - 2): 1
        0 = n: n - a
    ]
    replace enbase/base to binary! c 2 [any "0" end] "1"
]

```

`charset` is short for `make bitset!`
> 2 votes

# Answer
# Husk, ~~14~~ 12 bytes

*Edit: -2 bytes thanks to Leo*

```
↔:1!fo¬V&mḋN

```

Try it online!

Based on Etheryte's approach: upvote that!
> 2 votes

# Answer
# Retina 0.8.2, 63 bytes

```
.+
$*
(\G1|(?>\2?)(\1))*1
$#1$*01¶
+`^(.*).(.*¶)(\1.)¶
$3$2
¶
1

```

Try it online! Link includes test cases. Explanation:

```
.+
$*

```

Convert to unary.

```
(\G1|(?>\2?)(\1))*1

```

Use a tweaked version of @MartinEnder's answer to Am I a Fibonacci Number? to match Fibonacci numbers that sum to the input.

```
$#1$*01¶

```

For each match, generate the bit in the appropriate column.

```
+`^(.*).(.*¶)(\1.)¶
$3$2

```

Fold all of the bits together.

```
¶
1

```

Replace the final delimiter with a final 1 bit.
> 1 votes

# Answer
# Charcoal, 38 bytes

```
ＮθＦ²⊞υ⊕ιＷ‹⌈υθ⊞υΣ…⮌υ²←1ＦΦ⮌υκ«←Ｉ¬›ιθ≧﹪ιθ

```

Try it online! Link is to verbose version of code. Explanation: Outputs digits in reverse order, but this is the least of Charcoal's problems because it can simply print them backwards.

```
Ｎθ

```

Input `n`.

```
Ｆ²⊞υ⊕ι

```

Start with `1` and `2` from the Fibonacci sequence.

```
Ｗ‹⌈υθ⊞υΣ…⮌υ²

```

Keep pushing terms until one exceeds `n`.

```
←1

```

Print the final `1`.

```
ＦΦ⮌υκ«

```

Loop through all the terms except the last in reverse order.

```
←Ｉ¬›ιθ

```

Print `0` or `1` depending on whether this term is larger than `n`.

```
≧﹪ιθ

```

Subtract the term from `n` if it is smaller.
> 1 votes

# Answer
# Mini-Flak (BrainHack), 104 bytes

```
([{}]((()))){({}(())({{}[()](({}({}))){(()[{}]){(({}{}[()]))}}{}}{}(())){[({})]({}[()](()[()]))}{}{})}{}

```

Try it online!

Starts at `11` and iteratively computes the encoding of the next number `n-1` times.

```
# Create 11 while computing 1-n.
([{}]((())))

# Repeat
{

  # Add 1 to counter (going up to zero) and allow loop to start
  ({}(())

    # Eventually push number of iterations to reach 00 or 11
    (

      {

        # Remove 1 from stack
        {}[()]

        # Compute sum of two digits, keeping second, and push twice
        (({}({})))

        # If not 00:
        {

          # Subtract value from 1; this makes iteration evaluate to 1
          (()[{}])

          # If top of stack still isn't zero (i.e., digits were 11):
          {

            # Push two zeros: one to exit loop and the other to exit conditional
            (({}{}[()]))

        }}{}

      # Repeat until 00 or 11 found
      }{}

      # Push 1 at position
      (())

    # Push number of leading zeroes to use, plus one
    )

    # That many times:
    {

      # Compute -k: this will make each iteration evaluate to -1
      [({})]

      # Subtract 1 from k...
      ({}[()]

        # while pushing 0 below it
        (()[()])

      )

    }{}

    # Since the push evaluates to a number of iterations, and
    # those iterations all evaluate to -1, this main part of the main
    # loop evaluates to zero.

    # Remove extraneous zero: this is shorter than subtracting 1 earlier
    {}

# Repeat until counter reaches zero, and pop zero
)}{}

```
> 1 votes

# Answer
# Vyxal, 14 bytes

```
λbṅ11c¬;ȯtbṘ1J

```

Try it Online!

Port of Ethertyte's answer.

```
λ      ;ȯt     # Nth integer where...
 bṅ            # Binary
   11c¬        # Doesn't contain 11
          bṘ   # Get the binary of that, reversed
            1J # Append a 1

```
> 1 votes

# Answer
# Wolfram Language (Mathematica), 50 bytes

Based on tsh's JavaScript answer.

-4 bytes thanks to @att.

```
n1~If[#>n,k=n;1,2#0[+##,#]+If[k<#,0,k-=#;1]]&~1

```

Try it online!
> 1 votes

---
Tags: code-golf, integer, binary, fibonacci, coding-theory
---


# Question
Title: Find the smallest solution for this simple equation
# Input

4 integers w, x, y, z from the range -999 to 999 inclusive where none of the values is 0.

# Output

4 integers a, b, c, d so that a*w + b*x + c*y + d*z == 0 where none of the values is 0.

# Restrictions

Your output should be the solution with the smallest sum of absolute values possible. That is the smallest value of \\$|a|+|b|+|c|+|d|\\$. If there is more than one solution with the same sum of absolute values you can choose any one of them arbitrarily.

# Examples

```
Input: 78 -75 24 33
Output: b = -1, d = 1, a = -2, c = 2

Input: 84 62 -52 -52
Output: a = -1, d = -1, b = -2, c = -3

Input: 26 45 -86 -4
Output: a = -3, b = -2, c = -2, d = 1

Input: 894 231 728 -106
Output: a = 3, b = -8, c = -1, d = 1

Input: -170 962 863 -803
Output: a = -5, d = 8, c = 2, b = 4

Added thanks to @Arnauld
Input: 3 14 62 74
Output: -2, 4, -2, 1

```

# Unassessed bonus

Not in the challenge but does your code also work on this?

```
Input:  9923 -9187 9011 -9973

```

# Answer
> 4 votes
# Python 3 (PyPy), ~~139~~ 137 bytes

Assumes no boundary and runs fine for the additional test case.

```
f=lambda x,b=4,t=0:[[s*~i]+v for i in range(b)for s in(1,-1)for v in f(x[1:],b-i,t+s*~i*x[0])][:1]or x[3:]and f(x,b+1)if x else[x]*(t==0)

```

Try it online!

# Answer
> 3 votes
# , ~~136~~ ~~118~~ ~~110~~ ~~104~~ 102 bytes

```
function(v,r=combn(rep(c(1:4e3,-4e3:-1),4),4),s=r[,order(colSums(abs(r)))])s[,!apply(s,2,`%*%`,v)][,1]

```

Try it online!

Searches solutions in space bounded by sum of absolute values of the inputs (as input is bounded, we simply take `4e3`). This however makes the code run forever for the test cases.
This bound is sufficient, as `a,b,c,d=-x,w,-z,y` is a solution (courtesy of @loopy walt).

Here is a version (with lower fixed upper bound) that terminates in reasonable time: Try it online!.

### Explanation:

```
function(v,          # take the input vector
m=4e3,               # calculate the upper bound for solutions
r=combn(             # combine potential solutions into one matrix (potentially with repetitions)
 rep(c(1:m,-m:-1),4) # get 4 times the range from -m to m excluding 0
 ,4)                 # combinations of length 4
,s=r[,order(         # sort the potential solutions
  colSums(abs(r))    # by sums of absolute values
  )]
)
s[,                  # take from that array
 !apply(s,2,`%*%`,v) # rows which dot-multiplied by input are zero
][,1]                # and the first one from that

```

# Answer
> 3 votes
# JavaScript, ~~221~~ 205 bytes

```
(w,x,y,z)=>(g=n=>[...g+""].flatMap((_,k)=>(i=(x,a=[1,1,1,1])=>x?a.flatMap((_,z)=>((b=[...a])[z]++,i(x-1,b))):[a])(n).map(a=>a.map((r,s)=>(k>>s-1&2)*r-r))).find(c=>w*c[0]+x*c[1]+y*c[2]==-z*c[3])||g(n+1))(0)

```

Try it online!

**How it works:**

I count up from `0`, and for each number, I increment all possible combinations of items in an array which is initially `[1, 1, 1, 1]`. I then find all 16 signs of this array. I then just have to check for the one that is correct. That guarantees the minimum absolute value.

This is actually really fast for most of the test cases, with the speed being determined by the sum of the absolute values of the correct output rather than by the size of the input. It runs near-instantly for most of the test cases, takes about 20s with the `894` one, and times out for the `-170` one.

I think I found the world's most cursed golf. Instead of using `[...Array(16)]` to get an array (the indices of which I'd use to find the various signs), it seems `[...g+""]` works...by casting `g` (a function) into a string and splitting it into characters. Since there's modulo stuff going on with the indices, going over 16 doesn't matter since it just results in some duplicate arrays in the possible outputs that are checked.

# Answer
> 3 votes
# Wolfram Language (Mathematica), ~~52~~ 51 bytes

```
ArgMin[{Tr[d=Abs@v],v.#==0<d},v={a,b,c,},Integers]&

```

Try it online!

Input the list of numbers.

```

ArgMin[                      ,                   ]  find:
                              v={a,b,c,},Integers     integers {a, b, c, n}
       {           ,        }                         such that:
        Tr[d=Abs@v]                                     |a|+|b|+|c|+|n| is minimal,
                    v.#==0<d                            satisfying the output conditions

```

# Answer
> 2 votes
# 05AB1E, 19 bytes

```
₄4*LD(«4ãʒ*O_}ΣÄO}н

```

Try it online!

Finishes in unreasonable time. Uses \[-4000, 4000\] as the bound. The code is verified with changing `₄4*` with `3` for the first test case.

```
₄4*                     Push 4000  (1000*4)
   LD(«                 Make range of [-4000, 4000] (joining two seperate lists)
       4ã               All 4-combos (Cartesian power of 4)
         ʒ*O_}          Filter who dot producted with input cast 0
              ΣÄO}н     Sort by sum of abs and head (No min by builtin)

```

# Answer
> 2 votes
# Jelly, 17 bytes

```
³²R;N$ṗ4ḋÐḟµAS$ÞḢ

```

Try it online! (Replaced 100 with 3 to actually have this finish in finite time)

```
³²                 -- 100² = 10000
  R                -- range from 1 to 10000
     $             -- apply the two-atom function to this range
   ;N              --   append the negative
      ṗ4           -- 4th cartesian power
        ḋÐḟ        -- discard all values which have a non-zero dot product with the input
            AS$Þ   -- sort the remaining 4-tuples by the sum of the absolute values
                Ḣ  -- get the first value

```

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

Expects an array of 4 integers.

```
f=(A,n)=>(g=(a,s=n,q=n=>--n?g([...a,n],s-n)||q(n):0)=>a[3]?!s&&(h=i=>a.map((v,j)=>t+=A[j]*(b[j]=i>>j&1?v:-v),b=[t=0])|t?i--&&h(i):b)(15):q(n))([])||f(A,-~n)

```

Try it online!

### Commented

```
f = (A, n) => (               // A[] = input / n = sum of absolute values
  g = (                       // g is a recursive function taking:
    a,                        //   a[] = partition of n in 4 integers
    s = n,                    //   s = n - sum of partition
    q = n =>                  //   q is another recursive function which
      --n ?                   //   works together with g to build the
        g([...a, n], s - n)   //   partition
        || q(n)               //   we stop as soon as a solution is found
      :                       //
        0                     //
  ) =>                        //
  a[3] ?                      // if the partition is complete:
    !s && (                   //   abort if s is not 0; otherwise:
      h = i =>                //     h is yet another recursive function:
        a.map((v, j) =>       //       for each value v at position j in a[]:
          t += A[j] * (       //         add to t: A[j] multiplied by
            b[j] =            //           b[j] which is
              i >> j & 1 ? v  //           either v or -v
                         : -v //           depending on the j-th bit of i
          ),                  //
          b = [t = 0]         //         start with t = 0 and b = [ 0 ]
        ) | t ?               //       end of map(); if t is not 0:
          i-- && h(i)         //         try again with i - 1
        :                     //       else:
          b                   //         success: return b[]
    )(15)                     //     initial call to h with i = 15
  :                           // else:
    q(n)                      //   invoke q to get the next partition term
)([])                         // initial call to g with a = []
|| f(A, -~n)                  // if failed, try again with n + 1

```

# Answer
> 1 votes
# JavaScript (Node.js), 115 bytes

```
f=([h,...t],p=r=[],s=0,m=0,i)=>h?eval("for(i=-4e3;++i<4e3;)i&&f(t,[...p,i],i>0?s+i:s-i,m+i*h)"):m|s>r.s?r.p:r={p,s}

```

Try it online!

It works in theory. The tio link replaced `4e3` by `1e1` so it won't time out. It just need \\$2.56×10^{10}\\$ times current time usage to run. (So don't try it at home.) But as we are targeted to code-golf, why not make it a bit slower as long as it could be shorter.

```
f=(
[h,...t], // input array
p=r=[], // `p` is array of \$[a, b, c, d]\$
        // `r` is an object `{ p: number[], s: number }`
        // `r.p` is the best answer found, `r.s` is sum of abs of `r.p`
s=0, // sum of abs of `p`
m=0, // dot product of `p` and input vector
i // loop variable used in the function body
)=>
h?eval(`
for(i=-4e3;++i<4e3;)i&& // loop from -4000 to +4000 exclusive 0
f(t,[...p,i],i>0?s+i:s-i,m+i*h) // apply i
`):
m|s>r.s?
r.p: // output the best answer we ever found
r={p,s} // if dot product is 0 and current abs sum is less than prev one
        // we update the best answer we ever found

```

# Answer
> 1 votes
# Python 3.8, ~~180~~ 150 bytes

-30 bytes thanks to ovs.

```
import itertools as t;lambda*x,q=4000:min([s for s in t.product(*[range(-q,q)]*4)if sum(map(int.__mul__,x,s))==0<all(s)],key=lambda p:sum(map(abs,p)))

```

Try it online!

~~I am fairly certain there are some bytes to be shaved off. Here are some clever tricks that are close to working, but don't:~~

~~You can define the lambda function to be `lambda q=8,*x`, but there isn't a builtin prod function similar to sum that would allow us to take the product of the zip of `(a,b,c,d)` and `x`. You could try using `math.prod` perhaps.<br>~~

~~You can try to use Python 3.8's walrus operator inside the list comprehension to avoid having to use `(a,b,c,d)` everywhere like this: `min([s:=(a,b,c,d) for (a,b,c,d) in ... and all(map(bool, s))`, but unfortunately this gives a `NameError` while inside a lambda (see PEP 572).~~

# Answer
> 1 votes
# Wolfram Language (Mathematica), ~~83~~ 84 bytes

```
MinimalBy[{a,b,c,d}/.Solve[a#+b#2+c#3+d#4==0<Abs@{a,b,c,d}<7!,Integers],Total@*Abs]&

```

How it works:

`Solve[eqn, restrictions]` solves the given equation, with the restrictions that `Abs@{a,b,c,d}<7!`, and that the solutions are all integers.

`{a,b,c,d}/.` removes the `a->`, `b->`, etc. from the solution set, leaving only the numbers

`MinimalBy....Total@*Abs` takes the solution set, and finds the solutions whose values are the smallest according to the criterion `Total@*Abs`, which was specified by the OP.

I've run it with an upper bound of `Abs@{a,b,c,d}<20`, which is sufficient to answer all test cases plus the bonus. That's the bound I've used on Try It Online!, to avoid a timeout.

However, for codegolf purposes, I've changed the upper bound to 7! (=5040), which adds a byte, and is sufficient to exceed the 4000 upper bound others have specified. Unfortunately, this exceeds the memory capacity of my machine, and thus I can't actually run the code with this bound.

Try It online!

# Answer
> 0 votes
# Charcoal, 62 bytes

```
≔³ηＷ¬ⅉ«≔⁻…±ηη⟦⁰⟧ζ≦⊕ηＦζＦζＦζ«≔⟦κλμ⟧ε¿‹Σ↔εη«⊞ε⁻ηΣ↔ε¿¬ΣＥε×ν§θξ«⎚Ｉε

```

Try it online! Link is to verbose version of code. Not terribly efficient. Takes input as an array. Only outputs a solution with positive `d` (trivially the signs of `a`, `b`, `c` and `d` can always be flipped simultaneously). Explanation:

```
≔³η

```

Start with a sum of absolute values of `3` (which is impossible, but this gets incremented at the start of the loop).

```
Ｗ¬ⅉ«

```

Repeat until something has been printed.

```
≔⁻…±ηη⟦⁰⟧ζ

```

Create a range that more than suffices for the integers to test, but delete `0` from it.

```
≦⊕η

```

Increment the desired absolute sum.

```
ＦζＦζＦζ«

```

Loop `a`, `b` and `c` over the range.

```
≔⟦κλμ⟧ε

```

Make them into an array.

```
¿‹Σ↔εη

```

If the absolute sum of the array is less than the desired absolute sum, then:

```
⊞ε⁻ηΣ↔ε

```

Add positive `d` to give the desired absolute sum.

```
¿¬ΣＥε×ν§θξ«⎚Ｉε

```

If this list is a solution then clear any previous solution of the same sum and print it.

# Answer
> 0 votes
# MathGolf, 20 bytes

```
◙╤ç■■m─gÆêm*Σ┌áÅ±Σ├Þ

```

Unfortunately 'minimum by filter' isn't implemented yet despite being mentioned in the docs, otherwise the `áÅ±Σ├Þ` could have been `╓Å±Σ` for -2 bytes.

Try it online (with `10` instead of `4096` as range).

**Explanation:**

```
◙                    # Push 4096
 ╤                   # Pop and push a list in the range [-4096,4096]
  ç                  # Remove the 0 with a falsey filter
   ■                 # Take the cartesian product with itself to create pairs
    ■                # Do it again to create pairs of pairs
     m               # Map over each pair of pairs
      ─              #  Flatten it to a single quadruple-list
       g             # Filter this list of quadruplets by,
        Æ            # using the following five characters as inner code-block:
         ê           #  Push the inputs as integer-list
          m*         #  Multiply the values at the same positions in the two lists
            Σ        #  Sum it
             ┌       #  Check that it's equal to 0
              á      # Sort the remaining quadruplets by,
               Å     # using two characters as inner code-block:
                ±    #  Take the absolute value on each
                 Σ   #  And sum them together
                  ├  # After the sort-by, pop the first item from the list
                   Þ # Discard the list itself, only keeping this first item
                     # (after which the entire stack is output implicitly as result)

```

# Answer
> 0 votes
# Ruby, 104 bytes

```
f=->a,z=4{r=[*-z..z]-[0];r.product(r,r,r).find{|w|z==w.sum(&:abs)&&w.zip(a).sum{|x,y|x*y}==0}||f[a,z+1]}

```

Try it online!

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