title: Dirichlet Convolution

text:
# Question
Title: Dirichlet Convolution
The *Dirichlet convolution* is a special kind of *convolution* that appears as a very useful tool in number theory. It operates on the set of *arithmetic functions*.

### Challenge

Given two arithmetic functions \\$f,g\\$ (i.e. functions \\$f,g: \mathbb N \to \mathbb R\\$) compute the *Dirichlet convolution* \\$(f * g): \mathbb N \to \mathbb R\\$ as defined below.

### Details

* We use the convention \\$ 0 \notin \mathbb N = \\{1,2,3,\ldots \\}\\$.
* The Dirichlet convolution \\$f\*g\\$ of two arithmetic functions \\$f,g\\$ is again an arithmetic function, and it is defined as $$(f * g)(n) = \sum\_\limits{d|n} f\left(\frac{n}{d}\right)\cdot g(d) = \sum\_{i\cdot j = n} f(i)\cdot g(j).$$ (Both sums are equivalent. The expression \\$d|n\\$ means \\$d \in \mathbb N\\$ divides \\$n\\$, therefore the summation is over the natural *divisors* of \\$n\\$. Similarly we can subsitute \\$ i = \frac{n}{d} \in \mathbb N, j =d \in \mathbb N \\$ and we get the second equivalent formulation. If you're not used to this notation there is a step by step example at below.) Just to elaborate (this is not directly relevant for this challenge): The definition comes from computing the product of Dirichlet series: $$\left(\sum\_{n\in\mathbb N}\frac{f(n)}{n^s}\right)\cdot \left(\sum\_{n\in\mathbb N}\frac{g(n)}{n^s}\right) = \sum\_{n\in\mathbb N}\frac{(f * g)(n)}{n^s}$$
* The input is given as two black box functions. Alternatively, you could also use an infinite list, a generator, a stream or something similar that could produce an unlimited number of values.
* There are two output methods: Either a function \\$f\*g\\$ is returned, or alternatively you can take take an additional input \\$n \in \mathbb N\\$ and return \\$(f\*g)(n)\\$ directly.
* For simplicity you can assume that every element of \\$ \mathbb N\\$ can be represented with e.g. a positive 32-bit int.
* For simplicity you can also assume that every entry \\$ \mathbb R \\$ can be represented by e.g. a single real floating point number.

### Examples

Let us first define a few functions. Note that the list of numbers below each definition represents the first few values of that function.

* the multiplicative identity (A000007) $$\epsilon(n) = \begin{cases}1 & n=1 \\ 0 & n\>1 \end{cases}$$ `1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, ...`
* the constant unit function (A000012)$$ \mathbb 1(n) = 1 \\: \forall n $$ `1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, ...`
* the identity function (A000027) $$ id(n) = n \\: \forall n $$ `1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, ...`
* the Möbius function (A008683) $$ \mu(n) = \begin{cases} (-1)^k & \text{ if } n \text{ is squarefree and } k \text{ is the number of Primefactors of } n \\ 0 & \text{ otherwise } \end{cases} $$ `1, -1, -1, 0, -1, 1, -1, 0, 0, 1, -1, 0, -1, 1, 1, 0, -1, 0, -1, ...`
* the Euler totient function (A000010) $$ \varphi(n) = n\prod\_{p|n} \left( 1 - \frac{1}{p}\right) $$ `1, 1, 2, 2, 4, 2, 6, 4, 6, 4, 10, 4, 12, 6, 8, 8, 16, 6, 18, 8, ...`
* the Liouville function (A008836) $$ \lambda (n) = (-1)^k $$ where \\$k\\$ is the number of prime factors of \\$n\\$ counted with multiplicity `1, -1, -1, 1, -1, 1, -1, -1, 1, 1, -1, -1, -1, 1, 1, 1, -1, -1, -1, ...`
* the divisor sum function (A000203) $$\sigma(n) = \sum\_{d | n} d $$ `1, 3, 4, 7, 6, 12, 8, 15, 13, 18, 12, 28, 14, 24, 24, 31, 18, 39, 20, ...`
* the divisor counting function (A000005) $$\tau(n) = \sum\_{d | n} 1 $$ `1, 2, 2, 3, 2, 4, 2, 4, 3, 4, 2, 6, 2, 4, 4, 5, 2, 6, 2, 6, 4, 4, 2, 8, ...`
* the characteristic function of square numbers (A010052) $$sq(n) = \begin{cases} 1 & \text{ if } n \text{ is a square number} \\ 0 & \text{otherwise}\end{cases}$$ `1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, ...`

Then we have following examples:

* \\$ \epsilon = \mathbb 1 * \mu \\$
* \\$ f = \epsilon * f \\: \forall f \\$
* \\$ \epsilon = \lambda * \vert \mu \vert \\$
* \\$ \sigma = \varphi * \tau \\$
* \\$ id = \sigma * \mu\\$ and \\$ \sigma = id * \mathbb 1\\$
* \\$ sq = \lambda * \mathbb 1 \\$ and \\$ \lambda = \mu * sq\\$
* \\$ \tau = \mathbb 1 * \mathbb 1\\$ and \\$ \mathbb 1 = \tau * \mu \\$
* \\$ id = \varphi * \mathbb 1 \\$ and \\$ \varphi = id * \mu \\$

The last for are a consequence of the Möbius inversion: For any \\$f,g\\$ the equation \\$ g = f * 1\\$ is equivalent to \\$f = g * \mu \\$.

### Step by Step Example

This is an example that is computed step by step for those not familiar with the notation used in the definition. Consider the functions \\$f = \mu\\$ and \\$g = \sigma\\$. We will now evaluate their convolution \\$\mu * \sigma\\$ at \\$ n=12\\$. Their first few terms are listed in the table below.

$$\begin{array}{c|ccccccccccccc} f & f(1) & f(2) & f(3) & f(4) & f(5) & f(6) & f(7) & f(8) & f(9) & f(10) & f(11) & f(12) \\ \hline \mu & 1 & -1 & -1 & 0 & -1 & 1 & -1 & 0 & 0 & 1 & -1 & 0 \\ \sigma & 1 & 3 & 4 & 7 & 6 & 12 & 8 & 15 & 13 & 18 & 12 & 28 \\ \end{array}$$

The sum iterates over all natural numbers \\$ d \in \mathbb N\\$ that divide \\$n=12\\$, thus \\$d\\$ assumes all the natural divisors of \\$n=12 = 2^2\cdot 3\\$. These are \\$d =1,2,3,4,6,12\\$. In each summand, we evaluate \\$g= \sigma\\$ at \\$d\\$ and multiply it with \\$f = \mu\\$ evaluated at \\$\frac{n}{d}\\$. Now we can conclude

$$\begin{array}{rlccccc} (\mu * \sigma)(12) &= \mu(12)\sigma(1) &+\mu(6)\sigma(2) &+\mu(4)\sigma(3) &+\mu(3)\sigma(4) &+\mu(2)\sigma(6) &+\mu(1)\sigma(12) \\ &= 0\cdot 1 &+ 1\cdot 3 &+ 0 \cdot 4 &+ (-1)\cdot 7 &+ (-1) \cdot 12 &+ 1 \cdot 28 \\ &= 0 & + 3 & 1 0 & -7 & - 12 & + 28 \\ &= 12 \\ & = id(12) \end{array}$$

# Answer
> 5 votes
# Lean, ~~108~~ ~~100~~ ~~95~~ ~~78~~ 75 bytes

```
def d(f g:_->int)(n):=(list.iota n).foldr(λd s,ite(n%d=0)(s+f d*g(n/d))s)0

```

Try it online!

More testcases with all of the functions.

# Answer
> 4 votes
# Haskell, 46 bytes

```
(f!g)n=sum[f i*g(div n i)|i<-[1..n],mod n i<1]

```

Try it online!

Thanks to flawr for -6 bytes and a great challenge! And thanks to H.PWiz for another -6!

# Answer
> 3 votes
# Wolfram Language (Mathematica), 17 bytes

Of course Mathematica has a built-in. It also happens to know many of the example functions. I've included some working examples.

```
DirichletConvolve

```

Try it online!

# Answer
> 2 votes
# Python 3, 59 bytes

```
lambda f,g,n:sum(f(d)*g(n//d)for d in range(1,n+1)if 1>n%d)

```

Try it online!

# Answer
> 2 votes
# Add++, 51 bytes

```
D,g,@~,$z€¦~¦*
D,f,@@@,@b[VdF#B]dbRzGb]$dbL$@*z€g¦+

```

Try it online!

Takes two pre-defined functions as arguments, plus \\$n\\$, and outputs \\$(f * g)(n)\\$

## How it works

```
D,g,		; Define a helper function, $g
	@~,	; $g takes a single argument, an array, and splats that array to the stack
		; $g takes the argument e.g. [[τ(x) φ(x)] [3 4]]
		; STACK : 			[[τ(x) φ(x)] [3 4]]
	$z	; Swap and zip:			[[3 τ(x)] [4 φ(x)]]
	€¦~	; Reduce each by execution:	[[τ(3) φ(4)]]
	¦*	; Take the product and return:	τ(3)⋅φ(4) = 4

D,f,		; Define the main function, $f
	@@@,	; $f takes three arguments: φ(x), τ(x) and n (Let n = 12)
		; STACK:			[φ(x) τ(x) 12]
	@	; Reverse the stack:		[12 τ(x) φ(x)]
	b[V	; Pair and save:		[12]			Saved: [τ(x) φ(x)]
	dF#B]	; List of factors:		[[1 2 3 4 6 12]]
	dbR	; Copy and reverse:		[[1 2 3 4 6 12] [12 6 4 3 2 1]]
	z	; Zip together:			[[[1 12] [2 6] [3 4] [4 3] [6 2] [12 1]]]
	Gb]	; Push Saved:			[[[1 12] [2 6] [3 4] [4 3] [6 2] [12 1]] [[τ(x) φ(x)]]]
	$dbL	; Number of dividors:		[[[τ(x) φ(x)]] [[1 12] [2 6] [3 4] [4 3] [6 2] [12 1]] 6]
	$@*	; Repeat:			[[[1 12] [2 6] [3 4] [4 3] [6 2] [12 1]] [[τ(x) φ(x)] [τ(x) φ(x)] [τ(x) φ(x)] [τ(x) φ(x)] [τ(x) φ(x)] [τ(x) φ(x)]]]
	z	; Zip:				[[[τ(x) φ(x)] [1 12]] [[τ(x) φ(x)] [2 6]] [[τ(x) φ(x)] [3 4]] [[τ(x) φ(x)] [4 3]] [[τ(x) φ(x)] [6 2]] [[τ(x) φ(x)] [12 1]]]
	€g	; Run $g over each subarray:	[[4 4 4 6 4 6]]
	¦+	; Take the sum and return:	28

```

# Answer
> 2 votes
# , 58 bytes

```
function(n,f,g){for(i in (1:n)[!n%%1:n])F=F+f(i)*g(n/i)
F}

```

Try it online!

Takes `n`, `f`, and `g`. Luckily the `numbers` package has quite a few of the functions implemented already.

If vectorized versions were available, which is possible by wrapping each with `Vectorize`, then the following 45 byte version is possible:

# , 45 bytes

```
function(n,f,g,x=1:n,i=x[!n%%x])f(i)%*%g(n/i)

```

Try it online!

# Answer
> 2 votes
# APL (Dyalog Classic), 20 bytes

```
{(⍺⍺¨∘⌽+.×⍵⍵¨)∪⍵∨⍳⍵}

```

with `⎕IO←1`

Try it online!

Easy to solve, hard to test - generally not my type of challenge. Yet, I enjoyed this one very much!

`{` `}` defines a dyadic operator whose operands `⍺⍺` and `⍵⍵` are the two functions being convolved;  is the numeric argument

`∪⍵∨⍳⍵` are the divisors of  in ascending order, i.e. unique () of the LCMs () of  with all natural numbers up to it ()

`⍵⍵¨` apply the right operand to each

`⍺⍺¨∘⌽` apply the left operand to each in reverse

`+.×` inner product - multiply corresponding elements and sum

---

The same in ngn/apl looks better because of Unicode identifiers, but takes 2 additional bytes because of 1-indexing.

# Answer
> 1 votes
# Jelly, 9 bytes

```
ÆDṚÇ€ḋÑ€Ʋ

```

Try it online!

Line at the top is the main line of \\$f\\$, line at the bottom is the main line of \\$g\\$. \\$n\\$ is passed as an argument to this function.

# Answer
> 1 votes
# Swift 4,  ~~74 70~~  54 bytes

```
{n in(1...n).map{n%$0<1 ?f(n/$0)*g($0):0}.reduce(0,+)}

```

Try it online!

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

Takes input as `(f)(g)(n)`.

```
f=>g=>h=(n,d=n)=>d&&!(n%d)*f(n/d)*g(d)+h(n,d-1)

```

Try it online!

### Examples

```
liouville =
n => (-1) ** (D = (n, k = 2) => k > n ? 0 : (n % k ? D(n, k + 1) : 1 + D(n / k, k)))(n)

mobius =
n => (M = (n, k = 1) => n % ++k ? k > n || M(n, k) : n / k % k && -M(n / k, k))(n)

sq =
n => +!((n ** 0.5) % 1)

identity =
n => 1

// sq = liouville * identity
console.log([...Array(25)].map((_, n) => F(liouville)(identity)(n + 1)))

// liouville = mobius * sq
console.log([...Array(20)].map((_, n) => F(mobius)(sq)(n + 1)))

```

# Answer
> 1 votes
# C (gcc), 108 bytes

```
#define F float
F c(F(*f)(int),F(*g)(int),int n){F s=0;for(int d=0;d++<n;)if(n%d<1)s+=f(n/d)*g(d);return s;}

```

Straightforward implementation, shamelessly stolen from Leaky Nun's Python answer.

Ungolfed:

```
float c(float (*f)(int), float (*g)(int), int n) {
    float s = 0;
    for(int d = 1; d <= n;++d) {
        if(n % d == 0) {
            s += f(n / d) * g(d);
        }
    }
    return s;
}

```

Try it online!

# Answer
> 1 votes
## F#, 72 bytes

```
let x f g n=Seq.filter(fun d->n%d=0){1..n}|>Seq.sumBy(fun d->f(n/d)*g d)

```

Takes the two functions `f` and `g` and a natural number `n`. Filters out the values of `d` that do not naturally divide into `n`. Then evaluates `f(n/d)` and `g(d)`, multiples them together, and sums the results.

# Answer
> 0 votes
# Pari/GP, 32 bytes

```
(f,g,n)->sumdiv(n,d,f(n/d)*g(d))

```

Try it online!

There is a built-in `dirmul` function, but it only supports *finite* sequences.

# Answer
> 0 votes
# APL(NARS), 47 chars, 94 bytes

```
{(m⍵[1])×n⍵[2]}{+/⍺⍺¨{k←⍳⍵⋄(⍵÷b),¨b←k/⍨0=k∣⍵}⍵}

```

where m and n are the function one has to use (this because i don't know how to call one array of function in one function in APL). Using the example above the multiplication of Mobius function (here it is 12π) and sum of divisors function (here it is 11π) for value 12 that multiplication would be:

```
  {(12π⍵[1])×11π⍵[2]}{+/⍺⍺¨{k←⍳⍵⋄(⍵÷b),¨b←k/⍨0=k∣⍵}⍵}12
12

```

if one has to calculate some other value:

```
  {(12π⍵[1])×11π⍵[2]}{+/⍺⍺¨{k←⍳⍵⋄(⍵÷b),¨b←k/⍨0=k∣⍵}⍵}1002
1002
  {(12π⍵[1])×11π⍵[2]}{+/⍺⍺¨{k←⍳⍵⋄(⍵÷b),¨b←k/⍨0=k∣⍵}⍵}1001
1001
  {(12π⍵[1])×11π⍵[2]}{+/⍺⍺¨{k←⍳⍵⋄(⍵÷b),¨b←k/⍨0=k∣⍵}⍵}20000x
20000

```

One can see if for example the first 2000 number the function result is the identity

```
  (⍳2000)≡{(12π⍵[1])×11π⍵[2]}{+/⍺⍺¨{k←⍳⍵⋄(⍵÷b),¨b←k/⍨0=k∣⍵}⍵}¨⍳2000
1

```

---
Tags: code-golf, math, arithmetic, number-theory, functional-programming
---


title: Two steps forward and one step back

text:
# Question
Title: Two steps forward and one step back
Let's say I'm ten steps away from my destination. I walk there following the old saying, "Two steps forward and one step back". I take two steps forward, one back, until I'm standing exactly on my destination. (This might involve stepping past my destination, and returning to it). How many steps did I walk?

Of course, I might not be 10 steps away. I might be 11 steps away, or 100. I could measure ten paces, and keep walking back and forth to solve the problem, or... I could write some code!

* Write a function to work out how many steps it takes to get N steps away, in the sequence: two steps forward, one step back.
* Assume you've started at step 0. Count the "two steps forward" as two steps, not one.
* Assume all steps are a uniform length.
* It should return the number of steps first taken when you reach that space. (For instance, 10 steps away takes 26 steps, but you'd hit it again at step 30). We're interested in the 26.
* Use any language you like.
* It should accept any positive integer as input. This represents the target step.
* Smallest number of bytes win.

Example:

I want to get 5 steps away:

```
| | | | | | <- I'm at step 0, not yet on the grid.
| |X| | | | <- I take two steps forward, I'm on step 2: the count is 2
|X| | | | | <- I take one step back, I'm on step 1: the count is 3
| | |X| | | <- I take two steps forward, I'm on step 3: the count is 5
| |X| | | | <- I take one step back, I'm on step 2 again: the count is 6
| | | |X| | <- I take two steps forward, I'm on step 4: the count is 8
| | |X| | | <- I take one step back, I'm on step 3 again: the count is 9
| | | | |X| <- I take two steps forward, I'm on step 5: the count is 11

```

In this case, the result of the function would be 11.

Example results:

```
1      =>  3
5      =>  11
9      =>  23
10     =>  26
11     =>  29
100    =>  296
1000   =>  2996
10000  =>  29996
100000 =>  299996

```

Have fun, golfers!

# Answer
# Oasis, ~~5~~ 4 bytes

*1 byte saved thanks to @Adnan*

```
3+23

```

*Not to be confused with `23+3`*

Try it online!

**How?**

```
      implicitly push a(n-1)
3     push 3
 +    sum and implicitly print
  2   a(2) = 2
   3  a(1) = 3

```
> 5 votes

# Answer
# Python 2, 18 bytes

```
lambda n:3*n-1%n*4

```

Try it online.

I picked this trick up from xnor just a few days ago…!
> 12 votes

# Answer
# Python 2, 20 bytes

```
lambda n:n*3-4*(n>1)

```

Try it online!
> 11 votes

# Answer
# Python 2, 17 bytes

```
lambda n:n-3%~n*2

```

Try it online!

I found the expression by brute-force search. It effectively computes `n+2*abs(n-2)`.
> 10 votes

# Answer
# Polyglot: Java 8 / JavaScript / C# .NET, ~~16~~ ~~14~~ 12 bytes

```
n->3*n-1%n*4

```

Try it online (Java 8).

```
n=>3*n-1%n*4

```

Try it online (JavaScript).
Try it online (C# .NET).

Port of *@Lynn*'s Python 2 answer, so make sure to upvote his/her answer.

---

***Old answer:***

# Polyglot: Java 8 / JavaScript / C# .NET, ~~16~~ 14 bytes

```
n->n<2?3:n*3-4

```

Try it online (Java 8).

```
n=>n<2?3:n*3-4

```

Try it online (JavaScript).
Try it online (C# .NET).

**Explanation:**

```
n->       // Method with integer as both parameter and return-type
  n<2?    //  If the input is 1:
   3      //   Return 3
  :       //  Else:
   n*3-4  //   Return the input multiplied by 3, and subtract 4

```
> 9 votes

# Answer
# 05AB1E, ~~8~~ 7 bytes

```
3*s≠i4-

```

Try it online!

-1 byte thanks to Emigna !
> 7 votes

# Answer
# , 20 bytes

```
N=scan();3*N-4*(N>1)

```

Try it online!

Didn't notice the pattern until after I had implemented my less elegant solution.
> 7 votes

# Answer
# Oasis, 5 bytes

```
¹y4-3

```

Explanation:

```
    3  defines f(1) = 3
¹y4-   defines f(n) as:
¹      push input
 y     triple
  4-   subtract four

```

Try it online!
> 6 votes

# Answer
# Haskell, 15 bytes

```
f 1=3
f n=3*n-4

```

Try it online!
> 5 votes

# Answer
# Standard ML, 16 bytes

```
fn 1=>3|n=>3*n-4

```

Try it online!
> 5 votes

# Answer
# Dodos, 27 bytes

```
	dot D
D

	d d
	d d
d
	dip

```

Try it online!
> 5 votes

# Answer
# Jelly, 6 bytes

```
++_>¡4

```

Try it online!
> 4 votes

# Answer
# APL (Dyalog), 9 bytes

```
3∘×-4×1∘<

```

Try it online!
> 4 votes

# Answer
# Prolog (SWI), 21 bytes

```
1*3.
X*Y:-Y is 3*X-4.

```

Try it online!
> 4 votes

# Answer
# MATL, 7 bytes

Uses the `3*n-4*(n>1)` formula. Multiply input by 3 (`3*`), push input again (`G`) and decrement it (`q`). If the result is not zero (`?`) then subtract 4 from the result (`4-`).

```
3*Gq?4-

```

Try it online!
> 4 votes

# Answer
# Jelly, 4 bytes

```
ạ2Ḥ+

```

Try it online!

### How it works

```
ạ2Ḥ+  Main link. Argument: n

ạ2    Absolute difference with 2; yield |n-2|.
  Ḥ   Unhalve/double; yield 2|n-2|.
   +  Add; yield 2|n-2|+n.

```
> 4 votes

# Answer
# \>\<\>, ~~10~~ 9 bytes

Saved 1 byte thanks to *Jo King*

```
3*:3)4*-n

```

Try it online!
> 3 votes

# Answer
# C (gcc), 20 bytes

```
f(n){n=3*n-4*!!~-n;}

```

Try it online!
> 3 votes

# Answer
# MachineCode on x86\_64, ~~34~~ ~~32~~ 24 bytes

```
8d47fe9931d029d08d0447c3

```

Requires the `i` flag for integer output; input is taken via manually appending to the code.

Try it online!

---

I went through these 4 different C functions to find the 24-byte MachineCode program:

* `n+2*abs(n-2)` = `8d47fe9931d029d08d0447c3` (24 bytes)
* `3*n-4*!!~-n` = `8d047f31d2ffcf0f95c2c1e20229d0c3` (32 bytes)
* `n*3-4*(n>1)` = `31d283ff028d047f0f9dc2c1e20229d0c3` (34 bytes)
* `n<2?3:n*3-4` = `83ff01b8030000007e068d047f83e804c3` (34 bytes)
> 3 votes

# Answer
# , 54 bytes

```
3.6010160303604047002020003100000180010202046000095024

```

Try it online!

If you question the input method, please visit first the numerical input and output may be given as a character code meta post.
> 2 votes

# Answer
# Japt, 7 bytes

A port of Lynn's Python solution.

```
*3É%U*4

```

Try it

---

## Alternative

This was a fun alternative to the closed formula solutions that is, unfortunately, a byte longer:

```
_+3}gN³²

```

Try it
> 2 votes

# Answer
# TI-Basic, 8 bytes

```
3Ans-4(Ans>1

```
> 2 votes

# Answer
# 05AB1E, 4 bytes

Uses the abs-method from Dennis' Jelly answer

```
2α·+

```

Try it online!

**Explanation**

```
2α      # abs(input, 2)
  ·     # multiply by 2
   +    # add input

```
> 2 votes

# Answer
# 65816 machine code, 22 bytes

I could have made this 65C02 machine code easily for 3 bytes less, but didn't, since the register size on the 65C02 is 8-bit instead of 16-bit. It would work, but it's boring because you can only use really low numbers ;-)

xxd dump:

```
00000000: 7aa9 0000 aa89 0100 d004 8888 e824 c8e8  z............$..
00000010: 1ac0 0000 d0ef                           ......

```

disassembly / code explanation:

```
; target is on the stack
  ply              7A                  ; pull target from stack
  lda #$0000       A9 00 00            ; set loop counter to 0
  tax              AA                  ; set step counter to 0
loop:
  bit #$0001       89 01 00            ; sets Z if loop counter is even
  bne odd          D0 04               ; if Z is not set, jump to 'odd'
  dey              88                  ; decrement target twice
  dey              88
  inx              E8                  ; increment step counter
  .byte $24        24                  ; BIT $xx opcode, effectively skips the next byte
odd:
  iny              C8                  ; increment target

  inx              E8                  ; increment step counter
  inc a            1A                  ; increment loop counter

  cpy #$0000       C0 00 00            ; sets zero flag, can be optimized maybe?
  bne loop         D0 EF               ; if Y is non-zero, loop

; result is in register X

```

Testing it out on a 65816-compatible emulator:
> 2 votes

# Answer
# Python 3, 48 bytes

```
def a(x):
    if x!=1:
        return((3*x)-4)
    return(3)

```

Try It Online!
> 1 votes

# Answer
**SHELL** , **28 Bytes**

```
F(){ bc<<<$1*3-$(($1>1))*4;}

```

Tests :

```
F 1
3

F 2
2

F 3
5

F 4
8

F5
11

F 11
29

F 100
296

F 100000
299996

```

Explanation :

The formula is :

```
if n == 1  ==> F(1) = 3
else F(n) = 3*n - 4

```

following the sequence of 3 steps "Two steps forward and one step back", we will have the arithmetic series :

```
 +2  2 => 2  ( or 6 )
 -1  1 => 3
 -----------
 +2  3 => 5  ( or 9 )
 -1  2 => 6
 -----------
 +2  4 => 8  ( or 12 )
 -1  3 => 9
 -----------
 +2  5 => 11 ( or 15 )
 -1  4 => 12
 -----------
 +2  6 => 14 ( or 18 )
 -1  5 => 15
 -----------
 +2  7 => 17 ( or 21 )
 -1  6 => 18

```

At the minimum, or first coincidence :

```
 1 => 3
 2 => 2
 3 => 5
 4 => 8
 5 => 11
 6 => 14

```

in one formula :

```
F(n) = 3*n - 4(n>1)     with n>1 is 1 or 0 (if n==1)

```
> 1 votes

# Answer
# , 9 bytes

```
3&*-4*1&<

```

Try it online!
> 1 votes

# Answer
# MATLAB/Octave, 15 bytes

```
@(n)3*n-4*(n>1)

```

Try it online!

Kind of surprised there isn't already a MATLAB answer. Same algorithm of `3*n-4` if greater than 1, or `3*n` otherwise.
> 1 votes

# Answer
# Brain-Flak, 38 bytes

```
({<([()()]{})>()(){(<((){})>)()}{}}{})

```

Try it online!

The first answer I see to calculate the answer by stepping back and forth.

```
({ while not at 0
  <([()()]{})>()() take two steps forward, counting 2 steps
  {(<((){})>)()}{} take one step back, if not at 0, and add 1 step
}{}) remove the 0 and push step sum

```
> 1 votes

# Answer
## `d`, 7 bytes

```
♦óÖ╣░Θ$

```

## Explanation

```
3*1a<4*-

```

Evaluates `(a*3)-4*(a>1)`.

## Another possible alternative

```
3*1am4*-

```

Evaluates `(a*3)-4*(1%a)`.
> 1 votes

# Answer
# Ruby, 14 bytes

```
->n{3*n-1%n*4}

```

Try it online!

Uses the `1%1==0` trick as seen in other answers here.
> 0 votes

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


# Question
Title: From text to ascii art from CodinGame practice puzzle
On CodingGame, there is a Puzzle that ask to write words with ascii art. I solve the puzzle then tried to golf it. What improvement can I do on it?

```
INPUT
>>> 20
>>> 11
>>> MANHATTAN
>>>   .----------------.  .----------------.  .----------------.  .----------------.  .----------------.  .----------------.  .----------------.  .----------------.  .----------------.  .----------------.  .----------------.  .----------------.  .----------------.  .-----------------. .----------------.  .----------------.  .----------------.  .----------------.  .----------------.  .----------------.  .----------------.  .----------------.  .----------------.  .----------------.  .----------------.  .----------------.  .----------------.
>>> | .--------------. || .--------------. || .--------------. || .--------------. || .--------------. || .--------------. || .--------------. || .--------------. || .--------------. || .--------------. || .--------------. || .--------------. || .--------------. || .--------------. || .--------------. || .--------------. || .--------------. || .--------------. || .--------------. || .--------------. || .--------------. || .--------------. || .--------------. || .--------------. || .--------------. || .--------------. || .--------------. |
>>> | |      __      | || |   ______     | || |     ______   | || |  ________    | || |  _________   | || |  _________   | || |    ______    | || |  ____  ____  | || |     _____    | || |     _____    | || |  ___  ____   | || |   _____      | || | ____    ____ | || | ____  _____  | || |     ____     | || |   ______     | || |    ___       | || |  _______     | || |    _______   | || |  _________   | || | _____  _____ | || | ____   ____  | || | _____  _____ | || |  ____  ____  | || |  ____  ____  | || |   ________   | || |    ______    | |
>>> | |     /  \     | || |  |_   _ \    | || |   .' ___  |  | || | |_   ___ `.  | || | |_   ___  |  | || | |_   ___  |  | || |  .' ___  |   | || | |_   ||   _| | || |    |_   _|   | || |    |_   _|   | || | |_  ||_  _|  | || |  |_   _|     | || ||_   \  /   _|| || ||_   \|_   _| | || |   .'    `.   | || |  |_   __ \   | || |  .'   '.     | || | |_   __ \    | || |   /  ___  |  | || | |  _   _  |  | || ||_   _||_   _|| || ||_  _| |_  _| | || ||_   _||_   _|| || | |_  _||_  _| | || | |_  _||_  _| | || |  |  __   _|  | || |   / _ __ `.  | |
>>> | |    / /\ \    | || |    | |_) |   | || |  / .'   \_|  | || |   | |   `. \ | || |   | |_  \_|  | || |   | |_  \_|  | || | / .'   \_|   | || |   | |__| |   | || |      | |     | || |      | |     | || |   | |_/ /    | || |    | |       | || |  |   \/   |  | || |  |   \ | |   | || |  /  .--.  \  | || |    | |__) |  | || | /  .-.  \    | || |   | |__) |   | || |  |  (__ \_|  | || | |_/ | | \_|  | || |  | |    | |  | || |  \ \   / /   | || |  | | /\ | |  | || |   \ \  / /   | || |   \ \  / /   | || |  |_/  / /    | || |  |_/____) |  | |
>>> | |   / ____ \   | || |    |  __'.   | || |  | |         | || |   | |    | | | || |   |  _|  _   | || |   |  _|      | || | | |    ____  | || |   |  __  |   | || |      | |     | || |   _  | |     | || |   |  __'.    | || |    | |   _   | || |  | |\  /| |  | || |  | |\ \| |   | || |  | |    | |  | || |    |  ___/   | || | | |   | |    | || |   |  __ /    | || |   '.___`-.   | || |     | |      | || |  | '    ' |  | || |   \ \ / /    | || |  | |/  \| |  | || |    > `' <    | || |    \ \/ /    | || |     .'.' _   | || |    /  ___.'  | |
>>> | | _/ /    \ \_ | || |   _| |__) |  | || |  \ `.___.'\  | || |  _| |___.' / | || |  _| |___/ |  | || |  _| |_       | || | \ `.___]  _| | || |  _| |  | |_  | || |     _| |_    | || |  | |_' |     | || |  _| |  \ \_  | || |   _| |__/ |  | || | _| |_\/_| |_ | || | _| |_\   |_  | || |  \  `--'  /  | || |   _| |_      | || | \  `-'  \_   | || |  _| |  \ \_  | || |  |`\____) |  | || |    _| |_     | || |   \ `--' /   | || |    \ ' /     | || |  |   /\   |  | || |  _/ /'`\ \_  | || |    _|  |_    | || |   _/ /__/ |  | || |    |_|       | |
>>> | ||____|  |____|| || |  |_______/   | || |   `._____.'  | || | |________.'  | || | |_________|  | || | |_____|      | || |  `._____.'   | || | |____||____| | || |    |_____|   | || |  `.___.'     | || | |____||____| | || |  |________|  | || ||_____||_____|| || ||_____|\____| | || |   `.____.'   | || |  |_____|     | || |  `.___.\__|  | || | |____| |___| | || |  |_______.'  | || |   |_____|    | || |    `.__.'    | || |     \_/      | || |  |__/  \__|  | || | |____||____| | || |   |______|   | || |  |________|  | || |    (_)       | |
>>> | |              | || |              | || |              | || |              | || |              | || |              | || |              | || |              | || |              | || |              | || |              | || |              | || |              | || |              | || |              | || |              | || |              | || |              | || |              | || |              | || |              | || |              | || |              | || |              | || |              | || |              | || |              | |
>>> | '--------------' || '--------------' || '--------------' || '--------------' || '--------------' || '--------------' || '--------------' || '--------------' || '--------------' || '--------------' || '--------------' || '--------------' || '--------------' || '--------------' || '--------------' || '--------------' || '--------------' || '--------------' || '--------------' || '--------------' || '--------------' || '--------------' || '--------------' || '--------------' || '--------------' || '--------------' || '--------------' |
>>>  '----------------'  '----------------'  '----------------'  '----------------'  '----------------'  '----------------'  '----------------'  '----------------'  '----------------'  '----------------'  '----------------'  '----------------'  '----------------'  '----------------'  '----------------'  '----------------'  '----------------'  '----------------'  '----------------'  '----------------'  '----------------'  '----------------'  '----------------'  '----------------'  '----------------'  '----------------'  '----------------'

```

```
OUPUT:
 .----------------.  .----------------.  .-----------------. .----------------.  .----------------.  .----------------.  .----------------.  .----------------.  .-----------------.
| .--------------. || .--------------. || .--------------. || .--------------. || .--------------. || .--------------. || .--------------. || .--------------. || .--------------. |
| | ____    ____ | || |      __      | || | ____  _____  | || |  ____  ____  | || |      __      | || |  _________   | || |  _________   | || |      __      | || | ____  _____  | |
| ||_   \  /   _|| || |     /  \     | || ||_   \|_   _| | || | |_   ||   _| | || |     /  \     | || | |  _   _  |  | || | |  _   _  |  | || |     /  \     | || ||_   \|_   _| | |
| |  |   \/   |  | || |    / /\ \    | || |  |   \ | |   | || |   | |__| |   | || |    / /\ \    | || | |_/ | | \_|  | || | |_/ | | \_|  | || |    / /\ \    | || |  |   \ | |   | |
| |  | |\  /| |  | || |   / ____ \   | || |  | |\ \| |   | || |   |  __  |   | || |   / ____ \   | || |     | |      | || |     | |      | || |   / ____ \   | || |  | |\ \| |   | |
| | _| |_\/_| |_ | || | _/ /    \ \_ | || | _| |_\   |_  | || |  _| |  | |_  | || | _/ /    \ \_ | || |    _| |_     | || |    _| |_     | || | _/ /    \ \_ | || | _| |_\   |_  | |
| ||_____||_____|| || ||____|  |____|| || ||_____|\____| | || | |____||____| | || ||____|  |____|| || |   |_____|    | || |   |_____|    | || ||____|  |____|| || ||_____|\____| | |
| |              | || |              | || |              | || |              | || |              | || |              | || |              | || |              | || |              | |
| '--------------' || '--------------' || '--------------' || '--------------' || '--------------' || '--------------' || '--------------' || '--------------' || '--------------' |
 '----------------'  '----------------'  '----------------'  '----------------'  '----------------'  '----------------'  '----------------'  '----------------'  '----------------'

```

### Python 3: 145 bytes

```
i=input;l=int(i());h=int(i());t=[ord(c)-65if c.isalpha()else 26for c in i().upper()]
while h:h-=1;r=i();print(''.join(r[j*l:l*(j+1)] for j in t))

```

Try it online!

# Answer
# Python 3,  ~~131 130 128 126~~  125 bytes

```
i=input
L=int(i())
exec("t=[L*[27,ord(c)%32][c.isalpha()]for c in i()]"+";r=i();print(''.join(r[j-L:j]for j in t))"*int(i()))

```

A few golfs of the provided code.

Note: I upper-cased `l` to `L` and replaced a couple of `;` with newlines just for legibility.

**Try it online!**

1. When characters are alphabetical their ordinals are ranges \\$\[65,90\]+\[97,122\]\\$ which modulo \\$32\\$ are \\$\[1,27\]+\[1,27\]=\[1,27\]\\$. As such we can remove the `.upper()` and work with `ord(c)%32` in this case.
2. Rather than an `if-else` we can either use the fact that `False` is `0` and `True` is `1` and multiply (as originally suggested by manatwork in comments) or use list indexing for the two cases like above (`[27,ord(c)%32][c.isalpha()]` chooses the slice stop rather than its start).
3. We can save a little by replacing the `while` loop with the `exec` of a string of code produced using string multiplication.
4. We can save a byte by moving `t=...` into the `exec`-ed code so we do not have to assign to `h` at all. Another is saved by moving the repeated string's trailing `;` to the beginning so that the `t` assignment string doesn't require its own.
5. Rather than `[(j-1)*L:j*L]`, or even `[~-j*L:j*L]`, we can multiply by `L` once in the construction of `t` and just do `[j-L:j]`.
> 2 votes

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


# Question
Title: Proportion of self-avoiding walks on a square lattice
# The challenge

Given a positive integer `N`, compute the proportion of `N`-step walks on a plane that don't intersect themselves.

Each step can have any of the `4` possible directions North, East, South, West.

A walk intersects itself if it visits a previously visited point.

# Examples

* `N=1`: a single-step walk obviously doesn't intersect itself. So the result is `1`.
* `N=2`: given the first step in any direction, there are `3` possible directions that avoid intersection, and one that goes back to the origin, causing intersection. So the result is `3/4 = 0.75`.
* `N=3`: if the second step doesn't cause intersection, which happens `3/4` of the times, the third step will not cause intersection with probability again `3/4`. So the result is `(3/4)^2 = 0.5625`.
* `N=4`: things become more interesting because proper loops can be formed. A similar computation as above gives `(3/4)^3 - 8/4^4 = 0.390625`, where the second term accounts for the `8` proper loops out of the `4^4` possible paths (these are not excluded by the first term).

# Additional rules

# Test cases

```
1  -> 1
2  -> 0.75
3  -> 0.5625
4  -> 0.390625
5  -> 0.27734375
6  -> 0.1904296875
7  -> 0.132568359375
8  -> 0.09027099609375
9  -> 0.0620574951171875
10 -> 0.042057037353515625
11 -> 0.02867984771728515625
12 -> 0.0193674564361572265625

```

# Answer
# Jelly, ~~15~~ 12 bytes

```
‘ı×Ƭ¤ṗÄQƑ€Æm

```

Try it online!

A monadic link taking `N` as its argument and returning a float representing the proportion of non-self-intersecting walks of length `N`. Generates all walks of that length and then checks for intersections, using complex numbers to represent the 2D coordinates.

Thanks to @LuisMendo for saving a byte, and @Mr.XCoder for saving 2 more!

## Explanation

```
‘            | Increment by 1
    ¤        | Following as a nilad
 ı           | - 1i
  ×Ƭ         | - Multiply (by 1i) until no new values, returning all intermediate values
     ṗ       | Cartesian power (with N+1)
      Ä      | Cumulative sums of innermost lists
       QƑ€   | Check whether each list is invariant when uniquified
          Æm | Arithmetic mean

```
> 5 votes

# Answer
# Haskell, ~~153 149 144 140 126 118~~ 92 bytes

Here we represent the 2d coordinates as a single integer: We start at `0`, and the directions `N,E,S,W` correspond to adding `+n,+1,-n,-1` where `n` is the input (we could also use any larger number). Using this we generate all possible paths, and then just check for duplicate numbers in those paths.

Thanks @H.PWiz for -26 bytes!

```
g n|a<-scanl(+)0<$>mapM(\_->[1,-1,n,-n])[1..n]=sum[1|x<-a,[b|b<-x,c<-x,b==c]==x]/sum[1|x<-a]

```

Try it online!

### Explanation

```
--generate all possible paths
    a<-scanl(+)0<$>mapM(\_->[1,-1,n,-n])[1..n]
--count the non-self intersecting paths, compute the ratio to the total
g n|a<- ... =sum[1|x<-a,[b|b<-x,c<-x,b==c]==x]/sum[1|x<-a]

```
> 14 votes

# Answer
# Python 2, 89 bytes

```
f=lambda n,S=[0]:n>=len(S)and sum(f(n,S+[S[-1]+d])for d in[-n,-1,1,n])/4.or len(set(S))>n

```

Try it online!

A recursive approach inspired by flawr's lovely Haskell answer. Outputs a float.
> 7 votes

# Answer
# MATL, 16 bytes

Done with a lot of help from Luis Mendo in MATL CHATL.

```
QJ4:!^Z^!YsSdAYm

```

Try it at MATL Online!

Alternative:

```
Q8BPZFZ^!YsSdAYm

```

Try it at MATL Online!

## Explanation

```
QJ4:!^Z^!YsSdAYm    – Full program. Receives an integer N as input.
  4:                – Range 1...4.
 J  !^              – Raise J (imaginary unit) to those powers*. Yields j, -1, -j, 1.
Q     Z^            – Cartesian power N+1.
        !Ys         – Transpose and take the cumulative sums.
           Sd       – Sort and get the deltas (consecutive differences).
             A      – All. For each column, if it contains 0, then 0, else 1.
              Ym    – Arithmetic mean.

```

(\*): `!` is needed there because Octave is weird.
> 5 votes

# Answer
# \+ gtools, ~~111~~ 88 bytes

```
mean(!apply(diffinv(t(expand.grid(rep(list(c(1,-1,n<-scan(),-n)),n)))),2,anyDuplicated))

```

Try it online!

Test suite

Reads `N` from STDIN and implicitly prints the answer as a float.

Thanks to @LuisMendo for a fab challenge and saving 6 bytes! Thanks to @Mr.XCoder for saving 3 bytes (indirectly via my Jelly answer). Thanks to @Giuseppe for saving 10 bytes with an excellent suggestion partially inspired by @flawr’s Haskell answer!
> 4 votes

# Answer
# 05AB1E, 16 bytes

Uses flawr's method of reducing to 1D.

```
1‚D(«Iãε.¥DÙQ}ÅA

```

Try it online!
> 3 votes

# Answer
# Haskell, 69 bytes

```
(%[])
-1%_=1
n%l=sum[(n-1)%map(+d)(0:l)|d<-[1,-1,pi,-pi],all(/=0)l]/4

```

Try it online!

Uses a similar idea to flawr's solution of storing 2D coordinates as 1D values: \\$(x,y)\\$ is represented as \\$x+\pi y\\$. Maybe this is unfair because finite precision means that eventually two different coordinates will be represented as the same value. This will take an extremely large input though because `toRational pi` equals `884279719003555 % 281474976710656`.

Instead of updating the position after each move, we `map` the position change onto the list of previously visited coordinates. That way, we can detect a collision by seeing a 0 among the previous coordinates. Because we only check a coordinate the loop after it's added, one extra loop is done, for `n+1` total.
> 2 votes

# Answer
# Python 3, 76 bytes

```
f=lambda n,p=0,*S:n<1or sum(f(n-1,q,p,*S)for q in{p-1,p+1,p-1j,p+1j}-{*S})/4

```

Try it online!
> 2 votes

# Answer
# Charcoal, ~~56~~ 52 bytes

```
Ｎθ≔⁰η⊞υ⟦⁰⟧ＦυＦΦ⁺⟦¹θ±¹±θ⟧§ι±¹¬№ικ¿⁼Ｌιθ≦⊕η⊞υ⁺ι⟦κ⟧Ｉ∕ηＸ⁴θ

```

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

```
Ｎθ

```

Input `N`.

```
≔⁰η

```

Initialise the number of paths to `0`.

```
⊞υ⟦⁰⟧

```

Start off with a path with no steps.

```
Ｆυ

```

Perform a breadth-first search of the paths.

```
ＦΦ⁺⟦¹θ±¹±θ⟧§ι±¹¬№ικ

```

Take @flawr's list `1, N, -1, -N` and add the last position on the current path to each value. Filter out results that already appear in that path, and loop over the remaining self-avoiding values.

```
¿⁼Ｌιθ

```

If this path already has `N` steps...

```
≦⊕η

```

... then increment the count of found paths.

```
⊞υ⁺ι⟦κ⟧

```

... otherwise construct a new path and add it to the search list.

```
Ｉ∕ηＸ⁴θ

```

Print the proportion of self-avoiding paths.
> 1 votes

---
Tags: code-golf, integer
---


title: Determining the winner of a Chess game

text:
# Question
Title: Determining the winner of a Chess game
## Challenge

Being someone who plays far too much chess in his spare time, I thought I'd set a code golf challenge inspired by the game of chess (with a software flavour), for those interested.

> The challenge is to determine the winner of a game of standard chess given a *PGN* (Portable Game Notation) file as input -- or in the case of a draw/stalemate, be able to recognise it.
>
> Write a full program that takes via the standard input stream a PGN file *except the final result string* and outputs the winner of the game. (See the Wikipedia article for a simple description of the text format.) The program should determine the winner from the provided move information and output `1-0` for White winning, `0-1` for Black winning, and `1/2-1/2` for a draw (by stalemate). Mutually agreed draws and resignations should be denoted `?` since they cannot be differentiated on this basis alone. White is always assumed to move first.
>
> Note that the *Result* metadata tag nor the game result at the end of the PGN block itself is to be included in any input, as this must be determined by the program's algorithm. The checkmate symbol (usually `#`) is also never present. All other metadata and comments are valid input to the program.

Example (from Wikipedia page):

Input:

```
[Event "F/S Return Match"]
[Site "Belgrade, Serbia Yugoslavia|JUG"]
[Date "1992.11.04"]
[Round "29"]
[White "Fischer, Robert J."]
[Black "Spassky, Boris V."]
~~[Result "1/2-1/2"]~~

1. e4 e5 2. Nf3 Nc6 3. Bb5 {This opening is called the Ruy Lopez.} 3... a6
4. Ba4 Nf6 5. O-O Be7 6. Re1 b5 7. Bb3 d6 8. c3 O-O 9. h3 Nb8  10. d4 Nbd7
11. c4 c6 12. cxb5 axb5 13. Nc3 Bb7 14. Bg5 b4 15. Nb1 h6 16. Bh4 c5 17. dxe5
Nxe4 18. Bxe7 Qxe7 19. exd6 Qf6 20. Nbd2 Nxd6 21. Nc4 Nxc4 22. Bxc4 Nb6
23. Ne5 Rae8 24. Bxf7+ Rxf7 25. Nxf7 Rxe1+ 26. Qxe1 Kxf7 27. Qe3 Qg5 28. Qxg5
hxg5 29. b3 Ke6 30. a3 Kd6 31. axb4 cxb4 32. Ra5 Nd5 33. f3 Bc8 34. Kf2 Bf5
35. Ra7 g6 36. Ra6+ Kc5 37. Ke1 Nf4 38. g3 Nxh3 39. Kd2 Kb5 40. Rd6 Kc5 41. Ra6
Nf2 42. g4 Bd3 43. Re6 ~~1/2-1/2~~

```

Output: `?` (since it was a mutually agreed draw)

## Rules

Other than mentioned in the problem statement, there are no further restrictions. You may write the program in any compiled/interpreted programming language. The code for the program must be complete, i.e. compile without any modifications or external reference.

The aim as always is to solve the task with the smallest number of characters of code.

(Saying that, I can't promise to accept the answer with the shortest code. I'll also be looking at elegance of the code and time complexity of the algorithm, especially in the case of verbose language, and hope others will do the same!)

## My Solution

I'll be attempting an F# solution while this question is open -- will post it here when I have something.

---

## Format

Please post your answers in the following format for the purpose of easy comparison:

> ## Language
>
> **Number of characters: ???**
>
> Fully golfed code:
>
> ```
> (code here)
>
> ```
>
> Clear (ideally commented) code:
>
> ```
> (code here)
>
> ```
>
> Any notes on the algorithm/clever shortcuts the program takes.

---

# Answer
## Ruby 1.9

**Number of characters: 93**

Assuming that all inputs are valid games, and that games always end in checkmates or stalemates (as per Noldorin's response in the comments), then we only need to check who played the last move and whether it was a checkmate or not.

Golfed code:

```
*a,b,c=$<.read.gsub(/{[^}]*}|;.*$/,"").split;puts c=~/#/?(b=~/[^.]\.$/?"1-0":"0-1"):"1/2-1/2"

```

Ungolfed code:

```
# read entire input
game = $<.read
# strip comments
game = game.gsub(/{[^}]*}|;.*$/,"")
# split the input and get the last two words
*rest, second, last = game.split
# check if the last move has a checkmate symbol
if last =~ /#/
# if so, then determine whether the last move is white or black based
# on the number of periods in the second-to-last word
  puts second =~ /[^.]\.$/ ? "1-0" : "0-1"
else
# if not, then it's a draw
  puts "1/2-1/2"
end

```
> 9 votes

# Answer
## Python 3 (with python-chess)

**Number of characters: ~~173~~ ~~168~~ ~~150~~ 130**

*-5 characters thanks to Unrelated String*

```
import io,chess.pgn as c
g=c.read_game(open(0))
b=g.board()
for m in g.mainline_moves():b.push(m)
print(b.result().replace(*'*?'))

```

Figured I might as well do this, since I already studied python-chess to answer another chess challenge.

Attempt This Online! - the provided test case (outcome cannot be determined)

Attempt This Online! - an example of a stalemate

Attempt This Online! - an example of a checkmate

Attempt This Online! - an example of a real game that ended by threefold repetition at move #34w, extrapolated to hypothetical move #38w to make this program detect a draw

Attempt This Online! - an example of a real game that ended by threefold repetition at move #25b, extrapolated to hypothetical move #29b to make this program detect a draw
> 3 votes

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


title: Can I sweep the mines?

text:
# Question
Title: Can I sweep the mines?
Minesweeper is a popular puzzle game where you must discover which tiles are "mines" without clicking on those tiles. Instead, you click on nearby tiles to reveal the number of adjacent mines. One downside about the game is that it is possible to end up in a scenario where there are multiple valid answers and you may only guess. For example, take the following board:

```
1110
2*31
3*??
2*4?
112?

```

In this format, a number represents the number of adjacent mines, an `*` represents a known mine, and a "?" represents a potential mine. The unfortunate thing about this particular puzzle is that there are four distinct and *valid* potential solutions:

```
1110    1110    1110    1110
2*31    2*31    2*31    2*31
3*4*    3*5*    3**2    3**1
2*42    2*4*    2*4*    2*42
112*    1121    1121    112*

```

This means the board is *unsolvable*. Here is an example of a *solvable* board:

```
1121
1??*
12?*
0122

```

This board is solvable because there is only one possible valid solution:

```
1121
1*4*
12**
0122

```

Your task is to write either a program or function that takes a valid minesweeper board and determines if it is solvable or not. By "valid minesweeper board", I mean that the input will always be rectangular, have at least one solution, and not contain any invalid characters.

Your input may be an array of characters, an array of strings, a string containing newlines, etc. The output must be a truthy value if it is solvable and a falsy value if it is not. I am not extremely worried about performance, but your solution must *theoretically* work for any size input.

As usual, standard loopholes apply and the shortest solution in bytes wins!

# Examples:

The following examples are all solvable:

```
1121
1??*
12?*
0122

1110
1???
1110
0000

1110
3???
??20
*310

****
****
****
****

0000
0000
0000
0000

1100
*100
2321
??*2
13*2
1221
1*10
1110

1121
2*??
2*31
2220
1*10

```

The following examples are all unsolvable:

```
1110
2*31
3*??
2*4?
112?

01??11*211
12??2323*1
1*33*2*210
12?2122321
13?3101**1
1***101221

1***
3*52
2*31
12??
02??
01??

00000111
000012*1
00001*21
22101110
**100111
?31123*1
?311**31
**113*20

```

# Answer
> 20 votes
# GNU Prolog, 493 bytes

```
z(_,[_,_]).
z(F,[A,B,C|T]):-call(F,A,B,C),z(F,[B,C|T]).
i([],[],[],[]).
i([H|A],[I|B],[J|C],[H-I-J|T]):-i(A,B,C,T).
c(A/_-B/_-C/_,D/_-_/T-E/_,F/_-G/_-H/_):-T#=A+B+C+D+E+F+G+H.
r(A,B,C):-i(A,B,C,L),z(c,L).
q(63,V):-var(V).
q(42,1/_).
q(X,0/Y):-Y#=X-48.
l([],[0/_]).
l([H|T],[E|U]):-q(H,E),l(T,U).
p([],[[0/_,0/_]],0).
p([],[[0/_|T]],N):-M#=N-1,p([],[T],M).
p([H|T],[[0/_|E]|U],N):-p(T,U,N),l(H,E).
m([H|A],B):-length(H,N),p([],[R],N),p([H|A],M,N),z(r,[R|M]),p(B,M,N).
s(A):-setof(B,m(A,B),[_]).

```

An extra predicate that may be useful for testing (not part of the submission):

```
d([]).
d([H|T]):-format("~s~n",[H]),d(T).

```

Prolog's definitely the right language for solving this task from the practical point of view. This program pretty much just states the rules of Minesweeper and lets GNU Prolog's constraint solver solve the problem from there.

`z` and `i` are utility functions (`z` does a sort of fold-like operation but on sets of three adjacent elements rather than 2; `i` transposes 3 lists of *n* elements into a list of *n* 3-tuples). We internally store a cell as `*x*/*y*`, where *x* is 1 for a mine and 0 for a nonmine, and *y* is the number of adjacent mines; `c` expresses this constraint on the board. `r` applies `c` to every row of the board; and so `z(r,M)` checks to see if `M` is a valid board.

Unfortunately, the input format required to make this work directly is unreasonable, so I also had to include a parser (which probably accounts for more code than the actual rules engine, and most of the time spent debugging; the Minesweeper rules engine pretty much worked first time, but the parser was full of thinkos). `q` converts a single cell between a character code and our `*x*/*y*` format. `l` converts one line of the board (leaving one cell that's known to be not a mine, but with an unknown number of neighbouring mines, at each edge of the line as a border); `p` converts the entire board (including the bottom border, but excluding the top one). All of these functions can be run either forwards or backwards, thus can both parse and pretty-print the board. (There's some annoying wiggling around with the third argument to `p`, which specifies the width of the board; this is because Prolog doesn't have a matrix type, and if I don't constrain the board to be rectangular, the program will go into an infinite loop trying progressively wider borders around the board.)

`m` is the main Minesweeper solving function. It parses the input string, generating a board with a correct border (via using the recursive case of `p` to convert most of the board, then calling the base case directly to generate the top border, which has the same structure as the bottom border). Then it calls `z(r,[R|M])` to run the Minesweeper rules engine, which (with this call pattern) becomes a generator generating only valid boards. At this point, the board is still expressed as a set of constraints, which is potentially awkward for us; we could perhaps have a single set of constraints which could represent more than one board. Additionally, we haven't yet specified anywhere that each square contains at most one mine. As such, we need to explicitly "collapse the waveform" of each square, requiring it to be specifically either a (single) mine or a nonmine, and the easiest way to do this is to run it through the parser backwards (the `var(V)` on the `q(63,V)` case is designed to prevent the `?` case running backwards, and thus deparsing the board forces it to be fully known). Finally, we return the parsed board from `m`; `m` thus becomes a generator which takes a partially unknown board and generates all the known boards consistent with it.

That's really enough to solve Minesweeper, but the question explicitly asks to check whether there's exactly one solution, rather than to find all solutions. As such, I wrote an extra predicate `s` which simply converts the generator `m` into a set, and then asserts that the set has exactly one element. This means that `s` will return truthy (`yes`) if there is indeed exactly one solution, or falsey (`no`) if there is more than one or less than one.

`d` is not part of the solution, and not included in the bytecount; it's a function for printing a list of strings as though it were a matrix, which makes it possible to inspect the boards generated by `m` (by default, GNU Prolog prints strings as a list of ASCII codes, because it treats the two synonymously; this format is fairly hard to read). It's useful during testing, or if you want to use `m` as a practical Minesweeper solver (because it uses a constraint solver, it's highly efficient).

# Answer
> 11 votes
## Haskell, ~~193~~ ~~169~~ 168 bytes

```
c '?'="*!"
c x=[x]
g x|t<-x>>" ",w<-length(words x!!0)+1=1==sum[1|p<-mapM c$t++x++t,and[sum[1|m<-[-1..1],n<-[j-w,j,j+w],p!!(m+n)=='*']==read[d]|(j,d)<-zip[0..]p,d>'/']]

```

Usage example: `g "1121 1??* 12?* 0122"` -\> `True`.

How it works: make list of all possible boards with the `?` replaced by either `*` or `!` (`!` means ignore later). This is done via `mapM c`, but before we prepend and append a bunch of spaces to the input string so that our indexing won't be out of range. For each such board check if it's a valid board by looping over all elements (index `j`) and if it's a number (`d>'/'`) also over its neighbors (index `n`, `m`), count the `*` and compare to the number. Finally check the length of the list of valid boards.

# Answer
> 7 votes
## Perl, 215 bytes

213 bytes of code + `-p0` flags (2 bytes).

```
/.*/;$c="@+";$_=A x$c."
$_".A x$c;s/^|$/A/mg;sub t{my($_)=@_;if(/\?/){for$i(0..8,"*"){t(s/\?/$i/r)}}else{$r=1;for$i(/\d/g){$r&=!/(...)[^V]{$c}(.$i.)[^V]{$c}(...)(??{"$1$2$3"=~y%*%%!=$i?"":R})/}$e+=$r}}t$_;$_=$e==1

```

The idea of the code is to test every possibility and see if there is one and only one that leads to a fully filled board that is valid.

More readable, the code looks like:

```
/.*/;$c="@+";           # count the size of a line.
$_=A x$c."\n$_".A x$c;  # add a line of "A" at the begining and another at the end.
s/^|$/A/mg;        # add a "A" at the start and the end of each line.

# The funcion that actually solves the problem
sub t {
    my $_= pop; # Get the parameter, store it in $_ (default argument to regex).
    if (/\?/) {  # if there is another unknown char.
        for $i(0..8,"*") { # try every possibility
            t(s/\?/$i/r)  # reccursive call where the first unknown char has been replaced
        }
    } else { # no more unknown character, so here we check if the board is valid
        $r=1;  # if r == 1 at the end, then the board is valid, otherwise it's not
        for $i (/\d/g) { # for each number present of the board
            # the following regex checks if there is a number is surrounded by either
            # too much or too little mines.
            # (how it works: magic!)
         $r&=!/(...)[^V]{$c}(.$i.)[^V]{$c}(...)(??{"$1$2$3"=~y%*%%!=$i?"":R})/
        }
        $e+=$r # Increment the number of valid boards.
    }
}
t$_; # Call the previous function
$_=$e==1 # Checks if there is only one valid board ($_ is implicitly printed thanks to -p flag).
```

About the regex in the middle :

```
/(...)[^V]{$c}(.$i.)[^V]{$c}(...)(??{"$1$2$3"=~y%*%%!=$i?"":R})/

```

Note that `[^V]` just stands for "any character, including \n".
So the idea is: 3 char on a line, then 3 on the next (with `$i` in the middle), then 3 on the next. those 3 groups of 3 numbers are aligned, thanks to `[^V]{$c}` and the number we're interested into is in the middle.
And then, `"$1$2$3"=~y%*%%` counts the number of `*` (bombs) among those 9 characters: if it's different from `$i`, we add an empty string to match (`""` =\> instant matching, the regex returns true), otherwise, we force a fail by trying to match `R` (which can't be in the string).
If the regex matches, then the board isn't valid, so we set `$r` to `0` with `$r&=!/.../`.
And that's why we add some `A` everywhere around each line: so we don't have to worry about edges cases of numbers that are near the edges of the board: they'll have `A` as neighbors, which aren't mines (of course, roughly any char could have work, I chose `A`).

You can run the program from the command line like that :

```
perl -p0E '/.*/;$c="@+";$_=A x$c."\n$_".A x$c;s/^|$/A/mg;sub t{my($_)=@_;if(/\?/){for$i(0..8,"*"){t(s/\?/$i/r)}}else{$r=1;for$i(/\d/g){$r&=!/(...)[^V]{$c}(.$i.)[^V]{$c}(...)(??{"$1$2$3"=~y%*%%!=$i?"":R})/}$e+=$r}}t$_;$_=$e==1' <<< "1121
1??*
12?*
0122"

```

The complexity couldn't be worst: it's `O(m*9^n)` where `n` is the number of `?` on the board, and `m` is the number of cells on the board (without counting the complexity of the regex in the middle, which is probably pretty bad). On my machine, it works pretty fast for up to 4 `?`, and starts to be slower 5, takes a few minutes for 6, and I didn't try for larger numbers.

# Answer
> 7 votes
# Mathematica, ~~214~~ ~~192~~ ~~190~~ ~~180~~ ~~176~~ ~~174~~ ~~168~~ 165 bytes

```
0&/@Cases[b="*";If[!FreeQ[#,q="?"],(x#0@MapAt[x&,#,#&@@#~Position~q])/@{b,0},BlockMap[If[#[[2,2]]==b,b,Count[#,b,2]]&,#~ArrayPad~1,{3,3},1]]&@#,#/.q->_,All]=={0}&

```

Contains U+F4A1 (Private use). This unnamed function finds all possible combinations for `"?"` (i.e. replacing all `"?"`s with `"*"` or `0`) and checks whether there is only one valid solution.

# Explanation

```
b="*";

```

Set `b` to `"*"`.

```
!FreeQ[#,q="?"]

```

Set `q` to the string `"?"`. Check whether there is `"?"` in the input.

```
If[ ..., (x#0 ... ,0}, BlockMap[ ... ]]

```

---

If `True`...

```
(x#0@MapAt[x&,#,#&@@#~Position~q])/@{b,0}

```

Replace the first occurrence of `q`(=`"?"`) with `b`(=`"*"`) or `0` (i.e. two outputs), and apply the entire function again.

---

If `False`...

```
#~ArrayPad~1

```

Pad the input with one layer of `0`.

```
BlockMap[If[#[[2,2]]==b,b,Count[#,b,2]]&, ... ,{3,3},1]

```

Partition the input into 3 x 3 matrices with offset 1. For each partition, apply a function such that if the middle value is `b`(=`"*"`), the output is the `b`(=`"*"`), and if the middle value is not `b`(=`"*"`), the output is the number of `b`(=`"*"`) in the input. This step re-evaluates all the number cells.

---

```
Cases[ ... ,#/.q->_,All]

```

From all of the results, find the ones that match the input

```
0&/@ ... =={0}

```

Check whether the input is length 1.

# Answer
> 4 votes
# JavaScript (ES6), 221 ~~229~~

```
g=>(a=>{for(s=i=1;~i;g.replace(x,c=>a[j++],z=j=0).replace(/\d/g,(c,p,g)=>([o=g.search`
`,-o,++o,-o,++o,-o,1,-1].map(d=>c-=g[p+d]=='*'),z|=c)),s-=!z)for(i=a.length;a[--i]='*?'[+(c=a[i]<'?')],c;);})(g.match(x=/\?/g)||[])|!s

```

~~If all input is expected to be valid - that is with at least 1 solution - then I can save a byte changing `s==1` with `s<2`~~

*Less golfed*

```
g=>{
  a = g.match(/\?/g) || []; // array of '?' in a
  s = 1; // counter of solutions
  for(i=0; ~i;) // loop to find all configurations of ? and *
  {
    // get next configuration
    for(i = a.length; a[--i] = '*?'[+( c = a[i] < '?')], c; );
    z = 0; // init at 0, must stay 0 if all cells count is ok
    g
    .replace(/\?/g,c=>a[j++],j=0) // put ? and * at right places
    .replace(/\d/g,(c,p,g)=>(
       // look for mines in all 8 directions
       // for each mine decrease c
       // if c ends at 0, then the count is ok
       [o=g.search`\n`,-o,++o,-o,++o,-o,1,-1].map(d=>c-=g[p+d]=='*'),
       z|=c // z stays at 0 if count is ok
    )) // check neighbour count
    s-=!z // if count ok for all cells, decrement number of solutions
  }
  return s==0 // true if exactly one solution found
}

```

**Test**

```
F=
g=>(a=>{for(s=i=1;~i;g.replace(x,c=>a[j++],z=j=0).replace(/\d/g,(c,p,g)=>([o=g.search`
`,-o,++o,-o,++o,-o,1,-1].map(d=>c-=g[p+d]=='*'),z|=c)),s-=!z)for(i=a.length;a[--i]='*?'[+(c=a[i]<'?')],c;);})(g.match(x=/\?/g)||[])|!s

out=x=>O.textContent+=x+'\n'

Solvable=['1121\n1??*\n12?*\n0122'
,'1110\n1???\n1110\n0000'
,'1110\n3???\n??20\n*310'
,'****\n****\n****\n****'
,'0000\n0000\n0000\n0000'
,'1100\n*100\n2321\n??*2\n13*2\n1221\n1*10\n1110'
,'1121\n2*??\n2*31\n2220\n1*10']
Unsolvable=['1110\n2*31\n3*??\n2*4?\n112?'
,'01??11*211\n12??2323*1\n1*33*2*210\n12?2122321\n13?3101**1\n1***101221'
,'1***\n3*52\n2*31\n12??\n02??\n01??'
,'00000111\n000012*1\n00001*21\n22101110\n**100111\n?31123*1\n?311**31\n**113*20']
out('Solvable')
Solvable.forEach(t=>out(t+'\n'+F(t)+'\n'))
out('Unsolvable')
Unsolvable.forEach(t=>out(t+'\n'+F(t)+'\n'))
```

```
<pre id=O></pre>
```

# Answer
> 0 votes
# JavaScript (Node.js), 167 bytes

```
s=>g=(r=c='',[p,...q]=s,w)=>w?0:p?(g(r+0,q,p=='*')+g(r+1,q,1/p),c==1):c-=-![...s].some((p,i)=>p>' '&&[-1,1,-q,-1-q,-2-q,q,q+1,q+2].map(j=>p-=~~r[i+j])|p,q=s.search`
`)

```

Try it online!

Though op say "input will always be rectangular, have at least one solution", false sample 3 doesn't match, so I still require 1 solution, not \<2 solution

```
s=>(        // p.s. Here "block" can also mean \n
  c=0,          // possible mine count
  g=(           // recursive
    r='',       // mine states
    [p,...q]=s, // known info to check possible state for a block
    w           // invert condition, stop if true
  )=>
    w?0:
      p?(       // for each block
        g(r+0,q,p=='*')+   // possibly not bomb if doesn't say so
        g(r+1,q,1/p),      // number/newline can't be bomb
        c==1               // only one bomb
      ):
        c-=-![...s].some(  // no block doesn't satisfy
          (p,i)=>
            p>' '&& // \n don't mean number
                    // other symbols turn into NaN when counting
            [-1,1,-q,-1-q,-2-q,q,q+1,q+2].map(j=>p-=~~r[i+j])
                    // subtract each neighbor, OOB = 0
            |p,     // difference between intended and actual
            q=s.search('\n') // how many blocks in a line
        )
)

```

# Answer
> 0 votes
# APL (Dyalog Unicode), 78 bytesSBCS

```
{1=+/∧/∘,¨{⍵[1;1]∊' *',⍕+/'*'=,⍵}⌺3 3¨(⊂⍵){' *'[⍵]@c⊢⍺}¨,⍳2⊣¨c←⍸'?'=⍵}(⊢↑⍨2⌈⍴)

```

Try it online!

A function that takes a 2-dimensional character matrix as its right argument, and gives 1 if the board is solvable (has unique solution) and 0 otherwise.

### How it works

This is a straightforward implementation of the challenge description. Dimension extension is needed because the stencil operator isn't happy with too small arrays.

Ungolfed version:

```
sol←{
  coords←⍸'?'=⍵
  masks←,⍳2⊣¨coords
  replace←{' *'[⍺]@coords⊢⍵}
  check←∧/∘,{⍵[1;1]∊' *',⍕+/'*'=,⍵}⌺3 3
  1=+/masks(check replace)¨⊂⍵
}(⊢↑⍨2⌈⍴)

```

With comments:

```
sol←{  ⍝ ⍵←minesweeper board as a character matrix
  ⍝ 2D coordinates of '?'
  coords←⍸'?'=⍵

  ⍝ possible combinations of blank as 0 and mine as 1
  masks←,⍳2⊣¨coords
          2⊣¨coords  ⍝ (≢coords) copies of 2
        ,⍳           ⍝ cartesian product of 0..n-1 for each n in the above

  ⍝ create a board with selected mines
  replace←{' *'[⍺]@coords⊢⍵}
          {                }  ⍝ a function
                         ⊢⍵   ⍝ take the array ⍵
                  @coords     ⍝ replace the items at given coords
           ' *'[⍺]            ⍝ ... into blanks and mines as specified
                              ⍝ by boolean array ⍺

  ⍝ test if the complete board is valid
  check←∧/∘,{⍵[1;1]∊' *',⍕+/'*'=,⍵}⌺3 3
            {                     }⌺3 3  ⍝ for each 3x3 subarray (including ones centered at the edges)
                         ⍕+/'*'=,⍵       ⍝ s←count the mines and cast to string
             ⍵[1;1]∊' *',                ⍝ check if the center is one of blank, mine, or s
        ∧/∘,                             ⍝ reduce by AND for all subarrays

  ⍝ for all combinations, check if the board has unique solution
  1=+/masks(check replace)¨⊂⍵
      masks(      replace)¨⊂⍵  ⍝ generate all possible boards
            check              ⍝ check each board if it is a valid solution
  1=+/                         ⍝ check that there's exactly one valid solution in total

}(⊢↑⍨2⌈⍴)  ⍝ extend each dimension to have at least length 2 before calling main function
       ⍴   ⍝ dimensions
     2⌈    ⍝ max(n,2) for each dimension
  ⊢↑⍨      ⍝ extend the input to have ^ dimension; fill extended cells with blank

```

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


title: Singular or plural?

text:
# Question
Title: Singular or plural?
Here is a list of 30 English nouns in their singular and plural form. Your job is simply to write the shortest regular expression that matches *all* the nouns in one form and *none* in the other (easy, all English nouns end in `s` in plural form right?).

```
SINGULAR     PLURAL
---------    --------
car          cars
boat         boats
man          men
woman        women
omen         omens
bus          buses
cactus       cacti
spy          spies
pie          pies
louse        lice
mouse        mice
amice        amices
goose        geese
creese       creeses
person       people
child        children
siren        sirens
ox           oxen
foot         feet
tooth        teeth
formula      formulae
minx         minxes
sphinx       sphinges
wife         wives
knife        knives
ion          ions
criterion    criteria
jinni        jinn
zero         zeros
hero         heroes

```

Yes, some of the words have alternative forms, but these are the ones we're going to use.

Here is a script that can help you with the testing; just put your regex between the two slashes (`/`) on the first line.

# Answer
> 11 votes
44, or 46 if delimiting `//` count:

```
dr|wome|[aglx]e|et|ti|ia|[^u]s$|nn$|^.ic|^me

```

# Answer
> 4 votes
42 (or 44 with delimiters)

`^.(e[^r]|ic)|x.|..me|ia|ti|.l..|nn$|[^u]s$` \- Try it online!
`^.(e[^r]|ic)|x.|..me|ia|[adjlu]...$|[^u]s$` \- Try it online!

# Answer
> 2 votes
65 or 67

```
^[lm]i[^n]|^ge|ti|ia|[l|a]e$|ox.|^(wo)?men$|dren|nn$|et|[netro]s$

```

---
Tags: code-golf, regular-expression, natural-language
---


# Question
Title: Average number of strings with Levenshtein distance up to 3
The Levenshtein distance between two strings is the minimum number of single character insertions, deletions, or substitutions to convert one string into the other one. Given a binary string \\$S\\$ of length \\$n\\$, we are a interested in the number of different strings of length \\$n\\$ which have distance at most \\$3\\$ from \\$S\\$.

For example, if \\$S = 0000\\$ there are four strings with Levenshtein distance exactly \\$3\\$ from \\$S\\$, six with distance exactly \\$2\\$, four with distance exactly \\$1\\$ and exactly one with distance \\$0\\$. This makes a total of \\$15\\$ distinct strings with distance at most \\$3\\$ from the string \\$0000\\$. The only string with distance greater than \\$3\\$ is \\$1111\\$.

However, this number depends on the value of \\$S\\$. For example if \\$S = 0010\\$ then the number of distinct strings with distance at most \\$3\\$ is \\$16\\$, in other words all of them.

For this task the input is a value of \\$n \geq 3\\$. Your code must output the average number of binary strings of length \\$n\\$ which have Levenshtein distance at most \\$3\\$ from a uniform and randomly sampled string \\$S\\$. Your answer can be output in any standard way you choose but it must be exact.

# Examples

```
n = 3. Average = 8
n = 4. Average = 15 1/2
n = 5. Average = 28 13/16
n = 6. Average = 50 15/16
n = 7. Average = 85 23/64
n = 8. Average = 135 27/32
n = 9. Average = 206 77/256
n = 10. Average = 300 181/256
n = 11. Average = 423 67/1024
n = 12. Average = 577 99/256
n = 13. Average = 767 2793/4096.
n = 14. Average = 997 3931/4096.
n = 15. Average = 1272 3711/16384.

```

# Score

Your score is the highest value of \\$n\\$ you can reach.

# Answer
> 11 votes
# GAP and the automata package

The average number is the number of pairs of words of length \\$n\\$ with Levenshtein distance up to three, divided by \\$2^n\\$.

It is not very difficult to construct an nondeterministic finite automaton over the alphabet of pairs of bits that accepts the word \\$(a\_1,b\_1)(a\_2,b\_2)\dots(a\_n,b\_n)\\$ iff the binary words \\$a\_1a\_2\dots a\_n\\$ and \\$b\_1b\_2\dots b\_n\\$ have Levenshtein distance up to three. My version uses 14 states. This automaton can be transformed into a minimal deterministic one, which has 39 states. From its transition function we can get a matrix that describes the number of ways we can get from one state to another. Now counting the number of ways we can get from the initial state to some accepting state is just a matter of multiplication.

The implicit recurrance could be simplified because some values are always equal, and it might be solved to give a closed formula, but it seems to be good enough as is.

```
LoadPackage("automata");

nfa := Automaton("nondet", 14, 4,
     [[[1,5,9],[2,7,11],3,4,[5,13],[7,13],[7,14],14,
       [9,13],[11,13],[11,14],14,13,14],
      [[2,5,10],[3,7,12],4,0,[7,14],[5,14],0,7,
       [10,14],[12,14],12,0,14,0],
      [[2,6,9],[3,8,11],4,0,[6,14],[8,14],8,0,
       [11,14],[9,14],0,11,14,0],
      [[1,6,10],[2,8,12],3,4,[8,13],[6,13],14,[8,14],
       [12,13],[10,13],14,[12,14],13,14] ],
     [1], [1..14] );

dfa := MinimalizedAut(nfa);

size := NumberStatesOfAutomaton(dfa);;

mat := NullMat(size, size);;
for row in TransitionMatrixOfAutomaton(dfa) do
  for i in [1..size] do
    mat[i][row[i]] := mat[i][row[i]]+1;
  od;
od;

init := 0 * [1..size];;
init[InitialStatesOfAutomaton(dfa)[1]] := 1;;

fin := 0 * [1..size];;
for i in FinalStatesOfAutomaton(dfa) do
  fin[i] := 1;
od;

f := function(n)
  local res, intpart, fraction;
  res := init * mat^n * fin / 2^n;
  intpart := Int(res);
  fraction := res-intpart;
  Print("n = ", n, ". Average = ", intpart);
  if fraction <> 0 then
    Print(" ",fraction);
  fi;
  Print(".\n");
end;

```

Try it online!

Put it in a file, start `gap` and read the file with a command like `Read("l3.gap");`, then try something like `f(20);` or `for i in [0..100] do f(i); od;`.

Here are some results:

```
n = 0. Average = 1.
n = 1. Average = 2.
n = 2. Average = 4.
n = 3. Average = 8.
n = 4. Average = 15 1/2.
n = 5. Average = 28 13/16.
n = 6. Average = 50 15/16.
n = 7. Average = 85 23/64.
n = 8. Average = 135 27/32.
n = 9. Average = 206 77/256.
n = 10. Average = 300 181/256.
n = 11. Average = 423 67/1024.
n = 12. Average = 577 99/256.
n = 13. Average = 767 2793/4096.
n = 14. Average = 997 3931/4096.
n = 15. Average = 1272 3711/16384.
n = 16. Average = 1594 3985/8192.
n = 17. Average = 1968 48645/65536.
n = 18. Average = 2398 65249/65536.
n = 19. Average = 2889 64891/262144.
n = 20. Average = 3443 16339/32768.
n = 30. Average = 13385 268434611/268435456.
n = 40. Average = 34128 68719475971/137438953472.
n = 50. Average = 69670 281474976708241/281474976710656.
n = 60. Average = 124013 36028797018963093/72057594037927936.
n = 70. Average = 201155 295147905179352821071/295147905179352825856.
n = 80. Average = 305098 75557863725914323416001/151115727451828646838272.
n = 90. Average = 439840 309485009821345068724773101/
309485009821345068724781056.
n = 100. Average = 609383 9903520314283042199192993177/
19807040628566084398385987584.
n = 1000. Average = 660694208
669692879491417075592765655662501131600878007315958504652343992731469406953085\
076558248986759809911329746670573470716765741965803557696277249036098418660925\
245910485926514436588817162816398196367372136384565404686473871329212422972447\
846496629816432160699779855408885478776864478289024177325353755091/
133938575898283415118553131132500226320175601463191700930468798546293881390617\
015311649797351961982265949334114694143353148393160711539255449807219683732185\
049182097185302887317763432563279639273474427276913080937294774265842484594489\
5692993259632864321399559710817770957553728956578048354650708508672.
n = 10000. Average = 666066942458
[fractional part removed]

```

# Pari/GP, 51 bytes

All the eigenvalues of the matrix are integers (could I have known or expected that?), and I found this formula for \\$n\ge 2\\$:

```
f(n)=(40+6*n-4*n^2)/2^n-83/2+331/12*n-6*n^2+2/3*n^3

```

Try it online!

---
Tags: string, math, code-challenge, combinatorics
---


title: Swaps to Sort an Array

text:
# Question
Title: Swaps to Sort an Array
You are given an array \\$A\\$, **which may contain duplicate elements**. In each swap, you may swap the value of any two indices \\$i, j\\$ (i.e. switch the values of \\$A\_i\\$ and \\$A\_j\\$). What is the **least** amount of swaps needed to sort the array, and what are the corresponding swapped indices?

## Scoring

This is , so shortest code wins. **However, your program must terminate in reasonable time (less than 10 seconds) for any array \\$A\\$ with less than 1000 elements.**

## Input

The array \\$A\\$, in any necessary form.

## Output

A list of swaps, with each swap being a pair of numbers, in sequential order - first pair in list is swapped first, in any necessary form.
In the output, the numbers should all represent indices. You may output the answer either one-indexed or zero-indexed, but my samples will use one-indexing.
**The answer might not be unique. However, your answer should still have the same length as the optimal sequence of swaps.**

## Test cases

```
[4,3,2,1] => [(1,4),(2,3)]
[1,3,2,3] => [(2,3)]
[1,2,1,3,2,3] => [(2,3),(4,5)]
[1,2,3,4] => []
[4,2,5,1,3,3] => [(2,6),(1,5),(1,4),(2,3)]

```

# Answer
> 3 votes
# Jelly, ~~51~~ 43 bytes

```
ṪµṢ,$Ḣ©€E¬a="ʋṚƊ×\ẸÞṪTḢ,®ṛ¦Ẹ}¡@¥
WÇẸÐ¿FĖẠƇÄ

```

Try it online!

A pair of links which when called as a monad returns a list of pairs of 1-indexed indices to swap. Based on the clever J algorithm developed by @Jonah, so be sure to upvote that one too!

## Explanation

### Helper link

Takes a list containing a list of the remaining items to be sorted, optionally preceded by the most recent swap. Takes full advantage of the way that  (Head) and  (tail) pop items from a list, which for someone from an R background was something I found took some getting used to when I started using Jelly!

```
Ṫ                                 | Tail (yields the list of remaining items, and also removes this from the list that Ð¿ is collecting up)
 µ                                | Start a new monadic chain
  Ṣ,$                             | Pair the sorted list with the unsorted remaining items
     Ḣ©€                          | Take the head of each, removing from the list and storing each in turn in the register (so the register is left holding the head of the unsorted list)
               Ɗ                  | Following as a monad
             ʋṚ                   | - Following as a dyad, using a list of the remaining sorted and unsorted lists (in that order) as right argument
        E                         |   - Equal (i.e. the head of the unsorted and sorted lists matches)
         ¬                        |   - Not
          a                       |   - And:
              ="                  |     - Equal to zipped right argument (effectively a logical list indicating which of the remainder of the sorted list matched the head of the unsorted and vice-versa)
                ×\                | Cumulative product
                  ẸÞ              | Sort by whether any true
                    Ṫ             | Tail
                     T            | Convert to list of truthy indices
                      Ḣ           | Head (will be 0 if the head of the unsorted and sorted lists matches)
                               ¥  | Following as a dyad, using the remaining unsorted list as right argument
                       ,          | Pair the index to swap with:
                              @   | - Following with arguments reversed:
                           Ẹ}¡    |   - Run following once if index to swap is nonzero:
                        ®ṛ¦       |     - Replace item at index to swap with the original head of the unsorted list that was stored in the register

```

### Main link, takes a list to be sorted

```
W           | Wrap in a further list
  ẸÐ¿       | While any non-zero, do the following collecting up intermediate results
 Ç          | - Call helper link
     F      | Flatten (will remove the now empty initial list)
      Ė     | Enumerate (pair the index of each with the item)
       ẠƇ   | Keep only those without zeros
         Ä  | Cumulative sum of each pair

```

## Original algorithm that fails with repeated values, 16 bytes

```
ỤịƬ€`Ṣ€ŒQTịƲṡ€2Ẏ

```

Try it online!

A monadic link taking a list of integers and returning a list of lists of integers representing the 1-indexed swaps.

### Explanation

```
Ụ                 | Grade the list z up, i.e., sort its indices by their corresponding values.
  Ƭ€`             | For each member of the resulting list, do the following until no new values, using the list of indices itself as the right argument. Keep all intermediate values.
 ị                | - Index into list
           Ʋ      | Following as a monad:
     Ṣ€           | - Sort each list
       ŒQ         | - Logical list, true for original copy of each unique value
         T        | - Indices of truthy values
          ị       | - Index into list
            ṡ€2   | Split each into overlapping sets of 2
               Ẏ  | Join outer together

```

## Inefficient algorithm that is too slow for long lists with lots of repeats, 27 bytes

```
ĠŒ!€ŒpµFịƬ€`Ṣ€ŒQTịƲṡ€2Ẏ)LÞḢ

```

Try it online!

# Answer
> 5 votes
# , 126 bytes

```
[:>[:{:"1@}./:~(({.@I.@:~:>@{.)({:@](|.@:{`[`]}~;])[,[:(0{*/,&I.{.)(<0{i.@$)*"1{"0 1=|.@])(,:>@{.))^:(-.@-:>@{.)^:a:;&(0 2$'')

```

Try it online!

Here is the same code in a more procedural form, if you're looking for an explanation of algorithm.

```
f=. 3 :0
sorting=.y NB. copy of input we'll mutate
sorted=./:~y
swaps=.0 2$''
for_j. i.#y do.
  correct=.j{sorted
  cur=.j{sorting
  if. cur = correct do.
    continue.
  end.
  NB. correctly fill the current idx j
  valid_idxs=.(j<i.#sorting)
  good_j=. valid_idxs * correct = sorting
  NB. will any of these be the correct desitnation for the current elm?
  good_dest=. valid_idxs * cur = sorted
  both=.good_j * good_dest
  use=.(1 e.both) { good_j ,: both
  swap_with=. {.I.use
  swaps=.swaps,(j, swap_with)
  sorting=.(sorting {~ swap_with, j) (j, swap_with)} sorting
end.
swaps
)

```

Try it online!

---

# original answer, doesn't work for repeats

# , 18 bytes

```
[:;(2]\])&.>@C.@/:

```

Try it online!

*NOTE: Thanks to Neil for pointing out this currently fails on the test case `4 5 2 1 3 3`.*

* `/:` Grade up, ie, return the permutation that puts the list into order
* `C.@` Convert that to cyclic permutation form, which uses boxes
* `&.>` For each of those boxed lists, ie, permutation cycles...
* `(2]\])` Return all consecutive pairs of two elements. This gives us the swaps, and it works because J gives the cycle list in descending order.
* `[:;` raze the list of boxes. This gives us all the swap pairs as a single list of pairs, ie, an N x 2 matrix.

# Answer
> 3 votes
# Wolfram Language (Mathematica), ~~219~~ ~~188~~ 184 bytes

```
F@A_:=MinimalBy[##&@@@f/@#[[1]]&@*(FindPermutation@A~PermutationProduct~#&)/@GroupElements@PermutationGroup[Cycles@*List/@Join@@((f=Partition[#,2,1]&)/@Values@PositionIndex@A)],Length]

```

Try it online!

-31 bytes thanks to @Chris

-4 bytes by making the code much faster (no more GroupSetwiseStabilizer slowness)

Thanks to @NickKennedy for pointing out that the first version failed on non-unique list entries. The present version is a tour-de-force that calculates the permutation group that leaves the list unchanged, then tries each element of this group to see if it can be used to shorten the result.

This code still goes very slowly on massively duplicated lists.

Explicit code:

```
A = {4,5,2,1,3,3,10,9,7,6,8,8}
  (* compute the indices of equal elements *)
Q = Values[PositionIndex[A]]
  (* compute the permutation group that leaves A invariant *)
G = PermutationGroup[Cycles@*List /@ Join @@ (Partition[#, 2, 1] & /@ Q)]
  (* find the permutation that sorts A and combine it with every element of G *)
F = PermutationProduct[FindPermutation[A], #] & /@ GroupElements[G]
  (* convert every resulting permutation to the desired form *)
J = Join @@ (Partition[#, 2, 1] & /@ #[[1]]) & /@ F
  (* pick the shortest solutions *)
MinimalBy[J, Length]

```

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