# Question
Title: Output all the white or black squares of a chessboard
### Introduction

This is how a chessboard looks like.

You can see that `a1` is a **dark** square. However, `b1` is a **light square**.

### The Task

The challenge is, given `dark`, `light` or `both`, output all the **dark**, **light** or **all squares** *with a separator* (like a whitespace or a newline). The order of all the squares *does not matter*.

### Test cases

```
Input: dark
Output: a1 a3 a5 a7 b2 b4 b6 b8
        c1 c3 c5 c7 d2 d4 d6 d8
        e1 e3 e5 e7 f2 f4 f6 f8
        g1 g3 g5 g7 h2 h4 h6 h8

Input: light
Output: a2 a4 a6 a8 b1 b3 b5 b7
        c2 c4 c6 c8 d1 d3 d5 d7
        e2 e4 e6 e8 f1 f3 f5 f7
        g2 g4 g6 g8 h1 h3 h5 h7

Input: both
Output: a1 a2 a3 a4 a5 a6 a7 a8
        b1 b2 b3 b4 b5 b6 b7 b8
        c1 c2 c3 c4 c5 c6 c7 c8
        d1 d2 d3 d4 d5 d6 d7 d8
        e1 e2 e3 e4 e5 e6 e7 e8
        f1 f2 f3 f4 f5 f6 f7 f8
        g1 g2 g3 g4 g5 g6 g7 g8
        h1 h2 h3 h4 h5 h6 h7 h8

```

*Note:* I have prettified the output but this is **not necessary**.

This is , so the submission with the least amount of bytes wins!

# Answer
> 15 votes
## Pyth, ~~22~~ 21 bytes

*-1 byte by @Sp3000*

```
fn%Chz3%sCMT2sM*<G8S8

```

Under the function `%Chz3`, `dark` hashes to 1, `light` to 0, and `both` to 2. If we take the parity of the sum of the ords of a chess square (that is, `a1` -\> `[97, 33]` -\> `(97 + 33)%2` = `0`, dark squares go to 0, and light to 1. This allows us to filter by inequality.

```
fn%Chz3%sCMT2sM*<G8S8      implicit: z=input
               *           Cartesian product of
                <G8          first 8 letters in G (alphabet)
                   S8        with [1,...,8] implicitly stringified
             sM*<G8S8      ['a1','a2,...,'a8','b1'...'h8']
f          T               Filter that by gives truthy result to lambda T:
        sCMT                   The sum of the ords of the chars in T,
       %    2                  modulo 2
 n                            does not equal
   Chz                          ord of the first char in z,
  %   3                         modulo 3
                            Implicitly print the list.

```

Try it here.

# Answer
> 13 votes
# Bash + GNU Utilities, 74

```
printf %s\\n {a..h}{1..9}|sed -n "`sed '/[db]/a1~2p
/t/a2~2p
c/9/d'<<<$1`"

```

`{a..h}{1..9}` is a bash brace expansion that produces all the coordinates for an 8x8 board, plus an extra column `9`. This is important because it makes the row length odd which allows the chequerboard effect.

The `printf` simply formats each coordinate, one per line.

The built sed expression then deletes all `x9` coordinates and then prints either even or odd or both input lines, according to the script input.

# Answer
> 11 votes
## JavaScript (SpiderMonkey 30+), ~~90~~ ~~85~~ ~~83~~ 82 bytes

```
x=>[for(d of"12345678")for(c of"abcdefgh")if(x>'l'^parseInt(c+=d,19)%2|x<'d')c]+''

```

Returns a comma-separated string of squares. Compatible version for 99 bytes:

```
x=>([..."12345678"].map(d=>[..."abcdefgh"].map(c=>c+d).filter(s=>x>'l'^parseInt(s,19)%2|x<'d')))+''

```

Works by enumerating all 64 square names, then parsing them in base 19 to see whether they are light or dark modulo 2.

# Answer
> 10 votes
# JavaScript (ES6), 82 ~~87 98~~

Anonymous function returning a space separated string of squares.

```
i=>eval("for(o='',v=190;v<322;)v++%19<8&&i<'d'|v&1^i>'l'?o+=v.toString(19)+' ':o")

```

**TEST**

```
f=i=>eval("for(o='',v=190;v<322;)v++%19<8&&i<'d'|v&1^i>'l'?o+=v.toString(19)+' ':o")

// less golfed

q=i=>{
  // loop over the range of number a0 (base 19) to h8 (base 19)
  for(o='',v=190;v<322;)
  {
    if (v++ %19 < 8) // increment and execute the line below only if second digit in 1..8
      if (i<'d'|v&1^i>'l') // even == light, odd == dark, take both if input is 'both'
        o+=v.toString(19)+' '
  }
  return o
}

document.write('<hr>Both<br>'+f('both'))
document.write('<hr>Light<br>'+f('light'))
document.write('<hr>Dark<br>'+f('dark'))
```

# Answer
> 7 votes
## Batch, 192 bytes

```
@set s=a1 a3 a5 a7
@set t=b2 b4 b6 b8
@if not %1==light call:b
@set s=a2 a4 a6 a8
@set t=b1 b3 b5 b7
@if %1==dark exit/b
:b
@echo %s% %s:a=c% %s:a=e% %s:a=g% %t% %t:b=d% %t:b=f% %t:b=h%

```

# Answer
> 4 votes
# Pyth, ~~48~~ 39 bytes

```
K*<G8S8Jfq%xGhT2%seT2K?qhz\bK?qhz\lJ-KJ

```

Try it here!

Still longer than the other Pyth solution, but I don't think I can beat this with my algorithm.

## Explanation

First we generate a list of all squares on the board and assign it to `Y`. Then we filter this list so that only light squares remain and assign this list to `J`. After that we evaluate the input and print:

* `Y` if input was `both`
* `J` if input was `light`
* `Y-J` if the input was `dark`

Determining if a square is light works as follows:

* Map the char to a number from 1-8 (a-\>1, b-\>2), results in `18` for `a8`, etc.
* check if both those numbers are odd or even (`x%2 == y%2`)
* If they are, the square is light, otherwise its dark

```

K*<G8S8Jfq%xGhT2%seT2K?qhz\bK?qhz\lJ-KJ  # z=input

 *                                         # Cartesian product of
  <G8                                      # first 8 letters of the alphabet (a-h)
     S8                                    # 1-indexed range (1-8)
K                                          # K holds now all squares
       f             K                     # Filter K
        q                                  # is equal
         %xGhT2                            # map [a-h] to a number [1-8] and take it modulo 2
               %seT2                       # Take modulo 2 from the row number
                      ?qhz\bK              # If input starts with 'b' print K
                             ?qhz\lJ       # If it starts with 'l' print J
                                    -KJ    # Otherwise print the difference of those 2

```

# Answer
> 4 votes
# PHP, ~~132~~ ~~126~~ ~~120~~ ~~108~~ 106 bytes

```
for($s=strtr($argv[1],bdl,210);$c<8;$c++)for($r=0;$r<8;)if((++$r+$c)%2==$s||$s>1)echo"abcdefgh"[$c]."$r ";

```

It loops through the cols (0-7) and rows (1-8) and checks if the sum of both is odd/even.

Tested with PHP 5.6.4, run it: `php -d error_reporting=30709 -r '<CODE>' {dark|light|both}`

# Answer
> 4 votes
## Python 2, ~~73~~ ~~71~~ 70 bytes

```
lambda s:[chr(x/8+97)+`x%8+1`for x in range(64)if x+x/8&1^ord(s[0])%3]

```

I'm still a bit confused whether functions are okay for the question, since the challenge mentions a "separator", but since there's a lot of other function submissions I've done the same.

Similar to Erwan's answer but with a ~~lot~~ bit more Python 2-ness.

*(-2 bytes thanks to @xnor)*

# Answer
> 3 votes
# Vitsy, ~~90~~ 82 bytes

```
'`'8\[1+8\:]Yy1-\?8\['1'v8\[vD1+vr?]vX]i'h'-)[88*\[Z?aO]]i'r'-)[?1m]1m
84*\[Z??aO]
```

Explanation of the first line:

```
'`'8\[1+8\:]Yy1-\?8\['1'v8\[vD1+vr?]vX]i'h'-)[88*\[Z?aO]]i'r'-)[?1m]i'g'-)[1m]
'`'                     Push ` to the stack. (this is 1 less than a in ASCII)
   8\[     ]            Do the stuff in brackets 8 times.
      1+                Add one on every recursion (this gets a, b, c, d...)
        8\:             Clone the stack 8 times. (This gets 8 of each a, b, c...)
Y                       Remove the current stack.
 y1-\?                  Go one stack to the left (I really need to builtin this)
8\[                 ]   Do the stuff in brackets 8 times.
   '1'                  Push character literal 1 to the stack.
      v                 Save it as a temporary variable.
       8\[       ]      Do the stuff in brackets 8 times.
          v             Push the temporary variable to the stack.
           D            Duplicate the top item of the stack.
            1+          Add one to it (this gives us 1, 2, 3, 4...)
              v         Capture the top item of the stack as a temporary variable.
               r        Reverse the stack.
                ?       Go a stack to the right.
                  vX    Clear the temporary variable slot.
i'h')[          ]       If the last character of the input is 'h', do the stuff in brackets
      88*\[    ]        Do the stuff in brackets 64 times.
           Z            Output everything in the stack as a character.
            ?           Rotate right a stack.
             aO         Output a newline.
i'r')[?1m]              If the penultimate character of the input is 'r', rotate over a
                        stack, then execute the first index of lines of code.
1m                      Execute the first index of lines of code.
```

Explanation of the second line:

```
84*\[Z??aO]
84*\[     ]   Do the stuff in brackets 32 times.
     Z        Output everything in the stack as a char.
      ??      Rotate two stacks over.
        aO    Output a newline.
```

There will be bonus trailing newlines for 'dark' and 'both'. Requires that only 'dark', 'both', or 'light' will be input.

Try it online!

# Answer
> 3 votes
## PowerShell v3+, ~~142~~ 129 bytes

```
param($a)$d=$a[0]-in('d','b');$l=$a[0]-in('l','b')
97..104|%{$i=[char]$_;1..8|%{if((($q=($_+$i)%2)-eq$l)-or($q+1-eq$d)){"$i$_"}}}

```

Takes input `$a` and sets two variables for if we're to output `$d`ark or `$l`ight squares based on the first letter of the input.

Then, we loop over `a-h` and `1-8` and uses the same trick as on Determine the color of a chess square to parse whether it's a light or dark square (setting helper variable `$q` in the first test) and add that square to the pipeline if appropriate. After execution, the elements on the pipeline are output one per line.

Requires v3 or newer for the `-in` operator.

Edit - Saved 13 bytes by eliminating the `switch` and by changing equality testing order

# Answer
> 3 votes
# Jolf, 48 bytes

```
Ζ-ώ~1tΜ fΜZAQ8ΨΖ+ζ|<%ζγwώt8ώ6d|<i'd!x%H2>i'ldbHγ

```

It's all greek to me ¯\\\_(ツ)\_/¯ This is a transpiling of edc65's excellent answer.

```
Ζ-ώ~1t
Ζ        set ζ to
  ώ~1     100 * 2
 -   t    minus 10 (=190)

ΜZAQ8ΨΖ+ζ|<%ζγwώt8+2t
 ZAQ8                 A zero array of length Q8 (8*8 = 64)
Μ    Ψ                map that
      Ζ+ζ             ζ +=
           %ζγwώt       ζ % (γ = 19)
          <      8      < 8
         |        ώ6  || 12

Μ f■above thing■d|<i'd!x%H2>i'ldbHγ
 _f■above thing■d                    filter the above thing
                 |<i'd!x%H2>i'l      removing all the bad stuff (i<'d'|v%2^i>'l')
Μ                              dbHγ  map each character to base 19

```

# Answer
> 3 votes
# C++, 132 bytes

Takes input by command-line. Uses pointer/modulo voodoo for print condition.

```
#include<stdio.h>
int main(int i,char**v){for(int n=0;n<64;n++)if((n+(i=n/8))%2-*v[1]%3){putchar(i+97);putchar(n%8+49);putchar(32);}}

```

# Answer
> 3 votes
# PHP, ~~99~~ ~~82~~ ~~79~~ ~~76~~ ~~74~~ 73 bytes

Uses ISO 8859-1 encoding.

```
for($z=$argv[1];++$x<72;)$x%9&&$z<c|$z>k^$x&1&&print~ß.chr($x/9+97).$x%9;

```

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

```
php -d error_reporting=30709 -r 'for($z=$argv[1];++$x<72;)$x%9&&$z<c|$z>k^$x&1&&print~ß.chr($x/9+97).$x%9; echo"\n";' dark

```

It works like this: variable `$x` is incremented from 1 to 71, the numbers correspond to the cells as shown below.

```
r\c 1  2  3  4  5  6  7  8  [invalid column]
A   1  2  3  4  5  6  7  8  9
B  10 11 12 13 14 15 16 17 18
C  19 20 21 22 23 24 25 26 27
D  28 29 30 31 32 33 34 35 36
E  37 38 39 40 41 42 43 44 45
F  46 47 48 49 50 51 52 53 54
G  55 56 57 58 59 60 61 62 63
H  64 65 66 67 68 69 70 71 72

```

Therefore, `$x modulo 9` yields the column number and `$x / 9` yields the row number, which I convert to a letter using `chr`. The code `$z<c|$z>k^$x&1` yields `true` for input `both` (`$z<c`) and in the case of `light` or `dark` only for the even or odd cells respectively (`$z>k ^ $x&1`). The result of this expression determines whether or not the cell coordinates will then be printed. Finally, if `$x modulo 9` results in `0`, I skip that non-existant cell.

* Saved ~~18~~ 17 bytes (fixed a bug) by having only 1 loop, converting the number to a char instead of the other way around
* Saved 3 bytes by combining the condition for dark and light with a `xor`
* Saved 3 bytes by comparing against the full input instead of the first char
* Saved 2 bytes because no longer need to subtract `.125` in the expression `$x/9+69.9` to get the correct row number before converting to a char
* Saved a byte by using  to yield a space

# Answer
> 3 votes
# Perl, 69 + 3 = 72 bytes

```
$b=/b/;$i=/l/;$_="@{[grep{$i=!$i||$b}map{$l=$_;map{$l.$_}1..8}a..h]}"

```

To be run with `perl -p`, for which I've added 3 bytes.

Less-golfed version (slightly different, as the babycart operator makes it hard to format nicely):

```
$b=/b/;                       # flag for input containing b
$i=/l/;                       # start $i as true if input contains 'l'

@a = grep {
    $i = !$i||$b                # alternate unless $b is true
} map {
    $l = $_;                    # save letter
    map {
        $l.$_                   # join letter and number
    } 1..8                      # generate number sequence
} a..h;                         # generate letter sequence

# golfed version uses babycart operator around array expr to save one byte
$_ = "@a"                       # write array, separated

```

The golfed version uses `"@{[]}"`; the commented version uses `@a=...; "@"` so that the commented code is still runnable.

# Answer
> 3 votes
# Java, 143

```
class H{public static void main(String[]a){for(char
c=96;++c<'i';)for(int
i=0;++i<9;)if((i+c)%2!=a[0].charAt(0)%3)System.out.println(c+""+i);}}

```

Hey, it's not the longest answer :)

Input is taken as a command-line argument.

# Answer
> 2 votes
# JavaScript ES6, ~~187~~ ~~160~~ 159 bytes

~~I'm probably missing something painfully obvious.~~ Oh well. Not having to flatten the array helps.

```
l=s=>(E=[2,4,6,8],O=[1,3,5,7],h=(z=s[0]=="d")?O:E,d=z?E:O,[...h.map(t=>[..."aceg"].map(e=>e+t)),...(d.map(t=>[..."bdfh"].map(e=>e+t))),...(s[0]=="b"?l`d`:[])])

```

Returns a 2D array.

---

Try it here:

```
l=s=>(E=[2,4,6,8],O=[1,3,5,7],h=(z=s[0]=="d")?O:E,d=z?E:O,[...h.map(t=>[..."aceg"].map(e=>e+t)),...(d.map(t=>[..."bdfh"].map(e=>e+t))),...(s[0]=="b"?l`d`:[])])

U=x=>o.innerHTML=JSON.stringify(l(i.value));
i.onchange=U;U();
```

```
*{font-family:Consolas,monospace;}
```

```
<select id=i><option value="light">light</option><option value="dark">dark</option><option value="both">both</option></select><div id=o></div>
```

# Answer
> 2 votes
**Rust, ~~263~~ ~~259~~ 244 Bytes**

```
use std::char;use std::env;fn main(){let n=env::args().nth(1).unwrap();for i in 0..8{for j in 0..8{if n=="both"||(n=="dark"&&(i+j)%2==0)||(n== "light"&&(i+j)%2!=0){println!("{}{}",char::from_u32(i+97).unwrap(),char::from_u32(j+49).unwrap())}}}}

```

Expanded Form:

```
fn main() {
    let input = env::args().nth(1).unwrap();
    for i in 0..8{
            for j in 0..8{
                if input == "both"
                || (input == "dark" && (i+j)%2==0)
                || (input == "light" && (i+j)%2!=0){
                    println!("{}{}",char::from_u32(i+97).unwrap(),char::from_u32(j+49).unwrap());
            }
        }
    }
}

```

# Answer
> 2 votes
# R, ~~129~~ 94 bytes

I knew I could generate the board better :). Essentially this builds an inverted board, filtering out grid references where the shade does not match the input. Output is space separated.

```
a=which(array(c('light','dark'),c(9,9))[-9,-9]!=scan(,''),T);cat(paste0(letters[a[,1]],a[,2]))

```

Ungolfed

```
a=which(                           # Get the indexes of
  array(c('light','dark'),c(9,9))  # an array of light dark
    [-9,-9]                        # except for the ninth row and column
      !=scan(,'')                  # where the value doesn't equal the input
    ,T                             # return array index not vector
  );
cat(paste0(letters[a[,1]],a[,2]))  # using letters for col

```

Test

```
> a=which(array(c('light','dark'),c(9,9))[-9,-9]!=scan(,''),T);cat(paste0(letters[a[,1]],a[,2]))
1: dark
2:
Read 1 item
a1 c1 e1 g1 b2 d2 f2 h2 a3 c3 e3 g3 b4 d4 f4 h4 a5 c5 e5 g5 b6 d6 f6 h6 a7 c7 e7 g7 b8 d8 f8 h8
> a=which(array(c('light','dark'),c(9,9))[-9,-9]!=scan(,''),T);cat(paste0(letters[a[,1]],a[,2]))
1: light
2:
Read 1 item
b1 d1 f1 h1 a2 c2 e2 g2 b3 d3 f3 h3 a4 c4 e4 g4 b5 d5 f5 h5 a6 c6 e6 g6 b7 d7 f7 h7 a8 c8 e8 g8
> a=which(array(c('light','dark'),c(9,9))[-9,-9]!=scan(,''),T);cat(paste0(letters[a[,1]],a[,2]))
1: both
2:
Read 1 item
a1 b1 c1 d1 e1 f1 g1 h1 a2 b2 c2 d2 e2 f2 g2 h2 a3 b3 c3 d3 e3 f3 g3 h3 a4 b4 c4 d4 e4 f4 g4 h4 a5 b5 c5 d5 e5 f5 g5 h5 a6 b6 c6 d6 e6 f6 g6 h6 a7 b7 c7 d7 e7 f7 g7 h7 a8 b8 c8 d8 e8 f8 g8 h8
>

```

# Answer
> 2 votes
# Oracle SQL 11.2, ~~192~~ 180 bytes

```
SELECT CHR(64+x),DECODE(y,0,8,y)FROM(SELECT CEIL(LEVEL/8)x,MOD(LEVEL,8)y FROM DUAL CONNECT BY LEVEL<=64)WHERE(:1='dark'AND MOD(x+y,2)=0)OR(:1='light'AND MOD(x+y,2)=1)OR(:1='both');

```

Un-golfed

```
WITH v AS
(
  SELECT CEIL(LEVEL/8)x, DECODE(MOD(LEVEL,8),0,8,MOD(LEVEL,8))y
  FROM DUAL CONNECT BY LEVEL<=64
)
SELECT CHR(64+x),y
FROM   v
WHERE  (:1='dark' AND MOD(x+y,2)=0)OR(:1='light' AND MOD(x+y,2)=1)OR(:1='both');

```

The v view generate the coordinates of each square. If the sum of the coordinates is even then the square is black, else it's white.

# Answer
> 2 votes
# MATL, 31 bytes

```
1)t3\8:t!++w4\~?H\]2#f2Y2!w)wVh

```

**Try it online!**

# Answer
> 2 votes
# Ruby, 85

I think there are shorter ways about this, but this is a cute use of `.upto`.

```
gets;'a1'.upto('h8'){|e|puts e if e[/[1-8]/]&&(~/b/||((e.ord%2!=e[1].ord%2)^! ~/l/))}

```

# Answer
> 2 votes
# Haskell, 133 116 105 100 98 91 bytes

```
f r=[["abcdefgh"!!x,"12345678"!!y]|x<-l,y<-l,odd(x+y)||r<"l",even(x+y)||r!!0/='d']
l=[0..7]

```

This is my first attempt at golfing Haskell.

With some help from Michael Klein, we managed to get it under 100 chars!

# Answer
> 2 votes
# CJam, 29

```
qci3%:X;8Ym*{~+2%X-},"a1 "f.+

```

Just a quick and dirty solution :p
Try it online

**Explanation:**

```
q           read the input
ci          convert to (first) character then to integer
3%          modulo 3; results for d(ark), l(ight) and b(oth) are 1, 0, 2
:X;         store in X and pop
8Ym*        generate all pairs (Y=2) of numbers from 0 to 7
{…},        filter using the condition block
  ~         dump the current pair on the stack
  +2%       calculate the sum modulo 2
  X-        subtract X; if the result is not 0, the pair is kept
"a1 "f.+    vectorized-add "a1 " to each remaining pair
             this means the character 'a' is added to the first number,
             the character '1' is added to the second number,
             and then the space character is appended
            the contents of the stack are automatically printed at the end

```

# Answer
> 1 votes
# Mathematica 133 bytes

**Method 1**: 108 bytes. This constructs the board as a table, with labels in each cell, and returns light or dark diagonals or bands as required.

```
Table[Table[{i,j},{i,{h,g,f,e,d,c,b,a}},{j,Range@8}]~Diagonal~k,{k,If[#=="light",-6,-7],7,If[#=="both",1,2]}]&

```

---

```
%["light"]   (*where % repeats the preceding line *)

```

> {{{b, 1}, {a, 2}}, {{d, 1}, {c, 2}, {b, 3}, {a, 4}}, {{f, 1}, {e, 2}, {d, 3}, {c, 4}, {b, 5}, {a, 6}}, {{h, 1}, {g, 2}, {f, 3}, {e, 4}, {d, 5}, {c, 6}, {b, 7}, {a, 8}}, {{h, 3}, {g, 4}, {f, 5}, {e, 6}, {d, 7}, {c, 8}}, {{h, 5}, {g, 6}, {f, 7}, {e, 8}}, {{h, 7}, {g, 8}}}

---

**Method 2**: 133 bytes. Creates an array and selects according to the even-odd nature of the sum of the row number + column number of each cell.

```
Position[Array[Boole@OddQ[#+#2] &,{8,8}],Switch[#,"dark",0,"light",1,"both",0|1]]/.
{j_,k_}:>{j/.Thread[Range@8->{a,b,c,d,e,f,g,h}],k}&

```

---

# Answer
> 1 votes
# JS, 197 bytes

```
b=[];d=[];l=[];for(i=1;i<9;i++){for(j=1;j<9;j++){a=String.fromCharCode(96+i*1)+j;b.push(a);if((i+j)%2<1){d.push(a)}else{l.push(a)}}}m=[0,"both",b,"dark",d,"light",l];alert(m[m.indexOf(prompt())+1])

```

# Answer
> 1 votes
## Python (3.5), ~~106~~ ~~100~~ ~~96~~ 92 bytes

use the trick of MegaTom `(i+j)%2` to win 6 bytes

```
f=lambda s:[chr(97+i//8)+str(1+i%8)for i in range(64)if s[0]=='b'or(i//8+i)%2==(s[0]=='l')]

```

Try it on repl.it

## Results

```
>>> f('light')
['a2', 'a4', 'a6', 'a8', 'b1', 'b3', 'b5', 'b7', 'c2', 'c4', 'c6', 'c8', 'd1', 'd3', 'd5', 'd7', 'e2', 'e4', 'e6', 'e8', 'f1', 'f3', 'f5', 'f7', 'g2', 'g4', 'g6', 'g8', 'h1', 'h3', 'h5', 'h7']
>>> f('dark')
['a1', 'a3', 'a5', 'a7', 'b2', 'b4', 'b6', 'b8', 'c1', 'c3', 'c5', 'c7', 'd2', 'd4', 'd6', 'd8', 'e1', 'e3', 'e5', 'e7', 'f2', 'f4', 'f6', 'f8', 'g1', 'g3', 'g5', 'g7', 'h2', 'h4', 'h6', 'h8']
>>> f('both')
['a1', 'a2', 'a3', 'a4', 'a5', 'a6', 'a7', 'a8', 'b1', 'b2', 'b3', 'b4', 'b5', 'b6', 'b7', 'b8', 'c1', 'c2', 'c3', 'c4', 'c5', 'c6', 'c7', 'c8', 'd1', 'd2', 'd3', 'd4', 'd5', 'd6', 'd7', 'd8', 'e1', 'e2', 'e3', 'e4', 'e5', 'e6', 'e7', 'e8', 'f1', 'f2', 'f3', 'f4', 'f5', 'f6', 'f7', 'f8', 'g1', 'g2', 'g3', 'g4', 'g5', 'g6', 'g7', 'g8', 'h1', 'h2', 'h3', 'h4', 'h5', 'h6', 'h7', 'h8']

```

**Previous version**

```
f=lambda s:[i for i in[i+j for i in'abcdefgh'for j in'123456780'][s[0]=='l'::2-(s[0]=='b')]if'0'not in i]

```

# Answer
> 1 votes
C++, 119 Bytes

Based on MegaTom's trick.

```
#include <stdio.h>
int main(int n,char**v){for(n=0;n<64;++n){if((n+n/8)%2-**(v+1)%3){printf("%c%c ",n/8+97,n%8+49);}}}

```

# Answer
> 0 votes
# C (gcc), 112 bytes

```
f(char*s){for(int m=*s^'d'?*s^'l'?3:2:1,l=64,x;l--;m&1&!x|(m&2&&x)&&printf("%c%d ",l%8+97,l/8+1))x=l%8%2^l/8%2;}

```

Try it online!

If a == 1, then a square will always be black if the "oddness" of row and column is the same, i.e. both are odd or both are even. The opposite is true for white squares, where row and column will always differ in oddness.

After that, it's just a matter of combining row and column loops, as well as consulting a table of operator precedence until a sufficient level of incomprehensibility has been reached.

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


title: Optimal path through a matrix

text:
# Question
Title: Optimal path through a matrix
Given a matrix consisting of positive integers, output the path with the lowest sum when traversing from the upper left element to the bottom right. You may move vertically, horizontally and diagonally. Note that it's possible to move both up/down, right/left and diagonally to all sides.

### Example:

```
 1*   9    7    3   10    2    2
10    4*   1*   1*   1*   7    8
 3    6    3    8    9    5*   7
 8   10    2    5    2    1*   4
 5    1    1    3    6    7    9*

```

The path giving the lowest sum is marked with asterisks, and results in the following sum: **1+4+1+1+1+5+1+9=23**.

### Test cases:

```
1   1   1
1   1   1
Output: 3

 7    9    6    6    4
 6    5    9    1    6
10    7   10    4    3
 4    2    2    3    7
 9    2    7    9    4
Output: 28

2  42   6   4   1
3  33   1   1   1
4  21   7  59   1
1   7   6  49   1
1   9   2  39   1
Output: 27 (2+3+4+7+7+1+1+1+1)

 5    6    7    4    4
12   12   25   25   25
 9    4   25    9    5
 7    4   25    1   12
 4    4    4    4    4
Output: 34 (5+12+4+4+4+1+4)

1   1   1   1
9   9   9   1
1   9   9   9
1   9   9   9
1   1   1   1
Output: 15

 2   55    5    3    1    1    4    1
 2   56    1   99   99   99   99    5
 3   57    5    2    2    2   99    1
 3   58    4    2    8    1   99    2
 4   65   66   67   68    3   99    3
 2    5    4    3    3    4   99    5
75   76   77   78   79   80   81    2
 5    4    5    1    1    3    3    2
Output: 67 (2+2+3+3+4+5+4+3+3+3+1+2+2+1+3+1+1+4+5+1+2+3+5+2+2)

```

This is so the shortest code in each language wins.

# Answer
# JavaScript, ~~442 412 408~~ 358 bytes

This is my first PPCG submission. Feedback would be appreciated.

```
(m,h=m.length,w=m[0].length)=>{for(i=0;i<h*w;i++)for(x=0;x<w;x++){for(y=0;y<h;y++){if(m[y][x]%1==0)m[y][x]={c:m[y][x],t:m[y][x]};for(X=-1;X<=1;X++)for(Y=-1;Y<=1;Y++){t=x+X;v=y+Y;if((X==0&&Y==0)||t<0||t>=w||v<0||v>=h)continue;if(m[v][t]%1==0)m[v][t]={c:m[v][t],t:null};c=m[y][x].t+m[v][t].c;if (c<m[v][t].t||m[v][t].t==null)m[v][t].t=c}}}return m[h-1][w-1].t}

```

This takes a multi-dimensional array as input.

# Explanation

Basically, loop through all of the cells over and over adjusting the lowest known cost to get to each of the neighbors. Eventually, the grid will reach a state where the total cost to reach the bottom right is the lowest cost to get there.

# Demo

```
f=(m,h=m.length,w=m[0].length)=>{for(i=0;i<h*w;i++)for(x=0;x<w;x++){for(y=0;y<h;y++){if(m[y][x]%1==0)m[y][x]={c:m[y][x],t:m[y][x]};for(X=-1;X<=1;X++)for(Y=-1;Y<=1;Y++){t=x+X;v=y+Y;if((X==0&&Y==0)||t<0||t>=w||v<0||v>=h)continue;if(m[v][t]%1==0)m[v][t]={c:m[v][t],t:null};c=m[y][x].t+m[v][t].c;if (c<m[v][t].t||m[v][t].t==null)m[v][t].t=c}}}return m[h-1][w-1].t}

//Tests
console.log(f([[1,1,1],[1,1,1]])===3);
console.log(f([[7,9,6,6,4],[6,5,9,1,6],[10,7,10,4,3],[4,2,2,3,7],[9,2,7,9,4]])===28);
console.log(f([[2,42,6,4,1],[3,33,1,1,1],[4,21,7,59,1],[1,7,6,49,1],[1,9,2,39,1]])===27);
console.log(f([[5,6,7,4,4],[12,12,25,25,25],[9,4,25,9,5],[7,4,25,1,12],[4,4,4,4,4]])===34);
console.log(f([[1,1,1,1],[9,9,9,1],[1,9,9,9],[1,9,9,9],[1,1,1,1]])===15)
console.log(f([[2,55,5,3,1,1,4,1],[2,56,1,99,99,99,99,5],[3,57,5,2,2,2,99,1],[3,58,4,2,8,1,99,2],[4,65,66,67,68,3,99,3],[2,5,4,3,3,4,99,5],[75,76,77,78,79,80,81,2],[5,4,5,1,1,3,3,2]])===67);
```

Edit: Special thanks to @ETHproductions for helping me shave dozens of tasty bytes.

More thanks to @Stewie Griffin for your tips that knocked off 50 bytes.
> 8 votes

# Answer
# Python 3 \+ numpy \+ scipy, 239 222 186 bytes

```
from numpy import*
from scipy.sparse.csgraph import*
def f(M):m,n=s=M.shape;x,y=indices(s);return dijkstra([(M*(abs(i//n-x)<2)*(abs(i%n-y)<2)).flatten()for i in range(m*n)])[0,-1]+M[0,0]

```

Try it online!
> 7 votes

# Answer
# Octave + Image Processing package, ~~175~~ ~~162~~ ~~157~~ ~~151~~ ~~142~~ 139 bytes

Saved 14 bytes thanks to @Luis Mendo and 1 byte thanks to @notjagan

```
function P(G)A=inf(z=size(G));A(1)=G(1);for k=G(:)'B=im2col(padarray(A,[1,1],inf),[3,3])+G(:)';B(5,:)-=G(:)';A=reshape(min(B),z);end,A(end)

```

Uses the Image Processing package, because why not? Isn't that how everybody solves graph problems?

Try it online!

**Exploded**

```
function P(G)
   A=inf(z=size(G));         % Initialize distance array to all Inf
   A(1)=G(1);                % Make A(1) = cost of start cell
   for k=G(:)'               % For a really long time...
      B=im2col(padarray(A,[1,1],inf),[3,3])+G(:)';
       %  B=padarray(A,[1,1],inf);     % Add border of Inf around distance array
       %  B=im2col(B,[3,3]);           % Turn each 3x3 neighborhood into a column
       %  B=B+G(:)';                   % Add the weights to each row
      B(5,:)-=G(:)';         % Subtract the weights from center of neighborhood
      A=reshape(min(B),z);   % Take minimum columnwise and reshape to original
   end
   A(end)                    % Display cost of getting to last cell

```

---

**Explanation**

Given an array of weights:

```
7   12    6    2    4
5   13    3   11    1
4    7    2    9    3
4    2   12   13    4
9    2    7    9    4

```

Initialize a cost array so that the cost to reach every element is Infinity, except the starting point (the upper left element) whose cost is equal to its weight.

```
  7   Inf   Inf   Inf   Inf
Inf   Inf   Inf   Inf   Inf
Inf   Inf   Inf   Inf   Inf
Inf   Inf   Inf   Inf   Inf
Inf   Inf   Inf   Inf   Inf

```

This is iteration 0. For each subsequent iteration, the cost to reach a cell is set to the minimum of:

* the current cost to reach that element, and
* the current cost to reach the element's neighbors + the weight of the element

After the first iteration, the cost of the path to element (2,2) (using 1-based indexing) will be

```
minimum([  7   Inf   Inf]   [13  13  13]) = 20
        [Inf   Inf   Inf] + [13   0  13]
        [Inf   Inf   Inf]   [13  13  13]

```

The full cost array after the first iteration would be:

```
  7    19   Inf   Inf   Inf
 12    20   Inf   Inf   Inf
Inf   Inf   Inf   Inf   Inf
Inf   Inf   Inf   Inf   Inf
Inf   Inf   Inf   Inf   Inf

```

After iteration `k`, each element will be the lowest cost of reaching that element from the start taking at most `k` steps. For example, the element at (3,3) can be reached in 2 steps (iterations) for a cost of 22:

```
  7    19    25   Inf   Inf
 12    20    22   Inf   Inf
 16    19    22   Inf   Inf
Inf   Inf   Inf   Inf   Inf
Inf   Inf   Inf   Inf   Inf

```

But on the 4th iteration, a path of 4 steps is found with a cost of 20:

```
 7   19   25   24   28
12   20   22   32   25
16   19   20   30   34
20   18   30   34   35
27   20   25   40   39

```

Since no path through the *mxn* matrix can be longer than the number of elements in the matrix (as a very loose upper bound), after `m*n` iterations every element will contain the cost of the shortest path to reach that element from the start.
> 6 votes

# Answer
# JavaScript, 197 bytes

```
a=>(v=a.map(x=>x.map(_=>1/0)),v[0][0]=a[0][0],q=[...(a+'')].map(_=>v=v.map((l,y)=>l.map((c,x)=>Math.min(c,...[...'012345678'].map(c=>a[y][x]+((v[y+(c/3|0)-1]||[])[x+c%3-1]||1/0)))))),v.pop().pop())

```

Prettify:

```
a=>(
  // v is a matrix holds minimal distance to the left top
  v=a.map(x=>x.map(_=>1/0)),
  v[0][0]=a[0][0],
  q=[
     // iterate more than width * height times to ensure the answer is correct
    ...(a+'')
  ].map(_=>
    v=v.map((l,y)=>
      l.map((c,x)=>
        // update each cell
        Math.min(c,...[...'012345678'].map(
          c=>a[y][x]+((v[y+(c/3|0)-1]||[])[x+c%3-1]||1/0)
        ))
      )
    )
  ),
  // get result at right bottom
  v.pop().pop()
)

```
> 5 votes

# Answer
## Mathematica 279 Bytes

Basic idea is to create a graph with vertices corresponding to matrix entries and directed edges between any two vertices separated by a `ChessboardDistance` greater than zero but less than or equal to 1. Incidentally, this happens to be known as a King graph, since it corresponds to the valid moves of a king on a chessboard.

`FindShortestPath` is then used to get the minimal path. It works on `EdgeWeight`, not `VertexWeight`, so there is some extra code to define the `EdgeWeight` as the matrix entry corresponding to the destination of each directed edge.

Code:

```
(m=Flatten[#];d=Dimensions@#;s=Range[Times@@d];e=Select[Tuples[s,2],0<ChessboardDistance@@(#/.Thread[s->({Ceiling[#/d[[1]]],Mod[#,d[[1]],1]}&/@s)])≤1&];Tr[FindShortestPath[Graph[s,#[[1]]->#[[2]]&/@e,EdgeWeight->(Last@#&/@Map[Extract[m,#]&,e,{2}])],1,Last@s]/.Thread[s->m]])&

```

Note that the  character is the transpose symbol. It will paste into Mathematica as-is.

Usage:

```
%@{{2, 55, 5, 3, 1, 1, 4, 1},
  {2, 56, 1, 99, 99, 99, 99, 5},
  {3, 57, 5, 2, 2, 2, 99, 1},
  {3, 58, 4, 2, 8, 1, 99, 2},
  {4, 65, 66, 67, 68, 3, 99, 3},
  {2, 5, 4, 3, 3, 4, 99, 5},
  {75, 76, 77, 78, 79, 80, 81, 2},
  {5, 4, 5, 1, 1, 3, 3, 2}}

```

Output:

```
67

```

If you set `g=Graph[...,GraphLayout->{"GridEmbedding","Dimension"->d},VertexLabels->Thread[s->m]` and `p=FindShortestPath[...` then the following graphic will visually display the solution (top of the matrix corresponds to the bottom of the graph):

```
HighlightGraph[g,PathGraph[p,Thread[Most@p->Rest@p]]]

```
> 4 votes

# Answer
# Haskell, 228 bytes

Positions are lists of two elements, because those are easy to generate with `sequence` and just as easy to pattern match as 2-tuples.

```
h=g[[-1,-1]]
g t@(p:r)c|p==m=0|1<2=minimum$(sum$concat c):(\q@[a,b]->c!!a!!b+g(q:t)c)#(f(e$s$(\x->[0..x])#m)$f(not.e t)$zipWith(+)p#s[[-1..1],[-1..1]])where m=[l(c)-1,l(head c)-1]
(#)=map
f=filter
e=flip elem
s=sequence
l=length

```

Start at `-1,-1` and count the cost of each steps destination field.

Alternative first two lines: start at `0,0`, count the departure fields, terminate at the coordinates equal to the matrix dimensions (so down-right from the goal, which needs to be added to the list of legal destinations) - exact same length but slower:

```
j=i[[0,0]]
i t@(p@[a,b]:r)c|p==m=0|1<2=c!!a!!b+(minimum$(sum$concat c):(\q->i(q:t)c)#(f(e$m:(s$(\x->[0..x-1])#m))$f(not.e t)$zipWith(+)p#s[[-1..1],[-1..1]]))where m=[l c,l$head c]

```

Using an infix for `map` does not save bytes here but I substitute it as soon as it doesn't cost one, because it can only get better with more uses, and sometimes with other restructurings as well which shave off another pair of parentheses.

To be improved: Redundant `filter`s. Merging/in-lining them to `filter(flip elem$(s$(\x->[0..x])#m)\\p)` with `import Data.List` for `\\` costs 3 bytes.

Also, too bad `(fromEnumTo 0)` is 2 bytes longer than `(\x->[0..x])`.

`sum$concat c` is all fields' cost summed up and thus a concisely expressible upper bound on the path cost which is given to the `minimum` to avoid an empty list (my type checker has already determined the whole thing to work on `Integer`s, so no hard-coding the maximum, hehe). No matter how I restrict steps based on the previous one made (which would speed up the algorithm a lot, but also cost bytes), I can not avoid the dead ends that make this fall-back necessary.

* One filter idea was `((not.e n).zipWith(-)(head r))` with extracting `n=s[[-1..1],[-1..1]]`, which necessitates adding `,[-1,-1]` to the initial path. The algorithm then avoids going where it could already have gone in the previous step, which makes stepping on an edge field orthogonally to that edge a dead end.
* Another was `((>=0).sum.z(*)d)` with extracting `z=zipWith`, which introduces a new argument `d` to the recursive function that is given as `(z(-)p q)` in the recursion and `[1,1]` in the initial case. The algorithm avoids successive steps with a negative scalar product (`d` being the previous step), which means no sharp 45°-turns. This still narrows down the choices considerably, and avoids the previous trivial dead end, but there are still paths that end up enclosed in already-visited fields (and possibly an 'escape' which however would be a sharp turn).
> 3 votes

# Answer
# Python 2, ~~356~~ 320 bytes

```
s=input()
r=lambda x:[x-1,x,x+1][-x-2:]
w=lambda z:[z+[(x,y)]for x in r(z[-1][0])for y in r(z[-1][1])if x<len(s)>0==((x,y)in z)<len(s[0])>y]
l=len(s)-1,len(s[0])-1
f=lambda x:all(l in y for y in x)and x or f([a for b in[l in z and[z]or w(z)for z in x]for a in b])
print min(sum(s[a][b]for(a,b)in x)for x in f([[(0,0)]]))

```

Try it here!

-36 bytes thanks to notjagan!

Receives a list of lists as an input, and outputs the lowest cost when navigating the matrix from the upper left to the bottom right.

## Explanation

Find every possible route from the upper left to the bottom right of the matrix, creating a list of x,y coordinates for each route. The routes cannot backtrack, and they must end at `(len(s)-1,len(s[0])-1)`.

Sum the integers on each path of coordinates, and return the minimum cost.

The `print` can be easily changed to output the list of coordinates for the shortest route.
> 3 votes

# Answer
# APL (Dyalog Classic), 33 bytes

```
{⊃⌽,(⊢⌊⍵+(⍉3⌊/⊣/,⊢,⊢/)⍣2)⍣≡+\+⍀⍵}

```

Try it online!

`{ }` function with argument

`+\+⍀⍵` take partial sums by row and by column to establish a pessimistic upper bound on path distances

`( )⍣≡` repeat until convergence:

* `(⍉3⌊/⊣/,⊢,⊢/)⍣2` min of distances to neighbours, i.e. do twice (`( )⍣2`): prepend leftmost column (`⊣/,`) to self () and append rightmost columns (`,⊢/`), find minima in horizontal triples (`3⌊/`) and transpose ()
* `⍵+` add each node's value to its min of distances to neighbours
* `⊢⌊` try to beat the current best distances

`⊃⌽,` finally, return the bottom right cell
> 1 votes

---
Tags: code-golf, number, graph-theory, optimization, matrix
---


title: Locally invert a Polynomial

text:
# Question
Title: Locally invert a Polynomial
### Challenge

Given a polynomial \\$p\\$ with real coefficients of order \\$1\\$ and degree \\$n\\$, find another polynomial \\$q\\$ of degree at most \\$n\\$ such that \\$(p∘q)(X) = p(q(X)) \equiv X \mod X^{n+1}\\$, or in other words such that \\$p(q(X)) = X + h(X)\\$ where \\$h\\$ is an arbitrary polynomial with \\$ord(h) \geqslant n+1\\$. The polynomial \\$q\\$ is uniquely determined by \\$p\\$.

For a polynomial \\$p(X) = a\_nX^n + a\_{n+1}X^{n+1} + ... + a\_m X^m\\$ where \\$n \leqslant m\\$ and \\$a\_n ≠ 0\\$,\\$a\_m ≠ 0\\$, we say \\$n\\$ is the *order* of \\$p\\$ and \\$m\\$ is the *degree* of \\$p\\$.

**Simplification**: You can assume that \\$p\\$ has integer coefficients, and \\$a\_1 = 1\\$ (so \\$p(X) = X + \text{\[some integral polynomial of order 2\]}\\$). In this case \\$q\\$ has integral coefficients too.

The purpose of this simplification is to avoid the issues with floating point numbers. There is however a non-integral example for illustration purposes.

### Examples

* Consider the Taylor series of \\$\exp(x)-1 = x + x^2/2 + x^3/6 + x^4/24 + ...\\$ and \\$\ln(x+1) = x - x^2/2 + x^3/3 - x^4/4 + ... \\$ then obviously \\$\ln(\exp(x)-1+1)= x\\$. If we just consider the Taylor polynomials of degree 4 of those two functions we get with the notation from below (see testcases) \\$p = \[-1/4,1/3,-1/2,1,0\]\\$ and \\$q = \[1/24, 1/6, 1/2, 1,0\]\\$ and \\$(p∘q)(X) \equiv X \mod X^5\\$

* Consider the polynomial \\$p(X) = X + X^2 + X^3 + X^4\\$. Then for \\$q(X) = X - X^2 + X^3 - X^4\\$ we get

$$(p \circ q)(X) = p(q(X)) = X - 2X^5 + 3X^6 - 10X^7 +...+ X^{16} \equiv X \mod X^5$$

### Testcases

Here the input and output polynomials are written as lists of coefficients (with the coefficient of the highest degree monomial first, the constant term last):

```
p = [4,3,2,0];  q=[0.3125,-.375,0.5,0]

```

Integral Testcases:

```
p = [1,0]; q = [1,0]

p = [9,8,7,6,5,4,3,2,1,0]; q = [4862,-1430,429,-132,42,-14,5,-2,1,0]

p = [-1,3,-3,1,0]; q = [91,15,3,1,0]

```

# Answer
> 7 votes
# Python 2 + sympy, 128 bytes

We locally invert the polynomial by assuming that q(x) = x, composing it with p, checking the coefficient for x2, and subtracting it from q. Let's say the coefficient was 4, then the new polynomial becomes q(x) = x - 4x2. We then again compose this with p, but look up the coefficient for x3. Etc...

```
from sympy import*
i=input()
p=Poly(i,var('x'));q=p*0+x
n=2
for _ in i[2:]:q-=compose(p,q).nth(n)*x**n;n+=1
print q.all_coeffs()

```

# Answer
> 3 votes
# Mathematica, 45 bytes

```
Normal@InverseSeries[#+O@x^(#~Exponent~x+1)]&

```

Yeah, Mathematica has a builtin for that....

Unnamed function taking as input a polynomial in the variable `x`, such as `-x^4+3x^3-3x^2+x` for the last test case, and returning a polynomial with similar syntax, such as `x+3x^2+15x^3+91x^4` for the last test case.

`#+O@x^(#~Exponent~x+1)` turns the input `#` into a power series object, truncated at the degree of `#`; `InverseSeries` does what it says; and `Normal` turns the resulting truncated power series back into a polynomial. (We could save those initial 7 bytes if an answer in the form `x+3x^2+15x^3+91x^4+O[x]^5` were acceptable. Indeed, if that were an acceptable format for both input and output, then `InverseSeries` alone would be a 13-byte solution.)

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

```
a=>a.reduce((r,_,i)=>[...r,i<2?i:a.map(l=>c=p.map((m,j)=>(r.map((n,k)=>p[k+=j]=m*n+(p[k]||0)),m*l+(c[j]||0)),p=[]),c=[],p=[1])&&-c[i]],[])

```

Port of @orlp's answer. I/O is in the form of arrays of coefficients in reverse order i.e. the first two coefficients are always 0 and 1.

# Answer
> 1 votes
# Pari/GP, 29 bytes

```
p->Pol(serreverse(p+O(x^#p)))

```

Try it online!

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


title: Woody words, tinny words

text:
# Question
Title: Woody words, tinny words
*Note:* There are some rude words in this question.

There's an implicit puzzle posed in this classic Monty Python sketch (you can also ready the script online).

Various phrases are described as being 'woody' or 'tinny', and one is described as being 'PVC'.

Given a phrase, respond with its type according to the following lists:

### `woody`:

```
gone
sausage
seemly
prodding
vacuum
bound
vole
caribou
intercourse
pert
thighs
botty
erogenous zone
ocelot
wasp
yowling

```

### `tinny`:

```
litter bin
newspaper
antelope
recidivist
tit
simpkins

```

### `PVC`:

```
leap

```

---

## Rules

* If the input belongs to one of the above lists, the output should be `woody`, `tinny` or `PVC`, accordingly.
* All input is lower case.
* Any behaviour is acceptable for phrases which are not listed above.
* The fewest bytes in the answer wins.

# Answer
# Stax, 30 25 bytes

```
ï═H♣║GÇX→ΩM+@╢^j╬♪►╨╝ô╤c\

```

Run and debug it

The commented ascii representation is this. I didn't invent this algorithm. It's shamelessly ripped off Jonathan Allen's python solution.

```
9@                  10th character, modularly indexed
`#!z"pi0$L+%v9`X    store "tinny pvc woody" in the x register
3(                  keep only the first 3 characters ("tin")
#                   how many times the 10th char occurs in tin? (a)
y.eaI               index of "ea" in the input or -1 (b)
+                   a + b (one of -1, 0, or 1)
xj@                 modularly indexed word in x

```

Run this one
> 4 votes

# Answer
# Python 2, ~~99~~ ~~73~~ ~~65~~ ~~64~~ 63 bytes

```
lambda s:'PVC'*('ea'in s)or'wtoiondnyy'[s[-2:]in'instperit'::2]

```

Try it online!

Alternatives also with 63 bytes:

```
lambda s:'PVC'*('ea'in s)or'wtoiondnyy'[s[-6::5]in'dtenmsr'::2]
lambda s:'PVC'*('ea'in s)or'wtoiondnyy'[s[::5]in'lrinaosit'::2]

```
> 37 votes

# Answer
# Python 2, 62 bytes

```
lambda n:'wtPoiVonCdn yy'[hash(n)%97%78%28%15%2+('ea'in n)::3]

```

Try it online!

## How?

This submission uses the fact that the `hash` function is stable for strings in Python 2. Each valid input has a valid output. The brute-forced repeated modulo `%97%78%28%15%2` returns `1` for all *tinny* and *PVC* words and `0` for *woody* words. By adding the value of `('ea' in n)` to it, we get `2` instead of `1` for the input 'leap'. Here is a table of all values:

```
+----------------+----------------------+----------------+-------------+-------+
| word           | hash                 | %97%78%28%15%2 | +('ea'in n) | type  |
+----------------+----------------------+----------------+-------------+-------+
| leap           | 5971033325577305778  | 1              | 2           | PVC   |
+----------------+----------------------+----------------+-------------+-------+
| litter bin     | 2393495108601941061  | 1              | 1           | tinny |
| newspaper      | 1961680444266253688  | 1              | 1           | tinny |
| antelope       | -2930683648135325182 | 1              | 1           | tinny |
| recidivist     | -1480015990384891890 | 1              | 1           | tinny |
| tit            | -1495230934635649112 | 1              | 1           | tinny |
| simpkins       | 672871834662484926   | 1              | 1           | tinny |
+----------------+----------------------+----------------+-------------+-------+
| gone           | 3644900746337488769  | 0              | 0           | woody |
| sausage        | 4880706293475915938  | 0              | 0           | woody |
| seemly         | -8112698809316686755 | 0              | 0           | woody |
| prodding       | 7325980211772477495  | 0              | 0           | woody |
| vacuum         | -5283515051184812457 | 0              | 0           | woody |
| bound          | -6522768127315073267 | 0              | 0           | woody |
| vole           | -7823607590901614336 | 0              | 0           | woody |
| caribou        | -3644594841083815940 | 0              | 0           | woody |
| intercourse    | 2499732157679168166  | 0              | 0           | woody |
| pert           | 4142553773863848247  | 0              | 0           | woody |
| thighs         | -3490317966011085195 | 0              | 0           | woody |
| botty          | -6522767127163072681 | 0              | 0           | woody |
| erogenous zone | 7046120593231489339  | 0              | 0           | woody |
| ocelot         | -6961879712146820842 | 0              | 0           | woody |
| wasp           | -3668927459619339511 | 0              | 0           | woody |
| yowling        | 6823632481520320220  | 0              | 0           | woody |
+----------------+----------------------+----------------+-------------+-------+

```

The type to return is now extracted from the string `'wtPoiVonCdn yy'` by taking every third character, starting at the calculated index.
> 18 votes

# Answer
# JavaScript (ES6), Chrome/Edge, 54 bytes

Because the behavior of `parseInt()` on large inputs with a radix of 36 is implementation-dependent, this one doesn't work with SpiderMonkey (Firefox).

```
s=>[,'PVC',,'Tinny'][parseInt(s+383,36)%69%7]||'Woody'

```

Try it online!

### How?

The hash function returns **3** for Tinny words, **1** for PVC and either **0**, **4**, **5** or **6** for Woody words. The words marked with an asterisk are implicitly truncated because *space* is considered as an invalid character by **parseInt()**.

```
word           | +383           | base 36 -> decimal    | mod 69 | mod 7
---------------+----------------+-----------------------+--------+------
gone           | gone383        |           36318994131 |   54   |   5
sausage        | sausage383     |      2874302392811475 |   42   |   0
seemly         | seemly383      |        80120017777107 |    6   |   6
prodding       | prodding383    |     94214834629477200 |   12   |   5
vacuum         | vacuum383      |        88266035564499 |   60   |   4
bound          | bound383       |          916101808275 |    6   |   6
vole           | vole383        |           68967369939 |   39   |   4
caribou        | caribou383     |      1249086300450771 |   63   |   0
intercourse    | intercourse383 | 3.183324871563264e+21 |   11   |   4
pert           | pert383        |           55312791699 |   21   |   0
thighs         | thighs383      |        83184557510739 |    6   |   6
botty          | botty383       |          916052399571 |   63   |   0
erogenous zone | erogenous (*)  |        41664605989780 |    7   |   0
ocelot         | ocelot383      |        68678794158483 |   39   |   4
wasp           | wasp383        |           70309896339 |   63   |   0
yowling        | yowling383     |      3523299657958227 |   39   |   4
---------------+----------------+-----------------------+--------+------
litter bin     | litter (*)     |            1301413923 |   24   |   3
newspaper      | newspaper383   |   3081816298632183000 |    3   |   3
antelope       | antelope383    |     38980419895881940 |   24   |   3
recidivist     | recidivist383  | 129824740122576960000 |    3   |   3
tit            | tit383         |            1785109395 |   45   |   3
simpkins       | simpkins383    |    104264583727840850 |   24   |   3
---------------+----------------+-----------------------+--------+------
leap           | leap383        |           46576922259 |   57   |   1

```

---

# Previous version, ~~59~~ 57 bytes

```
s=>['Woody','Tinny','PVC'][82178>>parseInt(s,35)%50%26&3]

```

Try it online!

### How?

Below are the different steps of the function for each input. The result of the first modulo is an approximation within the precision of JS numbers and is mathematically invalid for *intercourse*.

```
input          | base-35 -> dec.   | %50 | %26 | 00000000010100000100000010
---------------+-------------------+-----+-----+---------------------------
gone           |            716219 |  19 |  19 |      00------------------>
sausage        |       52042888324 |  24 |  24 | 00----------------------->
seemly         |        1492249219 |  19 |  19 |      00------------------>
prodding       |     1659396207121 |  21 |  21 |    00-------------------->
vacuum         |        1643736697 |  47 |  21 |    00-------------------->
bound          |          17573443 |  43 |  17 |        00---------------->
vole           |           1359274 |  24 |  24 | 00----------------------->
caribou        |       22625709220 |  20 |  20 |     00------------------->
intercourse    | 51532867489988450 |  48 |  22 |   00--------------------->
pert           |           1089999 |  49 |  23 |  00---------------------->
thighs         |        1549436973 |  23 |  23 |  00---------------------->
botty          |          17572449 |  49 |  23 |  00---------------------->
erogenous zone |    33308397234728 |  28 |   2 |                       00->
ocelot         |        1279159344 |  44 |  18 |       00----------------->
wasp           |           1385255 |   5 |   5 |                    00---->
yowling        |       63810499496 |  46 |  20 |     00------------------->
litter bin     |        1131250042 |  42 |  16 |         01--------------->
newspaper      |    52754217228642 |  42 |  16 |         01--------------->
antelope       |      687218151914 |  14 |  14 |           01------------->
recidivist     |  2160354371100934 |  34 |   8 |                 01------->
tit            |             36184 |  34 |   8 |                 01------->
simpkins       |     1835782971008 |   8 |   8 |                 01------->
leap           |            917900 |   0 |   0 |                         10

```
> 13 votes

# Answer
## Retina, ~~39~~ ~~38~~ 36 bytes

*Saved 1 byte by using three substitution pairs as in Adám's answer.*

```
L#-3$0`ea
PVC
.p.|is?t
tinny
$
woody

```

Try it online!

I got the `.p.|is*t` regex from Peter Norvig's regex golfer.
> 9 votes

# Answer
# Java 8, ~~81~~ ~~80~~ 67 bytes

```
s->s.charAt(2)<98?"PVC":s.matches(".*(.p.|is?t).*")?"tinny":"woody"

```

Regex from *@MatrinEnder*'s Retina answer.

Try it online.

**Original answer: ~~81~~ 80 bytes**

```
s->"anetisilire".contains(s.substring(0,2))?"tinny":s.charAt(2)<98?"PVC":"woody"

```

Try it online.

**Explanation:**

```
s->                  // Method with String as both parameter and return-type
  "anetisilire".contains(s.substring(0,2))?
                     //  If the first two letters of the input are present in "anetisilire"
    "tinny"          //   Output "tinny"
   :s.charAt(2)<98?  //  Else-if the third character of the input is an 'a'
    "PVC"            //   Output "PVC"
   :                 //  Else:
    "woody"          //   Output "woody"

```

**Additional explanation:**

```
litter bin:  anetisi(li)re
newspaper:   a(ne)tisilire
antelope:    (an)etisilire
recidivist:  anetisili(re)
tit:         ane(ti)silire
simpkins:    aneti(si)lire

```
1. None of the first two letters of the `woody` words are present in this String above, nor is `le` from `leap`.
2. None of the `woody` words has an `a` as third letter, so that is used to get `leap` to `PVC` if it's not a `tinny` word.
3. Everything else is a word from the `woody` list.
> 9 votes

# Answer
# Haskell, 61 bytes

```
f(a:b:_)|b=='i'||elem a"ran"="tinny"|a=='l'="PVC"|1>0="woody"

```

Try it online!

Uses this hand-found logic:

* Words with second letter `i` or first letter `r`, `a`, or `n` are `tinny`
* Any other word starting with `l` (`leap`) is `PVC`
* Anything else is `woody`

Lynn saved a byte by checking `leap` by its first letter.
> 6 votes

# Answer
# QuadS, ~~34~~ 32 bytes

Shamelessly uses Martin Ender's system, including the regex from Peter Norvig's regex golfer.

```
⊃⍵
ea
.p.|is?t
$
PVC
tinny
woody

```

Try it online!

`⊃⍵` pick the first occurrence of

`ea` "ea"
`.p.|is?t` "p" surrounded by letters OR "i" and "t" with an optional "s" between them
`$` end of input

… but substituting the matches with the corresponding one of the following:

`PVC`
`tinny`
`woody`

---

The equivalent 43-byte Dyalog APL function is:

```
⊃'ea' '.p.|is?t' '$'⎕S'PVC' 'tinny' 'woody'

```

Try all the cases online!
> 5 votes

# Answer
# C (gcc), ~~81~~ ~~80~~ 79 bytes

-1 byte thanks to @ceilingcat.

```
h;f(char*s){puts(index("HzYfPW",h=*s^s[1]*4&127)?"Tinny":h<120?"Woody":"PVC");}

```

Try it online!

The first order of business was to find some hash function that would separate the words into their categories. After some fiddling about I stumbled upon `(s[0] ^ (s[1] << 2)) & 0x7f`, where the 0x7f is of course there to bring it down to printable ASCII levels. This produced the following information (the tables are sorted, but not the resulting strings):

```
Woody:
----
erogenous zone  - 45
prodding        8 56
yowling         E 69
vole            J 74
intercourse     Q 81
thighs          T 84
gone            [ 91
botty           ^ 94
bound           ^ 94
ocelot          c 99
pert            d 100
caribou         g 103
seemly          g 103
vacuum          r 114
wasp            s 115
sausage         w 119

[wg8r^JgQdT^-csE

Tinny:
----
litter bin      H 72
tit             P 80
simpkins        W 87
antelope        Y 89
recidivist      f 102
newspaper       z 122

HzYfPW

PVC:
----
leap            x 120

x

```

The hash collisions don't matter, since they are confided to the same category. We only have to check if the resulting hash is in the Tinny hashes string ("HzYfPW"), since the Woody hashes are all below the PVC hash (120). If 120 or higher, and not a Tinny word, it must be PVC. If not a Tinny word, and the hash is below 120, then it must be a good, woody sort of word.
> 5 votes

# Answer
# x86 32-bit machine code, 39 bytes

Hexdump:

```
69 01 47 6f 61 2c c7 02 50 56 43 00 3a c4 74 16
c7 02 77 6f 6f 64 85 c0 78 06 c7 02 74 69 6e 6e
66 c7 42 04 79 00 c3

```

The hash function is multiplication by a "magic" number `0x2c616f47`. There are only 6 numbers that can be used with this code.

First of all, it writes `PVC` to the output. This will be overwritten, if needed.

After hashing, it checks for the PVC word; the check is `al = ah` \- I chose it because it's a small 2-byte instruction. Then, it writes either `wood` or `tinn`, depending on the sign of the hashed result. Then, it writes `y`.

Assembly code:

```
    imul eax, [ecx], 0x2c616f47;
    mov dword ptr [edx], 'CVP';
    cmp al, ah;
    je done;
    mov dword ptr [edx], 'doow';
    test eax, eax;
    js skip;
    mov dword ptr [edx], 'nnit';
skip:
    mov word ptr [edx + 4], 'y';
done:
    ret;

```
> 4 votes

# Answer
# Jelly,  ~~27~~  26 bytes

```
⁵ịe“Ṗµ»_⁼“ḣG»$ị“©LẈḊ¶$Ḍ»Ḳ¤

```

A monadic link accepting and returning lists of characters.

**Try it online!**

### How?

```
⁵ịe“Ṗµ»_⁼“ḣG»$ị“©LẈḊ¶$Ḍ»Ḳ¤ - Link: list of characters, W   e.g. "gone"  "leap"  "newspaper"
⁵                          - literal ten                  10
 ị                         - index into (1-based & modular)     'o'     'e'     'n'
   “Ṗµ»                    - compression of characters    "int"
  e                        - exists in?                          0       0       1
              $            - last two links as a monad
          “ḣG»             -   compression of characters  "leap"
         ⁼                 -   equal?                            0       1       0
        _                  - subtract                            0      -1       1
                         ¤ - nilad followed by link(s) as a nilad:
                “©LẈḊ¶$Ḍ»  -   compression of characters  "tinny PVC woody"
                         Ḳ -   split at spaces            ["tinny","PVC","woody"]
               ị           - index into (1-based & modular)     "woody" "PVC"   "tinny"

```
> 4 votes

# Answer
# Haskell, 75 bytes

*-2 bytes thanks to Laikoni.*

```
f"leap"="PVC"
f s|take 2s`elem`words"li ne ti si an re"="tinny"|1>0="woody"

```

Try it online!

RIP `enklact`.
> 3 votes

# Answer
# Dirty, ~~73~~ ~~57~~ 54 bytes

```
⇖'le'⇗≐∀⭦)Ẃ'nar'⇗{=]}⭨'i'=]'woody'‼␛['tinny'‼␛('PVC'‼␛

```

Try it online!

**Explained:**

*For a similar older version (I'll update it when I stop golfing it)*

```
␛‼'CVP'⇨⇖'leap'⇗≡⊭◌⬅Ẃ'nar'⇗{=]}1ẁ'i'=]'woody'‼␛['tinny'‼␛

```

The body of this is made up of:

```
⇖            put the input into the left stack
 'leap'      push the string "leap"
       ⇗     put that string into the right stack
        ≡    are the left and right stacks equal
         ⊭   logically negate
          ◌  skip next instruction if true
           ⬅ change direction to leftwards

```

If we end up going left, then we have:

```
       ⇨⇖'leap'⇗≡⊭◌ does stuff to the stacks, but isn't relevant
  'CVP'              push the string "PVC" (reversed, because we're going left)
 ‼                   print the string on the main stack
␛                    exit the program (this should wrap into the other exit, but that isn't working yet)

```

Otherwise, this checks if the string starts with any of "nar":

```
Ẃ           wipe the right stack
 'nar'      push the string "nar"
       ⇗    move string to right stack
        {
         =  compare the top of the left and right stacks
          ] goto matching bracket if true
        }   consuming loop while the right stack is true

```

We then check if the second letter is "i":

```
1        push the number 1
 ẁ       drop ^ number of elements off of the left stack
  'i'    push "i"
     =   are the top of the left and middle stacks equal
       ] goto matching bracket if true

```

If they all fall through, we run into

```
'woody'   push the string "woody"
       ‼  print the string on the main stack
        ␛ exit the program

```

If we ended up jumping, we wrap around to

```
[          matching bracket for the goto
 'tinny'   push the string "tinny"
        ‼  print the string on the main stack
         ␛ exit the program

```
> 3 votes

# Answer
## C# 97 Bytes

```
string t(string w)=>w[0]!='p'&new[]{10,9,8,3}.Contains(w.Length)?"tinny":w[0]=='l'?"pvc":"woody";

```

I went looking for a pattern in the length of the strings and found they are unique except for lengths 4 and 8. So I special case those by looking at the first characters. Oh well, it's still shorter than some answers. :)
> 3 votes

# Answer
# Python, 59 bytes

```
lambda w:"wtPoiVonCdn yy"[(w*4)[9]in"tin"or(w[2]<"b")*2::3]

```

**Try it online!**

Uses the indexing from ovs's Python answer but a simpler and shorter choice function:

If the tenth letter of the word, `w`, with wrapping (`(w*4)[9]` \- where `w*4` repeats `w` four times) is a letter in the word **tin** (`in"tin"`) then the word is ***tinny***, otherwise if the third letter (`w[2]`) is an **a** (`<'b'`) then the word is ***PVC*** otherwise the word is ***woody***.

...this 59 does the same job:

```
lambda w:"wtPoiVonCdn yy"[[(w*4)[9]in"tin",2][w[2]<"b"]::3]

```
> 3 votes

# Answer
# C, 107 bytes

```
k;f(char*s){for(k=0;*s;)k+=*s++;k%=100;puts(k-18?(k-5)*(k-81)*(k-56)*(k-78)*(k-37)?"woody":"tinny":"PVC");}

```

Try it online!
> 2 votes

# Answer
## Batch, 145 bytes

```
@set/ps=
@if %s%==leap echo PVC&exit/b
@for %%s in (a n r)do @if %s:~,1%==%%s echo tinny&exit/b
@if %s:~1,1%==i echo tinny&exit/b
@echo woody

```

Takes input on STDIN. Explanation: After checking for `leap`, tinny words either begin with one of the letters `a`, `n` or `r` or their second letter is `i`.
> 2 votes

# Answer
## CJam, 35 bytes

```
1b_856%338<\418=-"woodytinnyPVC"5/=

```

Try it online!

I completely forgot that I had started a brute force search for short expressions to hash the woody and tinny strings into two classes. I just found the console window where the search ran and it turns out it actually found something...

### Explanation

```
1b     e# Sum the code points of the input string.
       e# The result is unique for each input, except "pert" and "wasp" which
       e# both sum to 443. But they're both woody, so that's fine.
_      e# Duplicate.
856%   e# Take the sum modulo 856.
338<   e# Check whether the result is less than 338. That's true for all
       e# tinny words.
\      e# Swap with the other copy of the sum.
418=   e# Check whether the sum is equal to 418, which identifies "leap".
-      e# Subtract. Gives -1 for "leap", 1 for tinny words and 0 for woody words.
"woodytinnyPVC"5/
       e# Create the list ["woody" "tinny" "PVC"].
       e# Select the correct string.

```
> 2 votes

# Answer
# Japt, ~~36~~ 34 bytes

Uses a RegEx from Martin's Retina solution.

```
g2 ¶'a?"PVC":`wÅnyy`ë2Uè`?t|.pe

```

Try it | Check all test cases
> 1 votes

# Answer
# Excel, 81 bytes

```
=IF(ISNUMBER(FIND(LEFT(A1,2),"anetisilire")),"tinny",IF(A1="leap","PVC","woody"))

```

Using the 'anetisilire' method.
> 1 votes

# Answer
# JavaScript, ~~60~~, 50

**EDIT** I saw all the other regex answers. I guess I'm just blind. Anyway, here's one using the same regex

```
i=="leap"?"PVC":/.p.|is*t/.test(i)?"tinny":"woody"

```

Also, now, it beats the other JS answer

Snippet:

```
let test = i => i=="leap"?"PVC":/.p.|is*t/.test(i)?"tinny":"woody"

let woody = `gone
sausage
seemly
prodding
vacuum
bound
vole
caribou
intercourse
pert
thighs
botty
erogenous zone
ocelot
wasp
yowling`;
console.log("THESE SHOULD BE woody");
woody.split("\n").forEach(el => console.log(test(el)));
let tinny = `litter bin
newspaper
antelope
recidivist
tit
simpkins`;
console.log("THESE SHOULD BE tinny");
tinny.split("\n").forEach(el => console.log(test(el)));
console.log("THIS SHOULD BE PVC");
console.log(test("leap"));
```

## Old answer

I didn't see any with regex yet, so I thought I'd give it a try

```
i=="leap"?"PVC":/[gyuz]|[or][tl]|as/.test(i)?"woody":"tinny"

```

Not sure if this counts as 60 or more because I didn't include a return statement. Will add a snippet when I get on my computer

**Edit: Snippet**

```
let test = i => i=="leap"?"PVC":/[gyuz]|[or][tl]|as/.test(i)?"woody":"tinny"

let woody = `gone
sausage
seemly
prodding
vacuum
bound
vole
caribou
intercourse
pert
thighs
botty
erogenous zone
ocelot
wasp
yowling`;
console.log("THESE SHOULD BE woody");
woody.split("\n").forEach(el => console.log(test(el)));
let tinny = `litter bin
newspaper
antelope
recidivist
tit
simpkins`;
console.log("THESE SHOULD BE tinny");
tinny.split("\n").forEach(el => console.log(test(el)));
console.log("THIS SHOULD BE PVC");
console.log(test("leap"));
```
> 1 votes

---
Tags: code-golf, string, classification
---


title: Rotate the Roots

text:
# Question
Title: Rotate the Roots
Given a nonzero polynomial with integer coefficients and roots that are on the imaginary and on the real line such that if `a` is a root then so is `-a`, return another polynomial with the roots rotated by 90 degrees.

### Details

The polynomial can be given in any reasonable format, e.g. as a list of coefficients. The symmetry condition that `a` is a root if and only if `-a` is a root too enforces the rotated polynomial to have real integer coefficients as well.

### Examples

In the following the polynomials are given as a list of coefficient of the monomials in descending degree. (i.e. the constant comes last) The polynomial `x^2-1` has roots `{1,-1}`. Rotating them by `90°` means multiplying by `i` (the imaginary unit), so the output polynomial should have the roots `{i,-i}`, which is `x^2 + 1`.

```
Input / Output
[1 0 10 0 -127 0 -460 0 576]  [1 0 -10 0 -127 0 460 0 576]
[1 0 -4 0] [1 0 4 0]
[1] [1]

```

# Answer
## Mathematica, 10 Bytes

Pure function which takes a function of x and substitutes in ix.

```
#/.x->I*x&

```

Alternative with only 7 bytes but not quite sure if it counts. Pure function which takes in a pure function and returns a function of x.

```
#[I*x]&

```
> 12 votes

# Answer
# Jelly, 5 bytes

```
Jı*Ċ×

```

Try it online!

## How it works

Multiplies the first element by `1`, the third element by `-1`, etc.

```
Jı*Ċ×  argument: z
J      [1,2,...,len(z)]
 ı     i (the imaginary unit)
  *    to the power of (each element)
   Ċ   imaginary part
    ×  multiply by input (vectorize)

```

## Proof of algorithm

Let the polynomial be `f(x)`.

Since we are guaranteed that if `x` is a root then so is `-x`, so `f` must be even, meaning that its coefficient for the odd powers must be `0`.

Now, rotating the roots by `90°` is essentially `f(ix)`.

Expanding then comparing coefficients proves the algorithm.
> 7 votes

# Answer
## JavaScript (ES6), 25 bytes

```
a=>a.map((e,i)=>i%4?-e:e)

```

The original polynomial has solutions of the form `x = ±a` where a lies on the real or imaginary line. Except when `a = 0` (in which case `x` is a factor of the polynomial), this means that `x² - a²` is a factor of the polynomial (which means alternate terms are always zero). Now when we rotate the roots, the factor changes to `x² + a²`. Since all the factors change at the same time, the third term of the polynomial, which is the sum of all the `-a²` terms, changes sign, the fifth term, which is the sum of products of pairs of `-a²` terms, keeps the same sign, etc. alternating every other term.
> 5 votes

# Answer
# Octave, 27 bytes

```
@(x)round(poly(roots(x)*j))

```

Try it online!

This directly applies the definition: compute roots, multiply by `j`, convert back from roots to polynomial. A final rounding is necessary because of floating-point numerical errors.
> 4 votes

# Answer
# Python 3, 42 bytes

```
f=lambda x,s=1:x and[0,x[0]*s]+f(x[2:],-s)

```

Try it online!
> 2 votes

# Answer
# S.I.L.O.S, ~~71~~ 66 bytes

```
readIO
b=i
lbla
readIO
d=c
d&2
i=i*(1-d)
printInt i
b-1
c+1
if b a

```

Try it online!

~~I have no clue what wizardry @Leaky Nun did here to save 5 bytes.~~

Took me a second to figure out, but The second bit of C will alternate like we want. Therefore @Leaky Nun exploited this to save the bits we need.
> 1 votes

# Answer
# Casio-Basic, 8 bytes

```
n|x=x

```

Unnamed function, using Ian Miller's Mathematica approach. The imaginary from the Math2 keyboard needs to be used (counts as 2 bytes, char code 769), and the polynomial should be entered as an equation of `x`.

7 bytes for the code, 1 byte to specify `n` as a parameter.

**Explanation**: Takes the equation `n`, then simply replaces all instances of `x` with `x`.
> 0 votes

# Answer
# Pari/GP, 16 bytes

```
p->x=I*x;eval(p)

```

Try it online!
> 0 votes

# Answer
# TI-Basic, 20 bytes

```
seq(real(i^X/i)Ans(X),X,1,dim(Ans

```

If stored in `prgmA`, run with:

```
{1, 0, 3, 0, 1}:prgmA

```

`seq(` just had to be the *one** command that doesn't support complex numbers. :)

<sub>\*: Exaggeration</sub>
> 0 votes

# Answer
# Stax, 5 bytes

```
Æ[]▐↨

```

Run and debug online!

Port of the Jelly answer.

Uses ASCII representation to explain:

```
mih|1*
m         Map each element with rest of program, print mapped results on individual lines
 i        Current 0-based loop index
  h       Floor(i/2)
   |1     (-1)^(i/2)
     *    Multiply with current element

```

If there can be leading zeros, they need to be trimmed first and it can be done at the cost of another byte.
> 0 votes

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


# Question
Title: Compute the Binary Sierpinski Triangle Sequence
The Binary Sierpinski Triangle sequence is the sequence of numbers whose binary representations give the rows of the Binary Sierpinski Triangle, which is given by starting with a 1 in an infinite row of zeroes, then repeatedly replacing every pair of bits with the xor of those bits, like so:

```
f(0)=      1                    =1
f(1)=     1 1                   =3
f(2)=    1 0 1                  =5
f(3)=   1 1 1 1                 =15
f(4)=  1 0 0 0 1                =17

```

More digits are given at OEIS: https://oeis.org/A001317

Input: A non-negative integer n in any format you like. (Must work for all n up to 30.)

Output: The nth term (0-indexed) of the sequence as a decimal number.

This is so try give the shortest answer in bytes of which your language is capable. No answer will be accepted. Standard loopholes apply (e.g. no hard-coding the sequence), except that you *may* use a language created/modified after this challenge was posted. (Do avoid posting another solution in a language that has already been used unless your solution is shorter.)

## Leaderboard

The Stack Snippet at the bottom of this post generates the catalogue from the answers a) as a list of shortest solution per language and b) as an overall leaderboard.

To make sure that your answer shows up, please start your answer with a headline, using the following Markdown template:

```
## Language Name, N bytes

```

where `N` is the size of your submission. If you improve your score, you *can* keep old scores in the headline, by striking them through. For instance:

```
## Ruby, <s>104</s> <s>101</s> 96 bytes

```

If there you want to include multiple numbers in your header (e.g. because your score is the sum of two files or you want to list interpreter flag penalties separately), make sure that the actual score is the *last* number in the header:

```
## Perl, 43 + 2 (-p flag) = 45 bytes

```

You can also make the language name a link which will then show up in the snippet:

```
## [><>](http://esolangs.org/wiki/Fish), 121 bytes

```

```
/* Configuration */

var QUESTION_ID = 67497; // Obtain this from the url
// It will be like http://XYZ.stackexchange.com/questions/QUESTION_ID/... on any question page
var ANSWER_FILTER = "!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe";
var COMMENT_FILTER = "!)Q2B_A2kjfAiU78X(md6BoYk";
var OVERRIDE_USER = 47050; // This should be the user ID of the challenge author.

/* App */

var answers = [], answers_hash, answer_ids, answer_page = 1, more_answers = true, comment_page;

function answersUrl(index) {
  return "http://api.stackexchange.com/2.2/questions/" +  QUESTION_ID + "/answers?page=" + index + "&pagesize=100&order=desc&sort=creation&site=codegolf&filter=" + ANSWER_FILTER;
}

function commentUrl(index, answers) {
  return "http://api.stackexchange.com/2.2/answers/" + answers.join(';') + "/comments?page=" + index + "&pagesize=100&order=desc&sort=creation&site=codegolf&filter=" + COMMENT_FILTER;
}

function getAnswers() {
  jQuery.ajax({
    url: answersUrl(answer_page++),
    method: "get",
    dataType: "jsonp",
    crossDomain: true,
    success: function (data) {
      answers.push.apply(answers, data.items);
      answers_hash = [];
      answer_ids = [];
      data.items.forEach(function(a) {
        a.comments = [];
        var id = +a.share_link.match(/\d+/);
        answer_ids.push(id);
        answers_hash[id] = a;
      });
      if (!data.has_more) more_answers = false;
      comment_page = 1;
      getComments();
    }
  });
}

function getComments() {
  jQuery.ajax({
    url: commentUrl(comment_page++, answer_ids),
    method: "get",
    dataType: "jsonp",
    crossDomain: true,
    success: function (data) {
      data.items.forEach(function(c) {
        if (c.owner.user_id === OVERRIDE_USER)
          answers_hash[c.post_id].comments.push(c);
      });
      if (data.has_more) getComments();
      else if (more_answers) getAnswers();
      else process();
    }
  });
}

getAnswers();

var SCORE_REG = /<h\d>\s*([^\n,<]*(?:<(?:[^\n>]*>[^\n<]*<\/[^\n>]*>)[^\n,<]*)*),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/;

var OVERRIDE_REG = /^Override\s*header:\s*/i;

function getAuthorName(a) {
  return a.owner.display_name;
}

function process() {
  var valid = [];

  answers.forEach(function(a) {
    var body = a.body;
    a.comments.forEach(function(c) {
      if(OVERRIDE_REG.test(c.body))
        body = '<h1>' + c.body.replace(OVERRIDE_REG, '') + '</h1>';
    });

    var match = body.match(SCORE_REG);
    if (match)
      valid.push({
        user: getAuthorName(a),
        size: +match[2],
        language: match[1],
        link: a.share_link,
      });
    else console.log(body);
  });

  valid.sort(function (a, b) {
    var aB = a.size,
        bB = b.size;
    return aB - bB
  });

  var languages = {};
  var place = 1;
  var lastSize = null;
  var lastPlace = 1;
  valid.forEach(function (a) {
    if (a.size != lastSize)
      lastPlace = place;
    lastSize = a.size;
    ++place;

    var answer = jQuery("#answer-template").html();
    answer = answer.replace("{{PLACE}}", lastPlace + ".")
                   .replace("{{NAME}}", a.user)
                   .replace("{{LANGUAGE}}", a.language)
                   .replace("{{SIZE}}", a.size)
                   .replace("{{LINK}}", a.link);
    answer = jQuery(answer);
    jQuery("#answers").append(answer);

    var lang = a.language;
    lang = jQuery('<a>'+lang+'</a>').text();

    languages[lang] = languages[lang] || {lang: a.language, lang_raw: lang, user: a.user, size: a.size, link: a.link};
  });

  var langs = [];
  for (var lang in languages)
    if (languages.hasOwnProperty(lang))
      langs.push(languages[lang]);

  langs.sort(function (a, b) {
    if (a.lang_raw.toLowerCase() > b.lang_raw.toLowerCase()) return 1;
    if (a.lang_raw.toLowerCase() < b.lang_raw.toLowerCase()) return -1;
    return 0;
  });

  for (var i = 0; i < langs.length; ++i)
  {
    var language = jQuery("#language-template").html();
    var lang = langs[i];
    language = language.replace("{{LANGUAGE}}", lang.lang)
                       .replace("{{NAME}}", lang.user)
                       .replace("{{SIZE}}", lang.size)
                       .replace("{{LINK}}", lang.link);
    language = jQuery(language);
    jQuery("#languages").append(language);
  }

}
```

```
body { text-align: left !important}

#answer-list {
  padding: 10px;
  width: 290px;
  float: left;
}

#language-list {
  padding: 10px;
  width: 290px;
  float: left;
}

table thead {
  font-weight: bold;
}

table td {
  padding: 5px;
}
```

```
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>
<link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b">
<div id="language-list">
  <h2>Shortest Solution by Language</h2>
  <table class="language-list">
    <thead>
      <tr><td>Language</td><td>User</td><td>Score</td></tr>
    </thead>
    <tbody id="languages">

    </tbody>
  </table>
</div>
<div id="answer-list">
  <h2>Leaderboard</h2>
  <table class="answer-list">
    <thead>
      <tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr>
    </thead>
    <tbody id="answers">

    </tbody>
  </table>
</div>
<table style="display: none">
  <tbody id="answer-template">
    <tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr>
  </tbody>
</table>
<table style="display: none">
  <tbody id="language-template">
    <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr>
  </tbody>
</table>
```

# Answer
> 14 votes
# 05AB1E, ~~5~~ 4 bytes

I proudly present to you, 05AB1E. Although it is very short, it is probably very bad at long challenges.

Thanks to ETHproductions for shaving off 1 byte :)

```
$Fx^

```

Explanation:

```
$      # Pushes 1 and input
 F     # Pops x, creates a for-loop in range(0, x)
  x    # Pops x, pushes x and 2x
   ^   # Bitwise XOR on the last two elements
       # Implicit, ends the for-loop
       # Implicit, nothing has printed so the last element is printed automatically

```

# Answer
> 12 votes
# Pari/GP, 27 bytes

```
n->lift(Mod(x+1,2)^n)%(x-2)

```

The function takes the \\$n\\$-th power of the polynomial \\$x+1\\$ in the ring \\$\mathbb{F}\_2\[X\]\\$, lifts it to \\$\mathbb{Z}\[X\]\\$, and then evaluates it at \\$x=2\\$.

Try it online!

# Answer
> 6 votes
# Jelly, 6 bytes

```
1Ḥ^$³¡

```

Try it online!

The binary version that works with this revision of the Jelly interpreter has the xxd dump

```
0000000: 31 a8 5e 24 8b 80  1.^$..

```

### How it works

```
1Ḥ^$³¡    Input: n

1         Set the left argument to 1.
 Ḥ        Multiple the left argument by two.
  ^       Hook; XOR it with its initial value.
   $      Create a monadic chain from the last two insructions.
    ³¡    Call the chain n times, updating the left argument after each call.

```

# Answer
> 5 votes
# Haskell, 44 bytes

```
import Data.Bits
f n=iterate((2*)>>=xor)1!!n

```

In the `((->) r)` monad, `(f >>= g) x` equals `g (f x) x`.

# Answer
> 4 votes
# JavaScript (ES6), 23 bytes

```
f=x=>x?(y=f(x-1))^y*2:1

```

Based on the first formula on the OEIS page. If you don't mind the code taking almost forever to finish for an input of 30, we can shave off a byte:

```
f=x=>x?f(--x)^f(x)*2:1

```

Here's a non-recursive version, using a `for` loop in an `eval`: (32 bytes)

```
x=>eval("for(a=1;x--;a^=a*2);a")

```

# Answer
> 4 votes
## Matlab, 45 bytes

Solution:

```
@(i)2.^[0:i]*diag(mod(fliplr(pascal(i+1)),2))

```

Test:

```
ans(10)
ans =
1285

```

Explanation: `pascal` constructs Pascal triangle, but it starts from 1, so input should be `i+1`. `fliplr` flips array from left to right. `mod(_,2)` takes remainder after division by 2. `diag` extracts main diagonal.Multiplication using `2.^[0:i]` converts vector to decimal

I'm glad, @flawr that I found Matlab competitor here :)

# Answer
> 3 votes
# Matlab, ~~77~~ 70 bytes

This function calculates the n-th row of the Pascal triangle via repeated convolution with `[1,1]` (a.k.a. binomial expansion or repeated multiplication with a binomial), and calculates the number from that.

```
function r=c(n);k=1;for i=1:n;k=conv(k,[1,1]);end;r=2.^(0:n)*mod(k,2)'

```

# Answer
> 3 votes
## CJam, 10 bytes

```
1ri{_2*^}*

```

Test it here.

Simple iterative solution using bitwise XOR.

# Answer
> 3 votes
# Ruby, 26 bytes

anonymous function with iteration.

```
->n{a=1;n.times{a^=a*2};a}

```

this recursive function is one byte shorter, but as it needs to be named to be able to refer to itself, it ends up one byte longer.

```
f=->n{n<1?1:(s=f[n-1])^s*2}

```

# Answer
> 3 votes
# Samau, 4 bytes

Now Samau has built-in functions for XOR multiplication and XOR power.

```
▌3$ⁿ

```

Hex dump (Samau uses CP737 encoding):

```
dd 33 24 fc

```

Explanation:

```
▌       read a number
 3      push 3
  $     swap
   ⁿ    take the XOR power

```

# Answer
> 3 votes
# Ruby, 25 bytes

```
->n{eval"n^=2*"*n+?1*n=1}

```

Shorter than the other answers on here so far. It constructs this string:

```
n^=2*n^=2*n^=2*n^=2*1

```

Then it sets `n=1` (this actually happens while the string is being made) and evaluates the above string, returning the result.

# Answer
> 2 votes
# MIPS, 28 bytes

Input in `$a0`, output in `$v0`.

```
0x00400004  0x24020001          li      $v0, 1
0x00400008  0x10800005  loop:   beqz    $a0, exit
0x0040000c  0x00024021          move    $t0, $v0
0x00400010  0x00021040          sll     $v0, $v0, 1
0x00400014  0x00481026          xor     $v0, $v0, $t0
0x00400018  0x2084ffff          addi    $a0, $a0, -1
0x0040001c  0x08100002          j       loop

```

# Answer
> 2 votes
# Pure Bash (no external utilities), 37

Bash integers are 64-bit signed, so this works for inputs up to and including 62:

```
for((x=1;i++<$1;x^=x*2)){
:
}
echo $x

```

# Answer
> 2 votes
## Python 2.7.6, 38 33 bytes

Thanks to Dennis for shaving off a few bytes!

```
x=1
exec'x^=x*2;'*input()
print x

```

# Answer
> 2 votes
# MATL, 15 bytes

Similar to @flawr's answer:

```
i:1w"TToX+]2\XB

```

*EDIT (May 20, 2016) Try it online! with `X+` replaced by `Y+` to conform to version 18.0.0 of the language.*

### Example

```
>> matl i:1w"TToX+]2\XB
> 5
51

```

### Explanation

```
i              % input
:              % vector of values 1, 2, ... to previous input
1              % number literal
w              % swap elements in stack
"              % for
    TTo        % vector [1 1]
    X+         % convolution
]              % end
2\             % modulo 2
XB             % convert from binary to decimal

```

# Answer
> 2 votes
# Pyth, 7 bytes

```
uxyGGQ1

```

Try it online: Demonstration

### Explanation:

```
u    Q1   apply the following statement input-times to G=1:
 xyGG        update G with (2*G xor G)

```

# Answer
> 2 votes
# Perl 5, 23 bytes

```
$.^=2*$.for 1..<>;say$.

```

Try it online!

# Answer
> 1 votes
# Mathematica, ~~40~~ 24 bytes

```
Nest[BitXor[#,2#]&,1,#]&

```

# Answer
> 1 votes
## k4, 26 bytes

```
{x{2/:~(=). 0b\:'1 2*x}/1}

```

`0b\:` converts a number to a boolean vector (i.e. bitstring), XOR is implemented as "not equal", `2/:` converts a bitstring back to a number by treating it as a polynomial to evaluate, and `x f/y` with `x` an integer is `f` applied to `y` first, and then to its successive outputs `x` times.

Sample run:

```
  {x{2/:~(=). 0b\:'1 2*x}/1}'!5
1 3 5 15 17

```

# Answer
> 1 votes
# Ruby, ~~31~~ 26 bytes

**EDIT:** Changed to a different language entirely! All golfing suggestions welcome!

This program bitwise XORs the previous element of the sequence with twice itself, i.e. `f(n) = f(n-1) ^ 2*f(n-1)`.

```
->n{v=1;n.times{v^=2*v};v}

```

# Answer
> 1 votes
# brainfuck, 87 bytes

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

```

Try it online!

Assumes infinite sized cells (otherwise it can’t get past 7, which is conveniently 255). The Pascal’s triangle mod 2 method is actually much longer because of the costly mod 2 operation, while XOR is much easier to implement.

# Answer
> 1 votes
# Stax, 5 bytes

```
±s┤ε─

```

Run and debug online!

Port of the Jelly answer.

Uses ASCII representation to explain:

```
ODcH|^
O         Put 1 under top of stack
 D        Repeat for times specified by input
  cH|^    Xor the number with itself doubled
          Implicit output

```

# Answer
> 0 votes
## Seriously, 12 bytes

```
2,╣`2@%`Mεj¿

```

Hex Dump:

```
322cb960324025604dee6aa8

```

Try it online

Since Seriously does not include any means of doing a bitwise xor, this solution takes the challenge completely literally, directly computing the given row of the triangle. This method gives correct answers up to n=1029 (after which there is not enough memory to compute the given row of Pascal's triangle).

Explanation:

```
 ,                       get input
  ╣                 push the nth row of pascal's triangle
   `2@%`M           take each element of the row mod 2
         εj         join all the binary digits into a string
2          ¿        interpret it as a base 2 number

```

# Answer
> 0 votes
## APL, 31 bytes

```
{({2⊥⊃~1 2=.{(64⍴2)⊤⍺×⍵}⍵}⍣⍵)1}

```

This is almost certainly awful code, but I'm a complete APL newb. I expect anyone with any skill could get rid of all the D-functions and shorten it considerably. The logic is more or less the same as my `k4` answer -- multiply by `1` or `2`, convert to bits with , XOR using not equals, convert back to a number with , wrap the whole thing in a function and ask for a specific number of iterations using . I have no idea why the result coming out of the inner product is enclosed, but  cleans that up.

# Answer
> 0 votes
# Pyt, ~~40~~ 10 bytes

```
Đ0⇹Řć2%ǰ2Ĩ

```

Explanation:

Observing that the Binary Sierpinski Triangle is equivalent to Pascal's Triangle mod 2,

```
                      Implicit input
Đ                     Duplicate input
 0⇹Ř                  Push [0,1,2,...,input]
    ć2%               Calculate the input-th row of Pascal's Triangle mod 2
       ǰ              Join elements of the array into a string
        2Ĩ            Interpret as a binary number
                      Implicit print

```

Try it online!

---
Tags: code-golf, sequence, binary, bitwise
---


title: Generate a heap of boxes

text:
# Question
Title: Generate a heap of boxes
(The text asks how many boxes there are in the picture)

Now you are required to generate such a problem and its answer.

# Input

* an integer `n`
* (optionally) random source of two values, in case you don't want to use the default random.

# Output can be

* a 3D array `A[n][n][n]` of booleans, where `A[i][j][k] => (i==0 || A[i-1][j][k]) && (j==0 || A[i][j-1][k]) && (k==0 || A[i][j][k-1])` (assuming 0-index)
where `&&` is logical AND, `||` is logical OR, and `=>` is "implies" (if `X` is true, then `Y` is true).

Basically this says that if you have a box at some position then for each coordinate that coordinate must be either `0` or also have a box if that coordinate is one less. So no holes in any direction that gets you closer to the origin.
* a 2D array `B[n][n]` of integers, where `B[i][j]` means how many `k` satisfy `A[i][j][k]`

Basically this is the height of the stacks where these heights can't become lower in any direction that gets you closer to the origin.
* Besides the array, the amount of boxes (how many `i,j,k` satisfy `A[i][j][k]`)

Every valid output should have nonzero probability to be outputted.

Example: (Here use 2D output format for convenience)

```
1 => [[0]] 0 or [[1]] 1
2 => [[0,0],[0,0]] 0
     [[1,0],[0,0]] 1
     [[1,0],[1,0]] 2
     [[1,1],[0,0]] 2
     [[1,1],[1,0]] 3
     [[1,1],[1,1]] 4
     [[2,0],[0,0]] 2
     [[2,0],[1,0]] 3
     [[2,0],[2,0]] 4
     [[2,1],[0,0]] 3
     [[2,1],[1,0]] 4
     [[2,1],[1,1]] 5
     [[2,1],[2,0]] 5
     [[2,1],[2,1]] 6
     [[2,2],[0,0]] 4
     [[2,2],[1,0]] 5
     [[2,2],[1,1]] 6
     [[2,2],[2,0]] 6
     [[2,2],[2,1]] 7 or
     [[2,2],[2,2]] 8

```

So for input `2` your program should randomly return one of the 20 possible outputs, and if run enough times every one of them should be returned at some point.

Your program must terminate.

# Winning criteria

This is , shortest code in bytes win!

# Answer
# Perl 5, `-ap` 121 bytes / 56 bytes

This 121 byte solution has a uniform distribution over all valid arrangements of boxes. It tries to be somewhat efficient but still times out on TIO for size 4 or more

```
#!/usr/bin/perl -ap
@a=((0 x$_.$")x$_.$/)x$_."";s%0%/0(|.{@F}|(\X{@F}\X){@F})\G/+${$z="$`1$'"}++||push@a,$z;0%eg for@a;$_=$a[rand@a];$\=y/1//

```

Try it online!

If you don't care about uniformity it's of course easy to go shorter, e.g. this 56 bytes solution is very biased towards the origin (it probably gives more nice pictures for the motivating example though)

```
#!/usr/bin/perl -a
say map{\@$_[rand@;+1,$#{$_-1}];@;-$#$_.$"}@;for@;=1..$_

```

Try it online!

(checked for size 2 and 3 that it indeed generates all possible outputs)
> 4 votes

# Answer
# Python 2, 144 bytes

```
from random import*
n=input()
a=[n]*n*n
for x in range(n*n):a[x]=randint(0,min(a[x-(x%n>0)],a[x-n]))
print[a[i*n:i*n+n]for i in range(n)],sum(a)

```

Try it online!

Quick and dirty solution.

Generates a random number (which is upper-bounded by its left (if present) and upper cells) for each cell as a linear array, and then prints its 2D version and the sum.
> 2 votes

# Answer
## JavaScript (ES6), 100 bytes

```
n=>[...Array(n)].map((_,i,a)=>k=a.map((_,j)=>l=0|Math.random()*-~(i?j?Math.min(k[j],l):k[0]:j?l:n)))

```
> 2 votes

# Answer
# Jelly, 16 bytes

```
³‘X’¤þ`ṂƤ€Z$⁺ṄS⁺

```

Try it online!

---

I made a terrible mistake. No idea why no-one noticed that.

Full program. Prints the array and the sum.

Not uniform, of course. Return all-zero most of the time.

Verification for side length 2.
> 1 votes

---
Tags: code-golf, random
---


title: Decompose Polynomials

text:
# Question
Title: Decompose Polynomials
Given an integral polynomial of degree strictly greater than one, completely decompose it into a composition of integral polynomials of degree strictly greater than one.

### Details

* An *integral polynomial* is a polynomial with only integers as coefficients.
* Given two polynomials `p` and `q` the *composition* is defined by `(p∘q)(x):=p(q(x))`.
* The *decomposition* of an integral polynomial `p` is a finite ordered sequence of integral polynomials `q1,q2,...,qn` where `deg qi > 1` for all `1 ≤ i ≤ n` and `p(x) = q1(q2(...qn(x)...))`, and all `qi` are not further decomposable. The decomposition is not necessarily unique.
* You can use e.g. lists of coefficients or built in polynomial types as input and output.
* Note that many builtins for this task actually decompose the polynomials over a given *field* and not necessarily integers, while this challenge requires a decomposition integer polynomials. (Some integer polynomials might admit decomposition into integer polynomials as well as decomposition that contain rational polynomials.)

### Examples

```
x^2 + 1
[x^2 + 1] (all polynomials of degree 2 or less are not decomposable)
x^6 - 6x^5 + 15x^4 - 20x^3 + 15x^2 - 6 x - 1
[x^3 - 2, x^2 - 2x + 1]
x^4 - 8x^3 + 18x^2 - 8x + 2
[x^2 + 1, x^2 - 4x + 1]
x^6 + x^2 + 1
[x^3 + x + 1, x^2]
x^6
[x^2, x^3]
x^8 + 4x^6 + 6x^4 + 4x^2 + 4 = (x^2 + 1)^4 + 3
[x^2 + 3, x^2, x^2 + 1]
x^6 + 6x^4 + x^3 + 9x^2 + 3x - 5
[x^2 + x - 5, x^3 + 3*x], [x^2 + 5*x + 1, x^3 + 3*x - 2]

```

Use Maxima for generating examples: Try it online!

Some decomposition algorithms can be found here and here.

# Answer
# Pari/GP, 84 bytes

```
f(p)=[if(q'',[f(q),r],p)|r<-x*divisors(p\x),r''&&p==subst(q=substpol(p,r,x),x,r)][1]

```

Based on the algorithm described here.

Try it online!
> 4 votes

# Answer
# Wolfram Language (Mathematica), 29 bytes

```
Decompose[#/.x->x+a,x]/.a->0&

```

Try it online!

I have the example set up here to compose a random polynomial from random quadratics (or less), expand it out, and then try to decompose it.

It's necessary to complicate the polynomial with dummy variable (a) since the built-in will not attempt to decompose a monomial.

I notice that the answer often has much larger coefficients than in the original composition, but they are indeed always integers.
> 2 votes

---
Tags: code-golf, math, number, abstract-algebra, polynomials
---