title: Weapons of Math Instruction

text:
# Question
Title: Weapons of Math Instruction
Last time when I tried to come up with something easy that wasn't a duplicate, it ended up being way too hard.. So hopefully this time it's indeed something newcomers can try as well.

**Input:**

An array/list with integers/decimals. (Or a string representing an array with integers/decimals.)

**Output:**

Loop through the numbers and apply the following five mathematical operands in this order:

* Addition (`+`);
* Subtraction ();
* Multiplication (`*` or `×` or `·`);
* *Real / Calculator* Division (`/` or `÷`);
* Exponentiation (`^` or `**`).

(NOTE: The symbols between parenthesis are just added as clarification. If your programming language uses a completely different symbol for the mathematical operation than the examples, then that is of course completely acceptable.)

Keep continuing until you've reached the end of the list, and then give the result of the sum.

**Challenge rules:**

* Exponentiation by 0 (`n ^ 0`) should result in 1 (this also applies to `0 ^ 0 = 1`).
* There are no test cases for division by 0 (`n / 0`), so you don't have to worry about that edge-case.
* If the array contains just a single number, we return that as the result.

**General rules:**

* This is , so shortest answer in bytes wins.
Don't let code-golf languages discourage you from posting answers with non-codegolfing languages. Try to come up with an as short as possible answer 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.

**Test cases:**

```
[1,2,3,4,5] -> 0
-> 1 + 2 = 3
  -> 3 - 3 = 0
    -> 0 * 4 = 0
      -> 0 / 5 = 0

[5,12,23,2,4,4,2,6,7] -> 539
-> 5 + 12 = 17
  -> 17 - 23 = -6
    -> -6 * 2 = -12
      -> -12 / 4 = -3
        -> -3 ^ 4 = 81
          -> 81 + 2 = 83
            -> 83 - 6 = 77
              -> 77 * 7 -> 539

[-8,50,3,3,-123,4,17,99,13] -> -1055.356...
-> -8 + 50 = 42
  -> 42 - 3 = 39
    -> 39 * 3 = 117
      -> 117 / -123 = -0.9512...
        -> -0.9512... ^ 4 = 0.818...
          -> 0.818... + 17 = 17.818...
            -> 17.818... - 99 -> -81.181...
              -> -81.181... * 13 = -1055.356...

[2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2] -> 256
-> 2 + 2 = 4
  -> 4 - 2 = 2
    -> 2 * 2 = 4
      -> 4 / 2 = 2
        -> 2 ^ 2 = 4
          -> 4 + 2 = 6
            -> 6 - 2 = 4
              -> 4 * 2 = 8
                -> 8 / 2 = 4
                  -> 4 ^ 2 = 16
                    -> 16 + 2 = 18
                      -> 18 - 2 = 16
                        -> 16 * 2 = 32
                          -> 32 / 2 = 16
                            -> 16 ^ 2 = 256

[1,0,1,0,1,0] -> 1
-> 1 + 0 = 1
  -> 1 - 1 = 0
    -> 0 * 0 = 0
      -> 0 / 1 = 0
        -> 0 ^ 0 = 1

[-9,-8,-1] -> -16
  -> -9 + -8 = -17
    -> -17 - -1 = -16

[0,-3] -> -3
  -> 0 + -3 = -3

[-99] -> -99

```

# Answer
# Jelly, 13 bytes

```
“+_×÷*”ṁṖ⁸żFV

```

Try it online! or verify all test cases.

### How it works

```
“+_×÷*”ṁṖ⁸żFV  Main link. Argument: A (list of integers)

“+_×÷*”        Yield the list of operations as a string.
        Ṗ      Yield A popped, i.e., with its last element removed.
       ṁ       Mold; reshape the string as popped A.
               This repeats the characters of the string until it contains
               length(A)-1 characters.
         ⁸ż    Zipwith; pairs the integers of A with the corresponding characters.
           F   Flatten the result.
            V  Eval the resulting Jelly code.
               Jelly always evaluates left-to-right (with blatant disregard towards
               the order of operations), so this returns the desired result.

```
> 7 votes

# Answer
# Javascript ES7 49 bytes

```
a=>a.reduce((c,d,e)=>[c**d,c+d,c-d,c*d,c/d][e%5])

```

Saved 9 bytes thanks to Dom Hastings, saved another 6 thanks to Leaky Nun

Uses the new exponentiation operator.
> 19 votes

# Answer
# Haskell, ~~76~~ ~~65~~ ~~64~~ 62 bytes

Thanks to @Damien for removing another two bytes=)

```
f(u:v)=foldl(\x(f,y)->f x y)u(zip(v>>[(+),(-),(*),(/),(**)])v)

```

This uses the `>>` which here just appends the list `[(+),...]` to itself `length v` times. The rest still works still the same as the old versions.

Old versions:

These solutions make use of the infinite lists, as `cycle[...]` just repeats the given list infinitely. Then it basically gets `zip`ed with the list of numbers, and we just `fold` (*reduce* in other languages) the zipped list via a lambda, that applies the operators to the accumulator/current list element.

```
f(u:v)=foldl(\x(f,y)->f x y)u(zip(cycle[(+),(-),(*),(/),(**)])v)

f(u:v)=foldl(\x(y,f)->f x y)u(zip v(cycle[(+),(-),(*),(/),(**)]))

f l=foldl(\x(y,f)->f x y)(head l)(zip(drop 1l)(cycle[(+),(-),(*),(/),(**)]))

```
> 11 votes

# Answer
## Pyke, ~~22~~ 21 bytes

```
lt5L%"+-*/^"L@\RJQ_XE

```

Try it here!

```
lt5L%                 -    map(len(input)-1, %5)
     "+-*/^"L@        -   map(^, "+-*/^"[<])
              \RJ     -  "R".join(^)
                    E - pyke_eval(^, V)
                 Q_X  -  splat(reversed(input))

```
> 8 votes

# Answer
# TSQL ~~116~~ ~~115~~ 88 bytes

Thanks to Ross Presser suggestion I was able to golf this down to 88 characters

```
-- In Try-it code, this must be DECLARE @y TABLE
CREATE TABLE T(a real, i int identity)
INSERT T values(5),(12),(23),(2),(4),(4),(2),(6),(7)

DECLARE @ REAL SELECT @=CHOOSE(i%5+1,@/a,ISNULL(POWER(@,a),a),@+a,@-a,@*a)FROM T
PRINT @

```

Try it online
> 7 votes

# Answer
# Haskell, 61 Bytes

```
foldl(flip id)0.zipWith flip((+):cycle[(+),(-),(*),(/),(**)])

```

Creates a series of transformations in a list, as in \[add 1, add 2, subtract 3, ...\], starting with 2 additions because we start with 0 in the fold. Next, we do what I call the List Application Fold, or foldl (flip id), which applies a list of homomorphisms in series. This starts with zero, adds the initial value, then does all of the above computed transformations to get a final result.

Note that (flip id) is the same as (\x y-\>y x), just shorter.

Sample usage:

```
f = foldl(flip id)0.zipWith flip((+):cycle[(+),(-),(*),(/),(**)])
f [1,2,3,4,5] -- Is 0.0

```
> 7 votes

# Answer
# Pyth, ~~27~~ ~~26~~ 25 bytes

```
.v+>tlQ*lQ"^c*-+":jdQ\-\_

```

Test suite.

Pyth uses prefix notation: `1+2` is written as `+1 2` (space needed to separate numbers).

Therefore, for the first testcase, the expression would be `(((1+2)-3)*4)/5`, which in prefix notation, would be written as `/*-+ 1 2 3 4 5`.

In Pyth, float division is `c` instead of `/`, so it becomes `c*-+ 1 2 3 4 5`.

Also, in Pyth, `-100` is written as `_100` instead.

Therefore, for the third test case, which is `((((((((-8+50)-3)*3)/-123)^4)+17)-99)*13)`, it becomes: `*-+^c*-+ _8 50 3 3 _123 4 17 99 13`.

```
.v+>tlQ*lQ"^c*-+":jdQ\-\_
                  jdQ       Join input by space.
                 :   \-\_   Replace "-" with "_".
   >tlQ*lQ"^c*-+"           Generate the string "...^c*-+" of suitable length.
  +                         Join the two strings above.
.v                          Evaluate as a Pyth expression.

```

## History
> 6 votes

# Answer
## Actually, 23 bytes

```
;l"+-*/ⁿ"*@R':j':+'?o+ƒ

```

Try it online!

Actually uses postfix notation for mathematics, and operators that only ever take two arguments (such as the operators for addition, subtraction, multiplication, division, and exponentiation) do nothing when there is only one element on the stack. Thus, turning the input into Actually code is as simple as reversing the input, formatting it as numerics, and appending the operations. Then, the resultant code can be executed, giving the desired output.

## Explanation:

```
;l"+-*/ⁿ"*@R':j':+'?o+ƒ
;l"+-*/ⁿ"*               repeat the operations a number of times equal to the length of the input
                            (since extraneous operations will be NOPs, there's no harm in overshooting)
          @R             reverse the input
            ':j          join on ":" (make a string, inserting ":" between every pair of elements in the list)
               ':+       prepend a ":" (for the first numeric literal)
                  '?o    append a "?"
                           (this keeps the poor numeric parsing from trying to gobble up the first + as part of the numeric literal, since ? isn't interpreted as part of the literal, and is a NOP)
                     +   append the operations string
                      ƒ  cast as a function and call it

```

Example of translated code for input `1,2,3,4,5`:

```
:5:4:3:2:1?+-*/ⁿ+-*/ⁿ+-*/ⁿ+-*/ⁿ+-*/ⁿ

```
> 6 votes

# Answer
# Julia, ~~53~~ 50 bytes

```
!x=(i=0;foldl((a,b)->(+,-,*,/,^)[i=i%5+1](a,b),x))

```

Try it online!
> 6 votes

# Answer
# J, 40 bytes

```
^~`(%~)`*`(-~)`+/@(|.@,7#:~#&2)(5-5|4+#)

```

Finds the number of values needed to use a multiple of 5 operators, than pads with the identity values of those operators. In order, `+` is 0, `-` is 0, `*` is 1, `%` is 1, and `^` is 1, which can be a bit value `00111`, or 7 in base 10. Then operates on that list while cycling through operators.

## Usage

```
   f =: ^~`(%~)`*`(-~)`+/@(|.@,7#:~#&2)(5-5|4+#)
   f 1 2 3 4 5
0
   f 5 12 23 2 4 4 2 6 7
539
   f _8 50 3 3 _123 4 17 99 13
_1055.36
   f 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
256
   f 1 0 1 0 1 0
1
   f _9 _8 _1
_16
   f 0 _3
_3
   f _99
_99

```

## Explanation

```
^~`(%~)`*`(-~)`+/@(|.@,7#:~#&2)(5-5|4+#) Input: A
                                      #  Get length of A
                                    4+   Add four to it
                                  5|     Take it mod 5
                                5-       Find 5 minus its value, call it x
                           #&2           Create x copies of 2
                       7#:~              Convert 7 to base 2 and take the last x digits
                      ,                  Append those x digits to the end of A
                   |.@                   Reverse it, call it A'
^~                                       Power, reversed operators
    %~                                   Division, reversed operators
       *                                 Multiplication
         -~                              Subtraction, reversed operators
            +                            Addition
             /@                          Insert the previous operations, separated by `,
                                         into A' in order and cycle until the end
                                         Then evaluate the equation from right-to-left
                                         and return

```
> 5 votes

# Answer
# Python 2, ~~81~~ ~~67~~ 64 bytes

```
i=10
for n in input():exec'r%s=n'%'*+-*/*'[i::5];i=-~i%5
print r

```

Input is an array of floats. Test it on Ideone.

### How it works

`'*+-*/*'[i::5]` selects every fifth character of the string, starting with the one at index **i**, so this yields `**` if **i = 0**, `+` if **i = 1**, `-` if **i = 2**, `*` if **i = 3** and `/` if **i = 4**. Since the string has length **6**, the expression will yield an empty string if **i \> 5**.

We initialize the variable **i** to **10**. For each number **n** in the input array, we construct the string `r<op>=n`, which `exec` executes.

Initially, **i = 10**, so `<op>` is the empty string, and it initializes **r** with `r+=n`. After each step, we increment **i** modulo **5** with `i=-~i%5`, so the next step will retrieve the proper operator.

When all input numbers has been processed, and we print **r**, which holds the desired output.
> 5 votes

# Answer
# Matlab - 95 91 85 bytes / Octave - 81 bytes

Input is in such form: `a = ['1' '2' '3' '4' '5'];`, I hope this is covered by "string representing an array with integers/decimals", else there are 2 num2str needed additionally.

Every intermediate result gets printed to console because that saves me some semicolons. `a(1)` is executed so its value is then saved to `ans`. Also of course using `ans` in code is bad practice.

```
b='+-*/^'
a(1)
for i=2:length(a)
  ['(',ans,')',b(mod(i-2,5)+1),a(i)]
end
eval(ans)

```

In Octave, `'+-*/^'(mod(i+2,5)+1)` also works, which saves another 4 bytes, thanks Adám and Luis Mendo:

```
a(1)
for i=2:length(a)
  strcat('(',ans,')','+-*/^'(mod(i-2,5)+1),a(i))
end
eval(ans)

```

Changelog:

* Removed spaces where possible
* added Octave solution
* replaced strcat() with \[\]
> 5 votes

# Answer
# Mathematica, ~~67~~ ~~66~~ 65 bytes

```
Fold[{+##,#-#2,#2#,#/#2,If[#2==0,1,#^#2]}[[i++~Mod~5+1]]&,i=0;#]&

```

Simple `Fold` with a variable `i` holding the index.
> 4 votes

# Answer
# CJam, 18 bytes

```
q~{"+-*/#"W):W=~}*

```

Input is an array of floats. Try it online!

### How it works

```
q~                  Read and evaluate all input.
  {             }*  Reduce:
   "+-*/#"            Push the string of operators.
          W           Push W (initially -1).
           ):W        Increment and save in W.
              =       Retrieve the character at that index.
               ~      Evaluate.

```
> 4 votes

# Answer
# , ~~87 78~~ 70 bytes

```
i=0
Reduce(function(a,j)get(substr("+-*/^",i<<-i%%5+1,i))(a,j),scan())

```

Try it online!
> 4 votes

# Answer
# Java 8, ~~173~~ ~~172~~ ~~167~~ ~~138~~ ~~137~~ ~~118~~ 113 bytes

```
a->{double r=a[0],t;for(int i=1;i<a.length;r=new double[]{Math.pow(r,t),r+t,r-t,r*t,r/t}[i++%5])t=a[i];return r;}

```

**Explanation:**

Try it here.

```
a->{                     // Method with double-array parameter and double return-type
  double r=a[0],         //  Result-double, starting at the first item of the input
         t;              //  Temp double
  for(int i=1;           //  Index-integer, starting at the second item
      i<a.length;        //  Loop over the input-array
      r=new double[]{    //    After every iteration, change `r` to:
         Math.pow(r,t),  //      If `i%5` is 0: `r^t`
         r+t,            //      Else-if `i%5` is 1: `r+t`
         r-t,            //      Else-if `i%5` is 2: `r-t`
         r*t,            //      Else-if `i%5` is 3: `r*t`
         r/t}[i++%5])    //      Else-if `i%5` is 4: `r/t`
                         //      And increase `i` by 1 afterwards with `i++`
    t=a[i];              //   Change `t` to the next item in the array
  return r;}             //  Return result-double

```
> 3 votes

# Answer
## Haskell - 74

```
f(x:xs)=foldl(\x(o,y)->o x y)x(zip(cycle[(+),(-),(*),(/),flip(^).floor])xs)

```

Test cases:

```
λ> f[1,2,3,4,5] -> 0.0
λ> f[5,12,23,2,4,4,2,6,7] -> 539.0
λ> f[-8,50,3,3,-123,4,17,99,13] -> -1055.356943846277
λ> f [2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2] -> 256.0

```

It could probably be shorter; Haskell's support for infinite lists and higher order functions make the direct solution quite pleasant, though. A version of `^ :: Double -> Double -> Double` would be nicer for golfing, but I couldn't find one. Thankfully, I didn't need a full lambda, so pointless style shaved off a few bytes.
> 3 votes

# Answer
# Oracle PL/SQL, ~~275~~ 254 Bytes

```
declare r number;begin for x in (select n,mod(rownum,5)r from t) loop if r is null then r:=x.n;elsif x.r=2then r:=r+x.n;elsif x.r=3then r:=r-x.n;elsif x.r=4then r:=r*x.n;elsif x.r=0then r:=r/x.n;else r:=r**x.n;end if;end loop;DBMS_OUTPUT.PUT_LINE(r);end;

```

The data must be inserted in a table called `T` with a column `N` of type `NUMBER`

Usage:

```
drop table t;
create table t (n number);
insert into t values (-8);
insert into t values (50);
insert into t values (3);
insert into t values (3);
insert into t values (-123);
insert into t values (4);
insert into t values (17);
insert into t values (99);
insert into t values (13);

declare r number;begin for x in (select n,mod(rownum,5)r from t) loop if r is null then r:=x.n;elsif x.r=2then r:=r+x.n;elsif x.r=3then r:=r-x.n;elsif x.r=4then r:=r*x.n;elsif x.r=0then r:=r/x.n;else r:=r**x.n;end if;end loop;DBMS_OUTPUT.PUT_LINE(r);end;

```

Output:

```
-1055,356943846277162152071601242992595623

```

### 275 Bytes version:

```
declare r number;cursor c is select n,mod(rownum,5) r from t;begin for x in c loop if r is null then r:=x.n;else case x.r when 2 then r:=r+x.n;when 3 then r:=r-x.n;when 4 then r:=r*x.n;when 0 then r:=r/x.n;else r:=r**x.n; end case;end if;end loop;DBMS_OUTPUT.PUT_LINE(r);end;

```
> 3 votes

# Answer
## PowerShell v2+, 124 bytes

```
param($n)$o=$n[0];if($y=$n.count-1){1..$y|%{$o=if(($x=$i++%5)-4){"$o"+'+-*/'[$x]+$n[$_]|iex}else{[math]::pow($o,$n[$_])}}}$o

```

Long because PowerShell doesn't have a `^` or `**` operator, so we have to account for a separate case and use a .NET call.

Takes input `$n` as an array, sets our output `$o` to be the first digit. We then check the `.count` of the array, and so long as it's greater than one we enter the `if`. Otherwise, we skip the `if`.

Inside the `if` we loop through the array `1..$y|%{...}` and each iteration we re-set `$o` to a new value, the result of another `if/else` statement. So long as our counter `$i++` isn't modulo-5 equal to 4 (i.e., we're not at the `^` operator), we simply take `$o` and concatenate it with the appropriate symbol `'+-*/'[$x]` and the next number in the input array `$n[$_]`. We pipe that to `iex` (alias for `Invoke-Expression` and similar to `eval`), and that gets re-saved to `$o`. If we're on the `^` operator, we're in the `else`, so we execute a `[math]::Pow()` call, and *that* result gets re-saved back into `$o`.

In either case, we simply output `$o` to the pipeline and exit, with output implicit.
> 3 votes

# Answer
# Rust, 123, 117 bytes

Original answer:

```
fn a(v:&[f32])->f32{v.iter().skip(1).enumerate().fold(v[0],|s,(i,&x)|match i%5{0=>s+x,1=>s-x,2=>s*x,3=>s/x,_=>s.powf(x)})}

```

stupid long method names ^^ ahh much better

```
fn f(v:&[f32])->f32{v[1..].iter().zip(0..).fold(v[0],|s,(&x,i)|match i%5{0=>s+x,1=>s-x,2=>s*x,3=>s/x,_=>s.powf(x)})}

```

ungolfed

```
fn f(values : &[f32]) -> f32 {
    values[1..].iter().zip(0..)
    .fold(values[0], |state,(&x,i)|
        match i%5 {
            0=>state+x,
            1=>state-x,
            2=>state*x,
            3=>state/x,
            _=>state.powf(x)
        }
    )
}

```
> 3 votes

# Answer
# Python 3, ~~88~~ 93 bytes

```
f=lambda x:eval('('*(len(x)-1)+'){}'.join(map(str,x)).format(*['+','-','*','/','**']*len(x)))

```

It started off being much shorter but then operator precedence defeated me and I had to include lots of parenthesis...
> 3 votes

# Answer
# Perl 6,  ~~70 68 65~~  62 bytes

```
~~{$/=[(|(&[+],&[-],&[*],&[/],&[**])xx*)];.reduce: {$/.shift.($^a,$^b)}}
{(@_ Z |(&[+],&[-],&[*],&[/],&[**])xx*).flat.reduce: {&^b($^a,$^c)}}
{(@_ Z |(*+*,*-*,&[*],*/*,&[**])xx*).flat.reduce: {&^b($^a,$^c)}}~~
{reduce {&^b($^a,$^c)},flat @_ Z |(*+*,*-*,&[*],*/*,&[**])xx*}
```

### Explanation:

```
-> *@_ {
  reduce
    -> $a, &b, $c { b($a,$c) },

    flat       # flatten list produced from zip
      zip
        @_,    # input

        slip(  # causes the list of operators to flatten into the xx list

          # list of 5 infix operators
          &infix:<+>, &infix:<->, &infix:<*>, &infix:</>, &infix:<**>

        ) xx * # repeat the list of operators infinitely
}

```

Technically `* + *` is a Whatever lambda, but is effectively the same as `&[+]` which is short for `&infix:<+>` the set of subroutines that handle infix numeric addition.
I didn't use that for multiplication or exponentiation as the ways to write them like that is at least as long as what I have (`*×*` or `* * *` and `* ** *`)

### Test:

Test it on ideone.com
(after they upgrade to a Rakudo version that isn't from a year and a half before the official release of the Perl 6 spectests)

```
#! /usr/bin/env perl6

use v6.c;
use Test;

my @tests = (
  [1,2,3,4,5] => 0,
  [5,12,23,2,4,4,2,6,7] => 539,
  [-8,50,3,3,-123,4,17,99,13] => -1055.35694385, # -2982186493/2825761
  [2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2] => 256,
  [1,0,1,0,1,0] => 1,
  [-9,-8,-1] => -16,
  [0,-3] => -3,
  [-99] => -99,
);

plan +@tests;

my &code = {reduce {&^b($^a,$^c)},flat @_ Z |(*+*,*-*,&[*],&[/],&[**])xx*}

for @tests -> $_ ( :key(@input), :value($expected) ) {
  is code(@input), $expected, .gist
}

```

```
1..8
ok 1 - [1 2 3 4 5] => 0
ok 2 - [5 12 23 2 4 4 2 6 7] => 539
ok 3 - [-8 50 3 3 -123 4 17 99 13] => -1055.35694385
ok 4 - [2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2] => 256
ok 5 - [1 0 1 0 1 0] => 1
ok 6 - [-9 -8 -1] => -16
ok 7 - [0 -3] => -3
ok 8 - [-99] => -99

```
> 3 votes

# Answer
A few tricks can reduce @Willmore´s approach by 23 to 174 bytes (requires php 5.6 or later). The most saving part is removing unneccessary parentheses (-10 bytes).

> function f($a){while(count($a)\>1){$l=array\_shift($a);$r=array\_shift($a);array\_unshift($a,($j=$i++%5)?($j==1?$l-$r:($j==2?$l\*$r:($j==3?$l/$r:$l\**$r))):$l+$r);}return end($a);}

But using the `**` operator instead of `pow()` also allows to use `eval` with an array for the operations; and with a few more tricks ...

# PHP \>= 5.6, 82 bytes

```
while(--$argc)eval('$x'.['/','**','+','-','*'][$i++?$i%5:2]."=$argv[$i];");echo$x;

```

takes list from command line parameters. Run with `php -nr '<code>'` or try it online.

## old version, ~~161 157 151 145 144 140 137~~ 117 bytes

```
function f($a){while(count($a)>1)eval('$a[0]=array_shift($a)'.['+','-','*','/','**'][$i++%5].'$a[0];');return$a[0];}

```

The most effective golfing came from writing the intermediate result directly to the first element - after shifting the previous result from the array.

**breakdown**

```
function f($a)
{
    while(count($a)>1)  // while array has more than one element ...
        eval('$a[0]='                           // future first element :=
            . 'array_shift($a)'                 // = old first element (removed)
            . ['+','-','*','/','**'][$i++%5]    // (operation)
            .'$a[0];'                           // new first element (after shift)
        );
    return$a[0];        // return last remaining element
}

```

**test suite**

```
$cases = array (
    0=>[1,2,3,4,5],
    539=>[5,12,23,2,4,4,2,6,7],
    '-1055.356...' => [-8,50,3,3,-123,4,17,99,13],
    256 => [2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2],
    1 => [1,0,1,0,1,0],
    -16 => [-9,-8,-1],
    -3 => [0, -3],
    -99 => [-99]
);
echo '<table border=1><tr><th>values</th><th>expected</th><th>actual result</th></tr>';
foreach ($cases as $expect=>$a)
{
    $result=f($a);
    echo "<tr><td>[", implode(',',$a),"]</td><td>$expect</td><td>$result</td></tr>";
}
echo '</table>';

```
> 3 votes

# Answer
# PHP, ~~135~~ 130 bytes

Thanks @titus, -5 bytes, plus 0 case fix!

```
function f($z){return array_reduce($z,function($c,$x)use(&$i){eval('$c'.['/','**','+','-','*'][$i++?$i%5:5].'=$x;');return$c;});};

```

Try it online!

Less golfy:

```
function f( $t ) {
    return array_reduce( $t,
        function( $c, $x ) use( &$i ) {
            eval('$c'.['/','**','+','-','*'][$i++?$i%5:5].'=$x;');
            return $c;
        }
    );
};

```

Was really rooting for array\_reduce() to work for this, but requires too many chars to beat the current lowest PHP score.

Posting it anyway in case anyone has any suggestions!
> 3 votes

# Answer
# Brachylog, 68 bytes

```
hI,?bL,1:+:-:*:/:^b:L:I{bhv?t.|[O:L:I]h$(P,LbM,OhA,Lh:Ir:A&:M:Pr&.}.

```

That's long… but it uses no evaluation predicate.

### Explanation

* Main predicate

```
hI,                                  Unify I with the first element of the input
   ?bL,                              L is the input minus the first element
       1:+:-:*:/:^b                  Construct the list of predicates [+:-:*:/:^]
                   :L:I{...}.        Call predicate 1 with [[+:-:*:/:^]:L:I] as input

```
* Predicate 1

```
bhv?t.                               If the second element of Input is empty (i.e. L),
                                     unify Output with the last element of Input
|                                    Or
[O:L:I]                              Input = [O:L:I]
       h$(P,                         P is O circularly permutated to the left
            LbM,                     M is L minus the first element
                OhA,                 A is the first element of O
                    Lh:Ir:A&         Call predicate A on [I:First element of L]
                            :M:Pr&.  Call predicate 1 recursively with P:M:

```
> 2 votes

# Answer
# APL (Dyalog Unicode), ~~29~~ 27 bytes<sup>SBCS</sup>

Anomymous tacit prefix function. Note that `*` is exponentiation in APL.

```
≢{⍎3↓⍕⌽⍵,¨⍨⍺⍴'+-×÷*',¨'⍨'}⊢

```

Try it online!

Because APL executes right to left, we can just reverse the order of arguments of the inserted operations and reverse the entire expression. Postfix  reverses arguments. After doing a perfect shuffle of numbers and operations, we only just need to reverse, flatten, and evaluate:

`≢{``}⊢` call the following function with count of and actual numbers as  and :

`'⍨'` this character

`'+-×÷*',¨` prepend each of these characters to that; `["+⍨","-⍨","×⍨","÷⍨","*⍨"]`

`⍺⍴` use the left argument (count of numbers) to cyclically **r**eshape that

reverse

format as flat string

`3↓` drop leading 3 characters (a space and a symbol and )

execute as APL code
> 2 votes

# Answer
# x86-16 + 8087 FPU, 65 bytes

```
00000000: 9bdf 04ad 499b de04 ad49 e334 9bde 24ad  ....I....I.4..$.
00000010: 49e3 2d9b de0c ad49 e326 9bde 34ad 49e3  I.-....I.&..4.I.
00000020: 1fad 919b d9e8 85c9 7413 9c7f 02f7 d99b  ........t.......
00000030: d8c9 e2fb 9d7d 069b d9e8 9bd8 f191 e2c5  .....}..........
00000040: c3                                       .

```

Callable function: input array at `DS:SI`, length in `CX`. Output to `ST` top 8087 register stack.

Listing:

```
9B DF 04    FILD    WORD PTR [SI]   ; load first item to 8087 stack
AD          LODSW
49          DEC     CX

        CALC:
            ; Add
9B DE 04    FIADD   WORD PTR [SI]   ; add
AD          LODSW                   ; SI = next input
49          DEC     CX              ; decrement counter
E3 34       JCXZ    WOMI_DONE       ; exit if end of input array

            ; Subtract
9B DE 24    FISUB   WORD PTR [SI]   ; subtract
AD          LODSW                   ; SI = next input
49          DEC     CX
E3 2D       JCXZ    WOMI_DONE

            ; Multiply
9B DE 0C    FIMUL   WORD PTR [SI]   ; multiply
AD          LODSW                   ; SI = next input
49          DEC     CX
E3 26       JCXZ    WOMI_DONE

            ; Divide
9B DE 34    FIDIV   WORD PTR [SI]   ; divide
AD          LODSW                   ; SI = next input
49          DEC     CX
E3 1F       JCXZ    WOMI_DONE

            ; Exponent
AD          LODSW                   ; AX = exponent, SI = next input
91          XCHG    AX, CX          ; CX = counter for loop (exponent), save CX
9B D9 E8    FLD1                    ; load 1 into ST
85 C9       TEST    CX, CX          ; is exponent pos, neg or 0?
74 13       JZ      EXP_DONE        ; exit (with value 1) if exponent is 0
9C          PUSHF                   ; save result flags for later
7F 02       JG      EXP_REP         ; if exp > 1 start calculation
F7 D9       NEG     CX              ; make exponent positive for loop
        EXP_REP:
9B D8 C9    FMUL    ST(0), ST(1)    ; multiply ST0 = ST0 * ST1
E2 FB       LOOP    EXP_REP
9D          POPF                    ; restore sign flag from earlier
7D 06       JGE     EXP_DONE        ; if exponent was neg, divide 1 by result
9B D9 E8    FLD1                    ; push 1 into numerator
9B D8 F1    FDIV    ST(0), ST(1)    ; ST0 = 1 / ST1
        EXP_DONE:
91          XCHG    AX, CX          ; restore CX

E2 C5       LOOP    CALC            ; if more input, start again

        WOMI_DONE:
C3          RET

```

Sample Output:
> 2 votes

# Answer
# Japt, 16 bytes

```
r@[XY]r"p+-*/"gZ

```

Try it online!

Explanation:

```
r@                  #Reduce the input list:
       "p+-*/"      # The list of functions to apply (offset by one due to the behavior of Z)
              gZ    # Choose the one at the current index, wrapping
  [  ]r             # Apply that function to:
   X                #  The result of the previous step
    Y               #  and the current number
                    #Implicitly return the result of the final step

```
> 2 votes

# Answer
# c#, ~~238~~, 202 bytes

```
double d(double[]a){Array.Reverse(a);var s=new Stack<double>(a);int i=0,j;while(s.Count>1){double l=s.Pop(),r=s.Pop();j=i++%5;s.Push(j==0?l+r:j==1?l-r:j==2?l*r:j==3?l/r:Math.Pow(l,r));}return s.Peek();}

```

I didn't see any c# solution so I will give one. This is my first codegolf. I started writing in c# "two months ago" (though I know Java to some extent).

It uses **Stack**

**Ungolfed and test cases**

```
using System;
using System.Collections.Generic;

class M
{
    double d(double[]a) {
        Array.Reverse(a);
        var s = new Stack<double>(a);
        int i=0,j;
        while (s.Count>1)
        {
            double l=s.Pop(),r=s.Pop();
            j=i++%5;
            s.Push(j==0?l+r:j==1?l-r:j==2?l*r:j==3?l/r:Math.Pow(l, r));
        }
        return s.Peek();
    }

    public static void Main()
    {
        int[][] a = new int[][]{
            new int[]{1,2,3,4,5},
            new int[]{5,12,23,2,4,4,2,6,7},
            new int[]{-8,50,3,3,-123,4,17,99,13},
            new int[]{2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2},
            new int[]{1,0,1,0,1,0},
            new int[]{-9,-8,-1},
            new int[]{0,-3},
            new int[]{-99}
        };

        for (int i = 0; i < a.Length; i++)
        {
            Console.WriteLine(new M().d(Array.ConvertAll(a[i], e => Convert.ToDouble(e))));
        }
        Console.ReadKey();
    }
}

```

**Output:**

```
0
539
-1055,35694384628
256
1
-16
-3
-99

```
> 1 votes

# Answer
# PHP, ~~206~~,~~198~~,197 bytes

```
function f($a){while(count($a)>1){$l=array_shift($a);$r=array_shift($a);array_unshift($a,($j=$i++%5)==0?($l+$r):($j==1?($l-$r):($j==2?($l*$r):($j==3?($l/$r):(pow($l,$r))))));}return array_pop($a);}

```

**Ungolfed**

```
<?php

function f($a)
{
    while(count($a)>1)
    {
        $l = array_shift($a); $r = array_shift($a);
        array_unshift($a,($j=$i++%5)==0?($l+$r):($j==1?($l-$r):($j==2?($l*$r):($j==3?($l/$r):(pow($l,$r))))));
    }
    return array_pop($a);
}

echo f([1,2,3,4,5])."\n";
echo f([5,12,23,2,4,4,2,6,7])."\n";
echo f([-8,50,3,3,-123,4,17,99,13])."\n";
echo f([2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2])."\n";
echo f([1,0,1,0,1,0])."\n";
echo f([-9,-8,-1])."\n";
echo f([0,-3])."\n";
echo f([-99])."\n";

```

In PHP, logic similar to my c# answer (**202 bytes**) :) .
> 1 votes

# Answer
# Emacs Lisp, 127 bytes

```
(lambda(x)(let((f'(+ - * / expt))(a(float(car x)))(x(cdr x)))(dotimes(i(length x)a)(set'a(funcall(nth(mod i 5)f)a(nth i x))))))

```

Ungolfed:

```
(lambda(x)
  (let ((f'(+ - * / expt))  ; list of functions in order they are called
        (a (float (car x))) ; initial value
        (x (cdr x)))        ;
    (dotimes (i (length x) a)
      (set 'a (funcall (nth (mod i 5) f) ; call the i % 5th function
                       a                 ; with accumulator
                       (nth i x))))))    ; and the ith value

```

Testcases:

```
(-map
  (lambda(x)(let((f'(+ - * / expt))(a(float(car x)))(x(cdr x)))(dotimes(i(length x)a)(set'a(funcall(nth(mod i 5)f)a(nth i x))))))
  '((1 2 3 4 5)
    (5 12 23 2 4 4 2 6 7)
    (-8 50 3 3 -123 4 17 99 13)
    (2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2)
    (1 0 1 0 1 0)
    (-9 -8 -1)
    (0 -3)
    (-99)))

```

Output:

```
(0.0 539.0 -1055.356943846277 256.0 1.0 -16.0 -3.0 -99.0)

```
> 1 votes

# Answer
# Ruby, 57 bytes

```
->a{i=0;a.reduce{|x,y|x.send %w[** + - * /][(i+=1)%5],y}}

```

Try it online!

Takes an array of floats, but also works with integers, as long as all division results are integer.

At first, I tried fiddling with `eval` which looks like the obvious approach, but it gets rather verbose. Instead, I opted for `send`, which is basically Ruby's way to call methods by names, so that `x.send("+",y)` is equivalent to `x+y`.
> 1 votes

# Answer
# shell script, ~~157~~ ~~135~~ ~~133~~ ~~130~~ ~~124~~ ~~99~~ ~~95~~ ~~88~~ ~~85~~ 81 bytes

golfed (bash/non-posix) - 81 bytes

```
f()(A=$1;S=+-*/^;shift;for B;{ C=${S:((I++%5)):1};A=`bc -l<<<$A$C$B`;};echo $A)

```

golfed (portable/posix, using 'cut'-operator) - 118 bytes

```
f()(S=+-x/^;A=$1;shift;for B;do C=`echo $S|cut -b1`;S=`echo $S|cut -b2-5`;S="$S$C";A=`echo $A$C$B|bc -l`;done;echo $A)

```

golfed (portable/posix, with builtins) - 124 bytes

```
f()(A=$1;shift;for B;do case $I in 1)C=-;;2)C=*;;3)C=/;;4)C=^;;*)C=+;I=;;esac;I=$((I+1));A=`echo $A$C$B|bc -l`;done;echo $A)

```

ungolfed (posix - with builtins):

```
A=$1
shift
for B;do
case $I in
1)C=-;;
2)C=*;;
3)C=/;;
4)C=^;;
*)C=+;I=
esac
I=$((I+1))
A=`echo $A$C$B|bc -l`
done
echo $A

```

ungolfed (posix - with 'cut'):

```
S=+-x/^
A=$1
shift
for B;do
C=`echo $S|cut -b1`
S=`echo $S|cut -b2-5`
S="$S$C"
A=`echo $A$C$B|bc -l`
done
echo $A

```

This is *unfair*!
We don't have real division in language 'sh',
so we must use 'bc' which is...lame 8-)
**hint:** your directory must have no files, otherwise the asterisk expands to filenames (◔\_◔)

# Tests:

```
# f 1 2 3 4 5
0
# f 5 12 23 2 4 4 2 6 7
539
# f -8 50 3 3 -123 4 17 99 13
-1055.35
# f 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
256.00
# f 1 0 1 0 1 0
1
# f -9 -8 -1
-16
# f 0 -3
-3
# f -99
-99

```
> 1 votes

# Answer
# 05AB1E, ~~29~~ ~~28~~ 27 bytes

**Using 'Python `eval`' builtin (~~29~~ ~~28~~ 27 bytes):**

```
g'(×svy')"+-*/"S„**ªNè}\J.E

```

Try it online or verify all test cases. (NOTE: `ª` is `¸«` and we use the legacy version in the TIO, because `.E` is disabled in the new version of 05AB1E on TIO.)

**Using 'Execute as 05AB1E' builtin (~~29~~ 28 bytes):**

```
vyD0‹i¦'(}N_iðë"m+-*/"Nè]J.V

```

Try it online or verify all test cases.

**Explanation:**

In Python `**` is used for exponentiation. In addition, `*`,`/`,`**` have operator precedence over `+`,`-`. So the code transforms `[-1,2,-3,4,-5]` to `(((((-1)+2)--3)*4)**-5)`, and then uses `.E` to execute the string as Python `eval`.

```
g                  # Take the length of the (implicit) input
 '(×              '# Create a string of "(" characters of that size
s                  # Swap so the (implicit) input is at the top of the stack again
 v            }    # Loop `y` of each of its items:
  y                #  Push `y`
   ')             '#  Push ")"
     "+-*/"S       #  Push ["+","-","*","/"]
            „**ª   #  Append a trailing "**": ["+","-","*","/","**"]
                Nè #  Get a string from this list based on the index of the loop
                   #  (with automatic wraparound)
\                  # Discard the trailing operand from the stack
 J                 # Join all strings on the stack together
  .E               # Execute as Python eval (and output implicitly)

```

In 05AB1E negative values are with a trailing `(` instead of leading `-`, and `m` is used for exponentiation. In addition, a Polish notation is used. So the program transforms `[-1,2,-3,4,-5]` to `1( 2+3-4*5(m`, and then uses `.V` to execute the string as 05AB1E code.

```
v                  # Loop `y` of each of its items:
 y                 #  Push `y`
  D0‹i   }         #  If `y` is negative:
      ¦            #   Remove the first character (the minus sign)
       '(         '#   And push a "("
  N_i              #  If the index of the loop is 0:
     ð             #   Push a space character
    ë              #  Else:
     "m+-*/"Nè     #   Push a character from "m+-*/" based on the index of the loop
                   #   (with automatic wraparound)
]                  # Close both the if-else and loop
 J                 # Join all strings on the stack together
  .V               # Execute as 05AB1E code (and output implicitly)

```
> 1 votes

# Answer
# 05AB1E, 15 bytes

```
ćsvy"+-*/m"Nè.V

```

Try it online! or as a Test Suite

**Explanation**

```
ć                # extract the head of the input list
 sv              # for each (value y, index N) in the rest of the list
   y             # push the element
    "+-*/m"Nè    # push a string representation of the Nth operator (wraps around)
             .V  # execute it as code

```
> 1 votes

# Answer
# C# (.NET Core), 130 bytes

Without LINQ.

```
s=>{var x=s[0];for(var j=1;j<s.Length;j++){int t=j%5;var z=s[j];x=t<1?x=Math.Pow(x,z):t<2?x+=z:t<3?x-=z:t<4?x*=z:x/=z;}return x;};

```

Try it online!
> 1 votes

# Answer
# Runic Enchantments, 64 bytes

```
R31B~~?@+31B~~?@S-31B~~?@*31B~~?@S,31B~~?@Sp
\i<{1[lil1-{S{)]{{B

```

Try it online!

First line is the main program loop, which reads a number from input and performs the next math instruction. If no input, the attack is dumped to the output and the program terminates. Entry point is the `<` on the second line, which reads the first number from input prior to entering the main loop. Invalid input blindly accepted with unpredictable results (only + and * are defined for strings, other operations would result in an empty stack).

Woo, finally found a use for `B`ranch command! The second line starting at index 3 acts like a function. In this case it takes in input, checks that it got input, and arranges the stack for return. Then `31B~~` invokes and cleans up after the invokation (as the `B`ranch instruction leaves 2 values on top of the stack, add a return pointer). All told the overhead (8+5n) was less than in-line (9n). I think I'll be adding a modifier that cause `B` to not push those 2 values (overhead of 2 bytes to save 2n bytes). Happily, no directional commands are needed to insure consistent execution.

Also featured is the `[` and `]` stack-of-stacks commands, which lets the program temporarily remove the return location from the stack as it handles reading input. It saves several bytes worth of stack manipulation having to otherwise work around those 2 values. These do enforce a maximum input list of 9 values. Changing the entry to `y<<` increases that to 19 items (and as `<` acts like a NOP, the branch pointer doesn't need to update). A third line with `\y<<` (changing the existing `\` to `U`) would double that again to 39 items.

Stack at the end of the Branch "function" would look like `[v,i,1,x,y]` where `x,y` are at the top and the 0-indexed location on the first line (`y` will always be 0) where the next instruction with execute. `v` is the value that started on the stack prior to entry into the Branch "function". And `i` is the value read from input. If no input was available, `[i,1]` would instead be `[0]` resulting in `v` being printed when `?@` is reached.
> 1 votes

# Answer
# x86-64 machine code (Linux), 90 bytes

```
0000000000000000 <weapons_asm>:
   0:   48 89 f1                mov    %rsi,%rcx
   3:   db 07                   fildl  (%rdi)

0000000000000005 <math_loop>:
   5:   48 83 c7 04             add    $0x4,%rdi
   9:   48 ff c9                dec    %rcx
   c:   e3 49                   jrcxz  57 <done>
   e:   da 07                   fiaddl (%rdi)
  10:   48 83 c7 04             add    $0x4,%rdi
  14:   48 ff c9                dec    %rcx
  17:   e3 3e                   jrcxz  57 <done>
  19:   da 27                   fisubl (%rdi)
  1b:   48 83 c7 04             add    $0x4,%rdi
  1f:   48 ff c9                dec    %rcx
  22:   e3 33                   jrcxz  57 <done>
  24:   da 0f                   fimull (%rdi)
  26:   48 83 c7 04             add    $0x4,%rdi
  2a:   48 ff c9                dec    %rcx
  2d:   e3 28                   jrcxz  57 <done>
  2f:   da 37                   fidivl (%rdi)
  31:   48 83 c7 04             add    $0x4,%rdi
  35:   48 ff c9                dec    %rcx
  38:   e3 1d                   jrcxz  57 <done>

000000000000003a <exp_rept>:
  3a:   51                      push   %rcx
  3b:   8b 0f                   mov    (%rdi),%ecx
  3d:   d9 e8                   fld1
  3f:   83 f9 00                cmp    $0x0,%ecx
  42:   74 10                   je     54 <exp_rept.done>
  44:   9c                      pushfq
  45:   7f 02                   jg     49 <exp_rept.l>
  47:   f7 d9                   neg    %ecx

0000000000000049 <exp_rept.l>:
  49:   d8 c9                   fmul   %st(1),%st
  4b:   e2 fc                   loop   49 <exp_rept.l>
  4d:   9d                      popfq
  4e:   7d 04                   jge    54 <exp_rept.done>
  50:   d9 e8                   fld1
  52:   de f9                   fdivrp %st,%st(1)

0000000000000054 <exp_rept.done>:
  54:   59                      pop    %rcx
  55:   eb ae                   jmp    5 <math_loop>

0000000000000057 <done>:
  57:   dd 1a                   fstpl  (%rdx)
  59:   c3

```

Firstly, credit to gwaugh's answer which is also submitted for this post. I started working on this solution before gwaugh posted, which can be seen in my git repo's log, but ultimately his approach to this problem was the most efficient (especially the exponentiation). If you feel inclined to upvote my submission, please check out his as well.

Like my other x86 solutions, this code is simply a function that's meant to be called from a C/C++ program, which can be seen at my git repo. This means that the input array, length, and return pointer are passed through rdi, rsi, and rdx. For x86-64, getting the output location as an argument saves bytes, because normally when a C/C++ function returns a double on this processor, it's passed back through xmm0. This means the result double has to be moved from the FPU stack to a place in memory, then moved into xmm0. If we specify a place in memory we want the result, then we can just move the result double directly from the FPU stack to the memory location.

Exponentiation is done through repeated multiplication, with the assumption that we'll only get integer exponents (though the exponent can be negative). If the problem requires handling floating point exponentiation, the solution becomes extremely complicated. The standard way to compute x^y on x86 is to compute 2^(y * log2(x)). However, if x is negative (which happens in test case 2), log2(x) is a complex number, which can't be directly handled by the FPU. If you're curious how pow(double x, double y) is solved in C, check out the glibc code here (hint: it's complicated).
> 1 votes

# Answer
# K (ngn/k), 42 bytes

```
{*x{?[x;0 2;y/]}/(#1_x)#(+;-;*;%;{*/y#x})}

```

Try it online!

Sets up a reduce with the original input as `x`, and a corresponding list of operations to apply.

* `(+;-;*;%;{*/y#x})` initialize a list of the desired operations to apply, using `{*/y#x}` for pow (only works for raising values to integer powers)
* `(#1_x)#...` "overtake" this list, expanding it to match the length of the input `x` minus one (as the operations are applied *between* elements of `x`)
* `x{...}/...` set up the reduce, seeded with the original input and run over the list of operations to apply
    + `?[x;0 2;y/]` use `?[x;i;f] splice` to apply the operation between the first two elements of the input, replacing those values with the result of applying the operation (`y`) between them
> 1 votes

# Answer
# C (gcc), 135 bytes

```
#include<math.h>
float r(float*a,int l){float z,v=*a;for(int p=1;p<l;v=(float[]){z?pow(v,z):1,v+z,v-z,v*z,v/z}[p++%5])z=a[p];return v;}

```

Try it online!
> 0 votes

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


# Question
Title: Translate an arithmetic expression to Brainfuck
Write a program that translates an arithmetic expression to a Brainfuck program which evaluates the expression and prints the result in decimal numbers. For example, this arithmetic expression,

```
2 * (3 + 4)

```

can be translated to Brainfuck as,

```
++ 2
>+++ 3
>++++ 4
[-<+>]< add
<[>[->+>+<<]>[-<+>]<<-]>[-]>>[-<<<+>>>]<<< mul
[->+<]>[>>>>++++++++++<<<<[->+>>+>-[<-]<[<<[->>>+<<<]>>>>+<<-<]<<]
++++++++[->++++++<]>[-<+>]>>>>[-<<<<+>>>>]<[-]<<<]<[.<] print decimal

```

The Brainfuck program doesn't take input. However, each integer constant or operator in the original expression must have a distinct translated form contained in the resulting Brainfuck program.

This is the definition of an arithmetic expression.

```
primary-expression
  integer-constant
  (arithmetic-expression)

multiplicative-expression
  primary-expression
  multiplicative-expression multiplicative-operator primary-expression

additive-expression
  multiplicative-expression
  additive-expression additive-operator multiplicative-expression

arithmetic-expression
  additive-expression

additive-operator
  + | -

multiplicative-operator
  * | /

integer-constant
  a decimal constant in the range [0-255],
  which cannot start with '0' unless the number is 0

```

In other words, a `multiplicative-expression` is evaluated before an`additive-expression`. An `arithmetic-expression` enclosed in parentheses is evaluated prior to the outer expressions. Otherwise, a chain of expressions is evaluated from left to right.

All whitespaces are ignored.

The Brainfuck machine to run the output will have 8-bit cells, each holding an unsigned integer. It is guaranteed that `255 + 1 == 0` and `0 - 1 == 255`, so you can use this fact to implement your Brainfuck operations. At the same time, you may safely assume that the initial input of an arithmetic expression does not overflow or underflow during its evaluation.

This is a `code-golf` challenge.

---

The print function in the example BF code won't print anything if it reads 0. However, your program's BF output should print 0 if the result of the expression is 0. This BF function for example will print 0 for 0, but it's longer.

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

```

You are free to find or make a shorter version for any BF operation. Here is a list of common operations implemented in BF. This is a webpage where you can test BF code and also look at the memory dump.

# Answer
> 4 votes
# JavaScript (Node.js),  ~~427~~  417 bytes

```
s=>[...(a=s.match(/\d+|./g),o=[],d="+-/<>[]./",Buffer("kla`XslY`^KfMflY[`d^[jY`^jYa^ZeaXedfmY`f`t[[KfdM[CdtkqkqSMDsldd@@@@@[[MDd`iK^]kadX[fdD[Y^s@@@@MD@@XfMCtddM[[`dtkq[sk_V").map(c=>d+=d[c&7]+d[c/8&7]),g=S=>!(s=a.shift())|s==')'?o=[...o,...S]:g(S,s<')'?g([]):1/s?o.push(s):(h=_=>/u|[+-][*/]/.test(S[0]+s)?S.unshift(s):h(o.push(S.shift())))()))([]),'<'].map(s=>1/s?">"+"+".repeat(s):d.split`/`[d.indexOf(s)+3]).join``

```

Try it online!

Try the Brainfuck code online!

This is using the BF code provided in the challenge and the division algorithm suggested by Nitrodon.

### Brainfuck compression

The BF code snippets are joined together with `/`'s. The resulting string is compressed by turning each pair of character codes \\$(a,b)\\$ into a single character of ASCII code \\$N\in\[64\dots 116\]\\$:

$$N=a+8b+64$$

where \\$a\\$ and \\$b\\$ are computed according to the following table:

```
+ - / < > [ ] .
0 1 2 3 4 5 6 7

```

Hence the decompression code:

```
d = "+-/<>[]./"
Buffer("... compressed data ...")
.map(c => d += d[c & 7] + d[c / 8 & 7])

```

Try it online!

### Infix to postfix conversion

```
s => (                        // s = infix expression, as a string
  a = s.match(/\d+|./g),      // a[] = s split into numbers and operators
                              //       (including parentheses)
  o = [],                     // o[] = postfix output, as a list
  g =                         // g is a recursive function taking
  S =>                        // an operator stack S[]
  !(s = a.shift()) |          // s = next entry extracted from a[]
  s == ')' ?                  // if s is undefined or ')':
    o = [...o, ...S]          //   append S[] to o[]
  :                           // else:
    g(                        //   recursive call:
      S,                      //     pass S[] unchanged
      s < ')' ?               //     if s is '(':
        g([])                 //       recursive call with an empty stack
      :                       //     else:
        1 / s ?               //       if s is a number:
          o.push(s)           //         push it in o[]
        :                     //       else (s is an operator):
          ( h = _ =>          //         helper function:
            /u|[+-][*/]/      //           if S[0] is undefined or S[0] is
            .test(S[0] + s) ? //           '+' or '-' and s is '*' or '/':
              S.unshift(s)    //             insert s at the beginning of S[]
            :                 //           else:
              h(              //             recursive call:
                o.push(       //               extract the first entry of S[]
                  S.shift()   //               and push it in o[]
                )             //
              )               //             end of recursive call
          )()                 //         initial call to h()
    )                         //   end of recursive call
)([])                         // initial call to g()

```

Try it online!

### Brainfuck output

```
o =>                          // o[] = postfix list
[...o, '<']                   // append a '<' to trigger the 'print'
.map(s =>                     // for each entry s:
  1 / s ?                     //   if s is a number:
    ">" +                     //     append a '>'
    "+".repeat(s)             //     followed by '+' repeated s times
  :                           //   else:
    d.split`/`[               //     split the BF code snippets
      d.indexOf(s) + 3        //     and append the relevant one
    ]                         //
).join``                      // end of map(); join everything

```

Try it online!

# Answer
> 3 votes
# Python 3, 675 bytes

```
import shlex
s,b,o=[],'',{'+':'[-<+>]<','-':'[-<->]<','*':'<[>[->+>+<<]>[-<+>]<<-]>[-]>>[-<<<+>>>]<<<','/':'[->>>+<<<]<[->+>>+>-[<-]<[<<[->>>+<<<]>>>>+<<-<]<<]>>>>>[-<<<<<+>>>>>]<[-]<<[-]<[-]<'}
for c in list(shlex.shlex(input())):
 try:
  b+='>'+'+'*int(c)
 except:
  if c=='(':s+='('
  elif c==')':
   t=s.pop()
   while t!='(':b+=o[t];t=s.pop()
  else:
   while len(s)>0 and s[-1]!='('and c in'+-':b+=o[s.pop()]
   s+=c
for c in range(len(s)):b+=o[s.pop()]
print(b+'>>++++++++++<<[->+>-[>+>>]>[+[-<+>]>+>>]<<<<<<]>>[-]>>>++++++++++<[->-[>+>>]>[+[-<+>]>+>>]<<<<<]>[-]>>[>++++++[-<++++++++>]<.<<+>+>[-]]<[<[->-<]++++++[->++++++++<]>.[-]]<<++++++[-<++++++++>]<.[-]<<[-<+>]<')

```

Try it online!

**Example:**

Input: `(8 - 4 / 2) * 7 + 1`

Output:

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

```

Output of brainfuck program: `43`

---
Tags: code-golf, brainfuck, compiler
---


# Question
Title: AoCG2021 Day 14: Adjusting dancing program's period
Part of **Advent of Code Golf 2021** event. See the linked meta post for details.

Related to AoC2017 Day 16. I'm using the wording from my Puzzling SE puzzle based on the same AoC challenge instead of the original AoC one for clarity.

---

\\$n\\$ people numbered \\$1, 2, \cdots, n\\$ are standing in line in the order of their corresponding numbers. They "dance", or swap places, according to some predefined instructions. There are two kinds of instructions called Exchange and Partner:

* **E**xchange(m,n): The two people standing at m-th and n-th positions swap places.
* **P**artner(x,y): The two people numbered x and y swap places.

For example, if there are only five people `12345` and they are given instructions E(2,3) and P(3,5) in order, the following happens:

* E(2,3): The 2nd and 3rd people swap places, so the line becomes `13245`.
* P(3,5): The people numbered 3 and 5 swap places, so the line becomes `15243`.

Let's define a **program** as a fixed sequence of such instructions. You can put as many instructions as you want in a program.

Regardless of the length of your program, if the whole program is repeated a sufficient number of times, the line of people will eventually return to the initial state \\$1,2,3,\cdots,n\\$. Let's define the program's **period** as the smallest such number (i.e. the smallest positive integer \\$m\\$ where running the program \\$m\\$ times resets the line of people to the initial position). The states in the middle of a program are not considered.

For example, a program `E(2,3); P(3,5); E(3,4)` has the period of 6:

```
       E(2,3)   P(3,5)   E(3,4)
1. 12345 -> 13245 -> 15243 -> 15423
2. 15423 -> 14523 -> 14325 -> 14235
3. 14235 -> 12435 -> 12453 -> 12543
4. 12543 -> 15243 -> 13245 -> 13425
5. 13425 -> 14325 -> 14523 -> 14253
6. 14253 -> 12453 -> 12435 -> 12345

```

Now, you want to write a program for \\$n\\$ people so that it has the period of exactly \\$m\\$. Is it possible?

**Input:** The number of people \\$n\\$ and the target period \\$m\\$

**Output:** A value indicating whether it is possible to write such a program or not. You can choose to

* output truthy/falsy using your language's convention (swapping is allowed), or
* use two distinct, fixed values to represent true (affirmative) or false (negative) respectively.

Standard rules apply. The shortest code in bytes wins.

## Test cases

Truthy:

```
n, m
1, 1
2, 2
3, 6
3, 3
8, 15
8, 120
16, 28
16, 5460

```

Falsy:

```
1, 2
2, 3
3, 4
6, 35
6, 60
8, 16
16, 17

```

# Answer
> 10 votes
# Pari/GP, 59 bytes

```
(n,m)->[[lcm(Vec(concat(p,q)))==m|q<-s]|p<-s=partitions(n)]

```

Try it online!

Let `x` and `y` loop over the integer partitions of `n`. Takes the LCM of all elements in `x` and `y`, and checks if it equals `m`. Outputs a list of lists, which is truthy when at least one element is truthy.

For a detailed explanation, please read (and upvote) xnor's answer on Puzzle SE.

Here I only list some facts about permutations (please read this Wikipedia page for the definition of the terms):

Here by "permutation" I mean a permutation of the set \\$\\{1,\dots,n\\}\\$.

1. Every permutation can be written as a product of 2-cycles (swapping two elements).
2. So a "program" in this question can be seen as left multiplying a permutation \\$X\\$, and right multiplying another permutation \\$Y\\$. Let \\$(X,Y)\\$ denote such a program. Applying the program \\$k\\$ times is just left multiplying \\$X^k\\$ and right multiplying \\$Y^k\\$. The "period" of \\$(X,Y)\\$ is the smallest \\$k\>0\\$ such that \\$X^kY^k=\operatorname{id}\\$. Here \\$\operatorname{id}\\$ is the permutation that changes nothing.
3. Every permutation can be written as a product of disjoint cycles.
4. If we write a permutation \\$X\\$ as a product of disjoint cycles, then the order of \\$X\\$ (i.e., the smallest \\$k\>0\\$ such that \\$X^k=\operatorname{id}\\$) is the LCM of the lengths of these cycles. The cycle lengths corresponds to an integer partition of \\$n\\$.
5. If \\$k\\$, \\$l\\$ are the orders of permutations \\$X\\$, \\$Y\\$ respectively, then the period of the program \\$(X,Y)\\$ is a divisor of \\$\operatorname{lcm}(k,l)\\$, but not necessarily equals \\$\operatorname{lcm}(k,l)\\$.
6. But when \\$k\\$ and \\$l\\$ are coprime, the period of \\$(X,Y)\\$ does equal \\$\operatorname{lcm}(k,l)=k\ l\\$. A proof can be found in xnor's answer on Puzzle SE.
7. If \\$k\\$ is the order of some permutation, \\$s\\$ a divisor of \\$k\\$, then there exists a permutation with order \\$s\\$. This can be seen from the fact that, if \\$k\\$ is the order of a cycle \\$C\\$, \\$s\\$ a divisor of \\$k\\$, then \\$C^{k/s}\\$ has order \\$s\\$.
8. If \\$\operatorname{lcm}(k,l)=m\\$, \\$u\\$ a divisor of \\$m\\$, then we can always find \\$s\mid k\\$, \\$t\mid l\\$ such that \\$s\\$ and \\$t\\$ are coprime, \\$s\ t=u\\$.
9. So if \\$k\\$, \\$l\\$ are the orders of permutations \\$X\\$, \\$Y\\$ respectively, we can always find a program \\$(X',Y')\\$ (not necessarily the same as \\$(X,Y)\\$) with period \\$\operatorname{lcm}(k,l)\\$.
10. So the possible periods of programs are exactly these \\$\operatorname{lcm}(k,l)\\$, where \\$k\\$ and \\$l\\$ run over the LCM's of integer partitions of \\$n\\$.

# Answer
> 5 votes
# 05AB1E, 10 bytes

```
Åœãε˜.¿}Iå

```

First input is \\$n\\$, second is \\$m\\$.

Port of *@alephalpha*'s Pari/GP answer, so make sure to upvote him as well!

Try it online or verify all test cases.

**Explanation:**

```
Åœ       # Get all lists of positive integers that sum to the first (implicit)
         # input `n`
  ã      # Use the cartesian power to create all possible pairs of these lists
   ε     # Map over each pair of lists:
    ˜    #  Flatten it to a single list
     .¿  #  Pop and push the LCM (Least Common Multiple)
   }Iå   # After the map: check if the second input `m` is in this list
         # (after which this is output implicitly as result)

```

# Answer
> 4 votes
# Python 3.8 (pre-release), 209, 187 (@pxeger), 180 179 bytes (merge)

```
lambda n,m:any(sum(g(m))-n<=s<=n for s in h(g(m)))
g=lambda a,p=2,e=0:a%p and[p**e][:e]+g(a,p+1)or g(a//p,p,e+1)if a+e>1else[]
h=lambda p,S=0:p and h(p[1:],S)+h(p[1:],S+p[0])or[S]

```

Try it online!

#### Older versions

```
lambda n,m:any(sum(g(m))-n<=s<=n for s in h(g(m)))
g=lambda a,p=2,e=0:a+e>1 and(a%p and[p**e][:e]+g(a,p+1)or g(a//p,p,e+1))or[]
h=lambda p,S=0:p and h(p[1:],S)+h(p[1:],S+p[0])or[S]

```

Try it online!

```
lambda n,m:(c:={x**g(m).count(x)for x in g(m)})!=1in(sum(c)-n<=s<=n for s in h(c))
g=lambda a,p=2:a%p and g(a,p+1)or[p]+g(a//p,p)if a>1else[]
h=lambda c:sum([h(c-{x})for x in c],[sum(c)])
```

^ ^ ^ ^ ^ ^ Big thanks @pxeger!

Attempt This Online!

```
g=lambda a,p=2:a>1 and(a%p and g(a,p+1)or[p]+g(a//p,p))or[]
def h(c):
 yield sum(c)
 for x in c:
  yield from h(c-{x})
def f(n,m):
 c={x**g(m).count(x)for x in{*g(m)}}
 return any(sum(c)-n<=s<=n for s in h(c))

```

Try it online!

#### Explanation

We can think of the two kinds of swaps as "multiplying from the left or right". The significance of this is that we can flip any adjacent pair of different kind swaps without changing the outcome and the space of possible chains of swaps is the same as one arbitrary permutation from the left and one from the right.

We therefore need to know the period of any n-permutation. This can be derived from the cycle representation. The period is just the lcm of the cycle lengths. And the combined (left and right) period is the lcm of the left and right lcms EDIT This is not generally true. What is, however, true is that cancellation can only affect shared prime factors. Indeed. let A and B the left and right permutations with periods m and n. If A^x B^x = 1 with x \< lcm(m,n) and m has a prime factor p that is neither in n nor in x then by taking the n-th power we get A^(xn) = 1 contradicting the assumption that the period be a multiple of p.

#### Implementation

Straight forward: `g` extracts the prime factors. The main function `f` groups them into powers and `h` determines whether these powers can be distributed over two times n elements.

# Answer
> 3 votes
# Charcoal, ~~64~~ ~~60~~ 59 bytes

```
ＮθＮηＦ…·²ηＷ¬﹪ηι«⊞υ×ι⎇﹪∨Πυ¹ι¹⊟υ≧÷ιη»¬‹θ⌊ＥＸ²Ｌυ⌈Ｅ²↨¹Φυ⁼λ﹪÷ιＸ²ξ²

```

Try it online! Link is to verbose version of code. Outputs a Charcoal boolean, i.e. `-` for possible, nothing if not. Explanation: Based on @xnor's Puzzling.SE answer.

```
ＮθＮη

```

Input `n` and `m`.

```
Ｆ…·²ηＷ¬﹪ηι«⊞υ×ι⎇﹪∨Πυ¹ι¹⊟υ≧÷ιη»

```

Decompose `m` into its prime power factors e.g. `120=3*5*8`.

```
¬‹θ⌊ＥＸ²Ｌυ⌈Ｅ²↨¹Φυ⁼λ﹪÷ιＸ²ξ²

```

Check whether the factors can be partitioned into two sets neither sum of which exceeds `n`, or expressed more golfily, the minimum possible maximum sums of two complementary sets of factors does not exceed `n`. In the case of `3*5*8` the sets are `{},{3,5,8}` maximum sum `16`, `{3},{5,8}` maximum sum `13`, `{5},{3,8}` maximum sum `11`, and `{8},{3,5}` maximum sum `8`. The minimum of these is `8`, so `n` needs to be at least `8` for an `m` of `120`.

# Answer
> 3 votes
# Ruby, ~~136~~ 106 bytes

```
->n,m{z=([*0..n]*n).combination(n).select{|x|x.sum==n};z.product(z).any?{|a,b|m==(a+b-[0]).reduce(&:lcm)}}

```

Try it online!

Port of Kevin Crujssen's 05AB1E answer, which was a port of alephalpha's Pari/GP answer, but explained in terms an engineer can understand. :-)

This is very slow because of the brute force partitioning: instead of trying to be clever, I just get all combinations of n numbers between 0 and n, and filter by sum, then remove the 0s when calculating lcm.

# Answer
> 2 votes
# JavaScript (ES6), 107 bytes

Expects `(m)(n)` and returns \\$0\\$ for true or \\$1\\$ for false.

Based on alephalpha's algorithm.

```
m=>F=(n,i=a=[1],p=1,g=q=>v%p?g(q,v+=q):v)=>n?i>n||F(n-i,i,g(v=i++))&F(n,i,p):a.every(x=>g(v=x)-m,a.push(p))

```

Try it online!

### Commented

```
m =>              // outer function taking the period m
F = (             // inner recursive function taking:
  n,              //   n   = number of people
  i =             //   i   = current value for integer partition
  a = [1],        //   a[] = list of LCMs
  p = 1,          //   p   = previous LCM
  g = q =>        //   g is a helper function taking q
  v % p ?         //   and computing LCM(p, q)
    g(q, v += q)  //   it must be called with v = q
  :               //
    v             //
) =>              //
n ?               // if n is not equal to 0:
  i > n ||        //   abort if i > n
  F(              //   otherwise do a 1st recursive call:
    n - i,        //     where i is subtracted from n,
    i,            //     i is left unchanged
    g(v = i++)    //     and p is updated to LCM(p, i)
  ) &             //
  F(              //   then do a 2nd recursive call:
    n,            //     where n is left unchanged,
    i,            //     i is incremented (this is done above)
    p             //     and p is left unchanged
  )               //
:                 // else (n = 0):
  a.every(x =>    //   test whether all x in a[]
    g(v = x) - m, //   are such that LCM(p, x) ≠ m
    a.push(p)     //   and append p to a[]
  )               //

```

# Answer
> 2 votes
# , ~~139~~ ~~134~~ 129 bytes

*Edit: -5 bytes thanks to pajonk*

```
function(n,m)all(apply(expand.grid(rep(list(0:n),2*n)),1,function(v){while(sum(v[1:n])==n&sum(v)==2*n&any(T%%v[v>0]))T=T+1;m-T}))

```

Try it online!

Approach based on alephalpha's answer: upvote that!
Returns `TRUE` if the loop is impossible, or `FALSE` if the loop is possible.

Generates all pairs of integer partitions of `n` by first creating a *huge* array of twice all combinations of `0...n`, and then testing the LCM of rows whose first and second halves each sum to `n`. So runs out of memory for any `n` greater than 5.

---

# , ~~204~~ ~~178~~ 176 bytes

*Edit: -2 bytes thanks to pajonk*

```
function(n,m,q=p(n),`[`=`for`){i[q,j[q,{k=1;while(any(k%%c(i,j)))k=k+1;F=F+!m-k}]];F}
p=function(x,y=x[1])c(list(x),if(y>1)unlist(lapply(2:y-1,function(i)p(c(i,y-i,x[-1]))),F))

```

Try it online!

Previous version with more-efficient (but significantly longer) integer partition function, allowing it to actually run on test cases with n\>5 (although still times-out on TIO for n=16 and higher).
Returns `0` (falsy) if the loop is not possible, or a non-zero integer (truthy) if the loop is possible.

**recursive function p** gets all integer partitions (with some duplicates)

```
p=function(x,y=x[1])c(list(x),if(y>1)unlist(lapply(2:y-1,function(i)p(c(i,y-i,x[-1]))),F))

```

**function l** calculates the LCM of its vector argment

```
l=function(v){k=1;while(any(k%%v))k=k+1;k}

```

So, finally, **function possible\_loop** uses these to check if the loop is possible:

```
possible_loop=function(n,m,q=p(n)){for(i in q)for(j in q)F=F+!m-l(c(i,j);F}

```

# Answer
> 2 votes
# TypeScript Types, 526 bytes

```
//@ts-ignore
type a<A,B,Q=[]>=A extends[...B,...infer X]?a<X,B,[...Q,0]>:[Q,A];type b<A,B,N=[]>=A extends[0,...infer A]?b<A,B,[...N,...B]>:N;type c<A,B>=[]extends A|B?Exclude<A|B,[]>:c<B,a<A,B>[1]>;type d<A,N=[0]>=A extends[infer M,...infer A]?d<A,b<a<M,c<M,N>>[0],N>>:N;type e<T,A=[],N=[0]>=T extends[0,...infer U]?|e<U,[...A,N],[0]>|e<U,A,[...N,0]>:[...A,N];type f<T,N=[]>=T extends N["length"]?N:f<T,[...N,0]>;type M<M,N,P=e<f<M>extends[0,...infer T]?T:0>,Q=P,O=P extends P?Q extends Q?d<[...P,...Q]>:0:0>=f<N>extends O?1:0

```

Try It Online!

> Port of Kevin Crujssen's 05AB1E answer, which was a port of alephalpha's Pari/GP answer, but explained in terms an engineer can understand. :-)

## Ungolfed / Explanation

```
// Returns [A / B, A % B]
type DivMod<A, B, Q = []> = A extends [...B, ...infer X] ? DivMod<X, B, [...Q, 0]> : [Q, A]

type Mult<A, B, N = []> = A extends [0, ...infer A] ? Mult<A, B, [...N, ...B]> : N

// Returns the GCD of A and B using the Euclidean algorithm
type Gcd<A, B> = [] extends A | B ? Exclude<A | B, []> : Gcd<B, DivMod<A, B>[1]>

// Returns the LCM of all the elements of A
type Lcm<A, N=[0]> = A extends [infer M, ...infer A] ? Lcm<A, Mult<DivMod<M, Gcd<M, N>>[0], N>> : N

// Returns a union of all integer partitions of T+1
type Partitions<
  T,
  // All previous numbers
  Arr = [],
  // The most recent number
  N = [0]
> =
  // U = T - 1
  T extends [0, ...infer U]
    // Return both:
    ?
      // The paritions if we end N here
      | Partitions<U, [...Arr, N], [0]>
      // The paritions if we add one to N here
      | Partitions<U, Arr, [...N, 0]>
    // T is zero
    : [...Arr, N]

// Converts a number literal into a tuple representation
type NumToTuple<T, N = []> = T extends N["length"] ? N : NumToTuple<T, [...N, 0]>

type Main<
  M,
  N,
  P = Partitions</* M - 1 */ NumToTuple<M> extends[0,...infer T]?T:0>,
  Q = P,
  // Map over the cross of P and Q and compute the LCMs
  Ns = P extends P ? Q extends Q ? Lcm<[...P, ...Q]> : 0 : 0
> =
  // Return 1 if N is in Ns
  NumToTuple<N> extends Ns ? 1 : 0

```

# Answer
> 1 votes
# Rust, 345 305 bytes

```
|n,m|{fn p(n:u64)->Vec<Vec<u64>>{let mut v=vec![];if n>0{v.push(vec![n]);for i in 1..n{for mut x in p(n-i).drain(..){x.push(i);x.sort();if!v.contains(&x){v.push(x)}}}}v}let q=p(n);for i in 0..q.len(){for j in i..q.len(){if(1..).find(|v|q[i].iter().chain(&q[j]).all(|a|v%a<1))==Some(m){return true}}}false}

```

Try it online!

Also a port of @alephalpha's answer. A good chunk of it is just implementing partitioning and LCM.

* -40 bytes by replacing the LCM implementation

# Answer
> 0 votes
# Wolfram Language (Mathematica), 51 bytes

```
!Outer[LCM,l=LCM@@@IntegerPartitions@#,l]~FreeQ~#2&

```

Try it online!

---
Tags: code-golf, math, decision-problem, number-theory, integer-partitions
---


title: AoCG2021 Day 15: Leapfrog Santa

text:
# Question
Title: AoCG2021 Day 15: Leapfrog Santa
Part of **Advent of Code Golf 2021** event. See the linked meta post for details.

The story continues from AoC2015 Day 3, Part 2. This challenge was kindly contributed by Wheat Wizard (Grain Ghost).

---

Santa is delivering presents to an infinite two-dimensional grid of houses each 1 unit apart. The delivery begins delivering a present to the house at an arbitrary starting location, and then moving along a predetermined path delivering a new present at every step of the path. The path is a list of moves made of characters:

* `^` north
* `v` south
* `>` east
* `<` west

At each step Santa reads the instruction and starts heading in that direction until a house which hasn't had a present delivered yet is reached. At that point a present is delivered to that house and the next instruction starts.

## Task

Given a non-empty string representing directions, output the total length of the path that Santa will take.

This is so answers will be scored in bytes.

## Test cases

```
v^v^v^v^: 36
^>v<^>v : 10
>>>>>><<<<<<< : 19
>>>vvv<<< : 9

```

# Answer
# Python 3.8 (pre-release), 76 bytes

```
f=lambda o,c=0,*v:len(o)and-~f(o[(d:=c+1j**(ord(o[0])%11))not in v:],d,c,*v)

```

Try it online!
> 4 votes

# Answer
# Python 2, 81 bytes

```
c=t=0
v=0,
for i in input():
 while c in v:c+=1j**(ord(i)%11);t+=1
 v+=c,
print t
```

Attempt This Online!

Improvable.

`1j**(ord(i)%11)` is a sufficient hash function to give a layout of complex numbers corresponding to some transformation of the cardinal directions `^v><`.
> 3 votes

# Answer
# Charcoal, 29 bytes

```
≔⁰ηＦＳ«Ｐ#Ｗ℅ＫＫ«Ｍ✳⊗⌕>^<ι≦⊕η»»⎚Ｉη

```

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

```
≔⁰η

```

Start with no path length.

```
ＦＳ«

```

Loop over the input characters.

```
Ｐ#

```

We already delivered a present here.

```
Ｗ℅ＫＫ«Ｍ✳⊗⌕>^<ι≦⊕η»

```

Look for somewhere to deliver the next present.

```
»⎚Ｉη

```

Cler the canvas and output the final path length.
> 3 votes

# Answer
# , 85 bytes

```
function(s,x=1){for(j in utf8ToInt(s)%%11){while(x%in%T){x=x+1i^j
F=F+1}
T=c(x,T)}
F}

```

Try it online!

Uses the complex number, mod 11 trick.
> 3 votes

# Answer
# JavaScript (ES6), 83 bytes

Expects a list of characters.

```
a=>a.map(g=c=>g[g[[x,y]]=++t,i='^>v'.indexOf(c),[x+=i%2,y+=~-i%2]]&&g(c),t=x=y=0)|t

```

Try it online!

---

# JavaScript (Node.js),  ~~81~~  80 bytes

*Saved 1 byte thanks to @Neil*

Expects a string. Uses the `mod 11` trick.

```
s=>Buffer(s).map(g=c=>g[g[[x,y]]=++t,i=c%11-7,[x+=i%2,y+=~i%2]]&&g(c),t=x=y=0)|t

```

Try it online!
> 2 votes

# Answer
# Ruby, ~~67~~ 62 bytes

```
->s{*r=a=0i;s.bytes.sum{|b|1.step.find{r!=r|=[a+=1i**b%=19]}}}

```

Try it online!

### How?

Basically the usual mod 19 (or 11 or 13) trick. Start from (0+0i), sum the distance we have to travel for each house:

```
1.step.find{

```

`a` is the current position, b%19 is the direction, this literally counts the steps we need to find the first house that we have not visited yet.

```
r!=r|=[a+=1i**b%=19]}

```

This is the check: a is incremented once, we add it to the list with a union operator. If the house was already in the list, the list is unchanged and the result of the comparison is false, so we have to walk another step.
> 2 votes

# Answer
# Rust, 145 138 bytes

```
|i:&str|i.bytes().scan((vec![],[0,0]),|(v,p),c|{while{v.push(*p);p[c as usize%3&1]+=1-(c%5&2)as i64;v.contains(&p)}{}Some(v.len())}).max()

```

Try it online!

Same trick as as days 1 and 8.
> 2 votes

# Answer
# 05AB1E, 37 bytes

```
1Ýˆv¯θ1ÝÂ‚D(«yÇ`11%è©[+Ðˆ»¯€»s¢#®]¯g<

```

Try it online or verify all test cases.

**Explanation:**

Uses a combination of generating `[[0,1],[1,0],[0,-1],[-1,0]]` that I've also used in my 05AB1E answer here and *@alephalpha*'s modulo-11 trick from the AoCG2021 Day 1 challenge for indexing into it.

```
1Ýˆ                   # Add starting position [0,1] to the global_array
                      # (where we start is irrelevant, and [0,1] is shorter to
                      # push than [0,0])
   v                  # Loop over the characters of the (implicit) input-string:
    ¯θ                #  Push the last coordinate of the global_array
      1Ý              #  Push [0,1]
        Â             #  Bifurcate it (short for Duplicate & Reverse copy): [1,0]
         ‚            #  Pair them together: [[0,1],[1,0]]
          D(          #  Duplicate, and negate it: [[0,-1],[-1,0]]
            «         #  Merge the lists together: [[0,1],[1,0],[0,-1],[-1,0]]
             yÇ`      #  Push the codepoint of the character
                11%   #  Modulo-11 (5,6,7,8 for <^>v respectively)
                   è  #  Use it to 0-based modulair index into it
                      #  ([1,0],[0,-1],[-1,0],[0,1] for <^>v respectively†)
                    © #  Store this pair in variable `®` (without popping)
    [                 #  Start an inner infinite loop:
     +                #   Add the top pair to the coordinate
      Ð               #   Triplicate it
       ˆ              #   Pop one, and add it to the global_array
        »             #   Pop another, and join it with newline delimiter
         ¯            #   Push the global_array
          €»          #   Join each coordinate with newline delimiter as well
            s         #   Swap them on the stack
             ¢        #   Count this coordinate in the global_array*
              #       #   If it's just 1: stop the infinite loop
               ®      #   (Else, when it's more than 1) Push the `®`-pair again
   ]                  # After both loops
    ¯g                # Push the length of the global_array
      <               # Decrease it by 1, because the PATH between coordinates is
                      # 1 lower than the amount of coordinates
                      # (after which the result is output implicitly)

```

: As you can see, the modular indexing into the pairs causes all four arrows to travel in the opposite direction, but just like the starting position, this is irrelevant for calculating the final result.
***: The count, indexOf, and contains builtins doesn't work when we want to check a list inside a list of lists, hence the join by newlines before we use the count.
> 2 votes

# Answer
# Python3, 78 bytes

```
f=lambda n,c=[0]:len(n)and-~f(n[(j:=c[-1]+1j**(ord(n[0])%11))not in c:],c+[j])

```

Try it online!
> 1 votes

# Answer
# TypeScript Types, 276 bytes

```
//@ts-ignore
type a<T,P=0,N=1>=T extends[N,...infer T]?T:[...T,P];type M<I,P=[[],[]],N=[],V=0>=I extends`${infer C}${infer R}`?{"^":[P[0],a<P[1]>],v:[P[0],a<P[1],1,0>],">":[a<P[0]>,P[1]],"<":[a<P[0],1,0>,P[1]]}[C]extends infer Q?M<Q extends V?I:R,Q,[...N,0],V|P>:0:N["length"]

```

Try It Online!

## Ungolfed / Explanation

```
// Increment an integer stored as e.g. [Pos, Pos] for 2, [Neg, Neg, Neg] for -3, and [] for 0
// Invoked as Inc<T> to increment, or Inc<T, 1, 0> to decrement
type Inc<T, Pos = 0, Neg = 1> = T extends [Neg, ...infer T] ? T : [...T, Pos]

type Main<
  Instructions,
  Pos = [[], []]
  PathLength = [],
  Visited = 0
> =
  // Get the first character of Instructions
  Instructions extends `${infer Char}${infer Rest}`
    // Store the new position in NewPos
    ? {
      "^": [Pos[0], Inc<Pos[1]>],
       v : [Pos[0], Inc<Pos[1], 1, 0 /* Dec */>],
      ">": [Inc<Pos[0]>, Pos[1]],
      "<": [Inc<Pos[0], 1, 0 /* Dec */>, Pos[1]],
    }[Char] extends infer NewPos
      ?
        Main<
          // If NewPos is not in Visited, set Instructions to Rest
          NewPos extends Visited ? Instructions : Rest,
          // Update Pos
          NewPos,
          // Add one to PathLength
          [...PathLength, 0],
          // Add Pos to NewPos
          Visited | Pos,
        >
      : 0
    // Instructions is empty
    : PathLength["length"]

```
> 1 votes

# Answer
# Pari/GP, 89 bytes

```
s->a=[p=c=0];[a=setunion(a,[while(c++;setsearch(a,p+=I^d),)+p])|d<-Vec(Vecsmall(s))%11];c

```

Try it online!
> 0 votes

# Answer
# Wolfram Language (Mathematica), 79 bytes

```
(a[d=p=0]=0Clear@a;(a@p=0While[a[p+=#]<++d])&/@(I^ToCharacterCode@#~Mod~11);d)&

```

Try it online!
> 0 votes

---
Tags: code-golf, grid
---


# Question
Title: Get all binary between a binary string and its reverse
Your Challenge is to take a binary string as input and get all binary numbers between itself and the reverse of its string representation (the reverse may be less than or greater than the original input).

Output must be padded with zeroes to be the same length as the input.

The Order in which the values are displayed doesn't matter, but the Code needs to work with Values that are bigger than its reverse.

## Test Cases

```
Input: (1 or 0)
Output: None, string and its reverse are identical

Input: (any palindrome binary)
Output: None, same as above

Input: 01
Output: None, since there is no binary between 01 and 10 (1 and 2)

Input: 001
Output: 010,011 (Numbers between 001 (1) and 100 (4): 2,3)

Input: 100
Output: 010,011 (Same as above)

Input: 0010
Output: 0011 (Numbers between 0010 (2) and 0100 (4): 3)

```

This is Code Golf, shortest code wins!

EDIT: After seeing some of the solutions i have removed the requirement of the number representation of the binary being in ascending order. This is my first code golf challenge and i don't want to make it to tedious, also added some clarifications from the comments.

# Answer
> 3 votes
# x86-16 machine code, ~~58~~ 57 bytes

```
00000000: 8be9 e82a 008b da8b cdfd 4ee8 2100 3bda  ...*......N.!.;.
00000010: 7602 87d3 433b da73 1f8b cd8b c303 f957  v...C;.s.......W
00000020: 4fd1 e850 b000 1430 aa58 e2f5 5feb e533  O..P...0.X.._..3
00000030: d2ac d0e8 13d2 e2f9 c3                   .........

```

Listing:

```
8B E9           MOV  BP, CX         ; save input "Binary Pad" length to BP
E8 002A         CALL BINDEC         ; BX = forward input value
8B DA           MOV  BX, DX         ; forward number in BX
8B CD           MOV  CX, BP         ; restore input pad length
FD              STD                 ; reverse string load/store direction
4E              DEC  SI             ; fix offset - SI is one char off
E8 0021         CALL BINDEC         ; DX = reversed input value
3B DA           CMP  BX, DX         ; is reversed number smaller?
76 02           JBE  MID_LOOP       ; if not, start looping through middle numbers
87 D3           XCHG DX, BX         ; otherwise swap numbers
            MID_LOOP:
43              INC  BX             ; increment middle number
3B DA           CMP  BX, DX         ; is less than end number?
73 1F           JAE  DONE           ; if not, return
8B CD           MOV  CX, BP         ; restore input pad length
8B C3           MOV  AX, BX         ; AX = next number
            DECBIN:                 ; convert value in AX to string at [DI]
03 F9           ADD  DI, CX         ; move pointer to end of padded output buffer
57              PUSH DI             ; save position for next number
4F              DEC  DI             ; fix offset - DI is one char off
            LOOP_BIT:
D1 E8           SHR  AX, 1          ; CF = LSb of number
50              PUSH AX             ; save number
B0 00           MOV  AL, 0          ; zero AL
14 30           ADC  AL, '0'        ; convert CF to ASCII
AA              STOSB               ; write char to [DI]
58              POP  AX             ; restore number
E2 F5           LOOP LOOP_BIT       ; loop next bit
5F              POP  DI             ; restore next number output offset
EB E5           JMP  MID_LOOP       ; keep looping
            BINDEC:                 ; convert ASCII binary string at [SI] to DX
33 D2           XOR  DX, DX         ; zero output value
            LOOP_DEC:
AC              LODSB               ; load next char into AL
D0 E8           SHR  AL, 1          ; CF = LSb of ASCII char
13 D2           ADC  DX, DX         ; shift LSb left onto result
E2 F9           LOOP LOOP_DEC       ; loop until end of string
            DONE:
C3              RET                 ; return to caller

```

Callable function, input binary string in `[SI]` length in `CX`, output to `[DI]`.

No helpful built-ins in machine code... just brute force string to decimal and back stuff!

Test program output:

# Answer
> 6 votes
# Jelly, 23 bytes

```
,UV€€Ḅr/BḊṖṭ@¹Uz0ZUṖṾ€€

```

Try It Online!

Follows the input format very strictly (input as string, output as list of strings including padding zeroes).

# Jelly, 8 bytes

```
,UḄr/ḊṖB

```

Try It Online!

Using actually reasonable I/O formatting, if we accept a list of digits and output as digit lists without doing leading zeroes, this is a lot more suitable for Jelly.

# Answer
> 4 votes
# Vyxal, 12 bytes

```
ṘB$BrḢƛb?L∆Z

```

Try it Online! Outputs as a list of lists of bits.

```
ṘB           # x reversed as an integer
  $B         # x as an integer
    rḢ       # Exclusive range
      ƛ      # Map...
       b     # convert to binary
          ∆Z # Zfill to...
        ?L   # Input length

```

# Answer
> 3 votes
# Pip `-p`, 27 bytes

```
0X#a-#_._MTB$,[1]+SNFB[Raa]

```

Replit! Or, here's a 28-byte equivalent in Pip Classic: Try it online!

Could be 17 bytes without the 0-padding requirement.

### Explanation

```
0X#a-#_._MTB$,[1]+SNFB[Raa]
                      [   ]  List containing
                       Ra     Reverse of argument
                         a    and argument
                    FB       Convert each from binary
                  SN         Sort in ascending order
              [1]+           Add 1 to the first (smaller) number in the list
            $,               Create a range from the first (inclusive) to the second (exclusive)
          TB                 Convert each to binary
         M                   Map this function to each:
  #a-#_                       Length of original input minus length of argument
0X                            That many zeros
       ._                     Concatenate with argument

```

# Answer
> 2 votes
# JavaScript (ES6), 88 bytes

```
x=>(f=y=>y<z[1]?[y,...f(y+1)]:[])(-~(z=["0b"+x,"0b"+[...x].reverse().join``]).sort()[0])

```

# Answer
> 2 votes
# Python, 87 bytes

```
lambda s:[f"{x:b}".zfill(len(s))for x in range(*sorted([int(s,2),int(s[::-1],2)]))][1:]
```

Attempt This Online!

Can probably be shorter, but I'm not interested in golfing it.

# Answer
> 1 votes
# Charcoal, 26 bytes

```
⊞υθ⊞υ⮌θ←Ｅ…⊕⍘⌊υ²⍘⌈υ²⮌⍘ι²ＵＢ0

```

Try it online! Link is to verbose version of code. Outputs the values in descending order. Explanation:

```
⊞υθ⊞υ⮌θ

```

Push the input and its reverse to the predefined empty list.

```
←Ｅ…⊕⍘⌊υ²⍘⌈υ²⮌⍘ι²

```

Convert the minimum and maximum of the input and its reverse from base 2, loop over the intermediate values, convert them back to base 2, then print them in reverse order and right-justified.

```
ＵＢ0

```

Fill unprinted areas with zeros.

# Answer
> 1 votes
# Python3, 74 bytes:

```
lambda x:[f"{i:b}".zfill(len(x))for i in range(int(x,2)+1,int(x[::-1],2))]

```

Try it online!

# Answer
> 1 votes
# Retina, 62 bytes

```
$
¶$^$`
O`.+
/(.+)¶\1$/^{-1`¶
¶$%`¶
)-2%T`d`10`01*$
,,-1A`
A`$

```

Try it online! Link includes test cases. Explanation:

```
$
¶$^$`

```

Append the reverse of the input.

```
O`.+

```

Sort in ascending order.

```
/(.+)¶\1$/^{
)`

```

Repeat until the last two lines are identical.

```
-1`¶
¶$%`¶

```

Duplicate the last but one line.

```
-2%T`d`10`01*$

```

Increment the newly duplicated line.

```
,,-1A`

```

Delete the original input.

```
A`$

```

Delete the line that duplicated the last line.

# Answer
> 1 votes
# APL (Dyalog Extended), ~~33~~ ~~29~~ 27 bytes

```
(∊¨-⍤≢⍕¨⍤↑¨¯1↓1↓⊢⊤¨⍤…⍥⊥⌽)⍎¨

```

Try it online!

**Explanation** (slightly outdated):

`⍎¨` Evaluate each character of the input to get a vector of 0's and 1's.
`…⍥⊥` Inclusive range, after converting the arguments from base 2: of the the vector  and its reverse `⌽⍵`.
`¯1↓1↓` Make the range exclusive by dropping one value from the start and one from the end.
`⊤¨` Convert all values in the exclusive range to base 2.
`(-≢⍵)↑¨` Pad the binary values to the length of the input with 0's in the front.
`∊¨⍕¨¨` In each binary number, convert each digit to a string, then join into a string.

# Answer
> 0 votes
# 05AB1E, 13 bytes

```
R‚CŸ¨¦bygjð0:

```

Try it online or verify all test cases.

**Explanation:**

```
R             # Reverse the (implicit) input
 ‚            # Pair it with the (implicit) input
  C           # Convert both from a binary-string to an integer
   Ÿ          # Convert this pair to a ranged list
    ¨¦        # Remove the first and last items to make it an exclusive list
      b       # Convert each integer to a binary-string
       Ig     # Push the input-length
         j    # Pad leading spaces to each binary-string to make it that length
          ð0: # Replace every space with a 0
              # (after which the result is output implicitly)

```

# Answer
> 0 votes
# JavaScript (SpiderMonkey), 90 bytes

```
x=>{for([x,y]=[1+x,1+[...x].reverse().join``].sort();++x<y;+t&&print(t.slice(3)))t='0b'+x}

```

Try it online!

# Answer
> 0 votes
# Perl 5, 84 bytes

```
sub{($_,$e,@r)=sort@_,"".reverse@_;push@r,$_ while s/01*$/$&=~y|01|10|r/e&&$_<$e;@r}

```

Try it online!

# Answer
> 0 votes
# Ruby, 78 bytes

```
->s{a,b=[s.to_i(2),s.reverse.to_i(2)].sort;(a+1...b).map{|x|"%0#{s.size}b"%x}}

```

Try it online!

---
Tags: code-golf, string, binary
---


title: All distances different on a chessboard

text:
# Question
Title: All distances different on a chessboard
*Inspired by this Puzzling SE question: All distances different on a chess board.*

## Introduction

Lets define a sequence \\$a(n), n\geqslant 1\\$ as how many pawns can you put on a \\$n \times n\\$ chessboard in such a way that all the distances between two pawns are different.

* Pawns are placed always in the centre of the square.
* The distance is simple Euclidean distance.

## Example

\\$a(4)=4\\$:

```
1100
0000
0010
0001

```

## Challenge

This is a standard challenge and the default rules apply.

This is also , so the shortest code per language wins!

## Test cases

First `9` terms: `1,2,3,4,5,6,7,7,8`.

Some more: A271490.

## Trivia/hints

* \\$a(n) \leqslant n\\$
* \\$a(n)\\$ is weakly increasing, ie. \\$a(n) \leqslant a(n+1)\\$

# Answer
# Jelly, 18 bytes

Very inefficient, \\$n=4\\$ is just on the edge of timing out on TIO.

```
Œc_/€²§QƑ
pµŒPÇƇṪL

```

Try it online!

**Commented**:

```
Œc_/€²§QƑ   -- helper function; verify a set of pawn coordinates is valid
Œc          -- unordered pairs of coordinates
  _/€       -- reduce each pair by subtraction
     ²      -- square all values
      §     -- sum to get the squared euclidean distance between each pair
       QƑ   -- is this invariant under deduplication?

p           -- cartesian product of (implicit) ranges [1..n] and [1..n]
  ŒP        -- the powerset of this (sorted by length)
    ÇƇ      -- filter the coordinate subsets on the helper function
      ṪL    -- get the length of the last subset

```
> 6 votes

# Answer
# Pyth, 16 bytes

```
lef{I.aM.cT2y*=U

```

Try it online!

Uses the standard algorithm: form all sets of points, form all pairs of points in the set, find distances, check for duplicates, find longest set without duplicates, output length.

However, there are some fun tricks to reduce the length. `*=U` is one I'm proud of.

```
lef{I.aM.cT2y*=U
               U    From input Q, form list [0..Q-1]
              =     Assign the result back to Q
             *      Take the Cartesian product with Q
                    Now, we have a list of all pairs of points.
                    The naive way would be ^UQ2, one character longer.
            y       Powerset, sorted by length
  f                 Filter the powerset on
        .cT2        Form all pairs (without repetition) of points in the set
     .aM            Map the pairs of points to their euclidean distances.
   {I               Check for duplicates (True if no duplicates)
 e                  Last element, longest remaining subset
l                   Length

```
> 6 votes

# Answer
# Python 3.8 (pre-release), 126 bytes

```
f=lambda n,i=0,l=[]:i<n*n and max(f(n,i+1,L:=l+[i//n+i%n*1j])-len(l)*len(L)/2+len({abs(p-q)for p in L for q in L}),f(n,i+1,l))

```

Try it online!

A very slow \\$ O(2^{n^2}) \\$ solution. Timeout for \\$n\>4\\$.

---

# Python 3.8 (pre-release), 130 bytes

```
f=lambda n,i=0,l=[]:i<n*n and max(len(l)*len(L:=l+[i//n+i%n*1j])/2<len({abs(p-q)for p in L for q in L})and-~f(n,i+1,L),f(n,i+1,l))

```

Try it online!

A bit faster (though time out for \\$n=8\\$), *only* need \\$ O(n^{2n}) \\$ time to rune.

-3 bytes by Jakque
> 4 votes

# Answer
# JavaScript (ES6),  ~~134 133~~  130 bytes

*Saved 3 bytes thanks to @tsh*

```
f=(n,a=[],i=0)=>-a.some(o=i=>a.some(j=>j>i&&!(o[(q=i%n-j%n)*q+(j-=i-q)*j/n/n]^=1)))||i<n*n&&Math.max(1+f(n,[...a,i],++i),f(n,a,i))

```

Try it online!

(This is just fast enough for f(8) but may time out from time to time.)

### Commented

```
f = (                       // f is a recursive function taking:
  n,                        //   n   = input
  a = [],                   //   a[] = list of pawn positions
  i = 0                     //   i   = current position (0 ≤ i < n²)
) =>                        //
-a.some(o = i =>            // for each position i in a[]:
  a.some(j =>               //   for each position j in a[]:
    j > i &&                //     test whether j is greater than i
    !(o[                    //     and this is the first time
      (q = i % n - j % n)   //     that the we encounter the
      * q +                 //     squared Euclidean distance between:
      (j -= i - q) * j      //       (i % n, j % n) and
      / n / n               //       (floor(i / n), floor(j / n))
    ] ^= 1)                 //
  )                         //   end of inner some()
)                           // end of outer some()
                            // return -1 if truthy
||                          // otherwise:
i < n * n &&                //   return 0 if i is equal to n²
Math.max(                   //   otherwise, return the maximum of:
  1 + f(n, [...a, i], ++i), //     1 + recursive call with i added to a[]
  f(n, a, i)                //     recursive call with a[] unchanged
                            //     (i is incremented in both cases)
)                           //   end of Math.max()

```
> 3 votes

# Answer
# Ruby, ~~139 ...~~ 116 bytes

```
->n{(w=*0...n*n).find{|x|w.combination(x+1).all?{|y|y.combination(2).map{|a,b|(a%n-b%n)**2+(a/n-b/n)**2}.uniq!}}||n}

```

Try it online!

Should work in theory, times out for n\>6.
> 3 votes

# Answer
# Python 3, 203 163 bytes

```
r=range
c=lambda l:len(set(l))==len(l)
f=lambda i:max(bin(j).count("1")for j in r(1<<i*i)if c([abs((a-b)%i*1j+a//i-b//i)for a in r(j)for b in r(a)if j>>a&j>>b&1]))

```

Try it online!

A simple brute force solution. The integer `j` is a binary encoded board. Next, all distances for `j` are calculated. The if-guard `j>>a&j>>b&1` checks that both selected squares are in the board `j`. Instead of `for a in r(i*i)` we can use `for a in r(j)`, since only values of `a`, where a bit is set in `j` at index `a`, matter. This means that `a < j` always (for set bits).
> 3 votes

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

```
Lãæʒ.Æ€øÆnODÙQ}éθg

```

Same exact approach as *@ovs*' Jelly answer, and it's even slightly slower, since it'll time out for \\$n=4\\$.

-1 byte thanks to *@Adnan*.

Try it online.

**Explanation:**

```
L              # Push a list in the range [1, (implicit) input]
 ã             # Cartesian power with itself to create all pairs
  æ            # Get the powerset of these coordinates
   ʒ           # Filter this by:
    .Æ         #  Get all pairs of coordinates from the current list
      €        #  Map over the pairs of coordinates:
       ø       #   Zip/transpose; swapping rows/columns
        Æ      #  Reduce each inner-most list by substracting
         n     #  Get the square of each integer
          O    #  Sum each together
               #  Check if all items are unique:
           D   #   Duplicate
            Ù  #   Uniquify the items in this copied list
             Q #   Check if it's still equal to the original list
   }é          # After the filter: sort the remaining lists of coordinates by length
     θ         # Pop and leave the last/longest one
      g        # Pop and push its length
               # (after which this is output implicitly as result)

```
> 3 votes

# Answer
# Charcoal, ~~72~~ 67 bytes

```
Ｎθ⊞υＥ²⟦⟧ＦθＦθＦυ«≔⁺§λ⁰Ｅ§λ¹ΣＸＥμ⁻ξ⎇πκι²η¿¬⊙η⊖№ημ⊞υ⟦η⁺§λ¹⟦⟦ικ⟧⟧⟧»Ｉ⌈ＥυＬ⊟ι

```

Try it online! Link is to verbose version of code. No longer manages to complete `n=6` on TIO, but that's code golf for you. Explanation:

```
Ｎθ

```

Input `n`.

```
⊞υＥ²⟦⟧

```

Start a breadth-first search with no pawns and no squared distances.

```
ＦθＦθＦυ«

```

Loop over all squares and all positions.

```
≔⁺§λ⁰Ｅ§λ¹ΣＸＥμ⁻ξ⎇πκι²η

```

Calculate the augmented set of squared distances that result when adding this pawn.

```
¿¬⊙η⊖№ημ

```

If they are all unique, then...

```
⊞υ⟦η⁺§λ¹⟦⟦ικ⟧⟧⟧

```

... add this with the updated set of pawns to the search list.

```
»Ｉ⌈ＥυＬ⊟ι

```

Output the maximum number of pawns found.
> 1 votes

# Answer
# , 112 bytes

Or **\>=4.1, 105 bytes** by replacing the word `function` with a `\`.

```
function(n){for(i in 0:2^n^2)if(all(table(dist(which(a<-!matrix(i%/%2^(1:n^2-1)%%2,n),T)))<2))T=max(T,sum(a));T}

```

Try it online!

My question with no  answer? No way!

Outputs `n`-th term `1`-indexed.

### Explanation

Straightforward brute-force approach:

* generate all numbers between \\$0\\$ and \\$2^{n^2}\\$ and convert to binary of fixed length of \\$n^2\\$
* reshape to \\$n \times n\\$ matrix
* get indices of zeros (we have to use `!` as `which` works only for logical input) - two-dimensional with `T` option
* calculate `dist`ances
* are they unique? (`all(table(...)<2)`)
* if so, how many ones did we have and update running max (kept in `T`)
> 1 votes

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