title: Is this Pascal's Matrix?

text:
# Question
Title: Is this Pascal's Matrix?
In Pascal's triangle each number is the sum of the two numbers directly above it, treating empty spots as zero:

By rotating the triangle, we can cut out square matrices of varying sizes and rotations which I will call *Pascal's matrices*. Note that those matrices always need to contain the top \\$1\\$. Here are some examples:

```
1  1  1  1
1  2  3  4
1  3  6 10
1  4 10 20

6  3  1
3  2  1
1  1  1

1  5 15 35 70
1  4 10 20 35
1  3  6 10 15
1  2  3  4  5
1  1  1  1  1

1

1  1
2  1

```

## The Task

Given a square matrix containing positive numbers in any reasonable format, decide if it is a *Pascal's matrix*.

*Decide* means to either return truthy or falsy values depending on whether the input is a *Pascal's matrix*, or to fix two constant values and return one for the true inputs and the other for false inputs.

This is , so try to use as few bytes as possible in the language of your choice. The shortest code in *each language* wins, thus I will not accept an answer.

### Test cases

True

```
[[1, 1, 1, 1], [1, 2, 3, 4], [1, 3, 6, 10], [1, 4, 10, 20]]
[[6, 3, 1], [3, 2, 1], [1, 1, 1]]
[[1, 5, 15, 35, 70], [1, 4, 10, 20, 35], [1, 3, 6, 10, 15], [1, 2, 3, 4, 5], [1, 1, 1, 1, 1]]
[[1]]
[[1, 1], [2, 1]]

```

False

```
[[2]]
[[1, 2], [2, 1]]
[[1, 1], [3, 1]]
[[1, 1, 1, 1], [1, 2, 3, 4], [1, 4, 6, 10], [1, 4, 10, 20]]
[[6, 3, 1], [1, 1, 1], [3, 2, 1]]
[[2, 2, 2, 2], [2, 4, 6, 8], [2, 6, 12, 20], [2, 8, 20, 40]]
[[40, 20, 8, 2], [20, 12, 6, 2], [8, 6, 4, 2], [2, 2, 2, 2]]
[[1, 5, 15, 34, 70], [1, 4, 10, 20, 34], [1, 3, 6, 10, 15], [1, 2, 3, 4, 5], [1, 1, 1, 1, 1]]

```

# Answer
# Brachylog, ~~28~~ ~~24~~ 23 bytes

This feels quite long but here it is anyway

* -4 bytes thanks to DLosc by compressing the optional flips
* -1 bytes thanks to DLosc again by doing the partial sums in 1 go

`{|↔}\↰₁{k{a₀ᶠ+ᵐ}ᵐ⊆?h=₁}`

## Explanation

```
{|↔}\↰₁{k{a₀ᶠ+ᵐ}ᵐ⊆?h=₁}       # Tests if this is a pascal matrix:
{|↔}\↰₁                       #     By trying to get a rows of 1's on top
{|↔}                          #       Through optionally mirroring vertically
     \                        #       Transposing
      ↰₁                      #       Through optionally mirroring vertically

       {k{a₀ᶠ+ᵐ}ᵐ⊆?h=₁}       #     and checking the following
                  ?h=₁        #        first row is a rows of 1's
        k{     }ᵐ             #        and for each row except the last
          a₀ᶠ+ᵐ               #          calculate the partial sum by
          a₀ᶠ                 #             take all prefixes of the input
             +ᵐ               #             and sum each
               ⊆?             #        => as a list is a subsequence of the rotated input

```

Try it online!
> 7 votes

# Answer
# JavaScript (ES6), 114 bytes

```
m=>[m,m,m=m.map(r=>[...r].reverse()),m].some(m=>m.reverse(p=[1]).every(r=>p=!r.some((v,x)=>v-~~p[x]-~~r[x-1])&&r))

```

Try it online!
> 4 votes

# Answer
# MATL, 17 bytes

```
4:"Gas2YLG@X!X=va

```

Try it online! Or verify all test cases.

Outputs `1` for Pascal matrices, `0` otherwise.

### Explanation

```
4:      % Push [1 2 3 4]
"       % For each
  G     %   Push input: N×N
  a     %   1×N vector containing 1 for matrix columns that have at least a nonzero
        %   entry, and 0 otherwise. So it gives a vector containing 1 in all entries
  s     %   Sum. Gives N
  2YL   %   Pascal matrix of that size
  G     %   Push input
  @     %   Push current iteration index
  X!    %   Rotate the matrix that many times in steps of 90 degress
  X=    %   Are they equal?
  v     %   Concatenate with previous accumulated result
  a     %   Gives 1 if at least one entry of the vector is nonzero
        % End (implicit). Display (implicit)

```
> 4 votes

# Answer
# Charcoal, 41 bytes

```
Ｆ‹¹⌈§θ⁰≔⮌θθＦ‹¹⌈Ｅθ§ι⁰≦⮌θ⌊⭆θ⭆ι⁼λ∨¬κΣ…§θ⊖κ⊕μ

```

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

```
Ｆ‹¹⌈§θ⁰

```

If the maximum of its first row is greater than 1,

```
≔⮌θθ

```

then flip the input array.

```
Ｆ‹¹⌈Ｅθ§ι⁰

```

If the maximum of its first column is greater than 1,

```
≦⮌θ

```

then mirror the input array.

```
⌊⭆θ⭆ι

```

Loop over the elements of the input array and print the minimum result (i.e. the logical And of all of the results),

```
⁼λ∨¬κΣ…§θ⊖κ⊕μ

```

comparing each value to 1 if it is on the first row otherwise the sum of the row above up to and including the cell above.
> 2 votes

# Answer
# , 104 bytes

```
function(m,R=row(m)-1,y=nrow(m):1,Z=choose(R+t(R),R))any(sapply(list(Z,Z[,y],Z[y,y],Z[y,]),identical,m))

```

Try it online!

Nasty...

Creates a canonical Pascal's matrix `Z` with dimensions equal to that of `m`, then tests if the input matrix `m` is `identical` to `any` of the rotations of `Z`.
> 2 votes

# Answer
# Python 2, 129 bytes

```
f=lambda M,i=4:i and(set(M[0])=={1}and all(a+b==c for x,y in zip(M,M[1:])for a,b,c in zip(x[1:],y,y[1:]))or f(zip(*M[::-1]),i-1))

```

Try it online!

Returns `True` if `M` is a Pascal's Matrix, else `0`.
> 1 votes

# Answer
# Julia 0.7, 78 bytes

```
m->any(i->(n=rotr90(m,i))[1]<2&&all(cumsum(n)'[1:end-1,:]-n[2:end,:].==0),0:3)

```

Try it online!
> 1 votes

# Answer
# 05AB1E, 29 bytes

```
¬P≠iR}DøнP≠ií}¬PΘsü)ε`sηOQ}P*

```

Try it online or verify all test cases.

**Explanation:**

```
¬P≠i }        # If the product of the first row of the (implicit) input-matrix is NOT 1:
    R         #  Reverse the order of the rows
D             # Duplicate the resulting matrix
 øнP≠i }      # If the product of the first column is NOT 1:
      í       #  Reverse each row individually
¬PΘ           # Check if the product of the first row is exactly 1
           *  # AND
          P   # And check if everything after the following map is truthy:
sü)ε     }    #  Map over each pair of rows:
    `sη       #   Get the prefixes of the first row
       O      #   Sum each prefix
        Q     #   And check if it's equal to the second row
              # (and output the result implicitly)

```
> 1 votes

# Answer
# Java (JDK), 234 bytes

```
m->{int l=m.length,L=l-1,p=1,s=0,S=0,e=l,E=l,d=1,D=1,i,j;if(m[0][0]>1|m[0][L]>1){s=L;e=d=-1;}if(m[0][0]>1|m[L][0]>1){S=L;E=D=-1;}for(i=s;i!=e;i+=d)for(j=S;j!=E;j+=D)p=(i==s|j==S?m[i][j]<2:m[i][j]==m[i-d][j]+m[i][j-D])?p:0;return p>0;}

```

Try it online!

## Credits
> 1 votes

# Answer
# Kotlin, 269 bytes

```
{m:List<List<Int>>->val n=m.size
var r=0
var c=0
fun f()=if(m[0][0]!=1)m[n-r-1][n-c-1]
else if(m[n-1][0]!=1)m[r][n-c-1]
else if(m[0][n-1]!=1)m[n-r-1][c]
else m[r][c]
var g=0<1
for(l in 0..n*2-2){r=l
c=0
var v=1
do{if(r<n&&c<n)g=f()==v&&g
v=v*(l-c)/++c}while(--r>=0)}
g}

```

Try it online!
> 1 votes

# Answer
# Jelly, 22 bytes

```
Ż€Iṫ2⁼ṖaFḢ=1Ʋ
,Ṛ;U$Ç€Ẹ

```

Try it online!

### Explanation

Helper link, checks whether this rotation of matrix valid

```
Ż€            | prepend each row with zero
  I           | find differences within rows
   ṫ2         | drop the first row
     ⁼Ṗ       | compare to the original matrix
              |   with the last row removed
       a      | logical and
        FḢ=1Ʋ | top left cell is 1

```

Main link

```
,Ṛ            | copy the matrix and reverse the rows
  ;U$         | append a copy of both of these
              |   with the columns reversed
     Ç€       | run each version of the matrix
              |   through the helper link
       Ẹ      | check if any are valid

```
> 1 votes

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


title: Gotta Collect 'Em All

text:
# Question
Title: Gotta Collect 'Em All
Your task here will be to write a very dumb AI capable of fetching all treasures on a map.

## Map

The map is defined as follow: (`artist-mode`™-powered)

Basic case:

```
+-+-+-+-+-+-+-+-+-+-+-+-+-+
|P| | | | | | | | | | | | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+
| | | | | | | | | | | | | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+
| | |T| | | | | | | | | | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+
| | |M|M|M|T| | | | | | | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+
| | | | | | | | | |T| | | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+
| | | | | | | | | | | | | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+

```

---

Locked up:

```
+-+-+-+-+-+-+-+-+-+-+-+-+-+
|P| | | | |M| | | | | | | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+
| | | | | |M| | | | | | | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+
| | |T| | |M| | | | | | | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+
|M|M|M|M|M|M| | | | | | | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+
| | | | | | | | | | | | | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+
| | | | | | | | | | | | | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+

```

---

No treasures

```
+-+-+-+-+-+-+-+-+-+-+-+-+-+
|P| | |M|M|M| | | | | | | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+
| | | | | |M|M|M|M|M|M|M| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+
| | |M| | | | | | | | | | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+
| | |M|M|M|M| | | | | | | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+
| | | | | | | | | | | | | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+
| | | | | | | | | | | | | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+

```

---

No way to move

```
+-+-+-+-+-+-+-+-+-+-+-+-+-+
|M|M|M|M|M|M|M|M|M|M|M|M|M|
+-+-+-+-+-+-+-+-+-+-+-+-+-+
|M|M|M|M|M|M|M|M|M|M|M|M|M|
+-+-+-+-+-+-+-+-+-+-+-+-+-+
|M|M|M|M|M|M|M|M|M|M|M|M|M|
+-+-+-+-+-+-+-+-+-+-+-+-+-+
|M|M|M|M|M|M|M|M|M|M|M|M|M|
+-+-+-+-+-+-+-+-+-+-+-+-+-+
|M|M|M|M|M|M|M|M|M|M|M|M|M|
+-+-+-+-+-+-+-+-+-+-+-+-+-+
|M|M|M|M|M|M|M|M|M|M|M|M|P|
+-+-+-+-+-+-+-+-+-+-+-+-+-+

```

---

The world is a giant treasure

```
+-+-+-+-+-+-+-+-+-+-+-+-+-+
|T|T|T|T|T|T|T|T|T|T|T|T|T|
+-+-+-+-+-+-+-+-+-+-+-+-+-+
|T|T|T|T|T|T|T|T|T|T|T|T|T|
+-+-+-+-+-+-+-+-+-+-+-+-+-+
|T|T|T|T|T|T|P|T|T|T|T|T|T|
+-+-+-+-+-+-+-+-+-+-+-+-+-+
|T|T|T|T|T|T|T|T|T|T|T|T|T|
+-+-+-+-+-+-+-+-+-+-+-+-+-+
|T|T|T|T|T|T|T|T|T|T|T|T|T|
+-+-+-+-+-+-+-+-+-+-+-+-+-+
|T|T|T|T|T|T|T|T|T|T|T|T|T|
+-+-+-+-+-+-+-+-+-+-+-+-+-+

```

---

Back alley

```
+-+-+-+-+-+-+-+-+-+-+-+-+-+
|P| | | | | | | | | | | |T|
+-+-+-+-+-+-+-+-+-+-+-+-+-+
| | | | | | | | |M|M|M|M|M|
+-+-+-+-+-+-+-+-+-+-+-+-+-+
| | | | | | | | | | | | | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+
| | | | | | | | |M|M|M|M|M|
+-+-+-+-+-+-+-+-+-+-+-+-+-+
| | | | | | | | | | | | |T|
+-+-+-+-+-+-+-+-+-+-+-+-+-+
| | | | | | | | |M|M|M|M|M|
+-+-+-+-+-+-+-+-+-+-+-+-+-+

```

---

1x1

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

```

## Cells

* Empty cases are empty
* `M` cells are mountains and cannot be walked on.
* `T` cells are treasures that need to be collected.

## Goal

* You will generate a "path string" describing the movements needed to obtain all the treasures. No extraneous moves after treasures were all collected are allowed.
* Moves can be: "Left" "Right" "Up" "Down".
* Generating a move that'd result in an attempt to clib a mountain (M) or hit a wall (Out Of Bounds) is an error (it's not simply ignored).

## General Rules

* **Map must be read.** (this is not a challenge, there are an infinite possible number of maps).
* There will always be one and only one player, P.
* There will always be a path to go get all the treasures, T.
* Map size may vary, but it'll always be at least `1x1`.
* The AI starts at P, the player.
* There might not be a treasure on the map. In this case, you're allowed to exit any falsy value (that isn't a valid path)
* Your algorithm pick -- it needn't be the most efficient.
* You must solve it before the heat death of the universe
* It is not guaranteed you'll be able to access every non-mountain cell on the map. Just enough to fetch all treasures.
* The AI may see the whole map.
* Standard rules apply for your answer with default I/O rules, so you are allowed to use STDIN/STDOUT, functions/method with the proper parameters and return-type, full programs. Your call.
* Default Loopholes are forbidden.
* If possible, please add a link with a test for your code (i.e. TIO).
* Also, adding an explanation for your answer is highly recommended.

## Format

### Input

* You can decide to take inputs as a multi-line string with or without the ASCII separators I included (same for the space between cells)
* Passed via stdio or a function argument or on your program's stack(s)
* You can other identifiers instead of " ",M,P -- so long they are uniquely identifiable and not a separator (you need it specified in your answer)
* You can decide to take an 2-dimensional array, or matrix, or the equivalent in your language, with the cells, as `[['P', ' ', ' '...], [...], [' ', ' ', 'T'...]...]`.
* You are also allowed to take an array of strings, such as `["P ...", ..., " T..."...]`.
* You are allowed to take the length as an extra input (width/height).

### Output

* The output must look like "LLRRUUDD" (Left/Left/Right/Right/Up/Up/Down/Down)
* You can decide to intersperse spaces, newlines, etc, so long they don't mix with your instructions.
* You can other identifiers instead of L,R,U,D -- so long they are uniquely identifiable and not a separator (you need it specified in your answer)
* There might be different solutions (i.e. `DR` vs `RD`), it doesn't matter which you output in this case.

## Scoring

This is a challenge.

# Answer
> 2 votes
# APL (Dyalog Extended), 132 bytes

Saved 16 bytes by having the function ouput `1 0,0 1,¯1 0,0 ¯1` instead of `U,L,D,R`. TIO link below decodes output back to letters.

I may write an explanation later, but most of the work is creating a graph in a format that the dfns path function likes, then using it to find successive shortest paths between the start and all treasures. Quite efficient, but because treasures are pathed left-to-right, top-to-bottom instead of being based on proximity, the answers are not optimal.

```
{z←×`/d←⍴⍵⋄g←z⍴⊂⍬⋄s t m←(⍸∘∊⍵=⊢)¨'PTM'⋄f←{(⍵∊m)∨0=⍺:⍬⋄g[⍺],←⍵}⋄h←(f`⍨,f)⋄⍬≡t⊣{2h`/⍵⊣2h`⌿⍵}x←d⍴⍳z:⍬⋄⊃,/⊃,/2-/¨{⍸x=⍵}¨¨2(g⌂path,)/s,t}

```

Try it online!

# Answer
> 5 votes
# PHP, ~~385~~ ~~335~~ ~~307~~ ~~270~~ 256 bytes

```
function c(&$m,$x,$r=-1,$d=0){if($r<0)$r=array_search(P,$m);$m[$r]=V;if(!in_array(T,$m))die;foreach([$r%$x?$r-1:-1,$m[$r-$x]?$r-$x:-1,$m[$r+$x]?$r+$x:-1,$r%$x<$x-1?$r+1:-1]as$o=>$n)if($n>=0&$m[$n]!=M&$m[$n]!=V){echo LUDR[$o];c($m,$x,$n,$o);}echo RDUL[$d];}

```

Try it online!

Uses a recursive depth-first search to crawl the map until all treasures are found.

Input is a one-dimensional array map and number of columns, example: `c( $map, 13 );`.
Output is to `STDOUT` as `L,R,U and D`.

Or **242 bytes** to output as numbers (but I prefer the letters).

**Ungolfed**

```
function c( &$m, $x, $r=-1, $d=0 ) {

    // locate starting room ($r) on first move
    if( $r < 0 )
        $r = array_search( 'P', $m );

    // mark square on map ($m) with V to show it has been visited
    $m[ $r ] = 'V';

    // end if no more treasures
    if ( ! in_array( 'T', $m ) )
        exit;

    // generate list of adjacent squares
    $dirs = [
        $r % $x ? $r - 1 : -1,            // Left
        $m[ $r - $x ] ? $r - $x : -1,     // Up
        $m[ $r + $x ] ? $r + $x : -1,     // Down
        $r % $x < $x - 1 ? $r + 1 : -1    // Right
    ];

    // consider valid directions for next move
    foreach ( $dirs as $o => $n )
        // if not a Wall or Mountain and not Visited
        if ( $n >= 0 and $m[ $n ] != 'M' and $m[ $n ] != 'V' ) {
            // display the direction
            echo 'LUDR'[ $o ];
            // and recursively keep crawling
            c( $m, $x, $n, $o );
        }

    // reached a dead end, go back to previous square
    echo 'RDUL'[ $d ];   // display the reverse direction

}

```

Basic Case

```
+-+-+-+-+-+-+-+-+-+-+-+-+-+
|P| | | | | | | | | | | | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+
| | | | | | | | | | | | | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+
| | |T| | | | | | | | | | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+
| | |M|M|M|T| | | | | | | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+
| | | | | | | | | |T| | | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+
| | | | | | | | | | | | | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+

```

`DDDDDRUUUUURDDRUURDDRUURDDDLDLLLDRRRRURUUUURDDDDDLRRU`

Locked Up

```
+-+-+-+-+-+-+-+-+-+-+-+-+-+
|P| | | | |M| | | | | | | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+
| | | | | |M| | | | | | | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+
| | |T| | |M| | | | | | | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+
|M|M|M|M|M|M| | | | | | | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+
| | | | | | | | | | | | | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+
| | | | | | | | | | | | | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+

```

`DDRUURDD`

No Treasure:

```
+-+-+-+-+-+-+-+-+-+-+-+-+-+
|M|M|M|M|M|M|M|M|M|M|M|M|M|
+-+-+-+-+-+-+-+-+-+-+-+-+-+
|M|M|M|M|M|M|M|M|M|M|M|M|M|
+-+-+-+-+-+-+-+-+-+-+-+-+-+
|M|M|M|M|M|M|M|M|M|M|M|M|M|
+-+-+-+-+-+-+-+-+-+-+-+-+-+
|M|M|M|M|M|M|M|M|M|M|M|M|M|
+-+-+-+-+-+-+-+-+-+-+-+-+-+
|M|M|M|M|M|M|M|M|M|M|M|M|M|
+-+-+-+-+-+-+-+-+-+-+-+-+-+
|M|M|M|M|M|M|M|M|M|M|M|M|P|
+-+-+-+-+-+-+-+-+-+-+-+-+-+

```

*(no output)*

No way to move

```
+-+-+-+-+-+-+-+-+-+-+-+-+-+
|M|M|M|M|M|M|M|M|M|M|M|M|M|
+-+-+-+-+-+-+-+-+-+-+-+-+-+
|M|M|M|M|M|M|M|M|M|M|M|M|M|
+-+-+-+-+-+-+-+-+-+-+-+-+-+
|M|M|M|M|M|M|M|M|M|M|M|M|M|
+-+-+-+-+-+-+-+-+-+-+-+-+-+
|M|M|M|M|M|M|M|M|M|M|M|M|M|
+-+-+-+-+-+-+-+-+-+-+-+-+-+
|M|M|M|M|M|M|M|M|M|M|M|M|M|
+-+-+-+-+-+-+-+-+-+-+-+-+-+
|M|M|M|M|M|M|M|M|M|M|M|M|P|
+-+-+-+-+-+-+-+-+-+-+-+-+-+

```

*(no output)*

The world is a giant treasure

```
+-+-+-+-+-+-+-+-+-+-+-+-+-+
|T|T|T|T|T|T|T|T|T|T|T|T|T|
+-+-+-+-+-+-+-+-+-+-+-+-+-+
|T|T|T|T|T|T|T|T|T|T|T|T|T|
+-+-+-+-+-+-+-+-+-+-+-+-+-+
|T|T|T|T|T|T|P|T|T|T|T|T|T|
+-+-+-+-+-+-+-+-+-+-+-+-+-+
|T|T|T|T|T|T|T|T|T|T|T|T|T|
+-+-+-+-+-+-+-+-+-+-+-+-+-+
|T|T|T|T|T|T|T|T|T|T|T|T|T|
+-+-+-+-+-+-+-+-+-+-+-+-+-+
|T|T|T|T|T|T|T|T|T|T|T|T|T|
+-+-+-+-+-+-+-+-+-+-+-+-+-+

```

`LLLLLLUURDRURDRURDRURDDDLLLLLLLDDRURDRURDRURDRURUUUURDDDDDLRRUUUUURDDDDDRUUUUU`

1x1

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

```

*(no output)*

Back Alley

`DDDDDRUUUUURDDDDDRUUUUURDDDDDRUUUUURDDDDDRUUUUURRRRRLLLLLDDRRRRRLLLLLDDRRRRR`

Hedge Maze (an original creation)

```
+-+-+-+-+-+-+-+-+-+-+-+-+-+
|P|M| |T|M| | | |M| |M|M|T|
+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |M| |M| | |M|T|M|T| | | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+
|T| | |M| |M| |T|M|M|M| |M|
+-+-+-+-+-+-+-+-+-+-+-+-+-+
|M|M| | | |M| |M|M| | | |M|
+-+-+-+-+-+-+-+-+-+-+-+-+-+
|T| | |M| |M| | | | |M| |M|
+-+-+-+-+-+-+-+-+-+-+-+-+-+
|M|M| |T| | |M|M|M|M|M| |T|
+-+-+-+-+-+-+-+-+-+-+-+-+-+

```

`DDRRUURLDDDDLLRRDRRUULRUURURRDDLDDRRRURRUULLUDRRRUDLDDDDR`

# Answer
> 4 votes
# JavaScript (ES6),  ~~187 183~~  173 bytes

Takes input as a matrix of characters. Returns an array of signed integers: **-2** = down, **-1** = right, **1** = left and **2** = up.

```
ff=(m,X,Y,p=[])=>/T/.test(m)?(g=u=>m.some((r,y)=>r.some((c,x)=>(r[o=c=='M'|c>u|(h=X-x)*h+(v=Y-y)*v^c!='P'?0:f(m,x,y,1/X?[...p,h+2*v]:p,r[x]=3-~r[x]),x]=c,o)))?O:g(-~u))``:O=p

```

Try it online! (with the output translated back to **L**, **R**, **U**, **D**)

### How?

This AI:

* Is definitely more artificial than intelligent.
* Rushes like a mad man in the map (i.e. implements a depth-first search).
* Stops as soon as there are no more treasures, but otherwise does not care about the positions of the remaining treasures. This test is done with a regular expression.

```
  /T/.test(m)

```
* Compares the quadrance between its current position \\$(X,Y)\\$ and a new position \\$(x,y)\\$ with \\$1\\$ to know whether it can move there. Or tests if the cell contains `"P"` if its position is not yet defined.

```
  (h = X - x) * h + (v = Y - y) * v ^ c != 'P'

```
* Writes \\$4N\\$ on a cell that has been visited \\$N\\$ times and uses this threshold combined with an internal counter \\$u\\$ to decide -- in a sudden flash of lucidity -- whether it should backtrack over already visited cells when everything else failed.

# Answer
> 2 votes
# Python 2, 233 bytes

```
G=input()
e=enumerate
P=T=M=E=frozenset()
for i,k in e(G):
 for j,l in e(k):exec l+'|={(i,j)}'
G={0}
c=-1
while T-G|G&M|G-E-T:
 G-=G;e=list(P)[0];x=c=c+1;r=()
 while x:m=x%5%4;x/=5;r+=m,;e=~-m%2*~-m+e[0],m%2*(m-2)+e[1];G|={e}
print r

```

Try it online!

Very slow. Most of the test cases would probably time out.

`MPTLRUD``EMPT1302`. Any other characters should be considered to be prefixes, separators or postfixes.

# Answer
> 2 votes
# Python 3, ~~766~~ 622 bytes

```
def f(s,W,H):
 Z=enumerate;I=[("L",-1),("R",1),("D",1j),("U",-1j)];o="";P,M,T=map(lambda t:{x+y*1jfor y,l in Z(s)for x,c in Z(l)if c==t},'PMT');E=D={c:{t:0}for t,c in Z(T)}
 while len(E):
  E={}
  for m,N in[(c+d,D[c])for c in D for _,d in I if not c+d in M]:
   if 0<=m.real<W and 0<=m.imag<H:
    T={t:N[t]+1for t in N if not m in D or not t in D[m]}
    if any(T)or not m in D:
     E[m]=T
  for m in E:
   if m in D:
    D[m].update(E[m])
   else:
    D[m]=E[m]
 for m in P:
  if m in D:
   for g in D[m]:
    while D[m][g]:
     for i,d in I:
      if m+d in D and D[m+d][g]<D[m][g]:
       o+=i;m=m+d;break
 return o

```

Try it online!

Fairly certain after this that I will never win code-golf, but contributing because I enjoyed the exercise.

This version works by building a dictionary of reachable locations, with each entry being a dictionary whose keys are a unique ID for the treasure, and whose value is the shortest distance to that treasure. The code supports multiple values for P: for each one it outputs a path that collects the treasures. No optimization is attempted.. it picks the nearest treasure from its current location until all treasures are collected.

---
Tags: code-golf, parsing
---


title: Terms of the EKG sequence

text:
# Question
Title: Terms of the EKG sequence
# Introduction

The EKG sequence begins with 1 and 2, then the rule is that the next term is the smallest positive integer not already in the sequence and whose common factor with the last term is greater than 1 (they are not coprimes).

The first terms are:

> 1, 2, 4, 6, 3, 9, 12, 8, 10, 5, 15, ...

It's called EKG because the graph of its terms is quite similar to an EKG.

It's sequence A064413 in the OEIS.

# Challenge

You have to write a function which takes an integer *n* as input and outputs how many of the *n* first terms of the sequence are greater than *n*.

As the sequence's rule begins with the third term, the input integer has to be greater or equal to 3. For example, given input `10` the output is `1` because the 7th term is `12` and none of the other first ten terms exceed 10.

# Test cases

> 3 -\> 1
>
> 10 -\> 1
>
> 100 -\> 9
>
> 1000 -\> 70

# Rules

* For integers lower than 3, the function may output 0 or an error code.
* No other particular rules except: it's code golf, the shorter the better!

# Answer
> 7 votes
# Jelly, ~~20~~ ~~19~~ 18 bytes

```
S‘gṪ’ɗƇḟ¹Ṃṭ
1Ç¡>¹S

```

This is a full program.

Try it online!

### How it works

```
1Ç¡>¹S       Main link. Argument: n (integer)

1            Set the return value to 1.
 Ç¡          Call the helper link n times.
   >¹        Compare the elements of the result with n.
     S       Take the sum, counting elements larger than n.

S‘gṪ’ɗƇḟ¹Ṃṭ  Helper link. Argument: A (array or 1)

S            Take the sum of A.
 ‘           Increment; add 1.
     ɗƇ      Drei comb; keep only elements k of [1, ..., sum(A)+1] for which the
             three links to the left return a truthy value.
  g              Take the GCD of k and all elements of A.
   Ṫ             Tail; extract the last GCD.
    ’            Decrement the result, mapping 1 to 0.
       ḟ¹    Filterfalse; remove the elements that occur in A.
         Ṃ   Take the minimum.
          ṭ  Tack; append the minimum to A.

```

Note that the generated sequence is \\$\[1, \mathbf{0}, 2, 4, 6, 3, 9, 12, 8, 10, 5, 15, \dots\]\\$. Since calling the helper link \\$n\\$ times generates a sequence of length \\$n + 1\\$, the \\$0\\$ is practically ignored.

# Answer
> 6 votes
# Perl 6, ~~66~~ ~~63~~ ~~59~~ 58 bytes

*-4 bytes thanks to Jo King*

```
{sum (1,2,{+(1...all *gcd@_[*-1]>1,*∉@_)}...*)[^$_]X>$_}

```

Try it online!

Too slow on TIO for n = 1000.

# Answer
> 5 votes
# Husk, 16 bytes

```
#>¹↑¡§ḟȯ←⌋→`-Nḣ2

```

Try it online!

## Explanation

```
#>¹↑¡§ḟȯ←⌋→`-Nḣ2  Implicit input, say n=10
              ḣ2  Range to 2: [1,2]
    ¡             Construct an infinite list, adding new elements using this function:
                   Argument is list of numbers found so far, say L=[1,2,4]
             N     Natural numbers: [1,2,3,4,5,6,7...
           `-      Remove elements of L: K=[3,5,6,7...
      ḟ            Find first element of K that satisfies this:
                    Argument is a number in K, say 6
     §    →         Last element of L: 4
         ⌋          GCD: 2
       ȯ←           Decrement: 1
                    Implicitly: is it nonzero? Yes, so 6 is good.
                  Result is the EKG sequence: [1,2,4,6,3,9,12...
   ↑              Take the first n elements: [1,2,4,6,3,9,12,8,10,5]
#                 Count the number of those
 >¹               that are larger than n: 1

```

# Answer
> 4 votes
# JavaScript (ES6), ~~107~~ ~~106~~ 105 bytes

```
f=(n,a=[2,1],k=3)=>a[n-1]?0:a.indexOf(k)+(C=(a,b)=>b?C(b,a%b):a>1)(k,a[0])?f(n,a,k+1):(k>n)+f(n,[k,...a])

```

Try it online!

### How?

The helper function \\$C\\$ returns *true* if two given integers are *not* coprime:

```
C = (a, b) => b ? C(b, a % b) : a > 1

```

The array \\$a\\$ is initialized to \\$\[2,1\]\\$ and holds all values that were encountered so far in reverse order. Therefore, the last value is always \\$a\[0\]\\$.

To know if \\$k\\$ qualifies as the next term of the sequence, we test whether the following expression is equal to \\$0\\$:

```
a.indexOf(k) + C(k, a[0])

```

`a.indexOf(k)` is equal to either:

* \\$-1\\$ if \\$k\\$ is not found in \\$a\\$
* \\$0\\$ if \\$k\\$ is equal to the last value (in which case it's necessarily not coprime with it)
* some \\$i\ge 1\\$ otherwise

Therefore, `a.indexOf(k) + C(k, a[0])` is equal to \\$0\\$ if and only if \\$k\\$ is not found in \\$a\\$ and \\$k\\$ is not coprime with the last value (\\$-1+true=0\\$).

# Answer
> 4 votes
## Haskell, ~~89~~ 82 bytes

Edit: -7 bytes thanks to @H.PWiz

```
f l=[n|n<-[3..],all(/=n)l,gcd(l!!0)n>1]!!0:l
g n=sum[1|x<-iterate f[2]!!(n-2),x>n]

```

Try it online!

# Answer
> 4 votes
# APL (Dyalog Unicode), 39 bytesSBCS

-2 bytes thanks to ngn, -1 byte by using proper conditional checking.

```
{+/⍵<⍵⍴3{(1=⍺∨⊃⌽⍵)∨⍺∊⍵:⍵∇⍨⍺+1⋄⍵,⍺}⍣⍵⍳2}

```

Try it online!

# Answer
> 3 votes
# MATL, 29 bytes

```
qq:2:w"GE:yX-y0)yZdqg)1)h]G>z

```

Try it online!

Explanation:

```
	#implicit input, n, say 10
qq:	#push 1:8
2:	#push [1 2]. Stack: {[1 .. 8], [1 2]}
w	#swap top two elements on stack
"	#begin for loop (do the following n-2 times):
 GE:	#push 1...20. Stack: {[1 2], [1..20]}
 y	#copy from below. Stack:{[1 2], [1..20], [1 2]}
 X-	#set difference. Stack: {[1 2], [3..20]}
 y0)	#copy last element from below. Stack:{[1 2], [3..20], 2}
 yZd	#copy from below and elementwise GCD. Stack:{[1 2], [3..20],[1,2,etc.]}
 qg)	#select those with gcd greater than 1. Stack:{[1 2], [4,6,etc.]}
 1)	#take first. Stack:{[1 2], 4}
 h	#horizontally concatenate. Stack:{[1 2 4]}
 ]	#end of for loop
G>z	#count those greater than input
	#implicit output of result

```

# Answer
> 2 votes
# JavaScript, ~~93~~ ~~91~~ 87 bytes

Throws an overflow error for `0` or `1`, outputs `0` for `2`.

```
n=>(g=x=>n-i?g[++x]|(h=(y,z)=>z?h(z,y%z):y)(x,c)<2?g(x):(g[c=x]=++i,x>n)+g(2):0)(i=c=2)

```

Try it online

# Answer
> 2 votes
# APL(NARS), chars 121, bytes 242

```
∇r←a w;i;j;v
r←w⋄→0×⍳w≤2⋄i←2⋄r←⍳2⋄v←1,1,(2×w)⍴0
j←¯1+v⍳0
j+←1⋄→3×⍳1=j⊃v⋄→3×⍳∼1<j∨i⊃r⋄r←r,j⋄i+←1⋄v[j]←1⋄→2×⍳w>i
r←+/w<r
∇

```

test in less one minute here in running time:

```
  a¨3 10 100 1000 2000
1 1 9 70 128

```

Natural there is no check for type and for range...

# Answer
> 1 votes
# Japt, ~~23~~ 21 bytes

```
@_jX ªAøZ}f}gA=ì)Aè>U

```

Try it

```
@_jX ªAøZ}f}gA=ì)Aè>U
                          :Implicit input of integer U
             A            :10
               ì          :Digit array
              =           :Reassign to A
@          }g             :While the length of A < U+1, take the last element as X,
                          :pass it through the following function & push the result to A
 _       }f               :  Find the first integer Z >= 0 that returns falsey
  jX                      :    Is Z co-prime with X?
     ª                    :    OR
      AøZ                 :    Does A contain Z?
                )         :End loop
                 Aè>U     :Count the elements in A that are greater than U

```

# Answer
> 1 votes
# Python 3, 153 bytes

```
import math
def f(n):
 l=[1];c=0
 for _ in range(n-1):l+=[min(*range(2,n*4),key=lambda x:n*8if x in l or math.gcd(x,l[-1])<2else x)];c+=l[-1]>n
 return c

```

Try it online! (Warning: Takes ~30 seconds to evaluate)

---
Tags: code-golf, sequence
---


title: The Base in the mix

text:
# Question
Title: The Base in the mix
**Input:**
A list/array of integers for which each item is in the range of `2-36`.

**Output:**
The sum of the integers (as base 10), where each next integer is in the base of the previous value (starting with a regular base 10).

**Example:**
Let's say we have an input like this: `[4, 12, 34, 20, 14, 6, 25, 13, 33]`
Then we have a sum like this:

```
4    (4  in base-10) +
6    (12 in base-4 ) +
40   (34 in base-12) +
68   (20 in base-34) +
24   (14 in base-20) +
6    (6  in base-14) +
17   (25 in base-6 ) +
28   (13 in base-26) +
42   (33 in base-13)
= 235

```

***Mathematical base explained:***
I considered assuming everyone knows how base works, but I'll give a brief example of how it works anyway, just in case. Let's take the `34 in base-12` for example, how did we get `40`?

```
1-34 in regular base-10:
 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34
 So, from 1 to 34 is 34 steps in base-10

1-34 in base-12:
 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 1A, 1B, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 2A, 2B, 30, 31, 32, 33, 34
 So, from 1 to 34 is 40 steps in base-12

```

Here is perhaps a useful calculator.

**Challenge rules:**

* Array size will be in reasonable range (like `1-100` / see test cases).
* The test cases will never contain integers of which the current value is invalid for it's previous base (i.e. You will never have something like `19 in base-6` or `6 in base-6`, because base-6 only contains the digits `0-5`).
* You can take the input any way you'd like. Can be as an int-array, as a comma/space-separated string, etc. Your call. (You are also allowed to take the int-array reversed, which could be useful for stack-based programming languages.)

**General Rules:**

* This is , so shortest answer in bytes wins.
Don't let code-golf languages discourage you from posting answers with non-golfing languages. Try to come up with as short an answer as possible for any programming language.
* Standard rules apply for your answer, so you are allowed to use STDIN/STDOUT, functions/method with the proper parameters, full programs. Your call.
* Default Loopholes are forbidden.
* If possible, please add a link with a test for your code.
* Also, please add an explanation if necessary.

**Test cases:**

```
[4, 12, 34, 20, 14, 6, 25, 13, 33]                            ->   235
 4+ 6+  40+ 68+ 24+ 6+ 17+ 28+ 42

[5, 14, 2, 11, 30, 18]                                        ->   90
 5+ 9+  2+ 3+  33+ 38

[12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 12, 2, 11, 3, 10, 2, 10]    ->   98
 12+ 13+ 11+ 9+ 8+ 7+ 6+ 5+ 4+ 3+ 5+  2+ 3+  3+ 3+  2+ 2

[36, 36]                                                      ->   150
 36+ 114

```

# Answer
> 4 votes
# 05AB1E, ~~7~~ ~~6~~ 5 bytes

Uses the 05AB1E encoding.

Saved 1 byte using the new built-in `š` as suggested by *Kevin Cruijssen*

```
TšüöO

```

**Explanation**

Input list is taken reversed, as allowed by challenge specification.

```
Tš     # prepend a 10 to the list
  üö   # reduce by conversion to base-10
    O  # sum

```

Try it online!

Modified testsuite

# Answer
> 9 votes
# Python 3, 40 bytes

```
lambda a:sum(map(int,map(str,a),[10]+a))

```

Tests are at **ideone**

`map(str, a)` creates a generator, `G`, that calls `str` on each value in `a`, converting to strings
`map(int, G, [10]+a)` creates a generator that calls `int(g, v)` for pairs across `G` and `[10]+a`
`int(g, v)` converts the string `g` from the integer base `v` (if `v` is in `[2,36]` and `g` is valid)
`sum` does what it says on the tin

# Answer
> 7 votes
# Python 2, 48 bytes

```
lambda a:sum(int(`x`,y)for x,y in zip(a,[10]+a))

```

Tests are at **ideone**

`zip(a,[10]+a)` traverses pairs of the values in `a`, and the previous value or `10` for the first
the `backticks` in the `int` call convert `x` to a string, `s`
`int(s, y)` converts the string `s` from the integer base `y` (if `y` is in `[2,36]` and `s` is valid)
`sum` does what it says on the tin

# Answer
> 6 votes
# Perl, ~~35~~ ~~34~~ 33 bytes

Includes +2 for `-ap`

Run with the list of numbers on STDIN:

```
basemix.pl <<< "4 12 34 20 14 6 25 13 33";echo

```

`basemix.pl`:

```
#!/usr/bin/perl -ap
$\+=$&+"$`$& 10"*/.$/*$`for@F}{

```

I've been waiting for ages for a chance to use this abuse...

## Explanation

The input numbers can have at most 2 digits. A number `xy` in base `b` is simply `b*x+y`. I'm going to use the regex `/.$/` so the first digit ends up in `$`` and the last digit in `$&`, so the contribution to the sum is `$&+$b*$``.

I abuse the fact that `for` does not properly localize the regex variables (like for example `map` and `while` do) so the results of a match in the previous loop is still available in the current loop. So if I'm careful about the order in which I do the operations the base is available as `"$`$&"`, except for the very first loop where I need the base to be 10. So I use `"$`$& 10"` instead

The way the first `$&` works is an abuse too since it is actually changed by the `/.$/` while it is already on the stack waiting to be added.

The final abuse is the `}{` at the end which changes the loop implied by `-p` from

```
LINE: while (defined($_ = <ARGV>)) {
    ...code..
}
continue {
    die "-p destination: $!\n" unless print $_;
}

```

to

```
LINE: while (defined($_ = <ARGV>)) {
    ...code..
}
{
}
continue {
    die "-p destination: $!\n" unless print $_;
}

```

Which means `$_` will be undefined in the print, but it still adds `$\` in which I accumulated the sum. It is also a standard golf trick to get post-loop processing

# Answer
> 4 votes
# PHP, ~~53~~ 51 bytes

```
for(;$x=$argv[++$i];$b=$x)$s+=intval($x,$b);echo$s;

```

Iterates over the input, converting each input to string variant. Then takes the integer value using the previous number as base. For the first number, the base will not be set, PHP will then start off with 10 (inferred from the number format).

Run like this (`-d` added for aesthetics only):

```
php -d error_reporting=30709 -r 'for(;$x=$argv[++$i];$b=$x)$s+=intval($x,$b);echo$s;' -- 12 11 10 9 8 7 6 5 4 3 12 2 11 3 10 2 10;echo

```

## Tweaks

* Actually, no need to convert to string, as CLI arguments are already string. Saved 2 bytes.

# Answer
> 3 votes
# Java 7, ~~109~~ ~~89~~ 86 bytes

```
int c(int[]a){for(Byte i=1;i<a.length;a[0]+=i.valueOf(a[i]+"",a[++i-2]));return a[0];}

```

Golfed 20 bytes thanks to *@cliffroot* (of which 12 because of a stupid mistake I made myself).

**Ungolfed & test code:**

Try it here.

```
class M{
  static int c(int[] a){
     for(Byte i = 1; i < a.length; a[0] += i.valueOf(a[i]+"", a[++i-2]));
     return a[0];
  }

  public static void main(String[] a){
    System.out.println(c(new int[]{ 4, 12, 34, 20, 14, 6, 25, 13, 33 }));
    System.out.println(c(new int[]{ 5, 14, 2, 11, 30, 18 }));
    System.out.println(c(new int[]{ 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 12, 2, 11, 3, 10, 2, 10 }));
    System.out.println(c(new int[]{ 36, 36 }));
  }
}

```

**Output:**

```
235
90
98
150

```

# Answer
> 3 votes
# Jelly, 7 bytes

```
ṙ1DḅṖḌS

```

Try it online!

# Answer
> 3 votes
## JavaScript ES6, ~~45~~ ~~42~~ 41 Bytes

```
const g =
     a=>a.map(v=>s+=parseInt(v,p,p=v),s=p=0)|s
;

console.log(g.toString().length);                                            // 42
console.log(g([4, 12, 34, 20, 14, 6, 25, 13, 33]));                          // 235
console.log(g([5, 14, 2, 11, 30, 18]  ));                                    // 90
console.log(g([12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 12, 2, 11, 3, 10, 2, 10] )); // 98
```

Conventiently `parseInt(x,0) === parseInt(x,10)`.

**edit**: Saved 1 byte thanks to @ETHproductions

# Answer
> 3 votes
# Java, 86 bytes

```
s->{int[]b={10};return s.reduce(0,(r,n)->{r+=n.valueOf(""+n,b[0]);b[0]=n;return r;});}

```

## Testing and ungolfed

```
import java.util.function.ToIntFunction;
import java.util.stream.Stream;

public class Main {

  public static void main(String[] args) {
    ToIntFunction<Stream<Integer>> f = s -> {
      int[] b = {10};                 // Base, initialized with 10
      return s.reduce(0, (r, n) -> {  // Typical use of reduction, sum starts with 0.
        r += n.valueOf("" + n, b[0]); // Add the value in the previous base.
        b[0] = n;                     // Assign the new base;
        return r;
      });
    };

    System.out.println(f.applyAsInt(Stream.of(new Integer[]{4, 12, 34, 20, 14, 6, 25, 13, 33})));
  }
}

```

# Answer
> 3 votes
# Pure bash, 38

```
b=10
for i;{((t+=$b#$i,b=i));}
echo $t

```

The input list is given at the command-line. `for i;` automatically iterates over the input parameters (equivalent to `for i in $@;`).

Ideone.

# Answer
> 2 votes
## Actually, 12 bytes

```
;p(dX(♂$♀¿Σ+

```

Try it online!

Explanation:

```
;p(dX(♂$♀¿Σ+
;             dupe input
 p            pop first element from list
  (dX         pop and discard last element from other copy
     (♂$      stringify all elements in first copy
        ♀¿    for each pair of elements in the two lists, interpret the first element as a base-(second element) integer
          Σ   sum
           +  add first element of original list

```

# Answer
> 2 votes
## CJam, 15 bytes

```
l~{A\:A10bb}%:+

```

Try it online!

### Explanation

```
l~     e# Read and evaluate input.
{      e# Map this block over the input...
  A    e#   Push A. Initially this is 10, afterwards it will be the value of the
       e#   last iteration.
  \:A  e#   Swap with current value and store that in A for the next iteration.
  10b  e#   Convert to base 10 to get its decimal digits.
  b    e#   Interpret those in the base of the previous A.
}%
:+     e# Sum all of those values.

```

# Answer
> 2 votes
# JavaScript (ES6), ~~54~~ ~~48~~ 40 bytes

I used a recursive approach.

```
f=([b,...a],c)=>b?parseInt(b,c)+f(a,b):0

```

Saved 6 bytes, thanks to Lmis!
Saved 8 more bytes, thanks to Neil!

# Answer
> 2 votes
# Haskell, ~~65~~ 59 bytes

```
b%x|x<1=x|y<-div x 10=b*b%y+x-10*y
sum.((10:)>>=zipWith(%))

```

Test it on Ideone.

# Answer
> 2 votes
# Matlab, 68 bytes

Not a very creative solution, but here it is:

```
function[s]=r(x);j=10;s=0;for(i=x)s=s+base2dec(num2str(i),j);j=i;end

```

Tests:

```
>> r([4,12,34,20,14,6,25,13,33])
ans =
   235
>> r([12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 12, 2, 11, 3, 10, 2, 10])
ans =
   98
>> r([5, 14, 2, 11, 30, 18])
ans =
   90
>> r([36,36])
ans =
   150

```

# Answer
> 2 votes
# Perl 6,  ~~52~~  50 bytes

```
{sum (10,|@_).rotor(2=>-1).map:{+":{.[0]}<{.[1]}>"}}
{sum (10,|@_).rotor(2=>-1).map:{":{.[0]}<$_[1]>"}}

```

## Explanation:

```
# bare block lambda with implicit parameter ｢@_｣
{
  sum

    ( 10, |@_ )        # the input with a preceding 10
    .rotor( 2 => -1 )  # grab 2 values, back up one, repeat
    .map:
    {
      # create a string of the form ":10<4>"
      ":{
        .[0]            # first element from $_
      }<{
        .[1]            # second element from $_
      }>"
    }
}

```

# Answer
> 1 votes
# Python 2, 52 bytes

```
f=lambda x:x[1:]and int(`x.pop()`,x[-1])+f(x)or x[0]

```

Test it on Ideone.

# Answer
> 1 votes
## Julia, 63 Bytes

```
f(l)=sum([parse(Int,string(l[i]),l[i-1])for i=2:length(l)])+l[]

```

Parses each number (except the first) taking the previous element as base and sums. Adds the first element at the end

# Answer
> 1 votes
## Ruby, 52 bytes

```
->a{eval a.zip([10]+a).map{|e|'"%s".to_i(%s)'%e}*?+}

```

### ungolfed

```
->a{
  eval(
    a.zip([10]+a).map { |e|
      '"%s".to_i(%s)' % e
    }.join("+")
  )
}

```

### usage

```
f=->a{eval a.zip([10]+a).map{|e|'"%s".to_i(%s)'%e}*?+}
p f[[4, 12, 34, 20, 14, 6, 25, 13, 33]] # => 235

```

# Answer
> 1 votes
# Scala, 67 bytes

```
def f(a:Int*)=a zip(10+:a)map{t=>Integer.parseInt(""+t._1,t._2)}sum

```

Explanation:

```
def f(a: Int*) =     //declare a method f with varargs of type Int as parameter
a zip (10 +: a)      //zip a with 10 prepended to a, resulting in...
                     //...Array((4,10), (12,4), (34,12), (20,34), (14,20), (6,14), (25,6), (13,25), (33,13))
map { t =>           //map each tuple t to...
  Integer.parseInt(  //...an integer by parsing...
    ""+t._1, t._2    //...a string of the first item in base-second-item.
  )
}
sum                  //and sum

```

# Answer
> 1 votes
# Mathematica, 59 bytes

I wish Mathematica's function names were shorter. But otherwise I'm happy.

```
Tr[FromDigits@@@Transpose@{IntegerDigits/@{##,0},{10,##}}]&

```

For example,

```
Tr[FromDigits@@@Transpose@{IntegerDigits/@{##,0},{10,##}}]&[4,12,34,20,14,6,25,13,33]

```

yields `235`.

`{##,0}` is a list of the input arguments with 0 appended (representing the numerals); `{10,##}` is a list of the input arguments with 10 prepended (representing the bases). That pair of lists is `Transpose`d to associate each with numeral with its base, and `FromDigits` (yay!) converts each numeral-base pair to a base-10 integer, the results of which are summed by `Tr`.

# Answer
> 1 votes
## Common Lisp, 83

```
(lambda(s)(loop for b ="10"then x for x in s sum(#1=parse-integer x :radix(#1#b))))

```

### Details

```
(defun base-mix (list)
  (loop
     for base = "10" then string
     for string in list
     sum (parse-integer string :radix (parse-integer base))))

```

The `loop` construct accepts *"v then w"* iteration constructs, where *v* is an expression to be evaluated the first time the iteration variable is computed, and *w* is the expression to be evaluated for the successive iterations. Declarations are evaluated one after the other, so `base` is first "10", then the previous element `string`of the list `list` being iterated. The `sum` keyword computes a sum: the integer read from `string` with base *b*, where *b* is the integer parsed from the `base` string, in base 10. `#1=` and `#1#` are notations to define and use *reader variables*: the first affects an s-expression to a variable, the other one replaces the reference by the same object. This saves some characters for long names.

### Example

```
(base-mix '("4" "12" "34" "20" "14" "6" "25" "13" "33"))
=> 235

```

# Answer
> 1 votes
# Japt `-x`, 7 bytes

```
äÏsnX}A

```

Try it

```
äÏsnX}A     :Implicit input of array
ä           :Take each consecutive pair of elements
 Ï          :Pass them through the following function as X & Y
  s         :  Convert Y to a base-10 string
   nX       :  Convert to an integer from base-X
     }      :End function
      A     :Before doing any of that, though, prepend 10 to the array
            :Implicit output of the sum of the resulting array

```

---
Tags: code-golf, math, base-conversion
---


title: Japanese Multiplication

text:
# Question
Title: Japanese Multiplication
There's a visual method for multiplication that is taught to Japanese schoolchildren <sup>\[citation needed\]</sup> that uses lines and crossings to get the answer.

Image Source

Your task is to implement this in ASCII art. You will be given two numbers to multiply. The output should be the corresponding ASCII art made up of `\`, `/`, and `X`, padded with ASCII spaces.

The first number of the multiplication will use backslashes, starting from left to right. The second number will use forward slashes, once again from leftmost digit to rightmost. The output is made up of distinct diagonal line groupings. The number of lines within a grouping should be equal to the value of the digit. There should be at least one diagonal space between each grouping and there should be no spaces within the grouping.

Suppose 43 is the first number. Before extending lines and creating crossings, it will start like this:

```
       \
      \
     \

   \
  \
 \
\

```

If the second number is 61, it will look like this before extending and crossing:

```
/
 /
  /
   /
    /
     /

       /

```

Conceptually "extend" the lines, using X's for intersection points, to get the result:

```
       \ /
      \ X /
     \ X X /
      X X X /
   \ / X X X /
  \ X / X X X /
 \ X X / X X X
\ X X X / X X \ /
 X X X X / X \ X
/ X X X X / \ X \
 / X X X X   X \
  / X X X \ / \
   / X X \ X
    / X \ X \
     / \ X \
        X \
       / \

```

# Example Test Cases

5 * 9

```
    \ /
   \ X /
  \ X X /
 \ X X X /
\ X X X X /
 X X X X X /
/ X X X X X /
 / X X X X X /
  / X X X X X /
   / X X X X X
    / X X X X \
     / X X X \
      / X X \
       / X \
        / \

```

16 * 27

```
       \ /
      \ X /
     \ X X
    \ X X \ /
   \ X X \ X /
  \ X X \ X X /
   X X \ X X X /
\ / X \ X X X X /
 X / \ X X X X X /
/ X   X X X X X X /
 / \ / X X X X X X
    X / X X X X X \
   / X / X X X X \
    / X / X X X \
     / X / X X \
      / X / X \
       / X / \
        / X
         / \

```

7 * 24

```
      \ /
     \ X /
    \ X X
   \ X X \ /
  \ X X \ X /
 \ X X \ X X /
\ X X \ X X X /
 X X \ X X X X
/ X \ X X X X \
 / \ X X X X \
    X X X X \
   / X X X \
    / X X \
     / X \
      / \

```

123 * 543

```
       \ /
      \ X /
     \ X X /
      X X X /
   \ / X X X /
  \ X / X X X
   X X / X X \ /
\ / X X / X \ X /
 X / X X / \ X X /
/ X / X X   X X X /
 / X / X \ / X X X
  / X / \ X / X X \ /
   / X   X X / X \ X /
    / \ / X X / \ X X /
       X / X X   X X X
      / X / X \ / X X \
       / X / \ X / X \
        / X   X X / \
         / \ / X X
            X / X \
           / X / \
            / X
             / \

```

735 * 21

```
                \ /
               \ X /
              \ X X
             \ X X \ /
            \ X X \ X
             X X \ X \
          \ / X \ X \
         \ X / \ X \
        \ X X   X \
         X X \ / \
      \ / X \ X
     \ X / \ X \
    \ X X   X \
   \ X X \ / \
  \ X X \ X
 \ X X \ X \
\ X X \ X \
 X X \ X \
/ X \ X \
 / \ X \
    X \
   / \

```

# Rules

* There should be at least one (diagonal) space between each set of lines. For the purposes of this challenge, it doesn't have to line up in any sort of pretty visual way.
* Border crossings should jut out by exactly one slash.
* Any amount of padding to the left or the right is allowed as long as all the crossings line up correctly.
* Single-width ASCII spaces must be used as padding.
* You do not need to calculate the actual result of the multiplication.
* You may assume the number is in base 10 and and is at most three digits long with no zeros.
* Order matters for the purposes of the output. The first number is always in the `\` direction and the second number is always in the `/` direction.
* Input and output may be in any convenient format.
* Standard loopholes are banned.

Happy Golfing!

# Answer
# Canvas, 41 bytes

```
（Ａ┬｛［１｝０｝┐）
⁷Ｌ├Ｘ⁷ｌＹø；｛³×？³ｙ³－╵ｘ＼╋
⁸⤢↔╶╶⁸ｎ

```

Try it here!
> 1 votes

# Answer
# JavaScript (ES6),  ~~207 197 196~~  188 bytes

Takes input as an array of two strings, e.g. `["16", "27"]`. Returns a matrix of characters.

```
a=>([[p,H],[q]]=a.map(x=>[[W=0,...x].map(x=>'1'.repeat(x,W-=~x)).join`0`,W]),[...Array(W+H)]).map((_,y,a)=>a.map((_,x)=>' \\/X'[(d=x-y)<H&~d<H&~(x+=y-H+2)<0&x<W*2&~x&&p[d+H>>1]|2*q[x/2]]))

```

Try it online!
> 0 votes

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


title: Visual Long Multiplication

text:
# Question
Title: Visual Long Multiplication
There is a nice way to perform long multiplication for two integers without having to do anything but counting, which occasional gets shared around the internet. You write the digits of each number as a bunch of slanted lines, with the two numbers at a 90 degree angle. Then you can simply count the intersections in the separate columns that arise. A diagram will probably clarify this. Here is an example for calculating `21 * 32`:

If you google for "visual/graphical long multiplication" you'll find a lot more examples.

In this challenge, you are to generate these diagrams using ASCII art. For the same example, the output would look like this:

```
   \ /
    X /
 \ / X /
\ X / X
 X X / \ /
/ X X   X /
 / X \ / X
  / \ X / \
     X X
    / X \
     / \

```

It's probably easiest to figure out the construction rules for these from some examples (see below), but here some details:

* Intersecting segments are `X`, non-intersecting segments of the lines are `/` or `\`.
* There should be exactly one segment after the outermost intersections.
* There should be exactly one segment between intersections belonging to different digits. If there are zero-digits, these will result in consecutive `/` or `\` segments.
* You have to support any positive input (at least up to some reasonable limit like 216 or 232), and any digits from `0` to `9`. However, you may assume that there neither leading nor trailing `0`s.
* You must not print extraneous leading whitespace or leading or trailing empty lines.
* You may print trailing whitespace but it must not exceed the diagram's axis-aligned bounding box.
* You may optionally print a single trailing newline.
* You may choose in which order you take the two input numbers. However, it you must support arbitrary numbers for either orientation, so you can't choose something like "The larger number is given first".
* If you're taking input as a string, you can use any non-digit separator between the two numbers.

You may write a program or function, taking input via STDIN (or closest alternative), command-line argument or function argument and outputting the result via STDOUT (or closest alternative), function return value or function (out) parameter.

This is code golf, the shortest answer (in bytes) wins.

## Examples

```
1*1
\ /
 X
/ \

2*61
 \ /
\ X /
 X X /
/ X X /
 / X X /
  / X X /
   / X X
    / X \ /
     / \ X
        X \
       / \

 45*1
         \ /
        \ X
       \ X \
      \ X \
     \ X \
      X \
   \ / \
  \ X
 \ X \
\ X \
 X \
/ \

21001*209
       \ /
        X /
       / X
      / / \
   \ / /   \ /
    X /     X /
 \ / X     / X /
\ X / \   / / X /
 X X   \ / / / X /
/ X \   X / / / X /
 / \ \ / X / / / X /
    \ X / X / / / X /
     X X / X / / / X /
    / X X / X / / / X
     / X X / X / / / \
      / X X / X / /
       / X X / X /
        / X X / X
         / X X / \
          / X X
           / X \
            / \

```

# Answer
> 1 votes
# Pyth - 79 bytes

A translation of @AlexeyBurdin's answer. Can probably be golfed a lot more.

```
AzHmu++Gm1sH]Zd]Z,_zwK+lzlHJmm\ KK .e.eX@J+kY+-Yklz@" \/x"+byZHzjbmjk:d2_1:J1_2

```

Takes input as two numbers, newline separated. Explanation coming soon.

Try it online here.

# Answer
> 4 votes
## python, 303

```
def f(s):
    a,b=s.split('*')
    a,b=map(lambda l:reduce(lambda x,y:x+[1]*int(y)+[0],l,[0]),[reversed(a),b])
    n=sum(map(len,[a,b]))
    l=[[' ']*n for i in xrange(n)]
    for i,x in enumerate(a):
        for j,y in enumerate(b):
            l[i+j][j-i+len(a)]=r' \/x'[x+2*y]
    return '\n'.join(''.join(x[2:-1]) for x in l[1:-2])

```

I think it's enough human-readable.
Verification:

```
print '---'
print '\n'.join('"%s"'%x for x in f('21001*209').split('\n'))
print '---'
---
"       \ /            "
"        x /           "
"       / x            "
"      / / \           "
"   \ / /   \ /        "
"    x /     x /       "
" \ / x     / x /      "
"\ x / \   / / x /     "
" x x   \ / / / x /    "
"/ x \   x / / / x /   "
" / \ \ / x / / / x /  "
"    \ x / x / / / x / "
"     x x / x / / / x /"
"    / x x / x / / / x "
"     / x x / x / / / \"
"      / x x / x / /   "
"       / x x / x /    "
"        / x x / x     "
"         / x x / \    "
"          / x x       "
"           / x \      "
"            / \       "
---

```

# Answer
> 2 votes
# Python 3, 205 bytes

```
L=a,b=[eval("+[0]+[1]*".join("0%s0"%x)[2:])for x in input().split()]
A,B=map(len,L)
for c in range(2,A+B-1):print((" "*abs(c-A)+" ".join(" \/X"[a[i-c]+2*b[i]]for i in range(max(0,c-A),min(c,B))))[1:A+B-2])

```

The expressions are quite long so I think there's a fair amount of room for improvement, but anyway...

Takes input space-separated via STDIN, e.g.

```
21 32
   \ /
    X /
 \ / X /
\ X / X
 X X / \ /
/ X X   X /
 / X \ / X
  / \ X / \
     X X
    / X \
     / \

```

There's a possible trailing space on some lines, but the `A+B-2` ensures that all of the trailing spaces are within the bounding box.

# Answer
> 1 votes
# C#, 451 bytes

```
void d(string s){var S=s.Split('*');int X=S[1].Select(c=>c-47).Sum(),Y=S[0].Select(c=>c-47).Sum(),L=9*(X+Y),A=1,B=L/3,i,j;var a=Range(0,L).Select(_=>new int[L]).ToArray();foreach(var c in S[1]){for(i=48;i<c;++i){for(j=-1;j<Y;++j)a[B-j][A+j]=1;A++;B++;}A++;B++;}A=1;B=L/3;foreach(var c in S[0]){for(i=48;i<c;++i){for(j=-1;j<X;++j)a[B+j][A+j]|=2;A++;B--;}A++;B--;}Write(Join("\n",a.Select(r=>Concat(r.Select(n=>@" /\X"[n]))).Where(r=>r.Trim().Any())));}

```

Formatted for readability, the function in context:

```
using System.Linq;
using static System.Console;
using static System.Linq.Enumerable;
using static System.String;

class VisualMultiply
{
    static void Main(string[] args)
    {
        new VisualMultiply().d("21001*209");

        WriteLine();
    }

    void d(string s)
    {
        var S = s.Split('*');

        int X = S[1].Select(c => c - 47).Sum(),
            Y = S[0].Select(c => c - 47).Sum(),
            L = 9 * (X + Y),
            A = 1,
            B = L / 3,
            i,
            j;

        var a = Range(0, L).Select(_ => new int[L]).ToArray();

        foreach (var c in S[1])
        {
            for (i = 48; i < c; ++i)
            {
                for (j = -1; j < Y; ++j)
                    a[B - j][A + j] = 1;
                A++;
                B++;
            }
            A++;
            B++;
        }

        A = 1;
        B = L / 3;
        foreach (var c in S[0])
        {
            for (i = 48; i < c; ++i)
            {
                for (j = -1; j < X; ++j)
                    a[B + j][A + j] |= 2;
                A++;
                B--;
            }
            A++;
            B--;
        }

        Write(Join("\n", a.Select(r => Concat(r.Select(n => @" /\X"[n]))).Where(r => r.Trim().Any())));
    }
}

```

The bitwise OR was just for fun, but addition would work too.

# Answer
> 1 votes
# JavaScript (*ES6*) 271

I'm sure that there is a solution that builds the output row by row, fiddling with math and x,y coordinates (x+y==k, x-y==k ...). But I still can't nail it.

So here is a solution that simply draws the lines one by one.

Run the snippet in Firefox to test.

```
F=(a,b)=>( // string parameters
  t=u=0,[for(v of a)t-=~v],[for(v of b)u-=~v],
  r=t+u,o=[...' '.repeat(r*r-r)],
  L=(x,y,n,z,m,c)=>{
    for(i=0;d=n[i++];)
      for(j=0;++x,y+=z,j++<d;)
        for(l=m+1,p=x+y*r-1-r;l--;p+=r-z,o[p-p%r-1]='\n')
          o[p]=o[p]>' '&&o[p]!=c?'X':c
  },
  L(u,0,a,1,u,'/'),
  L(0,u,b,-1,t,'\\'),
  o.join('')
)

// TEST

function test()
{
  O.innerHTML= F(A.value, B.value);
}

test();
```

```
<input id=A value=21001> * <input id=B value=209> <button onclick='test()'>-></button>
<pre id=O></pre>
```

# Answer
> 1 votes
## VC++ ~~(289)~~280

```
t(char*a){int i,j,k,r,c=1,e,A=0,B=0,*C,G[99],f,u;for(C=&A;c+48|(k=(c=(*(a+=c<1))---48)>0);G[2**(C=!(c+6)?&(B+=A):&(++*C))]=k**C);for(i=0;i<B*B;printf("\n%c"+!!j,32+15*((k=(c<(f=G[(c=i/B)+(j=i%B)+A+2]))*(j<f)*(f>A))+4*(r=(!!e*B>c+(e=G[A+j-c]))*(!!e*c>A-e-2)*(e<A)))+13*k*r),i++);

```

## Usage

```
#include  <stdio.h>
#include  <conio.h>

int t(char*);

int main(void)
{   char a[]="123*45";
    t((char*)a);
    getch();
    return 0;
}

int
//-------- padded code ------
t(char*a){int i,j,k,r,c=1,e,A=0,B=0,*C,G[99],f,u;memset(G,0,396);for(C=&A;c+48|(k=(c=(*(a+=c<1))---48)>0);G[2**(C=!(c+6)?&(B+=A):&(++*C))]=k**C);for(i=0;i<B*B;printf("\n%c"+!!j,32+15*((k=(c<(f=G[(c=i/B)+(j=i%B)+A+2]))*(j<f)*(f>A))+4*(r=(!!e*B>c+(e=G[A+j-c]))*(!!e*c>A-e-2)*(e<A)))+13*k*r),i++);

//---------------------------
return 0;}

```

## Results

```
       \ /
      \ x /
     \ x x /
      x x x /
   \ / x x x
  \ x / x x \ /
   x x / x \ x /
\ / x x / \ x x /
 x / x x   x x x /
/ x / x \ / x x x /
 / x / \ x / x x x
  / x   x x / x x \
   / \ / x x / x \
      x / x x / \
     / x / x x
      / x / x \
       / x / \
        / x
         / \

```

> * the function iterates one single loop , and use some geometricks and ascii trifling.

# Answer
> 1 votes
# Canvas, 41 bytes

```
（Ａ┬｛［１｝０｝┐）
⁷Ｌ├Ｘ⁷ｌＹø；｛³×？³ｙ³－╵ｘ＼╋
⁸⤢↔╶╶⁸ｎ

```

Try it here!

# Answer
> 0 votes
## C (329 b)

```
int f(char*a){int i,j,r,k,c,h,o,e=15,m=99,A=0,B=0,*C,L[m][m],G[m],*g=G;for(C=&A;(c=*a-48)+48;C=!(c+6)?&B:&(*C+=(*g++=c+1)),a++);for(i=B-1,j=0;j<(r=A+B-1);i--,j++)for(k=0,o=4*!!((*(g-=!*g))---1);k<=*(C=(h=i<0)?&B:&A);k++)L[abs(i)+k][j+k-2*k*h]+=o/(3*h+1)*e;for(i=0;i<r*r;i++)printf("\n%c"+!!(i%r),((h=L[i/r][i%r])>e*4)?120:h+32);}

```

## TRY IT

# Answer
> 0 votes
# Jelly, 58 bytes

```
ŒDṙLN‘ƊṚị“\/X ”K€
L‘0xż1xⱮ$F
DÇ€Ḥ2¦+þ/µZJUṖ;J’⁶xⱮżÑṖḊẎḊ$€Y

```

Try it online!

### Explanation

A full program that takes the two numbers as a list of two integers and returns a string.

Helper link 1: rotate the matrix

```
ŒD                        | get the diagonals
  ṙ                       | rotate left by
   LN‘Ɗ                   | minus num columns +1
       Ṛ                  | reverse order
        ị“\/X ”           | index into \/X
               K€         | join each with spaces

```

Helper link 2: generate the row and column templates

```
L‘0x                      | 0 copied (num digits + 1) times
    ż                     | interleaved with
     1xⱮ$                 | 1 copied as specified by the digits
         F                | flattened

```

Main link

```
D                         | convert to decimal digits
 Ç€                       | call above link for each number
   Ḥ2¦                    | double the second one
      +þ/                 | outer product using +
         µ                | start a new monadic chain
          ZJUṖ;J’         | reversed range counting down
                          | the columns, followed by range
                            counting up the rows (without
                            duplicating 0 in the middle)
                   ⁶xⱮ    | that many spaces (to provide indents)
                      ż   | interleaved with
                       Ñ  | rotated matrix
                        ṖḊẎḊ$€ Y | remove blank rows and columns and join with newlines

```

# Answer
> 0 votes
# , 294 bytes

```
d=do.call;r=outer;m=d(r,c(Map(function(y,w)d(c,c(lapply(y%/%10^rev(0:log10(y))%%10,function(z)c(0,rep(w,z))),0)),scan(),1:2),`+`))+1;p=matrix(" ",u<-sum(dim(m)),u);p[d(r,c(lapply(dim(m),seq),function(a,b)nrow(m)-a+b+u*(a+b-2)))]=c(" ","\\","/","X")[m];cat(apply(p,1,paste,collapse=""),sep="\n")

```

Try it online!

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


# Question
Title: Code Golf: 6174 - Kaprekar's mythical constant
Why is the number 6174 so interesting? As defined by Wikipedia

> 1. Take any four-digit number, using at least two different digits. (Leading zeros are allowed.)
> 2. Arrange the digits in ascending and then in descending order to get two four-digit numbers, adding leading zeros if necessary.
> 3. Subtract the smaller number from the bigger number.
> 4. Go back to step 2.
>
> The above process, known as Kaprekar's routine, will always reach 6174 in at most 7 iterations. Once 6174 is reached, the process will continue yielding it.

Write a program which runs the Kaprekar's routine against a given four-digit number (see definition above) printing out each step of the routine.

Rules:

* Submissions must be complete programs.
* Input must be read from standard input. Piping from *echo* is OK.
* Input should be in numeric form.
* Printing out leading zeros is required. (See examples below.)
* Last line should say how many iterations were needed. Punctuation is required.

Examples:

```
> 2607
7620 - 0267 = 7353
7533 - 3357 = 4176
7641 - 1467 = 6174
Iterations: 3.

> 1211
2111 - 1112 = 0999
9990 - 0999 = 8991
9981 - 1899 = 8082
8820 - 0288 = 8532
8532 - 2358 = 6174
Iterations: 5.

> 6174
7641 - 1467 = 6174
Iterations: 1.

```

Any programming language is welcome. Extra points for esoteric ones + a small bounty.

**Update 1**: There is already a similar question.

**Update 2**: Added example for 6174 as input. Thanks to Peter Taylor for the notice.

# Answer
# Perl - 147 143 134 130 129 126 129 128 126

```
for($_=<>;$_-6174+!$c;$c++){$_=reverse$d=join'',sort split//,"$_"
|$|x4;printf"$_ - $d = %04d\n",$_-=$d}die"Iterations: $c.\n"

```

EDIT: Now complies with 6174 case, at the cost of a few chars... run with `echo -n <number> | perl kaprekar.pl`

EDIT: Finally back to where I was before :D
> 9 votes

# Answer
## Ruby 1.9, 122 characters

```
puts"Iterations: #{(1..7).find{s=$_.chars.sort*"";puts [r=s.reverse,?-,s,?=,$_="%04d"%(r.to_i-s.to_i)]*" ";~/6174/}}."

```

Example invocation:

```
$ echo 1211 | ruby -ln kaprekar.rb

```

I've counted the `-ln` flag as 4 characters (difference between the normal invocation `ruby kaprekar.rb` and `ruby -ln kaprekar.rb`).
> 10 votes

# Answer
# Python, 141 chars

```
n=input()
i=0
while n-6174:a=''.join(sorted("%04d"%n));b=a[::-1];n=int(b)-int(a);print"%s - %s = %04d"%(b,a,n);i+=1
print"Iterations: %d."%i

```
> 7 votes

# Answer
## Golfscript, 74 characters

```
);:|;{0):0;|$:§-1%" - "§" = ""0"4$~§~-+-4>:|n|6174`=!}do"Iterations: "0"."

```
> 6 votes

# Answer
# Haskell, ~~197~~ ~~192~~ ~~182~~ 181 characters

```
import List
p=putStrLn.unwords
"6174"%k|k>0=p["Iterations:",shows k"."]
n%k=p[b,"-",a,"=",c]>>c%(k+1)where a=sort n;b=reverse a;c=take 4$shows(read b-read a)"0"
main=getLine>>=(%0)

```
> 5 votes

# Answer
# \>\<\> - 268 308

```
</&4pff1
v>i86*-:n&1-:&?!
>ao&        v
<v&0pff+1gff
 >&1+:4=   ?v&:a%:}-a,
 v&8[4r::0}~<
 >&1-:?!v&:@@:@(?$}&:&3%1=?}
 v      >~:}}:}@:}$:}
 \:n}:n}:n}:n}' - 'ooo:n}:n}:n}:n}' = 'ooo
 \a*+a*+a*+}a*+a*+a*+-:0&\
 v?       =4&:+1&,a-}:%a:<
/\&~~rnnnnao:29777****=   ?v
voooooooooooo"Iterations: "/
\ffgna'.'oo;

```

Not much of a contender for golf, but it was fun to write. :)

Run with `./fish.py kaprekar.fish -v <number>`
EDIT: Now takes input from STDIN.
> 5 votes

# Answer
## JavaScript, ~~189~~ ~~182~~ 165 chars

Credit to DocMax:

```
for(n=prompt(i=o=e='');!i--|n-6174;o+=n+' - '+a+' = '+(n=(p=n-a+e)[3]?p:0+p)+'\n')
  b=n.split(e).sort(),n=b.reverse(a=b.join(e)).join(e);
alert(o+"Iterations: "+~i+'.')

```

Original:

```
for(n=prompt(i=o=e='');n-6174;o+=(i++?n+"\n":e)+(n=(a=n.split(e).sort().join(e)).split(e).reverse().join(e))+' - '+a+' = ',n=n-a+e)while(!n[3])n=0+n
alert(o+n+"\nIterations: "+i+'.')

```

Ungolfed:

```
var i = 0;
var n = prompt();
var out = '';
while (n != 6174) {
    while ((n=''+n).length<4) n='0'+n // pad number
    if(i)out+=n+"\n"

    a = n.split('').sort().join('');
    n = a.split('').reverse().join('');

    out += n + ' - ' + a + ' = '
    n-=a
    i++;
}
console.log(out + "6174\nIterations: " + i + '.');

```
> 4 votes

# Answer
### PowerShell, 125 ~~128~~ ~~130~~ ~~131~~

```
for($a,$OFS=$input+'';$b-6174;++$i){$a=$b=+($c=''+($x="$a 000"[0..4]|sort)[4..0])-"$x"
"$c-$x = {0:d4}"-f$a}"Iterations: $i."

```

Passes all test cases from the question.
> 3 votes

# Answer
## JavaScript, 260 bytes

```
function z(c){for(u=c+y;u.length<4;)u=0+u;return u}for(p=prompt(i=0,r=y="");;)
if(s=(p+y).split(y).sort(),t=s.concat().reverse(),a=s.join(y),b=t.join(y),q=a<b?b:a,
w=a<b?a:b,p=z(q-w),i++,r+=z(q)+" - "+z(w)+" = "+p+"\n",p==6174)break;alert(r+
"Iterations: "+i+".")

```
> 2 votes

# Answer
**Scala 276**

```
object o{var i=0;def a(v:String){val c=v.toList.sortWith(_>_).mkString;val b=c.reverse;val d=c.toInt-b.toInt;val e="0"*(4-(d+"").length)+d;val p=c+" - "+b+" = "+e;if(d!=6174){println(p);i=i+1;a(e)}else{println(p+"\nIterations: "+(i+1)+".")}};def main(s:Array[String])=a(s(0))}

```

**Scala 283**

```
object o{var i=0;def a(v:String){val c=v.toList.sortWith(_>_).mkString;val b=c.reverse;val d=c.toInt-b.toInt;val e="0"*(4-(d+"").length)+d;val p=c+" - "+b+" = "+e;if(d!=6174){println(p);i=i+1;a(e)}else{println(p);println("Iterations: "+(i+1)+".")}};def main(s:Array[String])=a(s(0))}

```

diff:

```
else{println(p);println("Iterations: "+(i+1)+".")}};
// to
else{println(p+"\nIterations: "+(i+1)+".")}};

```
> 2 votes

# Answer
# Clojure, 256 characters

```
(let[i #(Integer/parseInt%)f #(format"%04d"%)a #(->>% f sort(apply str)i)d #(->>% f sort reverse(apply str)i)k #(let[u(d %)l(a %)n(- u l)](println(f u)"-"(f l)"="(f n))n)](while true(println"Iterations:"(count(take-while #(not=% 6174)(iterate k(read)))))))

```
> 2 votes

# Answer
## Scala 2.9, 194 characters

```
object K extends App{var(c,s)=(0,args(0));do{var d=s.sorted;var e=d.reverse.toInt-d.toInt;s="%04d".format(e);println(d.reverse+" - "+d+" = "+s);c+=1}while(s!="6174");print("Iterations: "+c+".")}

```

Makes use of the App trait from Scala 2.9.

**Edit:** gives correct output for initial input of 6174.
> 2 votes

# Answer
# PHP, 215 ~~259~~ ~~276~~ characters

```
<?php echo">";$n=str_split(str_pad(trim(fgets(STDIN)),4,0,0));for($k=0,$z=0;$k-6174;$z++){sort($n);$a=implode($n);$b=strrev($a);$k=str_pad($b-$a,4,0,0);echo"$b - $a = $k\n";$n=str_split($k);}echo"Iterations: $z\n";

```

Ungolfed:

```
<?php
echo ">";
$n = str_split(str_pad(trim(fgets(STDIN)),4,0,0));
for($k=0, $z=0; $k-6174; $z++) {
    sort($n);
    $a = implode($n);
    $b = strrev($a);
    $k = str_pad($b-$a,4,0,0);
    echo "$b - $a = $k\n";
    $n = str_split($k);
}
echo "Iterations: $z\n";

```
> 2 votes

# Answer
## CoffeeScript, 233 225 characters

```
o=e='';i=0;n=prompt()
while n!=6174
  n=e+n;q=(n='0'+n if !n[3]) for x in [0..2];n?=q;o+=n+"\n" if i;a=n.split(e).sort().join(e);n=a.split(e).reverse().join(e);o+=n+' - '+a+' = ';n-=a;i++
alert(o+"6174\nIterations: "+i+'.')

```

Try it here or with instructions here.
> 2 votes

# Answer
## GAWK - 152 chars

This is a GNU awk version. It may not work with other non-gnu versions.

```
{for(z=$1;z-6174+!c;++k){split(z,a,"");asort(a);for(b=c=i=0;i<4;z=c-b){c+=a[i+1]*10^i;b=b*10+a[++i]}printf c" - %.4d = "z"\n",b}print"Iterations: "k"."}

$ awk -f k.awk <<< 9992
2999 - 9992 = 6993
3699 - 9963 = 6264
2466 - 6642 = 4176
1467 - 7641 = 6174
Iterations: 4

```
> 2 votes

# Answer
## Ruby, 179 chars but posting anyway

```
s=gets.chomp
n=0
begin
  s=s.to_s.chars.sort.reduce{|s,c|s+c}.rjust(4,'0')
  a=s.reverse
  puts"#{a} - #{s} = #{'%04d'%(s=a.to_i-s.to_i)}"
  n+=1
end while s!=6174
puts"Iterations: #{n}."

```
> 2 votes

# Answer
# K, 104

```
{b::();{b,:,k," = ",r:"0"^(-:4)$$. k:(x@>x)," - ",x@<x;r}\[$x];-1'c,,"Iterations: ",$#c:$[1=#b;b;-1_b];}

```

Test cases

```
k){b::();{b,:,k," = ",r:"0"^(-:4)$$. k:(x@>x)," - ",x@<x;r}\[$x];-1'c,,"Iterations: ",$#c:$[1=#b;b;-1_b];}'2607 1211 6174;
7620 - 0267 = 7353
7533 - 3357 = 4176
7641 - 1467 = 6174
Iterations: 3
2111 - 1112 = 0999
9990 - 0999 = 8991
9981 - 1899 = 8082
8820 - 0288 = 8532
8532 - 2358 = 6174
Iterations: 5
7641 - 1467 = 6174
Iterations: 1

```
> 2 votes

# Answer
**PERL**

```
chomp($n=<STDIN>);
    do{
       $t++;
       $desc=join('',reverse sort split(//,$n));
       $asc=join('', sort split(//,$n));
       $n=($desc - $asc);
       for($i=4;$i>length $n;$i--){
          $n="0".$n;
       }
       print $desc." - ".$asc." = ".$n."\n";
       $n="6174" if $n eq "0000";
    }while($n ne "6174");
    print "Iterations: $t.\n";

```
> 1 votes

# Answer
# Mathematica, ~~314~~ 291 characters

This is the program, kaprekar.m :-

```
SetOptions[$Output,FormatType->OutputForm];
x=$ScriptCommandLine[[2]];
f[x_]:=(a=Characters@x;
b=Sort@ToExpression@a;
c=Sort[FromDigits/@{#,Reverse@#}&@b];
{c,{b,a}}=IntegerString[{#2-#&@@c,c},10,4];
Print[a," - ",b," = ",c];c)
x=f@x;
e=NestWhileList[f,x,#!="6174"&];
Print["Iterations: ",N@Length@e]

```

Setting the path prior to running :-

```
$ PATH=${PATH}:/Applications/Mathematica.app/Contents/MacOS ; export PATH

```

Running the program :-

```
$ MathematicaScript -script kaprekar.m 2607
7620 - 0267 = 7353
7533 - 3357 = 4176
7641 - 1467 = 6174
Iterations: 3.
$ MathematicaScript -script kaprekar.m 1211
2111 - 1112 = 0999
9990 - 0999 = 8991
9981 - 1899 = 8082
8820 - 0288 = 8532
8532 - 2358 = 6174
Iterations: 5.
$ MathematicaScript -script kaprekar.m 6174
7641 - 1467 = 6174
Iterations: 1.

```
> 1 votes

# Answer
# PHP, 160 bytes

```
function k($n,$d=1){$o=str_split($n);sort($o);echo$q=strrev($r=join($o))," - $r = ",$n=str_pad($q-$r,4,0,0),"
",$n==6174?"Iterations: $d.":k($n,++$d);}k($argn);

```

Try it online!

Complete program, input is `STDIN`, run with `php -nF`.

**Output**

```
> echo 2607|php -nF kap.php
7620 - 0267 = 7353
7533 - 3357 = 4176
7641 - 1467 = 6174
Iterations: 3.

> echo 1211|php -nF kap.php
2111 - 1112 = 0999
9990 - 0999 = 8991
9981 - 1899 = 8082
8820 - 0288 = 8532
8532 - 2358 = 6174
Iterations: 5.

> echo 6174|php -nF kap.php
7641 - 1467 = 6174
Iterations: 1.

```
> 0 votes

# Answer
# Rust - 375 bytes

```
use std::io::{self,BufRead};fn main() {let mut x=io::stdin().lock().lines().next().unwrap().unwrap().parse::<i16>().unwrap();let mut n=0;println!("Iterations: {}.",loop {let mut v=[x/1000%10,x/100%10,x/10%10,x%10];v.sort();let j=v.iter().fold(0,|a,i|a*10+i);let k=v.iter().rev().fold(0,|a,i|a*10+i);x=k-j;n+=1;println!("{:04} - {:04} = {:04}",k,j,x);if x==6174{break n};});}

```

I present this as a possible "upper bound", I challenge anyone to find a language where a reasonable implementation of this is longer - as in there is nothing superfluous, but also nothing even remotely obvious that would shrink it significantly. The thing about Rust is that it takes about 120 characters just to read from stdin and parse into an integer. "Oh but then just use the string representation"... but im 99% confident that would be even longer
> 0 votes

# Answer
# Perl 6 -n flag, 105 bytes

```
say "Iterations: "~+.&{{{say $!=.flip~" - $_"," = ",($/=$!.EVAL.fmt("%04d"));$/}([~] .comb.sort)}...6174}

```

Try it online!

I finally got to use my `{}...*` trick, since we need to have at least one iteration for 6174. I'm not sure why I need the extra wrapping `.&{ }` around the sequence though, which kinda sucks.

### Explanation:

```
    .&{                         } # Call a function on the input
       {                }...6174  # Create a sequence that goes until 6174
        {           }([~] .comb.sort) # Get the sorted digits of the number
         say $!=.flip~" - $_"," = "~($/=$!.EVAL.fmt("%04d"))  # Print the iteration
                        ;$/  # Return the result
say "Iterations: "~+.&{      }     # Print the number of iterations

```
> 0 votes

---
Tags: code-golf, repeated-transformation, sequence
---


title: Matrix Jigsaw Puzzle Pieces

text:
# Question
Title: Matrix Jigsaw Puzzle Pieces
*(Randomly inspired by https://codegolf.meta.stackexchange.com/a/17272/42963)*

Given a rectangular matrix of digits (i.e., `0 - 9`), output the "pieces" of the matrix as if the digits are connected together forming a single piece, in ascending order by the digits. The pieces are guaranteed to connect only orthongonally -- no piece will connect diagonally. There will only ever be a maximum of 10 pieces (i.e., a `3` piece won't appear twice in the same matrix).

For example, given the matrix

```
0 1 1 1
0 0 1 2
3 3 2 2

```

the following are the pieces, and an example output:

```
0
0 0

1 1 1
  1

  2
2 2

3 3

```

Spacing is important to keep the shape of the pieces, but the pieces do not necessarily need interior spacing. The pieces themselves should somehow be made distinct in a consistent manner (e.g., a newline between pieces, making sure each is a different character, etc.). Additionally, extraneous whitespace (for example, trailing newlines or leading columns) are not allowed. For example, the following would also be valid:

```
0
00
111
 1
 2
22
33

```

or

```
#
##

###
 #

 #
##

##

```

But the following would not be (note the trailing spaces behind the `0`s):

```
0
0 0

```

Rotations or reflections are also not allowed. For example, outputting

```
 1
111

```

for the above matrix is also invalid.

The matrix pieces may have holes, or be only a single element:

```
0 0 0 1
0 2 0 1
0 0 0 3

```

Or, the piece may be the whole matrix:

```
0 0 0
0 0 0

```

Here's a larger, more complicated test case:

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

```

And an example output:

```
00

11111

 22
222
2

3

444
 44

55
5
5

6666
6  66
666

 77
  7
777

88

9

```

### Rules and I/O

* Input and output can be given by any convenient method.
* You can print it to STDOUT or return it as a function result.
* Either a full program or a function are acceptable.
* Leading whitespace to keep the shape (e.g., the "T" shape of the `1` in the example) is required, consistent whitespace to make the pieces distinct, and a single trailing newline at the end is allowed, but no other whitespace is permitted.
* You can safely assume that the pieces are numbered `0` to `N` contiguously, meaning that (for example) `3` wouldn't be skipped in a six-piece matrix.
* Standard loopholes are forbidden.
* This is so all usual golfing rules apply, and the shortest code (in bytes) wins.

# Answer
# Jelly, 18 bytes

```
ẎQṢ=€ẸƇZ$⁺œr€ɗ€0o⁶

```

Try it online!

Returns a list of pieces, where `1` represents a part of a piece, and `' '` is padding. Trailing `' '`s are removed.
> 2 votes

# Answer
# C# (.NET Core), ~~258~~, 238 bytes

Without LINQ.

EDIT: Embodiment Of Ignorance pointing out better var declarations! Ty ty.

```
p=>{int j=0,o=0,l=0,x=p.GetLength(1),d=p.Length;while(j<d){int t=j/x,u=j++%x,z=p[t,u];o=z>o?z:o;l=z<l?z:l;}var s="";for(var m=l;m<=o;m++){j=0;while(j<d){int t=j/x,u=j++%x;s+=(p[t,u]==m?p[t,u]+"":" ")+(u==x-1?"\n":"");}s+="\n";}return s;};

```

Try it online!
> 2 votes

# Answer
# 05AB1E, ~~20~~ 19 bytes

```
ZƒNQ2Fζʒà}}ε0Ü}0ð:,

```

-1 byte thanks to *@Mr.Xcoder*.

Outputs 2D lists of pieces (with `1` and space characters `" "`) per newline.

Try it online or verify all test cases or pretty-print all test cases.

**Explanation:**

```
Z              # Get the maximum digit of the (implicit) matrix-input (implicitly flattens)
 ƒ             # Loop in the range [0, max]:
  NQ           #  Check for each digit in the (implicit) matrix if it's equal to the index
    2F    }    #  Inner loop two times:
      ζ        #   Zip/transpose; swapping rows/columns
       ʒ }     #   Filter the inner lists by:
        à      #    Get the max of the list
               #  (so all rows/columns containing only 0s are removed)
  ε  }         #  Map the remaining rows:
   0Ü          #   Remove all trailing 0s
  0ð:          #  Then replace any remaining 0 with a space " "
     ,         #  And output the piece-matrix with a trailing newline

```
> 2 votes

# Answer
## Haskell, ~~133~~ ~~132~~ 129 bytes

```
f x=[until(any(>"!"))(tail<$>)m|m<-[[until((>'!').last)init r|r<-[[last$' ':[s|s==n]|s<-z]|z<-x],any(>'!')r]|n<-['0'..'9']],m>[]]

```

Takes the matrix as a list of strings and returns a list of list of strings.

Try it online!

```
                                    -- example matrix: ["0111","0012","3322"]
                                    --
[          |n<-[0..9]]              -- for each digit 'n' from '0' .. '9'
  [  |z<-x]                         --   for each line 'z' of the input matrix 'x'
   [      |s<-z]                    --     for each digit 's' of line 'z'
      last$' ':[s|s==n]             --       take 's' if 's'=='n', else a space
                                    --       now we have a list of 10 matrices where
                                    --       each matrix contains only the
                                    --       corresponding digit 'n' at it's original
                                    --       position and spaces for all other digits
                                    --       -> [["0   ","00  ","    "],[" 111","  1 ","    "],["    ","   2","  22"],["    ","    ","33  "],["    ","    ","    "],["    ","    ","    "],["    ","    ","    "],["    ","    ","    "],["    ","    ","    "],["    ","    ","    "]]
   [     |r<-[    ],any(>'!')r]     --     loop through rows 'r' and keep those with
                                    --     at least one non-space element
    until((>'!').last)init r        --     and remove trailing spaces
                                    --     -> [["0","00"],[" 111","  1"],["   2","  22"],["33"],[],[],[],[],[],[]]
   [     |m<-[   ],m>[]]            --   loop through matrices 'm' and keep only
                                    --   non-empty
    until(any(>"!"))(tail<$>)m      --   and remove common leading spaces
                                    --   -> [["0","00"],["111"," 1"],[" 2","22"],["33"]]

```
> 2 votes

# Answer
# Python 3, ~~271~~ ~~209~~ ~~206~~ ~~183~~ ~~176~~ ~~172~~ 191 bytes

```
lambda t:[[[*"".join(' #'[i==d]for i in r).rstrip()]for r in[w[min(r.index(d)for r in t if d in r):max(len(R)-R[::-1].index(d)for R in t if d in R)]for w in t if d in w]]for d in{*sum(t,[])}]

```

Try it online!

Edit: Some cleanup and -5 thanks to @Jonathan Frech.

Edit: ~~-3~~ -26 once again thanks to @Jonathan Frech.

Edit: -7 again thanks to @Jonathan Frech.

Edit: +19: As noted by @nimi previously output had incorrect format.

---

Input is matrix as list of lists:

```
Input =  [[0, 1, 1, 1],
          [0, 0, 1, 2],
          [3, 3, 2, 2]]

```

Output is list of matricies:

```
Output = [[['#'],
           ['#', '#']],
          [['#', '#', '#'],
           [' ', '#']],
          [[' ', '#'],
           ['#', '#']],
          [['#', '#']]],

```

---

Ungolfed:

```
O = ' '
X = '#'

def digits(t):
    return {d for r in t for d in r}

def rows_with_digit(table, digit):
    return [row for row in table if digit in row]

def table_with_digit(table, digit):
    subtable = rows_with_digit(table, digit)
    left_most_column = min([row.index(digit) for row in subtable])
    right_most_column = max([len(row) - row[::-1].index(digit) for row in subtable])
    return [row[left_most_column:right_most_column] for row in subtable]

def format_table(table, digit):
    return [[X if i==digit else O for i in row] for row in table]

def f(table):
    D = digits(table)
    R = []
    for d in D:
        digit_table = table_with_digit(table, d)
        R.append(format_table(digit_table, d))
    return R

```
> 2 votes

# Answer
# Python 2, ~~173~~ ~~172~~ 165 bytes

```
s=input()
for i in sorted(set(sum(s,[]))):R=[''.join([' ',i][c==i]for c in r)for r in s if i in r];print'\n'.join(t[min(r.find(i)for r in R):t.rfind(i)+1]for t in R)

```

Try it online!

-15 bytes from an observation by nimi.

In program form, takes as input a list of lists of single characters; outputs by printing the pieces found using their character.
> 2 votes

# Answer
# APL (Dyalog Unicode), 38 bytesSBCS

Anonymous tacit prefix function. Takes a numeric matrix as argument and returns a list of lists strings. Each list of strings represents a piece with space-separated `1`s. Leading and internal (but not trailing) spaces are spaces.

```
⊂{' +$'⎕R''↓⍕' '@~{⍉⍵⌿⍨∨/⍵}⍣2⊢⍺=⍵}¨∪∘,

```

Try it online!

`∪∘,` the unique elements of the ravel (flattened) matrix

`⊂{` for each of those as , call the following function with the entire matrix as :

`⍺=⍵` indicate where that piece's number is in the matrix

yield that (separates `2` from )

`{``}⍣2` apply the following function twice ( is the Boolean matrix):

`∨/` mask for rows with at least one `1` (lit. row-wise OR-reduction)

`⍵⌿⍨` use that to filter the rows

transpose (so we do this on the columns too, then transpose back)

`' '@~` replace with spaces at positions where not (i.e. where `0`)

format as character matrix

split into list of strings

`' +$'⎕R''` PCRE replace trailing spaces (any number of spaces followed by a line-end) with nothing
> 2 votes

# Answer
# Python 2, 291 bytes

```
import re
t=input()
a,b=t.split(),{c for c in t if' '<c}
for c in sorted((b,a)[int(max(a))==len(a)],key=int):s=re.sub(r'[^%s\s]'%c,' ',t).split('\n');print"\n".join(''.join(l[i]for i in sorted({i for l in s for i,j in enumerate(l)if j in c})if i<len(l)).rstrip()for l in s if l.strip())+'\n'

```

Try it online!

Expects a quote-delimited sting as input. A semi-ludicrous percentage of the code is dedicated to handling non-space-separated/non-space-padded input.

**Un-golfed Explanation:**

```
# built-in python regex handling.
import re
# get argument from STDIN
t=input()
# get elements which are whitespace separated, and all distinct non-whitespace characters
a,b=set(t.split()),{c for c in t if' '<c}
                # choose whichever set has the appropriate number of values based on its max element
                # for non-space separated inputs, this prevents values like '333' for 4-piece sets
                (b,a)[int(max(a))==len(a)]
# get elements in order by their integer value
# this will force the items to print in order, since sets are unordered
for c in sorted(..........................,key=int):
      # using regex substitute, replace any instance that DOESN'T match the current value or a whitespace with a space
      re.sub(r'[^%s\s]'%c,' ',t)
    # split replaced string into lines on line breaks
    s=...........................split('\n')
                # for each line in replaced input
                for l in s
                           # get the index and value of each item in line
                           for i,j in enumerate(l)
             # get distinct indexes which have a value that appears in the current piece
             {i ..................................if j in c}
    # get ordered list of distinct indexes
    a=sorted(...............................................)
                                                               # for each line in the replaced input
                                                               # only return values where line has non-whitespace values
                                                               for l in s if l.strip()
                           # get the value for each index that has a non-space value on other lines
                           # as long as that index exists (for non-space-padded inputs)
                           # this ensures that the spaces between values, if any, are removed
                           # there may still be trailing spaces
                           l[i]for i in a if i<len(l)
                   # join characters back into one string, and remove trailing whitespace
                   ''.join(..........................).rstrip()
    # join the lines back together with line breaks, and terminate with an extra line break
    # print output to screen
    print"\n".join(...................................................................)+'\n'

```
> 1 votes

# Answer
# Retina, 75 bytes

```
$
¶9
.-10{T`9d`d`.$
*;(s`(\d)(?!.*\1$)

 +¶
¶
G`\d
/^\d|^$/m^+m`^.

.$
$&¶

```

Try it online! Explanation:

```
$
¶9

```

Append a digit to the input. This represents the loop counter. The newline simplifies the trailing whitespace removal.

```
.-10{

```

Inhibit default output and repeat exactly 10 times.

```
T`9d`d`.$

```

Advance the loop digit.

```
*;(

```

Output the result of the rest of the script but then restore the buffer.

```
s`(\d)(?!.*\1$)

```

Replace all digits that don't match the loop digit with spaces. (Because this uses a lookahead and there's nothing to look ahead at this point this also replaces the loop digit.)

```
 +¶
¶

```

Remove all trailing whitespace.

```
G`\d

```

Remove all blank lines.

```
/^\d|^$/m^+

```

Repeat as long as no line begins with a digit...

```
m`^.

```

... delete the first character on each line.

```
.$
$&¶

```

If there is anything left then append a newline to separate each shape from the next. (This is done to avoid stray newlines for missing digits.)
> 1 votes

# Answer
# Charcoal, 43 bytes

```
ＷＳ⊞υιＦχ«≔Φυ№κＩιθ¿θ«ＵＴＦθ«Ｆκ«¿⁼λＩιλ→»Ｍ±Ｌκ¹»Ｄ⎚

```

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

```
ＷＳ⊞υι

```

Read the input into an array. (This could be removed if I used an ugly input format.)

```
Ｆχ«

```

Loop over the 10 digits.

```
≔Φυ№κＩιθ

```

Get the rows which contain those digits.

```
¿θ«

```

Check that the digit was in fact found (to prevent outputting spurious newlines).

```
ＵＴ

```

Turn off automatic padding.

```
Ｆθ«

```

Loop over the found rows.

```
Ｆκ«

```

Loop over each column...

```
¿⁼λＩιλ→»

```

... if the current input character equals the current loop digit then print it otherwise move the cursor right.

```
Ｍ±Ｌκ¹»

```

Move to the start of the next row. Using movement commands like this allows Charcoal to trim the output on both sides.

```
Ｄ⎚

```

Dump and clear the canvas ready for the next digit. This allows the different digits to have different amounts of trimming.

I tried a programmatic approach but that weighed in at 47 bytes, although it would also have been 43 bytes for a brief amount of time when `Equals` vectorised:

```
ＵＴＷＳ⊞υιＦχ«≔ΦＥυＥκ⁼μＩιΣκθＥθ⭆✂κ⌊Ｅθ⌕μ¹⁻Ｌκ⌕⮌κ¹¦¹⎇μι

```

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

```
ＵＴ

```

Turn off automatic padding.

```
ＷＳ⊞υι

```

Read the input into an array.

```
Ｆχ«

```

Loop over the 10 digits.

```
≔ΦＥυＥκ⁼μＩιΣκθ

```

Compare each character with the input and build up a boolean array, but then filter out the rows with no matches.

```
Ｅθ⭆✂κ⌊Ｅθ⌕μ¹⁻Ｌκ⌕⮌κ¹¦¹⎇μι

```

Loop over the remaining rows and slice from the earliest match in any row to the latest match in the current row, then mapping the boolean array back to digits or spaces, which are then implicitly printed as an array of strings.
> 1 votes

# Answer
# Wolfram Language 101 bytes

There has got to be a much more efficient way to accomplish this.

```
(g=#;Column[Table[Grid@Map[Replace[#,Thread[Complement[u=Union@Flatten@g,{n}]->""]]&/@#&,g],{n,u}]])&

```
> 1 votes

# Answer
# Perl 5, 97 bytes

```
$x=$_;for$i(0..9){$_=$x;y/ //d;s/(?!$i)./ /g;s/ *$//gm;s/^
//gm;s/^ //gm until/^(?! )/m;$\.=$_}}{

```

TIO

Explanation

```
-p0777                       # options to read whole intput and print special var by default

$x=$_;                       # save default var (input) into $x
for$i(0..9){                 # for $i in 0..9
    $_=$x;                   #   restore default var
    y/ //d;                  #   remove all space char
    s/(?!$i)./ /g;           #   replace all char except $i by a space
    s/ *$//gm;               #   remove trailing space
    s/^\n//gm;               #   remove empty lines
    s/^ //gm until/^(?! )/m; #   remove leading space until there is no more
    $\.=$_                   #   append default var to output record separator
}
}{                           # trick with -p to output only reacord separator

```
> 1 votes

# Answer
# Japt, 29 bytes

```
AÆ®®¥X ÑÃÃÕfx Õfx ®¬r0S x1
fl

```

Try it online!

Updated to comply with stricter output formatting.

Outputs as a list of pieces with each piece represented by a list of lines, using 2 as the filler character.

Explanation:

```
AÆ                            #For the numbers 0-9:
  ®®    ÃÃ                    # Map over each digit in the input:
    ¥X                        #  True if it equals the current number, false otherwise
       Ñ                      #  Multiply by 2 to turn the bool into a number
          Õfx                 # Remove columns that are all 0
              Õfx             # Remove rows that are all 0
                  ®           # For each remaining row:
                   ¬          #  Turn it into a string
                    r0S       #  Replace "0" with " "
                        x1    #  Trim spaces from the right
fl                            #Remove unused pieces

```
> 1 votes

# Answer
# Python 3, 133 bytes

```
lambda s:[dedent(re.sub(" *$","",re.sub(f"[^{c}\\n]"," ",s),0,8)).strip("\n")for c in sorted(*s)[1:]]
from textwrap import*
import re

```

Try it online!

Takes a newline-seperated string, returns a list of newline-seperated strings. Uses `textwrap.dedent` to get rid of leading spaces.
> 0 votes

# Answer
# Jelly, 19 bytes

```
ŒĠµŒṬZSƇ$⁺ị⁾# œr€⁶)

```

Try it online!

A monadic link taking the matrix as input and returning a list of one ragged list per piece. Footer displays this prettily, but I think output without that is consistent with rules of question.
> 0 votes

---
Tags: code-golf, matrix
---


title: A "Sorting" algorithm

text:
# Question
Title: A "Sorting" algorithm
There is a "sorting algorithm" sometimes called Stalin sort in which in order to sort a list you simply remove elements from the list until it is sorted in increasing order. For example the list

```
[1, 2, 4, 5, 3, 6, 6]

```

When "sorted" using Stalin sort becomes

```
[1, 2, 4, 5, 6, 6]

```

The three was removed because it was out of order.

Now obviously there are many ways to remove elements to sort a list. For example any list with less than two elements must be sorted so by just removing enough elements blindly we can always sort a list. Since this is the case we only care about the *longest* possible result from a Stalin sort.

Your task will be to take a list of positive integers and output the length of the longest sorted (increasing) list that can be arrived at by removing elements from the original list. That is find the length of the longest sorted (possibly non-contiguous) sub-list.

Sorted lists can have the same element more than once in a row. You do not need to support the empty list unless your program itself is empty.

# Scoring

Your answer will be scored by the length of its own longest possible Stalin sort. Programs will be interpreted as a sequence of bytes rather than characters, and their order will be the natural one that arises by interpreting the bytes as numbers. Lower scores are better.

# *This is not*

Here's a neat-o tool to help you score your answers.

# Test cases

```
[1, 2, 4, 5, 3, 6, 6] -> 6
[19, 2] -> 1
[3, 3, 4, 3] -> 3
[10] -> 1
[1, 2, 4, 9] -> 4
[1, 90, 2, 3, 4, 5] -> 5
[1, 90, 91, 2, 3, 4, 5] -> 5

```

# Answer
# Python 2, length ~~14~~ ~~12~~ ~~10~~ 9

```
M=max;X=exit;i=input();L=[0]*M(i)
for	a	in	i:L[a-1]=M(L[:a])+1
X(M(L))

```

Output is via exit code.

Try it online!

### How it works

At all times, the array \\$L\\$ keeps track of the longest sorted subarrays encountered so far; \\$L\[a-1\]\\$ is the length of longest one that ends with \\$a\\$.

Initially, we haven't processed an array elements, so \\$L\\$ consists entirely of zeroes.

When processing the array element \\$a\\$, we first take the maximum of \\$\[L\[0\], \dots, L\[a-1\]\]\\$, which is length of the longest sorted subarray encountered so far that ends with \\$a\\$ or a smaller integer. Appending \\$a\\$ to such an array will keep it sorted, so the longest sorted subarray ending in \\$a\\$ is one element longer than that maximum. We update \\$L\[a-1\]\\$ with the computed value.

The final result is the maximum of \\$L\\$.
> 7 votes

# Answer
# Wolfram Language (Mathematica), score 9

```
Length@*LongestOrderedSequence

```

Try it online!
> 6 votes

# Answer
# Jelly, length  ~~4~~  2

```
ṢƑƇZLƲ}ŒP

```

Try it online!

### Bytes in Jelly's code page

```
183 146 144 90 76 169 125 19 80

```

### How it works

```
ṢƑƇZLƲ}ŒP  Main link. Argument: A (array)

       ŒP  Powerset; yield P, the array of all sub-arrays of A.
     Ʋ     Vier; combine the preceding four links into a monadic chain...
      }    and apply the chain to the right argument (P).
  Ƈ            Comb; only keep arrays for which the link to the left returns 1.
ṢƑ             Sort fixed; yield 1 if sorting doesn't alter the array.
   Z           Zip; read the filtered powerset by columns.
    L          Take the length.

```
> 5 votes

# Answer
# Haskell, Score ~~8~~ 7, 48 bytes

```
(l:k)%d|d>l=k%d|3>2=max(1+k%l)(k%d)
c%b=0
a=(%0)

```

Try it online!

The longest sorted sublist is

```
%%%%%%)

```
> 4 votes

# Answer
# Perl 6, score 9

```
*.combinations.map({@^a*[<=] @a}).max

```

Try it online!
> 4 votes

# Answer
# Pyth, score ~~3~~ 2 (~~7~~ bytes)

```
leSI#y

```

Saved a point thanks to Anders Kaseorg.
Try it here

### Explanation

```
leSI#y
     yQ    Take the power set of the (implicit) input (preserving order).
  SI#      Get the ones that are sorted.
 e         Take the last (longest).
l          Get the length.

```
> 4 votes

# Answer
# Stax, 4 maximal length stalin sort

```
S{:^fF%|M

```

Run and debug it

It works like this.

```
S       powerset of input
{:^f    filter by non-descending sequences
F%|M    take the maximum length remaining

```
> 3 votes

# Answer
# Brachylog, length 2 (4 bytes)

```
⊇≤₁l

```

Try it online!

An answer which makes up for being so concise by not being that much shorter sorted.

(`08 03 80 6C` in Brachylog's code page)

```
        Output
   l    the length of
 ≤₁     a non-decreasing
⊇       sublist of
        the input.
        (maximizing the size of the sublist)

```
> 2 votes

# Answer
# , Score ~~15~~ 11, ~~72~~ 62 bytes

```
function(L,M=max,A=1:M(L)*0){for(Y in L)A[Y]=M(A[1:Y])+1;M(A)}

```

Try it online!

Ports Dennis' Python answer to R.
> 1 votes

---
Tags: code-challenge, sorting
---


# Question
Title: Tips for golfing in Turing Machine But Way Worse
What are some tips for golfing in Turing Machine But Way Worse, a language made by MilkyWay90 and ASCII-only?

Tips should be Turing Machine But Way Worse-specific and not be trivial (For examples that you shouldn't post, removing unnecessary whitespace or using shorter state names).

EDIT: Added documentation to TMBWW

# Answer
> 2 votes
# Use the negative tape

For code-golf questions where you need to process input, it is easier to move onto the negative tape to push a bit to the tape instead of having to travel to the end of the input on the positive tape (and sometimes that way may even be impossible when you need to support NUL bytes).

For example, when you need to push  to the tape and you have input, going on the negative tape would be much shorter than having to go to the end of the input.

```
0 0 0 0 1 0 0
1 0 1 0 1 0 0
0 1 0 0 2 1 1

```

would be much shorter than

```
0 0 0 1 1 0 0
1 0 1 1 0 0 0
0 1 0 1 2 0 0
1 1 1 1 0 0 0
0 2 0 1 3 0 0
1 2 1 1 0 0 0
0 3 0 1 4 0 0
1 3 1 1 0 0 0
0 4 0 1 5 0 0
1 4 1 1 0 0 0
0 5 0 1 6 0 0
1 5 1 1 0 0 0
0 6 0 1 7 0 0
1 6 1 1 0 0 0
0 7 0 1 8 0 0
1 7 1 1 0 0 0
0 8 0 0 9 0 0
0 9 1 0 a 1 1

```

and the second solution doesn't even work with NUL bytes.

---
Tags: tips
---


title: Draw these shapes

text:
# Question
Title: Draw these shapes
Given: a width, a height, and a set of sets of points. Output: An image where each set of points is connected and colored in (like a shape). Each shape *must* be a different color from all of the other shapes, but **the actual color doesn't matter as long as each color is distinct**. The shapes must be in order; whether you start at the end or the beginning of the set doesn't matter, though. **The dots must be connected in the order they're given in the set.**

Output formats are in accordance with standard image rules.

## Examples

```
//the code here has nothing to do with the actual challenge and just shows examples

document.getElementById("one").getContext("2d").fillRect(0, 0, 300, 300)
const ctx = document.getElementById("two").getContext("2d")
ctx.fillStyle = "black"
ctx.beginPath();ctx.moveTo(0,0);ctx.lineTo(0,300);ctx.lineTo(300,0);ctx.closePath();ctx.fill()
ctx.fillStyle = "lime"
ctx.beginPath();ctx.moveTo(200,0);ctx.lineTo(600,0);ctx.lineTo(300,300);ctx.closePath();ctx.fill()
```

```
canvas {border: 1px dotted black}
```

```
<pre>Width: 500, Height: 500, Set: [[[0, 0], [0, 300], [300, 300], [300, 0]]]</pre>
<canvas id="one" width="500" height="500"></canvas>

<pre>Width: 600, Height: 300, Set:
[
  [[0,0], [0,300], [300,0]],
  [[200,0], [600,0], [300,300]]
]</pre>
<canvas id="two" width="600" height="300"></canvas>
```

Scoring is .

# Answer
# , ~~122~~ 71 bytes

```
function(w,h,p){plot.new();plot.window(c(0,w),c(0,h));polygon(p,c=1:8)}

```

Try it online!

RDRR - actually shows graphics

A function that takes arguments width, height and a matrix of points detailing the shapes. Each shape is separated by a row of NAs. Output is a plot to the screen of the shapes.
> 2 votes

---
Tags: code-golf, image-processing
---