title: Multiplication in the Steenrod Algebra

text:
# Question
Title: Multiplication in the Steenrod Algebra
Here's yet another Steenrod algebra question. Summary of the algorithm: I have a procedure that replaces a list of positive integers with a list of lists of positive integers. You need to repeatedly map this procedure over a list of lists and flatten the output until you reach a fixed point. Then for each sublist, if it appears an odd number of times, delete all but one occurrence. If it appears an even number of times, delete all occurrences. There is reference code at the bottom. The procedure for replacing a list with a list of lists is determined by a formula called the "Adem relation."

In order to represent an algebra, we need to know a basis for the algebra and also how to multiply things. From my previous question, we know the basis of the Steenrod algebra. In this question we're going to learn how to multiply Steenrod squares. The Steenrod algebra is generated by Steenrod squares \\$\mathrm{Sq}^{i}\\$ for \\$i\\$ a positive integer. It has a basis consisting of "admissible monomials" in the Steenrod squares.

A sequence of positive integers is called *admissible* if each integer is at least twice the next one. So for instance `[7,2,1]` is admissible because \\$7 \geq 2\*2\\$ and \\$2 \geq 2\*1\\$. On the other hand, `[2,2]` is not admissible because \\$2 \< 2\*2\\$. So \\$\mathrm{Sq}^7\mathrm{Sq}^2\mathrm{Sq}^1\\$ is an admissible monomial, but \\$\mathrm{Sq}^2\mathrm{Sq}^2\\$ is not.

Every inadmissible Steenrod monomial can be expressed as a sum of admissible Steenrod monomials. For example \\$\mathrm{Sq}^2\mathrm{Sq}^2 = \mathrm{Sq}^3\mathrm{Sq}^1\\$, where we see that the right hand side is admissible because \\$3\>2\*1\\$. As another example, \\$\mathrm{Sq}^2\mathrm{Sq}^3 = \mathrm{Sq}^5 + \mathrm{Sq}^4\mathrm{Sq}^1\\$.

Our goal is to express inadmissible Steenrod monomials as sums of admissible ones. There is a formula to express an inadmissible product of two Steenrod squares as a sum of admissible monomials called the *Adem relation*:

\\$\displaystyle\mathrm{Sq}^{a}\mathrm{Sq}^{b} = \sum\_{j=0}^{a/2} \binom{b-j-1}{a-2j} \mathrm{Sq}^{a+b-j}\mathrm{Sq}^{j} \quad\text{for a \< 2\*b}\\$

where it's understood that \\$\mathrm{Sq}^{a+b}\mathrm{Sq}^0 = \mathrm{Sq}^{a+b}\\$ and where the binomial coefficients are taken mod 2. In fact all arithmetic on Steenrod monomials is computed mod 2, so for instance \\$\mathrm{Sq}^2\mathrm{Sq}^1 + \mathrm{Sq}^2\mathrm{Sq}^1 = 0\\$.

The algorithm to express a Steenrod monomial as a sum of admissible ones is to repeatedly find the location of an inadmissible pair, apply the Adem relation and get a sum of monomials and recurse on the resulting sum.

## Goal:

Take as input a list representing a Steenrod monomial. Output the set of the admissible Steenrod monomials that appear in the reduced sum. This can be represented as a list without repeats or as any sort of set / dictionary / map, where presence of a key in the map determines whether a monomial is in the set. This is code golf so shortest code wins.

## Helpful Formulas for Mod 2 Binomial coefficients

\\$\displaystyle\binom{n}{k} =\begin{cases} 1 & n | k = n\\ 0 & \text{else}\end{cases} = \begin{cases} 1 & (n-k) \\& k = 0\\ 0 & \text{else}\end{cases}\\$ where \\$|\\$ and \\$\\&\\$ are bit-or and bit-and.

## Examples:

```
Input: [4,2]
Output: [[4,2]]

```

Since \\$4 \geq 2\*2\\$ the sequence is already admissible and nothing needs to be done.

```
Input: [2,4]
Ouput: [[6], [5,1]] (order doesn't matter)

```

\\$2 \< 2\*4\\$ and the sequence has length 2 so we just need to apply the Adem relation once. We get

\\$\mathrm{Sq}^2\mathrm{Sq}^4 = \displaystyle\sum\_{j=0}^{1} \binom{3-j}{2-2j} Sq^{6-j}Sq^j = \binom{3}{2}\mathrm{Sq}^6 + \binom{2}{0}\mathrm{Sq}^5\mathrm{Sq}^1 = \mathrm{Sq}^6 + \mathrm{Sq}^5\mathrm{Sq}^1\\$ where we used \\$3\\%2=1\\$.

```
Input: [2,4,2]
Output: [[6, 2]]

```

The pair `[2,4]` or \\$\mathrm{Sq}^2\mathrm{Sq}^4\\$ is inadmissible so applying the Adem relation there we get \\$\mathrm{Sq}^2\mathrm{Sq}^4\mathrm{Sq}^2 = \mathrm{Sq}^6\mathrm{Sq}^2 + \mathrm{Sq}^5\mathrm{Sq}^1\mathrm{Sq}^2\\$. Now \\$6\>2\*2\\$ so \\$\mathrm{Sq}^6\mathrm{Sq}^2\\$ is admissible and can be left alone. On the other hand, \\$1 \< 2\*2\\$ so there is more work to do on the other term. \\$\mathrm{Sq}^1\mathrm{Sq}^2 = \mathrm{Sq}^3\\$ so \\$\mathrm{Sq}^5\mathrm{Sq}^1\mathrm{Sq}^2 = \mathrm{Sq}^5\mathrm{Sq}^3\\$.

Since \\$5\<2\*3\\$ this can be reduced again and in fact \\$\mathrm{Sq}^5\mathrm{Sq}^3 = 0\\$. So \\$\mathrm{Sq}^2\mathrm{Sq}^4\mathrm{Sq}^2 = \mathrm{Sq}^6\mathrm{Sq}^2\\$.

```
Input: [2, 3, 2]
Output: []

```

Both `[2,3]` and `[3,2]` are inadmisible pairs so we can start in either location here. \\$\def\Sq{\mathrm{Sq}}\Sq^3\Sq^2=0\\$, so if we start in the second position, we immediately see the output is empty. Starting in the first position, we have \\$\Sq^2\Sq^3 = \Sq^5 + \Sq^4\Sq^1\\$. Then \\$\Sq^5\Sq^2\\$ is admissible, but \\$\Sq^4\Sq^1\Sq^2\\$ isn't.

\\$\Sq^4\Sq^1\Sq^2 = \Sq^4\Sq^3 = \Sq^5\Sq^2\\$ so the answer is \\$\Sq^5\Sq^2 + \Sq^5\Sq^2 = 0\\$ (all of our arithmetic is reduced mod 2).

## Test cases:

```
Input: [1, 1]
Output: []

Input: [2,2]
Output: [[3,1]]

Input: [2, 2, 2]
Output: [[5,1]]

Input: [2,2,2,2]
Output: []

Input: [4, 2, 4, 2]
Output: [[8,3,1], [10,2]] (Again, order doesn't matter)

Input: [2, 4, 2, 4]
Output: [[8,3,1],[9,2,1],[9,3],[10,2],[11,1]]

Input: [6, 6, 6]
Output: [[12, 5, 1], [13, 4, 1], [13, 5]]

Input: [6,6,6,6]
Output: []

Input: [4, 2, 1, 4, 2, 1, 4, 2, 1]
Output: [[15,5,1],[17,3,1]]

Input: [4, 2, 1, 4, 2, 1, 4, 2, 1, 4, 2, 1]
Output: []

```

## Reference Implementations:

There is a javascript calculator here, which is an easy way to get more test cases. https://math.berkeley.edu/~kruckman/adem/

Here is a python implementation:

```
def make_mono_admissible(result, mono):
    """Reduce a Steenrod monomial into a linear combination of admissible Steenrod monomials
       "mono" should be a tuple representing your Steenrod monomial.
       Writes answer into "result" which should be an empty dictionary.
    """
    inadmissible_indices = [j for j in range(len(mono) - 1) if mono[j] < 2*mono[j+1]]
    if not inadmissible_indices:
        if mono in result:
            del result[mono]
        else:
            result[mono] = 1
        return
    i = inadmissible_indices[0]
    a = mono[i]
    b = mono[i + 1]
    # Do adem relation for Sq^a Sq^b
    for j in range(1 + a//2):
        # check if binom(b - j - 1, a - 2j) % 2 == 1
        if (b - a + j - 1) & (a-2*j) == 0:
            new_pair = (a+b-j, j) if j>0 else (a+b,)
            make_mono_admissible(result, mono[:i] + new_pair + mono[i+2:])

```

As I was trying to make a TLDR, I made the following Mathematica code:

```
makeMonoAdmissibleStep[{a___Integer}] := {{a}}
(* If a < 2b for consecutive entries we can apply Adem relation *)
makeMonoAdmissibleStep[{start___, {p___, a_, b_, q___}, rest___}] /; a < 2 b :=
{start,
   Sequence@@
     (* If the mod 2 binomial coefficient is 1,
        add a new list with a, b replaced by a+b-#, # *)
     If[Mod[Binomial[b - # - 1, a - 2 #], 2] == 1, {p, a + b - #, # , q}, 0]&
         /@ Range[0, a/2],
 rest}] /. 0 -> Sequence[]
(* If the same list appears twice, drop it *)
makeMonoAdmissibleStep[{a___, x_List, b___, x_List, c___}] := {a, c}
(*If we can't do anything else, we're done *)
makeMonoAdmissibleStep[x_] := x
makeMonoAdmissible[l_] := FixedPoint[makeMonoAdmissibleStep, l]

```

# Answer
> 4 votes
# Wolfram Language (Mathematica), ~~225~~ ~~218~~ ~~206~~ ~~203~~ ~~200~~ 196 bytes

```
q=SetAttributes
{p,s}~q~Flat
s~q~Orderless
a_~s~a_:=s[]
p@0:=p[]
f=FixedPoint[#~Distribute~s&/@#/.a_~p~b_/;a<2b:>s@@(If[BitAnd[b+#-a-1,a-2#]<1,p[a+b-#,#],s[]]&)/@Range[0,a/2]&,s[p@@#]]/.s|p->List&

```

Try it online!

We represent the intermediate list as an expression with `[[15,5,1],[17,3,1]]` being `s[p[15,5,1], p[17,3,1]]`. In this format, Mathematica's expression engine does some heavy lifting, and allows us to use `Distribute`. However, it takes some work to convert between this format and lists.

---
Tags: code-golf, math, combinatorics, topology
---


title: Evaluate a Dice 10,000 roll

text:
# Question
Title: Evaluate a Dice 10,000 roll
## Introduction

Dice 10,000 is a dice game which can be played with 6 dice and something to write. Players roll the dice multiple times a turn and gain a score at the end of it. The player who reaches 10,000 point first wins the game. Calculating the score of one roll is your job in this challenge.
Look here for the full rules.
*Please note that the rules (especically the scoring) change from region to region since the game is widely known. We use the rules descibed below.*

## The Challenge

Given a list of six numbers from one to six representing a dice roll, output their score. The score is calculated in the follwing way:

* Ones counts **100** points
* Fives counts **50** points
* Triplets count their number **times 100** points. Three twos for example give 200 points. An exception are three ones which count **1000** points.
* Six of the same number count like two triplets as described above. So six threes give 600 points. The same goes for the edge case with the ones: Six ones are 2,000 points.
* One die can't be used more than once. If a die is part of a triplet, it does not count for other scorings. The fives in a triplet do **not** count 50 points in addition to the 500 points they give.
* Triples are always counted first to maximize the score. So three fives are never counted as 150 points. Four fives are counted as one triplet and one ordinary five which then gives 550 points.

### Notes

* The input will always contain six numbers from one to six. You will not recieve invalid input.
* The numbers can be in any order. You may not assume any specific ordering.

# Rules

* Input format is up to you as long as it's not preprocessed.
* Function or full program allowed.
* Default rules for input/output.
* Standard loopholes apply.
* This is , so lowest byte-count wins. Tiebreaker is earlier submission.

# Test cases

```
[1, 2, 3, 4, 5, 6] -> 150
[1, 1, 1, 2, 3, 5] -> 1050
[1, 1, 1, 1, 1, 1] -> 2000
[2, 2, 2, 2, 2, 2] -> 400
[6, 6, 1, 5, 5, 6] -> 800
[2, 3, 4, 6, 2, 4] -> 0
[1, 5, 1, 5, 1, 5] -> 1500
[5, 5, 5, 5, 2, 3] -> 550
[1, 1, 1, 1, 1, 5] -> 1250
[3, 3, 4, 4, 3, 4] -> 700

```

# Answer
# 05AB1E, ~~34~~ ~~31~~ 30 bytes

```
7G¹N¢O3‰N*2LRN1Q+°*X5‚Nå_i¨}OO

```

**Explanation**

```
7G                                  # for N in 1..6
  ¹N¢O                              # count number of occurrences of N in input
      3‰                            # divmod 3
        N*                          # multiply by N
          2LRN1Q+°*                 # multiply by 10, 100 or 1000
                   X5‚Nå_i¨}        # if N is not 1 or 5, scrap the singles
                            OO      # sum all triple and single scores so far
                                    # implicitly display total sum

```

Try it online
> 6 votes

# Answer
# Python 2, ~~152~~ ~~148~~ 125 bytes

Pretty simple solution. Can be golfed more. `L.count` is a bit long, but I couldn't remove the first call because L is updated.

```
def f(L):s=n=0;exec"n+=1\nwhile L.count(n)>2:s+=[n*100,1e3][n<2];exec'L.remove(n);'*3\n"*6;C=L.count;print s+100*C(1)+50*C(5)

```

**Try it online** \- (all test cases)

**Ungolfed:**

```
def f(L,s=0):
    L.sort()
    for n in range(1,7):
        while L.count(n)>2:
            s+=n*100*((n<2)*9+1) # multiply by 10 if n==1
            i=L.index(n)
            L=L[:i]+L[i+3:]
    s+=100*L.count(1)+50*L.count(5)
    print s

```

*Some golf credit to @Copper, using some tips from his code*
> 4 votes

# Answer
## PowerShell ~~v2+~~ v3+, ~~147~~ ~~144~~ ~~137~~ 133 bytes

```
$n=$args[0]|sort;while($n){if(($x=$n[0])-eq$n[2]){$s+=100*$x+900*($x-eq1);$a,$b,$n=$n}else{$s+=50*($x-in1,5)+50*($x-eq1)}$a,$n=$n};$s

```

<sub>*Crossed out 144 looks kinda like 144?*</sub>

Takes input `$args[0]` and `sort`s it, stores it into `$n`. Then, `while` there are still elements left, we evaluate an `if`/`else`.

If the first element (temp stored into `$x` to save some bytes) matches the third element, we have a triple. Add onto the `$s`um the result of some multiplication `100*$x` plus a Boolean-based `900` only if `$x` is `-eq`ual to `1`. This gets us the requisite `1000` for three ones. Then, peel off the first two elements into `$a`, and `$b`, and the remaining into `$n` -- removing the third element of the triple is handled later.

Otherwise, we don't have a triple, so add on to `$s`um the result of another Boolean-based addition. We add `50` if `$x` is either `1` or `5`, then add on another `50` if it's `-eq`ual to `1`. This section now requires v3+ for the `-in` operator.

In either case, we still have an element yet to remove, so peel off the first element into `$a` and leave the remaining in `$n`.

Finally, once the loop is done, place `$s` on the pipeline. Output is an implicit `Write-Output` at the end of execution.

### Test cases

```
PS C:\Tools\Scripts\golfing> (1,2,3,4,5,6),(1,1,1,2,3,5),(1,1,1,1,1,1),(2,2,2,2,2,2),(6,6,1,5,5,6),(2,3,4,6,2,4),(1,5,1,5,1,5),(5,5,5,5,2,3),(1,1,1,1,1,5),(3,3,4,4,3,4)|%{($_-join',')+" -> "+(.\evaluate-dice-1000.ps1 $_)}
1,2,3,4,5,6 -> 150
1,1,1,2,3,5 -> 1050
1,1,1,1,1,1 -> 2000
2,2,2,2,2,2 -> 400
6,6,1,5,5,6 -> 800
2,3,4,6,2,4 -> 0
1,5,1,5,1,5 -> 1500
5,5,5,5,2,3 -> 550
1,1,1,1,1,5 -> 1250
3,3,4,4,3,4 -> 700

```
> 4 votes

# Answer
# Ruby, ~~80~~ 78 bytes

Try it online!

-2 byte from @ezrast.

```
->d{s=0;7.times{|i|c=d.count i;i<2&&i=10;s+=c>2?c/3*i*100:1>i%5?c%3*i*10:0};s}

```
> 3 votes

# Answer
## JavaScript (ES6), ~~87~~ 86 bytes

```
a=>a.sort().join``.replace(/(.)\1\1|1|5/g,s=>r+=s>>7?s/1.11:s>5?1e3:s>1?50:100,r=0)&&r

```

Sorts and stringifies the input so that scoring combinations can be identified by means of regexp. Edit: Saved 1 byte thanks to @Arnauld.
> 3 votes

# Answer
# Python 2 or 3, ~~123 122 121 116 109 108 104 102 100~~ 97 bytes

**Python 2, 97 bytes**

```
lambda r:100*sum(c/3*((v<2)*9+v)+c%3*(v<2or(v==5)/2.)for v,c in enumerate(map(r.count,range(7))))

```

Test cases are on **ideone**

**Python 3, 97 bytes**

```
lambda r:100*sum(c//3*((v<2)*9+v)+c%3*(v<2or(v==5)/2)for v,c in enumerate(map(r.count,range(7))))

```
> 3 votes

# Answer
## Haskell, ~~130~~ 123 bytes

This is *not* a challenge for Haskell. Also I am in golfing this.

Thanks to @nimi.

```
import Data.List
f=g.sort
g(x:a@(y:z:b))|x>z=j x+g a|0<1=100*h x+g b
g(x:y)=j x+g a
g _=0
h 1=10
h x=x
j 1=100
j 5=50
j _=0

```
> 2 votes

# Answer
# Python 3, 131 bytes

```
lambda r,C=list.count:sum([x%7*100,1e3][x%7<2]*(C(r,x%7)>2and not exec('r.remove(x%7);'*3))for x in range(14))+50*C(r,5)+100*C(r,1)

```

This is a lambda expression; to use it, assign it by prepending `f=`.

We first check for triples twice (by using modulus), removing the triples as we go; then we simply add the counts of `5` and `1` to the score and return it.

Try it on Ideone! (with all test cases)

Here's my older Python 2 submission:

## Python 2, ~~176~~ ~~172~~ ~~171~~ ~~145~~ ~~136~~ ~~134~~ 133 bytes

```
def e(r):s=x=0;exec'x+=1;a=x%7;\nif r.count(a)>2:exec"r.remove(a);"*3;s+=[a*100,1e3][a<2]\n'*14;C=r.count;s+=50*C(5)+100*C(1);print s

```

*Saved a byte on the Python 2 solution thanks to @mbomb007!*
> 1 votes

# Answer
# BASH (sed + bc) 161

```
sed -re's/([1-6])(.*)\1(.*)\1/\100\2\3/g;s/([1-6])( .*)\1( .*)\1/\100\2\3/g;s/10/1/g; s/1/100/g;s/5( |$)/50 /g;s/[1-6][^0]//g;s/ +/+/g;s/(^\+|\+$)//g;s/^$/0/'|bc

```

I wanted to do it all in sed, but addition is really hard...

Explanation:

1. Find a triplet, add `00` to the first number and remove the other
e.g. `1 2 1 3 1 4` -\> `100 2 3 4`
2. Repeat step 1 incase there are two triples
3. Replace `10` with `1` then `1` with `100`
e.g. `100` -\> `10` -\> `1000` or `1` -\> `1` -\> `100`
4. Replace each `5` not followed by `0` with `50`
5. Remove any number that doesn't end in `0`
6. Replace groups of spaces with `+`
7. Remove leading and trailing `+`s
8. If the string is empty, add a `0`
9. Lastly pipe to `bc` to add everything up.
> 1 votes

# Answer
## Javascript (ES6), ~~85~~ 84 bytes

```
x=>x.map(v=>s+=v*(((z+=1<<v*3)>>v*3&7)%3?v-5?v-1?0:10:1:v-5?v-1?10:80:8),s=z=0)|10*s

```

Test cases:

```
let F =
x=>x.map(v=>s+=v*(((z+=1<<v*3)>>v*3&7)%3?v-5?v-1?0:10:1:v-5?v-1?10:80:8),s=z=0)|10*s

console.log(F([1, 2, 3, 4, 5, 6])); // 150
console.log(F([1, 1, 1, 2, 3, 5])); // 1050
console.log(F([1, 1, 1, 1, 1, 1])); // 2000
console.log(F([2, 2, 2, 2, 2, 2])); // 400
console.log(F([6, 6, 1, 5, 5, 6])); // 800
console.log(F([2, 3, 4, 6, 2, 4])); // 0
console.log(F([1, 5, 1, 5, 1, 5])); // 1500
console.log(F([5, 5, 5, 5, 2, 3])); // 550
console.log(F([1, 1, 1, 1, 1, 5])); // 1250
console.log(F([3, 3, 4, 4, 3, 4])); // 700
```
> 1 votes

# Answer
# Perl, 69 bytes

Includes +2 for `-ap`

Run with the input on STDIN:

```
dice10000.pl <<< "5 1 1 1 1 1"

```

`dice10000.pl`:

```
#!/usr/bin/perl -ap
$_=join 0,sort@F,A;print;s%(10|\d)\1\1|10|5%$n+=$1.0||$&%eg;$_=$n.0

```
> 1 votes

# Answer
# C# (.NET Core), ~~228~~ 227 bytes

```
class A{static void Main(string[] a){int[] x=new int[7];int i=0,s=0;for(;i<6;i++)x[int.Parse(a[i])]++;while(i>0){while(x[i]>2){s+=i>1?10*i:100;x[i]-=3;}i--;}while(x[1]-->0)s+=10;while(x[5]-->0)s+=5;System.Console.Write(s*10);}}

```

Try it online!

I feel like I'm missing many, many potential optimizations here, but I *did* save a byte by multiplying by 10 at the end. Input should be passed as separate command line args.
> 0 votes

# Answer
# Perl 5 `-ap`, 78 bytes

```
$_=join'',sort@F;s|(\d)\1\1|!($\+=$1*($1-1?2:20))|ge;$\+=y/5//+2*y/1//}{$\*=50

```

Try it online!
> 0 votes

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


title: Implement the EnScript CHS command

text:
# Question
Title: Implement the EnScript CHS command
JonoCode9374 had almost completely implemented my language EnScript except for the CHS command. I was impatient of waiting for them to implement this command, so I chose to put this question here.

## Challenge:

Write a solution that takes an input and returns the chased output. Standard loopholes are forbidden.

This is the CHS instruction reference copied from the website:

> CHS means to chase all of the numbers inside an accumulator.
>
> Chasing a number means to move a number forward inside the accumulator that-number of times.

Chasing an accumulator means to move all of the numbers inside an accumulator from the lowest number (0) to the highest number (9) **sequentially**, without repeating. **Sequentially means: the values are moved in a sequential order that was presented in the accumulator, which is from left to right.**

* **Here is an important note:** The number is still there while the number is moved, and that number will be removed from the original number if and only if the currently chased number has been put in place.
* **Here is an extra note:** A number with the lower magnitude should be "chased" first in the accumulator. For example, the number 1 should be chased prior to the numbers 2, 3, 4, etc.
* **One more note:** Accumulators should be unbounded, i.e. without an upper limit. Also, they cannot and **should not** support negative numbers. The implementation does not have to detect that; it can assume that the input is valid.
* The type of the accumulators should be in the unbounded integer form; The value of an accumulator should not be a floating-point integer.
* If zeroes are in front of the number at the end of the process, they are deleted by default.

## Examples:

* Take A=123 as an example.
* Value `1` will move forward 1 number. (It will be inserted behind `2`.) So, the number will be `213`. 1 will be marked as chased.
* Likewise, `2` will also be moved. It will be moved forward twice, so the number will be `132`.
* `3` will also be chased. It will move forward 1 time (finding that the end of the list is reached), and then it will go to the place before `1`. Then, it will go back to where it was.
* Accumulator A "chased" will be `132`.

Also, take `3112` as an example, which is quite vague. Some people may ask: which '1' gets "chased" first?

Answer: The first '1' from left to right gets "chased" first. See the notes from above.

So, the chase after 1 iteration will be: 31121324→31131224

Another example. 10 will be chased to 01, as 0 cannot be moved and 1 will be moved for 1 digit. Then, this preceding 0 will be deleted, leaving a 1 to the accumulators.

## Test Cases:

```
123 -> 132
12345 -> 14253
3141 -> 3141
123123 -> 312132
94634 -> 96434
1277 -> 7172
10 -> 1

```

Please comment for me if this question is too vague!

# Answer
# Python 3, ~~262~~ ... 170 bytes

This program outputs the result via Stderr.

I'm a bit out of practice at golfing, since I have not been too active lately, so I'm sure it can be golfed more.

```
L=[[c,int(c)]for c in input()]
while 1:i=L.index(min([x for x in L if x[1]]or exit(str(int("".join(x[0]for x in L))))));L[i][1]-=1;q=i+1<len(L)and-~i;L.insert(q,L.pop(i))

```

**Try it online**

### Ungolfed

```
# Index to shift, Times remaining
def Shift(i, t):
    if t<1:
        L[i][1]=0
        return
    if i+1<len(L):
        L[i],L[i+1]=L[i+1],L[i]
        Shift(i+1,t-1)
    else:
        L.insert(0,L.pop())
        Shift(0,t-1)
L=[[c,1]for c in input()]
while 1:
    t=[x for x in L if x[1]]or exit("".join(x[0]for x in L).lstrip('0'))
    i=L.index(min(t,key=lambda x:x[0]))
    Shift(i,int(L[i][0]))

```
> 3 votes

---
Tags: code-golf
---


title: Row, row, row your boat

text:
# Question
Title: Row, row, row your boat
Everyone is likely familiar with the following song, which is a musical round:

# Background

Fewer people might recall trying to sing the 4-person version of this with a few friends and failing. Offsetting the lyrics of a song with different harmonious pitches is known as singing a "round" and that's what we're here to simulate today using static output. Here's an example of someone actually performing the piece (link to audio/video, will have sound).

# The Challenge

**This challenge is to output the text as follows exactly as it follows:**

```
Row, row, row your boat,           |-----------------------------------|-----------------------------------|-----------------------------------
Gently down the stream.            |Row, row, row your boat,           |-----------------------------------|-----------------------------------
Merrily, merrily, merrily, merrily,|Gently down the stream.            |Row, row, row your boat,           |-----------------------------------
Life is but a dream.               |Merrily, merrily, merrily, merrily,|Gently down the stream.            |Row, row, row your boat,
-----------------------------------|Life is but a dream.               |Merrily, merrily, merrily, merrily,|Gently down the stream.
-----------------------------------|-----------------------------------|Life is but a dream.               |Merrily, merrily, merrily, merrily,
-----------------------------------|-----------------------------------|-----------------------------------|Life is but a dream.

```

# Rules

* Trailing whitespace is acceptable, but not required, this includes newlines.
* Hyphens and bars are part of the required output, yes.
* Commas, periods, capitalization and all syntactical elements related to grammar are required.

This is , the lowest byte-count code without using standard loopholes is the winner.

# Answer
> 12 votes
# 05AB1E, ~~80~~ 77 bytes

```
“¢ã,¢ã,¢ã€žžÄ,““èî„‹€€šæ.“"merrily, "4×¨“‚ì€ˆ€³€…žâ.“'-35×Ð)€ª.B3FDÁ})øvy'|ý,

```

Try it online!

Work in progress.

# Answer
> 10 votes
# , ~~139~~, 128 bytes

```
iLife is but a dream ±µ |4amerrily, x7b~A|Gently down the stream.±² |3arow, X5b~Ayour boat,±± |3I³µ-|3AòÄó.û-}|ò5DÎ4f|C|

```

A one-liner! (sortof :P)

Try it online!

Hexdump:

```
00000000: 694c 6966 6520 6973 2062 7574 2061 2064  iLife is but a d
00000010: 7265 616d 20b1 b520 7c1b 3461 6d65 7272  ream .. |.4amerr
00000020: 696c 792c 201b 7837 627e 417c 4765 6e74  ily, .x7b~A|Gent
00000030: 6c79 2064 6f77 6e20 7468 6520 7374 7265  ly down the stre
00000040: 616d 2eb1 b220 7c1b 3361 726f 772c 201b  am... |.3arow, .
00000050: 5835 627e 4179 6f75 7220 626f 6174 2cb1  X5b~Ayour boat,.
00000060: b120 7c1b 3349 b3b5 2d7c 1b33 4101 1bf2  . |.3I..-|.3A...
00000070: c4f3 2efb 2d7d 7cf2 3544 ce34 667c 437c  ....-}|.5D.4f|C|

```

Do I get bonus points for landing exactly on `2^7`?

This took a while to figure out. I'm hoping I can golf tons off like my keyboard ASCII art answer, but I'm not sure. We'll see. They are very similar challenges (and both very fun :D)

Originally I tried this (180):

```
3irow, ch your boat,±± ||"rCLife is but a dream.±µ ||"lD4imerrily, r||"mCGently down the stream.±² ||"gC³µ-|B"dCR³D
GRDD
MGRD
LMGR
DLMG
DDLM
³DLÍR/r
ÍG/g
ÍM/m
ÍL/l
ÍD/d

```

Try it online!

Which inserts this:

```
RDDD
GRDD
MGRD
LMGR
DLMG
DDLM
DDDL

```

and then does substitution to expand it out. But building it style is much shorter (and more fun TBH)

# Answer
> 6 votes
## Batch, ~~292~~ ~~288~~ 275 bytes

```
@set d=-------
@set "d=%d%%d%%d%%d%%d%^|
@set "m=M_ m_ m_ m_^|
@set "s=           ^|
@set "s=Life is but a dream.    %s%%m:_=errily,%Gently down the stream. %s%Row, row, row your boat,%s%%d%%d%%d%"
@for /l %%i in (1,1,6)do @call:c
:c
@echo %s:~111,146%
@set "s=%d%%s%

```

Edit: Saved 13 bytes by rewriting the code to use a version of the substring trick I used in my Retina answer. Conveniently I can loop six times and then fall through for a seventh iteration of the loop body, which means the quoting needed to output `|`s doesn't get too onerous, however I have to be careful to take the `^`s into account when selecting the substring.

# Answer
> 6 votes
# Python 3, ~~252~~ ~~235~~ ~~208~~ ~~206~~ 205 bytes

Alright, alright. Here's a less boring answer:

```
w=' '*11
t=["Row, row, row your boat,"+w,"Gently down the stream. "+w,"Merrily,"+" merrily,"*3,"Life is but a dream.    "+w,*['-'*35]*3]
for a in zip(*[t[z:]+t[:z]for z in range(7,3,-1)]):print(*a,sep='|')

```

**Old answer, 252 bytes:**

Boring answer, and the other Python answer is shorter, but I thought I'd try if this approach is shorter. Python 3 despite the savings in byte/string 2-3 difference because both `gzip` and `base64` are shittier in Python 2.

```
from base64 import*
from gzip import*
print(decompress(b85decode('ABzY8Fgf~I0{;ujFV|5hf)Waq`K3h)N%@H-ItmC-qe~c2OAVKMYF<fBr9w)6d7eT^Myf(_Nl|KIuATz2dxGfaW-i~<qN2>4N*#q<oQxVex|z!-Gc8pivsfXiv_v6MAqB%CkU6w=GZ!&|OJj#}Q7chW$(>wu%p_Rd3;?AKH=M}>000')).decode())

```

# Answer
> 5 votes
# PowerShell, ~~224~~ ~~207~~ 202 bytes

```
$a=' '*11;0..6|%{((0..4+4+4)[($_,($_+=6),--$_,--$_|%{$_%7})]|%{("Row, row, row your boat,$a","Gently down the stream.$a ","Merrily,$(' merrily,'*3)","Life is but a dream.$a    ",('-'*35))[$_]})-join'|'}

```

Try it online! *(the output is wrapped if your screen isn't wide enough)*

Good grief, this array generation thing is ugly, but it saved 17 bytes, so ...

```
0..6|%{((0..4+4+4)[($_,($_+=6),--$_,--$_|%{$_%7})]

```

We loop from `0` to `6`. Each iteration, we're indexing into an array `(0,1,2,3,4,4,4)`. The indexing is based on the current digit, the current digit `+6`, that `-1`, and then *that* `-1`. Each of *those* is then fed through a loop where we modulo with `%7`. For example, if we're on `0` of the outer `0..6` loop, then these would be `0,6,5,4`, then each `%7`, so `0,6,5,4`. That's indexed into the `(0,1,2,3,4,4,4)` array, so the output is `0,4,4,4`. For input `1` we get `1,7,6,5` then `1,0,6,5` which yields `1,0,4,4`. And so on. *(things would be so much easier if we had a `.clamp` function)*

Those are one-at-a-time spit into a loop `|%{}`. Each iteration, we index into the proper spot in the song-lyrics-array, and leave that string on the pipeline. Those strings are then `-join`ed together with `|` to format the output line. Those strings are left on the pipeline and output is implicit.

*Saved some bytes thanks to Value Ink.*

# Answer
> 4 votes
# JavaScript (ES8), ~~285~~ ~~256~~ ~~240~~ ~~231~~ ~~229~~ ~~217~~ ~~214~~ ~~213~~ ~~211~~ ~~210~~ 206 bytes

```
_=>"0444104421043210432144324443".replace(/./g,(x,y)=>["Row, row, row your boat,","Gently down the stream.","Merrily,"+(m=" merrily,")+m+m,"Life is but a dream.","-".repeat(35)][x].padEnd(35)+`
|||`[++y&3])

```

Saved a few bytes by borrowing a trick from Arnauld's answer

Try it online!

# Answer
> 4 votes
# PHP, 191 Bytes

```
for(;$n<7;$n++)for($m=0;$m<4;)echo $m?"|":"\n",str_pad($i=["Row, row, row your boat,","Gently down the stream.",M.($t="errily,")." m$t m$t m$t","Life is but a dream."][$n-$m++],35," -"[!$i]);

```

Try it online!

Expanded

```
for(;$n<7;$n++)
  for($m=0;$m<4;)
    echo $m?"|":"\n"
     ,str_pad($i=["Row, row, row your boat,","Gently down the stream."
       ,M.($t="errily,")." m$t m$t m$t","Life is but a dream."][$n-$m++]
       ,35," -"[!$i]);

```

# Answer
> 3 votes
# Python 2, 199 bytes

```
w=' '
s=['-'*35]
t=['Row, row, row your boat,'+w*11,'Gently down the stream.'+w*12,'Merrily,'+' merrily,'*3,'Life is but a dream.'+w*15]
print'\n'.join(map('|'.join,zip(t+s*3,s+t+s+s,s+s+t+s,s*3+t)))

```

Try it online!

---

Thanks to @mathjunkie for saving 14 bytes

# Answer
> 2 votes
# CJam, ~~128~~ 122 bytes

```
"Row, row, row your boat,""gently down the stream."'M" merrily,"4*2>+"Life is but a dream."'-35*__]{35Se]}%a4*4,.m>z'|f*N*

```

Try it online!

**Explanation**

```
"Row, row, row your boat,"  e# Push this string.
"gently down the stream."   e# Push this string.
'M                          e# Push the character 'M'.
" merrily,"4*               e# Push the string " merrily, merrily, merrily, merrily,".
2>+                         e# Remove the first two letters of it, and append it to 'M',
                            e#   fixing the capitalization.
"Life is but a dream."      e# Push this string.
'-35*__                     e# Push a string containing 35 hyphens and make two copies of it.
]                           e# Collect all these strings in an array.
{35Se]}%                    e# Pad each of them to length 35 by adding spaces to the right.
a4*                         e# Repeat the array 4 times.
4,                          e# The range [0 1 2 3].
.m>                         e# Rotate each subarray of strings rightward by the corresponding
                            e#   number in the range.
z                           e# Transpose the array.
'|f*                        e# Join the strings on each row with '|' characters.
N*                          e# Join the rows together with newlines.

```

# Answer
> 2 votes
## JavaScript (ECMAScript 2017), ~~191~~ ~~187~~ 182 bytes

*Saved 3 bytes thanks to Shaggy*

```
f=(i=27,s=['Life is but a dream.','Merrily,'+(m=' merrily,')+m+m,'Gently down the stream.','Row, row, row your boat,'][(i>>2)-i%4]||'')=>i?s.padEnd(35,' -'[+!s])+`
|||`[i&3]+f(i-1):s

o.innerHTML = f();
```

```
<pre id=o style="font-size:10px"></pre>
```

# Answer
> 2 votes
# C (GCC), ~~231~~ 230 bytes

-1 byte thanks to ceilingcat!

```
#define m"errily, "
char s[7][35]={"Life is but a dream.","M"m"m"m"m"m"m"m,"Gently down the stream.","Row, row, row your boat,"};f(l,c){memset(s[4],45,'k');for(l=7;l--;)for(c=0;c<4;)printf("%-35.35s%c",s[(4+l+c++)%7],"|||\n"[c]);}

```

Pretty straightforward. First it builds the 7 lines string array, part via a macro to factorise out the "merrily" part, then the lines of dashes are filled in with a `memset`. Then the lines are printed with the adequate offset and separators.

Try it online!

# Answer
> 2 votes
# SOGL, 83 bytes

```
┌׀0ρMVxDrž|⁷ΨB≈π93|↑D~Νķ‰¤t╤▼ΣΗ⁶⅔¾№⁷Ζ÷│²╥Ν9°‘-”)0ΔH«‘4*jŗ"ΣΨ¬¹‘4*;+7{’⁄{»}⁽:’∞n1wpX

```

The 1st part `┌׀0ρMVxDrž|⁷ΨB≈π93|↑D~Νķ‰¤t╤▼ΣΗ⁶⅔¾№⁷Ζ÷│²╥Ν9°‘` is a compressed string resulting in

```
`life is but a dream.               |-|gently down the stream.            |row, row, row your boat,           |`

```

These are the lines reversed (since this is printing them line-by-line), with the "merrily" part cut out to be replaced in the program.
The rest of the program:

```
...‘                                        Push the compressed string
      )0ΔH«‘                                push "merrily, "
            4*                              repeat it 4 times
              j                             take the last letter off
    -”         ŗ                            replace "-" with the merrily line
                "ΣΨ¬¹‘                      push 35 dashes with an appending "|"
                      4*                    repeat it 4 times
                        ;+                  add inverted ("---|---..."+"Life is but a dream  ...")
                                            The resulting string of above is "-----------------------------------|-----------------------------------|-----------------------------------|-----------------------------------|life is but a dream.               |merrily, merrily, merrily, merrily,|gently down the stream.            |row, row, row your boat,           |"
                          7{                repeat 7 times
                            ’⁄{»}            rotate right 35 times
                                 ⁽           uppercase the 1st letter
                                  :          duplicate
                                   ’∞n       split into parts of length 135
                                      1w     get the 1st one
                                        p    output that
                                         X   delete the splat array

```

# Answer
> 2 votes
# ///, 200 bytes

```
/_/     //&/errily,//*/ m&//+/-------//@/Row, row, row your boat, __//#/Gently down the stream.  __//$/M&***//%/Life is but a dream.___//~/+++++/@|~|~|~
#|@|~|~
$|#|@|~
%|$|#|@
~|%|$|#
~|~|%|$
~|~|~|%

```

Try it online!

Simple, uses common occurrences as replacements.

# Answer
> 2 votes
# PHP, 179 bytes:

```
for($m="errily,";$i<28;)echo str_pad($s=["Row, row, row your boat,","Gently down the stream.","M$m m$m m$m m$m","Life is but a dream."][($i>>2)-$i%4],35," -"[!$s]),"
|||"[++$i%4];

```

**ungolfed**

```
for($i=0;$i<28;$i++)
{
    $x=$i%4;
    $y=$i>>2;

    $s=["Row, row, row your boat,",
        "Gently down the stream.",
        M.($m="errily,")." m$m m$m m$m",
        "Life is but a dream."
    ][$y-$x];

    $pad_string = $s ? " ":"-";
    $postfix = $x<3 ? "|" : "\n";
    echo str_pad($s,35,$pad_string),$postfix;
}

```

# Answer
> 2 votes
**Microsoft Sql Server, 421 bytes**

```
with v as(select left(s+space(35),35)s,n from(values('Row, row, row your boat,',1),('Gently down the stream.',2),('Merrily, merrily, merrily, merrily,',3),('Life is but a dream.',4))t(s,n))select isnull(v.s,s.s)+'|'+isnull(b.s,s.s)+'|'+isnull(c.s,s.s)+'|'+isnull(d.s,s.s)from v full join v b on v.n=b.n+1 full join v c on b.n=c.n+1 full join v d on c.n=d.n+1 cross apply(select replicate('-',35)s)s order by isnull(v.n,9)

```

Check It Online

# Answer
> 2 votes
# T-SQL, ~~296 277~~ 276 bytes

```
PRINT REPLACE(REPLACE(REPLACE(REPLACE(REPLACE(REPLACE(REPLACE('1|0|0|0
2|1|0|0
3|2|1|0
4|3|2|1
0|4|3|2
0|0|4|3
0|0|0|4',0,REPLICATE('-',35))
        ,1,'Row, row, row your boat,6')
        ,2,'Gently down the stream. 6')
        ,3,'M5 m5 m5 m5')
        ,4,'Life is but a dream.    6')
        ,5,'errily,')
        ,6,SPACE(11))

```

Line breaks at the beginning are part of the original string, line breaks near the end are for display purposes only, and are not counted toward the byte total.

Inspired largely by Conrade SparklePony's answer. Different technique than Andrei Odegov's SQL answer.

Pretty straight-forward multi-replacement, but a few things that help save bytes:

* SQL allows line breaks in the original string
* Using numerals instead of characters allows me to eliminate a whole bunch of single quotes
* Nested replacements (5 and 6), save me even more bytes (thanks, @t-clausen.dk)

If only I could `REPLACE` all the `REPLACE`s with something shorter. Hmm....

# Answer
> 1 votes
# Swift, 416 406 405 380 ~~372~~ 307 bytes

```
var f=String.init(repeating:count:);_={[[0,4,4,4],[1,0,4,4],[2,1,0,4],[3,2,1,0],[4,3,2,1],[4,4,3,2],[4,4,4,3]].forEach{print($0.map{["Row, row, row your boat,"+f(" ",11),"Gently down the stream."+f(" ",12),"Merrily,"+f(" merrily,",3),"Life is but a dream."+f(" ",15),f("-",35)][$0]}.joined(separator:"|"))}}

```

You can try it here.

Thanks to @Mr. Xcoder for saving me 65 bytes!

# Answer
> 1 votes
# Python 2, 225 Bytes

```
w=[["-"*35]*7for _ in[0]*4]
for i in [0]*4:w[i][i:i+4]=[a.ljust(35)for a in["Row, row, row your boat,","Gently down the stream.","Merrily,"+" merrily,"*3,"Life is but a dream."]]
print "\n".join(["|".join(i)for i in zip(*w)])

```

Try it online!

# Answer
> 1 votes
# Retina, ~~153~~ 150 bytes

```

<-|>Life is but a dream.15|M!< m!>|Gently down the stream.12|Row, row, row your boat,11<|->
<(.*?)>
$1$1$1
!
errily,
-
35$*-
\d+
$*
r!&`.{71}\|.{71}

```

Try it online!

I tried arbitrary run-length encoding but `$1$*$2` doesn't do what I want and repeating strings proved too tricky. Edit: Saved 2 bytes by encoding `errily,` and 1 byte by removing an unnecessary `^`.

# Answer
> 1 votes
# MATLAB, 280 bytes

```
a='errily,';
z={'Row, row, row your boat,';'Gently down the stream.';['M',a,' m',a,' m',a,' m',a];'Life is but a dream.'};
z{5}(1:35)='-';
y=5*ones(7,4);
for j=1:4;z{j}(end+1:35)=' ';y(j:j+3,j)=(1:4)';end
x=z(y);
for j=1:7;fprintf('%s|%s|%s|%s\n',x{j,1},x{j,2},x{j,3},x{j,4});end

```

The cell array indexing is pretty costly, that seems like the easiest place to discard some bytes (if possible).

# Answer
> 1 votes
# Perl 5, 215 bytes

```
$m='merrily,';$s=' 'x11;$l='-'x35;
@t=@s=("Row, row, row your boat,$s","Gently down the stream. $s",
       "\u$m $m $m $m","Life is but a dream.    $s",$l,$l,$l);
map{$i--;map$t[$_].="|".$s[$i++%7],0..6}1..3;print"$_\n"for@t

```

Try it online!

# Answer
> 1 votes
# Japt `-R`, ~~99~~ ~~95~~ ~~94~~ ~~92~~ ~~90~~ ~~89~~ 87 bytes

```
R³i`Life  ¿t a Ým.
M{34î`Îk, m`}
Gt§ Üµ e Ðpam.
Row, w, w yr ¾,`ú)·ú-
£éY Å¤q|

```

Try it

```
R³i`L...{34î`...`}...,`ú)·ú-
R                                :Newline
 ³                               :Repeat 3 times
  i                              :Prepend
   `                             :  Decompress
    L...                         :    "Life is but a dream.\nM"
        {                        :    Interpolate
         34î                     :      Repeat & slice to length 34
            `...`                :        The compressed string "errily, m"
                 }               :    End interpolation
                  ...,           :    "\nGently down the stream.\nRow, row, row your boat,"
                      `          :  End decompression
                       ú         :  Right pad each line with spaces to the length of the longest
                        )        :End prepend
                         ·       :Split on newlines
                          ú-     :Right pad each element with "-" to the length of the longest
£éY Å¤q|                         :Assign the above to U
£                                :Map each element at 0-based index Y
 éY                              :  Rotate U right Y times
    Å                            :  Slice off the first element
     ¤                           :  Slice off the first two elements
      q|                         :  Join with "|"
                                 :Implicit output, joined with newlines

```

# Answer
> 0 votes
# Japt, 158 157 bytes

```
='|L=`Row, žw, žw yŒr ¾…,`+Sp11 +UV=`Gt§ Üµ e Ðpam.`+S³²²+UW=`M€Îk,`+` ´rÎk,`³+UJ=W+VX=`Life ‰ ¿t a Ý„m.`+Sp15 +UZ='-p35 +U[LZ³RVLZ²RJLZRXJLRZXJRZ²XWRZ³X]q

```

Try it online!

# Answer
> 0 votes
# Ruby, 162 bytes

```
7.times{|i|puts (~i..~i+3).map{|j|[*[?-*35]*3,"Life is but a dream.",?M+['errily,']*4*" m","Gently down the stream.","Row, row, row your boat,"][j].ljust(35)}*?|}

```

# Answer
> 0 votes
# Java, 295 bytes / 272 259 bytes

with newlines every 4 columns (295b)

```
void r(){String m=" merrily,",t="-------",s="     ",e=t+t+t+t+t;String[]v={"Gently down the stream.  "+s+s, "Merrily,"+m+m+m, "Life is but a dream."+s+s+s, e, e, e, "Row, row, row your boat, "+s+s};for(int i=0;i<7;i++){for(int j=6+i;j>2+i;j--)System.out.print(v[j%7]+'|');System.out.println();}}

```

Try it Online

no newline version (259b):

```
void r(){String m=" merrily,",t="-------",s="     ",e=t+t+t+t+t;String[]v={"Gently down the stream.  "+s+s, "Merrily,"+m+m+m, "Life is but a dream."+s+s+s, e, e, e, "Row, row, row your boat, "+s+s};for(int i=0;i<28;i++)System.out.print(v[(6-i%4+i/4)%7]+'|');}

```
* Condensed 2 for loops into 1

Try it Online

# Answer
> 0 votes
# Stax, 63 bytes

```
∞╖]ÇàI╨‼Çö¼fi╩╨╛Aóß╟uƒ←37qÄô.Z╛Θ6►Mûj╚#Å[░]Oá0"y╧o╙)5;V╞♥╬F¼♫t~

```

Run and debug it

# Answer
> 0 votes
# Perl 5, 163 bytes

```
say join'|',(('-'x26)x3,"Life is but a dream".$"x7,ucfirst(join$",("merrily,")x3),"Gently down the stream    ",ucfirst "row, "x3 ."your boat  ")[-$_..3-$_]for 1..7

```

Try it online!

# Answer
> 0 votes
# Runic Enchantments, 292 bytes

```
B͍"-"'#*"|"3s
"Row, row, row your boat,"b" "S*q"|"3sB͍>01B10B3*1-akr@>12B01B10B2*1-akr@>13B12B01B10B1-akr@>14B13B12B01B1-akr@>10B3*14B1-r0[10B2*14B13B1-akr0[10B14B13B12B1-akr]]@
B͍"Gently down the stream."c" "S*q"|"3s
B͍"Merrily,"3" merrily,"S*q"|"3s
B͍"Life is but a dream."f" "S*q"|"3s

```

Try it online!

I don't generally do challenges, but the layout was one I could work with without too much trouble. Runic does not have good ways to compress arbitrary strings, so all we have to work with are the repetitious parts.

### Explanation:

Uncompressing slightly:

```
B͍"-"'#*"|"3s
B͍"Row, row, row your boat,"b" "S*q"|"3s
B͍"Gently down the stream."c" "S*q"|"3s
B͍"Merrily,"3" merrily,"S*q"|"3s
B͍"Life is but a dream."f" "S*q"|"3s
>11B10B3*1-akr@
>12B11B10B2*1-akr@
>13B12B11B10B1-akr@
>14B13B12B11B1-akr@
>10B3*14B1-r0[10B2*14B13B1-akr0[10B14B13B12B1-akr]]@

```

First 5 lines act as functions to build each portion of the song (where the first line generates the 35 `-` for the spacer using the decimal value of `#` to save 2 bytes over `3X5+`). The return instruction is at the beginning of the line to insure that all IPs that enter a function will also *leave* the function after the same number of cycles to avoid IPs merging (resulting in missing lines of output), as programs are rectangular and empty cells are implicit.

The next four lines are responsible for printing the first four lines of the output

The fifth line then prints the last 3 lines of output. Due to all three lines needing to start with at least one stanza-spacer it is not feasible to use 3 separate IPs (as they would need delays in order to avoid merging). `>`, `y`, `@`, and a newline cost more bytes (4) than `0[...]` (3 bytes) where `...` is arbitrary instructions (ie. another line of output).

Conversely replacing `>` and `@` to use a single IP requires more bytes.

Finally, merging all five entry-point lines onto the 2nd line saves 5 bytes worth of newlines. We just have to insure that the ranch-return instruction moves to the end of its line first, preserving the function's functionality.

---
Tags: code-golf, kolmogorov-complexity
---


# Question
Title: Sort a list of numbers on the λ-calculus
Write a term on the pure untyped lambda calculus that, when applied to a church-encoded list of numbers, returns it with its numbers sorted in ascending or descending order. Church lists and numbers must be encoded as folds for their usual ADTs:

```
-- Usual ADTs for Lists and Nats (in Haskell, for example)
data List a = Cons a (List a) | Nil
data Nat a  = Succ (Nat a) | Zero

-- Their respective folds are the λ-calculus representation used on this challenge
church_list = (λ c n . (c ... (c ... (c ... n))))
church_num  = (λ succ zero . (succ (succ (succ ... zero))))

```

Example input:

```
(λ cons nil .
    (cons (λ f x . (f x))                         -- 1
    (cons (λ f x . (f (f (f (f (f (f (f x)))))))) -- 7
    (cons (λ f x . (f (f x)))                     -- 2
    (cons (λ f x . (f (f (f x))))                 -- 3
    nil)))))

```

Example output:

```
(λ cons nil .
    (cons (λ f x . (f x))                         -- 1
    (cons (λ f x . (f (f x)))                     -- 2
    (cons (λ f x . (f (f (f x))))                 -- 3
    (cons (λ f x . (f (f (f (f (f (f (f x)))))))) -- 7
    nil)))))

```

The score of a submission will be calculated as follows:

```
score(x)    = 1
score(λx.t) = score(t) + 1
score(t s)  = score(t) + score(s) + 1

```

Lowest score wins.

# Answer
> 3 votes
I've managed to beat my own mark:

```
sort = λabcd.a(λef.f(λghi.g(λj.h(λkl.kj(ikl)))(hi))e(λgh.h))
       (λe.d)(λe.b(λf.e(f(λghi.hg)(λgh.cfh))))

```

There is a caveat, though - this term must receive an additional argument with the maximum size of naturals that are considered. For example, `sort 4 [1,7,3,6,5]` will return `[1,3]`, ignoring anything above or equal 4. Of course, you could just give infinity (i.e., the Y-combinator):

```
sort = λbcd.(λfx.f(x x))(λfx.f(x x))(λef.f(λghi.g(λj.h(λkl.kj(ikl)))
       (hi))e(λgh.h))(λe.d)(λe.b(λf.e(f(λghi.hg)(λgh.cfh))))

```

And it would sort any list of natural numbers, but this term obviously doesn't have a normal form anymore.

# Answer
> 1 votes
**121 characters / score 91**

```
sort = λabc.a(λdefg.f(d(λhij.j(λkl.k(λmn.mhi)l)(h(λkl.l)i))
       (λhi.i(λjk.bd(jhk))(bd(h(λjk.j(λlm.m)k)c))))e)(λde.e)
       (λde.d(λfg.g)e)c

```

It is in normal form and could be made shorter by lifting common subexpressions.

# Answer
> 1 votes
Here's an implementation of an insertion sort:

```
let nil =       \f x.x in
let cons = \h t.\f x.f h (t f x) in
let 0 =       \f x.x in
let succ = \n.\f x.f (n f x) in
let None =    \a b.b in
let Some = \x.\a b.a x in
let pred = \n.n (\opt.opt (\m.Some(succ m)) (Some 0)) None in
let optpred = \opt.opt pred None in
let - = \m n.n optpred (Some m) in
let < = \m n.\trueval falseval.- m n (\diff.falseval) trueval in
let pair = \x y.\f.f x y in
let snd = \p.p (\x y.y) in
let insert = \n l.snd (l (\h recpair.recpair (\rawtail insertedtail.
  let rawlist = cons h rawtail in
    pair rawlist (< h n (cons h insertedtail) (cons n rawlist))))
  (pair nil (cons n nil))) in
\l.l insert nil

```

Here, `pred n` returns an element of `option nat`: `pred 0` is `None` whereas `pred (n+1)` is `Some n`. Then, `- m n` returns an element of `option nat` which is `Some (m-n)` if `m>=n` or `None` if `m<n`; and `< m n` returns a boolean. Finally, `insert` uses an internal function returning a pair where `f l = (l, insert n l)` (a fairly typical method to get the tail of the list to get passed to the recursion along with the recursive value).

Now, some notes for future golfing work: actually `nil`, `0`, `None` happen to be the same function formally (and it also appears in `snd`). Then, I would certainly consider doing beta reductions on the `let` statements (which is of course the usual syntactic sugar where `let a = x in y` means `(\a.y)x` and thus has score `score(x) + score(y) + 2`) to see in which cases doing so would reduce the score - which it most definitely would for the bindings that are only used once.

Then would come trickier things: for example, I just noticed that formally `pred = pair (pair (\m.Some(succ m)) (Some 0)) None`, `optpred = pair pred None`, `- = \m.pair optpred (Some m)`, the sort function definition amounts to `pair insert nil`, etc. which could reduce the score slightly.

---
Tags: sorting, atomic-code-golf, lambda-calculus
---


title: Who won a Game of Bar Dice?

text:
# Question
Title: Who won a Game of Bar Dice?
# Challenge

Bar Dice is a simple game played in a Bar with Dice (hence the name). You roll 5 six-sided dice and attempt to make the best hand.

> Scoring is based on amassing the largest number of dice with the same digits. Each hand must include at least a single "Ace", or one, in order to be a valid hand; Aces act as "wilds", and can be paired with any other digit. The strength of a player's hand depends first on the number of digits and then value of those digits. As an example, a hand (counting wilds) with four 3's is better than a hand with three 5's, but not better than a hand with five 2's.
> Taken from the Wikipedia article

This means the highest ranked hand is made entirely of 6's and 1's, and the lowest ranked is any hand without a 1.

Your challenge is to take two hands and return which player won, or if they tied.

# Input

Two unsorted lists of 5 numbers, ranging from 1 to 6. Each list represents a player's hand. The input format is flexible.

# Output

Any three distinct but consistent, static values (ranges are not allowed) signifying whether player 1 or player 2 won, or if it was a tie. Please state in your answer what values you are using for what. For example, you can return `-1` if P1 wins, `0` if it's a tie, and `1` if P2 wins.

# Rules

* Input will always be valid
* Only the best possible score of each hand is used to determine a winner. There are no tie-breakers. E.g., `[1,4,4,3,3]` will tie `[1,4,4,2,2]` instead of using the 3's and 2's as a tie-breaker.
* Output must be one of the 3 chosen values every time. Simply mapping all negative numbers to `P1 Wins` is not allowed and must be normalized.
* Invalid hands, i.e. those with no 1's, lose to all valid hands but tie with all other invalid hands. E.g., `[2,2,2,2,2]` ties `[3,3,3,3,3]`.
* A hand of `[1,1,1,1,1]` counts as a valid set of 6's for ranking purposes.
* This is so shortest byte count wins.

# Examples

```
#You guys are pretty good at finding edge-cases that break things. Good job!
Input:  [2,1,5,6,6], [6,2,6,6,6]
Output: P1 Wins

Input:  [2,4,5,6,6], [6,2,6,6,6]
Output: Tie

Input:  [1,2,3,4,5], [5,4,3,2,1]
Output: Tie

Input:  [1,5,5,3,2], [5,4,1,6,6]
Output: P2 Wins

Input:  [3,2,2,2,1], [4,1,3,6,6]
Output: P1 Wins

Input:  [1,1,1,1,1], [6,1,1,6,6]
Output: Tie

Input:  [1,3,3,4,4], [1,2,2,5,5]
Output: P2 Wins

Input:  [1,3,3,5,5], [1,3,3,2,2]
Output: P1 Wins

Input:  [1,3,3,3,4], [1,1,3,3,3]
Output: P2 Wins

Input:  [2,2,2,6,1], [5,3,3,1,2]
Output: P1 Wins

Input:  [5,5,5,1,5], [1,1,1,1,1]
Output: P2 Wins

Input:  [1,1,1,1,1], [1,1,5,1,1]
Output: P1 Wins

```

# Answer
# Jelly, ~~17~~ 14 bytes

```
ċⱮ6Ḣ©+$®aĖUṀ)M

```

Try it online!

A monadic link that takes a list of the two lists as its argument and returns `[1]` for player 1 wins, `[2]` for player 2 wins and `[1, 2]` for a tie. TIO link tidies this up for display.

Thanks to @JonathanAllan for saving 3 bytes!

### Explanation

```
            )   | For each input list (e.g. of one list 1,1,3,3,4)
ċⱮ6             | - Count each of 1..6 (e.g. 2,0,2,1,0,0)
      $         | - Following as a monad:
   Ḣ            |   - Head (number of 1s)
    ©           |   - Copy to register
     +          |   - Add (e.g. 2,4,3,0,0)
       ®a       | - Register logical and with this
         Ė      | - Enumerate (e.g. [1,2],[2,4],[3,3],[4,0],[5,0])
          U     | - Reverse each (e.g. [2,1],[4,2],[3,3],[0,4],[0,5])
            Ṁ   | - Max (e.g. 4,2)
              M | Index/indices of maximal score

```
> 10 votes

# Answer
# , ~~115~~ 96 bytes

-6 bytes thanks to Giuseppe.

-6 bytes thanks to Aaron Hayman.

-2 bytes thanks to Arnauld, following the output format in his JavaScript answer.

```
function(i,j)(f(i)-f(j))/0
f=function(x,s=tabulate(x,6),l=s[1]+s[-1]*!!s[1])max(l)*6+order(l)[5]

```

Try it online!

Returns `Inf` for P1, `NaN` for a tie, `-Inf` for P2.

Uses the helper function `f` which computes a score for each hand. The score is defined as follows: let `d` be the digit which is repeated the most, and `n` the number of times it is repeated. Then the score is `6*n+d` if there is at least one ace, and `0` if there are no aces. We then just need to find the player with the highest score.

Ungolfed:

```
f = function(x) {
  s = tabulate(x, 6)         # number of occurrences of each integer
  l = s[1] + s[-1] * !!s[1]  # add the number of wild aces to all values; set to 0 if s[1] == 0
  max(l) * 6 +               # highest number of repetitions (apart from aces)
    order(l)[5]              # most repeated integer (take largest in case of tie)
}
function(i, j){
  sign(f(i) - f(j))
}

```
> 9 votes

# Answer
# Python 2, ~~85~~ ~~81~~ 80 bytes

```
lambda p:cmp(*[max((h.count(i)+h.count(i>1),i)*(1in h)for i in[6]+h)for h in p])

```

Try it online!

Returns `1` for P1, `0` for tie, and `-1` for P2.

-1 byte, thanks to squid
> 6 votes

# Answer
# 05AB1E, ~~16~~ 15 bytes

*-1 byte thanks to JonathanAllan*

```
εWΘ*6L¢ć+°ƶà}ZQ

```

Try it online!

Returns \[1, 0\] for P1 wins, \[1, 1\] for ties, \[0, 1\] for P2 wins.

Rather than using lexicographic order on a 2-tuple (dice count, dice value), this computes the score as 10\**dice count * dice value. Hands without a 1 score 5.

```
ε           }           # map each hand to its computed score
 WΘ                     # minimum == 1 (1 if the hand contains a 1, 0 otherwise)
   *                    # multiply (sets hands without 1 to [0, 0, 0, 0, 0])
    6L                  # range [1..6]
      ¢                 # count occurences of each in the hand
       ć                # head extract (stack is now [2-count, ..., 6-count], 1-count)
        +               # add the 1-count to all the other counts
         °              # 10**x
          ƶ             # multiply each element by its 1-based index
           à            # take the maximum

Z                       # maximum
 Q                      # equality test (vectorizes)

```
> 6 votes

# Answer
# JavaScript (ES6),  ~~97~~  90 bytes

Takes input as `(a)(b)`. Returns `+Infinity` for P1, `-Infinity` for P2 or `NaN` for a tie.

```
a=>b=>((g=(x,m)=>x>6?m*/1/.test(a):g(-~x,a.map(k=>n+=k<2|k==x,n=x/6)|m>n?m:n))()-g(a=b))/0

```

Try it online!

### Commented

```
a => b => (                 // a[] = dice of P1; b[] = dice of P2
  ( g = (                   // g is a recursive function taking:
      x,                    //   x = dice value to test; initially, it is either undefined
                            //       or set to a non-numeric value
      m                     //   m = maximum score so far, initially undefined
    ) =>                    //
      x > 6 ?               // if x is greater than 6:
        m * /1/.test(a)     //   return m, or 0 if a[] does not contain any 1
      :                     // else:
        g(                  //   do a recursive call:
          -~x,              //     increment x (or set it to 1 if it's non-numeric)
          a.map(k =>        //     for each dice value k in a[]:
            n +=            //       add 1 to n if:
              k < 2 |       //         k is equal to 1
              k == x,       //         or k is equal to x
            n = x / 6       //       start with n = x / 6
          ) |               //     end of map()
          m > n ?           //     if m is defined and greater than n:
            m               //       pass m unchanged
          :                 //     else:
            n               //       update m to n
        )                   //   end of recursive call
  )()                       // first call to g, using a[]
  - g(a = b)                // subtract the result of a 2nd call, using b[]
) / 0                       // divide by 0 to force one of the 3 consistent output values

```
> 6 votes

# Answer
# Perl 6, ~~60~~ 49 bytes

```
&[cmp]o*.map:{.{1}&&max (.{2..6}X+.{1})Z ^5}o&bag

```

Try it online!

Returns `More`, `Same`, `Less` for `P1 Wins`, `Tie`, `P2 Wins`.

### Explanation

```
       *.map:  # Map input lists
                                             &bag  # Convert to Bag
             {                             }o  # Pass to block
              .{1}&&  # Return 0 if no 1s
                    max  # Maximum of
                         .{2..6}  # number of 2s,3s,4s,5s,6s
                                X+.{1}  # plus number of 1s
                        (             )Z     # zipped with
                                         ^5  # secondary key 0,1,2,3,4
&[cmp]o  # Compare mapped values

```
> 4 votes

# Answer
# T-SQL query, 147 bytes

Using table variable as input

> p: player
>
> v: value for roll

```
DECLARE @ table(p int,v int)
INSERT @ values(1,5),(1,5),(1,5),(1,5),(1,5)
INSERT @ values(2,4),(2,3),(2,3),(2,1),(2,4)

SELECT sign(min(u)+max(u))FROM(SELECT(p*2-3)*(s+sum(1+1/~s-1/v))*(s/5*5+v+30)u
FROM(SELECT*,sum(1/v)over(partition by p)s FROM @)c GROUP BY v,s,p)x

```

**Try it online**

```
Player 1 wins returns -1
Tie returns 0
Player 2 wins returns 1

```
> 4 votes

# Answer
# Java 8, ~~244~~ ~~240~~ ~~236~~ ~~215~~ 199 bytes

```
a->b->{int c[][]=new int[2][7],m[]=new int[2],p,i=5;for(;i-->0;c[1][b[i]]++)c[0][a[i]]++;for(i=14;i-->4;)m[p=i%2]=Math.max(m[p],c[p][1]>0?i/2+9*(c[p][i/2]+c[p][1]):0);return Long.compare(m[0],m[1]);}

```

-4 bytes thanks to *@someone*.
-21 bytes thanks to *@Neil*.
-16 bytes thanks to *@ceilingcat*.

Returns `1` if P1 wins; `-1` if P2 wins; `0` if it's a tie.

Try it online.

**Explanation:**

```
a->b->{                        // Method with 2 integer-array parameters & integer return
  int c[][]=new int[2][7],     //  Create a count-array for each value of both players,
                               //  initially filled with 0s
      m[]=new int[2],          //  The maximum per player, initially 0
      p,                       //  Temp-value for the player
  i=5;for(;i-->0;              //  Loop `i` in the range (5, 0]:
    c[1]                       //   For player 2:
        [b[i]                  //    Get the value of the `i`'th die,
             ]++)              //    and increase that score-count by 1
    c[0][a[i]]++;              //   Do the same for player 1
  for(i=14;i-->4;)             //  Then loop `i` in the range (14, 4]:
    m[p=i%2]=                  //   Set the score of a player to:
                               //   (even `i` = player 1; odd `i` = player 2)
      Math.max(                //    The max between:
        m[p],                  //     The current value,
                               //     And the value we calculate as follows:
        c[p][1]>0?             //     If this player rolled at least one 1:
          i/2                  //      Use the current value `i` integer-divided by 2
          +9*                  //      With 9 times the following added:
             (c[p][i/2]        //       The amount of dice for value `i//2`
              +c[p][1])        //       Add the amount of dice for value 1
        :                      //     Else (no 1s were rolled):
         0);                   //      Use 0
  return Long.compare(m[0],m[1]);}
                               //  Finally compare the maximum scores of the players,
                               //  resulting in -1 if a<b; 0 if a==b; 1 if a>b

```
> 2 votes

# Answer
# Jelly, 21 bytes

crushed before I even posted it by Nick Kennedy :)

```
’-oÆṃṀ$$Ạ?fÆṃ$L;$o5)M

```

A monadic Link accepting a list of players which outputs a list of (1-indexed) winners.

So P1 is `[1]`, P2 is `[2]` and a tie is `[1,2]`.

**Try it online!**
> 2 votes

# Answer
# PowerShell, ~~112~~ ~~126~~ ~~123~~ 121 bytes

Takes input as `(a)(b)`. Returns `-1` for P1 win, `1` for P2 or `0` for a tie.

```
$args|%{$d=$($_-ne1|group|sort c*,n*|%{$m=$_};(7*(($o=($_-eq1).Count)+$m.Count)+$m.Name+6*!$m)[!$o])-$d}
[math]::Sign($d)

```

Try it online!

Test case `@( @(1,1,5,1,1), @(1,1,1,1,1), 1)` added.

Unrolled:

```
$args|%{
    $score=$(                                            # powershell creates a new scope inside expression $(...)
        $_-ne1|group|sort count,name|%{$max=$_}          # $max is an element with the widest group and the maximum digit except 1
        $ones=($_-eq1).Count                             # number of 1s in a player's hand
        $scoreRaw=7*($ones+$max.Count)+$max.Name+6*!$max # where $max.Name is digit of the widest group
        $scoreRaw[!$ones]                                # output $scoreRaw if the array contains 1, otherwise output $null
    )                                                    # powershell deletes all variables created inside the scope on exit
    $diff=$score-$diff
}
[math]::Sign($diff)                                     # output the score difference

```
> 2 votes

# Answer
# Wolfram Language (Mathematica), ~~78~~ ~~75~~ 74 bytes

*-1 byte by Greg Martin*

```
Order@@(#~FreeQ~1||Last@Sort[Reverse/@Tally@Flatten[#/. 1->Range@6]]&)/@#&

```

Try it online!

Outputs -1 when player 1 wins, 1 when player 2 wins, and 0 for a tie.

```
                                    Helper function to score a list:
FreeQ[#,1] ||                       If there are 0 1s, score is True
Last@Sort[                          Otherwise, take the largest element of
    Reverse/@Tally@                 the {frequency, number} pairs in the flat list
       Flatten[ #/. 1->Range@6]     where each 1 is replaced by {1,2,3,4,5,6}.
]&                              e.g. {1,3,3,5,5} -> {1,2,3,4,5,6,3,3,5,5} -> {3,5}

Order @@ (...) /@ #&                Apply this function to both lists,
                                    then find the ordering of the result.

```
> 2 votes

# Answer
# Jelly, 27 bytes

```
’o5Rṗ5¤ṢŒr$€UẎṀ1e⁸¤×µ€_/Ṡo/

```

Try it online!

1 for P1, -1 for P2, 0 for tie

# Explanation

```
’o5Rṗ5¤ṢŒr$€UẎṀ1e⁸¤×µ€_/Ṡo/  Main link
                    µ€       For each list
’                            Decrement each value (so 1s become falsy)
 o                           Vectorized logical or (this replaces previous 1s (now 0s) with the test values)
  5Rṗ5¤                      1..5 cartesian-power 5 (1,1,1,1,1; 1,1,1,1,2; 1,1,1,1,3; ...)
          $€                 For each test list
       ṢŒr                   Sort and run-length encode (gives [digit, #digit])
            U                Reverse each list (gives [#digit, digit])
             Ẏ               Tighten by one (gives a list containing each possible hand for each possible wildcard)
              Ṁ              Take the maximum
               1e⁸¤×         Multiply the list values by (whether or not the original contained a 1) - becomes [0, 0] if not
                      _/Ṡ    Take the sign of the difference between the #digits and the digits
                         o/  If the number of digits differs, then 1/-1 is returned; otherwise, check the value of the digit (could still be 0)

```
> 1 votes

# Answer
# Charcoal, ~~48~~ 45 bytes

```
ＵＭθ⮌Ｅ⁷№ι∨λ¹ＵＭθ×¬¬⊟ι⁺⊟ιιＵＭθ⟦⌈ι±⌕ι⌈ι⟧Ｉ⁻⌕θ⌈θ⌕θ⌊θ

```

Try it online! Link is to verbose version of code. Takes input as an array of arrays and outputs `-1` if player 1 wins, `0` for a tie, and `1` if player 2 wins. Explanation:

```
ＵＭθ⮌Ｅ⁷№ι∨λ¹

```

Replace each hand with the count of how many times the values `6..1` appear in the hand. The list is reversed because a) it makes it easier to find the highest value with the highest count and b) it makes it easier to remove the count of `1`s. The count of `1`s is doubled because it needs to be removed twice, once to check that it is nonzero and once to add it to the other counts.

```
ＵＭθ×¬¬⊟ι⁺⊟ιι

```

Add the count of `1`s to the counts for `6..2`, but set all of the counts to zero if the count of `1`s was zero.

```
ＵＭθ⟦⌈ι±⌕ι⌈ι⟧

```

For each hand find the highest count and the highest value with that count. (Actually we find value minus `6` as that's golfier.)

```
Ｉ⁻⌕θ⌈θ⌕θ⌊θ

```

Determine which hand won by subtracting the positions of the winning and losing hands. (If the hands are tied then the first hand is both winning and losing so the result is `0` as desired.)
> 1 votes

# Answer
# Sledgehammer 0.4, 27 bytes

```
⢱⢙⢂⠠⡾⢃⠐⢈⠸⣞⠴⠻⠎⡥⡳⡐⢒⠘⢛⣩⡓⣮⡕⡠⣢⣡⠿

```

Decompresses into this Wolfram Language function:

```
Order @@ (FreeQ[#1, 1] || Last[Sort[Reverse[Tally[Flatten[#1 /. 1 -> Range[6]]], 2]]] & ) /@ #1 &

```

which turns out to be exactly the same as my Mathematica answer.
> 1 votes

# Answer
# C (gcc) / 32 bit, 117 bytes

```
t;m;s(int*r){int c[6]={};for(m=0;t=*r++;m=t>m?t:m)c[--t]+=5,t=t?c[t]+t:5;t=*c?*c+m:0;}f(a,b){t=s(a)-s(b);t=(t>0)-!t;}

```

Try it online!

Takes two zero-terminated integer arrays. Returns `1`, `0`, `-1` for `P1 Wins`, `P2 Wins`, `Tie`.
> 1 votes

# Answer
# , ~~47~~ 44 bytes

```
*@-&([:({.([:>./#\@]+9^*@[*+)}.)1#.i.@6=/<:)

```

Try it online!

Inspired by Nick Kennedy's idea.

## ungolfed

```
*@-&([: ({. ([: >./ #\@] + 9 ^ *@[ * +) }.) 1 #. i.@6 =/ <:)

```
> 1 votes

# Answer
# Perl 5 `-MList::Util=max -pl`, 80 bytes

```
sub t{$t=pop;$_=max map$_ x$t=~s/$_//g,2..6;/./;$t&&$_.$t*($&||6)}$_=t($_)<=>t<>

```

Try it online!

**Input:**

Each player on a separate line, no spaces

**Output:**

`1` Line one wins

`0` Tie

`-1` Line two wins
> 1 votes

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


title: Insert commas into numbers

text:
# Question
Title: Insert commas into numbers
Write a program that reads a string, and inserts commas to divide large numbers in groups of 3. i.e. 10000 =\> 10,000. It should 'fix' incorrectly formatted numbers as described below.

* It must work for all numbers on the same line
* It should not modify numbers after a decimal point. i.e. 1234.5678 =\> 1,234.5678
* Leading zeros should be removed (or inserted where appropriate):
    + 00000 =\> 0
    + 00001234 =\> 1,234
    + .1234 =\> 0.1234
    + 00.1234 =\> 0.1234
    + 1000.1234 =\> 1,000.1234
* All non-digit characters should not be altered.
* It should correct, incorrectly placed "," characters only when followed before or after a digit:
    + 10,,00 =\> 1,000
    + 00,000 =\> 0
    + a,2 =\> a2
    + 2,a =\> 2a
    + ,a2 =\> ,a2
    + 0,a2 =\> 0a2
    + ,,, =\> ,,,
    + ,,,. =\> ,,,.
    + ,,,1 =\> 1
    + ,.,,1 =\> 0.1
* Numbers that contain multiple "." should not be treated as a number, and therefore no comma separation should be used:
    + 1..3 =\> 1..3
    + 1234.5678.9012 =\> 1234.5678.9012
    + 1234,,.5678abc.123 =\> 1,234.5678abc0.123
    + 1234.,.5678abc.123 =\> 1234.,.5678abc0.123
* Explanations to unusual cases:
    + ,,,. =\> ,,,. (not a number, no special meanings to ",", ".")
    + ,,,.0 =\> 0 (these characters are neighbouring a number and treated as such)
    + 1,,, =\> 1
    + ,,,1 =\> 1
    + ,.,,1 =\> 0.1 (the "." indicates decimal number, remove incorrectly placed "," in number).
    + ,.,,.1 =\> ,.,,.1 (not a number because multiple ".")
    + a,,,b1234 = \> a,,,b1,234 (first few characters are not neighbouring a number and treated as text)

Example inputs:

```
10000
10,000
$1234.12
~$123456789.12345~
HELLO123456.99BYE
The_amount_€45678_is_$USD51805.84
5000000-1999999=3000001
!1234567.1234+1234567.1234=2469134.2468!
00000a00
0b0001234
.a.1234
00.1234
1000.1234
10,,00
00,000
a,2
2,a
,a2
0,a2
,,,
,,,.
,,,1
,.,,1
1..3
1234.5678.9012
1234,,.5678abc.123
1234.,.5678abc.123
,,,.
,,,.0
1,,,
,,,1
,.,,1
,.,,.1
a,,,b1234

```

Corresponding outputs:

```
10,000
10,000
$1,234.12
~$123,456,789.12345~
HELLO123,456.99BYE
The_amount_€45,678_is_$USD51,805.84
5,000,000-1,999,999=3,000,001
!1,234,567.1234+1,234,567.1234=2,469,134.2468!
0a0
0b1,234
.a0.1234
0.1234
1,000.1234
1,000
0
a2
2a
,a2
0a2
,,,
,,,.
1
0.1
1..3
1234.5678.9012
1,234.5678abc0.123
1234.,.5678abc0.123
,,,.
0
1
1
0.1
,.,,.1
a,,,b1,234

```

Code golf: shortest code wins.

# Answer
> 3 votes
# Retina, 71 bytes

```
/[\d.,]+/_/\d/&/\..*\./^&(`,

^0+

^\B
0
'.&`\.?0+$

/^\d+/_r`\B...
,$&

```

Try it online! Link includes test cases. Explanation:

```
/[\d.,]+/_

```

Find all runs of digits, `.`s and `,`s.

```
/\d/&

```

Ignore those with no digits.

```
/\..*\./^&

```

Ignore those with two `.`s.

```
(`

```

Process the rest of the script on each remaining match.

```
,

```

Delete all commas.

```
^0+

```

Delete all leading zeros.

```
^\B
0

```

Insert a leading zero if the number does not begin with a digit.

```
'.&`

```

If the number contains a `.`...

```
\.?0+$

```

... delete trailing zeros and any preceding `.`.

```
/^\d+/_

```

On the part of the number before the `.`...

```
r`\B...
,$&

```

Match groups of three starting from the end, but leave at least one digit at the beginning, and insert commas before each match.

---
Tags: code-golf, regular-expression, text-processing
---


# Question
Title: Shortest Gomoku (5 in a row) implementation
I suspect Gomoku may be one of the simplest games to implement in code. https://en.wikipedia.org/wiki/Gomoku The game is this: players BLACK and WHITE take turns putting down black and white stones. Black traditionally goes first. If, when a player puts down their stone, they now have 5 in a row of their color, they win. That's it.

A simple way to implement this is to just keep two lists of (x, y) integer coordinates, one for black stones and one for white stones. Players simply specify an integer x,y coordinate, any x,y coordinate at all! The game checks if there is already a stone there of either color, and if not x,y is added to the list, and then the game checks if that stone made them have 5 in a row now.

Notice I have said nothing about board size, or checking if a move is on the board or not. My thought is that specifying board size and determining what to do at edges actually complicates things more! Gomoku *can* be played on an infinite board, and the game still works actually!

Anyway, to be clear, I believe the specifications are, implement Gomoku on a board of size between or including 15x15 and infinity x infinity (I actually suspect inifinite may be simpler.) Let the user know who's turn it is to play, by alternately printing "b\>","w\>". If an invalid entry is made, such as playing where there already is a stone there, just keep asking the user who played the invalid move until they play a valid move. To keep things extra short, no need to print the board state, actually! But if on a user's turn, they have completed 5 in a row orthogonaly or diagonally, print, or throw an error, that can simply say "w" or "b", to say who won. Shortest code that does the specified, wins.

If you want to print the board state or make things look nicer or make an AI or whatever, no need to do that, but you can add with or separately to your submission if you feel like it.

I wrote a non-golfed but still shortish implementation in Python, with simple board printing and stuff before. Here it is: https://github.com/jeffkaufman/game-complexity/blob/master/gomoku.py

And here's my entire attempt at a golfed version with the basic IO and move checking, but without board printing. I am quite sure this is *not* optimal at all, I'm not often a golfer. All I mostly did was make variables one character / remove whitespace and stuff, you guys can \*easily\* do better, I know.

```
w,b=[],[]
def o((x,y),s,(v,u)):
 if (x,y) in s:return o((x+v,y+u),s,(v,u))
 if v:return x
 return y
d=((0,1),(1,0),(1,1),(-1,1))
def W(m,s):
 for (x,y) in d:
  if o(m,s,(x,y))-o(m,s,(-x,-y))>5:return 1
 return 0
def t(c,p):
 while 1:
  C=raw_input(c+'>')
  try:
   x,y=C.split()
   m=(int(x),int(y))
  except ValueError:continue
  if m in b+w:continue
  p.append(m)
  if W(m,p):raise Exception(c)
  break
while 1:t("b",b),t("w",w)

```

an example run from that, which throws a Python error saying who won, at the end:

```
b>0 0
w>-4 5
b>0 1
w>0 1
w>7 12
b>0 2
w>7 12
w>4 5
b>0 -1
w>4 4
b>0 3

Traceback (most recent call last):
  File "C:/Users/udqbp/OneDrive/Desktop/test.py", line 22, in <module>
    while 1:t("b",b),t("w",w)
  File "C:/Users/udqbp/OneDrive/Desktop/test.py", line 20, in t
    if W(m,p):raise Exception(c)
Exception: b

```

# Answer
> 0 votes
# Jelly, 54 bytes

```
Ḋ,Z,ŒD$ŒrFs2ḢƇ<5Ȧ
0x⁹s⁴-;N1¦Ṅ©+Ɠœị®Ḋ¤$¿ṪṬṭ0x$Ʋ¹NƭƊƊ$Ç¿

```

Try it online!

A full program that reads input on stdin. For each loop through it prints the current player (1 or -1) and the 16x16 grid. Moves are input on stdin as a Python array (e.g. `[3,2]`) with or without the surrounding square brackets. The only validation done is to make sure that the relevant cell is empty. When there are 5 (or more) in a row, the program ends and prints out the winner and final grid.

If checking for a valid move can be omitted, 10 bytes can be saved:

# Jelly, 44 bytes

```
Ḋ,Z,ŒD$ŒrFs2ḢƇ<5Ȧ
0x⁹s⁴-;N1¦Ṅ+ƓṪṬṭ0x$¹Nƭ¤ƲÇ¿

```

Try it online!

Conversely, if the w/b designation in the spec is strict, that costs 15 bytes:

# Jelly, 69 bytes

```
ị“wb ”Ḣ
Ḋ,Z,ŒD$ŒrFs2ḢƇ<5Ȧ
0x⁹s⁴-;N1¦Ñ;”>ṄṛƲ©+Ɠœị®Ḋ¤$¿ṪṬṭ0x$Ʋ¹NƭƊƊ$Ç¿Ñ

```

Try it online!

---
Tags: code-golf, board-game
---


title: Bailey–Borwein–Plouffe Iterations

text:
# Question
Title: Bailey–Borwein–Plouffe Iterations
# Bailey–Borwein–Plouffe Iterations

We've seen a few pi challenges on PPCG, but none that specifically dictate the algorithm you should be using. I'd like to see implementations of the Bailey–Borwein–Plouffe algorithm in any language up to iteration `n`. The formula is as follows:

Your algorithm should output each iteration up to n, showing intermediate sums as well as the final result to form a "piangle". You may also use the reduced polynomial form of the algorithm shown on the wikipedia page. An example run for `n=50` is shown below:

```
3
3.1
3.14
3.141
3.1415
3.14159
3.141592
3.1415926
3.14159265
3.141592653
3.1415926535
3.14159265358
3.141592653589
3.1415926535897
3.14159265358979
3.141592653589793
3.1415926535897932
3.14159265358979323
3.141592653589793238
3.1415926535897932384
3.14159265358979323846
3.141592653589793238462
3.1415926535897932384626
3.14159265358979323846264
3.141592653589793238462643
3.1415926535897932384626433
3.14159265358979323846264338
3.141592653589793238462643383
3.1415926535897932384626433832
3.14159265358979323846264338327
3.141592653589793238462643383279
3.1415926535897932384626433832795
3.14159265358979323846264338327950
3.141592653589793238462643383279502
3.1415926535897932384626433832795028
3.14159265358979323846264338327950288
3.141592653589793238462643383279502884
3.1415926535897932384626433832795028841
3.14159265358979323846264338327950288419
3.141592653589793238462643383279502884197
3.1415926535897932384626433832795028841971
3.14159265358979323846264338327950288419716
3.141592653589793238462643383279502884197169
3.1415926535897932384626433832795028841971693
3.14159265358979323846264338327950288419716939
3.141592653589793238462643383279502884197169399
3.1415926535897932384626433832795028841971693993
3.14159265358979323846264338327950288419716939937
3.141592653589793238462643383279502884197169399375
3.1415926535897932384626433832795028841971693993751
3.14159265358979323846264338327950288419716939937510

```

The precision of each iteration should equal the `n` that is passed to the algorithm, that is to say that each iteration should calculate pi up to the passed `n` for all `k`.

# Rules:

* Built-ins are not allowed, nor is `pi`, you must use the formula.
* You must support `n` up to a maximum that your language allows in terms of the calculation of `16^n`. If the input is causing an arithmetic overflow during calculation after `x<n` executions because your language only supports decimals up to `2^32-1`, this is fine. Any other assumptions on `n` are not fine.
* You **MUST** provide an explanation of how you got the output if it is not obvious. For instance, if you're posting in a Golfing language a break-down is 100% required. This is to ensure you're using the algorithm that is specified.
* Standard loop-holes are disallowed.
* This is code-golf, lowest byte count wins here.

Reference Code (Code used to Generate Example):

```
public static void main(String[] args) {
    (0..50).each {
        n->
        def x=(0..n).collect {
            j->
            def k=new BigDecimal(j)
            def s={it.setScale(n)}
            def a=s(1.0g).divide(s(16.0g)**s(k))
            def b=s(4.0g)/(s(8.0g)*s(k)+s(1.0g))
            def c=s(2.0g)/(s(8.0g)*s(k)+s(4.0g))
            def d=s(1.0g)/(s(8.0g)*s(k)+s(5.0g))
            def e=s(1.0g)/(s(8.0g)*s(k)+s(6.0g))
            def f=a*(b-c-d-e)
        }.sum()
        println(n + "\t" + x.setScale(n, BigDecimal.ROUND_DOWN))
    }
}

```

This implementation caps out at `n=255`, you may cap out at less or more.
This implementation was done in Groovy.

# Answer
> 9 votes
# 05AB1E, ~~63~~ ~~52~~ 50 bytes

**Specialization formula**

```
Îƒ0NU62201122vyÍ¹Ì°*8X*N>+÷+}16Xm÷+DX>£X__iÀ'.ìÁ},

```

Try it online!

**BBP formula**

```
ƒ4¹>°UX*8N*©>÷YX*®4+÷-1X*®5+÷-1X*®6+÷-1X*16Nm÷*ODN>£N__iÀ'.ìÁ},

```

Try it online!

# Answer
> 6 votes
# Python 2, ~~109~~ 108 bytes

```
def f(n):k=1;s=0;t=100**n;exec-~n*'s+=4*t/k-2*t/(k+3)-t/(k+4)-t/(k+5)>>k/2;print"3."[:k]+`s`[1:k/8+1];k+=8;'

```

Test it on Ideone.

# Answer
> 4 votes
# PARI/GP, 86 bytes

```
n->for(k=p=0,n,printf("%."k"f\n",(p=16*p-4/(3-j=8*k+4)-2/j-1/j++-1/j++)\(8/5)^k/10^k))

```

Or without the decimal point in **69 bytes**:

```
n->for(k=p=0,n,print((p=16*p-4/(3-j=8*k+4)-2/j-1/j++-1/j++)\(8/5)^k))

```

Rather than dividing through by *16k* each iteration, the previous value of *p* is instead multiplied by *16*. Floor of *p ÷ (8/5)k* is then the value of *π* truncated to the correct number of digits.

**Sample Usage**

```
$ gp
? n->for(k=p=0,n,printf("%."k"f\n",(p=16*p-4/(3-j=8*k+4)-2/j-1/j++-1/j++)\(8/5)^k/10^k))
? %(20)
3
3.1
3.14
3.141
3.1415
3.14159
3.141592
3.1415926
3.14159265
3.141592653
3.1415926535
3.14159265358
3.141592653589
3.1415926535897
3.14159265358979
3.141592653589793
3.1415926535897932
3.14159265358979323
3.141592653589793238
3.1415926535897932384
3.14159265358979323846

```

# Answer
> 3 votes
# Python 2, 174 Bytes

Man, this is a time when I wish that Python had some easier way of keeping infinite precision for decimals.. Possibly implementing your own infite accuracy type for this challenge is shorter but I can't imagine how. The formula is written verbatim.

```
from decimal import*
n=input();d=Decimal;getcontext().prec=n+2;p=d(0)
for i in range(n+1):f=8.*i;p+=d(16**(-i))*(4/d(f+1)-2/d(f+4)-1/d(f+5)-1/d(f+6));print str(p)[:-~i+(i>0)]

```

Example output for `n=100` (with some added line numbers):

```
3
3.1
3.14
3.141
3.1415
3.14159
3.141592
3.1415926
3.14159265
3.141592653
3.1415926535
3.14159265358
3.141592653589
3.1415926535897
3.14159265358979
3.141592653589793
3.1415926535897932
3.14159265358979323
3.141592653589793238
3.1415926535897932384
3.14159265358979323846
3.141592653589793238462
3.1415926535897932384626
3.14159265358979323846264
3.141592653589793238462643
3.1415926535897932384626433
3.14159265358979323846264338
3.141592653589793238462643383
3.1415926535897932384626433832
3.14159265358979323846264338327
3.141592653589793238462643383279
3.1415926535897932384626433832795
3.14159265358979323846264338327950
3.141592653589793238462643383279502
3.1415926535897932384626433832795028
3.14159265358979323846264338327950288
3.141592653589793238462643383279502884
3.1415926535897932384626433832795028841
3.14159265358979323846264338327950288419
3.141592653589793238462643383279502884197
3.1415926535897932384626433832795028841971
3.14159265358979323846264338327950288419716
3.141592653589793238462643383279502884197169
3.1415926535897932384626433832795028841971693
3.14159265358979323846264338327950288419716939
3.141592653589793238462643383279502884197169399
3.1415926535897932384626433832795028841971693993
3.14159265358979323846264338327950288419716939937
3.141592653589793238462643383279502884197169399375
3.1415926535897932384626433832795028841971693993751
3.14159265358979323846264338327950288419716939937510
3.141592653589793238462643383279502884197169399375105
3.1415926535897932384626433832795028841971693993751058
3.14159265358979323846264338327950288419716939937510582
3.141592653589793238462643383279502884197169399375105820
3.1415926535897932384626433832795028841971693993751058209
3.14159265358979323846264338327950288419716939937510582097
3.141592653589793238462643383279502884197169399375105820974
3.1415926535897932384626433832795028841971693993751058209749
3.14159265358979323846264338327950288419716939937510582097494
3.141592653589793238462643383279502884197169399375105820974944
3.1415926535897932384626433832795028841971693993751058209749445
3.14159265358979323846264338327950288419716939937510582097494459
3.141592653589793238462643383279502884197169399375105820974944592
3.1415926535897932384626433832795028841971693993751058209749445923
3.14159265358979323846264338327950288419716939937510582097494459230
3.141592653589793238462643383279502884197169399375105820974944592307
3.1415926535897932384626433832795028841971693993751058209749445923078
3.14159265358979323846264338327950288419716939937510582097494459230781
3.141592653589793238462643383279502884197169399375105820974944592307816
3.1415926535897932384626433832795028841971693993751058209749445923078164
3.14159265358979323846264338327950288419716939937510582097494459230781640
3.141592653589793238462643383279502884197169399375105820974944592307816406
3.1415926535897932384626433832795028841971693993751058209749445923078164062
3.14159265358979323846264338327950288419716939937510582097494459230781640628
3.141592653589793238462643383279502884197169399375105820974944592307816406286
3.1415926535897932384626433832795028841971693993751058209749445923078164062862
3.14159265358979323846264338327950288419716939937510582097494459230781640628620
3.141592653589793238462643383279502884197169399375105820974944592307816406286208
3.1415926535897932384626433832795028841971693993751058209749445923078164062862089
3.14159265358979323846264338327950288419716939937510582097494459230781640628620899
3.141592653589793238462643383279502884197169399375105820974944592307816406286208998
3.1415926535897932384626433832795028841971693993751058209749445923078164062862089986
3.14159265358979323846264338327950288419716939937510582097494459230781640628620899862
3.141592653589793238462643383279502884197169399375105820974944592307816406286208998628
3.1415926535897932384626433832795028841971693993751058209749445923078164062862089986280
3.14159265358979323846264338327950288419716939937510582097494459230781640628620899862803
3.141592653589793238462643383279502884197169399375105820974944592307816406286208998628034
3.1415926535897932384626433832795028841971693993751058209749445923078164062862089986280348
3.14159265358979323846264338327950288419716939937510582097494459230781640628620899862803482
3.141592653589793238462643383279502884197169399375105820974944592307816406286208998628034825
3.1415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253
3.14159265358979323846264338327950288419716939937510582097494459230781640628620899862803482534
3.141592653589793238462643383279502884197169399375105820974944592307816406286208998628034825342
3.1415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421
3.14159265358979323846264338327950288419716939937510582097494459230781640628620899862803482534211
3.141592653589793238462643383279502884197169399375105820974944592307816406286208998628034825342117
3.1415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170
3.14159265358979323846264338327950288419716939937510582097494459230781640628620899862803482534211706
3.141592653589793238462643383279502884197169399375105820974944592307816406286208998628034825342117067
3.1415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679

```

This does seem to work for larger numbers, `n=1000` runs in a couple seconds and `n=10000` doesn't seem to have given me any errors yet!

# Answer
> 3 votes
# J, ~~73~~ ~~64~~ 62 bytes

```
(j.":"+10&^(<.@*%[)[:+/\16&^%~[:-/4 2 _1 1%1 4 5 6+/*&8)@i.@>:

```

This outputs each approximation to *n* digits as a formatted string. This uses the polynomial simplification of the formula and gets the first *n* digits by multiplying the sum by a power of 10, flooring it, and dividing by that same power of 10.

The input is taken as an extended integer, meaning that rationals are used when division occurs which keeps results exact.

## Usage

This is the output for *n* = 100, showing the cumulative sums for *k* in \[0, 100\].

```
   f =: (j.":"+10&^(<.@*%[)[:+/\16&^%~[:-/4 2 _1 1%1 4 5 6+/*&8)@i.@>:
   f 100x
3
3.1
3.14
3.141
3.1415
3.14159
3.141592
3.1415926
3.14159265
3.141592653
3.1415926535
3.14159265358
3.141592653589
3.1415926535897
3.14159265358979
3.141592653589793
3.1415926535897932
3.14159265358979323
3.141592653589793238
3.1415926535897932384
3.14159265358979323846
3.141592653589793238462
3.1415926535897932384626
3.14159265358979323846264
3.141592653589793238462643
3.1415926535897932384626433
3.14159265358979323846264338
3.141592653589793238462643383
3.1415926535897932384626433832
3.14159265358979323846264338327
3.141592653589793238462643383279
3.1415926535897932384626433832795
3.14159265358979323846264338327950
3.141592653589793238462643383279502
3.1415926535897932384626433832795028
3.14159265358979323846264338327950288
3.141592653589793238462643383279502884
3.1415926535897932384626433832795028841
3.14159265358979323846264338327950288419
3.141592653589793238462643383279502884197
3.1415926535897932384626433832795028841971
3.14159265358979323846264338327950288419716
3.141592653589793238462643383279502884197169
3.1415926535897932384626433832795028841971693
3.14159265358979323846264338327950288419716939
3.141592653589793238462643383279502884197169399
3.1415926535897932384626433832795028841971693993
3.14159265358979323846264338327950288419716939937
3.141592653589793238462643383279502884197169399375
3.1415926535897932384626433832795028841971693993751
3.14159265358979323846264338327950288419716939937510
3.141592653589793238462643383279502884197169399375105
3.1415926535897932384626433832795028841971693993751058
3.14159265358979323846264338327950288419716939937510582
3.141592653589793238462643383279502884197169399375105820
3.1415926535897932384626433832795028841971693993751058209
3.14159265358979323846264338327950288419716939937510582097
3.141592653589793238462643383279502884197169399375105820974
3.1415926535897932384626433832795028841971693993751058209749
3.14159265358979323846264338327950288419716939937510582097494
3.141592653589793238462643383279502884197169399375105820974944
3.1415926535897932384626433832795028841971693993751058209749445
3.14159265358979323846264338327950288419716939937510582097494459
3.141592653589793238462643383279502884197169399375105820974944592
3.1415926535897932384626433832795028841971693993751058209749445923
3.14159265358979323846264338327950288419716939937510582097494459230
3.141592653589793238462643383279502884197169399375105820974944592307
3.1415926535897932384626433832795028841971693993751058209749445923078
3.14159265358979323846264338327950288419716939937510582097494459230781
3.141592653589793238462643383279502884197169399375105820974944592307816
3.1415926535897932384626433832795028841971693993751058209749445923078164
3.14159265358979323846264338327950288419716939937510582097494459230781640
3.141592653589793238462643383279502884197169399375105820974944592307816406
3.1415926535897932384626433832795028841971693993751058209749445923078164062
3.14159265358979323846264338327950288419716939937510582097494459230781640628
3.141592653589793238462643383279502884197169399375105820974944592307816406286
3.1415926535897932384626433832795028841971693993751058209749445923078164062862
3.14159265358979323846264338327950288419716939937510582097494459230781640628620
3.141592653589793238462643383279502884197169399375105820974944592307816406286208
3.1415926535897932384626433832795028841971693993751058209749445923078164062862089
3.14159265358979323846264338327950288419716939937510582097494459230781640628620899
3.141592653589793238462643383279502884197169399375105820974944592307816406286208998
3.1415926535897932384626433832795028841971693993751058209749445923078164062862089986
3.14159265358979323846264338327950288419716939937510582097494459230781640628620899862
3.141592653589793238462643383279502884197169399375105820974944592307816406286208998628
3.1415926535897932384626433832795028841971693993751058209749445923078164062862089986280
3.14159265358979323846264338327950288419716939937510582097494459230781640628620899862803
3.141592653589793238462643383279502884197169399375105820974944592307816406286208998628034
3.1415926535897932384626433832795028841971693993751058209749445923078164062862089986280348
3.14159265358979323846264338327950288419716939937510582097494459230781640628620899862803482
3.141592653589793238462643383279502884197169399375105820974944592307816406286208998628034825
3.1415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253
3.14159265358979323846264338327950288419716939937510582097494459230781640628620899862803482534
3.141592653589793238462643383279502884197169399375105820974944592307816406286208998628034825342
3.1415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421
3.14159265358979323846264338327950288419716939937510582097494459230781640628620899862803482534211
3.141592653589793238462643383279502884197169399375105820974944592307816406286208998628034825342117
3.1415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170
3.14159265358979323846264338327950288419716939937510582097494459230781640628620899862803482534211706
3.141592653589793238462643383279502884197169399375105820974944592307816406286208998628034825342117067
3.1415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679

```

## Explanation

First make the range \[0, *n*\], shown for *n* = 5

```
   i. >: 5
0 1 2 3 4 5

```

Multiply each by 8

```
   (*&8) i. >: 5
0 8 16 24 32 40

```

Form the addition table between `[1, 4, 5, 6]` and the products with 8

```
   (1 4 5 6+/*&8) i. >: 5
1  9 17 25 33 41
4 12 20 28 36 44
5 13 21 29 37 45
6 14 22 30 38 46

```

Divide each row by `[4, 2, -1, 1]`

```
   (4 2 _1 1%1 4 5 6+/*&8) i. >: 5
       4   0.444444  0.235294       0.16  0.121212   0.097561
     0.5   0.166667       0.1  0.0714286 0.0555556  0.0454545
    _0.2 _0.0769231 _0.047619 _0.0344828 _0.027027 _0.0222222
0.166667  0.0714286 0.0454545  0.0333333 0.0263158  0.0217391

```

Then reduce the columns from bottom-to-top using subtraction

```
   ([:-/4 2 _1 1%1 4 5 6+/*&8) i. >: 5
3.13333 0.129426 0.0422205 0.0207553 0.0123137 0.00814508

```

Divide each 16*k* for *k* in \[0, *n*\] by each result

```
   (16&^%~[:-/4 2 _1 1%1 4 5 6+/*&8) i. >: 5
3.13333 0.00808913 0.000164924 5.06722e_6 1.87893e_7 7.76775e_9

```

Find the cumulative sums

```
   ([:+/\16&^%~[:-/4 2 _1 1%1 4 5 6+/*&8) i. >: 5
3.13333 3.14142 3.14159 3.14159 3.14159 3.14159

```

Compute 10*k* for *k* in \[0, *n*\] and multiply it with each

```
   (10&^(*)[:+/\16&^%~[:-/4 2 _1 1%1 4 5 6+/*&8) i. >: 5
3.13333 31.4142 314.159 3141.59 31415.9 314159

```

Then floor each of the products

```
   (10&^(<.@*)[:+/\16&^%~[:-/4 2 _1 1%1 4 5 6+/*&8) i. >: 5
3 31 314 3141 31415 314159

```

Divide it by the same power of 10 to get the results

```
   (10&^(<.@*%[)[:+/\16&^%~[:-/4 2 _1 1%1 4 5 6+/*&8) i. >: 5
3 3.1 3.14 3.141 3.1415 3.14159

```

# Answer
> 3 votes
# C GCC, 118 bytes

Golfed:

```
main(){double k,a,s=1,t;k=a=0;while(k<15){t=k++*8;a+=(4/(t+1)-2/(t+4)-1/(t+5)-1/(t+6))/s;s*=16;printf("%.15lf\n",a);}}

```

Ungolfed:

```
main(){
    double k,a,s=1,t;
    k=a=0;
    while(k<15){
        t=k++*8;
        a+=(4/(t+1)-2/(t+4)-1/(t+5)-1/(t+6))/s;
        s*=16;
        printf("%.15lf\n",a);
    }
}

```

To change n, just change while(k\<15) to while(k \< n)

output:

```
$ gcc pigolf.c -o pigolf
some gcc screaming warnings
$ ./pigolf
3.133333333333333
3.141422466422466
3.141587390346582
3.141592457567436
3.141592645460336
3.141592653228088
3.141592653572881
3.141592653588973
3.141592653589752
3.141592653589791
3.141592653589793
3.141592653589793
3.141592653589793
3.141592653589793
3.141592653589793

```

max precision is 15 decimal places, i could increase to any value with gmp, but maybe next pi day :P

## with pretty print, 143 bytes

Golfed:

```
main(){double k,a,s=1,t;char o[19];k=a=0;while(k<15){t=k++*8;a+=(4/(t+1)-2/(t+4)-1/(t+5)-1/(t+6))/s;s*=16;snprintf(o,k+3,"%.15lf",a);puts(o);}}

```

Ungolfed:

```
main(){
    double k,a,s=1,t;
    char o[19];
    k=a=0;
    while(k<15){
        t=k++*8;
        a+=(4/(t+1)-2/(t+4)-1/(t+5)-1/(t+6))/s;
        s*=16;
        snprintf(o,k+3,"%.15lf",a);
        puts(o);
    }
}

```

output:

```
$ gcc pigolf_pretty.c -o pigolf_pretty
more gcc screaming warnings
$ ./pigolf_pretty
3.1
3.14
3.141
3.1415
3.14159
3.141592
3.1415926
3.14159265
3.141592653
3.1415926535
3.14159265358
3.141592653589
3.1415926535897
3.14159265358979
3.141592653589793

```

# Answer
> 2 votes
## Haskell, ~~101~~ 100 bytes

Thanks to @nimi for a byte.

```
f n=take(n+2).show$sum[1/16^k*(4/(l+1)-2/(l+4)-1/(l+5)-1/(l+6))|k<-[0..100+n],l<-[8*fromIntegral k]]

```

Straightforward implementation. Calculates `n` up to 15 digits (standard double precision).

# Answer
> 2 votes
# IBM/Lotus Notes Formula, 125 bytes

```
p:=0;@For(n:=0;n<=a;n:=n+1;b:=8*n;p:=p+@Power(16;-n)*(4/(b+1)-2/(b+4)-1/(b+5)-1/(b+6));o:=o:@Left(@Text(p);n+@If(n=0;1;2)));o

```

Formula in a computed field with another field called "a" for input.

Basically a port of the algorithm from the Python answer from @shebang. Calculates up to 15 digits after which it truncates due to a limitation of the language (see output). Had to waste 12 bytes with the @If statement at the end just to get rid of the . after the 3 at the start :-/

**Ungolfed**

```
p:=0;
@For(n:=0; n<=a; n:=n+1;
 b:=8*n;
 p:=p+@Power(16;-n)*(4/(b+1)-2/(b+4)-1/(b+5)-1/(b+6));
 o:=o:@Left(@Text(p);n+@If(n=0;1;2))
 );
o

```

# Answer
> 0 votes
# C#, 183 bytes

Golfed:

```
void F(int n){double s=0;for(int k=0;k<=n;k++){s+=1/Math.Pow(16,k)*(4.0/(8*k+1)-2.0/(8*k+4)-1.0/(8*k+5)-1.0/(8*k+6));double p=Math.Pow(10,k);Console.WriteLine(Math.Truncate(s*p)/p);}}

```

Ungolfed:

```
void F(int n)
{
    double s = 0;

    for (int k = 0; k <= n; k++)
    {
        s += 1/Math.Pow(16, k)*(4.0/(8*k + 1) - 2.0/(8*k + 4) - 1.0/(8*k + 5) - 1.0/(8*k + 6));
        double p = Math.Pow(10, k);

        Console.WriteLine(Math.Truncate(s*p)/p);
    }
}

```

# Answer
> 0 votes
# APL(NARS), 206 chars, 412 bytes

```
fdn←{1∧÷⍵}⋄fnm←{1∧⍵}⋄r2fs←{q←⌈-/10x⍟¨(fdn ⍵),fnm ⍵⋄m←⎕ct⋄⎕ct←0⋄a←⌊⍵×10x*⍺⋄⎕ct←m⋄k←≢b←⍕a⋄0≥k-⍺:'0.',((⍺-k)⍴'0'),b⋄((k-⍺)↑b),'.',(k-⍺)↓b}⋄p←{+/¨{k←1+8×⍵⋄(+/4 2 1 1÷k,-k+3..5)÷16*⍵}¨¨{0..⍵}¨0..⍵}⋄q←{⍪⍵r2fs¨p⍵}

```

This find all approssimation in big rational, than use one function that convert big rational in numeric string... test:

```
 q 1x
3.1
3.1
  q 2x
3.13
3.14
3.14
  q 3x
3.133
3.141
3.141
3.141
  q 10x
3.1333333333
3.1414224664
3.1415873903
3.1415924575
3.1415926454
3.1415926532
3.1415926535
3.1415926535
3.1415926535
3.1415926535
3.1415926535
  q 20x
3.13333333333333333333
3.14142246642246642246
3.14158739034658152305
3.14159245756743538183
3.14159264546033631955
3.14159265322808753473
3.14159265357288082778
3.14159265358897270494
3.14159265358975227523
3.14159265358979114638
3.14159265358979312961
3.14159265358979323271
3.14159265358979323815
3.14159265358979323844
3.14159265358979323846
3.14159265358979323846
3.14159265358979323846
3.14159265358979323846
3.14159265358979323846
3.14159265358979323846
3.14159265358979323846
  q 57x
3.133333333333333333333333333333333333333333333333333333333
3.141422466422466422466422466422466422466422466422466422466
3.141587390346581523052111287405405052463875993287757993640
3.141592457567435381837004555057293394007389950594818748976
3.141592645460336319557021222442381831727406617979907186696
3.141592653228087534734378035536204469558528012197801934814
3.141592653572880827785240761895898484239065603786606461624
3.141592653588972704940777767170189446971120489811822860633
3.141592653589752275236177868398102225795024633409061087027
3.141592653589791146388776965910347414779015888488996772587
3.141592653589793129614170564041344858816452676296281615895
3.141592653589793232711292261930077163422606275435901151635
3.141592653589793238154766322501863827762609260414389714560
3.141592653589793238445977501940281666096938425156252904675
3.141592653589793238461732482037982486800056278143046732780
3.141592653589793238462593174670682882792683045699610435502
3.141592653589793238462640595138128445061235672871301070791
3.141592653589793238462643227424822458237094279625505676929
3.141592653589793238462643374515761485970237552267559842751
3.141592653589793238462643382784091514246623611329334708720
3.141592653589793238462643383251362615881909316518417908555
3.141592653589793238462643383277897474896408560218644955706
3.141592653589793238462643383279410929692483875831459799593
3.141592653589793238462643383279497597978087353533999465917
3.141592653589793238462643383279502579284902684600486947911
3.141592653589793238462643383279502866555094658758532859204
3.141592653589793238462643383279502883173477103651067488504
3.141592653589793238462643383279502884137610730938143080855
3.141592653589793238462643383279502884193695667358321264063
3.141592653589793238462643383279502884196966326705909950134
3.141592653589793238462643383279502884197157502154596455091
3.141592653589793238462643383279502884197168700950456888403
3.141592653589793238462643383279502884197169358296080453391
3.141592653589793238462643383279502884197169396954642664355
3.141592653589793238462643383279502884197169399232246022950
3.141592653589793238462643383279502884197169399366660542801
3.141592653589793238462643383279502884197169399374605817825
3.141592653589793238462643383279502884197169399375076175949
3.141592653589793238462643383279502884197169399375104060947
3.141592653589793238462643383279502884197169399375105716347
3.141592653589793238462643383279502884197169399375105814747
3.141592653589793238462643383279502884197169399375105820603
3.141592653589793238462643383279502884197169399375105820952
3.141592653589793238462643383279502884197169399375105820973
3.141592653589793238462643383279502884197169399375105820974
3.141592653589793238462643383279502884197169399375105820974
3.141592653589793238462643383279502884197169399375105820974
3.141592653589793238462643383279502884197169399375105820974
3.141592653589793238462643383279502884197169399375105820974
3.141592653589793238462643383279502884197169399375105820974
3.141592653589793238462643383279502884197169399375105820974
3.141592653589793238462643383279502884197169399375105820974
3.141592653589793238462643383279502884197169399375105820974
3.141592653589793238462643383279502884197169399375105820974
3.141592653589793238462643383279502884197169399375105820974
3.141592653589793238462643383279502884197169399375105820974
3.141592653589793238462643383279502884197169399375105820974
3.141592653589793238462643383279502884197169399375105820974

```

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