title: Play flip--flop

text:
# Question
Title: Play flip--flop
Flip flop is a memory / arithmetic game that I played in high school. Some number of players stand in a circle. The players take turns. On the `n`th turn, the current player checks:

1. What is the largest power of 7 dividing n?
2. How many instances of the digit 7 does the decimal representation of n contain?
3. What is the largest power of 8 dividing n?
4. How many instances of the digit 8 does the decimal representation of n contain?

Let `FLIPS(n)` be the sum of the power of 7 dividing `n` and the number of `7`'s n contains. For example, `FLIPS(7)=2` (divisible by 7 once, contains one 7), `FLIPS(14) = 1` (divisible by 7 once, contains zero 7's), `FLIPS(17)=1` (not divisible by 7, contains one 7).

Let `FLOPS(n)` be the sum of the power of 8 dividing `n` and the number of `8`'s `n` contains.

On a player's turn, if `FLIPS(n)=FLOPS(n)=0` they say `n`. Otherwise, they first say "flip" `FLIPS(n)` times and then say "flop" `FLOPS(n)` times.

If `FLIPS(n)` is odd, the direction of play swaps (from counterclockwise to clockwise or from clockwise to counterclockwise). The next `FLOPS(n)` players in the new play order are skipped.

## Task

Write a program that takes a pair of integers `(num_players, turns)` and plays Flipflop with a group of `num_players` players for `turns` turns. Output should be a list of the `current_player` on the nth turn. The players are numbered 1 through num\_players. The player to the left of player 1 is player num\_players. (If it's more convenient to label the players `0` to `num_players - 1`, that is fine too.) Play begins with player 1 in counterclockwise order.

## Example:

I'll give an example with 5 players. For the first 6 turns nothing interesting happens:

1. Player 1 says "1" (CCW)
2. Player 2 says "2" (CCW)

...

5. Player 5 says "5" (CCW)
6. Player 1 says "6" (CCW)
7. Player 2 says "flipflip" (still CCW `FLIPS(7)=2` is even)
8. Player 3 says "flopflop" (CCW, skip players 4 and 5)
9. Player 1 says "9" (CCW)

...

14. Player 1 says "flip" (now CW play order)
15. Player 5 says "15" (CW)
16. Player 4 says "flop" (CW)
17. Player 2 says "flip" (now CCW)
18. Player 3 says "flop" (CCW)
19. Player 5 says "19" (CCW)

The 70's and 80's have a lot of activity. When trying to actually play this game, it is hard to remember where in this 20 digit sequence you are (though 700 / 800 is much worse).

69. Player 4 says "69" (CW)
70. Player 3 says "flipflip" (still CW)
71. Player 2 says "flip" (CCW)
72. Player 3 says "flipflop" (CW)
73. Player 1 says "flip" (CCW)
74. Player 2 says "flip" (CW)
75. Player 1 says "flip" (CCW)
76. Player 2 says "flip" (CW)
77. Player 1 says "flipflipflip"(CCW)
78. Player 2 says "flipflop" (CW)
79. Player 5 says "flip" (CCW)
80. Player 1 says "flopflop" (CCW)
81. Player 4 says "flop" (CCW)
82. Player 1 says "flop" (CCW)
83. Player 3 says "flop" (CCW)
84. Player 5 says "flipflop" (CW)
85. Player 3 says "flop" (CW)
86. Player 1 says "flop" (CW)
87. Player 4 says "flipflop" (CCW)
88. Player 1 says "flopflopflop"(CCW)
89. Player 5 says "flop" (CCW)
90. Player 2 says "90" (CCW)

## Scoring

This is code golf, so shortest answer in bytes wins.

## Test Cases:

```
[2,100] => {1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,2,1,1,2,1,2,1,2,2,1,2,1,1,2,1,2,2,1,2,1,2,1,1,2,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,1,2,2,1,2,1,2,1,2,1,2,1,1,2,1,2,2,1,2,1,2,1,1,2,1,1,1,1,1,1,1,1,1,1,2,1,2,1,2,1,1,2,2,1}
[3,100] => {1,2,3,1,2,3,1,2,2,3,1,2,3,1,3,2,3,1,3,1,2,1,3,2,3,2,1,2,3,2,1,3,1,3,2,3,1,3,1,3,1,3,1,2,3,1,2,1,1,3,2,1,3,2,1,3,2,1,2,1,3,2,1,2,2,3,1,3,1,3,2,3,1,2,1,2,1,2,3,1,1,3,2,1,2,3,1,3,1,3,1,3,2,1,3,2,3,1,3,1}
[4,100] => {1,2,3,4,1,2,3,4,3,4,1,2,3,4,3,2,4,1,3,4,1,4,3,2,4,3,2,3,1,4,3,2,4,3,2,3,4,3,1,4,2,1,2,3,4,1,2,1,2,1,4,3,2,1,4,3,1,4,2,1,4,3,2,3,2,3,4,3,1,4,3,4,2,3,2,3,2,3,1,2,1,3,1,3,1,3,1,3,3,1,2,1,4,3,2,1,3,4,2,3}
[5,100] => {1,2,3,4,5,1,2,3,1,2,3,4,5,1,5,4,2,3,5,1,2,1,5,4,2,1,5,1,4,3,2,1,4,3,2,3,4,3,1,5,3,2,3,4,5,1,2,1,3,2,1,5,4,3,2,1,3,2,5,4,3,2,1,2,5,1,2,1,4,3,2,3,1,2,1,2,1,2,5,1,4,1,3,5,3,1,4,1,5,2,3,2,1,5,4,3,1,2,4,5}
[6,100] => {1,2,3,4,5,6,1,2,5,6,1,2,3,4,3,2,6,1,3,4,5,4,3,2,6,5,4,5,3,2,1,6,4,3,2,3,4,3,1,6,4,3,4,5,6,1,2,1,4,3,2,1,6,5,4,3,5,4,2,1,6,5,4,5,2,3,4,3,1,6,5,6,4,5,4,5,4,5,3,4,1,3,5,1,5,3,1,3,1,3,4,3,2,1,6,5,3,4,6,1}
[7,100] => {1,2,3,4,5,6,7,1,4,5,6,7,1,2,1,7,5,6,1,2,3,2,1,7,5,4,3,4,2,1,7,6,4,3,2,3,4,3,1,7,5,4,5,6,7,1,2,1,5,4,3,2,1,7,6,5,7,6,4,3,2,1,7,1,4,5,6,5,3,2,1,2,7,1,7,1,7,1,6,7,3,5,7,2,7,5,3,5,2,4,5,4,3,2,1,7,5,6,1,2}

```

## A picture

I had 100 players play the game for \\$200^2\\$ steps, made it into a 200 by 200 square and colored the squares by hue. Made with Mathematica.

# Answer
> 5 votes
# Jelly, ~~35~~ 22 bytes

```
Dċ¥+ọɗþ7,8Ä-*Ɗ‘ƭ€P1;Ä%

```

Try it online!

A dyadic link that takes the number of turns as the left argument and number of players as the right. Players and numbered from 0 to *number of players - 1* and play starts with player 1. Currently returns the start player and the current player after each turn (so 101 players in total); this could easily be changed to omit the final one at the cost of a byte.

As a bonus, here's a version that prints the player and what they say.

## Explanation

```
     ɗþ7,8              | Outer table using the following as a dyad and [7,8] as the rught argument (and 1..number of turbs as left argument)
  ¥                     | - Following as a dyad
D                       |   - Convert to decimal digits
 ċ                      |   - Count (right argument)
   +                    | - Add to
    ọ                   |   - Order (power of right argument that exactly divides left argument)
             ƭ€         | Alternate between the following:
           Ɗ            | - For first list (flips), following as a monad:
        Ä               |   - Cumulative sum
         -*             |   - -1 to the power of this
            ‘           | - For second list (flops) add 1
                 P      | Product (flips × flops)
                  1;    | Prepend 1
                    Ä   | Cumulative sum
                     %  | Modulo number of players

```

# Answer
> 2 votes
# JavaScript (ES6),  ~~121 117~~  115 bytes

Takes input as `(players)(turns)`. The output is 0-indexed.

```
P=>T=>(F=p=>++t>T?[]:[p%P,...F(p+(g=(x,n=t)=>n%x?(t+g).split(x).length:1+g(x,n/x))(8)*(d*=g(7)&1||-1)+P)])(t=0,d=1)

```

Try it online! (raw output)

Try it online! (post-processing for 1-indexed output)

### Commented

```
P => T => (                   // P = number of players, T = number of turns
  F = p =>                    // F = recursive function taking the current player ID p
    ++t > T ?                 // increment the turn ID; if it's greater than T:
      []                      //   stop recursion
    :                         // else:
      [                       //   update the output array:
        p % P,                //     append the current player ID
        ...F(                 //     append the result of a recursive call:
          p + (               //       update p ...
            g = (x,           //         g is a helper function taking x = 7 or 8
                    n = t) => //         and a counter n initialized to t
              n % x ?         //         if x is not a divisor of n:
                (t + g)       //           coerce t to a string
                .split(x)     //           and count the number of occurrences of x
                .length       //           plus 1
              :               //         else:
                1 +           //           increment the result
                g(x, n / x)   //           recursive call with n / x
          )(8) * (            //       invoke g(8) = FLOPS(t) + 1
            d *= g(7) & 1     //         leave d unchanged if g(7) = FLIPS(t) + 1 is odd
                 || -1        //         otherwise, update d to -d
          ) + P               //       make sure that p remains positive
        )                     //     end of recursive call
      ]                       //   end of output update
)(t = 0, d = 1)               // initial call to F with p = t = 0 and d = 1

```

# Answer
> 2 votes
# Python 2, 143 bytes

```
def f(P,m):r=[];p=0;d=i=1;exec"r+=[p%P];d*=g(i,7)%2*2-1;p+=d*g(i,8);i+=1;"*m;return r
g=lambda n,b,k=1:n%b**k<1and g(n,b,k+1)or`n`.count(`b`)+k

```

Try it online!

Input in `P` number of players, `m` rounds. Output is 0 indexed.

The function `g(n,b)` returns `flips(n)+1` or `flops(n)+1` with `b=7,8`, respectively. That `+1` saves a byte or three...

# Answer
> 2 votes
# Charcoal, 64 bytes

```
Ｎθ≔⁰ε≔¹δＦＮ«⟦Ｉ﹪εθ⟧≦⊕ιＦ⁺№Ｉι7№Ｅ↨ι⁷﹪ιＸ⁷⊕λ⁰≦±δ≧⁺×δ⊕⁺№Ｉι8№Ｅ↨ι⁸﹪ιＸ⁸⊕λ⁰ε

```

Try it online! Link is to verbose version of code. Players are 0-indexed. Explanation:

```
Ｎθ

```

Input the number of players.

```
≔⁰ε

```

Set the current player to player 0.

```
≔¹δ

```

Set the initial direction of play.

```
ＦＮ«

```

Loop for the given number of turns.

```
⟦Ｉ﹪εθ⟧

```

Output the current player.

```
≦⊕ι

```

1-index the current turn.

```
Ｆ⁺№Ｉι7№Ｅ↨ι⁷﹪ιＸ⁷⊕λ⁰

```

Count the number of flips.

```
≦±δ

```

Reverse the direction of play for each flip.

```
≧⁺×δ⊕⁺№Ｉι8№Ｅ↨ι⁸﹪ιＸ⁸⊕λ⁰ε

```

Calculate the next player to play.

Bonus 91-byte version outputs what each player says too:

```
Ｎθ≔⁰ε≔¹δＦＮ«≦⊕ι≔⁺№Ｉι7№Ｅ↨ι⁷﹪ιＸ⁷⊕λ⁰η≔⁺№Ｉι8№Ｅ↨ι⁸﹪ιＸ⁸⊕λ⁰ζ⟦⪫⟦⊕﹪εθ∨⁺×flipη×flopζι⟧:⟧≧×Ｘ±¹ηδ≧⁺×δ⊕ζε

```

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

# Answer
> 1 votes
# Vyxal, 26 bytes

```
ƛ78fMƛ÷₍ǑO∑;;∩÷›u„¦e*¦Ȯ%0p

```

Try it Online!

Pretty much a port of Nick Kennedy's Jelly answer. First argument `turns-1`, second argument `num_players`, players are zero-indexed.

## How?

```
                           #                 e.g. stack (top ->)
ƛ78fMƛ÷₍ǑO∑;;∩÷›u„¦e*¦Ȯ%0p #                      100
ƛ                          # for i = 1..turns     77
 78f                       #   push, split        77 [7,8]
    M                      #   pair               [77,7] [77,8]
     ƛ                     #   for [i,7] [i,8]    [77,7]
      ÷                    #     split            77 7
       ₍                   #     parallel apply
        Ǒ                  #       multiplicity   1
         O                 #       count          2
                           #     end              [1,2]
          ∑                #     sum              3
           ;               #   end                [3,0]
            ;              # end                  [[0,0],[0,0],[0,0],...]
             ∩             # transpose            [[0,0,0,...],[0,0,0,...]]
              ÷            # split                [0,0,0,...] [0,0,0,...]
               ›           # increment            [0,0,0,...] [1,1,1,...]
                u          # push -1              [0,0,0,...] [1,1,1,...] -1
                 „         # rotate left          [1,1,1,...] -1 [0,0,0,...]
                  ¦        # prefix sum           [1,1,1,...] -1 [0,0,0,...]
                   e       # exponent             [1,1,1,...] [1,1,1,...]
                    *      # multiply             [1,1,1,...]
                     ¦     # prefix sum           [1,2,3,...]
                      Ȯ    # over                 [1,2,3,...] 3
                       %   # modulo               [1,2,0,...]
                        0p # prepend 0            [0,1,2,...]

```

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


title: Unique rainbow programs

text:
# Question
Title: Unique rainbow programs
Given a list of positive integers as input you are to determine if there is a way to pair up the elements such that:

* All but one element is in a pair
* No element is in more than one pair
* Every pair is of equal elements
* No two pairs have elements separated by the same distance in the original list

For example if the input is:

```
[2,2,1,2,3,3,1]

```

Then we can choose the following pairs:

```
[2,2,1,2,3,3,1] <- Input
  [2,  2]       % Separated by 2
    [1,      1] % Separated by 4
        [3,3]   % Separated by 1

```

The first `2` is the element which is not in a pair.

**Very importantly**, when you take the list of code points of your program it must satisfy the property. Answers which do not are invalid.

This is the goal is to minimize the size of your source code as measured in bytes while satisfying the constraints.

To decide, your program should output one of two fixed values. The first if the solution there is a pairing of the input list as described and the second of the two values if there is not.

# Test cases

### Pairing possible

```
[1]
[1,1,1]
[1,1,1,1,1]
[2,2,1,1,1]
[2,2,1,2,1]
[2,2,1,2,3,3,1]
[2,2,2,1,2,3,3]

```

### Pairing not possible

```
[]
[1,1]
[1,2,3]
[1,1,1,1]
[2,2,1,2,3]
[2,2,1,3,3]
[1,1,1,1,1,1]
[2,2,2,2,1,3,3]

```

# Answer
> 4 votes
# , 151 bytes

```
(1=1#.2|1#.=)*.1 e.[:(~.@;-:;)&>@,@{<@(i.@!@#<@(2|@-/\]}.~2|#)@A.])@I.@=NB. .BN=@.I@)].A@)#|2~.}]\/-@|2(@<#@!@.i(@<{@,@>&);:-;@.~(:[.e 1.*)=.#1|2.#1=1(

```

Try it online!

What the hell, I'll kick things off with this grotesquerie of brute force. Looking forward to seeing more clever solutions....

# Answer
> 2 votes
# Pyth, ~~67~~ 63 bytes

```
&ff&{IaMY!fnF@LQZYcR2.PTlT-LUQUQ%lQ2 " 2%UU-TTP.2RcYZ@Fnf!YMaI{

```

Try it online! -- Truthy test suite -- Falsey test suite

(Outputs `1` for true and `[]` for false)

---

The `"` near the middle of the program is the unpaired character. Everything after it is part of a string literal.

Most characters in the main program have a twin in the string literal. Below are the exceptions:

| Character | Index A | Index B | Distance |
| --- | --- | --- | --- |
| `&` | 0 | 3 | 3 |
| `f` | 1 | 2 | 1 |
| `L` | 14 | 27 | 13 |
| `Q` | 15 | 31 | 16 |
| `l` | 24 | 33 | 9 |
| `Q` | 29 | 34 | 5 |

### Explanation

`-LUQUQ` \- Build a list of lists of indexes, each list containing all but one index of the input

`f ... cR2.PTlT` \- for each list, generate all permutations, and split into chunks of size 2

`f ... !fnF@LQZY` \- for each permutation, check whether the indexes of each pair correspond to equal elements of the input...

`&{IaMY` \- ... and that the differences between each pair is unique

If no permutation for any list of indexes satisfies those conditions, the `&` short-circuits and `[]` is returned. Otherwise...

`%lQ2` \- ...return the length of the input mod 2

# Answer
> 2 votes
# 05AB1E, 43 bytes

```
ā<œ.Δ¨2ôDÆÄDÙQiè€ËP]gÉqÉg]PË€èiQÙÄÆô2¨Δ.œ<ā

```

Try it online.

The base program is 22 bytes: `ā<œ.Δ¨2ôDÆÄDÙQiè€ËP]gÉ` \- try it online or verify all test cases.
(Although could be 21 bytes if just truthy/falsey would have been allowed instead of two consistent values, where the truthy results are still `1`, but the falsey results would be either `""` or `0`.)

Unfortunately, it only contains `D` as duplicated used character, and everything else is unique. So we'll just add a trailing `q` (the unique character) and the reversed program minus the two `D`s.

**Explanation:**

```
ā                    # Push a list in the range [1, (implicit) input-length]
 <                   # Decrease each by 1 to the range [0,length)
  œ                  # Get all permutations of this list
   .Δ                # Get the first list that's truthy for (or -1 if none are):
     ¨               #  Remove the last index
      2ô             #  Split all other indices into pairs
        D            #  Duplicate this list
         Æ           #  Reduce each inner pair by subtracting
          Ä          #  And then taking their absolute values
           DÙQi      #  If this list of absolute differences is unique:
           D         #    Duplicate
            Ù        #    Uniquify
             Q       #    Check if both lists are still the same
              i      #    Pop, and if this is truthy:
               è     #   Index the pairs into the (implicit) input-list
                €Ë   #   Check if for each pair of values if they're the same
                  P  #   Check if this is truthy for all of them
    ]                # Close the if-statement and find_first-loop
     g               # Pop and push the length (2 for the -1 results)
      É              # Check if this length is odd
       q             # Stop the program, making everything after it no-ops
                     # (and implicitly output the result)
Ég]PË€èiQÙÄÆô2¨Δ.œ<ā # No-ops

```

---
Tags: code-golf, decision-problem, self-validating
---


title: Build a Digital Plotter

text:
# Question
Title: Build a Digital Plotter
*Problem adapted from the book **Fortran 77 by Donald M. Monro***

## Introduction

Digital plotting machines are widely used to produce various forms of drawings, graphs and other pictorial results. Most such machines can move their pens only in certain directions, usually as single steps in the X and Y direction or both. A typical machine would move in one of the eight directions shown in Fig. 1:

Fig. 1

## Challenge

Write a program *without trigonometric functions* which takes a number from 0 to 7 (inclusive) as input and outputs the corresponding coordinates of the endpoints in Fig. 1.

Output should as an array or list with two elements (i.e. `(1, 0)` or `[0,-1]`)

## Table of I/O

```
0 (1, 0)
1 (1, 1)
2 (0, 1)
3 (-1, 1)
4 (-1, 0)
5 (-1, -1)
6 (0, -1)
7 (1, -1)

```

## Winning

Shortest code in bytes wins

# Answer
# Jelly, 8 bytes

```
Hı*µḞ,ĊṠ

```

Using complex arithmetic appears to be allowed.

Try it online!

### How it works

```
Hı*µḞ,ĊṠ  Main link. Argument: n

H         Halve; yield n/2.
 ı*       Yield i^(n/2), where i is the imaginary unit. Since i = e^(iπ/2), this
          computes e^(inπ/4) = cos(nπ/4) + i×sin(nπ/4) = x + iy, where (x, y) is
          the coordinate pair of (nπ/4)/(2π) = n/8 turns along the unit circle.
   µ      Begin a new chain with argument z = x + iy.
    Ḟ     Real part of z; yield x.
      Ċ   Imaginary part of z; yield y.
     ,    Pair, yielding (x, y).
       Ṡ  Apply the sign function to x and y.

```
> 6 votes

# Answer
# Python 2, 29 bytes

```
lambda n:1j**(n/2)*(1+n%2*1j)

```

Returns the coordinates as a complex number.
> 15 votes

# Answer
# Mathematica, 24 bytes

```
Sign@{12-8#+#^2,4#-#^2}&

```

Pure function, using `Sign` and knowing where certain parabolas go.
> 7 votes

# Answer
# C, ~~103~~ ~~86~~ ~~74~~ ~~73~~ 70 bytes

*Thanks to @orlp for saving ~~12~~ 15 bytes!*

```
f(n){n="biM1*#?["[n]/7;printf("%c%d %d",n&8?32:45,n/4&1,n%2*~-(n&2));}

```

Try it online!
> 6 votes

# Answer
# Desmos, 33 bytes

```
f(n)=mod(floor([4,2]^55/3^n),3)-1

```

Try it on Desmos!

The coordinate is returned as a 2 element list.
> 5 votes

# Answer
## JavaScript (ES6), ~~41~~ 36 bytes

```
r=>[1-(6800>>r*2&3),(425>>r*2&3)-1]

```

Uses two simple lookup tables which encode the 8 entries in base 4 after adding one to each "digit". Alternate version, using simpler lookup tables:

```
r=>["22100012"[r]-1,"12221000"[r]-1]

```

---

Old version (4 bytes shorter thanks to @Neil):

```
r=>[r>2&r<6?-1:r<2|r>6,r>4?-1:r%4&&1]

```

Naive approach using some simple calculations to find the X and Y coordinates separately...
> 4 votes

# Answer
# APL, 21 bytes

```
{×¯4 4+1 ¯1×2*⍨⍵-4 2}

```
> 4 votes

# Answer
# TI-Basic, 23 bytes

```
Prompt X
e^(i(pi)X/4
round({real(Ans),imag(Ans)},0

```

Assumes your calculator is in radian mode; if that needs to be in the program, then it's 25 bytes.
> 3 votes

# Answer
# Jelly, ~~13~~ 12 bytes

*I am still fairly confident there is shorter, but I have not found anything yet, so thought I'd post this*

```
+2,ị6400b3¤’

```

**Try it online!** or see a test suite

### How?

```
+2,ị6400b3¤’ - Main link: n                        e.g. 7
+2           - n+2                                      9
  ,          - paired with n: [n+2,n]                   [9,7]
          ¤  - nilad followed by link(s) as a nilad      9th         7th
    6400     -     6400                                  v           v
        b3   -     to base 3: [2,2,2,1,0,0,0,1]         [2,2,2,1,0,0,0,1]
   ị         - index into (1-indexed and modular)       [2,0]
           ’ - decrement (vectorises)                   [1,-1]

```

---

An alternative method, also **12 bytes**:

```
_/,+/Ṡ  - Link 1: get next coordinate: current coordinate (list) e.g. [-1,-1]
_/      - reduce by subtraction                                       0
   +/   - reduce by addition                                         -2
  ,     - pair                                                        [0,-2]
     Ṡ  - sign (vectorises)                                           [0,-1]

2BÇ⁸¡ - Main link: n
2B    - 2 in binary: [1,0]
    ¡ - repeat
   ⁸  - left argument (n) times:
  Ç   -     last link (1) as a monad

```
> 2 votes

# Answer
# C, 66 bytes

```
f(n){printf("%d %d\n",(n-2)%4?n>2&n<6?-1:1:0,(n-4)%4?n>4?-1:1:0);}

```

test code

```
main(i)
{for(i=0;i<8;++i) f(i);}

```

results

```
1 0
1 1
0 1
-1 1
-1 0
-1 -1
0 -1
1 -1

```
> 1 votes

# Answer
# JavaScript (Node.js), 34 bytes

```
e=>[434,5].map(n=>(85*n>>2*e&3)-1)

```

Try it online!
> 1 votes

# Answer
## C, 56 bytes

```
d(n){printf("%d,%d",n+2&3?n+2&4?-1:1:0,n&3?n&4?-1:1:0);}

```

Simple binary search done twice. The first search is done on n shifted by 2.

Online output on Ideone.

## C, 53 bytes

```
r;p(n){r?0:p(r=n+2);r=!printf("%d ",n&3?n&4?-1:1:0);}

```

Output without a comma was able to be compacted even more using a recursive call.

Online output on Ideone.
> 0 votes

---
Tags: code-golf
---


title: The Hungry Mouse

text:
# Question
Title: The Hungry Mouse
Sixteen piles of cheese are put on a 4x4 square. They're labeled from \\$1\\$ to \\$16\\$. The smallest pile is \\$1\\$ and the biggest one is \\$16\\$.

The Hungry Mouse is so hungry that it always goes straight to the biggest pile (i.e. \\$16\\$) and eats it right away.

After that, it goes to the biggest neighboring pile and quickly eats that one as well. (Yeah ... It's *really* hungry.) And so on until there's no neighboring pile anymore.

A pile may have up to 8 neighbors (horizontally, vertically and diagonally). There's no wrap-around.

## Example

We start with the following piles of cheese:

$$\begin{matrix} 3&7&10&5\\ 6&8&12&13\\ 15&9&11&4\\ 14&1&16&2 \end{matrix}$$

The Hungry Mouse first eats \\$16\\$, and then its biggest neighbor pile, which is \\$11\\$.

$$\begin{matrix} 3&7&10&5\\ 6&8&12&13\\ 15&9&&4\\ 14&1&\color{grey}\uparrow&2 \end{matrix}$$

Its next moves are \\$13\\$, \\$12\\$, \\$10\\$, \\$8\\$, \\$15\\$, \\$14\\$, \\$9\\$, \\$6\\$, \\$7\\$ and \\$3\\$ in this exact order.

$$\begin{matrix} &\color{grey}\leftarrow&\small\color{grey}\swarrow&5\\ \small\color{grey}\nearrow&\small\color{grey}\swarrow&\color{grey}\uparrow&\color{grey}\leftarrow\\ \color{grey}\downarrow&\small\color{grey}\nwarrow&\small\color{grey}\nearrow&4\\ \small\color{grey}\nearrow&1&\color{grey}\uparrow&2 \end{matrix}$$

There's no cheese anymore around the Hungry Mouse, so it stops there.

## The challenge

Given the initial cheese configuration, your code must print or return the sum of the remaining piles once the Hungry Mouse has stopped eating them.

For the above example, the expected answer is \\$12\\$.

## Rules

* Because the size of the input matrix is fixed, you may take it as either a 2D array or a one-dimensional array.
* Each value from \\$1\\$ to \\$16\\$ is guaranteed to appear exactly once.
* This is .

## Test cases

```
[ [ 4,  3,  2,  1], [ 5,  6,  7,  8], [12, 11, 10,  9], [13, 14, 15, 16] ] --> 0
[ [ 8,  1,  9, 14], [11,  6,  5, 16], [13, 15,  2,  7], [10,  3, 12,  4] ] --> 0
[ [ 1,  2,  3,  4], [ 5,  6,  7,  8], [ 9, 10, 11, 12], [13, 14, 15, 16] ] --> 1
[ [10, 15, 14, 11], [ 9,  3,  1,  7], [13,  5, 12,  6], [ 2,  8,  4, 16] ] --> 3
[ [ 3,  7, 10,  5], [ 6,  8, 12, 13], [15,  9, 11,  4], [14,  1, 16,  2] ] --> 12
[ [ 8,  9,  3,  6], [13, 11,  7, 15], [12, 10, 16,  2], [ 4, 14,  1,  5] ] --> 34
[ [ 8, 11, 12,  9], [14,  5, 10, 16], [ 7,  3,  1,  6], [13,  4,  2, 15] ] --> 51
[ [13, 14,  1,  2], [16, 15,  3,  4], [ 5,  6,  7,  8], [ 9, 10, 11, 12] ] --> 78
[ [ 9, 10, 11, 12], [ 1,  2,  4, 13], [ 7,  8,  5, 14], [ 3, 16,  6, 15] ] --> 102
[ [ 9, 10, 11, 12], [ 1,  2,  7, 13], [ 6, 16,  4, 14], [ 3,  8,  5, 15] ] --> 103

```

# Answer
> 11 votes
# Python 2, ~~133~~ 130 bytes

```
a=input();m=16
for i in range(m):a[i*5:i*5]=0,
while m:i=a.index(m);a[i]=0;m=max(a[i+x]for x in[-6,-5,-4,-1,1,4,5,6])
print sum(a)

```

Try it online!

Takes a flattened list of 16 elements.

### How it works

```
a=input();m=16

# Add zero padding on each row, and enough zeroes at the end to avoid index error
for i in range(m):a[i*5:i*5]=0,

# m == maximum element found in last iteration
# i == index of last eaten element
# eaten elements of `a` are reset to 0
while m:i=a.index(m);a[i]=0;m=max(a[i+x]for x in[-6,-5,-4,-1,1,4,5,6])
print sum(a)

```

# Answer
> 8 votes
# MATL, ~~50~~ ~~49~~ 47 bytes

```
16:HZ^!"2G@m1ZIm~]v16eXK68E16b"Ky0)Y)fyX-X>h]s-

```

Input is a matrix, using `;` as row separator.

Try it online! Or verify all test cases.

### Explanation

```
16:HZ^!  % Cartesian power of [1 2 ... 16] with exponent 2, transpose. Gives a
         % 2-row matrix with 1st column [1; 1], 2nd [1; 2], ..., last [16; 16]
"        % For each column, say [k; j]
  2      %   Push 2
  G@m    %   Push input matrix, then current column [k; j], then check membership.
         %   This gives a 4×4 matrix that contains 1 for entries of the input that
         %   contain k or j
  1ZI    %   Connected components (based on 8-neighbourhood) of nonzero entries.
         %   This gives a 4×4 matrix with each connected component labeled with
         %   values 1, 2, ... respectively
  m~     %   True if 2 is not present in this matrix. That means there is only
         %   one connected component; that is, k and j are neighbours in the
         %   input matrix, or k=j
]        % End
v16e     % The stack now has 256 values. Concatenate them into a vector and
         % reshape as a 16×16 matrix. This matrix describes neighbourhood: entry
         % (k,j) is 1 if values k and j are neighbours in the input or if k=j
XK       % Copy into clipboard K
68E      % Push 68 times 2, that is, 136, which is 1+2+...+16
16       % Push 16. This is the initial value eaten by the mouse. New values will
         % be appended to create a vector of eaten values
b        % Bubble up the 16×16 matrix to the top of the stack
"        % For each column. This just executes the loop 16 times
  K      %   Push neighbourhood matrix from clipboard K
  y      %   Copy from below: pushes a copy of the vector of eaten values
  0)     %   Get last value. This is the most recent eaten value
  Y)     %   Get that row of the neighbourhood matrix
  f      %   Indices of nonzeros. This gives a vector of neighbours of the last
         %   eaten value
  y      %   Copy from below: pushes a copy of the vector of eaten values
  X-     %   Set difference (may give an empty result)
  X>     %   Maximum value. This is the new eaten value (maximum neighbour not
         %   already eaten). May be empty, if all neighbours are already eaten
  h      %   Concatenate to vector of eaten values
]        % End
s        % Sum of vector of all eaten values
-        % Subtract from 136. Implicitly display

```

# Answer
> 8 votes
# Python 2, 111 bytes

```
i=x=a=input()
while x:x,i=max((y,j)for j,y in enumerate(a)if i>[]or 2>i/4-j/4>-2<i%4-j%4<2);a[i]=0
print sum(a)

```

Try it online!

Method and test cases adapted from Bubbler. Takes a flat list on STDIN.

The code checks whether two flat indices `i` and `j` represent touching cells by checking that both row different `i/4-j/4` and column difference `i%4-j%4` are strictly between -2 and 2. The first pass instead has this check automatically succeed so that the largest entry is found disregarding adjacency.

# Answer
> 6 votes
# PHP, ~~177 174~~ 171 bytes

```
for($v=16;$v;$u+=$v=max($p%4-1?max($a[$p-5],$a[$p-1],$a[$p+3]):0,$a[$p-4],$a[$p+4],$p%4?max($a[$p-3],$a[$p+1],$a[$p+5]):0))$a[$p=array_search($v,$a=&$argv)]=0;echo 120-$u;

```

Run with `-nr`, provide matrix elements as arguments or try it online.

# Answer
> 5 votes
# JavaScript, 122 bytes

I took more than a couple of wrong turns on this one and now I've run out of time for further golfing but at least it's working. Will revisit tomorrow (or, knowing me, on the train home this evening!), if I can find a minute.

```
a=>(g=n=>n?g([-6,-5,-4,-1,1,4,5,6].map(x=>n=a[x+=i]>n?a[x]:n,a[i=a.indexOf(n)]=n=0)|n)-n:120)(16,a=a.flatMap(x=>[...x,0]))

```

Try it online

# Answer
> 5 votes
# , ~~128~~ ~~124~~ ~~123~~ ~~112~~ 110 bytes

```
function(r){r=rbind(0,cbind(0,r,0),0)
m=r>15
while(r[m]){r[m]=0
m=r==max(r[which(m)+c(7:5,1)%o%-1:1])}
sum(r)}

```

Try it online!

It creates a 4x4 matrix (which helped me to visualize things), pads it with 0's, then begins from 16 and searches it's surrounding "piles" for the next largest, and so forth.

Upon conclusion, it does output a warning, but it is of no consequence and does not change the result.

**EDIT:** -4 bytes by compressing the initialization of the matrix into 1 line.

**EDIT:** -1 thanks to Robert Hacken

**EDIT:** -13 bytes combining Giuseppe and Robin Ryder's suggestions.

# Answer
> 5 votes
# Powershell, ~~143~~ ~~141~~ ~~136~~ ~~130~~ ~~122~~ 121 bytes

```
$a=,0*5+($args|%{$_+0})
for($n=16;$i=$a.IndexOf($n)){$a[$i]=0
$n=(-1,1+-6..-4+4..6|%{$a[$i+$_]}|sort)[-1]}$a|%{$s+=$_}
$s

```

Less golfed test script:

```
$f = {

$a=,0*5+($args|%{$_+0})
for($n=16;$i=$a.IndexOf($n)){
    $a[$i]=0
    $n=(-1,1+-6..-4+4..6|%{$a[$i+$_]}|sort)[-1]
}
$a|%{$s+=$_}
$s

}

@(
    ,( 0  , ( 4,  3,  2,  1), ( 5,  6,  7,  8), (12, 11, 10,  9), (13, 14, 15, 16) )
    ,( 0  , ( 8,  1,  9, 14), (11,  6,  5, 16), (13, 15,  2,  7), (10,  3, 12,  4) )
    ,( 1  , ( 1,  2,  3,  4), ( 5,  6,  7,  8), ( 9, 10, 11, 12), (13, 14, 15, 16) )
    ,( 3  , (10, 15, 14, 11), ( 9,  3,  1,  7), (13,  5, 12,  6), ( 2,  8,  4, 16) )
    ,( 12 , ( 3,  7, 10,  5), ( 6,  8, 12, 13), (15,  9, 11,  4), (14,  1, 16,  2) )
    ,( 34 , ( 8,  9,  3,  6), (13, 11,  7, 15), (12, 10, 16,  2), ( 4, 14,  1,  5) )
    ,( 51 , ( 8, 11, 12,  9), (14,  5, 10, 16), ( 7,  3,  1,  6), (13,  4,  2, 15) )
    ,( 78 , (13, 14,  1,  2), (16, 15,  3,  4), ( 5,  6,  7,  8), ( 9, 10, 11, 12) )
    ,( 102, ( 9, 10, 11, 12), ( 1,  2,  4, 13), ( 7,  8,  5, 14), ( 3, 16,  6, 15) )
    ,( 103, ( 9, 10, 11, 12), ( 1,  2,  7, 13), ( 6, 16,  4, 14), ( 3,  8,  5, 15) )
) | % {
    $expected, $a = $_
    $result = &$f @a
    "$($result-eq$expected): $result"
}

```

Output:

```
True: 0
True: 0
True: 1
True: 3
True: 12
True: 34
True: 51
True: 78
True: 102
True: 103

```

Explanation:

**First**, add top and bottom borders of 0 and make a single dimensional array:

```
0 0 0 0 0
# # # # 0
# # # # 0
# # # # 0
# # # # 0

     ↓

0 0 0 0 0 # # # # 0 # # # # 0 # # # # 0 # # # # 0

```

Powershell returns `$null` if you try to get the value behind the end of the array.

**Second**, loop `biggest neighbor pile` started from 16 to non-zero-maximum. And nullify it (The Hungry Mouse eats it).

```
for($n=16;$i=$a.IndexOf($n)){
    $a[$i]=0
    $n=(-1,1+-6..-4+4..6|%{$a[$i+$_]}|sort)[-1]
}

```

**Third**, sum of the remaining piles.

# Answer
> 4 votes
# Java 10, ~~272~~ ~~248~~ ~~239~~ 237 bytes

```
m->{int r=0,c=0,R,C,M=16,x,y,X=0,Y=0;for(;M-->0;)if(m[M/4][M%4]>15)m[r=M/4][c=M%4]=0;for(;M!=0;m[r=X][c=Y]=0)for(M=0,C=9;C-->0;)try{if((R=m[x=r+C/3-1][y=c+C%3-1])>M){M=R;X=x;Y=y;}}finally{continue;}for(var Z:m)for(int z:Z)M+=z;return M;}

```

The cells are checked the same as in my answer for the *All the single eights* challenge.
-24 bytes thanks to *@OlivierGrégoire*.
-11 bytes thanks to *@ceilingcat*.

Try it online.

**Explanation:**

```
m->{                       // Method with integer-matrix parameter and integer return
  int r=0,                 //  Row-coordinate for the largest number, starting at 0
      c=0,                 //  Column-coordinate for the largest number, starting at 0
      R,C,                 //  Row and column indices (later reused as temp integers)
      M=16,                //  Largest number the mouse just ate, starting at 16
      x,y,X=0,Y=0;         //  Temp integers
  for(;M-->0;)             //  Loop `M` in the range (16, 0]:
    if(m[M/4][M%4]>15)     //   If the current cell is 16:
      m[r=M/4][c=M%4]      //    Set `r,c` to this coordinate
        =0;                //    And empty this cell
                           //  (after this first loop, `M` will be -1)
  for(;M!=0;               //  Loop as long as the largest number `M` isn't 0:
      ;                    //    After every iteration:
       m[r=X][c=Y]         //     Change the `r,c` coordinates,
         =0)               //     And empty this cell
    for(M=0,               //   Reset `M` to 0
        C=9;C-->0;)        //   Inner loop `C` in the range (9, 0]:
          try{if((R=       //    Set `R` to:
            m[x=r+C/3-1]   //     If `C` is 0, 1, or 2: Look at the previous row
                           //     Else-if `C` is 6, 7, or 8: Look at the next row
                           //     Else (`C` is 3, 4, or 5): Look at the current row
             [y=c+C%3-1])  //     If `C` is 0, 3, or 6: Look at the previous column
                           //     Else-if `C` is 2, 5, or 8: Look at the next column
                           //     Else (`C` is 1, 4, or 7): Look at the current column
               >M){        //    And if the number in this cell is larger than `M`
                 M=R;      //     Change `M` to this number
                 X=x;Y=y;} //     And change the `X,Y` coordinate to this cell
          }finally{continue;}
                           //    Catch and ignore ArrayIndexOutOfBoundsExceptions
                           //    (try-finally saves bytes in comparison to if-checks)
  for(var Z:m)             //  Then loop over all rows of the matrix:
    for(int z:Z)           //   Inner loop over all columns of the matrix:
      M+=z;                //    And sum them all together in `M` (which was 0)
  return M;}               //  Then return this sum as result

```

# Answer
> 4 votes
# Charcoal, 47 bytes

```
ＥＡ⭆ι§αλ≔QθＷ›θA«≔⌕ＫＡθθＪ﹪θ⁴÷θ⁴≔⌈ＫＭθA»≔ΣＥＫＡ⌕αιθ⎚Ｉθ

```

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

```
ＥＡ⭆ι§αλ

```

Convert the input numbers into alphabetic characters (A=0 .. Q=16) and print them as a 4x4 grid.

```
≔Qθ

```

Start by eating the Q, i.e. 16.

```
Ｗ›θA«

```

Repeat while there is something to eat.

```
≔⌕ＫＡθθ

```

Find where the pile is. This is a linear view in row-major order.

```
Ｊ﹪θ⁴÷θ⁴

```

Convert to co-ordinates and jump to that location.

```
≔⌈ＫＭθ

```

Find the largest adjacent pile.

Eat the current pile.

```
≔ΣＥＫＡ⌕αιθ

```

Convert the piles back to integers and take the sum.

```
⎚Ｉθ

```

Clear the canvas and output the result.

# Answer
> 4 votes
# Haskell, 163 bytes

```
o f=foldl1 f.concat
r=[0..3]
q n=take(min(n+2)3).drop(n-1)
0#m=m
v#m=[o max$q y$q x<$>n|y<-r,x<-r,m!!y!!x==v]!!0#n where n=map(z<$>)m;z w|w==v=0|0<1=w
f=o(+).(16#)

```

Try it online!

The `f` function takes the input as a list of 4 lists of 4 integers.

### Slightly ungolfed

```
-- helper to fold over the matrix
o f = foldl1 f . concat

-- range of indices
r = [0 .. 3]

-- slice a list (take the neighborhood of a given coordinate)
-- first we drop everything before the neighborhood and then take the neighborhood itself
q n = take (min (n + 2) 3) . drop (n - 1)

-- a step function
0 # m = m -- if the max value of the previous step is zero, return the map
v # m =
    -- abuse list comprehension to find the current value in the map
    -- convert the found value to its neighborhood,
    -- then calculate the max cell value in it
    -- and finally take the head of the resulting list
    [ o max (q y (q x<$>n)) | y <- r, x <- r, m!!y!!x == v] !! 0
       # n -- recurse with our new current value and new map
    where
        -- a new map with the zero put in place of the value the mouse currently sits on
        n = map (zero <$>) m
        -- this function returns zero if its argument is equal to v
        -- and original argument value otherwise
        zero w
            | w == v = 0
            | otherwise = w

-- THE function. first apply the step function to incoming map,
-- then compute sum of its cells
f = o (+) . (16 #)

```

# Answer
> 4 votes
# JavaScript (ES7), 97 bytes

Takes input as a flattened array.

```
f=(a,s=p=136,m,d)=>a.map((v,n)=>v<m|(n%4-p%4)**2+(n-p)**2/9>d||(q=n,m=v))|m?f(a,s-m,a[p=q]=0,4):s

```

Try it online!

### Commented

```
f = (                    // f= recursive function taking:
  a,                     // - a[] = flattened input array
  s =                    // - s = sum of cheese piles, initialized to 1 + 2 + .. + 16 = 136
      p = 136,           // - p = position of the mouse, initially outside the board
  m,                     // - m = maximum pile, initially undefined
  d                      // - d = distance threshold, initially undefined
) =>                     //
  a.map((v, n) =>        // for each pile v at position n in a[]:
    v < m |              //   unless this pile is not better than the current maximum
    (n % 4 - p % 4) ** 2 //   or (n % 4 - p % 4)²
    + (n - p) ** 2 / 9   //      + (n - p)² / 9
    > d ||               //   is greater than the distance threshold:
    (q = n, m = v)       //     update m to v and q to n
  )                      // end of map()
  | m ?                  // if we've found a new pile to eat:
    f(                   //   do a recursive call:
      a,                 //     pass a[] unchanged
      s - m,             //     update s by subtracting the pile we've just eaten
      a[p = q] = 0,      //     clear a[q], update p to q and set m = 0
      4                  //     use d = 4 for all next iterations
    )                    //   end of recursive call
  :                      // else:
    s                    //   stop recursion and return s

```

# Answer
> 4 votes
# Julia, ~~133~~ 127 bytes

```
*(A,S=136,I=keys(A))=((v,r,c)=maximum(i->(get(A,i,0),i[1],i[2]),I);S-=v;v>0 ? (A[r,c]=0;A*S*[(r+i,c+j) for i=-1:1,j=-1:1]) : S)
```

`-6` bytes by @MarcMush, thx!

Attempt This Online!

readable version:

```
*(A,S=136,I=keys(A))=(
(v,r,c)=maximum(i->(get(A,i,0),i[1],i[2]),I);S-=v;
v>0 ? (A[r,c]=0;A*S*[(r+i,c+j) for i=-1:1,j=-1:1]) : S)

```
* input: matrix (not a list of lists)
* works for arbitrary shaped matrices with positive numbers in it - as long as the path taken by the mouse is uniquely determined by the numbers.
* interesting math questions:
    + what is the expected outcome of this "game"? (i got a value (approx.) between 18.2 and 18.3 with simulation
    + what is the expected length of the path?

# Answer
> 3 votes
# SAS, ~~236~~ 219 bytes

Input on punch cards, one line per grid (space-separated), output printed to the log.

This challenge is slightly complicated by some limitations of arrays in SAS:

* There is no way to return the row and column indexes of a matching element from multidimensional data-step array - you have to treat the array as 1-d and then work them out for yourself.
* If you go out of bounds, SAS throws an error and halts processing rather than returning null / zero.

## Updates:

* Removed `infile cards;` statement (-13)
* Used wildcard `a:` for array definition rather than `a1-a16` (-4)

## Golfed:

```
data;input a1-a16;array a[4,4]a:;p=16;t=136;do while(p);m=whichn(p,of a:);t=t-p;j=mod(m-1,4)+1;i=ceil(m/4);a[i,j]=0;p=0;do k=max(1,i-1)to min(i+1,4);do l=max(1,j-1)to min(j+1,4);p=max(p,a[k,l]);end;end;end;put t;cards;
    <insert punch cards here>
    ;

```

## Ungolfed:

```
data;                /*Produce a dataset using automatic naming*/
input a1-a16;        /*Read 16 variables*/
array a[4,4] a:;     /*Assign to a 4x4 array*/
p=16;                /*Initial pile to look for*/
t=136;               /*Total cheese to decrement*/
do while(p);         /*Stop if there are no piles available with size > 0*/
  m=whichn(p,of a:); /*Find array element containing current pile size*/
  t=t-p;             /*Decrement total cheese*/
  j=mod(m-1,4)+1;    /*Get column number*/
  i=ceil(m/4);       /*Get row number*/
  a[i,j]=0;          /*Eat the current pile*/
                     /*Find the size of the largest adjacent pile*/
  p=0;
  do k=max(1,i-1)to min(i+1,4);
    do l=max(1,j-1)to min(j+1,4);
      p=max(p,a[k,l]);
    end;
  end;
end;
put t;              /*Print total remaining cheese to log*/
                    /*Start of punch card input*/
cards;
  4  3  2  1  5  6  7  8 12 11 10  9 13 14 15 16
  8  1  9 14 11  6  5 16 13 15  2  7 10  3 12  4
  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16
 10 15 14 11  9  3  1  7 13  5 12  6  2  8  4 16
  3  7 10  5  6  8 12 13 15  9 11  4 14  1 16  2
  8  9  3  6 13 11  7 15 12 10 16  2  4 14  1  5
  8 11 12  9 14  5 10 16  7  3  1  6 13  4  2 15
 13 14  1  2 16 15  3  4  5  6  7  8  9 10 11 12
  9 10 11 12  1  2  4 13  7  8  5 14  3 16  6 15
  9 10 11 12  1  2  7 13  6 16  4 14  3  8  5 15
;                    /*End of punch card input*/
                     /*Implicit run;*/

```

# Answer
> 3 votes
# APL (Dyalog Unicode), ~~42~~ 41 bytesSBCS

```
16{×⍺:a∇⍨+/,m×⌈/⌈/⊢⌺3 3⊢a←⍵×~m←⍺=⍵⋄+/,⍵}⊢

```

Try it online!

# Answer
> 2 votes
# Jelly,  ~~31 30~~  29 bytes

```
³œiⱮZIỊȦ
⁴ṖŒPŒ!€Ẏ⁴;ⱮṢÇƇṪ
FḟÇS

```

Since the method is far too slow to run within 60s with the mouse starting on `16` this starts her off at `9` and limits her ability such that she is only able to eat `9`s or less **Try it online!** (thus here she eats `9, 2, 7, 4, 8, 6, 3` leaving `97`).

### How?

```
³œiⱮZIỊȦ - Link 1, isSatisfactory?: list of integers, possiblePileChoice
³        - (using a left argument of) program's 3rd command line argument (M)
   Ɱ     - map across (possiblePileChoice) with:
 œi      -   first multi-dimensional index of (the item) in (M)
    Z    - transpose the resulting list of [row, column] values
     I   - get the incremental differences
      Ị  - insignificant? (vectorises an abs(v) <= 1 test)
       Ȧ - any and all? (0 if any 0s are present in the flattened result [or if it's empty])

⁴ṖŒPŒ!€Ẏ⁴;ⱮṢÇƇṪ - Link 2, getChosenPileList: list of lists of integers, M
⁴               - literal 16
 Ṗ              - pop -> [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]
  ŒP            - power-set -> [[],[1],[2],...,[1,2],[1,3],...,[2,3,7],...,[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]]
      €         - for each:
    Œ!          -   all permutations
       Ẏ        - tighten (to a single list of all these individual permutations)
        ⁴       - (using a left argument of) literal 16
          Ɱ     - map across it with:
         ;      -   concatenate (put a 16 at the beginning of each one)
           Ṣ    - sort the resulting list of lists
             Ƈ  - filter keep those for which this is truthy:
            Ç   -   call last Link as a monad (i.e. isSatisfactory(possiblePileChoice)
              Ṫ - tail (get the right-most, i.e. the maximal satisfactory one)

FḟÇS - Main Link: list of lists of integers, M
F    - flatten M
  Ç  - call last Link (2) as a monad (i.e. get getChosenPileList(M))
 ḟ   - filter discard (the resulting values) from (the flattened M)
   S - sum

```

# Answer
> 1 votes
# J, 82 bytes

```
g=.](]*{:@[~:])]_1}~[:>./]{~((,-)1 5 6 7)+]i.{:
[:+/[:(g^:_)16,~[:,0,~0,0,0,.~0,.]

```

Try it online!

I plan to golf this more tomorrow, and perhaps write a more J-ish solution similar to this one, but I figured I'd try the flattened approach since I hadn't done that before.

# Answer
> 1 votes
# Red, 277 bytes

```
func[a][k: 16 until[t:(index? find load form a k)- 1
p: do rejoin[t / 4 + 1"x"t % 4 + 1]a/(p/1)/(p/2): 0
m: 0 foreach d[-1 0x-1 1x-1 -1x0 1x0 -1x1 0x1 1][j: p + d
if all[j/1 > 0 j/1 < 5 j/2 > 0 j/2 < 5 m < t: a/(j/1)/(j/2)][m: t]]0 = k: m]s: 0
foreach n load form a[s: s + n]s]

```

Try it online!

It's really long solution and I'm not happy with it, but I spent so much time fixing it to work in TIO (apparently there are many differences between the Win and Linux stable versions of Red), so I post it anyway...

## More readable:

```
f: func [ a ] [
    k: 16
    until [
        t: (index? find load form a n) - 1
        p: do rejoin [ t / 4 + 1 "x" t % 4 + 1 ]
        a/(p/1)/(p/2): 0
        m: 0
        foreach d [ -1 0x-1 1x-1 -1x0 1x0 -1x1 0x1 1 ] [
            j: p + d
            if all[ j/1 > 0
                    j/1 < 5
                    j/2 > 0
                    j/2 < 5
                    m < t: a/(j/1)/(j/2)
            ] [ m: t ]
        ]
        0 = k: m
    ]
    s: 0
    foreach n load form a [ s: s + n ]
    s
]

```

# Answer
> 1 votes
Not my best work. There's some definite improvements to be done, some probably fundamental to the algorithm used -- I'm sure it can be improved by using only an `int[]`, but I couldn't figure out how to efficiently enumerate neighbors that way. I'd love to see a PowerShell solution that uses only a single dimensional array!

# PowerShell Core, 348 bytes

```
Function F($o){$t=120;$a=@{-1=,0*4;4=,0*4};0..3|%{$a[$_]=[int[]](-join$o[(3+18*$_)..(3+18*$_+13)]-split',')+,0};$m=16;while($m-gt0){0..3|%{$i=$_;0..3|%{if($a[$i][$_]-eq$m){$r=$i;$c=$_}}};$m=($a[$r-1][$c-1],$a[$r-1][$c],$a[$r-1][$c+1],$a[$r][$c+1],$a[$r][$c-1],$a[$r+1][$c-1],$a[$r+1][$c],$a[$r+1][$c+1]|Measure -Max).Maximum;$t-=$m;$a[$r][$c]=0}$t}

```

Try it online!

---

More readable version:

```
Function F($o){
    $t=120;
    $a=@{-1=,0*4;4=,0*4};
    0..3|%{$a[$_]=[int[]](-join$o[(3+18*$_)..(3+18*$_+13)]-split',')+,0};
    $m=16;
    while($m-gt0){
        0..3|%{$i=$_;0..3|%{if($a[$i][$_]-eq$m){$r=$i;$c=$_}}};
        $m=($a[$r-1][$c-1],$a[$r-1][$c],$a[$r-1][$c+1],$a[$r][$c+1],$a[$r][$c-1],$a[$r+1][$c-1],$a[$r+1][$c],$a[$r+1][$c+1]|Measure -Max).Maximum;
        $t-=$m;
        $a[$r][$c]=0
    }
    $t
}

```

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

```
x;y;i;b;R;C;
g(int a[][4],int X,int Y){b=a[Y][X]=0;for(x=-1;x<2;++x)for(y=-1;y<2;++y)if(!(x+X&~3||y+Y&~3||a[y+Y][x+X]<b))b=a[C=Y+y][R=X+x];for(i=x=0;i<16;++i)x+=a[0][i];return b?g(a,R,C):x;}
s(int*a){for(i=0;i<16;++i)if(a[i]==16)return g(a,i%4,i/4);}

```

Try it online!

Note: This submission modifies the input array.

`s()` is the function to call with an argument of a mutable `int[16]` (which is the same in-memory as an `int[4][4]`, which is what `g()` interprets it as).

`s()` finds the location of the `16` in the array, then passes this information to `g`, which is a recursive function that takes a location, sets the number at that location to 0, and then:

* If there is a positive number adjacent to it, recurse with the location of the largest adjacent number
* Else, return the sum of the numbers in the array.

# Answer
> 1 votes
# Wolfram Language (Mathematica), 149 bytes

```
(g@p_:=#&@@Position[s,Max@p];m=g[s=#];While[Tr[b=s[[##]]&@@#&/@Select[#+m&/@Tuples[{-1,0,1},2],Max@#<5&&Min@#>0&]]>0,m=g@b;s[[##&@@m]]=0];Tr[Tr/@s])&

```

Try it online!

# Answer
> 1 votes
# Add++, 281 bytes

```
D,f,@@,VBFB]G€=dbLRz€¦*bMd1_4/i1+$4%B]4 4b[$z€¦o
D,g,@@,c2112011022200200BD1€Ω_2$TAVb]8*z€kþbNG€lbM
D,k,@~,z€¦+d4€>¦+$d1€<¦+$@+!*
D,l,@@#,bUV1_$:G1_$:
D,h,@@,{l}A$bUV1_$:$VbU","jG$t0€obU0j","$t€iA$bUpVdbLRG€=€!z€¦*$b]4*$z€¦o
y:?
m:16
t:120
Wm,`x,$f>y>m,`m,$g>x>y,`y,$h>x>y,`t,-m
Ot

```

Try it online!

Oof, this is a complicated one.

**Verify all test cases**

## How it works

For this explanation, we will use the input

\\$M = \left\[\begin{matrix} 3 & 7 & 10 & 5 \\ 6 & 8 & 12 & 13 \\ 15 & 9 & 11 & 4 \\ 14 & 1 & 16 & 2 \\ \end{matrix}\right\]\\$

We start by defining a series of helper functions. We will use \\$x\\$ to represent an integer such that \\$1 \le x \le 16\\$, \\$M\\$ to, initially, represent the \\$4\text{x}4\\$ input matrix. The functions are:

* \\$f(x, M)\\$: Given a value and a \\$4\text{x}4\\$ matrix, return the co-ordinates of \\$x\\$ in \\$M\\$ e.g. if \\$x = 16\\$ and \\$M\\$ is above, \\$f(x, M) = (4, 3)\\$
* \\$g(M, y)\\$: Given a matrix and two co-ordinates, return the largest of the neighbours of the value at that point e.g. using \\$f(x, M)\\$ from above, \\$g(M, f(x, M)) = 11\\$

This implements the two helper functions:

\\$k(x)\\$ which removes any co-ordinates which would wrap around or be out of bounds

\\$l(M, y)\\$ which, given a matrix and co-ordinates, returns the value at those co-ordinates
* \\$h(y, M)\\$ which, given a matrix and co-ordinates, sets the value at those indexes to \\$0\\$

After these functions are defined, we come to the main body of the program. The first step is to assign the four variables, **x**, **y**, **m** and **t**. **x** is set to \\$0\\$ by default, **y** to the input, **m** to \\$16\\$ (the first value to search for) and **t** to \\$120 \\: (1 + 2 + \cdots + 14 + 15)\\$.

Next, we enter a while loop, that loops while **m** does not equal \\$0\\$. The steps in the loop go something along the lines of

While **m** \\$\neq 0\\$:

* Set **x** to \\$f(\textbf{y}, \textbf{m})\\$. For the first iteration, this sets **x** to the co-ordinates of \\$16\\$ is \\$M\\$ (\\$x := (4, 3)\\$ in our example)
* Set **m** to \\$g(\textbf{x}, \textbf{y})\\$. This yields the largest new neighbour to **m**, or \\$0\\$, if there are no new neighbours (which ends the while loop).
* Set **y** to \\$h(\textbf{x}, \textbf{y})\\$. This sets the previous value of **m** (\\$16\\$ in the first iteration) to \\$0\\$, in order for the previous step to work
* Set **t** to \\$\textbf{t} - \textbf{m}\\$, removing that value from the total value amount.

Finally, output **t**, i.e. the remaining, non collected values.

# Answer
> 1 votes
# C# (.NET Core), 258 bytes

Without LINQ. The using System.Collections.Generic is for the formatting after - the function doesn't require it.

```
e=>{int a=0,b=0,x=0,y=0,j=0,k;foreach(int p in e){if(p>15){a=x=j/4;b=y=j%4;}j++;}e[x,y]=0;while(1>0){for(j=-1;j<2;j++)for(k=-1;k<2;k++){try{if(e[a+k,b+j]>e[x,y]){x=a+k;y=b+j;}}catch{}}if(e[x,y]<1)break;e[x,y]=0;a=x;b=y;}a=0;foreach(int p in e)a+=p;return a;}

```

Try it online!

# Answer
> 1 votes
# Perl 6, ~~151~~ ~~136~~ ~~126~~ ~~125~~ 119 bytes

```
{my@k=$_;my $a=.grep(16,:k)[0];while @k[$a] {@k[$a]=0;$a=^@k .grep({2>$a+>2-$_+>2&$a%4-$_%4>-2}).max({@k[$_]})};[+] @k}

```

Super shabby solution. Takes input as flattened array.

Try it online!

# Answer
> 1 votes
# Perl 5 `-MList::Util=sum -p`, 137 bytes

```
splice@F,$_,0,0for 12,8,4;map{$k{++$,}=$_;$n=$,if$_&16}@F;map{map{$n=$_+$"if$k{$"+$_}>$k{$n}&&!/2|3/}-6..6;$k{$"=$n}=0}@F;$_=sum values%k

```

Try it online!

# Answer
> 1 votes
# K (ngn/k), 49 bytes

```
{{h[,x]:0;*>(+x+0,'1-!3 3)#h}\*>h::(+!4 4)!x;+/h}

```

Try it online!

the input (`x`) is a 1d array

`(+!4 4)!x` a dictionary that maps pairs of coords to the values of `x`

`h::` assign to a global variable `h`

`*>` the key corresponding to the max value

`{` `}\` repeat until convergence, collecting intermediate values in a list

`h[,x]:0` zero out the current position

`+x+0,'1-!3 3` neighbour positions

`(` `)#h` filter them from `h` as a smaller dictionary

`*>` which neighbour has the max value? it becomes the current position for the new iteration

`+/h` finally, return the sum of `h`'s remaining values

# Answer
> 1 votes
# Wolfram Language (Mathematica), ~~124~~ 115 bytes

```
(p=#&@@Position[m=Join@@ArrayPad[#,1],16];Do[m[[p]]=0;p=MaximalBy[#&@@p+{0,-1,1,-5,5,-6,6,-7,7},m[[#]]&],16];Tr@m)&

```

Try it online!

This takes a 2D array, pads it on each side, then immediately flattens it so we don't have to spend bytes indexing. The only cost to this is `Join@@` to flatten. Afterwards it proceeds as below.

**124-byte version** for a 2D array: Try it online!

Mostly my own work, with a bit derived from J42161217's 149-byte answer.

Ungolfed:

```
(p = #& @@ Position[m = #~ArrayPad~1,16];     m = input padded with a layer of 0s
                                              p = location of 16
Do[
    m = MapAt[0&,m,p];                        Put a 0 at location p
    p = #& @@ MaximalBy[                      Set p to the member of
        p+#& /@ Tuples[{0,-1,1},2],             {all possible next locations}
        m~Extract~#&],                        that maximizes that element of m,
                                              ties broken by staying at p+{0,0}=p.
16];                                        Do this 16 times.
Tr[Tr/@m]                                   Finally, output the sum of m.
)&

```

# Answer
> 0 votes
Not the shortest solution, but pretty straight forward.

## Ruby, 207

```
a=eval(ARGV[0])
n=16
while n!=0 do
a[i=a.index(n)]=0
t=[a[i+4]]
t<<a[i-4]if i>3
if i%4!=0
t<<a[i-5]if i>3
t<<a[i-1]
t<<a[i+3]
end
if i%4!=3
t<<a[i+1]
t<<a[i+5]
t<<a[i-3]if i>3
end
n=t.compact.max
end
p a.sum

```

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


title: Zipper multiplication

text:
# Question
Title: Zipper multiplication
## Introduction

Let's define a new arithmetical operation, which I call *zipper multiplication*. To zipper multiply two nonnegative integers, you add leading zeros to make the lengths match, multiply the corresponding base-10 digits of the numbers, add leading zeros to the results to get 2-digit numbers, concatenate them, and finally drop leading zeros.

Here's an example with **A = 1276** and **B = 933024**:

```
1. Add leading zeros
 A = 001276
 B = 933024

2. Multiply digit-wise
 A = 0  0  1  2  7  6
 B = 9  9  3  0  2  4
 ->  0  0  3  0 14 24

3. Pad to 2 digits
 -> 00 00 03 00 14 24

4. Concatenate
 -> 000003001424

5. Drop leading zeros
 -> 3001424

```

The operation is extended to all integers with the usual sign rules: positive times negative is negative, negative times negative is positive and so on.

## The task

Your inputs are two integers, and your output is their zipper multiplication. You should be able to handle arbitrarily large inputs. Input and/or output can be in string format (and indeed must be, if your language doesn't support arbitrarily large integers). Note that `-0` is not a valid input or output.

## Rules and scoring

You can write a full program or a function, and the lowest byte count wins.

## Test cases

```
0 0 -> 0
302 40 -> 0
302 -40 -> 0
-4352 448 -> -122016
0 6623 -> 0
0 -6623 -> 0
20643 -56721 -> -1000420803
63196 21220 -> 1203021800
1276 933024 -> 3001424
-1276 933024 -> -3001424
-1276 -933024 -> 3001424
5007204555 350073039 -> 12001545
-612137119 -8088606033 -> 816060042000327
3389903661 -6619166963 -> -18180881090018543603
-23082746128560880381 1116941217 -> -8050600723200060807
-668336881543038127783364011867 896431401738330915057436190556 -> -485448120906320001351224000900090235004021121824000900403042
402878826066336701417493206805490000415 312487283677673237790517973105761463808 -> 120004325656161618004242182118140007280900200921180018080025285400000000320040

```

# Answer
> 9 votes
# Jelly, ~~11~~ 10 bytes

```
ƓDUz0P€Uḅ³

```

Try it online!

I couldn't get this down to 10 bytes by myself, but @Pietu1998 pointed me to an atom I'd missed, this giving this 10-byte solution. Unusually for Jelly, this one takes input from standard input (in the form `1276,933024`), not from the command line (this enables the use of the `³` command, which returns the command line argument, defaulting to 100).

Explanation:

```
ƓDUz0P€Uḅ³
Ɠ           read standard input
 D          convert to base 10
  U         reverse elements
   z0       transpose, padding the end with zeroes
     P€     take the product of each (€) inner list
       U    reverse elements back
        b³  convert from base 100

```

The use of base 100 is a simple way to implement the "pad to 2 digits, then convert to base 10" technique. The only other subtle thing here is the reversing; we want to pad with zeroes at the start of the number, but Jelly's `z` command pads at the end, so reversing the lists means that `z` will pad correctly.

# Answer
> 4 votes
# Python 2, 99 bytes

```
a,b=input();o=0;p=1-2*(a*b<0);a,b=abs(a),abs(b)
while a:o+=a%10*(b%10)*p;p*=100;a/=10;b/=10
print o

```

A lot of the bytes are there to account for the sign in case of negative input. In Python, `n%d` is always non-negative if `d` is positive1. In my opinion this is generally desirable, but here it seems inconvenient: removing the calls to `abs` would break the above code. Meanwhile `p` keeps track of the "place value" (ones, hundreds, etc.) and also remembers the desired sign of the output.

The code is basically symmetric in `a` and `b` except in the `while` condition: we keep going until `a` is zero, and terminate at that time. Of course if `b` is zero first, then we'll end up adding zeroes for a while until `a` is zero as well.

---

1 For example, `(-33)%10` returns `7`, and the integer quotient of `(-33)/10` is `-4`. This is correct because `(-4)*10 + 7 = -33`. However, the zipper product of `(-33)` with `33` must end in `3*3 = 09` rather than `7*3 = 21`.

# Answer
> 3 votes
## JavaScript (ES6), 44 bytes

```
f=(x,y)=>x&&f(x/10|0,y/10|0)*100+x%10*(y%10)

```

Conveniently this automatically works for negative numbers.

# Answer
> 2 votes
# C, 77 bytes

-2 bytes for removing redundant braces (`*` is associative).

```
r,t;f(a,b){t=1;r=0;while(a|b)r+=t*(a%10)*(b%10),a/=10,b/=10,t*=100;return r;}

```

`t`=1,100,10000,... is used for padding. As long as `a` or `b` is not zero keep multiplicating the last digit `%10` with `t` and accumulate. Then erease the last digit of `a` and `b` (`/=10`) and shift `t` by 2 digits (`*=100`).

Ungolfed and usage:

```
r,t;
f(a,b){
 t=1;
 r=0;
 while(a|b)
  r+=t*(a%10)*(b%10),
  a/=10,
  b/=10,
  t*=100;
 return r;
}

main(){
 printf("%d\n", f(1276,933024));
}

```

# Answer
> 1 votes
# Actually, ~~23~~ 19 bytes

Input is taken as two strings. Also, apparently attempting to convert from base 100, as ais523 does in their Jelly answer, doesn't work so well in Actually. Would have saved 9 bytes too if it worked :/ Golfing suggestions welcome! Try it online!

**Edit:** -4 bytes from changing how the result is built up into a new number.

```
k`♂≈R`M┬ñ`iτ╤@π*`MΣ

```

**Ungolfing**

```
          Implicit input a and b.
k         Wrap a and b into a list.
`...`M    Map over the list of strings.
  ♂≈        Convert each digit to its own int.
  R         Reverse for later.
┬         Transpose to get pairs of digits from a and b.
ñ         enumerate(transpose) to get all of the indices as well.
`...`M    Map over the transpose.
  i         Flatten (index, pair) onto the stack.
  τ╤        Push 10**(2*index) == 100**index to the stack.
  @π        Swap and get the product of the pair of integers.
  *         Multiply the product by 100**index.
Σ         Sum everything into one number.
          Implicit return.

```

# Answer
> 1 votes
# R, ~~182~~ ~~110~~ ~~107~~ 86 bytes

No longer the longest answer (thanks, Racket), and in fact shorter than the Python solution (a rare treat)! An anonymous function that takes two integers as input.

```
function(a,b)sum((s=function(x)abs(x)%%10^(99:1)%/%(e=10^(98:0))*e)(a)*s(b))*sign(a*b)

```

Here's how it works.

The zipper multiplication involves splitting the input numbers into their constituent digits.We take the absolute value of number and carry out modulo for descending powers of 10:

```
abs(x) %% 10^(99:1)

```

So here we're taking one number, `x`, and applying modulo with 99 other numbers (`10^99` through `10^1`). R implicitly repeats `x` 99 times, returning a vector (list) with 99 elements. (`x %% 10^99`, `x %% 10^98`, `x %% 10^97`, etc.)

We use `10^99` through `10^1`. A more efficient implementation would use the value of number of digits in the longest number (check the edit history of this post; previous versions did this), but simply taking `99..1` uses fewer bytes.

For `x = 1276` this gives us

```
1276 1276 1276 ... 1276 276 76 6

```

Next, we use integer division by descending powers of 10 to round out the numbers:

```
abs(x) %% 10^(99:1) %/% 10^(98:0)

```

This yields

```
0 0 0 ... 1 2 7 6

```

which is exactly the representation we want. In the code, we end up wanting to use `10^(98:0)` again later, so we assign it to a variable:

```
abs(x) %% 10^(99:1) %/% (e = 10^(98:0))

```

(Wrapping an expression in parentheses in R generally evaluates the expression (in this case, assigning the value of `10^(98:0)` to `e`), and then also returns the output of the expression, allowing us to embed variable assignments within other calculations.)

Next, we perform pairwise multiplication of the digits in the input. The output is then padded to two digits and concatenated. The padding to two digits and concatenating is equivalent to multiplying each number by `10^n`, where `n` is the distance from the right edge, and then summing all the numbers.

```
 A = 0         0         1         2         7         6
 B = 9         9         3         0         2         4
 ->  0         0         3         0        14        24
 -> 00        00        03        00        14        24
 ->  0*10^6 +  0*10^5 +  3*10^4 +  0*10^3 + 14*10^2 + 24*10^1
 =  000003001424

```

Notably, because multiplication is commutative, we can perform the multiplication by `10^n` *before* we multiply **A** by **B**. So, we take our earlier calculation and multiply by `10^(98:0)`:

```
abs(x) %% 10^(99:1) %/% 10^(98:0) * 10^(98:0)

```

which is equivalent to

```
abs(x) %% 10^(99:1) %/% (e = 10^(98:0)) * e

```

After applying this to **A**, we would then want to repeat this whole operation on **B**. But that takes precious bytes, so we define a function so we only have to write it once:

```
s = function(x) abs(x) %% 10^(99:1) %/% (e=10^(98:0)) * e

```

We do our embedding-in-parentheses trick to allow us to define and apply a function at the same time, to call this function on **A** and **B** and multiply them together. (We could have defined it on a separate line, but because we're eventually going to put all of this into an anonymous function, if we have more than one line of code then everything needs to be wrapped in curly braces, which costs valuable bytes.)

```
(s = function(x) abs(x) %% 10^(99:1) %/% (e=10^(98:0)) * e)(a) * s(b)

```

And we take the sum of all of this, and we're nearly finished:

```
sum((s = function(x) abs(x) %% 10^(99:1) %/% (e=10^(98:0)) * e)(a) * s(b))

```

The only thing to consider now is the sign of the input. We want to follow regular multiplication rules, so if one and only one of **A** and **B** is negative, the output is negative. We use the function `sign` which returns `1` when given a positive number and `-1` when given a negative number, to output a coefficient that we multiply our entire calculation by:

```
sum((s = function(x) abs(x) %% 10^(99:1) %/% (e=10^(98:0)) * e)(a) * s(b)) * sign(a * b)

```

Finally, the whole thing is wrapped into an anonymous function that takes `a` and `b` as input:

```
function(a, b) sum((s = function(x) abs(x) %% 10^(99:1) %/% (e=10^(98:0)) * e)(a) * s(b)) * sign(a * b)

```

Remove the whitespace and it's 86 bytes.

# Answer
> 1 votes
## Mathematica 66 Bytes

```
i=IntegerDigits;p=PadLeft;FromDigits@Flatten@p[i/@Times@@p[i/@#]]&

```

Ungolfed:

```
IntegerDigits/@{1276,933024}
PadLeft[%]
Times@@%
IntegerDigits/@%
PadLeft[%]
Flatten@%
FromDigits@%

```

where % means the previous output yields

```
{{1,2,7,6},{9,3,3,0,2,4}}
{{0,0,1,2,7,6},{9,3,3,0,2,4}}
{0,0,3,0,14,24}
{{0},{0},{3},{0},{1,4},{2,4}}
{{0,0},{0,0},{0,3},{0,0},{1,4},{2,4}}
{0,0,0,0,0,3,0,0,1,4,2,4}
3001424

```

# Answer
> 1 votes
# Python 3, ~~92 bytes~~, 119 bytes

```
lambda m,n:(1-(n*m<0)*2)*int(''.join([f"{int(a)*int(b):02}"for a,b in zip(str(abs(n))[::-1],str(abs(m))[::-1])][::-1]))

```

Try it online!

*Fix for handling negative numbers cost 29 bytes :/*

# Answer
> 1 votes
# Julia, ~~70~~ 64 bytes

Big thanx to @MarcMush for his advices!

```
~=digits∘abs
a\b=evalpoly(big(100),prod.(zip(~a,~b)))sign(a*b)
```

Attempt This Online!

# Answer
> 1 votes
# 05AB1E, 9 bytes

```
Tвí0ζPRтβ

```

Port of *@user62131*'s Jelly answer

Try it online or verify all test cases.

**Explanation:**

```
Tв        # Convert both integers in the (implicit) input-pair to a base-10 list
  í       # Reverse each inner list
    ζ     # Zip/transpose; swapping rows/columns,
   0      # using 0 as filler for unequal length lists
     P    # Take the product of each inner pair
      R   # Reverse the list of integers
       тβ # Convert it from a base-100 list to a base-10 integer
          # (after which the result is output implicitly)

```

# Answer
> 0 votes
## Pyke, 16 bytes

```
FY_),FBw�+`t)_sb

```

Try it here!

Where � is the byte `0x84` or `132`

# Answer
> 0 votes
# PHP, 84 bytes

```
for(list(,$a,$b)=$argv,$f=1;$a>=1;$a/=10,$b/=10,$f*=100)$r+=$a%10*($b%10)*$f;echo$r;

```

slightly longer with string concatenation (86 bytes):

```
for(list(,$a,$b)=$argv;$a>=1;$a/=10,$b/=10)$r=sprintf("%02d$r",$a%10*($b%10));echo+$r;

```

# Answer
> 0 votes
## Racket 325 bytes

```
(let*((g string-append)(q quotient/remainder)(l(let p((a(abs a))(b(abs b))(ol'()))(define-values(x y)(q a 10))
(define-values(j k)(q b 10))(if(not(= 0 x j))(p x j(cons(* y k)ol))(cons(* y k)ol)))))(*(string->number
(apply g(map(λ(x)(let((s(number->string x)))(if(= 2(string-length s)) s (g "0" s))))l)))(if(<(* a b)0)-1 1)))

```

Ungolfed:

```
(define (f a b)
  (let* ((sa string-append)
         (q quotient/remainder)
         (ll (let loop ((a (abs a))
                        (b (abs b))
                        (ol '()))
               (define-values (x y) (q a 10))
               (define-values (j k) (q b 10))
               (if (not(= 0 x j))
                   (loop x j (cons (* y k) ol))
                   (cons (* y k) ol)))))
    (*(string->number (apply sa
                             (map (λ (x)
                                    (let ((s (number->string x)))
                                      (if (= 2 (string-length s))
                                          s
                                          (sa "0" s))))
                                  ll)))
      (if (< (* a b) 0) -1 1))))

```

Testing:

```
(f 1276 933024)
(f 302 40)
(f 0 6623)
(f 63196 21220)
(f 20643 -56721)

```

Output:

```
3001424
0
0
1203021800
-1000420803

```

# Answer
> 0 votes
# Perl 5 `-MList::Util=min`, 140 bytes

```
@a=<>=~/\S/g;@F=<>=~/\S/g;$q=1+min$#a,$#F;say+('-'x("@a@F"=~y/-//%2).sprintf'%02d'x$q,map$F[$_]*$a[$_],-$q..-1)=~s/^-?\K0+//r=~s/^-0*$//r||0

```

Try it online!

# Answer
> 0 votes
# PowerShell, ~~153~~ 151 bytes

```
param($a,$b)do{$x,$y=$a[--$i],$b[$i]|%{if($_-eq45){$s+=$_;$_=0}$_}
$r=(+"$x"*"$y"|% t*g "00")+$r}while($x+$y)$s+$r-replace'(?<!\d)0+(?=\d)|--|-(?=0+$)'

```

Try it online!

Less golfed:

```
param($a,$b)
do{
    $x,$y=$a[--$i],$b[$i]|%{
        if($_-eq45){                                # [char]45 is '-'
            $signs+=$_
            $_=0
        }
        $_                                          # a digit or $null
    }
    $res=(+"$x"*"$y"|% toString "00")+$res          # "00" is the custom format to get 2-digit number
}
while($x+$y)
$signs+$res-replace'(?<!\d)0+(?=\d)|--|-(?=0+$)'    # cleanup and return

```

---
Tags: code-golf, string, arithmetic
---


# Question
Title: Largest Number in Brainfuck BigInt for each program length up to 50 instructions
This challenge is for the largest finite number you can get BrainFuck programs of given lengths to contain in memory.

We must use one of the BF versions that uses big integers for the cells rather than byte values as not to be capped at 255. Do not use negative positions and values in memory. Do not use the BF instruction to input memory, also the output instruction is not needed.

---

Challenge:

Write Brainfuck programs with lengths from 0 to 50. Your score is the sum of each programs maximum value in memory.

---

As they may well be trivial feel free to omit the programs listed below and start from a length of 16, I'll use the following for the smaller sizes:

Length, Score, Program

```
 0,  0
 1,  1, +
 2,  2, ++
 3,  3, +++
Pattern Continues
10, 10, ++++++++++
11, 11, +++++++++++
12, 12, ++++++++++++
13, 16, ++++[->++++<]
14, 20, +++++[->++++<]
15, 25, +++++[->+++++<]

```

Total Score: 139

---

Related but different:

Large Numbers in BF

Largest Number Printable

Busy Brain Beaver

See the comments below for more info.

---

---

The combined results so far, being the sum of the best of each size:

```
length: 16 to 24
by sligocki

100, 176, 3175, 3175, 4212
4212, 6234, 90,963, 7,467,842

```

---

```
length: 25 to 30
by sligocki

```

239,071,921

---

```
length: 31, 32, 33, (34 to 37)
by sligocki

        380,034,304
     30,842,648,752
 39,888,814,654,548
220,283,786,963,581

```

---

```
length: 38
based on code by l4m2, by alan2here

```

(4 ^ 1366 - 4) / 3

---

```
length: 39 to 47
based on code by l4m2, by alan2here

```

Σ (n = 4 to 12) of (fn(0) | f(x) := (4x+2 \- 4) / 3)

---

```
length: 48
based on code by l4m2, by alan2here

```

(172) - 2

---

```
length: 49, 50
by l4m2

(<sup>21</sup>2) - 2
(<sup>26</sup>2) - 2

```

# Answer
> 6 votes
# (262)-2

```
+++++[->+++++<]>[->+[->+[->++<]>[-<+>]<<]<[->+<]>]

```

Where (42) = 2222

# f20(0), where f(x):=(4x+2-4)/3

```
++++[->+++++<]>[->+[->+[->++<]>[-<++>]<<]<[->+<]>]

```

# Answer
> 5 votes
There's been a lot posted about the top of the range (size ~ 50). But here are some high-scoring programs near the bottom:

* Size 16: `+[->++++++[-<]>]` scores 100
* Size 20: `+[->++++++++++[-<]>]` scores 4,212
* Size 28: `+[->++++++++++++++++++[-<]>]` scores 804,576

In general, if we parameterize it so that there are N+1 `+`s in the middle, then this simulates the "Collatz-like" iteration:

* $$C(2k) \to Halt(Nk)$$
* $$C(2k+1) \to C(N(k+1))$$

Where C(m) = `[0, *m*, 0 ...]` (Data pointer looking at value m, at least one zero to the left, infinite 0s to the right).

It turns out that for $$N = 2^m + 1$$ this iterates exactly m+2 times (starting from C(1)) and scores

$$\frac{N}{2} (\frac{N^{m+1} - 2^{m+1}}{N - 2} + 1) \approx \frac{N^{m+1}}{2} \approx N^{\log\_2(N)}$$

points using N + 12 size.

# Answer
> 3 votes
total: (≈ & \>) 172

more detail:

```
length: 0 to 12
see question
total: 78

```

---

```
length: 13 to 24
N × N
(N + 1) × N
16, 20, 25, 30, 36, 42, 49, 56, 64, 72, 81, 90

++++[->++++<]
+++++[->++++<]
+++++[->+++++<]
Pattern Continues
+++++++++[->++++++++<]
+++++++++[->+++++++++<]
++++++++++[->+++++++++<]

total: 581

```

total so far: 659

---

each yeild: fn(0) | f(x) = x × m + 1

```
length: 25
(m, n) = (5, 4)
156
>+>+>+>+<[>[-<+++++>]<<]>

length: 26
(m, n) = (4, 5)
341
>+>+>+>+>+<[>[-<++++>]<<]>

total: 497

```

total so far: 1156

---

each yeild: fr or (r × s)(0) | f(x) = (x + 1) × (p × q)

```
length: 27
(p, q, r) = (2, 2, 5)
1364
+++++[->+[->++<]>[-<++>]<<]

length: 28
(p, q, r) = (2, 2, 6)
5460
++++++[->+[->++<]>[-<++>]<<]

length: 29
(p, q, r) = (2, 2, 7)
21,844
+++++++[->+[->++<]>[-<++>]<<]

length: 30
(p, q, r) = (2, 2, 8)
87,380
++++++++[->+[->++<]>[-<++>]<<]

total: 116,048

```

total so far: 117,204

```
length: 37
(p, q, r, s) = (2, 3, 4, 4)
(≈ & >) (6 ^ 16 = 1,721,598,279,680)
++++[->++++<]>
[->+[->+++<]>[-<++>]<<]

total: (≈ & >) 1,721,598,279,680

```

total so far: (≈ & \>) 1,721,598,396,884

---

Based a design by l4m2

each yeild: fn(0) | f(x) = (4x + 2 \- 4) / 3

```
length: 38
n = 4
+++[->+[->+[->++<]>[-<++>]<<]<[->+<]>]

length: 39
n = 4
++++[->+[->+[->++<]>[-<++>]<<]<[->+<]>]

length: 40
n = 5
+++++[->+[->+[->++<]>[-<++>]<<]<[->+<]>]

length: 41
n = 6
++++++[->+[->+[->++<]>[-<++>]<<]<[->+<]>]

length: 42
n = 7
+++++++[->+[->+[->++<]>[-<++>]<<]<[->+<]>]

length: 43
n = 8
++++++++[->+[->+[->++<]>[-<++>]<<]<[->+<]>]

length: 44
n = 9
+++++++++[->+[->+[->++<]>[-<++>]<<]<[->+<]>]

length: 45
n = 10
++++++++++[->+[->+[->++<]>[-<++>]<<]<[->+<]>]

length: 46
n = 11
+++++++++++[->+[->+[->++<]>[-<++>]<<]<[->+<]>]

length: 47
n = 12
++++++++++++[->+[->+[->++<]>[-<++>]<<]<[->+<]>]

```

---

```
Based a design by l4m2
length: 48
++++[->++++<]>[->+[->+[->++<]>[-<+>]<<]<[->+<]>]

total: <sup>17</sup>2 - 2

```

---

---

```
Honorary Mention
(3 × 3) ^ 4
>+<++++[->[->+++<]>[-<+++>]<<]

```

# Answer
> 1 votes
# Revision!

Even bigger numbers now!

```
++++++++[>+>>++++++++[<<[>+++<-]>[<++++>-]>-]<<<-]

```

Result: 1.1684220603446423e+69 or 116842206034464220000000000000000000000000000000000000000000000000000 (At least that's what the compiler says)

# How?

How this works is that repeats the assignment v=v(4\*3)^v 8 times(At least that's what I intended it to do.

# Answer
> 1 votes
Just found a more powerful family of programs in the 16-33 size range. These are programs that look like `++[>+++++[-<]>>]` (M+1 `+`s at start and N+1 `+`s in middle).

Here are all the ones that beat existing champions (IIUC).

```
Size 16 / Params M= 1 N= 4 / Score =                  176 / ++[>+++++[-<]>>]
Size 17 / Params M= 1 N= 5 / Score =                3,175 / ++[>++++++[-<]>>]
Size 21 / Params M= 2 N= 8 / Score =                6,234 / +++[>+++++++++[-<]>>]
Size 22 / Params M= 2 N= 9 / Score =               90,963 / +++[>++++++++++[-<]>>]
Size 23 / Params M= 2 N=10 / Score =            7,467,842 / +++[>+++++++++++[-<]>>]
Size 24 / Params M= 2 N=11 / Score =          239,071,921 / +++[>++++++++++++[-<]>>]
Size 30 / Params M= 3 N=16 / Score =          380,034,304 / ++++[>+++++++++++++++++[-<]>>]
Size 31 / Params M= 3 N=17 / Score =       30,842,648,752 / ++++[>++++++++++++++++++[-<]>>]
Size 32 / Params M= 3 N=18 / Score =   39,888,814,654,548 / ++++[>+++++++++++++++++++[-<]>>]
Size 33 / Params M= 3 N=19 / Score =  220,283,786,963,581 / ++++[>++++++++++++++++++++[-<]>>]

```

Note: These programs all go one spot to left of the starting memory location ... if you want to disallow that, you'll need to prepend them with `>`.

This program follows the recurrence:

```
Start -> [M, N*]
[b+k,  b*]  -> Halt(max(Nb, k))
[a,   a+k+1*] -> [k, N(a+1)*]

```

In other words: if the register to the left has an equal or larger value, it will halt. If current register has greater value, iterate like the second line. All of these recurrences seem to eventually halt, but I don't have any deeper insight yet ...

---
Tags: number, brainfuck, busy-beaver
---