# Question
Title: Counting King's Hamiltonian Paths through 3-by-N grid
## Background

A Hamiltonian path is a path on a graph that steps through its vertices exactly once. On a grid, this means stepping through every cell exactly once.

On a square grid, a Chess King can move to a horizontally, vertically, or diagonally adjacent cell in one step.

## Challenge

Count the number of Hamiltonian paths using Chess King's moves through a square grid of 3 rows and N columns (denoted `X` below), starting at the left side of the entire grid (denoted `S` below) and ending at the right side (denoted `E` below):

```
  <------N------>
  X X X ... X X X
S X X X ... X X X E
  X X X ... X X X

```

In other words, count all paths from `S` to `E` that passes through every `X` exactly once using only King's movements.

Standard rules apply. The shortest code in bytes wins. Kudos if you can solve this with short code in a way other than brute-forcing all possible paths.

## Test cases

Generated using this APL code (equivalent Python 3 + Numpy) which I created by finding 15 possible states of the rightmost column and deriving a 15-by-15 transition matrix (figures up to `N=3` are crosschecked with a pure brute-force Python).

```
N  -> Answer
0  -> 1
1  -> 2
2  -> 28
3  -> 154
4  -> 1206
5  -> 8364
6  -> 60614
7  -> 432636
8  -> 3104484
9  -> 22235310
10 -> 159360540

```

Thanks to @mypronounismonicareinstate and @ChristianSievers for confirming the test cases in the sandbox.

# Answer
# Wolfram Language (Mathematica), ~~76~~ 72 bytes

```
LinearRecurrence[{6,12,-27,2,30,4,-6},{0,0,1,2,3,29,155}-6/5,{#+4}]+1/5&

```

Try it online!

*The non-homogeneous linear recurrence equation is so much shorter to express that it saves a few bytes to modify the code to handle non-homogeneous linear recurrence.*

More info: In this case, it cannot be represented as a polynomial. I tried to put the recurrence into `RSolve`, but it takes a long time to figure out the exact symbolic form (I terminate it before it completes), and I'm pretty sure that the required coefficients are irrational (approximate numerical formula can be obtained).

Returns a singleton list containing the result.
> 8 votes

# Answer
# Python 2, ~~136~~ 129 bytes

```
f=lambda n,c=0,p=1:p==3*n+4and c+6>>3*n+3or sum(f(n,c|1<<p,p+d-4)for d in range(9)if~47&1<<p+3and(p%3*3+d%3)%8and~c&(-p>~n*3)<<p)

```

Try it online!

*-5 bytes thanks to @ovs*

Performs a depth-first search starting at S and ending at E. The start position is encoded as `p=1`, and increase down and to the right, so the top row for n=4 is `0,3,6,9` and the bottom row is `5,8,11,14`.

```
f=lambda n,c=0,p=1:(
    # if at final position:
    p==3*n+4
        and c+6>>3*n+3 # return 1 if all cells passed through else 0
    or
    # else return sum of:
     sum(
        f(n,c|1<<p,p+d-4)  # ways from that point
        for d in range(9) # for all 9 points within distance 1
        if~47&1<<p+3 # except if off to the left

        and(p%3*3+d%3)%8 # or that would be walking off top or bottom
        # (-p>~n*3) # or off to the right
        # (if this evaluates False, then the next condition is ~c&0<<p, which always gives falsey 0;
        #  if this evaluates True, then the next condition is ~c&1<<p, which tests if location already visited)
        and~c&(-p>~n*3)<<p
    )
)

```
> 4 votes

# Answer
# Python 3, 104 bytes

```
f=lambda n,a=[154,28,2,1,0,-1,-1]:n and f(n-1,[sum(map(int.__mul__,a,(6,12,-27,2,30,4,-6)))-4]+a)or a[3]

```

Try it online!

Unlike Mathematica, Python doesn't have a built-in for linear recurrence equations, so calculating a homogeneous recurrence equation takes approximately the same number of bytes as a non-homogeneous one.

Alternative solution.
> 4 votes

# Answer
# 05AB1E, 26 bytes

```
_i1ëL3LâœʒθнQyннyüα2‹PPP}g

```

Brute-force approach, so it's pretty slow. Also, 4 bytes are wasted on edge-case `n=0`.

Try it online or verify the \\$\[0,1,2\]\\$ test cases (times out for \\$n\geq3\\$).

**Explanation:**

In general:

1. Get all possible coordinates based on the input \\$n\\$
2. Get all permutations of these coordinates
3. Filter this list of permutations and only keep those that satisfy:
    * The first coordinate in this permutation is in the first column
    * The last coordinate in this permutation is in the last column
    * The difference between each overlapping pair of coordinates in this permutation is 1 step (in either a horizontal, vertical, or (anti-)diagonal direction)
4. Get the amount of valid permutations left to get the result
5. (Fix edge case \\$n=0\\$.)

```
_i       # If the (implicit) input-integer is 0:
  1      #  Push 1 (which is implicitly printed as result)
 ë       # Else:
  L      #  Push a list in the range [1, (implicit) input]
   3L    #  Push list [1,2,3]
     â   #  Take the cartesian product of the lists to get all (1-based) coordinates
      œ  #  Get all permutations of these coordinates
ʒ        #  Filter the list of permutations by:
  н      #   Get the x-coordinate
 θ       #   of the last coordinate in this permutation
   Q     #   And check if it's equal to the (implicit) input-integer
 y н     #   Also get the x-coordinate
  н      #   of the first coordinate in this permutation
 yü      #   For each overlapping pair of coordinates:
   α     #    Get the absolute difference between the two: [|x1-x2|,|y1-y2|]
    2‹   #   Check for each difference in each pair if it's 0 or 1: [|x1-x2|<2,|y1-y2|<2]
      P  #   Check if both values within each pair are truthy: (|x1-x2|<2)*(|y1-y2|<2)
       P #   Check if all checks for each overlapping pair are truthy
 P       #   Get the product of all three checks (note: only 1 is truthy in 05AB1E)
}g       #  After the filter: get the amount of valid permutations by taking the length
         #  (which is output implicitly as result)

```
> 3 votes

# Answer
# Brachylog, 40 bytes

Bruteforce for now. Times out on TIO for test cases \> 2, but at least 3 was verified locally.

```
0+₁|{;3⟦₁ᵐẋp{hh1&b;?zk{\-ᵐȧᵐ≤ᵛ1}ᵐ&th}?}ᶜ

```

Try it online!

### How it works

```
0+₁|

```

If input is zero, return 1. Otherwise …

```
{…}ᶜ

```

Count all …

```
;3⟦₁ᵐẋ

```

coordinates `[[1,1],[1,1],[1,2],…,[N,1],[N,2],[N,3]]`

```
p{ … }

```

permutations that fulfill:

```
hh1

```

The first point's x coordinate must be 1

```
&b;?zk

```

Zip the permutation with itself shifted by one, drop the wrapped around. `[[[1,1],[2,2]], …]`

```
{\-ᵐȧᵐ≤ᵛ1}ᵐ

```

Check king moves: For each of the pairs, `[[1,1],[2,2]]` transpose `[[1,2],[1,2]]` subtract `[-1,-1]` absolute values `[1,1]` all of them must be less or equal than 1.

```
&th}?

```

Also, the last point's x coordinate must unify with the input.
> 2 votes

# Answer
# Charcoal, 128 bytes

```
Ｎθ⊞υＥ⁺³θ⁰⊞υＥ⁺³θ∧›ι¹‹ι⁺²θ⊞υＥ⁺³θ›ι¹⊞υ§υ¹⊞υ§υ⁰≔⟦Ｅ³∨ιυ⟧υ≔⁰ηＦυＦ…·⊖§ι²⊕§ι²Ｆ…·⊖§ι¹⊕§ι¹Ｆ§§§ι⁰κλ¿‹λ⁺²θ⊞υ⟦Ｅ§ι⁰Ｅν∧∨⁻ξκ⁻ρλπλκ⟧≧⁺¬⊖ΣＥ§ι⁰ΣνηＩη

```

Try it online! Link is to verbose version of code. Brute force version, because I haven't figured out a recurrence relation, assuming one is even possible. Explanation:

```
Ｎθ

```

Input `n`.

```
⊞υＥ⁺³θ⁰⊞υＥ⁺³θ∧›ι¹‹ι⁺²θ⊞υＥ⁺³θ›ι¹⊞υ§υ¹⊞υ§υ⁰

```

Build up an array of unvisited squares, but with a border of `0`s so the starting square is actually `[2, 1]` (and is visited).

```
≔⟦Ｅ³∨ιυ⟧υ

```

Start a breadth-first search with this array and the starting square just mentioned.

```
≔⁰η

```

Start with zero successful paths.

```
ＦυＦ…·⊖§ι²⊕§ι²Ｆ…·⊖§ι¹⊕§ι¹Ｆ§§§ι⁰κλ

```

For each position, loop through all of the unvisited squares of the `3×3` square that has the current square at its centre.

```
¿‹λ⁺²θ

```

If we have not reached the finish, then ...

```
⊞υ⟦Ｅ§ι⁰Ｅν∧∨⁻ξκ⁻ρλπλκ⟧

```

... push the grid with this square visited plus the new position to the list of positions to search...

```
≧⁺¬⊖ΣＥ§ι⁰Σνη

```

... otherwise if this is the last unvisited square then increment the number of successful paths.

```
Ｉη

```

Print the final count of successful paths.
> 2 votes

# Answer
# Jelly, ~~28~~ ~~25~~ 27 bytes

```
Rp3Ḷ¤Æị€;ıŒ!ISḞ=ʋƇ³IA<2ẠƲƇL

```

or

```
Ḷp3R¤Æị€Œ!ISḞ=ʋƇ’IA<2ẠƲƇL+¬

```

Try it online!

Not the most exciting answer: brute-forces all possible paths and times out on TIO for `n>2`.

*+3 bytes for fixing `n=0` case.*

~~I have temporarily paused golfing since the bytecount reached `f(2)=28`.~~

```
Rp3Ḷ¤Æị€;ıŒ!ISḞ=ʋƇ³IA<2ẠƲƇL
Rp3Ḷ¤Æị€                       # Generate all points on a lattice from 1+0j to n+2j
        ;ı                     # Append 0+1j (start position)
          Œ!                   # Take all permutations
                ʋƇ             # Filter for
            ISḞ=  ³              # real(last-first)=n
                        ƲƇ     # Filter for
                   IA<2Ạ         # All moves have magnitude less than 2
                          L    # Length

```
> 1 votes

# Answer
# , ~~191~~ 168 bytes

*Edit: -23 bytes by switching to linear instead of matrix coordinates*

```
f=function(p=-1,m=rep(0,3*n),n){if(p>0)m[p]=1
`if`(all(m),p/3>n-1,`if`(!sum(q<-!m[a<-(a=p+(-4:4)[!!c((p+2)%%3,1,(p+3)%%3)])[a>0&a<=3*n]]),0,sum(sapply(a[q],f,m,n))))}

```

Try it online!

Recursively tries all paths & counts-up those that end in last column & visit all positions.

Commented version:

```
paths=f=function(p=c(2,0),m=matrix(0,3,n),n){       # start at position 'S'; fill matrix with zeros
    m[t(p)]=1                                       # set visited positions to 1
    if(all(m)){                                     # visited all positions?
        if(p[2]==n){                                # if we're in the last column...
            return(1)}                              # ...then this is a valid path
        else{return(0)}                             # otherwise it isn't.
    } else {                                        # if there are still some positions to visit:
        a=p+rbind(1:3,rep(1:3,e=3))-2               # a = all possible king moves...
        a<-t(a[,!colSums(a<1|a>dim(m))])            # ...limited to bounds of matrix
        q=!m[a]                                     # q = moves to unvisited positions
        if(!sum(q)){return(0)}                      # if we can't move, it's not a valid path
        else{                                       # if we can move...
            return(sum(sapply(split(a,seq(q))[q],f,m,n)))
                                                    # return the sum of all valid paths from here
                                                    # by recursively calling self with each new position
        }
    }
}

```
> 1 votes

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

This is using @user202729's linear recurrence.

```
f=n=>([5,5,6,7,8,34,160][n+3]||[6,12,-27,p=2,30,4,-6].map(c=>p+=c*f(--n))&&p)-6

```

Try it online!
> 1 votes

# Answer
# Husk, 22 bytes

```
#¹mo→→fΛδΛ≈fȯε→←P¤×eḣ3

```

Try it online!

It's just brute force, so not that fast, though TIO can handle \\$n = 3\\$. Husk's default return values line up nicely so that I don't waste any bytes special casing \\$n = 0\\$.

# Explanation

```
P¤×eḣ3  Generate all permutations of vertices.
 ¤   3  Apply to both 3 and n:
    ḣ   Range from 1.
  ×e    Cartesian product.
P       Permutations.
        For n=0 the range and the product are empty,
        and P gives [[]].
        Note that the second coordinates run from 1 to n.

f(ε→←)  Check initial vertex.
f(   )  Filter by condition:
    ←     First element.
   →      Last element of that
  ε       has absolute value at most 1.
        For n=0 the condition is checked for [],
        which is a list of lists of numbers.
        ← defaults to [], an empty list of numbers in this case.
        → defaults to 0 on it, and ε reports true.

fΛδΛ≈  Check adjacent vertices.
f      Filter by condition:
 Λ       For all adjacent pairs,
  δΛ     in both coordinates
    ≈    the values differ by at most 1.
       For the empty list, Λ is always true regardless of the condition.

#¹mo→→  Check last vertex.
  mo    Map
    →→  Last element of last element.
#¹      Count occurrences of n.
        The defaults work as with the initial vertex.

```
> 1 votes

# Answer
# +gtools, 147 bytes

```
n=scan();m=3*n;`if`(!n,1,sum(apply((p=permutations(m,m,complex(m,rep(1:n,e=3),1:3)))[Re(p[,1])<2&Re(p[,m])==n,],1,function(x)all(abs(diff(x))<2))))

```

Try it online!

Tests all permutations of coordinates as complex numbers, and counts those that start with Re=1, end with Re=n, and for which all steps have an absolute value less than 2.

I felt that I couldn't consider myself a 'real' code-golfer unless I'd submitted a ridiculously-inefficient 'brute-force' answer that would time-out with anything except the shortest input...

Completes on TIO for n up to 3.
> 0 votes

---
Tags: code-golf, combinatorics, grid, graph-theory
---


title: Distributive on myself

text:
# Question
Title: Distributive on myself
## Background

We all know about distributivity, i.e. \\$a(b+c) = ab + ac\\$. This is a property on *2* different operations, namely addition and multiplication. But indeed, nothing can stop us from studying distributivity of 1 operation. In this challenge, you will be studying a kind of left-distributive operation.

## Task

Given a positive integer \\$N\\$. Consider an operation \\$p \star q\\$ where \\$p, q\in\\{0, 1,\dots, N-1\\}\\$, such that \\$ p \star 1 \equiv p + 1 \pmod N\\$ and \\$p \star (q \star r) = (p \star q) \star (p \star r)\\$. In essence, you are making an \\$N\times N\\$ table. For instance, if \\$N = 4\\$, a possible \\$\star\\$ is:

```
⋆ q 0 1 2 3
p-+---------
0 | 0 1 2 3
1 | 0 2 0 2 ←
2 | 0 3 0 3
3 | 0 0 0 0
      ↑

```

Note that the marked column satisfies \\$ p \star 1 \equiv p + 1 \pmod N\\$. In this challenge, we are interested in the marked *row*. It seems to be periodic, and the challenge is to find its period. The smallest positive period for a sequence \\$a\_0, \dots , a\_{N-1}\\$, is defined to be the smallest positive integer \\$k\\$, such that \\$k\\$ divides \\$N\\$, and \\$a\_i = a\_{i + k}\\$, for \\$i=0..(N-k-1)\\$.

However, there may be many possible \\$\star\\$'s for a given \\$N\\$, or there may be none. So you need to compute the (smallest positive) periods for all of them.

> Task: given a positive integer `N`, compute all the possible smallest positive periods of `1 ⋆ q`. This is .

## Details and clarifications

In the case `N = 4`, the given table turns out to be the only possible one, so you should output a list (or a set, etc.) consisting only of the number `2`. But for `N = 3`, no operation satisfies all the requirements, so you can output an empty list, or 0, or some falsy value.

The smallest positive period will always be between 1 and \\$N\\$, if the sequence `1 ⋆ q` (`0 <= q < N`) doesn't repeat at all, it is of period \\$N\\$.

`N` will range from 1 to \\$2^{32}-1\\$. So it is almost . But note that a formula or recurrence relation of this is unknown.

## Test cases

```
In : N = 1
Out: [1]

In : N = 2
Out: [1]

In : N = 3
Out: []

In : N = 4
Out: [2]

```

# Answer
# Python 2, 113 bytes

```
N=input()
f=lambda p,q:f(f(p,q-1),-~p%N)if p*q else q
print([i for i in range(1,N)if N%i+f(1,i)<1]+[N])[:N&N-1<1]

```

*-2 bytes thanks to @Jakque*

Try it online!

The short, recursive approach is slow since it repeats computation of many entries, so I've made an iterative, memoized approach which is much faster (quadratic in `N`) and can compute up to `N=4096` within 60 seconds on TIO.

# How it Works

The algorithm assumes that \\$\star\\$ is unique, if it exists (proof below). It uses recursion, setting

\\$p\star q=\begin{cases} q, &p=0 \\ p+1 \mod n, &q=1 \\ (p \star (q-1 \mod n))\star (p+1 \mod n), &\text{otherwise} \end{cases}\\$

The first case (\\$p=0\\$) is Lemma 1 in the uniqueness proof: \\$0\star q=q\\$.

The second case (\\$q=1\\$) is given.

The third case has a simple proof despite its complex self (assuming addition and subtraction are mod \\$N\\$:

\begin{align\*} &p \star q\\ =&p \star ((q-1)+1) \\ =&p \star ((q-1)\star 1) \\ =&(p \star (q-1))\star(p\star 1) \\ =&(p \star (q-1))\star(p+1) \end{align\*}

This is enough to determine the unique \\$\star\\$ (The proof shows that the third case will not recurse indefinitely).

The period is the minimum \\$i\\$ such that \\$1\star (i+1) = 1\star 1 = 2\\$. If this \\$i\\$ doesn't divide \\$N\\$, then it is not a period.

### Ungolfed code:

```
# f(p,q,N) = p⋆q
def f(p,q,N):
    if p==0:
        return q
    if q==1:
        return (p+1)%N
    return f(f(p,(q-1)%N,N),(p+1)%N, N)

def period(N):
    if any(f(p,f(q,r,N),N) != f(f(p,q,N),f(p,r,N),N) for p in range(N) for q in range(N) for r in range(N)):
        # The f does not exist
        return []
    for i in range(1, N):
        # period is i if f(1,i+1)=f(1,1)=2
        if f(1,i+1,N) == 2:
            # might not be divisible, in which case it is not the period
            if N%i:
                return [N]
            return [i]

```

This could be sped up immensely by memoization utilizing \\$ a \star 2 = a \star (1 \star 1) = (a\star 1)\star (a\star 1) = (a+1)\star(a+1) \\$ and \\$1 \star a = (1\star (a-1))\star 2\\$.

# Proof of Uniqueness of \\$\star\\$

For this section, we assume all addition/subtraction is mod \\$N\\$.

**Lemma 1**: For all \\$a\\$, \\$0 \star a = a\\$

*Proof*: Induction

Base case: \\$a=1\\$. Given since \\$0\star 1=1\\$.

Step: Assume this lemma holds for \\$a=k\\$. Then \begin{align\*} &0 \star (k + 1)\\ =& 0\star (k\star 1) \\ =& (0\star k)\star (0\star 1) \\ =& k \star 1 \\ =& k+1, \end{align\*} so this holds for \\$a=k+1\\$. Since this addition is mod \\$N\\$, this will "wrap around" back to \\$0\\$, so it applies for \\$a=0\\$ too, not just \\$a\geq 1\\$

**Theorem**: If an operation \\$\star\\$ is valid for a given \\$N\\$, then it the unique \\$\star\\$ that is valid for that \\$N\\$.

*Proof:* We use strong induction to show that, for all \\$0\leq a,b\leq N-1\\$, \\$a\star b\\$ is uniquely determined by \\$N\\$. In addition, for each \\$a\\$ and \\$b\\$ in the same set, either (1) \\$a\star b=0\\$ or (2) \\$a\<a\star b\<N\\$

1. Base case: \\$a\star b\\$ is uniquely determined and equal to \\$0\\$ for \\$a=N-1\\$ and for all \\$b\\$.

We prove this base case with induction too.

1. Base case: \\$b=1\\$. We are given \\$a\star 1=a+1\\$, so \\$(N-1)\star 1=0\\$, uniquely determined.
    2. Step: Given \\$(N-1)\star b=0\\$ for \\$b=k\\$, then \begin{align\*} &(N-1)\star (b+1)\\ =&(N-1)\star (b\star 1)\\ =&((N-1)\star b)\star((N-1)\star 1)\\ =&0\star0 \\ =&0, \end{align\*} where we use Lemma 1 to show \\$0\star 0=0\\$, so \\$(N-1)\star b\\$ is uniquely determiend to be \\$0\\$.
2. Assume \\$a\star b\\$ is uniquely determined and either (1) or (2) hold for all \\$k\<a\leq N-1\\$ and for all \\$b\\$. Then for \\$a=k\\$, we will show \\$a\star b\\$ is uniquely determined and either (1) or (2) hold for all \\$b\\$, again with induction.

1. Base case: \\$k\star b\\$ is uniquely determined and either (1) or (2) hold for \\$b=1\\$. This is trivial since \\$k\star 1=k+1\>k\\$, so \\$k\star 1\\$ is unique and (2) holds
    2. Step: Assume \\$k\star b\\$ is uniquely determined and either (1) or (2) hold for \\$b=j\\$. Then: \begin{align\*} &k\star (b+1)\\ =&k\star (b\star 1)\\ =&(k\star b)\star(k\star 1)\\ =&(k\star b)\star(k+1) \end{align\*} If (1) holds, then \\$k\star b=0\\$, so \\$k\star(b+1)=k+1\>k\\$ by Lemma 1. Thus \\$k\star(b+1)\\$ is uniquely determined and satisfies (2).

    If (2) holds, then \\$k\<k\star b\leq N-1\\$,so by the outer inductive assumption, \\$k\star(b+1)=(k\star b)\star (k+1)\\$ is uniquely determined and either (1) or (2) holds for it.

    In either case, \\$k\star(b+1)\\$ is uniquely determined and either (1) or (2) hold for it, completing the inductive step.
> 11 votes

# Answer
# Wolfram Language (Mathematica), ~~106~~ ~~90~~ 42 bytes

```
AtomQ@#&&2^Tr@UnitStep[#-{2,3,5,9}]&@*Log2

```

Try it online!

Returns the period if it exists, or `False` otherwise.

Laver Tables exist iff \\$N\\$ is a power of 2. The sequence of periods is A098820 on the OEIS.

Assuming the l3 rank-into-rank cardinal exists, it's been shown that the first \\$N\\$ for which the period is greater than 16 is at least \\$2^{A(9,A(8,A(8,255)))}\ggg2^{31}-1\\$, where \\$A\\$ is the Ackermann function. John Baez has a relatively accessible layman's explanation here.
> 3 votes

---
Tags: code-golf
---


title: Verify Tents and Trees solution

text:
# Question
Title: Verify Tents and Trees solution
## Background

**Tents and Trees** (try here) is a puzzle played on a square (or rectangular) grid, where the objective is to place tents horizontally or vertically adjacent to each of the trees, so that no two tents touch each other in 8 directions (horizontally, vertically, and diagonally) and the number of tents on each row/column matches the given clues.

### Example puzzle and solution

In these examples, trees are `T` and tents are `A`.

```
Puzzle
  2 0 2 0 2 1
2 . T . T . .
1 . . . . T .
1 T . T . . .
2 . . . . . T
1 T . . . . .
0 . . . . . .

Solution
  2 0 2 0 2 1
2 . T A T A .
1 A . . . T .
1 T . T . A .
2 A . A . . T
1 T . . . . A
0 . . . . . .

```

## Challenge

Given a grid with some tents and trees, determine whether the tents are placed correctly. Ignore the number clues in this challenge. In particular, your program should check the following:

* The number of tents equals the number of trees,
* The tents do not touch each other in 8 directions, and
* There is at least one way to associate every tent with an adjacent tree in 4 directions, so that every tree is used exactly once.

If all of the above are satisfied, output a truthy value; otherwise, output a falsy value. You can choose to follow your language's convention of truthy/falsy, or use two distinct values for true/false respectively.

You may take the input in any reasonable way to represent a matrix containing three distinct values to represent a tree, a tent, and an empty space respectively.

Standard rules apply. The shortest code in bytes wins.

## Test cases

This uses the same notation as the above example; `T` for trees, `A` for tents, and `.` for empty spaces.

### Truthy

```
. . .
. . .
. . . (empty board)

T A

A T A
. . T

A T A
T . T
A T A
(note that there are two ways to associate tents with trees)

A . .
T T A
A T T
. . A

. T A .
A . . T
T T . A
. A . .

```

### Falsy

```
(The number of Ts and As don't match)
T

A

T A T

(Two A's touch each other)
T A T
A . .

A . . A
T T T T
. A A .

(Some T's are not associated with an A)
A T A
T T .
A T A

A . T
T T A
A . .

```

# Answer
> 4 votes
# , 88 86 bytes

Expects a matrix with 0 for `.`, 1 for `A` and 2 for `T`.

```
(2>1#.1=,);.3~&2 2*/@,&,1&=((1 e.[:*/"{2>[:+/"1|@-"2)i.@!@#A.]) ::0&($ #:i.@$#~&,])2&=

```

Try it online!

### How it works

```
1&= (…) 2&=

```

Tents on the left side, trees on the right side.

```
(…)&($#:i.@$#~&,])

```

Convert both arguments to 2D coordinates.

```
(…) ::0

```

If the following function throws an error, return 0. This happens only in the single `A` case. :-(

```
i.@!@#A.]

```

List all permutations of the trees.

```
|@-"2

```

Get the difference between the tents from every permutation.

```
[:*/2>[:+/"1

```

Check that each difference's sum is 1.

```
1 e.

```

Does any permutation fulfill this?

```
(2>1#.1=,);.3~&2 2

```

Get all 2x2 matrices of the original, and check if there is at most one tent in there.

```
*/@,@,

```

Combine both results, flatten the lists, and check if there are only 1's.

# Answer
> 3 votes
# JavaScript (ES7),  ~~159 156~~  153 bytes

Expects a matrix of integers, with **0** for empty, **-1** for a tree and **1** for a tent. Returns **0** or **1**.

```
m=>(g=(X,Y,R)=>!/1/.test(m)|m.some((r,y)=>r.some((v,x)=>1/Y?(q=(x-X)**2+(y-Y)**2)?R?v+q?0:g(R[X]=r[x]=0)|R[X]++|r[x]--:q<3*v:0:v>0&&!g(x,y)&g(x,y,r))))``

```

Try it online!

### How?

The main recursive function is used to perform 3 distinct tasks. The corresponding calls are marked as A-type, B-type and C-type respectively in the commented source. Below is a summary:

```
 type   | Y defined | R defined | task
--------+-----------+-----------+----------------------------------------------------
 A-type |    no     |     no    | Look for tents. Process B-type and C-type calls
        |           |           | for each of them.
--------+-----------+-----------+----------------------------------------------------
 B-type |   yes     |     no    | Look for another tent touching the reference tent.
--------+-----------+-----------+----------------------------------------------------
 C-type |   yes     |    yes    | Look for adjacent trees. Attempt to remove each of
        |           |           | them with the reference tent. Chain with an A-type
        |           |           | call.

```

### Commented

```
m => (                       // m[] = input matrix
  g = (                      // g is the main recursive function taking:
    X, Y,                    //   (X, Y) = reference tent coordinates
    R                        //   R[] = reference tent row
  ) =>                       //
    !/1/.test(m) |           // success if all the tents and trees have been removed
    m.some((r, y) =>         // for each row r[] at position y in m[]:
      r.some((v, x) =>       //   for each value v at position x in r[]:
        1 / Y ?              //     if Y is defined:
          ( q = (x - X) ** 2 //       q = squared distance (quadrance)
              + (y - Y) ** 2 //           between (x, y) and (X, Y)
          ) ?                //       if it's not equal to 0:
            R ?              //         if R[] is defined (C-type call):
              v + q ? 0 :    //           if v = -1 and q = 1, meaning that we have
                             //           found an adjacent tree:
                g(           //             do an A-type recursive call:
                  R[X] =     //               with both the reference tent
                  r[x] = 0   //               and this tree removed
                )            //             end of recursive call
                | R[X]++     //             restore the tent
                | r[x]--     //             and the tree
            :                //           else (B-type call):
              q < 3 * v      //             test whether this is a tent with q < 3
          :                  //       else (q = 0):
            0                //         do nothing
        :                    //     else (A-type call):
          v > 0 &&           //       if this is a tent:
            !g(x, y)         //         do a B-type recursive call to make sure it's
            &                //         not touching another tent
            g(x, y, r)       //         do a C-type recursive call to make sure that
                             //         it can be associated to a tree
      )                      //   end of inner some()
    )                        // end of outer some()
)``                          // initial A-type call to g with both Y and R undefined

```

# Answer
> 2 votes
# 05AB1E, ~~53~~ ~~49~~ ~~42~~ 60 bytes

```
1«ÐεNUεXN)]€`{.¡н}¦`UœεX‚®ζε`αO<]PßsZð×ª€ü2ø€ü2J˜2δ¢à*ISPΘ‚à

```

+11 bytes as bug-fix (thanks for noticing *@xash*) and +7 bytes to account for inputs only containing empty cells.. Not too happy with the current program full of ugly edge-case workarounds tbh, but it works..

Input as a list of string-lines, where \\$2\\$ is a tent; \\$3\\$ is a tree; and \\$1\\$ is an empty spot.
Outputs \\$1\\$ for truthy; and anything else for falsey (only \\$1\\$ is truthy in 05AB1E, so this is allowed by the challenge rule "*You can choose to follow your language's convention of truthy/falsy*").

Try it online or verify all test cases.

**Explanation:**

I do three main steps:

Step 1: Get all coordinates of the trees and tents, and check whether there is a permutation of tree permutations that has a horizontal or vertical distance of 1 with the tent coordinates.

```
1«         # Add a trailing empty spot to each row
           # (to account for matrices with only tents/trees and single-cell inputs)
  Ð        # Triplicate this matrix with added trailing 2s
   ε       # Map each row to:
    NU     #  Store the index of this outer map in `X`
    ε      #  Inner map over each cell of this row:
     XN)   #   Create a triplet of the cell-value, `X`, and the inner map-index `N`
   ]       # Close the nested maps
    €`     # Flatten the list of lists of cell-coordinates one level down
{          # Sort the list of coordinates, so the empty spots are before tents, and tents
           # before trees
 .¡ }      # Then group them by:
   н       #  Their first item (the type of cell)
     ¦     # And remove the first group of empty spots
`          # Pop and push the list of tree and tent coordinates separated to the stack
 U         # Pop and store the tent coordinates in variable `X`
           # (or the input with trailing empty spots if there were only empty spots in
           #  the input)
  œ        # Get all permutations of the tree coordinates
           # (or the input with trailing empty spots if there are none, hence the
           #  triplicate instead of duplicate..)
ε          # Map each permutation of tree coordinates to:
 X‚        #  Pair it with the tent coordinates `X`
    ζ      #  Zip/transpose; swapping rows/columns,
   ®       #  with -1 as filler value if the amount of tents/trees isn't equal
     ε     #  Map each pair of triplets to:
      `    #  Pop and push them separated to the stack
       α   #  Get the absolute different between the values at the same positions
        O  #  Take the sum of those differences for each triplet
         < #  Subtract each by 1 to account for the [2,3] of the tree/tent types
]          # Close the nested maps
 P         # Take the product of each difference of coordinates
  ß        # And pop and push the smallest difference

```

Step 2: Get all 2x2 blocks of the matrix, and check that each block contains either none or a single tent (by counting the amount of tents per 2x2 block, and then getting the maximum).

```
s          # Swap to get the input-matrix with trailing empty spots we triplicated
 Z         # Get its maximum (without popping)
  ð×       # Create a string with that many spaces
    ª      # And append it to the list
           # (it's usually way too large, but that doesn't matter since it's shortened
           #  automatically by the `ø` below)
 €         # For each row:
  ü2       #  Create overlapping pairs
           #  (the `ü2` doesn't work for single characters, hence the need for the
           #   `1«` and `Zð×ª` prior)
    ø      # Zip/transpose; swapping rows/columns
           # (which also shortens the very long final row of space-pairs)
     €     # For each column of width 2:
      ü2   #  Create overlapping pairs
           # (we now have a list of 2x2 blocks)
 J         # Join all 2x2 blocks together to a single 4-sized string
  ˜        # And flatten the list
    δ      # Then for each 4-sized string:
   2 ¢     #  Count the amount of tents it contains
      à    # Pop and get the maximum count
           # (if this maximum is 1, it means there aren't any adjacent nor diagonally
           #  adjacent tents in any 2x2 block)

```

Step 3: Add the checks together, and account for inputs consisting only of empty spots as edge-case:

```
*          # Multiply the two values together
 I         # Push the input-matrix again
  S        # Convert it to a flattened list of digits
   P       # Take the product
    Θ      # Check that this is exactly 1 (1 if 1; 0 if not)
     ‚     # Pair it with the multiplied earlier two checks
      à    # And pop and push the maximum of this pair
           # (for which 1 is truthy; and anything else is falsey)
           # (after which it is output implicitly as result)

```

# Answer
> 2 votes
# Brachylog, 59 47 54 45 bytes

Trying to get into Brachylog lately, so here is a (now very) rough port of my J approach. Takes in a matrix with 0 for `.`, 2 for `A` and 3 for `T`. Either fails to unify (prints false) or doesn't.

```
c=₀|¬{s₂\s₂c⊇Ċ=₂}&{iiʰgᵗcṗʰ}ᶠhᵍpᵗz₂{\b-ᵐȧᵐ+1}ᵐ

```

Try it online! or verify all test cases (returns truthy cases).

### How it works

```
c=₀|

```

Either the flatten matrix contains only 0's or …

```
¬{s₂\s₂c

```

No 2x2 submatrix flattened …

```
⊇Ċ=₂}

```

contains an ordered subset of length 2 that is just 2's (tents).

```
&{iiʰgᵗc

```

And the input must be converted to `[type, y, x]`, where …

```
ṗʰ}

```

`type` is a prime (there seems no shorter way to filter out 0).

```
ᶠp

```

Find all `[type, y, x]` put them into a list, and permute this list.

```
hᵍ

```

Group them by their `type`; `[[[3,0,2], …], [[4,1,2], …]]`.

```
z₂

```

Zip both groups together and make sure they have the same length. We now have `[[[3,0,2], [4,1,2]], …]`

```
{\b-ᵐȧᵐ+1}ᵐ

```

For every element `[[3,0,2], [4,1,2]]` transpose `[[3,4],[0,1],[2,2]]` behead `[[0,1],[2,2]]` subtract `[_1,0]` absolute value `[1,0]` sum `1` and that must unify with 1. So this unifies if any permutation of the one group is exactly 1 tile away from the other one.

# Answer
> 2 votes
# Wolfram Language (Mathematica), 146 bytes

```
<<Combinatorica`
f=2*Length@MaximalMatching@MakeGraph[v=Position[#,A|T],Norm[#-#2]==1&]==Length@v&&
And@@Join@@BlockMap[Count[#,A,2]<2&,#,{2,2},1]&

```

Try it online!

Note:

* The second line break is only added in the post for ease of reading.
* importing `Combinatorica` later will make the symbols refer to the Global ones and will not have the correct result.
* Although `Combinatorica`MakeGraph` is rather long, `MaximalMatching` is 7 characters shorter than `FindIndependentEdgeSet`.
* I suppose this solution is the fastest...? There exists algorithms to find maximal matching in polynomial time, while testing all permutations take exponential time.

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


# Question
Title: Display powers of Phi with Fibonacci precision
Write some code that takes a single non-negative integer \\$n\\$ and outputs the \\$n\\$th power of phi (\\$\phi\\$, the Golden Ratio, approximately 1.61803398874989) with the same number of decimal digits as the \\$n\\$th Fibonacci number.

Your code must produce the correct sequence of digits for all inputs up to at least 10 (55 decimal digits). The output must be human-readable decimal. You may choose whether to round the last digit to the closest value, or truncate the value. Please specify which one your code uses.

\\$n\\$ and output, up to 10, rounding down:

```
 0   1
 1   1.6
 2   2.6
 3   4.23
 4   6.854
 5  11.09016
 6  17.94427190
 7  29.0344418537486
 8  46.978713763747791812296
 9  76.0131556174964248389559523684316960
10 122.9918693812442166512522758901100964746170048893169574174

```

\\$n\\$ and output, up to 10, rounding to the closest value:

```
 0   1
 1   1.6
 2   2.6
 3   4.24
 4   6.854
 5  11.09017
 6  17.94427191
 7  29.0344418537486
 8  46.978713763747791812296
 9  76.0131556174964248389559523684316960
10 122.9918693812442166512522758901100964746170048893169574174

```

The 7th Fibonacci number is 13, so the output for \\$n=7\\$, \\$\phi^7\\$, has 13 decimal places. You must not truncate trailing zeros that would display too few digits; see output for 6 in the first table, which ends in a single zero to keep the decimal precision at 8 digits.

Maybe as a bonus, say what the highest number your program can correctly output is.

# Answer
> 4 votes
# dc, 26 bytes

```
99k5v1+2/?^d5v/.5+0k1/k1/p

```

Due to the initial precision of 99 digits after the comma, this will work up yo input **11**. A dynamic (or higher static) precision is possible, but would elevate the byte count.

### Test cases

```
$ for ((i = 0; i < 11; i++)) { dc -e '99k5v1+2/?^d5v/.5+0k1/k1/p' <<< $i; }
1
1.6
2.6
4.23
6.854
11.09016
17.94427190
29.0344418537486
46.978713763747791812296
76.0131556174964248389559523684316960
122.9918693812442166512522758901100964746170048893169574174

```

### How it works

Since the desired output is **φn**, we can calculate the the Fibonacci number **F(n)** as **⌊φn ÷ √5 + 0.5⌋** with little additional effort.

```
99k                         Set the precision to 99.
   5v                       Compute the square root of 5.
     1+                     Add 1.
       2/                   Divide by 2.
                            This pushes the golden ratio.
         ?                  Read the input from STDIN.
          ^                 Elevate the golden ratio to that power.
           d                Push a copy.
            5v/             Divide it by the square root of 5.
               .5+          Add 0.5.
                  0k        Set the precision to 0.
                    1/      Divide by 1, truncating to the desired precision.
                            This pushes F(n).
                      k     Set the precision to F(n).
                       1/   Divide by 1, truncating to the desired precision.
                         p  Print.

```

# Answer
> 1 votes
# Mathematica, 50 bytes

```
N[GoldenRatio^#,2^#]~NumberForm~{2^#,Fibonacci@#}&

```

Basic solution. Rounds to the nearest value. ~~Still verifying the highest value that won't make my computer run out of memory.~~ Input `32` works, but it takes 45 minutes and uses 16GiB of RAM. However, given infinite time and memory, this could theoretically run for any value.

# Answer
> 0 votes
# Javascript, 65 bytes

```
a=>Math.pow((1+Math.sqrt(5))/2,a).toFixed(k(a));k=b=>b?b+k(b-1):0

```

Getting Phi by calculating `(1+Math.sqrt(5))/2`.

Getting Fib value using the function: `k=b=>b?b+k(b-1):0`.

Try it out

---
Tags: code-golf, fibonacci
---


title: Code golf a random orthogonal matrix

text:
# Question
Title: Code golf a random orthogonal matrix
An orthogonal matrix is a square matrix with real entries whose columns and rows are orthogonal unit vectors (i.e., orthonormal vectors).

This means that M^T M = I, where I is the identity matrix and ^T signifies matrix transposition.

Note that this is orthogonal not "special orthogonal" so the determinant of M can be 1 or -1.

The aim of this challenge is not machine precision so if M^T M = I to within 4 decimal places that will be fine.

The task is to write code that takes a positive integer `n > 1` and outputs a random orthogonal n by n matrix. The matrix should be randomly and uniformly chosen from **all** n by n orthogonal matrices. In this context, "uniform" is defined in terms of the Haar measure, which essentially requires that the distribution does not change if multiplied by any freely chosen orthogonal matrix. This means the values of the matrix will be floating point values in the range -1 to 1.

The input and output can be any form you find convenient.

Please show an explicit example of your code running.

You may not use any existing library function which creates orthogonal matrices. This rule is a little subtle so I will explain more. This rule bans the use of any existing function which takes in some (or no) input and outputs a matrix of size at least n by n which is guaranteed to be orthogonal. As an extreme example, if you want the n by n identity matrix, you will have to create it yourself.

You can use any standard random number generator library for choosing random numbers of your choosing.

Your code should complete within at most a few seconds for `n < 50`.

# Answer
# Haskell, ~~169~~ ~~150~~ ~~148~~ ~~141~~ ~~132~~ 131 bytes

```
import Numeric.LinearAlgebra
z=(unitary.flatten<$>).randn 1
r 1=asRow<$>z 1
r n=do;m<-r$n-1;(<>diagBlock[m,1]).haussholder 2<$>z n

```

Recursively extend an orthogonal matrix of size `n-1` by adding 1 to lower right corner and apply a random Householder reflection. `randn` gives a matrix with random values from a gaussian distribution and `z d` gives a uniformly distributed unit vector in `d` dimensions.

`haussholder tau v` returns the matrix `I - tau*v*vᵀ` which isn't orthogonal when `v` isn't a unit vector.

Usage:

```
*Main> m <- r 5
*Main> disp 5 m
5x5
-0.24045  -0.17761   0.01603  -0.83299  -0.46531
-0.94274   0.12031   0.00566   0.29741  -0.09098
-0.02069   0.30417  -0.93612  -0.13759   0.10865
 0.02155  -0.83065  -0.35109   0.32365  -0.28556
-0.22919  -0.41411   0.01141  -0.30659   0.82575
*Main> (<1e-14) . maxElement . abs $ tr m <> m - ident 5
True

```
> 8 votes

# Answer
# Python 2+NumPy, 163 bytes

Thanks to xnor for pointing out to use normal distributed random values instead of uniform ones.

```
from numpy import*
n=input()
Q=random.randn(n,n)
for i in range(n):
 for j in range(i):u=Q[:,j];Q[:,i]-=u*dot(u,Q[:,i])/dot(u,u)
Q/=(Q**2).sum(axis=0)**0.5
print Q

```

Uses the Gram Schmidt Orthogonalization on a matrix with gaussian random values to have all directions.

The demonstration code is followed by

```
print dot(Q.transpose(),Q)

```

n=3:

```
[[-0.2555327   0.89398324  0.36809917]
 [-0.55727299  0.17492767 -0.81169398]
 [ 0.79003155  0.41254608 -0.45349298]]
[[  1.00000000e+00   0.00000000e+00   0.00000000e+00]
 [  0.00000000e+00   1.00000000e+00  -5.55111512e-17]
 [  0.00000000e+00  -5.55111512e-17   1.00000000e+00]]

```

n=5:

```
[[-0.63470728  0.41984536  0.41569193  0.25708079  0.42659843]
 [-0.36418389  0.06244462 -0.82734663 -0.24066123  0.3479231 ]
 [ 0.07863783  0.7048799   0.08914089 -0.64230492 -0.27651168]
 [ 0.67691426  0.33798442 -0.05984083  0.17555011  0.62702062]
 [-0.01095148 -0.45688226  0.36217501 -0.65773717  0.47681205]]
[[  1.00000000e+00   1.73472348e-16   5.37764278e-17   4.68375339e-17
   -2.23779328e-16]
 [  1.73472348e-16   1.00000000e+00   1.38777878e-16   3.33066907e-16
   -6.38378239e-16]
 [  5.37764278e-17   1.38777878e-16   1.00000000e+00   1.38777878e-16
    1.11022302e-16]
 [  4.68375339e-17   3.33066907e-16   1.38777878e-16   1.00000000e+00
    5.55111512e-16]
 [ -2.23779328e-16  -6.38378239e-16   1.11022302e-16   5.55111512e-16
    1.00000000e+00]]

```

It completes within a blink for n=50 and a few seconds for n=500.
> 5 votes

# Answer
# APL (Dyalog Unicode), ~~63~~ 61 bytes

```
⎕CY'dfns'
n←⊢÷.5*⍨a←+.×⍨
{{⍵,(n⊢-⊣×a)/⌽⍺,⍵}/⊂∘n¨↓NormRand⍵ ⍵}

```

Try it online for n=5

*-1 byte thanks to @user41805 (improved train for inner dfn)*

Uses the modified Gram-Schmidt process on a set of `n` random unit vectors --- fast.

**How?**

```
⎕CY'dfns'   ⍝ Copy the dfns namespace, which includes the NormRand dfn
n←⊢÷.5*⍨+.×⍨  ⍝ n: normalize the vector argument, from https://codegolf.stackexchange.com/a/149160/68261
{{⍵,(n⊢-⊣×+.×⍨)/⌽⍺,⍵}/⊂∘n¨↓NormRand⍵ ⍵} ⍝ Main anonymous function
                           NormRand ⍵ ⍵  ⍝ Generate an n×n array of gaussian variables
                       ⊂∘n¨↓             ⍝ Treat as an array of singular arrays of n-vectors; normalize each
 {                   }/                  ⍝ Reduce in a sneaky manner to get array of orthogonal (e_1, ... e_n)
                                         ⍝ Start with e_arr=⍬ (empty)
                                         ⍝ For each vector v_i:
                ⌽⍺,⍵                      ⍝ Start this step with e_arr←(e_{i-1}, ..., e_1, e_0, v_i)
    (         )/                          ⍝ Reduce this to repeatedly modify from the right:
     n⊢-⊣×+.×⍨                             ⍝ Normalize(v_i - proj_{e_j}(v_i))
  ⍵,                                       ⍝ Append this to e_arr

```
> 4 votes

# Answer
# Mathematica, 69 bytes, probably non-competing

```
#&@@QRDecomposition@Array[RandomVariate@NormalDistribution[]&,{#,#}]&

```

`QRDecomposition` returns a pair of matrices, the first of which is guaranteed to be orthogonal (and the second of which is not orthogonal, but upper triangular). One could argue that this technically obeys the letter of the restriction in the post: it doesn't output an orthogonal matrix, but a pair of matrices....

# Mathematica, 63 bytes, definitely non-competing

```
Orthogonalize@Array[RandomVariate@NormalDistribution[]&,{#,#}]&

```

`Orthogonalize` is unambiguously forbidden by the OP. Still, Mathematica is pretty cool eh?
> -1 votes

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


title: Pi got your number

text:
# Question
Title: Pi got your number
## Challenge :

\\$\pi\\$ is supposed to be infinite. That means every number is contained inside the decimal part of \\$\pi\\$. Your task will be to take a positive integer on input and return the position of this number in \\$\pi\\$ digits on output.

For example, if the input is `59`, we'll return `4`

**Here is why :** we will look for the number `59` in the digits of \\$\pi\\$

```
3.14159265...
     ^^

```

The value starts at the 4th digit, so the output will be `4`.

**Some other examples :**

```
input : 1      output : 1
input : 65     output : 7
input : 93993  output : 42
input : 3      output : 9

```

## Rules :

* You don't have to handle digits that doesn't exist within the first 200 digits
* Standard loopholes are, as always, forbidden.
* This is , so the fewer bytes wins.

# Answer
# Python 2, ~~69~~ ~~75~~ ~~71~~ 67 bytes

*Saved 4 bytes due to caird coinheringaahing.*

```
x=p=1333
while~-p:x=p/2*x/p+2*10**200;p-=2
print`x`.find(input(),1)

```

Not finding `3` at position zero cost ~~6~~ 2 bytes. Input is given as a string.

Try it online!

---

**Unbounded Version**

## Python 2, 224 bytes

```
def g():
 q,r,t,i,j=1,0,1,0,1
 while True:
  i+=1;j+=2;q,r,t=q*i,(2*q+r)*j,t*j;n=(q+r)/t
  if n*t>4*q+r-t:yield n;q,r=10*q,10*(r-n*t)
a=input()
l=len(`a`)
s=z=10**l;i=1-l
p=g().next;p()
while s!=a:s=(s*10+p())%z;i+=1
print i

```

Using an unbounded spigot based on the same formula used above.

Try it online!

---

**Faster Version**

```
from gmpy2 import mpz
def g():
  # Ramanujan 39, multi-digit
  q, r, s ,t = mpz(0), mpz(3528), mpz(1), mpz(0)
  i = 1
  z = mpz(10)**3511
  while True:
    n = (q+r)/(s+t)
    if n == (22583*i*q+r)/(22583*i*s+t):
      for d in digits(n, i>597 and 3511 or 1): yield d
      q, r = z*(q-n*s), z*(r-n*t)
    u, v, x = mpz(1), mpz(0), mpz(1)
    for k in range(596):
      c, d, f = i*(i*(i*32-48)+22)-3, 21460*i-20337, -i*i*i*24893568
      u, v, x = u*c, (u*d+v)*f, x*f
      i += 1
    q, r, s, t = q*u, q*v+r*x, s*u, s*v+t*x

def digits(x, n):
  o = []
  for k in range(n):
    x, r = divmod(x, 10)
    o.append(r)
  return reversed(o)

a=input()
l=len(`a`)
s=z=10**l;i=1-l
p=g().next;p()
while s!=a:s=(s*10+p())%z;i+=1
print i

```

A much faster unbounded spigot, based on Ramanujan #39.

Try it online!
> 22 votes

# Answer
# Husk, 5 bytes

```
€tİπd

```

Try it online!

### Explanation

```
€tİπd                              59
    d  Convert to base-10 digits   [5,9]
  İπ     The digits of pi          [3,1,4,1,5,9..]
 t       Remove the first element  [1,4,1,5,9,2..]
€      Index of the sublist        4

```
> 19 votes

# Answer
# Excel, 212 bytes

```
=FIND(A1,"14159265358979323846264338327950288419716939937510582097494459230781640628620899862803482534211706798214808651328230664709384460955058223172535940812848111745028410270193852110555964462294895493038196")

```

Excel only handles 15 decimal places so pi is just hard-coded. This should be a pretty weak upper bound for this challenge.
> 18 votes

# Answer
# Java 8, ~~615~~ ~~217~~ ~~202~~ ~~184~~ ~~182~~ ~~166~~ 165 bytes (calculated ~~999~~ 200 digits)

```
n->{var t=java.math.BigInteger.TEN.pow(200);var r=t;for(int p=667;p-->1;)r=t.valueOf(p).multiply(r).divide(t.valueOf(p-~p)).add(t).add(t);return(r+"").indexOf(n,1);}

```

1-indexed

Try it online.

Java's builtin `Math.PI` has a precision of 15 decimal values, like many other languages. To have more digits, you'll have to calculate them yourself with `BigIntegers` or `BigDecimals`. This above is a way to do it.. ~~Maybe someone can golf this below 211 bytes, lol..~~
EDIT: Created a port of *@primo*'s Python 2 answer (make sure to upvote him!), so calculating being shorter than hard-coded is not so far-fetched anymore. ~~Just 7 more bytes to golf for it to be shorter.~~

-15 bytes thanks to *@Neil*, making it shorter than the hard-coded answer below!
-36 bytes thanks to *@primo*.
-1 byte changing `java.math.BigInteger t=null,T=t.TEN.pow(200),r=T;` to `var T=java.math.BigInteger.TEN.pow(200);var r=T;`, because `var` is 1 byte shorter than `null` (gotta love the new Java 10).

**Explanation:**

```
n->{                            // Method with String parameter and integer return-type
  var t=java.math.BigInteger.TEN.pow(200);
                                //  Temp BigInteger with value 10^200
  var r=t;                      //  Result BigInteger, also starting at 10^200
  for(int p=667;                //  Index-integer, starting at 667
      p-->1;)                   //  Loop as long as this integer is still larger than 1
                                //  (decreasing `p` by 1 before every iteration with `p--`)
    r=                          //   Replace the Result BigInteger with:
      t.valueOf(p)              //    `p`
       .multiply(r)             //    multiplied by `r`,
       .divide(t.valueOf(p-~p)) //    divided by `2*p+1`
       .add(t).add(t);          //    And add 2*10^200
  return(r+"")                  //  Convert the BigInteger to a String
    .indexOf(n,                 //  And return the index of the input,
               1);}             //  skipping the 3 before the comma

```

---

# Java 8, 211 bytes (hard-coded 200 digits)

```
"14159265358979323846264338327950288419716939937510582097494459230781640628620899862803482534211706798214808651328230664709384460955058223172535940812848111745028410270193852110555964462294895493038196"::indexOf

```

0-indexed

Try it online.
> 9 votes

# Answer
# MATL, ~~16~~ 15 bytes

```
YP8WY$4L)jXfX<q

```

Try it online!

### Explanation

```
YP     % Push pi as a double
8W     % Push 2^8, that is, 256
Y$     % Compute pi with 256 significant digits using variable-precision arithmetic
       % The result as a string
4L)    % Remove first character. This is to avoid finding '3' in the integer part
       % of pi
j      % Push input as a string
Xf     % Strfind: gives array of indices of occurrences of the input string in the
       % pi string
X<     % Mimimum
q      % Subtract 1. Implicitly display

```
> 6 votes

# Answer
# 05AB1E, 6 bytes

```
₁žs¦¹k

```

Try it online!

**How?**

```
₁        push 256
 žs      push pi to 256 places
   ¦     remove the leading 3
    ¹    push the input
     k   index inside that string

```
> 6 votes

# Answer
# \+ numbers package, 52 bytes

```
regexec(scan(),substring(numbers::dropletPi(200),3))

```

Try it online!

`dropletPi` computes the first 200 decimal digits of `pi` but includes a `3.` at the beginning, so we strip that out with `substring` and then match with `regexec`, which returns the index of the match along with some metadata about the match.
> 4 votes

# Answer
# Jelly, 23 bytes

```
⁵*⁹Ḥ;ȷḊ+J$¤×⁹:2¤:ɗ\SṾḊw

```

A monadic link accepting a list of characters (the integer to find) and returning the index. Works for inputs contained within the first 252 digits of the decimal part of π.

**Try it online!**

### How?

This uses the Leibniz formula for π to calculate the first 253 digits including the leading `3` (plus four trailing incorrect digits). The leading `3` is then dropped and the index of the input is found:

```
⁵*⁹Ḥ;ȷḊ+J$¤×⁹:2¤:ɗ\SṾḊw - Link: list of characters
⁵                       - literal ten
  ⁹                     - literal 256
 *                      - exponentiate = 10000...0 (256 zeros)
   Ḥ                    - double       = 20000...0
          ¤             - nilad followed by links as a nilad:
     ȷ                  -   literal 1000
      Ḋ                 -   dequeue -> [2,3,4,5,...,1000]
         $              -   last two links as a monad:
        J               -     range of length -> [1,2,3,4,...,999]
       +                -     addition (vectorises) -> [3,5,7,9,...,1999]
    ;                   -   concatenate -> [20000...0,3,5,7,9,...,1999]
                  \     - cumulative reduce with:
                 ɗ      -   last three links as a dyad:
               ¤        -     nilad followed by link(s) as a nilad:
            ⁹           -       chain's right argument (the right of the pair as we traverse the pairs in the list -- 3, 5, 7, 9, ...)
              2         -       literal two
             :          -       integer division (i.e. 1, 2, 3, ...)
           ×            -     multiply (the left of the pair, the "current value", by that)
                :       -   integer divide by the right argument (i.e. 3, 5, 7, 9, ...)
                   S    - sum up the values (i.e. 20000...0 + 66666...6 + 26666...6 + 11428...2 + ... + 0)
                    Ṿ   - un-evaluate (makes the integer become a list of characters)
                     Ḋ  - dequeue (drop the '3')
                      w - first (1-based) index of sublist matching the input

```

If you prefer a list of digits as input use `⁵*⁹Ḥ;ȷḊ+J$¤×⁹:2¤:ɗ\SDḊw` (also 23), while if you really want to give it an integer use `⁵*⁹Ḥ;ȷḊ+J$¤×⁹:2¤:ɗ\SDḊwD` (for 24).
> 3 votes

# Answer
# BASH (GNU/Linux), ~~75~~ ~~67~~ 66 bytes

Saved 1 byte thanks to Sophia Lechner, and 7 bytes thanks to Cows quack.

```
a=`bc -l<<<"scale=999;4*a(1)"|tail -c+2|grep -ob $1`;echo ${a%%:*}

```

This is a shell script that takes a single argument, which is the number. Test with

```
$ bash <script-path> 59
4

```

This script first executes a pipeline of three commands:

```
bc -l<<<"scale=999;4*a(1)"|    #produce pi with its first 999 fractional digits
tail -c+2|                     #cut off the "3."
grep -ob $1                    #compute the byte offsets of our argument in the string

```

The result of this pipeline is assigned to the shell variable `a`, which is then echoed out with anything but the first number removed:

```
a=`...`;         #assign the result of the pipeline to a variable
echo ${a%%:*}    #cleave off the first : character and anything following it

```

---

Unfortunately, `bc` has the tendency to break output lines when they become too long. This may lead to wrong results if the number to be found is not on the first line. You can avoid that by setting the environment variable `BC_LINE_LENGTH`:

```
export BC_LINE_LENGTH=0

```

This deactivates the line breaking feature completely.

---

Obviously, the last two commands may be omitted if other output is tolerated.
This gives a count of **48 bytes**:

```
bc -l<<<"scale=999;4*a(1)"|tail -c+2|grep -ob $1

```

With the resulting output:

```
$ bash <script-path> 59
4:59
61:59
143:59
179:59
213:59
355:59
413:59
415:59
731:59
782:59
799:59
806:59
901:59
923:59
940:59
987:59

```
> 3 votes

# Answer
# Haskell, ~~208~~ 120 bytes

```
a=1333
x=tail$show$foldr(\p x->p`div`2*x`div`p+2*10^200)a[3,5..a]
x!n|take(length n)x==n=0|1<2=1+tail x!n
f n=1+x!show n

```

Try it online!

Many thanks to Jonathan Allan for his suggestions!

### Old version (208 bytes)

```
(+1).((tail$g(1,0,1,1,3,3))!)
g(q,r,t,k,n,l)=([n:g(10*q,10*(r-n*t),t,k,div(10*(3*q+r))t-10*n,l)|4*q+r-t<n*t]++[g(q*k,(2*q+r)*l,t*l,k+1,div(q*(7*k+2)+r*l)(t*l),l+2)])!!0
x!n|take(length n)x==n=0|1<2=1+tail x!n

```

I actually don't know how the code above works; I've taken it from this paper and all I implemented was the lookup part. `g(1,0,1,1,3,3)` returns the digits of pi and is surprisingly efficient (it computes 10 000 digits on tio.run in less than 4s).

The input is a list consisting of the digits of the number to be found.

Try it online!
> 2 votes

# Answer
# SmileBASIC, ~~179~~ 164 bytes

```
INPUT I$FOR I=0TO 103Q$=Q$+STR$(ASC("\A#YO &.+& O2TGE']KiRa1,;N(>VYb>P0*uCb0V3 RB/]T._2:H5;(Q0oJ2)&4n7;@.^Y6]&"[I]))NEXT?INSTR(Q$,I$)+1

```

Digits of pi are hardcoded and packed into the ascii values of characters. 14 -\> `CHR$(14)`, 15 -\> `CHR$(15)`, 92 -\> `\`, 65 -\> `A`, 35 -\> `#`.

The string contains unprintable characters, so here are the bytes written in hexadecimal: `0E 0F 5C 41 23 59 4F 20 26 2E 1A 2B 26 20 4F 32 1C 54 13 47 45 27 5D 4B 69 52 00 61 31 2C 3B 17 00 4E 10 28 3E 56 14 59 62 3E 50 03 30 19 03 2A 75 00 43 62 15 30 00 56 33 20 52 1E 42 2F 00 5D 54 2E 00 5F 32 3A 16 1F 48 35 3B 28 51 1C 30 6F 4A 32 1C 29 00 1B 00 13 26 34 6E 37 3B 40 2E 16 5E 59 36 5D 00 26 13 06`

In decimal, you can see the digits of pi: `14 15 92 65 35 89 79 32 38 46 26 43 38 32 79 50 28 84 19 71 69 39 93 75 105 82 0 97 49 44 59 23 0 78 16 40 62 86 20 89 98 62 80 3 48 25 3 42 117 0 67 98 21 48 0 86 51 32 82 30 66 47 0 93 84 46 0 95 50 58 22 31 72 53 59 40 81 28 48 111 74 50 28 41 0 27 0 19 38 52 110 55 59 64 46 22 94 89 54 93 0 38 19 6`
> 2 votes

# Answer
# Japt, ~~186~~ 177 bytes

```
`nqnrvosrpruvtvpopuqsosqppÕÝvr¶uuqnvtnsvpvvptrnmruomvtqvqqrvopmÉæqÛàÑ$vvÔàmpqupqm¡vuqum«rnpopmssqtmvpuqqsmvrrmruoopÌÊprvqÛ$uqunnqr¶uqn¶tmnvpÔnmrrrvsqqsoovquvrqvpmpunvs`®c -#mÃbU

```

Since Japt shares Javascript's 15-digit Pi constraint and shoco, the encoding used by Japt, doesn't encode numbers, some shenanigans are required for compression.

Shortly explained, the beginning is the below string in encoded form:

```
"nqnrvosrpruvtvpopuqsosqppupotvrmouuqnvtnsvpvvptrnmruomvtqvqqrvopmtunsqmsousomuvvusoumpquorpqonntmstvuonqumusrnpouopmssqtmvpuqqsmvrrmruoopntorprvqmunouqunnntqrmouqnmotmnvpuronnmrrrvsqqsoovquvrqvpmpunvs"

```

Which is a string where each letter is `'m' + corresponding digit of pi`. I tested the whole alphabet and that letter gives the best compression by a few bytes.

Backticks tell Japt to decode the string. The rest of it is pretty straightforward:

```
®c -#mÃbU
®          // Given the above string, map each letter
 c         // and return its charcode
   -#m     // minus the charcode of 'm', 109.
      Ã    // When that's done,
        bU // find the index of the implicit input U.

```

Outputs 0-based index of the matching fragment.
Shaved another two bytes off thanks to Oliver.

Try it online!
> 2 votes

# Answer
# JavaScript, ~~197~~ 187

-10: Thanks, Neil!

```
x=>"50ood0hab15bq91k1j9wo6o2iro3by0h94bg3geu0dnnq5tcxz7lk62855h72el61sx7vzsm1thzibtd23br5tr3xu7wsekkpup10cek737o1gcr6t00p3qpccozbq0bfdtfmgk".replace(/.{9}/g,a=>parseInt(a,36)).search(x)+1

```

Takes a series of nine-digit base-36 integers, converts them to base 10, and concatenates them to create the first 200 digits of pi.
> 2 votes

# Answer
# Charcoal, ~~27~~ 15 bytes

```
Ｉ⊖∨⌕Ｉ▷N⟦≕Piφ⟧θχ

```

Try it online! Link is to verbose version of code. Works up to nearly 1000 digits. Explanation:

```
        ≕Pi     Get variable `Pi`
           φ    Predefined variable 1000
     ▷N⟦    ⟧   Evaluate variable to specified precision
    Ｉ           Cast to string
             θ  First input
   ⌕            Find
              χ Predefined variable 10
   ∨             Logical OR
  ⊖              Decrement
 Ｉ               Cast to string
                 Implicitly print

```
> 2 votes

# Answer
First time doing code golf. Use delegates and lambda expressions to reduce the function calls. V2 shorten class name into a single byte.

# \[C#\], ~~361~~ 355 bytes

```
using System;class P{static void Main(){Func<string,int>F=f=>"14159265358979323846264338327950288419716939937510582097494459230781640628620899862803482534211706798214808651328230664709384460955058223172535940812848111745028410270193852110555964462294895493038196".IndexOf(f)+1;Action<int>w=Console.WriteLine;w(F("1"));w(F("65"));w(F("93993"));w(F("3"));}}

```

**Formatted version:**

```
using System;

class P
{
    static void Main()
    {
        Func<string,int>F=f=>"14159265358979323846264338327950288419716939937510582097494459230781640628620899862803482534211706798214808651328230664709384460955058223172535940812848111745028410270193852110555964462294895493038196".IndexOf(f)+1;
        Action<int>w=Console.WriteLine;
        w(F("1"));
        w(F("65"));
        w(F("93993"));
        w(F("3"));
    }
}

```

Ideone!

NB.I miscounted the first version. It was 361 bytes, not 363 bytes.

# \[C#\], tio version 218 bytes

```
f=>"14159265358979323846264338327950288419716939937510582097494459230781640628620899862803482534211706798214808651328230664709384460955058223172535940812848111745028410270193852110555964462294895493038196".IndexOf(f)+1

```

Try it online!
> 2 votes

# Answer
# Ruby, ~~37~~ 35 bytes

```
p"#{BigMath::PI 200}"[3..-3]=~/#$_/

```

Try it online!

Nothing special, just showcasing the built-in library. Output is 0-indexed. The Pi string is formatted as `0.31415...e1`, so we need to strip off the first 3 chars. The `e1` part in the end doesn't really do any harm, but it is stripped off too, as we need to provide a range end (or slice length) value anyway.
> 2 votes

# Answer
# Haskell, 230 bytes

Using laziness to find the number anywhere in the infinite digits of pi, not just in the first 200 digits. Oh yeah, and it returns you every (infinitely many?) instance(s) of the number, not just the first one.

```
p=g(1,0,1,1,3,3)where g(q,r,t,k,n,l)=if 4*q+r-t<n*t then n:g(10*q,10*(r-n*t),t,k,div(10*(3*q+r))t-10*n,l) else g(q*k,(2*q+r)*l,t*l,k+1,div(q*(7*k+2)+r*l)(t*l),l+2)
z n=[(i,take n$drop i p)|i<-[1..]]
f l=[n|(n,m)<-z$length l,m==l]

```

## Examples from the challenge

```
>  take 10 $ f [1]
[1,3,37,40,49,68,94,95,103,110]
>  take 10 $ f [6,5]
[7,108,212,239,378,410,514,672,870,1013]
>  take 1 $ f [9,3,9,9,3]
[42]
>  take 10 $ f [3]
[9,15,17,24,25,27,43,46,64,86]

```

## Credits

'p' is the infinite stream of pi digits, taken from https://rosettacode.org/wiki/Pi#Haskell

```
> take 20 p
[3,1,4,1,5,9,2,6,5,3,5,8,9,7,9,3,2,3,8,4]

```
> 2 votes

# Answer
# Jelly, 24 bytes

```
ȷ*
ȷR×¢:Ḥ‘$ƲU×:¢+¢ʋ/ḤṾḊw

```

Try it online!

~~Use a Machin-like formula, specifically 1/4 pi == tan-1(1/2) + tan-1(1/3).~~

Use the formula pi/2 == 1 + 1/3 × (1 + 2/5 × (1 + 3/7 × (1 + 4/9 × ( ... ))))
> 1 votes

# Answer
# AWK -M , ~~131 119~~ 117 bytes

Uses `-M` flag for arbitrary precision calculations. Added `p=k=0` (5 bytes) to the TIO link to allow multi-line input

```
{CONVFMT="%.999f";PREC=1e3;for(p=k=0;k<1e3;)p+=(4/(8*k+1)-2/(8*k+4)-1/(8*k+5)-1/(8*k+6))/16^k++;$0=$1==3?9:index(p,$1)-2}1

```

Try it online!

**Explanation:**

```
{CONVFMT="%.999f";  # Allows 999 decimal digits to be used when numbers are convert to strings
PREC=1e3;           # Digits of precision to use for calculations
for(;k<1e3;)p+=(4/(8*k+1)-2/(8*k+4)-1/(8*k+5)-1/(8*k+6))/16^k++; # The most concise numerical calculation I could find. It doesn't converge  extremely rapidly, but it seems to work OK
$0=$1==3?9:index(p,$1)-2}  # Replace input line with either 9 or index-2
                           # since indices will either be 1 (meaning 3 was input) or >= 3
1                   # Print the "new" input line

```
> 1 votes

# Answer
## Python 2 ~~239~~ ~~238~~ ~~229~~ 214 bytes

*-9 bytes due to @primo*

```
from bigfloat import*;a=s=n=10**10**5;b=k=0
while a:k+=1;a*=k*(k*(108-72*k)-46)+5;a/=k**3*(640320**3/24);s+=a;b+=k*a
with precision(10**7):print`(426880*sqrt(10005*n)*n)/(13591409*s+545140134*b)`.find(input())-16

```

Uses the Chudnovsky-Ramanujan algorithm to find the first ~~1 million digits~~ 50000 digits of π (change `10**10**5` to `10**10**6` for more, but it takes ages to run) and then searches them for the desired string.
> 1 votes

# Answer
## Javascript 217 bytes (200 hardcoded)

```
a=>"14159265358979323846264338327950288419716939937510582097494459230781640628620899862803482534211706798214808651328230664709384460955058223172535940812848111745028410270193852110555964462294895493038196".search(a)+1

```
> 0 votes

# Answer
### PHP, 27 bytes

Not a very serieus answer, it requires a change in the php.ini settings as pi() defaults to 14 digits, not 200, but for once the PHP solution is fairly elegant:

```
<?=strpos(pi(),$_GET[n])-1;

```
> 0 votes

# Answer
# Julia 0.6, 53 bytes

```
setprecision(9^6)
x->searchindex("$(big(π))","$x",3)

```

Set the precision for BigFloats high enough, then convert `pi` to a string and search. Precision of `9^6` handles 159980 digits.

Try it online!
> 0 votes

# Answer
# J, 25 Bytes

```
{.I.(}.":<.@o.10x^999)E.~

```

Try it online!

0-Indexed

Takes input as a string, +2 Bytes (`":`) if that's not allowed.

Explanation eventually.
> 0 votes

# Answer
## Perl 5 with `-MMath::BigFloat+bpi` and `-n`, 20 bytes

```
bpi($>)=~/.$_/;say@-

```

Try it online!

I'm not sure where usage of `$>` stands, since it's the `EFFECTIVE_USER_ID` which is not portable, but on TIO this is 1000 and satisfies our requirement, for -1 byte vs. `200`.
> 0 votes

# Answer
# Husk, 5 bytes

```
€tİπd

```

Try it online!

```
€        The 1-based index as a substring of
    d    the decimal digits of
         the input
  İπ     in the infinite list of digits of pi
 t       after the radix point.

```
> 0 votes

# Answer
# JavaScript (Node.js) (ES2020), 75 bytes

```
n=>`${eval(`for(a=c=2n*10n**300n,d=1n;a*=d;)c+=a/=d+++d`)}`.search("."+n)+1

```

Try it online!

Uses the formula I've used in another Pi-related challenge. `search("."+n)` is needed to drop the leading `3`. Change `300` to a higher number gives more precision.
> 0 votes

---
Tags: code-golf, pi
---


title: 10 9 8 7 6 5 4 3 2 1... Print 2016

text:
# Question
Title: 10 9 8 7 6 5 4 3 2 1... Print 2016
As a spin-off to my challenge over at Puzzling, your goal is to output `2016`.

Rules:

* You must include the numbers `10 9 8 7 6 5 4 3 2 1` in that order. They can be used as individual integers or concatenated together (like `1098`), but the `10` may not be separated into `1` and `0` \- no character(s) may be present between the digits. Note that, in some languages, `10` may not actually represent the integer literal `10`, which is acceptable.
* Your code must not contain any other numbers or pre-defined number variables or constants (so `T` in Pyth is not allowed, since it is a numeric constant).
* You must **calculate** `2016` using numerics. Simply outputting `2016` without performing any operations on the required numbers (for example, by decoding an encoded string consisting of only alphabetic characters) is not allowed. Outputting `2016` in pieces (such as `20`, then `16`) is also not allowed; you must have a single output consisting of the numeric value `2016`.
* The valid answer with the fewest bytes wins.

# Answer
> 22 votes
# Jelly, ~~17~~ ~~15~~ 14 bytes

```
109876:54+3_21

```

Try it online!

### How it works

```
109876:54+3_21

109876            Initialize the left argument as 109876.
      :54         Perform integer division by 54, yielding 2034.
         +3       Add 3, yielding 2037.
           _21    Subtract 21, yielding 2016.

```

# Answer
> 8 votes
# Hexagony, 61 bytes

Not gonna win, but I just wanted to do a challenge in Hexagony.

This uses a different method than other answers (much worse). It takes some factors of 2016 (2,3,6,7,8) and multiplies them all together.

Minified:

```
\109.8/7}_=\"6<}{>...$_5_4/*!@...../}3.."2\/="*=}<*...$1>"*"/

```

Unminified:

```
    \ 1 0 9 .
   8 / 7 } _ =
  \ " 6 < } { >
 . . . $ _ 5 _ 4
/ * ! @ . . . . .
 / } 3 . . " 2 \
  / = " * = } <
   * . . . $ 1
    > " * " /

```

Explanation coming soon;

# Answer
> 5 votes
# Pyth, 16 bytes

```
+/109876 54-3 21

```

Does integer division, then adds (3-21).

Try it here.

# Answer
> 4 votes
## TI-BASIC, ~~17~~ 15 bytes

```
int(109876/54-√(321

```

This uses @nicael's method.

17 bytes:

```
10+9*8-7+654*3-21

```

This solution from Puzzling can be directly translated into TI-BASIC.

# Answer
> 3 votes
# Japt, ~~17~~ 16 bytes

```
Â(109876/54-321q

```

~~I hate this 17. Probably will find another solution.~~ YAYZ.

Explanation:

* `321q` is a square root of 321.
* `~~` floors the number.

Try it online!

# Answer
> 3 votes
# Matlab / Octave, 23 bytes

```
(10-9+8-7)^(6-5+4)*3*21

```

Try it online

# Answer
> 3 votes
# bc, 14

```
109876/54+3-21

```

Nothing exciting here - borrows from other answers.

# Answer
> 2 votes
## Haskell, 31 bytes

```
[10,9*8*7+const 6 5..]!!4+3*2*1

```

Not the shortest, `10+9*8-7+654*3-21` like seen in other answers works in Haskell too, but something different.

This builds a list starting with `10` and `9*8*7+6 = 510`, so the offset is `500` for the following elements. The whole list is `[10,510,1010,1510,2010,2510 ...]`. We pick the `4th` element (index 0-based), i.e. `2010` and add `3*2*1 = 6`. Voilà.

I use `const 6 5 = 6` to get rid of the `5` which is not needed.

# Answer
> 2 votes
# Python 2, 20 bytes

```
print 109876/54+3-21

```

Again, that same boring `2016.(740)`. Makes use of the fact that if you don't have a decimal number in your expression it returns an integer.

# Answer
> 1 votes
# Polyglot, 17 Bytes

```
10+9*8-7+654*3-21
```

This code, first used in Thomas Kwa's TI-BASIC answer, also works in:

* AppleScript (full program)
* bc (full program)
* Math++ (expression or full program)
* Mathematica (function, therefore not valid)
* Powershell (full program)
* Japt (full program)
* ~~JavaScript (console input, therefore not valid)~~ Needs second verification
* ~~Perl 5 (function, therefore not valid).~~ Needs second verification
* Haskell (function, therefore not valid)
* Python REPL (expression, so REPL environment is needed to get the output)

# Answer
> 1 votes
# Math++, 17 bytes

```
_(109876/54)+3-21

```

Actually, this prints `2016.0`. But there's really no way to print the exact string `2016` in this language.

The 17-byte TI-BASIC solution would also work here.

# Answer
> 1 votes
# BotEngine, ~~42~~ ~~39~~ ~~36~~ 13x2=26

```
v109876543210
>ee   e@  eRP

```

# Answer
> 1 votes
# \>\<\> (fish), 18 bytes

```
10987**r65r4*n;321

```

explaination:

multiplies 9 8 and 7 together to get 504, reverses the stack and reverses it again right before the 4 is added, then multiplies 504 and 4 to get 2016. Then prints the number and ends the program before the last 3 numbers (i could do it after too with no difference, if that matters rules-wise).

# Answer
> 1 votes
# 2, 15 chars / 17 bytes

```
109876/54+3-21⍜

```

`Try it here (Firefox only).`

Translates to `round(109876/54+3-21)`.

*Thanks to @Dennis for saving 2 bytes!*

# Answer
> 1 votes
# Java 7, 31 bytes

```
int c(){return 109876/54+3-21;}

```

Boring port from other answers, of which I believe *@Dennis*' Jelly answer was the first.

# Answer
> 1 votes
# PHP, 27 bytes

```
<?=~~(109876/54+3-21);

```

(22 bytes) was too boring,

so I used 10 to 9 as separate numbers:

```
<?=10*(9-8+7-6),5+4-3+2<<1;

```

other solutions, mostly with small cheats:

```
30: <?=10**(9+8-7-6)/5+4*3+(2<<1);
30: <?=10*trim(9*8,7),6+5+4+3-2*1;
29: <?=10*trim(9*8,76),5*4-3-2+1;
31: <?=10*trim(9*8,765),4+(3*2<<1);
31: <?=10*trim(9*8,765),4*3+(2<<1);
32: <?=ceil(1098*76/54)+321+ord(~j);
33: <?=(10<<9)/876*543/M_PI*2-M_E&~1;

```

# Answer
> 1 votes
# CJam, 15 bytes

```
109876 54/3+21-

```

Another port from Dennis' answer that I suspect works for many stack-based languages except 05AB1E, which seems to be the only stack-based answer besides Forth, which needs several more bytes.

# Answer
> 0 votes
# Milky Way 1.6.5, ~~28~~ 25 bytes

```
10+9*(8)7;^*6*5/4*3/2*A!1

```

---

### Explanation

```
10+9*                      ` perform 10*9 (leaves 90 at TOS)
     (8)7;^*               ` get rid of 8 and multiply the TOS by 7
            6*5/4*3/2*A    ` perform TOS*6/5*4/3*2 (leaves 2016 at TOS)
                       !   ` output the TOS
                        1  ` push 1 to the stack

```

# Answer
> 0 votes
# 05AB1E, 15 bytes

```
109876 54÷3+21-

```

Try it online!

Port of Dennis' answer.

# Answer
> 0 votes
# Forth, 22 bytes

Same calculation seen in other answers.

```
109876 54 / 3 + 21 - .

```

**Try it online**

# Answer
> 0 votes
# C 37 bytes

```
main(){printf("%d",109876/54+3-21);}

```

Same theme as many present.

# Answer
> 0 votes
# VBA, 15 bytes

```
?109876\54+3-21

```

(calculation unashamedly stolen from Dennis)

# Answer
> 0 votes
# JavaScript (ES6), 21 bytes

```
f=

_=>~~(109876/54+3-21)

console.log(f())
```

If the "countdown" went to 0, it could be done in 19 bytes.

```
f=
_=>109876/54+3-21|0
console.log(f())
```

And, seeing as it's 2017 now, that can also be done in 21 bytes:

```
f=
_=>-~(109876/54+3-21)
console.log(f());
```

---
Tags: number, restricted-source, code-golf, expression-building
---


title: Too much lines for me!

text:
# Question
Title: Too much lines for me!
## The problem

You just got a new job, hurray! You expect to be given various interesting tasks, and be able to learn a lot in the next few months. Good news, your boss gave you your first work this morning. You are now in charge of... Writting adresses on envelopes. Yay. Fortunatelly, you are not required to write everything by hand : there is a software for this, in which you can enter the address as plain text.

However, the software is not really well-made and very old. When you opened the files, every information was scared on several lines, and do not fit anymore on the envelope format you were given.

Definitely not wanting to repare this by hand, you decide to write a small programm that will put the data back in the right format for you.

---

## Your task

Distribute the input on the right amount of lines. Each line should have **the same amount of inputs (regardless of their size in characters)** when possible, and if not, the number of line with different lengths should be limited to its minimum. Meaning that the distribution is to be made in terms of `inputs` and not `characters`.

For cases where two solutions are possible (7 inputs on 3 lines for example), the algorithm should maximise the number of inputs in the first lines (starting from the top). There is an example for this very case.

---

## Input format

```
N M
string0
string1
string2
string3
string4
string5
...
string(N-1)

```

Where :

`N` is an `int` and corresponds to the number of fragments in which the data was scattered.

`M` is an `int` and corresponds to the number of lines in which the data should be. You may assume that `M<=N` if necessary.

`string0` ... `string(N-1)` are `string`s that can contain **any *non-control* ASCII character, including spaces** and end with `[space]\n`. You thus **do not need do add spaces between the strings in the output.** You may also assume that there is no horizontal length limit.

**They do not contain any line break except the final one.**

---

## Examples

```
Input            Output

```

```
3 1            string0 string1 string2
string0
string1
string2

```

```
5 3            AA BBB
AA             C DDDDD
BBB            EEEE
C
DDDDD
EEEE
```

```
8 2            AAAAA BBB C DDD
AAAAA          EE FFF GGGG HH
BBB
C
DDD
EE
FFF
GGGG
HH

```

```
8 3           AAA BBB CCC
AAA           DDD EEE FFF
BBB           GGG HHH
CCC
DDD
EEE
FFF
GGG
HHH

```

```
7 3            string0 string1 string2
string0        string3 string4 string5
string1        string6
string2
string3
string4
string5
string6

```

---

## Test cases

```
5 3
This
is
the
first
test case

```

```
8 6
Good Night, Good night!
Parting
is
such sweet
sorrow,
that I shall
say good night
till it be morrow.

```

```
8 3
I
am starting
to
run
out
of
ideas for
test cases.

```

### Expected outputs:

```
This is  //2 strings [This ] and [is ]
the first //2 strings [the ] and [first ]
test case //1 string [test case ]

```

```
Good Night, Good night! Parting //2 strings [Good Night, Good night! ] and [Parting ]
is such sweet //2 strings [is such ] and [sweet ]
sorrow, //1 string [sorrow, ]
that I shall //1 string [that I shall ]
say good night //1 string [say good night ]
till it be morrow. //1 string [till it be morrow. ]

```

```
I am starting to //3 strings
run out of //3 strings
ideas for test cases. //2 strings

```

---

## Rules

Please mark your answer as : **Language - XX bytes**.

It is , so the winner is the answer with the smallest score in bytes.

It would also be very nice if you could provide even briefs explainations, as it is always very enlightning to read this kind of post.

---

# Answer
> 5 votes
# 05AB1E, ~~23~~ 21 bytes

This is my first **05AB1E** program (In fact this is my first golfing using golfing language), so please, if you have any notes, tips or improvements - I would love to get some in the comments section.

**Program:**

```
`rs/î©\õ.gGs«N®%0Qi¶«}}

```

**Explaination:**

```
`rs/î©\õ.gGs«N®%0Qi¶«}}
`                             Push each element of the input to the stack
 r                            Reverse the stack
  s                           Swap the first two values in stack (which are the numbers)
   /                          Division between both numbers in order to get the number of words in each line
    î                         Round up
     ©                        Store that value in the register
      \                       Remove that number from the stack (remove head)
       õ                      Push empty string to pass over the first iteration
        .g                    Push the length of the stack (which is the number of words)
          G            }      Loop from 1 to The length of the stack
           s                  Swap the two words in the head of the stack
            «                 Concatenate
             N                Push counter_variable
              ®               Push the number we saved in the register (number of words per line)
               %              Modulo (To check if we need to concatenate a newline)
                0Q            Equals zero
                  i  }        If true
                   ¶          Push newline
                    «         Concatenate

```

Try it online!

**Saving 2 bytes** with the help of @KevinCruijssen:

```
`rs/îUõ.gGs«NX%_i¶«}}

```

Try it online!

# Answer
> 4 votes
# K (ngn/k), 15 bytes

Anonymous lambda. Takes `N`, `M`, and `strings` as arguments.

```
{,/'(&~y!!x)_z}

```

Try it online!

`{``}` lambda; `x` is `N`, `y` is `M`, `z` is `strings`:

`(``)_z` cut list of strings before the following indices:

`!x` enumerate strings

`y!` division remainder when divided by target number of lines

`~` mask indicating zeros

`&` indices of trues in mask

`,/'` concatenate elements of each list

# Answer
> 4 votes
# APL (dzaima/APL), 18 bytes

Anonymous tacit infix lambda. Takes `N` as right argument and `M` as left argument. Prompts stdin for strings as list of character vectors.

```
{,/⍺⍬⍴⎕,(⍺|-⍵)⍴⊂⍬}

```

Try it online!

`{``}` "dfn"; left and right arguments are  and :

`⊂⍬` enclose the empty list to treat it as a whole

`(``)⍴` cyclically **r**eshape it to the following length:

`-⍵` negate the number of inputs

`⍺|` division remainder when divided by the number of output lines

`⎕,` concatenate that many empty list to the string from stdin

`⍺⍬⍴` reshape to `M` rows and as many columns as needed

`,/` concatenate across

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


title: Find the Fibonacci Kernel

text:
# Question
Title: Find the Fibonacci Kernel
You've probably heard of the Fibonacci numbers; they're pretty famous. Each number in the Fibonacci sequence is the sum of the last two in the sequence with the first and second numbers being 1. The sequence looks like this:

```
1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946 17711 28657 46368 75025 121393 196418 317811 514229 832040 1346269 2178309 3524578 5702887 9227465 14930352 24157817 39088169 63245986 102334155 165580141 267914296 433494437 701408733 1134903170 1836311903 2971215073 4807526976 7778742049 12586269025 20365011074 32951280099 53316291173 86267571272 139583862445 225851433717 365435296162 591286729879 956722026041 1548008755920 2504730781961 4052739537881 6557470319842 10610209857723 17167680177565 27777890035288 44945570212853 72723460248141 117669030460994 190392490709135 308061521170129 498454011879264 806515533049393 1304969544928657 2111485077978050 3416454622906707 5527939700884757 8944394323791464 14472334024676221 23416728348467685 37889062373143906 61305790721611591 99194853094755497 160500643816367088 259695496911122585 420196140727489673 679891637638612258 1100087778366101931 1779979416004714189 2880067194370816120 4660046610375530309 7540113804746346429 12200160415121876738 19740274219868223167 31940434634990099905 51680708854858323072 83621143489848422977 135301852344706746049 218922995834555169026 354224848179261915075 573147844013817084101 927372692193078999176 1500520536206896083277 2427893228399975082453 3928413764606871165730 6356306993006846248183 10284720757613717413913 16641027750620563662096 26925748508234281076009 43566776258854844738105 70492524767089125814114 114059301025943970552219 184551825793033096366333 298611126818977066918552 483162952612010163284885 781774079430987230203437 1264937032042997393488322

```

Similarly, Lucas sequences are the result of substituting the rather arbitrary `1 1` that start the Fibonacci sequence with any two arbitrary integers. Additionally unlike the Fibonacci sequence Lucas sequences also go backwards infinitely. For example `1 1` not only generates all of the numbers in the Fibonacci sequence but all the numbers that would lead up to it:

```
... 13 -8 5 -3 2 -1 1 0 1 1 2 3 5 8 13 ...

```

The Kernel of a Lucas sequence is the closest two consecutive members of the sequence. For example the Kernel of the Fibonacci sequence is `1 1` because they are 0 apart and thus must be the closest two numbers.

The size of the Kernel is measured as the absolute difference between the two members of the Kernel.

Since every pair of numbers is generated by at least one Lucas Sequence, and each sequence has a unique Kernel, for each pair of numbers there is a set of Kernels that generate them. The smallest Lucas Kernel is the smallest Kernel that generates two numbers.

For example take 8 and 21.

Here are a couple of sequences that have both 8 and 21 in them:

```
... 1 1 2 3 5 8 13 21 ...
... 18 -5 13 8 21 29 50 79 ...
... 21 -13 8 -5 3 -2 1 -1 0 -1 -1 ...
... 34 -13 21 8 29 37 68 ...

```

Now if we find the Kernels of each of these sequences we get:

```
1 1
13 8
-1 -1
29 37

```

The smallest Kernels are `1 1` and `-1 -1` (they are tied). We can know this without checking any other sequences because they are of size 0 and it is impossible to find any Kernels smaller than size 0.

## Task

Given two integers determine the smallest Lucas Kernel that generates them.

This is a question so the goal is to write code that performs this task in as few bytes as possible.

Standard input and output formats are accepted and enforced. You must handle negative numbers.

In cases where there are multiple valid solutions you need only output one

## Test Cases

```
8   21 -> 1   1
137 66 -> 66  67
45  80 -> 43  45
-6  45 -> 39  45
37 149 -> 18  19
37  97 -> -2  -3

```

# Answer
# Python 2, 444 391 372 bytes

Crossed out 444 is still regular 444 ;(

Huge thanks to @Dennis for a whopping -52 -71 bytes!

```
k=lambda c,a,b:abs(a+c*a-c*b)-c<abs(b-a)>0and k(c,b-c*a,a+b-c*b)or(a,b)
def f(*t):
 a,b=sorted(t);m=b-a+1,0;g=lambda _:min([k(1,*k(0,*s)),m][_!=b:],key=lambda(x,y):abs(x-y))
 if b<0:x,y=f(-a,-b);return-x,-y
 for c in range(-b,b+1):
    for s in(c,a),(a,c):
     x,y=s
     if min(s)>0:
        while y<b:x,y=y,x+y
        m=g(y)
     x,y=s
     while(x!=b)&((x>b)^(b>0)):x,y=y-x,x
     m=g(x)
 return m

```

Try it online!

The solution can be run by calling `f(a, b)` on the two input integers. It is based on the idea that if both `a` and `b` are within at least one of the same sequence (where `a` and `b` are ordered beforehand such that `a ≤ b`), it follows that there is at least one integer `c` equivalent to an adjacent value of `a` in a shared sequence of `a` and `b` for which the sequence generated by `a` and `c` contains `b` in it.

Furthermore, if at least one of the two integers is positive, all values of `c` must be bounded by `-b ≤ c ≤ b` for it to even be possible to generate the value of `b` on either side of the starting pair. Thus, the solution simply brute-forces values of `c` between `-b` and `b` that in combination with `a` are capable of generating `b` within the sequence, and finds the one for which the difference of the kernel values for `a` and `c` are minimal (this is possible because finding the kernel for two adjacent numbers in a sequence is trivial).

If neither `a` nor `b` is positive, the solution simply negates both and returns the negative of the kernel generated for the negated pair.
> 12 votes

# Answer
# APL (Dyalog Unicode), ~~81~~ 75 bytes

```
⌊{⌽q⊃⍨⊃⍋|-/¨q←⊃,/2,/¨p/⍨B∊¨p←2(+/⍤↑,⊢,¯2-/⍤↑⊢)⍣{∧/B≤|¯2↑1⌽⍵}¨⍺,¨(-,⊢)⍳B←⍵}⌈

```

*-6 bytes thanks to @Adám*

Try it online!

## Explanation

This performs a similar algorithm as @notjagan's answer. For each `C` between `-B` and `B` inclusive, it produces the Lucas sequence containing `A,C` (where `A` and `B` are the minimum and maximum of the two arguments, respectively).

The part where this solution gets interesting is how the Lucas sequences and kernels are computed. Since a Lucas sequence is infinite, we can only generate a finite number of terms. Starting with `A,C`, we add one term to the beginning and one term to the end until the subsequence computed includes (at minimum) all terms with absolute value at most `B` (and thus B, iff the Lucas sequence contains B) and includes the kernel. This occurs if the beginning and end of the subsequence have absolute value at least B and the subsequence has at least 4 terms.

```
⌊{ ... B←⍵}⌈  ⍝ Find ⍺=min(x, y); B=max(x, y):
  (-,⊢)⍳B     ⍝ (-1,-2,-3...-B,1,2,3,..B)
                ⍝ (Don't need 0 since sequence from (A,0) is same as (A,A), which occurs since A≤B)
  ⍺,¨           ⍝ Prepend ⍺ to each to get all possible (A, C) pairs
   ... ¨        ⍝ For each (A, C) pair:
    2(+/⍤↑,⊢,¯2-/⍤↑⊢)     ⍝ Extend the Lucas sequence once in each direction
                          ⍝ (This is the reverse of the normal recurrence, so f(a-1) = f(a) + f(a+1)):
      +/2↑,               ⍝ Sum of the left two,
            ⊢             ⍝ Existing sequence,
              ¯2-/⍤↑⊢     ⍝ Difference of the last two
    ⍣{    ..         }  ⍝ Extend until:
      ∧/B≤|¯2↑1⌽⍵         ⍝ The element with minimum absolute value is not one of the two endpoints
                          ⍝ (At this point, the sequence must contain B if it ever will,
                          ⍝ and it must contain the element with minimum absolute value,
                          ⍝ so the kernel is just pair of elements with minimum absolute difference)
  p/⍨B∊¨p←          ⍝ Filter for those that contain B
  2,/¨              ⍝ Find all consecutive pairs of terms in each sequence
  ⌽q⊃⍨⊃⍋|-/¨q←⊃,/   ⍝ Choose the pair of terms with minimum absolute difference; it must be a kernel

```
> 4 votes

---
Tags: code-golf, number, sequence, fibonacci
---


# Question
Title: Find the Block on the Extended Periodic Table Using the Diagonal Rule
The periodic table gets its shape from the arrangement of elements into blocks:

An element is assigned its block based on what type of orbital holds its valence electron(s). For instance, the sole valence electron of neutral hydrogen occupies the 1s orbital in the 1s subshell, and so hydrogen belongs to the s-block.

The least energetic subshell is the 1s subshell, followed by 2s, 2p, 3s, etc. Electrons fill orbitals in less-energetic subshells first, in accordance with the following chart:

The diagonal arrows give the diagonal rule its name.

When finding the block of an element, there are some important facts to consider:

* Each subsequent element has one more electron than its predecessor.
* Every new type of subshell (s, p, d . . . ) can hold four more electrons than its predecessor as a consequence of the presence of two additional orbitals.
* All subshells (1s, 2s . . . ) have an odd number of orbitals, each of which can hold two electrons. As such, all subshells can hold twice an odd number of electrons.
* Subshells beyond s, p, d and f have names reserved for their eventual observation: after f comes the rest of the alphabet, starting with g and omitting j.

# The Challenge

Given the atomic number of an element, output its block (a letter).

Because one can tell how many electrons are held by theorized, not-yet-observed subshells, input will be less than or equal to 17296 (found with the sum \\$2\sum\_{n=1}^{23}\sum\_{\ell=0}^{n-1}2\left(2\ell+1\right)\\$), the atomic number of the last element with valence electrons in the 46s subshell. Letters beyond z would be needed for elements past that point, and so they will not be included in the challenge. An extended version of the diagonal line chart above can be seen here.

# Rules

* This is so the shortest answer in bytes in each language wins
* For the purpose of this challenge, when s and p are reached a second time after f, they will be capitalized. This means letters are sequenced as follows: `s p d f g h i k l m n o P q r S t u v w x y z`. Additionally, it means output is case-sensitive.
* Assume only valid input is given.
* There is a discrepancy between the periodic table above and the expected output: in reality, lanthanum and actinium (57 and 89) are in the d-block, and lutetium and lawrencium (71 and 103) are in the f-block. The diagonal rule implies that lanthanum and actinium are in the f-block, and that lutetium and lawrencium are in the d-block, and so that is what the program should state.

# Test Cases

```
In: 1
Out: s

In: 5
Out: p

In: 21
Out: d

In: 57
Out: f

In: 2784
Out: l

In: 17296
Out: s

In: 15181
Out: z

In: 12024
Out: q

```

# Answer
# 05AB1E, 46 bytes

```
[N4*Ìˆ¯O·-Ð1‹#U}A3.$„sp©Du‡®ì„ejмÁ¯.sOX<¯O%›Oè

```

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

Try it online or verify all test cases.

**Explanation:**

```
[                    # Start an infinite loop:
 N4*                 #  Multiply the (0-based) loop-index by 4
    Ì                #  Increase it by 2
     ˆ               #  Pop and add this value to the global array
 ¯O                  #  Get the sum of the global array
   ·                 #  Double this sum
    -                #  Subtract it from the current integer,
                     #  which will be the (implicit) input in the first iteration
     Ð               #  Triplicate this new value
      1‹             #  If it's 0 or negative:
        #            #   Stop the infinite loop
      U              #  Pop and store the triplicated value in variable `X`
                     #  (which is 1 by default, which doesn't matter for inputs ≤ 4)
}A                   # After the infinite loop: push the lowercase alphabet
  3.$                # Remove the leading "abc"
     „sp             # Push string "sp"
        ©            # Store it in variable `®` (without popping)
         D           # Duplicate "sp"
          u          # Uppercase the copy: "SP"
           ‡         # Transliterate "s" to "S" and "p" to "P"
            ®ì       # Prepend "sp" from variable `®`
              „ejм   # Remove "e" and "j"
                  Á  # Rotate it once towards the right
                     # (we now have the string "zspdfghiklmnoPqrStuvwxy")
 ¯.s                 # Get a list of suffices of the global array
    O                # Sum each inner suffix
     X<              # Push value `X`, and decrease it by 1
       ¯O%           # Modulo it by the sum of the global array
          ›          # Check for each prefix-sum if it's larger than this value
                     # (1 if truthy; 0 if falsey)
           O         # Get the amount of truthy values by summing
 è                   # And use it to (0-based) index into the string
                     # (after which the resulting character is output implicitly)

```
> 2 votes

# Answer
# Charcoal, 59 bytes

```
Ｎθ⊞υ²Ｗ›θ⊗Συ«≧⁻⊗Συθ⊞υ⁺⁴⌈υ»§”>-◧βYTＢ↷p{ï⭆Σ]¬∕↷›”ＬΦυ‹﹪⊖θΣυΣ✂υκ

```

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

```
Ｎθ

```

Input the atomic number.

```
⊞υ²

```

Start with just an `s`-shell.

```
Ｗ›θ⊗Συ«

```

Repeat while the number of electrons left will fill all the shells twice...

```
≧⁻⊗Συθ

```

... remove those electrons, and...

```
⊞υ⁺⁴⌈υ

```

... add another shell which can hold 4 more electrons than the previous.

```
»§”>-◧βYTＢ↷p{ï⭆Σ]¬∕↷›”ＬΦυ‹﹪⊖θΣυΣ✂υκ

```

Count how many of the remaining shells have no electrons and look that up in the compressed string of block letters. (Because of the way `Sum` works in Charcoal, the calculation is adjusted slightly to avoid a sum of no elements, which ends up offsetting the result by 1, which is compensated by moving the `z` to the beginning of the string where it can be cyclically indexed.)
> 3 votes

# Answer
# , 64 bytes

*-4 for 12024 being q*

```
('spdfghiklmnoPqrStuvwxyz'{~]{~[I.~[:+/\2+4*])&(;2#</.99|i.2#99)

```

Try it online!

### How it works

```
99|i.2#99

```

Create a 99x99 matrix where each row counts up: `0 1 2 3 …`

```
;2#</.

```

Take each diagonal `0;1 0;2 1 0` two times: `0 0 1 0 1 0 2 1 0 2 1 0 …`.

```
[:+/\2+4*]

```

Multiply each number by 4, add 2, add each number left to it: `2 4 10 12 18 20 30 …`

```
[I.~

```

Use this as range boundaries to find the index for the input, e.g. `13`.

```
]{~

```

Get the corresponding shell at that index, e.g. `1`.

```
'spdfghiklmnoPqrStuvwxyz'{~

```

Retrieve the shell name.
> 3 votes

---
Tags: code-golf, chemistry
---


title: Implement a Non-Guessing Sudoku Solver

text:
# Question
Title: Implement a Non-Guessing Sudoku Solver
Implement the shortest Sudoku solver.

**Sudoku Puzzle:**

```
 | 1 2 3 | 4 5 6 | 7 8 9
-+-----------------------
A|   3   |     1 |
B|     6 |       |   5
C| 5     |       | 9 8 3
-+-----------------------
D|   8   |     6 | 3   2
E|       |   5   |
F| 9   3 | 8     |   6
-+-----------------------
G| 7 1 4 |       |     9
H|   2   |       | 8
I|       | 4     |   3

```

**Answer:**

```
 | 1 2 3 | 4 5 6 | 7 8 9
-+-----------------------
A| 8 3 2 | 5 9 1 | 6 7 4
B| 4 9 6 | 3 8 7 | 2 5 1
C| 5 7 1 | 2 6 4 | 9 8 3
-+-----------------------
D| 1 8 5 | 7 4 6 | 3 9 2
E| 2 6 7 | 9 5 3 | 4 1 8
F| 9 4 3 | 8 1 2 | 7 6 5
-+-----------------------
G| 7 1 4 | 6 3 8 | 5 2 9
H| 3 2 9 | 1 7 5 | 8 4 6
I| 6 5 8 | 4 2 9 | 1 3 7

```

**Rules:**

1. Assume all sudokus are solvable by logic only.
2. All input will be 81 characters long. Missing characters will be 0.
3. Output the solution as a single string.
4. The "grid" may be stored internally however you wish.
5. The solution must use a non-guessing solution. (see Sudoku Solver)

**Example I/O:**

```
>sudoku.py "030001000006000050500000983080006302000050000903800060714000009020000800000400030"
832591674496387251571264983185746392267953418943812765714638529329175846658429137

```

# Answer
**RUBY** (449 436 chars)

```
I=*(0..8)
b=$*[0].split('').map{|v|v<'1'?I.map{|d|d+1}:[v.to_i]};f=b.map{|c|!c[1]}
[[z=I.map{|v|v%3+v/3*9},z.map{|v|v*3}],[x=I.map{|v|v*9},I],[I,x]
].map{|s,t|t.map{|i|d=[a=0]*10;s.map{|j|c=b[i+j];c.map{|v|d[v]+=1if !f[i+j]}
v,r=*c;s.map{|k|b[i+k].delete(v)if j!=k}if !r
s[(a+=1)..8].map{|k|s.map{|l|b[i+l]-=c if l!=k&&l!=j}if c.size==2&&c==b[i+k]}}
v=d.index 1;f[i+k=s.find{|j|b[i+j].index v}]=b[i+k]=[v]if v}}while f.index(!1)
p b*''

```

Example:

```
C:\golf>soduku2.rb 030001000006000050500000983080006302000050000903800060714000009020000800000400030
"832591674496387251571264983185746392267953418943812765714638529329175846658429137"

```

quick explanation:
Board `b` is an array of 81 arrays holding all the possible values for each cell. The array on line three holds \[offset,start\_index\] for each group (boxes,rows,columns). Three tasks are performed while iterating through the groups.

1. The value of any cell of size 1 is removed from the rest of the group.
2. If any pair of cells contain the same 2 values, these values are removed from the rest of the group.
3. The count of each value is stored in `d` \- if there is only 1 instance of a value, we set the containing cell to that value, and mark the cell fixed in `f`

Repeat until all cells are fixed.
> 6 votes

# Answer
# Prolog - 493 Characters

```
:-use_module(library(clpfd)).
a(X):-all_distinct(X).
b([],[],[]).
b([A,B,C|X],[D,E,F|Y],[G,H,I|Z]):-a([A,B,C,D,E,F,G,H,I]),b(X,Y,Z).
c([A,B,C,D,E,F,G,H,I|X])-->[[A,B,C,D,E,F,G,H,I]],c(X).
c([])-->[].
l(X,Y):-length(X,Y).
m(X,Y):-maplist(X,Y).
n(L,M):-l(M,L).
o(48,_).
o(I,O):-O is I-48.
:-l(L,81),see(user),m(get,L),seen,maplist(o,L,M),phrase(c(M),R),l(R,9),m(n(9),R),append(R,V),V ins 1..9,m(a,R),transpose(R,X),m(a,X),R=[A,B,C,D,E,F,G,H,I],b(A,B,C),b(D,E,F),b(G,H,I),flatten(R,O),m(write,O).

```

**Output:**

Inputting: `000000000000003085001020000000507000004000100090000000500000073002010000000040009` Outputs: `987654321246173985351928746128537694634892157795461832519286473472319568863745219`

Inputting: `030001000006000050500000983080006302000050000903800060714000009020000800000400030` Outputs: `832591674496387251571264983185746392267953418943812765714638529329175846658429137`
> 3 votes

# Answer
# PowerShell, ~~491~~ ~~490~~ ~~488~~ ~~465~~ 463 bytes

```
$w=,0*81;$c=,(1..9)*81
$a=(24,24,6)*3|%{,(0..8|%{($r++)});,(0..8|%{$v%81;$v+=9});$v++;,((1,1,7)*3|%{+$q;$q+=$_});$q-=$_}
filter g($v,$i){if($v){$a|?{$i-in$_}|%{$_|%{$c[$_]=$c[$_]-ne$v}};$w[$i]=$v;$c[$i]=@()}}
$args|% t*y|%{g($_-48)($i++)}
for(;$a|%{($b=$_)|?{($v=$c[$_])}|?{(($c[$b]|%{"$_"})-eq$v).Count-eq$v.Count
$c[$b]|%{$_}|group|? C* -eq 1|? N* -in $v|%{$v=+$_.Name;1}}|%{$b|?{"$v"-ne$c[$_]}|%{$c[$_]=@($c[$_]|?{$_-notin$v})}
g($v[0]*!$v[1])$_
1}}){}
-join$w

```

Try it online!

Implemented Solving methods: Single, Naked Pair, Naked Trio, Naked Quad and Hidden Single.

See Terms related to solving

See also the code with debug output.
> 3 votes

# Answer
# Perl 5, 295 bytes

```
sub P{$r=$p/9;$c=$p%9;$q=3*~~($r/3)+$c/3}sub N{($i,$u)=@_;P;$G[$p]=$u*$i;$R[$r]{$i}=$C[$c]{$i}=$Q[$q]{$i}=$u}sub S{if($p>80){print@G;exit}if($G[$p]){S(++$p);$p--}else{N($_,1),S(++$p),$p--,N($_)for grep{P;$R[$r]{$_}+$C[$c]{$_}+$Q[$q]{$_}<1}1..9}}@G=split'',$ARGV[0];N($G[$p=$_],1)for 0..80;$p=0;S

```

Try it online!

Shortened from 339 to 317 to 315 to 314 to 310 to 309 to 298 to 295
> 3 votes

---
Tags: code-golf, game, puzzle-solver, sudoku
---