title: Impossible darts scores

text:
# Question
Title: Impossible darts scores
I was surprised to not find this asked already, though there is a great question on darts checkouts: Darts meets Codegolf

Your challenge is to calculate which scores are not possible with 'n' darts below the maximum score for 'n' darts. E.g. for n=3, the maximum possible score is 180 so you would return \[163,166,169,172,173,175,176,178,179\]

For a bare bones rule summary:

Possible scores for a single dart are:

* 0 (miss)
* 1-20, 25, 50
* double or triple of 1-20

Rules:

* standard code golf rules apply
* you must take a single parameter 'n' in whatever way your language allows and return a list/array of all unique scores below the maximum score which cannot be scored with n darts. You may also print these values to the console.
* order of results is unimportant
* shortest code in bytes wins

# Answer
# Python 3, ~~80~~ ~~79~~ ~~59~~ 57 bytes

-1 byte thanks to Arnauld
-20 bytes thanks to ArBo
-2 bytes thanks to negative seven

```
lambda x:[-i-~x*60for i in(x<2)*b'a[YUSOLI'+b'MJGDCA@>=']

```

Try it online!
> 32 votes

# Answer
# Perl 6, 42 bytes

```
{^60*$_∖[X+] [[|(^21 X*^4),25,50]xx$_,]}

```

Try it online!

Brute force solution that works out all possible dart values.
> 14 votes

# Answer
# JavaScript (ES6),  ~~55~~  54 bytes

*Saved 1 byte thanks to @Shaggy*

Based on the pattern used by Rod.

```
n=>[...1121213+[n-1?33:2121242426]].map(x=>n-=x,n*=60)

```

Try it online!
> 9 votes

# Answer
# Perl 6, 39 bytes (37 chars)

This is definitely using a massive sledgehammer but it works. (It doesn't just brute force it, it brutally brute forces it)

```
{^60*$_∖[X+] (|(^21 X*^4),25,50)xx$_}

```

Try it online!

Here's an explanation of it:

```
{                                   } anonymous block for the
       ∖                                set difference of
 ^60*$_                                   - 0 .. max score (60 * throwcount)
        [X+]                    xx$_      - the cross addition (throwcount times) of
             (                 )              all possible score values, being
              |(    X*  )                       flattened cross multiplication of
                ^21   ^4                          0..20 and 0..3 (for double and triple)
                         ,25,50                 and 25 and 50

```

The `X* ^4` cross multiplier generates a lot of duplicate values (there will be 20+ zeros involved and that's *before* doing the cross addition), but that doesn't cause any problems since we use the set difference  which works with the unique values.

This currently fails for `$n == 1` (which should return an empty set), but there is an issue filed and will likely work in future versions. JoKing's version is a teeny bit longer, but works for `$n == 1` in current Rakudo.
> 9 votes

# Answer
# Jelly, 19 bytes

```
20Ż;25×Ɱ3ẎṖœċ⁸§ṪṖḟƊ

```

Try it online!
> 8 votes

# Answer
# MATL, ~~25~~ 23 bytes

*Thanks to @Giuseppe, who fixed a mistake and golfed 2 bytes!*

```
25tE3:!21:q*vZ^!stP:wX-

```

Try it online!

### Explanation

Brute force approach.

```
25      % Push 25
tE      % Duplicate, double: gives 50
3:!     % Push column vector [1;2;3]
21:q    % Push row vector [0 1 ... 20]
*       % Multiply with broadcast. Gives a matrix with all products
v       % Concatenate everything into a column vector
Z^      % Implicit input: n. Cartesian power with exponent n
!s      % Sum of each row
tP      % Duplicate, flip: The first entry is now 60*n
:       % Push row vector [1 2 ... 60*n]
w       % Swap
X-      % Set difference. Implicit display

```
> 8 votes

# Answer
# , ~~48~~ 45 bytes

```
2&>(35 44,q:626b66jh)&,60&*-1 4 8 14,q:@13090

```

Try it online!

*-3 bytes thanks to FrownyFrog*

Attempted a brute force solution, but was not able to beat this translation of Rod's idea.
> 7 votes

# Answer
# , 64 bytes

```
function(n,`!`=utf8ToInt)c(60*n-!"",(!"#%),/")[n<2])

```

Try it online!

Ports the amazing answer found by Rod.

# , ~~85~~ ~~73~~ 68 bytes

```
function(n)setdiff(0:(60*n),combn(rep(c(0:20%o%1:3,25,50),n),n,sum))

```

Try it online!

Brute force generates all possible scores with `n` darts, then takes the appropriate set difference.

Credit to OrangeCherries' Octave solution for reminding me of `combn`.

5 more bytes thanks to Robin Ryder's suggestion of using `%o%`.
> 6 votes

# Answer
# Octave, ~~91 bytes~~ ~~73 bytes~~ 71 Bytes

Another brute force method.

```
@(n)setdiff(0:60*n,sum(combnk(repmat([x=0:20,x*2,x*3,25,50],1,n),n),2))

```

Down to ~~73 Bytes~~ thanks to Giuseppe
Down to 71 Bytes by replacing nchoosek with combnk

Try it online!
> 4 votes

# Answer
# Pyth, 22 bytes

```
-S*60Q+M^+yB25*M*U4U21

```

Try it online!

Times out in TIO for inputs greater than 3.

```
-S*60Q+M^+yB25*M*U4U21Q   Implicit: Q=eval(input())
                          Trailing Q inferred
                 U4       Range [0-3]
                   U21    Range [0-20]
                *         Cartesian product of the two previous results
              *M          Product of each
          yB25            [25, 50]
         +                Concatenate
        ^             Q   Cartesian product of the above with itself Q times
      +M                  Sum each
                            The result is all the possible results from Q darts, with repeats
  *60Q                    60 * Q
 S                        Range from 1 to the above, inclusive
-                         Setwise difference between the above and the possible results list
                          Implicit print

```
> 3 votes

# Answer
# Python 2, 125 bytes

```
lambda n:set(range(60*n))-set(map(sum,product(sum([range(0,21*j,j)for j in 1,2,3],[25,50]),repeat=n)))
from itertools import*

```

Try it online!

---

# Python 3, ~~126~~ ~~125~~ 122 bytes

```
lambda n:{*range(60*n)}-{*map(sum,product(sum([[i,i*2,i*3]for i in range(21)],[25,50]),repeat=n))}
from itertools import*

```

Try it online!

-3 bytes, thanks to Rod
> 2 votes

# Answer
# Stax, 24 bytes

```
¿ß☺o↕αg╠╩╬ò▼í¬«¥↕▄í■♣▓î►

```

Run and debug it

It's pretty slow for n=3, and gets worse from there.
> 2 votes

# Answer
# 05AB1E, ~~21~~ ~~20~~ 18 bytes

```
20Ý25ª3Lδ*˜¨ãOZÝsK

```

-3 bytes thanks to *@Grimy*.

Times out pretty quickly the higher the input goes due to the cartesian product builtin `ã`.

Try it online or verify a few more test cases.

**Explanation:**

```
20Ý                 # Push a list in the range [0, 20]
   25ª              # Append 25 to this list
      3L            # Push a list [1,2,3]
        δ*          # Multiply the top two lists double-vectorized:
                    #  [[0,0,0],[1,2,3],[2,4,6],[3,6,9],...,[20,40,60],[25,50,75]]
          ˜         # Flatten this list: [0,0,0,1,2,...,40,60,25,50,75]
           ¨        # Remove the last value (the 75)
            ã       # Create all possible combinations of the (implicit) input size,
                    # by using the cartesian power
             O      # Sum each inner list of input amount of values together
              Z     # Get the maximum (without popping the list), which is 60*input
               Ý    # Create a list in the range [0, 60*input]
                s   # Swap so the initially created list is at the top of the stack again
                 K  # And remove them all from the [0, 60*input] ranged list
                    # (then output the result implicitly)

```
> 2 votes

# Answer
# Jelly, 28 bytes

```
21Ḷ×þ3R¤;25;50FœċµS€³×60¤R¤ḟ

```

Try it online!
> 1 votes

# Answer
# MathGolf, 26 bytes

```
╟*rJrN▐3╒*mÅ~*╡ak.ε*mÉa─Σ-

```

Try it online!

-2 bytes thanks to Kevin Cruijssen

## Explanation

```
╟*r                          push [0, ..., 60*input-1]
   Jr                        push [0, ..., 20]
     N▐                      append 25 to the end of the list
       3╒                    push [1, 2, 3]
         *                   cartesian product
          mÅ                 explicit map
            ~                evaluate string, dump array, negate integer
             *               pop a, b : push(a*b)
              ╡              discard from right of string/array
               a             wrap in array
                k            push input to TOS
                 .           pop a, b : push(b*a) (repeats inner array input times)
                  ε*          reduce list with multiplication (cartesian power)
                    mÉ       explicit map with 3 operators
                      a      wrap in array (needed to handle n=1)
                       ─     flatten array
                        Σ    sum(list), digit sum(int)
                         -   remove possible scores from [0, 60*input-1]

```
> 1 votes

# Answer
# Wolfram Language (Mathematica), 69 bytes

```
Complement[Range[60#],Tr/@{Array[1##&,{4,21},0,##&],25,50}~Tuples~#]&

```

Try it online!

Based off of lirtosiast's answer.

`Array`'s third argument specifies the offset (default 1), and its fourth argument specifies the head to use instead of `List`. `##&` is equivalent to `Sequence`, so `Array[1##&,{4,21},0,##&]` returns a (flattened) `Sequence` containing members of the outer product of `0..3` and `0..20`.
> 1 votes

# Answer
# Charcoal, 36 bytes

```
Ｉ⁺Ｅ…wvtsqpmjgkhea_[YS⎇⊖θ⁹¦¹⁷℅ι×⁶⁰⁻θ²

```

Try it online! Link is to verbose version of code. Uses @Rod's algorithm; brute force would have taken 60 bytes. Works by truncating the string to 9 characters if the input is greater than 1, then taking the ordinals of the characters and adding the appropriate multiple of 60.
> 0 votes

# Answer
# Perl 5 `-n`, ~~96~~ ~~93~~ 91 bytes

```
$"=',';@b=map{$_,$_*2,$_*3,25,50}0..20;map$r[eval]=1,glob"+{@b}"x$_;map$r[$_]||say,0..$_*60

```

Try it online!

It was optimized for code length rather than run time, so it's kind of slow. It generates a lot of redundant entries for its lookup hash. Running the `@b` array through `uniq` speeds it up greatly, but costs 5 more bytes, so I didn't do it.
> 0 votes

# Answer
# Wolfram Language (Mathematica), 81 bytes

```
Complement[Range[60#-1],Total/@Tuples[Flatten[{Array[Times,{3,20}],0,25,50}],#]]&

```

Try it online!

Mathematica has a few related builtins including `FrobeniusSolve` and the restricted form of `IntegerPartitions`, but none of them are shorter than brute force.
> 0 votes

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

```
(a,b)=>(int)Math.Pow(a,b);f=n=>{var l=new List<int>(new int[21].SelectMany((_,x)=>new[]{x,x*2,x*3})){25,50};int a=l.Count,b,c,d,e=P(a,n),f;var r=new int[e];for(b=e;b>0;b--)for(c=0;c<n;c++){d=b;while(d>P(a,c+1))d-=P(a,c+1);f=(d/P(a,c))-1;r[b-1]+=l[f>0?f:0];}return Enumerable.Range(0,l.Max()*n).Except(r);}

```

Well, there doesn't seem to be an easy way of calculating all the possible combinations in C#, so this disaster of a code is all I could come up with.

Plus it takes about 30s to complete...

Would love to see a better solution.

```
P=(a,b)=>(int)Math.Pow(a,b);
F=n=>
{
    var l=new List<int>(new int[21].SelectMany((_,x)=>new[]{x,x*2,x*3})){25,50};
    int a=l.Count,b,c,d,e=P(a,n),f;
    var r=new int[e];
    for(b=e;b>0;b--)
        for(c=0;c<n;c++)
        {
            d=b;
            while(d>P(a,c+1))
                d-=P(a,c+1);
            f=(d/P(a,c))-1;
            r[b-1]+=l[f>0?f:0];
        }
    return Enumerable.Range(0,l.Max()*n).Except(r);
}

```

Try it online!
> 0 votes

# Answer
# Kotlin, 118 bytes

```
{n:Int->val i=if(n<2)listOf(23,24,31,25,37,41,44,47)
else
List(0){0}
i+List(9){n*60-listOf(17,14,11,8,7,5,4,2,1)[it]}}

```

Try it online!
> 0 votes

---
Tags: code-golf
---


# Question
Title: Does this addition pyramid puzzle have a unique solution?
Given an addition pyramid \\$P\\$, determine whether it can be solved. An addition pyramid consists of *layers*, each having one number less than the one below it. Layer \\$i\\$ is symbolized as \\$P\_i\\$. \\$P\_1\\$ is the base layer, and \\$P\_{i+1}\\$ is the layer atop \\$P\_i\\$. The \\$j\\$th number of \\$P\_i\\$ is denoted as \\$P\_{i,j}\\$. \\$P\_{i,1}\\$ is the leftmost number of \\$P\_i\\$, and \\$P\_{i,j+1}\\$ is the number to the right of \\$P\_{i,j}\\$. You may visualize \\$P\_{i+1,j}\\$ residing on top of \\$P\_{i,j}\\$ and \\$P\_{i,j+1}\\$ at the middle, hence the name "addition *pyramid*".

* \\$\forall P\_{i,j},P\_{i,j}\in\mathbb N^\*\\$, that is, every number in the pyramid is a non-zero positive integer.
* \\$\forall i\>1,P\_{i,j}=P\_{i-1,j}+P\_{i-1,j+1}\\$, that is, every number not on the base layer of the pyramid is the sum of the two numbers below it.
* If \\$P\_1\\$ has \\$n\\$ numbers, \\$P\_i\\$ has \\$n-i+1\\$ numbers, therefore \\$P\_{i,n-i+1}\\$ is the rightmost number of \\$P\_i\\$. In simpler terms, each layer has one number less than the layer below it.

An *addition pyramid puzzle* \\$Q\\$ is an addition pyramid with some numbers removed (replaced with \\$?\\$). Its solution is an addition pyramid \\$P\\$, where \\$\forall Q\_{i,j}\ne{?},P\_{i,j}=Q\_{i,j}\\$, that is, the numbers that were originally present in the puzzle have been left unchanged. Such a puzzle may have more than one solution.

Your job is, given an addition pyramid puzzle, to determine if it has exactly one solution.

## Input

You can get input in any of the following forms, but be consistent:

* Array of layers.
* Array of layers, shaped like a pyramid using a consistent non-positive-integer value as a separator between elements (used only once each time) as well as left and right padding. The separator and the padding must be the same.
* Array of layers with a consistent valid right or left padding (you must be consistent and not mix right and left padding in this case).

Please note that a consistent value that's not a strictly positive integer must be used to represent a missing number; this value can't be used as padding. Also, you can take the layers concatenated (you can still separate them), and the ordering can either be from the base to the top or from the top to the base.

## Output

One of two consistent distinct values, where one represents the presence of a unique solution and the other the absence of a solution or the presence of more than one solution.

## Rules

* \\$Q\_{i+1,j}=Q\_{i,j}+Q\_{i,j+1}\\$ will always be true if \\$Q\_{i,j},Q\_{i,j+1},Q\_{i+1,j}\in\mathbb N^\*\\$, that is, the input is guaranteed to not contain a number on top of two other numbers that isn't their sum if all three numbers are known.
* \\$\exists Q\_{i,j},Q\_{i,j}\ne{?}\\$, that is, the pyramid will contain at least one known number.
* Don't do these things.
* This is , so the shortest answer wins! However, don't let that discourage you from posting a solution just because your language is "too verbose".

## Test cases

An array with the layers from the top to the base is used for these test cases, with `0` representing \\$?\\$.

```
[[10], [0, 0], [0, 2, 0], [0, 0, 0, 1]] -> True
[[32], [0, 0], [0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0]] -> True
[[0], [1, 1]] -> True
[[1], [0, 0]] -> False
[[10], [5, 5], [2, 3, 2], [0, 0, 0, 0]] -> False
[[5], [0, 0], [0, 0, 0]] -> False

```

## Worked examples

The test cases are worked here.

### Unique solution 1

$$\begin{array}c&&&10\\\&&?&&?\\\&?&&2&&?\\\?&&?&&?&&1\end{array}$$

Step 1: \\$x+y=2\leftrightarrow x=y=1\\$.

$$\begin{array}c&&&10\\\&&?&&?\\\&?&&2&&?\\\?&&\color{red}1&&\color{red}1&&1\end{array}$$

Step 2: \\$x=y=1\leftrightarrow x+y=2\\$.

$$\begin{array}c&&&10\\\&&?&&?\\\&?&&2&&\color{red}2\\\?&&1&&1&&1\end{array}$$

Step 3: \\$x=y=2\rightarrow x+y=4\\$.

$$\begin{array}c&&&10\\\&&?&&\color{red}4\\\&?&&2&&2\\\?&&1&&1&&1\end{array}$$

Step 4: \\$x+4=10\leftrightarrow x=6\\$.

$$\begin{array}c&&&10\\\&&\color{red}6&&4\\\&?&&2&&2\\\?&&1&&1&&1\end{array}$$

Steps 5-6 are similar to 4.

$$\begin{array}c&&&10\\\&&6&&4\\\&\color{red}4&&2&&2\\\color{red}3&&1&&1&&1\end{array}$$

So here we have our unique solution.

### Unique solution 2

$$\begin{array}c&&&&&32\\\&&&&?&&?\\\&&&?&&?&&?\\\&&?&&?&&?&&?\\\&?&&?&&?&&?&&?\\\?&&?&&?&&?&&?&&?\end{array}$$

Step 1: There's no obvious approach here, so let's try using the minimum possible values.

$$\begin{array}c&&&&&32\\\&&&&?&&?\\\&&&?&&?&&?\\\&&?&&?&&?&&?\\\&?&&?&&?&&?&&?\\\color{red}1&&\color{red}1&&\color{red}1&&\color{red}1&&\color{red}1&&\color{red}1\end{array}$$

Steps 2-5: It looks like the minimum values result in a solution, therefore this is the only solution and is therefore unique.

$$\begin{array}c&&&&&32\\\&&&&\color{red}{16}&&\color{red}{16}\\\&&&\color{red}8&&\color{red}8&&\color{red}8\\\&&\color{red}4&&\color{red}4&&\color{red}4&&\color{red}4\\\&\color{red}2&&\color{red}2&&\color{red}2&&\color{red}2&&\color{red}2\\1&&1&&1&&1&&1&&1\end{array}$$

Hint: There's a theorem about addition pyramid puzzles related to this puzzle that you can prove if you think hard enough.

### Unique solution 3

$$\begin{array}c&?\\1&&1\end{array}$$

Step 1: \\$x=y=1\rightarrow x+y=2\\$.

$$\begin{array}c&\color{red}2\\1&&1\end{array}$$

This is an obviously unique solution.

### No solution 1

$$\begin{array}c&1\\\?&&?\end{array}$$

\\$\min\mathbb N^\*=1\rightarrow x,y\ge1\rightarrow x+y\ge2\>1\\$, so there is no solution.

### No solution 2

$$\begin{array}c&&&10\\\&&5&&5\\\&2&&3&&2\\\?&&?&&?&&?\end{array}$$

Steps 1-2: \\$x+y=2\leftrightarrow x=y=1\\$.

$$\begin{array}c&&&10\\\&&5&&5\\\&2&&3&&2\\\color{red}1&&\color{red}1&&\color{red}1&&\color{red}1\end{array}$$

From there, it follows that \\$1+1=3\\$, which is a contradiction, therefore there's no solution.

### Non-unique solution

$$\begin{array}c&&5\\\&?&&?\\\?&&?&&?\end{array}$$

Two solutions:

$$\begin{array}c&&5&&&&&&&5\\\&2&&3&&&&&3&&2\\1&&1&&2&&&2&&1&&1\end{array}$$

Since there are at least two solutions, there's no unique solution.

# Answer
# Jelly, ~~18~~ 16 bytes

```
FṀ‘ṗLSƝƬ€Ṗ€a@ċ⁼1

```

Try it online!

A monadic link that takes the pyramid in reverse order and returns 1 for true and 0 for false. Generates all possible pyramids with a base up to the max number in the pyramid and checks whether there is one unique match for the input.

Thanks to @Arnauld for pointing out that this failed for `[[1,0],[0]]`; now corrected.

Thanks to @JonathanAlan for saving 2 bytes!

## Explanation

```
F                | Flatten
 Ṁ               | Maximum
  ‘              | Increase by 1
   ṗ             | Cartesian power of this with:
    L            | - Length of input
        €        | For each:
       Ƭ         | - Repeat the following until no change
     SƝ          |   - Sum of neighbours
         Ṗ€      | Remove last element from each list
           a@    | Logical and input with each list
             ċ   | Count times input appears
              ⁼1 | Check if equal to 1

```
> 5 votes

# Answer
# C# (Visual C# Interactive Compiler), ~~303~~ 227 bytes

```
n=>{int i=n.Max(x=>x.Max()),j=n.Count,t=0,k,m=0,z;for(;t<Math.Pow(i,j);){k=t++;var s=n.Select(_=>(a:k%i+1,k/=i).a).ToList();if(n.All(x=>(z=0,b:x.All(o=>o==s[z++]|o<1),s=s.Skip(1).Select((a,b)=>a+s[b]).ToList()).b))m++;}m/=m-1;}

```

Throws exception if true, runs normally if false.

Try it online!
> 2 votes

# Answer
# Wolfram Language (Mathematica), ~~85~~ 88 bytes

```
Count[l=Length@#;NestList[2#~MovingMedian~2&,#,l-1]&/@Range@Max@#~Tuples~l,#/. 0->_]==1&

```

Try it online!

+3 fixed.

Brute force: for all bases with values `1..*(sum of all numbers)*`, see if the resulting pyramid matches the given form, and check if the total number of matches is 1. Takes input as a list of levels, base first, with `0` representing missing numbers.
> 1 votes

# Answer
# 05AB1E, 25 bytes

```
ZÌLsgãε©.Γü+}¨®š.S*˜O_}OΘ

```

Takes the pyramid layers in upside down order, base to tip (i.e. `[[0,0,0,1],[0,2,0],[0,0],[10]]`).

Also, there seems to be a bug somewhere in 05AB1E with  inside a map.. The `©...®š` should just be `...yš` for -1 byte..

Try it online or verify a few more test cases.

A minor equal-bytes alternative for `©.ΓüO}®š` could be `[Ðg#üO}\)`: Try it online.

**Explanation:**

```
Z        # Get the flattened maximum of the (implicit) input (without popping)
 Ì       # Increase it by 2
  L      # Create a list in the range [1, max+2]
   sg    # Swap to get the input again, and get the length (amount of layers)
     ã   # Create a cartesian product of this list repeated that many times
ε        # Map each inner list to:
 ©       #  Store it in variable `®` (without popping)
  .Γ     #  Collect all results until the following doesn't change anymore:
    ü    #   Get the pairwise:
     +   #    Sums
   }®š   #  After we've collected all, prepend the original list `®`
 .S      #  Now compare this potential pyramid with the (implicit) input-pyramid
         #  (-1 if a<b; 0 if a==b; 1 if a>b)
   *     #  Multiply that with the (implicit) input-pyramid
    ˜O   #  Then take the flattened sum
      _  #  And check that this sum equals 0 (1 if truhy; 0 if falsey)
}O       # After the map, take the sum to get the amount of truthy values
  Θ      # And trutify it (== 1), since we must output distinct values instead of truthy/falsey
         # (after which the result is output implicitly)

```
> 1 votes

# Answer
## Haskell, 106 bytes

```
z=zipWith
a#b=a*b==a*a
f x=[1|t<-mapM(\_->[1..sum(sum<$>x)])x,all and$z(z(#))x$iterate(z(+)=<<tail)t]==[1]

```

Takes an upside down pyramid, e.g. `[[0,0,0,1],[0,2,0],[0,0],[10]]`.

Try it online!

The brute force approach in Haskell:

* create all possible base layers `t` (`mapM(\_->[1..sum(sum<$>x)])x`), where the numbers go from 1 to the sum of all numbers in the input pyramid
* create a pyramid from `t` (`iterate(z(+)=<<tail)t`)
* compare each layer element-wise with the input (`z(z(#))x`). The comparison function `a # b` returns `True` if both numbers are equal or `a` is zero (`a*b==a*a`).
* take a `1` for every pyramid that matches and compare the resulting list to the singleton list `[1]`.
> 0 votes

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


title: Move arrows along a contour

text:
# Question
Title: Move arrows along a contour
Sandboxed

Given a set of closed non-overlapping 2d contours (separated by at least one space even on diagonals) with arrows oriented consistently in the same clockwise or counter-clockwise direction (each contour has its own direction) and a positive number `n`, move the arrows `n` steps along the contours in the respective direction. The arrows are represented by `> v < ^` respectively for right, down, left and up directions. There the other characters are `-` (horizontal), `|` (vertical) and `+` (corner). When an arrow is on a corner, it keeps its current direction and changes it only after the turn is taken.

There will always be a straight segment (or a space) between any two corners (like `+-+` for the horizontal and similar for the vertical) - in other words the sharp `U` turns are forbidden. The segments between the corners are either vertical or horizontal and the bend at a corner is always 90 degree.

# Input:

* a positive integer - `n` \- number of steps
* an ASCII representation of the contours - it can be a multiline string, a list of strings, a list of characters and so on.

# Output:

The same contours with all arrows shifted `n` steps in each contour's overall direction.

# Test cases:

# 1.

Input:

`n` = 1

```
 +----->->
 |       |
 |       v---+
 |           |
 +---<-------+

```

Output:

```
 +------>+
 |       v
 |       +>--+
 |           |
 +--<--------+

```

# 2.

Input:

`n` = 2

```
 +-----+ +---+
 |     | |   |
 +-->--+ |   v
         |   |
 +--->---+   |
 |           |
 +------<<---+

```

Output:

```
 +-----+ +---+
 |     | |   |
 +---->+ |   |
         |   |
 +----->-+   v
 |           |
 +----<<-----+

```

# 3.

Input:

`n` = 3

```
 +---+   +---+   +-------+
 |   |   |   v   |       |
 ^   |   |   |   +-<-+   |
 |   |   ^   |       |   v
 |   +---+   +-->----+   |
 |                       |
 |   +-------+   +---+   |
 |   |       |   v   |   |
 +---+       +---+   +---+

```

Output:

```
 +>--+   ^---+   +-------+
 |   |   |   |   ^       |
 |   |   |   |   +---+   |
 |   |   |   |       |   |
 |   +---+   v----->-+   |
 |                       |
 |   +-------+   +---+   v
 |   |       |   |   |   |
 +---+       +-<-+   +---+

```

# 4.

Input:

`n` = 1

```
+--+
|  |
|  +---+
|      |
+----+ |
     | |
     +-+

```

Output:

```
+--+
|  |
|  +---+
|      |
+----+ |
     | |
     +-+

```

# 5.

Input

`n` = 4

```
^>>>>
^   v
^   v>>>>
^       v
<<<<<<<<v

```

Output:

```
^>>>>
^   v
^   v>>>>
^       v
<<<<<<<<v

```

# 6.

Input:

`n` = 1

```
^->
^ v
<<v

```

Output:

```
^>+
^ v
<<v

```

Write a function or a program solving the above task. The shortest code in bytes in every language wins. Don't be discouraged by the golfing languages. Explanation of the algorithm and the code is highly appreciated.

# Answer
> 15 votes
# JavaScript (ES6),  ~~210 ... 182~~  180 bytes

Takes input as `(m)(n)`, where \\$m\\$ is a list of lists of characters. Returns the result in the same format.

```
m=>g=n=>n?g(n-1,m=m.map((r,y)=>r.map((c,x)=>(i=0,h=$=>~$?(m[Y=y+($-2)%2]||0)[X=x+~-$%2]>h?"-|+"[n+=`;m[${Y}][${X}]=S[${$}]`,i?2:$&1]:h($^++i):c)((S="<^>v").indexOf(c)))),eval(n)):m

```

Try it online!

## How?

You can follow this link to see a formatted version of the source.

### Wrapper

The recursive function \\$g\\$ is just used as a wrapper that invokes the main code to move all arrows by 1 step and keeps calling itself with \\$n-1\\$ until \\$n=0\\$.

### Update method

We can't safely move each arrow one at a time because we would run the risk of overwriting non-updated arrows with updated ones. Instead, we first remove all arrows and compute their new positions. We apply the new positions in a second time.

This is done by re-using \\$n\\$ as a string to store the position updates as JS code.

For instance, in the first test case, \\$n\\$ is set to:

```
"1;m[0][7]=S[2];m[1][8]=S[3];m[2][9]=S[2];m[4][3]=S[0]"

```

(Note that the leading number -- which is the original value of \\$n\\$ -- is harmless.)

The new positions are applied by just doing `eval(n)`.

### Directions

Each arrow is converted into a direction \\$d\\$ (named `$` in the code), using the following compass:

$$\begin{matrix} &1\\ 0&+&2\\ &3 \end{matrix}$$

The corresponding values of \\$dx\\$ and \\$dy\\$ are computed this way:

```
 d | dx = (d - 1) % 2 | dy = (d - 2) % 2
---+------------------+------------------
 0 |        -1        |         0
 1 |         0        |        -1
 2 |        +1        |         0
 3 |         0        |        +1

```

### Corners

If the next character in the identified direction is a space or is out of bounds, it means that we're located on a corner and we need to take a 90° or 270° turn. This is why the helper function \\$h\\$ is testing up to 3 distinct directions: \\$d\\$, \\$d\operatorname{xor}1\\$ and \\$d\operatorname{xor}3\\$.

If we're located on a corner, we overwrite the cell with `+`. Otherwise, we overwrite it with either `-` or `|`, depending on the parity of \\$d\\$.

**Note**: The parameter of \\$h\\$ is not named `$` just because it looks uber l33t but also because it allows us to compare a given character with \\$h\\$ (implicitly coerced to a string) to know if it's a space (below `"$"`), a contour character (above `"$"`) or another arrow (also above `"$"`).

## Animated version

```
f=
m=>g=n=>n?g(n-1,m=m.map((r,y)=>r.map((c,x)=>(i=0,h=$=>~$?(m[Y=y+($-2)%2]||0)[X=x+~-$%2]>h?"-|+"[n+=`;m[${Y}][${X}]=S[${$}]`,i?2:$&1]:h($^++i):c)((S="<^>v").indexOf(c)))),eval(n)):m

m = [
  [..."+---+   +---+   +-------+"],
  [..."|   |   |   v   |       |"],
  [..."^   |   |   |   +-<-+   |"],
  [..."|   |   ^   |       |   v"],
  [..."|   +---+   +-->----+   |"],
  [..."|                       |"],
  [..."|   +-------+   +---+   |"],
  [..."|   |       |   v   |   |"],
  [..."+---+       +---+   +---+"]
];

(F = _ => (o.innerHTML = m.map(r => r.join('')).join('\n'), m = f(m)(1), window.setTimeout(F, 100)))()
```

```
<pre id=o></pre>
```

# Answer
> 8 votes
# K (ngn/k), ~~183 161 157~~ 155 bytes

```
{A:"^>v<";D,:-D:(-1 0;!2);s:#'1*:\x;r:" -+|"r*+/'3':|0,|0,r:~^x;$[p:+s\&~^t:A?,/x;;:r];s#@[,/r;s/+q;:;A@D?-p-q:q@'*'&'~^x ./:/:q:+p+/:D@4!(t^0N)+/:0 1 3]}/

```

Try it online!

`{` `}/` when called with an int left arg n, this will apply the function in `{` `}` n times to the right arg

`A:"^>v<"` arrows

`D,:-D:(-1 0;!2)` ∆y,∆x for the 4 cardinal directions

`s:#'1*:\x` shape of the input: height,width

`r:~^x` countours - boolean matrix showing where the non-spaces are

`r:" -+|"r*+/'3':|0,|0,r` recreate the character matrix with a countour but without arrows, by counting self+upper+lower for each cell in `r` and replacing 1-\>`-`, 2-\>`+`, 3-\>`|`

`t:A?,/x` types of arrows: 0 1 2 3 for `^>v<`, all other cells are represented as `0N` (null)

`p:+s\&~^t` coordinates of the arrows

`$[#p` `;;:r]` if there aren't any arrows, return `r`

`q:+p+/:D@4!(t^0N)+/:0 1 3` all 3 possible new positions for each arrow - if it keeps going forward, if it turns left, and if it turns right

`q:q@'*'&'~^x ./:/:q` for each arrow choose the first option that lands on the countour

`@[,/r;s/+q;:;A@D?q-p]` flatten `r` and put on it the arrows at their new positions and with their new directions

`s#` reshape to the original shape

# Answer
> 5 votes
# Charcoal, 105 bytes

```
Ｗ¬ΦυΣκ⊞υＳ≔⊟υη≔⪫υ⸿θ≔⟦⟧υ≔>^<vζＰθＦθ¿№ζι«⊞υ⟦⌕ζιⅉⅈ⟧§+|-↨ＥＫＶ›κ ²»ιＦυ«Ｊ⊟ι⊟ι≔⊟ιιＦＩη«≔⊟Φ⁴∧﹪⁻⊖ι⊕λ⁴›§ＫＶ⁻⁵λ ιＭ✳⊗ι»§ζι

```

Try it online! Link is to verbose version of code. Includes 22 bytes used to avoid requiring a cumbersome input format. Explanation:

```
Ｗ¬ΦυΣκ⊞υＳ≔⊟υη≔⪫υ⸿θ≔⟦⟧υ

```

Conveniently input the contours and the number of steps.

```
≔>^<vζ

```

The direction characters are used several times so the string is cached here. The index of a direction character in this string is known as its direction.

```
Ｐθ

```

Print the original contours without moving the cursor.

```
Ｆθ

```

Loop over the characters in the contour.

```
¿№ζι«

```

If the current characters is a direction character...

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

```

... then save the direction and position in a list...

```
§+|-↨ＥＫＶ›κ ²

```

... and replace the character with the appropriate line character.

```
»ι

```

Otherwise output the character and move on to the next character.

```
Ｆυ«

```

Loop over the saved positions.

```
Ｊ⊟ι⊟ι

```

Jump to the saved position.

```
≔⊟ιι

```

Extract the saved direction.

```
ＦＩη«

```

Loop over the appropriate number of steps.

```
≔⊟Φ⁴∧﹪⁻⊖ι⊕λ⁴›§ＫＶ⁻⁵λ ι

```

Find the direction of the next step, which is any direction that is neither reverse nor empty.

```
Ｍ✳⊗ι

```

Take a step in that direction. (Charcoal direction indices for the `Move` command are twice the value of my direction.)

```
»§ζι

```

Print the appropriate direction character.

# Answer
> 3 votes
# APL (Dyalog Unicode), 111 bytesSBCS

```
{A[D⍳q-p]@q⊢' |+-'[c×3+/0,c,0]⊣q←⊃¨(⍸c←' '≠⍵)∘∩¨↓⍉D[4|0 1 3∘.+4~⍨,t]+⍤1⊢p←⍸4>t←⍵⍳⍨A←'v>^<'⊣D←9 11∘○¨0j1*⍳4}⍣⎕⊢⎕

```

Try it online!

similar to my k answer

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


title: Primitive Pythagorean Triples

text:
# Question
Title: Primitive Pythagorean Triples
(related)

A *Pythagorean Triple* is a list `(a, b, c)` that satisfies the equation *a2 \+ b2 = c2*.

A *Primitive* Pythagorean Triple (PPT) is one where `a`, `b`, and `c` are all coprime (i.e., the only common divisor between the three elements is `1`). For example, the `(3, 4, 5)` right triangle is a famous Primitive Pythagorean Triple.

## The Challenge

* Given input `n`, output the `n`th PPT. Or,
* Given input `n`, output the first `n` PPTs.

There are multiple ways to order these PPTs to form a well-ordered list, to determine which is the `n`th. You can choose any ordering you want, so long as you can prove (informally is fine) that your algorithm can generate every possible unique PPT. For example, your code should not output both `(3,4,5)` and `(4,3,5)` since those are duplicates of the same triple -- one or the other, please.

Similarly, whether your code is zero- or one-indexed is fine, so long as you state which you're using.

## Examples

For the examples below, I'm using one-indexing, outputting the `n`th PPT, and ordering by smallest `c`, then smallest `a`, then smallest `b`.

```
n | output
1 | (3, 4, 5)
2 | (5, 12, 13)
5 | (20, 21, 29)
12| (48, 55, 73)

```

## Rules

* The input and output can be given in any convenient format.
* In your submission, please state how your entries are ordered, and whether your entries are 0-indexed or 1-indexed.
* Your chosen ordering cannot create duplicates.
* Either a full program or a function are acceptable. If a function, you can return the output rather than printing it.
* If possible, please include a link to an online testing environment so other people can try out your code!
* Standard loopholes are forbidden.
* This is so all usual golfing rules apply, and the shortest code (in bytes) wins.

# Answer
> 12 votes
# Jelly, ~~27~~ 25 bytes

*2 bytes thanks to Jonathan Allan.*

```
²IH;Pµ;ÆḊ
+2ḶḤ‘Œcg/ÐṂÇ€Ṣḣ

```

Try it online!

Outputs the first `n` 1-indexed triples `[b, a, c]`, sorted by increasing `b` and then `a`.

Uses the algorithm from Wikipedia:

This generates all primitive triples for all unique coprime pairs of odd integers `m > n > 0`.

### Explanation

```
+2ḶḤ‘Œcg/ÐṂÇ€Ṣḣ    Main link. Argument: n
+2                   Add 2 to n, to get enough results.
  Ḷ                  Get integers [0, 1, ..., n+1].
   Ḥ                 Double to get [0, 2, ..., 2n+2].
    ‘                Increment to get [1, 3, ..., 2n+3].
     Œc              Get all ordered pairs [[1, 3], [1, 5], ..., [2n+1, 2n+3]].
       g/            GCD of each pair.
         ÐṂ          Grab the pairs with minimal GCD (which is 1).
           Ç€        Call the helper link on each pair to get the triples.
             Ṣ       Sort the triples first by a, then by b, then by c.
              ḣ      Get the last n.

²IH;Pµ;ÆḊ    Helper link. Argument: pair [m, n]
²              Square to get [m², n²].
 I             Increments: get [m²-n²].
  H            Halve: get [(m²-n²)/2], i.e. [b].
    P          Product: get mn, i.e. a.
   ;           Append to get [b, a].
     µ         Begin a new monadic chain with argument [b, a].
       ÆḊ      Get the length of the vector, i.e. c.
      ;        Append to get [b, a, c].

```

# Answer
> 8 votes
# MATL, 36 bytes

```
`@:Ut&+wmR&fZd1Mhw/vXutnGE<]GY)t&2|h

```

Input is 1-based. The output order guarantees that each triple appears exactly once. The order is explained in the following. The explanation requires delving a little into how the program works.

The code keeps increasing a counter `k` in a loop, starting at `1`. For each `k` it generates all pairs with `a = 1,...,k`, `b = 1,...,k`, `a < b`, and picks those that give a Pythagorean triple with `c <= k`. The pairs are obtained in order of increasing `b`, then `a`.

Each pair is then divided by its gcd. The resulting (possibly duplicated) pairs are arranged as a two-column matrix. This matrix is vertically concatenated with a similar matrix containing the accumulated results obtained for smaller values of `k`. The rows of the matrix are then stably deduplicated. This removes *two* types of duplicates:

1. Pairs that have been found more than once for the current `k` (such as `3,4`, which also results from `6,8` when dividing by its gcd);
2. Pairs that were already found with smaller `k`.

In fact, each iteration `k` finds all pairs that were already found for previous iterations. But it may find them *in a different order*. For example, `k=25` will find the triple `7,24,25` and not `20,21,29` (because `c` cannot exceed `k`). Later on, iteration `k=29` will find both, but with `20,21,29` *before* `7,24,25` (order is increasing `b`, then `a`). This is why, instead of keeping all pairs found for the latest `k`, we append them to the previous ones and deduplicate stably. Doing so assures that the order is the same for any input `n`.

The above guarantees that each primitive Pythagorean triple will eventually appear, and it will appear only once. For input `n`, the loop over `k` finishes when at least `n` valid triples have been obtained; and then the `n`-th triple is ouput.

Try it online!

Or use this modified code to see the first `n` triples:

```
`@:Ut&+wmR&fZd1Mhw/vXutnGE<]G:Y)tU&2sX^h

```

Try it online!

# Answer
> 8 votes
# Haskell, 98 bytes

```
f 0=(3,4,5)
f n|let(a,b,c)=f$div(n-1)3;r=mod n 3;d=a*(-1)^2^r;e=b*(-1)^r;s=2*(d+e+c)=(s-d,s-e,s+c)

```

Try it online!

### How it works

This interprets the bijective base-3 digits of *n* as a path down the tree of primitive Pythagorean triples. It runs with no searching in O(log *n*) operations.

# Answer
> 5 votes
# Jelly, ~~19~~ 18 bytes

```
*g/²_/
4*œc3UṢÇÐḟḣ

```

The program takes a 1-based index **n** and prints the first **n** PPTs **\[c, b, a\]** in lexicographical order.

This is a **O(64n)** solution, so TIO will choke on inputs **4** and higher. I'll work on making it faster.

Try it online!

### Alternate version, O(n3), *probably* valid

To find the **n**th triplet – **\[cn, bn, an\]** – the solution above assumes that **cn ≤ 4n**, which is easy to verify. However, A020882 proves that **cn ~ 2πn**, so there is a **k** such that **cn ≤ kn** for all **n**.

If we can take **k = 7**, the solution below is also valid (and much, much faster).

```
*g/²_/
×7œc3UṢÇÐḟḣ

```

Try it online!

### How it works

```
4*œc3UṢÇÐḟḣ  Main link. Argument: n

4*           Compute 4**n, the n-th power of 4.
  œc3        Take all 3-combinations of the set {1, ..., 4**n}, each sorted in
             ascending order. The triples themselves are sorted lexicographically.
     U       Upend; reverse each triple [a, b, c], yielding [c, b, a].
      Ṣ      Sort the descending triples lexicographically. This ensures that their
             order is independent of n.
       ÇÐḟ   Keep only triples for which the helper link returns a falsy value.
          ḣ  Dyadic head; take the first n triples.

*g/²_/       Helper link. Argument: [c, b, a]

 g/          Reduce [c, b, a] by greatest common divisor, yielding g.
*            Elevate the integers to that power, computing [c**g, b**g, a**g].
   ²         Square, yielding [c**2g, b**2g, a**2g].
    _/       Reduce by subtraction, yielding c**2g - b**2g - a**2g.
             Fermat's Last Theorem assures that this difference will be non-zero
             whenever g > 1, so this yields 0 iff g = 1 and c² = a² = b².

```

# Answer
> 4 votes
## JavaScript (ES7), ~~106~~ ~~105~~ 103 bytes

Outputs the Nth PPT. Results are 1-indexed and ordered by the value of ***b***.

```
n=>(g=(a,b)=>b?g(b,a%b):a,F=a=>(x=a*a+b*b,c=x**.5|0)*c-x*g(a,g(b,c))||--n?F(a-b?a+1:!++b):[a,b,c])(b=1)

```

### Demo

```
let f =

n=>(g=(a,b)=>b?g(b,a%b):a,F=a=>(x=a*a+b*b,c=x**.5|0)*c-x*g(a,g(b,c))||--n?F(a-b?a+1:!++b):[a,b,c])(b=1)

for(n = 1; n <= 20; n++) {
  console.log('#' + n + ' : ' + f(n));
}
```

# Answer
> 4 votes
# MATL, 63 bytes

```
3lvi:"t"[HlHllO;aOlOHl]!@Y*2eh]]!XuGY)&*tt[lO;Oa]*ssD2)ED2Xy*ss

```

Try it online!

A lesson in golfing gone horribly wrong. I'm posting it anyway because I'm wondering if there are ways to golf this better.

I based this on this Wikipedia page in combination with Euclid's formula, to constructively generate all triples rather than trial-and-error approaches.

First, odd coprime pairs are generated as a ternary tree. This is done as a big matrix multiplication, accounting for most of the byte count. Then, Euclid's formula is applied, possibly also in a very byte-wasting manner. If anyone has tips for these two parts, I'd love to hear them.

Note that, to save bytes, this program generates a tree the same depth as the input, rather than `log3(n)`. Also, children are generated for each row rather than only for the last row of the tree, and then filtered again with `Xu`. So much for an efficient constructive approach.

```
3lv % Push root node of ternary tree
i:" % Generate a tree of depth of input (WAY too large, but golfy)
t"  % loop over all nodes (golfier than looping over last tree row)
[HlHllO;aOlOHl]! % Matrix to generate three children of current node
@Y* % Multiply with current node to get children
2e  % Reshape to get node pairs
h]] % Append to tree, exit loops
!Xu % Remove duplicates (more efficient to do it before last ] but golfier this way)
GY) % Select n-th odd coprime pair
&*tt % Multiply with it's own transpose to get [m²,m*n;m*n,n²]
[lO;Oa]*ssD % Sum of matrix multiplication = m²-n² to get a
2)ED % Second element doubled for b=2mn
2Xy*ss % Sum of matrix multiplication with identify matrix to get c=m²+n²

```

# Answer
> 3 votes
## Haskell, 65 bytes

```
([(a,b,c)|c<-[5..],b<-[1..c],gcd c b<2,a<-[1..b],a^2+b^2==c^2]!!)

```

0-based indexing. For a given `c`, `b` runs up to `c` and `a` up to `b`, so `c > b > a` always holds.

Try it online!

# Answer
> 3 votes
# Python, ~~67~~ ~~50~~ ~~48~~ 46 Bytes

Using the formulas found on wikipedia,

`a=m*n, b=(m^2-n^2)/2, c=(m^2+n^2)/2`

where `m>n>0` and `m` and `n` are coprimes and odd. Here is the code

```
lambda n:[3+2*n,~-(3+2*n)**2-1/2,-~(3+2*n)**2/2]

```

-17 bytes thanks to @Martin Ender

Try it Online

Works by always having the value of the `n` variable in the equation being 1, meaning that `m` simply is any other odd value, in this case, `3+2*n` where `n` is the number of the primitive Pythagorean triple. This allows us to assume the value of 1 for all `n` values.

# Answer
> 2 votes
# Husk, 18 bytes

```
↑üOf§=F⌋ȯ¬Ḟ-m□ΠR3N

```

Try it online!

-4 bytes thank to Zgarb, with inspiration from Dennis

Super-slow brute force approach, won't work on TIO for inputs larger than 1. You can try a more manageable version, limited to a,b≤200 here

### Explanation

```
↑üOf§=F⌋ȯ¬Ḟ-m□ΠR3N
              ΠR3N   Get all triples of natural numbers
   f                 Keep only those triples where
      F⌋                their GCD
    §=                  is equal to
        ȯ¬Ḟ-m□          the logical negation of c²-b²-a²
 üO                  Remove duplicates by their sorted version
↑                    Get the first <input> values of this sequence

```

# Answer
> 1 votes
# Mathematica, 89 bytes

using Solve ordered by c

```
SortBy[{a,b,c}/.Solve[a^2+b^2==c^2&&GCD[a,b]==1&&0<a<b<c<9#,{a,b,c},Integers],Last][[#]]&

```

# Mathematica, 124 bytes

```
(s={};Table[If[IntegerQ[c=Sqrt[a^2+b^2]]&&GCD[a,b]==1,AppendTo[s,{a,b,c}]],{a,9#},{b,9#}];SortBy[Union[Sort/@s],Last][[#]])&

```

# Answer
> 1 votes
# R (+ numbers), 88 bytes

```
n=scan();while(all(nrow(T)<n))T=numbers::pythagorean_triples(5,5+(F<-F+1));T[n,3:5]

```

For using a builtin to generate the numbers, it takes actually a surprising amount of bytes to get what we want. The builtin takes two arguments `c1` and `c2`, and returns those triplets that have `c >= c1 & c <= c2`. This makes it slightly annoying to get to the `n`-th triplet. This will just keep increasing `c2` 1 at a time until the output is just enough rows.

# Answer
> 1 votes
# PHP, 273 Bytes

```
function t($n){$x=[];for($c=3;;$c++)for($b=2;$b<$c;$b++)for($a=2;$a<$b;$a++)if(d($a,$b,$c)&&$a**2+$b**2==$c**2){$x[]=[$a,$b,$c];if(--$n==0)return $x;}}function d($a,$b,$c){for($i=2;$i<$a;$i++)if($a%$i==0&&$b%$i==0||$a%$i==0&&$c%$i==0||$b%$i==0&&$c%$i==0)return 0;return 1;}

```
* `t($n)` returns an array of \[a,b,c\] with ordering `a < b < c`
* Returns a zero-based index

Try it online! (code is readable there too)

# Answer
> 1 votes
# Jelly, ~~27~~ 25 bytes

```
⁽0(ḃs
Ɠḃd2Ḥ’×€Ç
3r5DṭÇæ×/

```

This is an implementation of the tree approach from @AndersKaseorg's Haskell answer, with a different branch order. The program uses 0-based indexing and takes input from STDIN.

Try it online!

### Background

As mentioned on the Wikipedia page Tree of primitive Pythagorean triples, every PPT can be obtained by repeatedly left-multiplying the row vector **(3, 4, 5)** by matrices with certain properties.

In each iteration, the previous result can be left-multiplied by either **A**, **B**, or **C**, which can be chosen as follows.

When **A**, **B**, and **C** are fixed, each PPT can be obtained in a unique fashion.

### How it works

```
3r5DṭÇæ×/  Main link. No arguments.

3          Set the argument and the return value to 3.
 r5        Create a range from 3 to 5, i.e., [3, 4, 5].
   D       Decimal; convert each integer to base 10, yielding [[3], [4], [5]].
     Ç     Call the second helper link with argument 3.
    ṭ      Tack; append [[3], [4], [5]] to the result.
      æ×/  Reduce by matrix multiplication.

```

```
Ɠḃd2Ḥ’×€Ç  Second helper link. Argument: 3

Ɠ          Read and evaluate one line of input, yielding an integer n.
 ḃ         Convert n to bijective base 3.
  d2       Divmod 2; map each digit d to [d/2, d%2].
    Ḥ      Unhalve; multiply the results by 2.
     ’     Decrement the doubled results.
           The previous four atoms apply the following mapping to the digits.
               1 -> [0, 1] -> [0, 2] -> [-1,  1]
               2 -> [1, 0] -> [2, 0] -> [ 1, -1]
               3 -> [1, 1] -> [2, 2] -> [ 1,  1]
        Ç  Call the helper link with argument 3, yielding the following 2D array.
               [[ 1,  2,  2],
                [ 2,  1,  2],
                [ 2,  2,  3]]
      ×€   Multiply each [-1,  1], [ 1, -1], and [ 1,  1] by that matrix, using
           vectorizing multiplication (not matrix multiplication), yielding one
           of the following three 2D arrays.

               [[-1,  2,  2],    [[ 1, -2,  2],    [[ 1,  2,  2],
                [-2,  1,  2],     [ 2, -1,  2],     [ 2,  1,  2],
                [-2,  2,  3]]     [ 2, -2,  3]]     [ 2,  2,  3]]

```

```
⁽0(ḃs      First helper link. Argument: 3

⁽0(        Numeric literal; yield 13041.
   ḃ       Convert 13041 to bijective base 3, yielding [1, 2, 2, 2, 1, 2, 2, 2, 3].
    s      Split the result into chunks of length 3, yielding the aforementioned
           2D array.

```

# Answer
> 1 votes
# C, 158 bytes

I believe this is my first submission here, so you can most probably do better.

```
#include<stdio.h>
void f(n){int i=0,j=3,k,l;while(1){for(k=1;k<j;k++){for(l=k;l<j;l++){if(j*j==k*k+l*l)i++;if(i==n){printf("%d %d %d",j,k,l);return;}}}j++;};}

```

And ungolfed version:

```
#include <stdio.h>

void f(n)
{
  int i=0, j=3, k, l;
  while (1) {
    for (k=1; k<j; k++) {
      for (l=k; l<j; l++) {
        if (j*j==k*k+l*l)
          i++;
        if (i==n) {
          printf("%d %d %d\n", j, k, l);
          return;
        }
      }
    }
    j++;
  };
}

void main()
{
  int i;

  scanf("%d", &i);

  f(i);
  printf("\n");
}

```

For *a2 \+ b2 = c2*, the ordering is increasing *c* then increasing *a*.

There can no be twice the same PPT as *b* is at leas *a* in this algorithm.

# Answer
> 1 votes
# APL(NARS), 90 chars, 180 bytes

```
{a⊃⍨⍵⊃⍋↑¨a←{⍵[⍋⍵]}¨a/⍨{1=∨/⍵}¨a←{(-/k),(×/2,⍵),+/k←⍵*2}¨a/⍨{>/⍵}¨a←,a∘.,a←⍳(⌊2⍟2+⍵)×9+⌊√⍵}

```

if the argument of the function above is ⍵, the above function would return the element of the index ⍵ (1 based) of the array has elements Pythagorean triples (a,b,c) where a\<=b\<=c and that array is order first for a, (the side more short), then for b (the other side not hypotenuse). There would be something wrong because there is not seen where I order for b too... test:

```
  f←{a⊃⍨⍵⊃⍋↑¨a←{⍵[⍋⍵]}¨a/⍨{1=∨/⍵}¨a←{(-/k),(×/2,⍵),+/k←⍵*2}¨a/⍨{>/⍵}¨a←,a∘.,a←⍳(⌊2⍟2+⍵)×9+⌊√⍵}
  f¨1..10
3 4 5  5 12 13  7 24 25  8 15 17  9 40 41  11 60 61  12 35 37  13 84 85  15 112 113  16 63 65

```

it is related with http://oeis.org/A020884 and http://oeis.org/A020884/b020884.txt

A020884: Ordered short legs of primitive Pythagorean triangles.

```
  ↑¨f¨1..23
3 5 7 8 9 11 12 13 15 16 17 19 20 20 21 23 24 25 27 28 28 29 31
  f 999
716 128163 128165
  f 1000
717 28556 28565

```

I don't know if it is right, it seems function give correct result of first side of triangle until 1000 but I don't know for the remain, and possible could be some triple not right too even \<1000.

# Answer
> 0 votes
# JavaScript, 101 bytes

By Euclid's formula all primitive Pythagorean triples can be generated from integers `m` and `n` with `m>n>0`, `m+n` odd `gcd(m,n)==1` (Wikipedia)

This function enumerates all `m,n` pair incrementing m starting from `m=2` and decrementing `n` by 2 starting from `m-1` (so that `m+n` is odd)

```
c=>eval("g=(a,b)=>b?g(b,a%b):a;for(m=2,n=1;c-=g(m,n)<2;(n-=2)>0||(n=m++));[m*m-n*n,2*m*n,m*m+n*n]")

```

*Less golfed*

```
c => {
  g = (a,b) => b ? g(b,a%b) : a;
  for( m = 2, n = 1;
       g(m,n) < 2 ? --c : c;
       (n -= 2) > 0 || (n = m++))
    /* empty for body */;
  return [m*m - n*n, 2*m*n, m*m + n*n]
}

```

**Test**

```
F=
c=>eval("g=(a,b)=>b?g(b,a%b):a;for(m=2,n=1;c-=g(m,n)<2;(n-=2)>0||(n=m++));[m*m-n*n,2*m*n,m*m+n*n]")

for(i=1;i<=50;i++) console.log(i+' '+F(i))
```

---
Tags: code-golf, arithmetic, number-theory
---


title: A program that deletes itself

text:
# Question
Title: A program that deletes itself
If a compiled language is used, the program must delete the compiled executable (but need not delete the source file). If an interpreted language is used, the program must delete the source file.

My opening bid:

## Python (29 characters)

```
import os;os.remove(__file__)

```

Edit: to prevent solutions like rm -rf /, the program must not delete anything except the executable or source file.

```
html,body{margin:0;padding:0;height:100%;overflow:hidden}
```

```
 <iframe src="https://xmikee1.github.io/ppcg-leaderboard/?id=19355" width="100%" height="100%" style="border:none;">Oops, your browser is too old to view this content! Please upgrade to a newer version of your browser that supports HTML5.</iframe>
```

# Answer
> 23 votes
## Bash script (7 characters, 7 bytes)

```
rm "$0"

```

# Answer
> 18 votes
# Unix? (9):

```
#!/bin/rm

```

A classic. Uses `rm` as interpreter, for instant self-deletion. Not the very shortest though.

# Answer
> 10 votes
## Batch - 6 bytes

```
Del %0

```

Pretty simple. Note: Works even if the name contains spaces.

# Answer
> 9 votes
# Ruby, 14 characters

```
File.delete $0

```

`$0` is a special global variable that contains the name of the currently running script.

# Answer
> 7 votes
# BASIC-80 / BASICA / GW-BASIC / IBM BASIC / Commodore 64 BASIC / Vintage BASIC / Commodore LCD BASIC / Atari BASIC *

# 5 bytes

```
1 NEW

```

Well, that's about as simple as it gets. `NEW` creates a new program, so putting this anywhere in your program will delete it.

Proof of concept on IBM BASIC (putting `NEW` on line 40 for clarity):

<sup>* Yeah, I listed every old BASIC version I've tested this in (or pretty much ever used)</sup>

# Answer
> 6 votes
# PHP, 17 characters

```
unlink(__FILE__);

```

# Answer
> 3 votes
**PowerShell (32)**

```
del $MyInvocation.MyCommand.Name

```

# Answer
> 3 votes
**Perl 5 (8 characters)**

```
unlink$0

```

`$0` is the script name, and `unlink` removes it. Normally, you'd at least add a space in between for readability.

# Answer
> 3 votes
**C# (112)**

```
Process.Start("cmd.exe","/C choice /C Y /N /D Y /T 3 & Del " + Application.ExecutablePath);
Application.Exit();

```

Shamelessly stolen from http://www.codeproject.com/Articles/31454/How-To-Make-Your-Application-Delete-Itself-Immedia

# Answer
> 3 votes
### R, 26 characters

```
unlink(sys.frame(1)$ofile)

```

# Answer
> 3 votes
# k (8)

```
~-1!.z.f

```

Or the q equivalent for 14:

```
hdel hsym .z.f

```

# Answer
> 3 votes
# Python, 18

```
open(__file__,'w')

```

Opens itsself in write-only mode, erasing itself.

# Answer
> 1 votes
# Node.js - 22 chars

```
fs.unlink(__filename);

```

# Answer
> 1 votes
# Julia, 13 bytes

```
rm(@__FILE__)

```

Simple. But longer. :P

# Answer
> 1 votes
# Vitsy + bash, 8 bytes

```
iG' mr',

iG       Get the name of the use declaration at the top item (-1) (returns the current one)
  ' mr'  Concatenate "rm " to the front of it.
       , Execute via shell.
```

# Answer
> 1 votes
# Mathematica, 29 bytes

```
DeleteFile@NotebookFileName[]

```

# Answer
> 1 votes
## C, 32 bytes

```
main(c,v)char**v;{remove(v[0]);}

```

# Answer
> 1 votes
# Lua, 17 bytes

```
os.remove(arg[0])

```

This actually only works if you run the program by typing out the full filepath, i.e.
`lua ~/Scripts/removeself.lua` would work, but `lua removeself.lua` would not, assuming a filename of `removeself.lua` and a current working directory of `~/Scripts`.

As far as I know, there's no way to find the actual filepath of a script, just the arguments passed to it. I do know about `debug.getinfo(1).source`, but in my testing that game exactly the same results as `arg[0]`. If anyone knows of a way to find the filepath, please let me know.

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

```
f=_=>delete f

```

---

## Try It

Logs the source of `f`, calls `f` (which deletes `f`), tries to log `f` again but throws an error because `f` is now undefined.

```
f=_=>delete f
console.log(f)
f()
console.log(f)
```

# Answer
> 1 votes
# JS, 37 bytes

```
document.documentElement.innerHTML=""

```

Does this count? It kills javascript on the page

# Answer
> 1 votes
# tcl, 18

```
file delete $argv0

```

demo**ATTENTION:** It is only a one time demo! Only the first time it will be runnable. Please reserve it to the question's original poster. To try: press the `Execute` button. The green area will not report any error. After that, any subsequent clicks on the `Execute` button will result on a `not found` error!

# Answer
> 1 votes
# VBA, ~~69~~ 62 Bytes

Subroutine that takes no input and deletes itself.

Requires that the code below be the first line in the active code pane, and that VBA has trusted access to the VBE Project model.

```
Sub A:Parent.VBE.CodePanes(1).CodeModule.DeleteLines 1:End Sub

```

-2 bytes for replacing `ActiveCodePane` with with `CodePane(1)`

-5 bytes for replacing `Application` with `Parent`

# Answer
> 1 votes
# shortC, 10 bytes

```
Aremove(*@

```

How it works:

```
A           main function
 remove(    delete file specified in next string
        *@  program name

```

Equivalent C program:

```
int main(int argc, char **argv){remove(*argv);}

```

# Answer
> 1 votes
# 8086/8088 machine code, 1 byte

```
aa    stosb

```

Assumptions:

* The registers CS, IP, ES, DI, and AL are all initially 0.
* This code is placed at address 0.

The `stosb` instruction stores the byte in the AL register at the memory location pointed to by ES and DI, then increments or decrements DI. In this case, it stores the byte 0 at the memory address 0, which happens to be where the instruction itself is.

Granted, this program doesn't delete a file or anything. But if you manage to get your hands on an 8086 processor, poke this program into memory, and run it, it will in fact overwrite itself.

# Answer
> 0 votes
## PowerShell v3 - 17

```
ri $PSCommandPath

```

# Answer
> 0 votes
# Julia - 25 bytes

Write this into a file, and then include the file with `include("<filename here>")` and run `f()`:

```
f()=rm(functionloc(f)[1])

```

This is, obviously, a function - I'm not sure how one would go about detecting the file name of a file being run directly (as an include statement without a function definition in it).

# Answer
> 0 votes
## C++, 137 bytes.

Works most of the time on windows

```
#include <stdlib.h>
#include <string>
int main(int, char*v[]){char c[99];sprintf(c,"start cmd /C del \"%s\"/Q", *v);return system(c);}

```

## C, 90 bytes

```
void main(int n,char**v){char c[99];sprintf(c,"start cmd /C del \"%s\"/Q", *v);system(c);}

```

# Answer
> 0 votes
## MATLAB, 36 bytes

```
delete([mfilename('fullpath'),'.m'])

```

Save the above code as an m-file following Matlab's filename guidelines.

# Answer
> 0 votes
# Nodejs, 32 bytes

```
require("fs").unlink(__filename)

```

# Answer
> 0 votes
# T-SQL, 28 bytes

```
CREATE PROC d AS DROP PROC d

```

It just drops/removes the procedure and the code when executing itself. Usage:

```
EXECUTE d

```

---
Tags: code-golf, file-system
---


title: List of Python versions

text:
# Question
Title: List of Python versions
Python is the fastest-growing major programming language today. It is the most wanted language for the third year in a row, meaning that developers who do not yet use it say they want to learn it.\[1\]

The reason for Python's popularity is its many versions.\[citation needed\] There are in fact 116 versions of Python, including two development versions.

Your task is to output/print a list of all the Python versions, in whatever order you like, and on whatever format you like. You may not use any built-in functions that have this information stored.

You are free to choose the output format, but each version must be identified on the standard way: `1.1`, `2.3.0`, `2.7.10` and so on.

The complete list2 of Python versions, comma-separated is shown below:

```
1.1, 1.2, 1.3, 1.4, 1.5, 1.5.1, 1.5.2, 1.6, 2.0, 2.0.1, 2.1, 2.1.1, 2.1.2, 2.1.3, 2.2, 2.2.1, 2.2.2, 2.2.3, 2.3, 2.3.1, 2.3.2, 2.3.3, 2.3.4, 2.3.5, 2.4, 2.4.1, 2.4.2, 2.4.3, 2.4.4, 2.5, 2.5.1, 2.5.2, 2.5.3, 2.5.4, 2.6, 2.6.1, 2.6.2, 2.6.3, 2.6.4, 2.6.5, 2.6.6, 2.6.7, 2.6.8, 2.6.9, 2.7, 2.7.1, 2.7.2, 2.7.3, 2.7.4, 2.7.5, 2.7.6, 2.7.7, 2.7.8, 2.7.9, 2.7.10, 2.7.11, 2.7.12, 2.7.13, 2.7.14, 2.7.15, 2.7.16, 3.0, 3.0.1, 3.1, 3.1.1, 3.1.2, 3.1.3, 3.1.4, 3.1.5, 3.2 , 3.2.1, 3.2.2, 3.2.3, 3.2.4, 3.2.5, 3.2.6, 3.3.0, 3.3.1, 3.3.2, 3.3.3, 3.3.4, 3.3.5, 3.3.6, 3.3.7, 3.4.0, 3.4.1, 3.4.2, 3.4.3, 3.4.4, 3.4.5, 3.4.6, 3.4.7, 3.4.8, 3.4.9, 3.4.10, 3.5.0, 3.5.1, 3.5.2, 3.5.3, 3.5.4, 3.5.5, 3.5.6, 3.5.7, 3.6.0, 3.6.1, 3.6.2, 3.6.3, 3.6.4, 3.6.5, 3.6.6, 3.6.7, 3.6.8, 3.7.0, 3.7.1, 3.7.2, 3.7.3

```

or by major versions:

```
1.1
1.2
1.3
1.4
1.5, 1.5.1, 1.5.2
1.6
2.0, 2.0.1
2.1, 2.1.1, 2.1.2, 2.1.3
2.2, 2.2.1, 2.2.2, 2.2.3
2.3, 2.3.1, 2.3.2, 2.3.3, 2.3.4, 2.3.5
2.4, 2.4.1, 2.4.2, 2.4.3, 2.4.4
2.5, 2.5.1, 2.5.2, 2.5.3, 2.5.4
2.6, 2.6.1, 2.6.2, 2.6.3, 2.6.4, 2.6.5, 2.6.6, 2.6.7, 2.6.8, 2.6.9
2.7, 2.7.1, 2.7.2, 2.7.3, 2.7.4, 2.7.5, 2.7.6, 2.7.7, 2.7.8, 2.7.9, 2.7.10, 2.7.11, 2.7.12, 2.7.13, 2.7.14, 2.7.15, 2.7.16
3.0, 3.0.1
3.1, 3.1.1, 3.1.2, 3.1.3, 3.1.4, 3.1.5
3.2, 3.2.1, 3.2.2, 3.2.3, 3.2.4, 3.2.5, 3.2.6
3.3.0, 3.3.1, 3.3.2, 3.3.3, 3.3.4, 3.3.5, 3.3.6, 3.3.7
3.4.0, 3.4.1, 3.4.2, 3.4.3, 3.4.4, 3.4.5, 3.4.6, 3.4.7, 3.4.8, 3.4.9, 3.4.10
3.5.0, 3.5.1, 3.5.2, 3.5.3, 3.5.4, 3.5.5, 3.5.6, 3.5.7
3.6.0, 3.6.1, 3.6.2, 3.6.3, 3.6.4, 3.6.5, 3.6.6, 3.6.7, 3.6.8
3.7.0, 3.7.1, 3.7.2, 3.7.3

```

The challenge is a fixed output challenge, and very close to a , except that the output format is optional.

2The list is taken from the official Python website, here and here. There are some versions that aren't included, such as `0.9.0` .. `0.9.9` and `1.5.1p1`. You must use the list above, even if you find versions that aren't included. I've decided to stick with the official lists, since otherwise someone would probably find a `2.1.0.1.2` version or something like that.

# Answer
> 17 votes
# JavaScript (ES6),  ~~128 125~~  124 bytes

*Saved 1 bytes thanks to @OlivierGrégoire*

Outputs each version on a separate line. Ordered from highest to lowest major version, and from lowest to highest revision.

```
f=(r=v=28)=>v?r<parseInt('0111131000244655ah002678b8940'[v],36)?(1+v/10).toFixed(1)+(r|v>22?'.'+r:'')+`
`+f(r+1):f(+!v--):''

```

Try it online!

### How?

The major and minor versions are held in the variable \\$v \in \[0..27\]\\$:

* major = \\$\lfloor v/10+1\rfloor\\$
* minor = \\$v \bmod 10\\$

The revision is held in the variable \\$r\ge0\\$. The maximum value of \\$r\\$ depends on \\$v\\$ and is stored in a lookup table encoded in Base-36. Any \\$0\\$ in this table means that this version was not released at all.

Besides, we use the test \\$v\>22\\$ to know whether the revision should be included even when it's \\$0\\$ (starting with Python 3.3.0).

# Answer
> 5 votes
# Pyth, 52 bytes

```
.emj\.+W|d>k18,h/k8%k8dbxLG"abbbbdbaceegffkrcghilije

```

Try it online here.

Output is a nested list, with elements grouped by major and minor version. There is an empty list at the start of the output, and another one after `1.6`. Full output is as follows:

```
[[], ['1.1'], ['1.2'], ['1.3'], ['1.4'], ['1.5', '1.5.1', '1.5.2'], ['1.6'], [], ['2.0', '2.0.1'], ['2.1', '2.1.1', '2.1.2', '2.1.3'], ['2.2', '2.2.1', '2.2.2', '2.2.3'], ['2.3', '2.3.1', '2.3.2', '2.3.3', '2.3.4', '2.3.5'], ['2.4', '2.4.1', '2.4.2', '2.4.3', '2.4.4'], ['2.5', '2.5.1', '2.5.2', '2.5.3', '2.5.4'], ['2.6', '2.6.1', '2.6.2', '2.6.3', '2.6.4', '2.6.5', '2.6.6', '2.6.7', '2.6.8', '2.6.9'], ['2.7', '2.7.1', '2.7.2', '2.7.3', '2.7.4', '2.7.5', '2.7.6', '2.7.7', '2.7.8', '2.7.9', '2.7.10', '2.7.11', '2.7.12', '2.7.13', '2.7.14', '2.7.15', '2.7.16'], ['3.0', '3.0.1'], ['3.1', '3.1.1', '3.1.2', '3.1.3', '3.1.4', '3.1.5'], ['3.2', '3.2.1', '3.2.2', '3.2.3', '3.2.4', '3.2.5', '3.2.6'], ['3.3.0', '3.3.1', '3.3.2', '3.3.3', '3.3.4', '3.3.5', '3.3.6', '3.3.7'], ['3.4.0', '3.4.1', '3.4.2', '3.4.3', '3.4.4', '3.4.5', '3.4.6', '3.4.7', '3.4.8', '3.4.9', '3.4.10'], ['3.5.0', '3.5.1', '3.5.2', '3.5.3', '3.5.4', '3.5.5', '3.5.6', '3.5.7'], ['3.6.0', '3.6.1', '3.6.2', '3.6.3', '3.6.4', '3.6.5', '3.6.6', '3.6.7', '3.6.8'], ['3.7.0', '3.7.1', '3.7.2', '3.7.3']]

```

If this isn't acceptable, prepend `.n` to the code to have output as a flattened list, at a cost of 2 bytes.

# Answer
> 5 votes
# C# (Visual C# Interactive Compiler), 109 bytes

```
for(int j,k=1;;k++)for(j=@" [SOH][SOH][SOH][SOH][ETX][SOH][NUL][NUL][NUL][STX][EOT][EOT][ACK][ENQ][ENQ]
[DC1][NUL][NUL][STX][ACK][BEL][BS][VT][BS][TAB][EOT]"[k];j-->0;)Print($"{k*.1+1:N1}"+(j<1&k<17?"":"."+j));

```

Contains many unprintables, whose codes are shown in the brackets. This is a full program. The null bytes are replaced by `\0`s in the TIO link, since my device can't copy and paste them.

Saved one byte thanks to @OlivierGregoire.

Try it online! (Thanks to @OlivierGregoire for implanting the null bytes)

# Explanation

Each character in the string represents how many minor versions in the major position. For example, the character at index 5(`ETX`) has an ASCII value of three, and corresponds to the major version `1.5.x` which has three minor versions. The program takes the ascii value of the current character and loops that many times, printing the minor versions before moving on to the next major version.

For some versions, there are gaps to the next versions. To fix that, the string contains null bytes, so that the program loops zero times when it encounters those.

The unprintable string contains these character values:

```
1,1,1,1,3,1,0,0,0,2,4,4,6,5,5,10,17,0,0,2,6,7,8,11,8,9,4

```

# Answer
> 4 votes
# Java (JDK), 134 bytes

```
v->{for(int a=0,b;;)for(b="0111131000244655:A002678;894".charAt(++a)-48;b-->0;)System.out.printf("%.1f%s ",a*.1+1,b<1&a<23?"":"."+b);}

```

Try it online!

The versions are printed from the highest to the lowest.

## Credits

# Answer
> 3 votes
# Retina, 105 bytes

```

11* 111131   244655TS  2678E894
L$`.
$&_$.`
T
10
E
11
S
17
.+_
*
Lv$`_+(.)(.)
$1.$2.$.%`
,16`(...)\.0
$1

```

Try it online! Loosely based on @Arnauld's solution. Explanation:

```

11* 111131   244655TS  2678E894

```

Insert the string consisting of 11 spaces followed by the given characters.

```
L$`.
$&_$.`

```

For each character, list it suffixed with a `_` and its column number.

```
T
10
E
11
S
17

```

Convert the three letters to numeric values.

```
.+_
*

```

Convert the numeric values to unary.

```
Lv$`_+(.)(.)
$1.$2.$.%`

```

For each value up to the given value, use that as the suffix for the version number, extracting the major and minor from the column number.

```
,16`(...)\.0
$1

```

Delete the zero suffix for the first 16 versions that have one.

# Answer
> 2 votes
# Jelly, 51 bytes

```
+⁵D;ⱮḶ}j€”.
“øṄƇịɱ⁽Ɱj>⁶7,Ẉ¢’b18Ė0ị$Ƈç/€ḣ3$€1¦€17R¤¦

```

Try it online!

A niladic link that outputs a list of lists of `.`-separated integers, grouped by major version. On TIO, there’s some footer code to print these prettily.

# Answer
> 0 votes
# 33, 484 bytes

```
"1."es[lz1azpois4m]"1.5"pi"1.5."z1apoiapoi"1.6"pi"2.0"pip".1"pizcz"2.1"''pie"."e''es[lz1azpois3m]"2.2"''pie"."et''es[lz1azpois3m]"2.3"''pie"."et''es[lz1azpois5m]"2.4"''pie"."et''es[lz1azpois4m]"2.5"''pie"."et''es[lz1azpois4m]"2.6"''pie"."et''es[lz1azpois9m]"2.7"''pie"."et''es[lz1azpois16m]"3.0"pip".1"pi"3.1"''pie"."et''es[lz1azpois5m]"3.2"''pie"."et''es[lz1azpois6m]"3.3."''es[lzpoi1azs8m]"3.4."''es[lzpoi1azs11m]"3.5."''es[lzpoi1azs8m]"3.6."''es[lzpoi1azs9m]"3.7."''es[lzpoi1azs4m]

```

I wanted to give this a go in my brainf\*ck-style language.

It prints each python version required for the challenge, delimited by newlines.

Here's a small explanation.

```
[lz1azpois4m] | Imitates a for loop starting at 1
[  1az    4m] | For i in range 1 through 4
      p       | - Print the string declared previously (1.5., 3.4., etc.)
       o      | - Print the current value of i
        i     | - Print a newline

[lzpoi1azs8m] | Imitates a for loop starting at 0
[     1az 8m] | For i in range 0 through 7
   poi        | Print the version

```

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


title: How many times should I press this?

text:
# Question
Title: How many times should I press this?
We are all used to the old-school telephone keypad, right? For reference, here is what it looks like:

---

Given a String consisting only of **lowercase ASCII letters and single spaces**, your task is to return the number of taps one should make in order to type down the full String with a telephone keypad as the one above.

For those who are unfamiliar with this, here's how it works:

* The key with the digit `2`, for example, also has the string `abc` written down on it. In order to type `a`, you must press this key once, for `b` you must press twice and for `c` you must press thrice.
* For consecutive letters that are on the same key, you must wait 1 second before pressing again. So, if you want to type `cb`, you must press 3 times for `c`, wait a second and then press twice for `b`, so still 5 taps.
* The same applies for all other keys, except for a *single* space, which only requires 1 press. Also note that the keys `7` and `9` have four letters on them. The same algorithm is applied, the only difference being the number of letters. The strings corresponding to each key can be found in the image above (but lowercase), or in the following list, that contains all the characters you might receive:

```
"abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz", " "

```

# Test Cases

```
Input  ->  Output  (Explanation)

"" -> 0                   (nothing should be tapped)
"water" -> 8              ("w,a,t" each require 1 tap (on keys 9, 2 and 8), "e" requires 2 taps (on key 3), "r" requires 3 taps (on key 7), 1+1+1+2+3 = 8)
"soap"  -> 9              (4+3+1+1)
"candela" -> 13           (3+1+2+1+2+3+1)
"code golf" -> 20         (3+3+1+2+1(for the space)+1+3+3+3)
"king of the hill" -> 33  (2+3+2+1+1+3+3+1+1+2+2+1+2+3+3+3)

```

# Specs

* Standard I/O rules and Default Loopholes apply.
* You may only take input in your language's native String type. Output can either be an integer or a string representation of that integer.
* This is , the shortest answer *in every language* wins.

# Answer
# JavaScript (ES6) ~~77~~ ~~66~~ ~~64~~ 60 bytes

(Saved some bytes thanks to @Johan Karlsson and @Arnauld).

```
s=>[...s].map(l=>s=~~s+2+'behknquxcfilorvysz'.search(l)/8)|s

```

```
f=

s=>[...s].map(l=>s=~~s+2+'behknquxcfilorvysz'.search(l)/8)|s

console.log(f(''));                 //0
console.log(f('water'));            //8
console.log(f('soap'));             //9
console.log(f('candela'));          //13
console.log(f('code golf'));        //20
console.log(f('king of the hill')); //33
```
> 11 votes

# Answer
# 05AB1E, ~~29~~ ~~26~~ 25 bytes

```
ð¢svA•22ā₂•S£ð«øðδKy.åƶOO

```

Try it online!

**Explanation**

```
ð¢                         # count spaces in input
  sv                       # for each char y in input
    A                      # push the lowercase alphabet
     •22ā₂•S               # push the base-10 digit list [3,3,3,3,3,4,3,4]
            £              # split the alphabet into pieces of these sizes
             ð«            # append a space to each
               ø           # transpose
                ðδK        # deep remove spaces
                   y.å     # check y for membership of each
                      ƶ    # lift each by their index in the list
                       O   # sum the list
                        O  # sum the stack

```
> 7 votes

# Answer
# Python 2, 56 bytes

Uses the same algorithm as @RickHitchcock's Javascript solution

```
lambda x:sum('behknquxcfilorvysz'.find(c)/8+2for c in x)

```

Try it online!
> 7 votes

# Answer
# Dyalog APL, 37 bytes

```
+/⌈9÷⍨'adgjmptw behknqux~cfilorvy~'⍳⍞

```

Try it online!

**How?**

Get the ndex of every char of the input in the string `'adgjmptw behknqux~cfilorvy~'` (`s` and `z` will default to 28), divide by 9, round up and sum.
> 5 votes

# Answer
# Python 3, ~~69~~ ~~67~~ ~~65~~ 64 bytes

1 byte thanks to Mr. Xcoder.

1 byte thanks to Felipe Nardi Batista.

```
lambda x:sum((ord(i)+~(i>"s"))%3+3*(i in"sz")+(i>" ")for i in x)

```

Try it online!
> 5 votes

# Answer
## JavaScript (ES6), 71 bytes

```
f=
s=>[...s].map(c=>t+=((c=parseInt(0+c,36))>23?c+3:c&&~-c%3)%7%4+1,t=0)|t
```

```
<input oninput=o.textContent=f(this.value)><pre id=o>
```

Look no letter tables! I didn't quite understand @LeakyNun's formula so I came up with my own.
> 4 votes

# Answer
# C, ~~211~~ 196 bytes

First submission here...looks quite lengthy and I see that this is not an efficient approach, but at least it works :)

```
f(char*n){char*k=" abcdefghijklmnopqrstuvwxyz";int t[]={0,3,3,3,3,3,4,3,4};int l=0,s,j,i;while(*n){i=0;while(k[i]){if(k[i]==*n){s=0;for(j=0;s<i-t[j];s+=t[j++]);*n++;l+=(!i?1:i-s);}i++;}}return l;}

```

Ungolfed version:

```
int f(char *n){
  char *k=" abcdefghijklmnopqrstuvwxyz";
  int t[]={0,3,3,3,3,3,4,3,4};
  int l=0,s,j,i;
  while(*n){                          // loop through input characters
    i=0;
    while(k[i]){
      if(k[i]==*n){                   // find matching char in k
        s=0;
        for(j=0;s<i-t[j];s+=t[j++]);  // sum up the "key sizes" up to the key found
        *n++;
        l+=(!i?1:i-s);                // key presses are i-s except for space (1)
      }
      i++;
    }
  }
  return l;
}

```
> 4 votes

# Answer
# Haskell - ~~74~~ ~~71~~ 62 bytes

*Edit: removed 3 bytes by using a list comprehension instead of filter*

*Edit: Save 9 bytes thanks to Siracusa, Laikoni and Zgarb!*

```
f=sum.(>>= \x->1:[1|y<-"bcceffhiikllnooqrrsssuvvxyyzzz",y==x])

```

## Usage

```
λ> f "candela"
13
λ>

```

Try it online!
> 4 votes

# Answer
# Jelly, 25 bytes

```
Øaḟ⁾sz©;⁶s3Z®ṭċ@€€⁸×"J$ẎS

```

Try it online!
> 3 votes

# Answer
## Clojure, ~~82~~ 76 bytes

```
#(apply +(for[c %](+(count(filter #{c}"bcceffhiikllnooqrrsssuvvxyyzzz"))1)))

```

Oh it is simpler to just `filter` and `count` than use `frequencies`. Original:

```
#(apply +(count %)(for[c %](get(frequencies"bcceffhiikllnooqrrsssuvvxyyzzz")c 0)))

```

The string encodes how many times more than just once you need to press the key for a given character :)
> 3 votes

# Answer
# Python 3, 91 bytes

```
lambda x:sum(j.find(i)+1for j in' !abc!def!ghi!jkl!mno!pqrs!tuv!wxyz'.split('!')for i in x)

```

Try it online!
> 2 votes

# Answer
## Retina, ~~46~~ 36 bytes

*Thanks to CalculatorFeline for saving 6 bytes.*

```
s|z
,c
[cfilorvy]
,b
[behknqux]
,,
.

```

Try it online!
> 2 votes

# Answer
## Java, ~~95~~ 73 bytes

```
a->a.chars().map(b->1+(b<64?0:b+(Math.abs(b-115)<4?4:5))%(3+b/112)).sum()

```

Thanks to Kevin Cruijssen for making the function a lambda expression (where `a` is of type `String`). 95 bytes became 73 bytes!

A lambda expression sums up the press count of each character using `map()`. `map()` converts each character (ASCII in lower case range is 97-122) in the stream to the appropriate value (looks like simple saw wave, but taking into account both 4 cycles is annoying) using this math: `1+(b<64?0:b+(Math.abs(b-115)<4?4:5))%(3+b/112)`. Here's a desmos graph of that model.
> 2 votes

# Answer
# Python 3, 60 bytes

Probably sub-optimal, as this is my first golf ever in Python.

```
lambda x:sum((ord(i)-8)%3.15//1+3*(i>'y')+(i>' ')for i in x)

```

Try it online!
> 2 votes

# Answer
# Pip, ~~100~~ 90 bytes

```
a:qb:["abc""def""ghi""jkl""mno""pqrs""tuv""wxyz"s]Fc,#a{Fd,#b{e:((bd)@?(ac))e<4?i+:e+1x}}i

```

Check each character of the input for a match in each element of b. The index of that match plus 1 gets added to the total.

Try it online!
> 2 votes

# Answer
# Mathematica, 83 bytes

```
c=Characters;Tr[Tr@Mod[c@"bc1def1ghi1jkl1mno1pqrstuv1wxyz "~Position~#,4]+1&/@c@#]&

```
> 1 votes

# Answer
# QBIC, 94 bytes

```
[_l;||_SA,a,1|p=p-(instr(@sz`,B)>0)-(instr(@cfilorvy`+C,B)>0)-(instr(@behknqux`+C+D,B)>0)+1}?p

```

## Explanation

```
[    |      FOR a = 1 TO
 _l |         the length of
   ;            the input string (A$)
_SA,a,1|    Take the a'th char of A$ and assign it to B$
p=p         p is our tap-counter, and in each iteration it gets increased by the code below
            which consist of this pattern:
                instr(@xyz`,B)>0    where
                - instr tests if arg 2 is in arg 1 (it either returns 0 or X where X is the index of a2 in a1)
                - @...` defines the letters we want to test as arg1
                - B is the current letter to count the taps for
            Each of these blocks adds 1 tap to the counter, and each block has the letters of its level
            (4-taps, 3-taps or 2-taps) and the level 'above' it.
    -(instr(@sz`,B)>0)              <-- letters that require 4 taps
    -(instr(@cfilorvy`+C,B)>0)      <-- 3 or 4 taps
    -(instr(@behknqux`+C+D,B)>0)    <-- 2, 3,or 4 taps
    +1                              <-- and always a 1-tap
}           NEXT
?p          PRINT the number of taps

```
> 1 votes

# Answer
# Bash, ~~69~~  68 bytes

```
bc<<<`fold -1|tr "\n "adgjmptwbehknquxcfilorvysz +[1*9][2*8][3*8]44`

```

Try it online!

Folds one char per line, transliterates each newline with `+`, each space with `1` and each letter with the corresponding number of pushes. bc does the sum.
> 1 votes

# Answer
## C, 92 88 bytes

```
c,n;f(char*s){n=0;while(c=*s++)n+=(c=='s')+3*(c>'y')+1+(c+1+(c<'s'))%3-(c<33);return n;}

```
> 1 votes

# Answer
# C (gcc), 75 ~~77~~ bytes

```
n,b;f(char*a){for(n=0;b=*a++;)n+=b<'s'?--b%3+(b>31):""[b-'s'];a=n;}

```

The unprintable string `""` is a table of `04 01 02 03 01 02 03 04`.

Try it online!
> 1 votes

# Answer
# APL (Dyalog), 36 bytes

```
{+/(3×⍵∊'sz'),1+3|¯1+⍵⍳⍨819⌶⎕A~'SZ'}

```

Try it online!

Finds the mod-3 indices in the alphabet without *S* and *Z*. Since space, *S*, and *Z* are not found, they "have" index 25 (one more than the max index), which is good for space. Then we just need to add 3 for each *S* or *Z*.

`{` anonymous function where the argument is represented by :

`⎕A~'SZ'` the uppercase **A**lphabet, except for *S* and *Z*

`819⌶` lowercase

`⍵⍳⍨` the **ɩ**ndices of the argument in that

`¯1+` add negative one

`3|` mod-3

`1+` add one (this converts all 0-mods to 3)

`(``),` prepend:

`⍵∊'sz'` Boolean where the argument is either *s* or *z*

multiply by 3

`+/` sum
> 1 votes

---
Tags: code-golf, string, number, keyboard
---


title: Pythagorean Triplets

text:
# Question
Title: Pythagorean Triplets
The **Pythagorean Theorem** states that for a right triangle with sides `a`, `b`, and `c`, a2+b2=c2.

A **Pythagorean triplet** is a set of three numbers, where a2+b2=c2, a To extend this even further, a **primitive Pythagorean triplet** is a Pythagorean triplet where `gcd(a,b,c)=1`.

The goal is to find 100 primitive Pythagorean triplets.

**Input:** No input.

**Output:** 100 primitive Pythagorean triplets, in whatever order and shape, as long as the output contains only those triplets.

Shortest code wins. Good luck!

# Answer
> 9 votes
## Python, 42

```
i=4
while i<203:print 2*i,i*i-1,i*i+1;i+=2

```

# Answer
> 5 votes
# Javascript, 44 characters

**Update:**

```
for(i=s=0;i^400;)s+=[i+=4,r=i*i/4-1,r+2]+' '

```

I should have looked up an algorithm first. Well, can't beat python anyway.

Run in a console to see the result.

**Old, slow, brute-force variant (140 characters)**

```
for(q=a=[];563>++a;)for(b=a;--b;)(k=Math.sqrt(a*a+b*b))==~~k==function c(e,d,f){return f?c(c(f,e),d):d?c(d,e%d):e}(a,b,k)&&q.push([b,a,k]);q

```

# Answer
> 5 votes
## J, 64 60 38 49 characters

```
100$}.~.(/:~*(0<*/*1=+./))"1[4$.$.(=/+/~)2^~i.699

```

Should've realised that such a big gain was probably flawed. Still uses the brute-force method, but done a bit more efficiently.

Explanation:

`x=.2^~i.699` generates a list of ints from 0 to 699 and squares `2^~` them (`~` here reverses the order of the arguments).

`(=+/~)` is a hook that generates an addition table and compares the result to the list. This gives me a three dimensional array with items which are either `1` or `0`. A `1` means that a2+b2=c2.

`$.` converts to a sparse array. For my smaller (9) example I get:

```
   $.(=/+/~)2^~i.9
0 0 0 | 1
1 0 1 | 1
1 1 0 | 1
2 0 2 | 1
2 2 0 | 1
3 0 3 | 1
3 3 0 | 1
4 0 4 | 1
4 4 0 | 1
5 0 5 | 1
5 3 4 | 1
5 4 3 | 1
5 5 0 | 1
6 0 6 | 1
6 6 0 | 1
7 0 7 | 1
7 7 0 | 1
8 0 8 | 1
8 8 0 | 1

```

`4$.` just gives me the left part of this list.

`(/:~*(0<*/*1=+./))"1[` decides which rows meet the criteria. `(verb)"1` tells the verb to act on the individual rows rather than on the list. `[` just separates the `1` and `4`, otherwise J will think that `1 4` is a list of 2 numbers. '1=+./' gets the GCD of the three numbers and checks if it's `1`. `*/` multiplies each triple together (getting `0` if it contains a `0`) and these two are multiplied together. `0<` turns the result into a boolean. `*` multiplies this result by each triple which eliminates all triples which contain a `0` or have a GCD which is not `1`. `/:~` sorts each triple.

`~.` selects the unique items from the list.

`}.` removes the first item (0 0 0) from the list.

`100$` takes the first 100 items from the list.

The above is my answer to this question, but as a matter of interest I implemented grc's method, (27 characters):

```
2(*,.<:@^~,.>:@^~)2*2+i.100

```

# Answer
> 2 votes
### Scala 180:

```
def g(a:Int,b:Int):Int=if(a==b)a else
if(a>b)g(a-b,b)else
g(b,a)
for(c<-(5 to 629);
a<-(1 to c-2);
b<-(a to c-1);
if((a*a+b*b==c*c)&&g(c,g(a,b))==1)&&a<400)println(a+"  "+b+" "+c)

```

Ungolfed:

```
def gcd (a: Int, b: Int) : Int = if (a == b)
  a else
    if (a > b) gcd (a-b, b) else
      gcd (b, a)

def gcd (a: Int, b: Int, c:Int): Int = gcd (c, gcd (a, b))

def pythagorean (a: Int, b: Int, c: Int) = (a * a + b * b == c * c)

for (c <- (5 to 629);
  a <- (1 to c-2);
  b <- (a to c-1);
  if (pythagorean (a, b, c) && gcd (a, b, c) == 1)) yield {
    println (a + "² + "  + b + "² = " + c + "² => " + (a*a) + " + " + (b*b) + " = " + (c*c))
    c*c
  }

```

# Answer
> 2 votes
## APL (31)

```
↑{(2×⍵),(A-1),1+A←⍵×⍵}¨2+2×⍳100

```

It uses basically the same approach as the Python program.

# Answer
> 2 votes
# MATLAB 29

```
i=2:2:200;[2*i;i.*i-1;i.*i+1]

```

# Answer
> 2 votes
**Mathematica 33**

```
{2#,#^2-1,#^2+1}&/@Range[4,203,2]

```

# Answer
> 1 votes
# APL(NARS), 26 chars, 52 bytes

```
{k(4×⍵),2+k←¯1+×⍨2×⍵}¨⍳100

```

test:

```
  a←{k(4×⍵),2+k←¯1+×⍨2×⍵}¨⍳100
  ≢a
100
  +/{(x y z)←⍵⋄(z*2)=(y*2)+x*2}¨a
100
  +/{∨/⍵}¨a
100
  10↑a
3 4 5  15 8 17  35 12 37  63 16 65  99 20 101  143 24 145  195 28 197  255 32 257  323 36 325  399 40 401

```

# Answer
> 0 votes
## R, 49 characters

translated from the Python solution:

```
i=4;while(i<203){print(c(2*i,i*i-1,i*i+1));i=i+2}

```

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


title: Count the squares

text:
# Question
Title: Count the squares
# Challenge

Origami (folding paper) is a creative form of art. As far as I know, master of Origami prefers square paper. Let's start from beginning - convert a rectangular paper to a square one.

So the paper is divided into squares. We remove the biggest square which shares one shorter edge with the current shape, step by step (see the picture below). And if the remaining part after one step is less or equal than `0.001 * (area of the original paper)`, the paper cannot be divided any further. It is possible that nothing remains at last.

Your task is to calculate how many squares are made during the process. The square in the last step that makes the paper unable to be divided is counted into the output.

Example (a paper of `1.350` width/height), output is 10:

# Input and Output

Input: width / height ratio for the rectangular paper, one decimal (or an integer without the dot) from `1.002` to `1.999` with a minimal step of `0.001`. You may also use any other reasonable format describing the ratio. Just mention it in your answer.

Output: square count, one integer.

# Example I/O

A mapping format is used to keep the page tidy, while your code doesn't need to support a list input nor to be a mapping function.

```
1.002 => 251
1.003 => 223
1.004 => 189
1.005 => 161
1.006 => 140
1.007 => 124
1.008 => 111
1.009 => 100

```

List of all answers

Thanks to @LuisMendo, here is the graph of answers.

# Remarks

* This is a code-golf so shortest code wins
* Pay attention to standard loopholes
* It's your freedom to decide how to deal with input and output but they should follow standard restrictions.

By the way...

* Comment if you have anything unclear about the challenge
* Personally I would suggest your answer contains a explanation if you are using a golfing language
* Thanks to @GregMartin, read his answer for a good mathematical explanation for the challenge.

# Example Code

Here is a ungolfed version of C++ code:

```
#include <iostream>
#include <utility>

int f (double m)
{
    double n = 1, k = 0.001;
    int cnt = 0;
    k *= m;                       // the target minimum size
    while(m*n >= k)
    {
        m -= n;                   // extract a square
        if(n > m)
            std::swap(n, m);      // keep m > n
        ++ cnt;
    }
    return cnt;
}

int main()
{
    double p;
    std::cin >> p;
    std::cout << f(p);
    return 0;
}

```

All calculations related in the example code need an accuracy of 6 decimal digits, which is covered in `float`.

# Answer
> 2 votes
# MATL, 19 bytes

```
`SZ}y-htG/p1e-3>}x@

```

The input is an array with the two numbers defining the original ratio, such as `[1, 1.009]`. (It is not necessary that the numbers be sorted or that one of them be 1.)

Try it online!

### Explanation

```
`        % Do...while loop
  S      %   Sort array. Takes 1×2 array as input (implicit) the first time
  Z}     %   Split array into its 2 elements: first the minimum m, then the maximum M
  y      %   Duplicate m onto the top of the stack. The stack now contains m, M, m
  -      %   Subtract. The stack now contains m, M-m
  h      %   Concatenate into [m, M-m]. This is the remaining piece of paper
  t      %   Duplicate
  G/     %   Divide by input, element-wise
  p      %   Product of array. Gives ratio of current piece's area to initial area
  1e-3>  %   True if this ratio exceeds 1e-3. In that case the loop continues
}        % Finally (execute after last iteration, but still within the loop)
  x      %   Delete last piece of paper
  @      %   Push current loop counter. This is the result
         % End (implicit)
         % Display (implicit)

```

# Answer
> 6 votes
# Haskell, ~~71 70 65 63 62 61 58~~ 56 bytes

Thanks to @xnor for a some ingenious improvements!

```
(n#m)e|e>n*m*1e3=0|n<m=m#n$e|d<-n-m=(d#m)e+1
n!m=n#m$n*m

```

Try it online!

# Answer
> 4 votes
## JavaScript (ES6), ~~59~~ 58 bytes

```
f=(m,n=!(k=m/1e3,c=0))=>m*n<k?c:(c++,m-=n)<n?f(n,m):f(m,n)

```

### Test

```
f=(m,n=!(k=m/1e3,c=0))=>m*n<k?c:(c++,m-=n)<n?f(n,m):f(m,n)

console.log(f(1.002))
console.log(f(1.003))
console.log(f(1.004))
console.log(f(1.005))
console.log(f(1.006))
console.log(f(1.007))
console.log(f(1.008))
console.log(f(1.009))
```

# Answer
> 3 votes
## Mathematica, ~~64~~ 53 bytes

```
({t=1,#}//.{a_,b_}/;1000a*b>#:>Sort@{++t;a,b-a};t-1)&

```

An imperative (C-style) solution is exactly the same length:

```
(For[t=a=1;b=#,1000a*b>#,If[a>b,a-=b,b-=a];++t];t-1)&

```

# Answer
> 2 votes
# C (GCC/Clang), ~~61~~ 59 bytes

```
c,k;f(m,n){for(k=m*n;m*n/k;m>n?(m-=n):(n-=m))++c;return c;}

```

Input is two integers (width & height) without dot, such as `f(1999,1000)`.

I hope someone could save one byte pushing C into the 58-byte club. ;)

# Answer
> 1 votes
# C, 59 bytes

```
s,a,n=1e3;C(m){for(a=m;m*n>a;s++)m>n?m-=n:(n-=m);return s;}

```

Try It online

The input is an integer which is the width / height ratio in thousandths (eg. 1002 for 1.002:1).

### Ungolfed version

```
int C(int m)
{
    int n = 1000;
    int a = m;
    int s = 0;

    while (m * n > a)
    {
        if (m > n)
            m -= n;
        else
            n -= m;

        s++;
    }

    return s;
}

```

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


title: longest ungolfable quine

text:
# Question
Title: longest ungolfable quine
Create a quine that cannot be golfed. Your score is your byte count, where higher is better. If someone finds a shorter version, their score is your original byte count, and you lose points

Scoring example:

original submission, 34 bytes // score is 34

```
function(this){self.printquine();}

```

golfed, 31 bytes // score is 34, original submission is scored 31

```
function(this){_.printquine();}

```

golfed again by someone else, 18 bytes // score is 31, first golfed submission is scored 18

```
this.printquine();

```

Here "golfing" is defined as creating a shorter version of **someone else's** source file exclusively by removing characters or rearranging existing characters (without affecting its quine-ness). This seems like a good way to define it because otherwise googling the shortest quine in a given language would be the only reasonable starting point.

Standard loopholes apply, unless you have a creative use of one then go for it. Use this site's definition of a valid quine, if you can actually find one that's agreed on.

# Answer
> 2 votes
# HQ9+, 1 byte

I guess I'm not winning any points for creativity.

```
Q

```

---
Tags: quine
---


title: Complete the grid-filling meander

text:
# Question
Title: Complete the grid-filling meander
A grid-filling meander is a closed path that visits every cell of a square \\$N \times N\\$ grid at least once, never crossing any edge between adjacent cells more than once and never crossing itself. For example:

Once filled, each cell of the grid can be represented by one of the following 8 tiles:

Numbered this way, the tiles of the above meander can be represented by this matrix:

```
5 6 5 6
4 8 3 2
5 7 6 2
4 3 4 3

```

Your task is to complete a grid-filling meander given an incomplete set of tiles. For example, the incomplete meander:

...which can be represented using `0`s for missing tiles:

```
5 0 0 0 6
0 0 7 0 0
0 0 0 0 3
2 4 0 0 0
0 0 3 0 0

```

...could be completed like this:

...i.e.:

```
5 6 5 1 6
4 8 7 6 2
5 7 7 7 3
2 4 8 8 6
4 1 3 4 3

```

### Specifications

* The input will always have at least \\$1\\$ and at most \\$N^2\\$ (non-empty) tiles, where \\$2 \le N \le 7\\$.
* You may use any set of values to represent the tiles, as long as it's specified in your answer.
* Your input and output may be in any format and order, as long as it's specified in your answer.
* At least one valid solution will exist for all inputs (i.e. you don't need to handle invalid input).
* Standard I/O rules apply.
* Standard loopholes are forbidden.
* Explanations, even for "practical" languages, are encouraged.

### Test cases

> Input ():
>
> ```
> 0 6
> 0 0
>
> ```
>
> Output ():
>
> ```
> 5 6
> 4 3
>
> ```

> Input ():
>
> ```
> 5 6 5 6
> 4 0 3 2
> 5 7 6 2
> 4 3 4 3
>
> ```
>
> Output ():
>
> ```
> 5 6 5 6
> 4 8 3 2
> 5 7 6 2
> 4 3 4 3
>
> ```

> Input ():
>
> ```
> 5 0 0 0 6
> 0 0 7 0 0
> 0 0 0 0 3
> 2 4 0 0 0
> 0 0 3 0 0
>
> ```
>
> Output ():
>
> ```
> 5 6 5 1 6
> 4 8 7 6 2
> 5 7 7 7 3
> 2 4 8 8 6
> 4 1 3 4 3
>
> ```

# Answer
# JavaScript (ES7),  ~~236 ... 193~~  185 bytes

Outputs by modifying the input matrix.

```
m=>(g=(d,x,y,v,r=m[y],h=_=>++r[x]<9?g(d,x,y,v)||h():r[x]=0)=>r&&1/(n=r[x])?x|y|!v?n?g(d='21100--13203-32-21030321'[n*28+d*3+7&31],x+--d%2,y+--d%2,v+=n<7||.5):h():!m[v**.5|0]:0)(0,0,0,0)

```

Try it online!

(includes some post-processing code to print the result both as a matrix and as a flat list compatible with the visualization tool provided by the OP)

## Results

## How?

### Variables

\\$g\\$ is a recursive function taking the current direction \\$d\\$, the current coordinates \\$(x,y)\\$ and the number of visited cells \\$v\\$.

The following variables are also defined in the scope of \\$g\\$:

* \\$r\\$ is the current row of the matrix.

```
r = m[y]

```
* \\$h\\$ is a helper function that tries all values from \\$1\\$ to \\$8\\$ for the current cell and invokes \\$g\\$ with each of them. It either stops as soon as \\$g\\$ succeeds or sets the current cell back to \\$0\\$ if we need to backtrack.

```
h = _ => ++r[x] < 9 ? g(d, x, y, v) || h() : r[x] = 0

```

### Initial checks

We first make sure that our current location is valid and we load the value of the current cell into \\$n\\$:

```
r && 1 / (n = r[x]) ? ... ok ... : ... failed ...

```

We test whether we're back to our starting position, i.e. we're located at \\$(0,0)\\$ and we've visited at least a few cells (\\$v\>0\\$):

```
x | y | !v ? ... no ... : ... yes ...

```

For now, let's assume that we're not back to the starting point.

### Looking for a path

If \\$n\\$ is equal to \\$0\\$, we invoke \\$h\\$ to try all possible values for this tile.

If \\$n\\$ is not equal to \\$0\\$, we try to move to the next tile.

The tile connections are encoded in a lookup table, whose index is computed with \\$n\\$ and \\$d\\$, and whose valid entries represent the new values of \\$d\\$.

```
d = '21100--13203-32-21030321'[n * 28 + d * 3 + 7 & 31]

```

The last 8 entries are invalid and omitted. The other 4 invalid entries are explicitly marked with hyphens.

For reference, below are the decoded table, the compass and the tile-set provided in the challenge:

```
   | 1 2 3 4 5 6 7 8
---+-----------------
 0 | 0 - - 1 3 - 3 1          1
 1 | - 1 - - 2 0 2 0        0 + 2
 2 | 2 - 1 - - 3 1 3          3
 3 | - 3 0 2 - - 0 2

```

We do a recursive call to \\$g\\$ with the new direction and the new coordinates. We add \\$1/2\\$ to \\$v\\$ if we were on a tile of type \\$7\\$ or \\$8\\$, or \\$1\\$ otherwise (see the next paragraph).

```
g(d, x + --d % 2, y + --d % 2, v += n < 7 || .5)

```

If \\$d\\$ is invalid, \\$x\\$ and \\$y\\$ will be set to *NaN*, forcing the next iteration to fail immediately.

### Validating the path

Finally, when we're back to \\$(0,0)\\$ with \\$v\>0\\$, it doesn't necessarily mean that we've found a valid path, as we may have taken a shortcut. We need to check if we've visited the correct number of cells.

Each tile must be visited once, except tiles \\$7\\$ and \\$8\\$ that must be visited twice. This is why we add only \\$1/2\\$ to \\$v\\$ when such a tile is visited.

In the end, we must have \\$v = N^2\\$. But it's also worth noting that we can't possibly have \\$v \> N^2\\$. So, it's enough to test that we don't have \\$v \< N^2\\$, or that the \\$k\\$th row of the matrix (0-indexed) does not exist, where \\$k=\lfloor\sqrt{v}\rfloor\\$.

Hence the JS code:

```
!m[v ** .5 | 0]

```

### Formatted source

```
m => (
  g = (
    d,
    x, y,
    v,
    r = m[y],
    h = _ => ++r[x] < 9 ? g(d, x, y, v) || h() : r[x] = 0
  ) =>
    r && 1 / (n = r[x]) ?
      x | y | !v ?
        n ?
          g(
            d = '21100--13203-32-21030321'[n * 28 + d * 3 + 7 & 31],
            x + --d % 2,
            y + --d % 2,
            v += n < 7 || .5
          )
        :
          h()
      :
        !m[v ** .5 | 0]
    :
      0
)(0, 0, 0, 0)

```
> 11 votes

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