# Question
Title: Spanish ID card control character calculator
This is a very very simple algorithm, that I am sure can be solved in many many different languages. In Spain ID cards (known as *DNI*) consist of 8 numbers and a control character. The control character is calculated with the following algorithm: divide the number by 23, take the remainder of the operation and replace it with a character according to this table:

```
0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22
T  R  W  A  G  M  Y  F  P  D  X  B  N  J  Z  S  Q  V  H  L  C  K  E

```

If the DNI belongs to a foreign person living in Spain, the first digit is changed to `X`, `Y` or `Z` and it is called an *NIE*. In this case, the following substitutions are made before calculating the control character:

```
X Y Z
0 1 2

```

There are a lot of calculators online that help you get the control character, but, how short can you write that code? Write an algorithm (program or function) that receives a `string` with the DNI number (that will always consist of 8 alphanumeric characters) and returns just the single control character calculated and nothing more (a trailing newline is accepted).

Notes:

* The DNI is always written in uppercase, but in your algorithm you can choose the input and output to be upper- or lowercase, just be consistent.
* In real life, some NIEs issued before 2008 have 8 digits after the `X`, `Y` or `Z`, but for the purposes of this game, you can consider they have 7 digits as they have nowadays.
* You can consider that the input string will always have 8 characters, but if they are not in the "8 digits" format nor the "\[XYZ\] plus 7 digits" format, you must return an error (of your choice) or just throw an exception.

### Test cases:

```
00000010 -> X (HRM Juan Carlos I's DNI number)
01234567 -> L
98765432 -> M
69696969 -> T
42424242 -> Y
Z5555555 -> W (Z=2)
Y0000369 -> S (Y=1)
A1234567 -> <Error code or exception>
1231XX12 -> <Error code or exception>

```

This is , so may the shortest code for each language win!

# Answer
# Python 3, 83 bytes

```
lambda n:'TRWAGMYFPDXBNJZSQVHLCKE'[int([n,str(ord(n[0])%4)+n[1:]][n[0]in'XYZ'])%23]

```

Try it online!

-5 thanks to AlixEinsenhardt (from 99 to 94). -1 thanks to JonathanAllan.
> 11 votes

# Answer
# Haskell, 107 93 92 bytes

```
c(x:y)="TRWAGMYFPDXBNJZSQVHLCKE"!!mod(read(("X0Y1Z2"!x):y))23
(a:b:c)!x|x==a=b|2>1=c!x
_!x=x

```

Try it online!
> 8 votes

# Answer
# Pyth, ~~35~~ 34 bytes

The code contains some unprintable characters, so here is a reversible `xxd` hexdump.

```
00000000: 402e 5043 22fc eeff 1ffc adc7 e614 9451  @.PC"..........Q
00000010: 2247 2573 7358 637a 5d31 3e33 4755 3320  "G%ssXcz]1>3GU3
00000020: 3233                                     23

```

Uses **lowercase** characters.

Try it online. Test suite.

### Printable version

```
@.P305777935990456506899534929G%ssXcz]1>3GU3 23

```

### Explanation

* `cz]1` splits the input at position 1, e.g. `"y0000369"` to `["y", "0000369"]`.
* `>3G` gets the last 3 characters of the alphabet, `"xyz"`.
* `U3` gets the range **\[0, 3\[**, `[0, 1, 2]`.
* `X` maps `xyz` to `[0, 1, 2]` in the split array, e.g. `["y", "0000369"]` to `[1, "0000369"]`. This replaces the first character if it is one of `xyz`, while leaving the tail of 7 characters untouched since any 7 character string can't be equal to a single character.
* `s` joins the array with the empty string, e.g. `[1, "0000369"]` to `"10000369"`.
* `s` casts this string to integer, e.g. `"10000369"` to `10000369`. This throws an error if any extra non-digit characters are left in the string.
* `%``23` gets the value modulo 23, e.g. `10000369` to `15`.
* `C"``"` converts the binary string from base 256 to integer (about 3.06 × 1026).
* `.P``G` gets the permutation of the alphabet with that index.
* `@` gets the correct character from the permutation.
> 5 votes

# Answer
# MATL, ~~62~~ 59 bytes

```
'RWAGMYFPDXBNJZSQVHLCKET'j'[\dXYZ]\d{7}'XXg'XYZ'I:47+XEU1))

```

The error for not valid input is `A(I): index out of bounds` (compiler running in Octave) or `Index exceeds matrix dimensions` (compiler running in Matlab).

**Try it online!**

### Explanation

```
'RWAGMYFPDXBNJZSQVHLCKET' % Push this string (output letters circularly shifted by 1)
j                         % Unevaluated input
'[\dXYZ]\d{7}'            % Push this string (regexp pattern)
XX                        % Regexp. Returns cell arary with matching string, or empty
g                         % Convert to standard array. Will be empty if non-valid input
'XYZ'                     % Push this string
I:47+                     % Push [47 48 49] (ASCII codes of '012')
XE                        % Transliterate
U                         % Convert to number
1)                        % Get first entry. Gives an error if empty
)                         % Index (modular, 1-based) into initial string
                          % Implicitly display

```
> 4 votes

# Answer
# ES6, 83 82 81 bytes

```
i=>'TRWAGMYFPDXBNJZSQVHLCKE'[(/^[XYZ]/.test(i)?i.charCodeAt()%4+i.slice(1):i)%23]

```

In action!

Uppercase only, the error code for invalid numbers is `undefined`.

One byte saved thanks to Jonathan Allan.
Another byte saved thanks to Shaggy.
> 4 votes

# Answer
# Java 8, ~~154~~ ~~145~~ 104 bytes

```
s->{s[0]-=s[0]<88|s[0]>90?0:40;return"TRWAGMYFPDXBNJZSQVHLCKE".charAt(new Integer(new String(s))%23);}

```

-9 bytes thanks to *@OliverGrégoire*.
-41 bytes thanks to *@OliverGrégoire* again, by taking the input as a char-array (`char[]`).

If the input is invalid, it will either fail with a `java.lang.NumberFormatException` or `java.lang.StringIndexOutOfBoundsException`.

**Explanation:**

Try it here. (Invalid test cases are surrounded by try-catch so it doesn't stop at the first error.)

```
s->{                      // Method with char[] parameter and char return-type
  s[0]-=s[0]<88|s[0]>90?  // If the first character is not XYZ:
    0                     //  Leave the first character as is
   :                      // Else:
    40;                   //  Subtract 40 to convert it to 012
  return"TRWAGMYFPDXBNJZSQVHLCKE".charAt(
                          //    Get the char from the String
    new Integer(          //    by converting the following String to an integer:
      new String(s)       //     by converting the char-array to a String
    )%23);                //    And take modulo-23 of that integer
}                         // End of method

```
> 3 votes

# Answer
# PHP, 88 bytes

prints 1 for an error

```
$a[0]=strtr(($a=$argn)[0],ZYX,210);echo!ctype_digit($a)?:TRWAGMYFPDXBNJZSQVHLCKE[$a%23];

```

Try it online!
> 2 votes

# Answer
# Jelly, 42 bytes

```
“X0Y1Z2”⁸y@1¦RṪ€V%23ị“Ñ×ⱮEɼiʋ}'uƒẹsø’ṃØA$¤

```

Try it online!

Too long, Jelly! Dennis is disappointed of you!\[citation-needed\]
> 2 votes

# Answer
# q/kdb+, 68 bytes

**Solution:**

```
{"TRWAGMYFPDXBNJZSQVHLCKE"mod["J"$$[3>a:"XYZ"?x 0;($)a;x 0],1_x;23]}

```

**Examples:**

```
q){"TRWAGMYFPDXBNJZSQVHLCKE"mod["J"$$[3>a:"XYZ"?x 0;($)a;x 0],1_x;23]}"00000010"
"X"
q){"TRWAGMYFPDXBNJZSQVHLCKE"mod["J"$$[3>a:"XYZ"?x 0;($)a;x 0],1_x;23]}"01234567"
"L"
q){"TRWAGMYFPDXBNJZSQVHLCKE"mod["J"$$[3>a:"XYZ"?x 0;($)a;x 0],1_x;23]}"98765432"
"M"
q){"TRWAGMYFPDXBNJZSQVHLCKE"mod["J"$$[3>a:"XYZ"?x 0;($)a;x 0],1_x;23]}"69696969"
"T"
q){"TRWAGMYFPDXBNJZSQVHLCKE"mod["J"$$[3>a:"XYZ"?x 0;($)a;x 0],1_x;23]}"42424242"
"Y"
q){"TRWAGMYFPDXBNJZSQVHLCKE"mod["J"$$[3>a:"XYZ"?x 0;($)a;x 0],1_x;23]}"Z5555555"
"W"
q){"TRWAGMYFPDXBNJZSQVHLCKE"mod["J"$$[3>a:"XYZ"?x 0;($)a;x 0],1_x;23]}"Y0000369"
"S"
q){"TRWAGMYFPDXBNJZSQVHLCKE"mod["J"$$[3>a:"XYZ"?x 0;($)a;x 0],1_x;23]}"A1234567"
" "
q){"TRWAGMYFPDXBNJZSQVHLCKE"mod["J"$$[3>a:"XYZ"?x 0;($)a;x 0],1_x;23]}"1231XX12"
" "

```

**Explanation:**

If the first character, `x 0`, is in the string `"XYZ"` then `a` will be `0`, `1` or `2`. If the first character is not in the string, then `a` will be `3`. If `a` is less than 3, we switch out the first character for the string of a (`0`, `1` or `2`), otherwise we switch out for the first character (thus effectively doing nothing). This string is cast to a long (`"J"$`), which is then `mod`'d with 23 to give the remainder. This remainder is used to index into the lookup table.

```
{ "TRWAGMYFPDXBNJZSQVHLCKE" mod["J"$$[3>a:"XYZ"?x 0;string a;x 0],1_x;23] } / ungolfed solution
{                                                                         } / lambda function
                            mod[                                     ;23]   / performds mod 23 of the stuff in the gap
                                                                  1_x       / 1 drop input, drops the first character
                                                                 ,          / concatenation
                                    $[             ;        ;   ]           / if COND then TRUE else FALSE - $[COND;TRUE;FALSE]
                                        a:"XYZ"?x 0                         / "XYZ" find x[0], save result in a
                                      3>                                    / is this result smaller than 3
                                                    string a                / if so, then string a, e.g. 0 -> "0"
                                                             x 0            / if not, just return first character x[0]
                                "J"$                                        / cast to long
  "TRWAGMYFPDXBNJZSQVHLCKE"                                                 / the lookup table

```

**Notes:**

`" "` is returned in the error scenarios, this is because the cast returns a null, and indexing into a string at index null is an empty char. I could add 4 bytes at the beginning (`"!"^`) to make it more obvious that an error had occurred:

```
q){"!"^"TRWAGMYFPDXBNJZSQVHLCKE"("J"$$[3>a:"XYZ"?x 0;($)a;x 0],1_x)mod 23}"1231XX12"
"!"

```
> 1 votes

# Answer
# JavaScript(ES6), 121 byte

```
f=i=>{c=+i[0];a=3;while(a--){i[0]=="XYZ"[a]&&(c=a)}b=7;while(b--){c= +i[7-b]+c*10}return "TRWAGMYFPDXBNJZSQVHLCKE"[c%23]}

console.log([f("00000010"),f("01234567"),f("98765432"),f("69696969"),f("42424242"),f("Z5555555"),f("Y0000369"),f("A1234567"),f("1231XX12")])
```
> 1 votes

# Answer
# Japt, 50 bytes

Similar to most of the other approaches.

Input and output is lowercase, outputs `undefined` for invalid input.

```
`tr°gmyfpdxbnjzsqvhlcke`g("xyz"øUg)?Uc %4+UÅ:U %23

```

Test it
Test all valid test cases
> 1 votes

# Answer
# Rust, 206 bytes

I don't think rust is well suited for code golfing -\_-

```
let b=|s:&str|{s.chars().enumerate().map(|(i,c)|match i{0=>match c{'X'=>'0','Y'=>'1','Z'=>'2',_=>c},_=>c}).collect::<String>().parse::<usize>().ok().and_then(|x|"TRWAGMYFPDXBNJZSQVHLCKE".chars().nth(x%23))};

```
> 1 votes

# Answer
# 05AB1E, ~~41~~ ~~40~~ 39 bytes

```
ć…xyz2ÝJ‡ìDd_i.ǝ}23%.•Xk¦fΣT(:ˆ.Îðv5•sè

```

Takes the input in lowercase (to save 1 byte *yay*)

Try it online!

Prints the input to STDERR if it is malformed

### Explanation

```
ć…xyz2ÝJ‡ìDd_i.ǝ}23%.•Xk¦fΣT(:ˆ.Îðv5•sè
ć                                       # Get head of input and put the rest of the input under it on the stack
 …xyz                                   # Push xyz
     2ÝJ                                # Push 012
        ‡                               # Transliterate
         ì                              # Prepend to the rest of the input
          Dd_                           # Does the result contain something other than numbers?
             i.ǝ}                       # If so print input to STDERR
                 23%                    # Modulo 23
                    .•Xk¦fΣT(:ˆ.Îðv5•   # Pushes the character list
                                     sè # Get the char at the index of the modulo

```
> 1 votes

# Answer
## Dyalog APL, 95 bytes

`{'TRWAGMYFPDXBNJZSQVHLCKE'[1+23|(10⊥¯1+'0123456789'⍳{(⍕{('XYZ'⍳⍵)<4:('XYZ'⍳⍵)-1⋄⍵} ⊃⍵),1↓⍵}⍵)]}`

This is a monadic operator that accepts a character string as its operand and returns its result.

**FIXME** it doesn't check its input. It's not properly golfed.

Usage:

```
    OP ← {'TRWAGMYFPDXBNJZSQVHLCKE'[1+23|(10⊥¯1+'0123456789'⍳{(⍕{('XYZ'⍳⍵)<4:('XYZ'⍳⍵)-1⋄⍵} ⊃⍵),1↓⍵}⍵)]}

      OP '01234567'
L

      OP '00000010'
X

```
> 0 votes

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


title: Draw the rainbow

text:
# Question
Title: Draw the rainbow
The challenge is simple: Draw a rainbow in as few bytes as possible

The specs for the rainbow are as follows:

* The figure must be exactly 400 pixels wide and 200 pixels high (optionally 401x201 if you want a single center pixel)
* The red ring should touch all borders of the figure (outer radius = 200 pixels)
* All rings shall have the same width (10 pixels)
    + The violet ring shall have an inner radius of 130 pixels
* The bow should be the upper half of a perfect circle
* The background shall be white (transparent is also accepted)
* The figure shall not have borders, (exception is made if the border can't be suppressed)
* Builtin rainbow making functions are not allowed!

The following colors are to be used in the rainbow:

This is code golf, so the shortest code in bytes win!

Example:

##

Related, but different!

# Answer
# MATL, ~~107~~ ~~95~~ ~~92~~ ~~87~~ ~~84~~ 83 bytes

```
-200:200 0:200!PYyq10/k12-t8<*t0>*Q7B.561FTh.295Oh.51h4BPFTF6Bl.5hOh4B8$v255*k5M/YG

```

This works in current release (14.0.0) of the language/compiler.

*EDIT (July 6, 2017)*: You can try it at MATL Online!.

To check that the colors are correct, remove the last five characters (you need to wait for a few seconds and scroll down to the end of the output).

### Explanation

The code has three main steps:

**Step 1**: Generate a 201x401 matrix with numbers from `1` to `8`. Pixels with value `1` are background (white), pixels with values `2`, ..., `8` represent each band of the rainbow.

Horizontal coordinates range from `-200` to `200` left to right, and vertical coordinates range from `0` to `200` bottom to top. So the origin (0,0) is bottom center, the upper left corner is (-200,200), etc.

The different bands of the rainbow are generated by computing the distance from each pixel to the origin and quantizing in steps of 10 pixels.

**Step 2**: Generate an 8x3 matrix defining the colormap. Each row is one of the necessary colors (white and the seven colors of the rainbow). Each value of the previous 201x401 matrix will be interpreted as an index to a row of this colormap.

We generate the colormap matrix using values between 0 and 1 for each color component, and then multiplying by 255 and rounding down. This way most values are initially 0 and 1, which will later become 0 and 255. Intermediate values are coded as values between 0 and 1 with 2 or 3 decimals, chosen so that when multiplied and rounded give the exact desired value.

**Step 3**: Display the image with that colormap.

```
               % STEP 1: CREATE MATRIX DEFINING THE RAINBOW BANDS
-200:200       % row vector [-200, -199, ..., 200]
0:200          % row vector [0, 1, ..., 200]
!P             % transpose and flip: convert into column vector [200; 199; ...; 0]
Yy             % hypotenuse function with broadcast: distance from each point to (0,0)
q10/k          % subtract 1, divide by 10, floor (round down). Gives 20 circular bands
               % 10 pixels wide, with values from 0 to 19
12-            % subtract 12
t8<*           % values larger than 7 are set to 0
t0>*           % values less than 0 are set to 0. We now have 7 bands with values
               % 1, ..., 7, and the white background with value 0
Q              % add 1: white becomes 1, bands become 2, ..., 8

               % STEP 2: CREATE MATRIX DEFINING THE COLORMAP
7B             % first row: [1 1 1] (7 converted to binary: color white)
.561FTh        % second row (light purple)
.295Oh.51h     % third row (dark purple)
4BP            % fourth row: [0 0 1] (4 converted to binary and flipped: blue)
FTF            % fifth row (green)
6B             % sixth row: [1 1 0] (6 converted to binary: yellow)
l.5hOh         % seventh row: orange
4B             % eigth row: [1 0 0] (4 converted to binary: red)
8$v            % vertically concatenate the 8 eight rows
255*k          % multiply by 255 and round down. Gives exact color values
5M/            % push 255 again and divide. This is needed because colors in MATL are
               % defined between 0 and 1, not between 0 and 255

               % STEP 3: DISPLAY
YG             % display image with that colormap

```
> 15 votes

# Answer
# Piet, 838 codels, several thousand pixels

Someone had to do it:

If you save this image you can try it online!

The actual Piet program is only the top ~125 pixels, which I created using a Python program I wrote.

Editing this afterwards really hurt my vision, I'll be tripping for days!

This outputs the image in an SVG format, because SVG really is (in my opinion) the simplest way to do this. I shamelessly stole Doorknob's SVG code. Outputs:

well, this really:

```
<svg viewBox='0 0 400 200'><circle cx='200' cy='200' r='200' fill='red'/><circle cx='200' cy='200' r='190' fill='#ff7f00'/><circle cx='200' cy='200' r='180' fill='yellow'/><circle cx='200' cy='200' r='170' fill='lime'/><circle cx='200' cy='200' r='160' fill='blue'/><circle cx='200' cy='200' r='150' fill='indigo'/><circle cx='200' cy='200' r='140' fill='#8f00ff'/><circle cx='200' cy='200' r='130' fill='white'/></svg>

```

Good luck beating this answer, non-Esolang users!
> 28 votes

# Answer
# Minecraft 1.10 (almost), 2677 characters one-command, 868 blytes

Well I sure picked a verbose language.

```
summon FallingSand ~ ~1 ~ {Block:log,Time:1,Passengers:[{id:FallingSand,Block:redstone_block,Time:1,Passengers:[{id:FallingSand,Block:activator_rail,Time:1,Passengers:[{id:MinecartCommandBlock,Command:"summon ArmorStand ~ ~ ~ {Tags:[\"b\"]}"},{id:MinecartCommandBlock,Command:"summon Pig ~ ~ ~ {NoAI:1b}"},{id:MinecartCommandBlock,Command:setblock ~-1 ~-2 ~6 chain_command_block 3 replace {auto:1,Command:"execute @e[tag=b] ~ ~ ~ execute @e[rm=200] ~ ~ ~ tp @e[c=1] ~ -99 ~"}},{id:MinecartCommandBlock,Command:setblock ~-1 ~-2 ~5 chain_command_block 3 replace {auto:1,Command:"execute @e[tag=b] ~ ~ ~ execute @e[rm=190,r=200] ~ ~ ~ setblock ~ ~ ~ wool 14"}},{id:MinecartCommandBlock,Command:setblock ~-1 ~-2 ~4 chain_command_block 3 replace {auto:1,Command:"execute @e[tag=b] ~ ~ ~ execute @e[rm=180,r=190] ~ ~ ~ setblock ~ ~ ~ wool 1"}},{id:MinecartCommandBlock,Command:setblock ~ ~-2 ~4 chain_command_block 4 replace {auto:1,Command:"execute @e[tag=b] ~ ~ ~ execute @e[rm=170,r=180] ~ ~ ~ setblock ~ ~ ~ wool 4"}},{id:MinecartCommandBlock,Command:setblock ~ ~-2 ~5 chain_command_block 2 replace {auto:1,Command:"execute @e[tag=b] ~ ~ ~ execute @e[rm=160,r=170] ~ ~ ~ setblock ~ ~ ~ wool 13"}},{id:MinecartCommandBlock,Command:setblock ~ ~-2 ~6 chain_command_block 2 replace {auto:1,Command:"execute @e[tag=b] ~ ~ ~ execute @e[rm=150,r=160] ~ ~ ~ setblock ~ ~ ~ wool 11"}},{id:MinecartCommandBlock,Command:setblock ~ ~-2 ~7 chain_command_block 2 replace {auto:1,Command:"execute @e[tag=b] ~ ~ ~ execute @e[rm=140,r=150] ~ ~ ~ setblock ~ ~ ~ wool 10"}},{id:MinecartCommandBlock,Command:setblock ~ ~-2 ~8 chain_command_block 2 replace {auto:1,Command:"execute @e[tag=b] ~ ~ ~ execute @e[rm=130,r=140] ~ ~ ~ setblock ~ ~ ~ wool 2"}},{id:MinecartCommandBlock,Command:setblock ~1 ~-2 ~8 chain_command_block 4 replace {auto:1,Command:"tp @e[type=Cow] ~1 ~ ~"}},{id:MinecartCommandBlock,Command:setblock ~1 ~-2 ~7 chain_command_block 3 replace {auto:1,Command:"tp @e[type=Bat] ~-1 ~ ~"}},{id:MinecartCommandBlock,Command:setblock ~1 ~-2 ~6 chain_command_block 3 replace {auto:1,Command:"execute @e[type=Pig] ~ ~ ~ summon Bat ~ ~ ~ {NoAI:1b}"}},{id:MinecartCommandBlock,Command:setblock ~1 ~-2 ~5 chain_command_block 3 replace {auto:1,Command:"execute @e[type=Pig] ~ ~ ~ summon Cow ~ ~ ~ {NoAI:1b}"}},{id:MinecartCommandBlock,Command:setblock ~1 ~-2 ~4 repeating_command_block 3 replace {auto:1,Command:"tp @e[type=Pig] ~ ~1 ~"}},{id:MinecartCommandBlock,Command:setblock ~ ~ ~1 command_block 0 replace {Command:fill ~ ~-3 ~-1 ~ ~ ~ air}},{id:MinecartCommandBlock,Command:setblock ~ ~-1 ~1 redstone_block},{id:MinecartCommandBlock,Command:kill @e[type=MinecartCommandBlock,r=1]}]}]}]}

```

Make a new Superflat world, paste that mess into an Impulse command block, set your render distance fairly high, and run it. Break the armor stand when your computer stops lagging.

The result is 400 blocks across and 200 blocks tall, as requested.

I used MrGarretto's one command generator to pack everything together, and then modified the result of that a little bit to save a couple more bytes. Here's the input to it:

```
INIT:summon ArmorStand ~ ~ ~ {Tags:["b"]}
INIT:summon Pig ~ ~ ~ {NoAI:1b}
tp @e[type=Pig] ~ ~1 ~
execute @e[type=Pig] ~ ~ ~ summon Cow ~ ~ ~ {NoAI:1b}
execute @e[type=Pig] ~ ~ ~ summon Bat ~ ~ ~ {NoAI:1b}
tp @e[type=Bat] ~-1 ~ ~
tp @e[type=Cow] ~1 ~ ~
execute @e[tag=b] ~ ~ ~ execute @e[rm=130,r=140] ~ ~ ~ setblock ~ ~ ~ wool 2
execute @e[tag=b] ~ ~ ~ execute @e[rm=140,r=150] ~ ~ ~ setblock ~ ~ ~ wool 10
execute @e[tag=b] ~ ~ ~ execute @e[rm=150,r=160] ~ ~ ~ setblock ~ ~ ~ wool 11
execute @e[tag=b] ~ ~ ~ execute @e[rm=160,r=170] ~ ~ ~ setblock ~ ~ ~ wool 13
execute @e[tag=b] ~ ~ ~ execute @e[rm=170,r=180] ~ ~ ~ setblock ~ ~ ~ wool 4
execute @e[tag=b] ~ ~ ~ execute @e[rm=180,r=190] ~ ~ ~ setblock ~ ~ ~ wool 1
execute @e[tag=b] ~ ~ ~ execute @e[rm=190,r=200] ~ ~ ~ setblock ~ ~ ~ wool 14
execute @e[tag=b] ~ ~ ~ execute @e[rm=200] ~ ~ ~ tp @e[c=1] ~ -99 ~

```

That's a total of 15 1.9+ command blocks, and 838 bytes, so 15\*2 + 838 = 868 blytes.

Here's the (almost) part, it's missing a corner and edge. It logically shouldn't - Minecraft bug? Would be exactly 400x200 blocks if it wasn't for that. Not much I can do.
> 15 votes

# Answer
## Pyth, ~~150~~ ~~149~~ 128 bytes

```
"<svg viewBox=0,0,400,200>"V8s["<circle cx=200 cy=200 r="-200*TN" fill="@c"red #ff7f00 #ff0 #0f0 #00f indigo #8f00ff #fff"dN" />

```

Outputs in SVG:

```
<svg viewBox=0,0,400,200>
<circle cx=200 cy=200 r=200 fill=red />
<circle cx=200 cy=200 r=190 fill=#ff7f00 />
<circle cx=200 cy=200 r=180 fill=#ff0 />
<circle cx=200 cy=200 r=170 fill=#0f0 />
<circle cx=200 cy=200 r=160 fill=#00f />
<circle cx=200 cy=200 r=150 fill=indigo />
<circle cx=200 cy=200 r=140 fill=#8f00ff />
<circle cx=200 cy=200 r=130 fill=#fff />

```

Thanks to @MamaFunRoll for 16 bytes and @PatrickRoberts for 6 more!
> 14 votes

# Answer
# Mathematica ~~152~~ ~~144~~ 126 bytes

```
Graphics@MapIndexed[{#,Disk[{0,0},4-#/5&@@#2,{Pi,0}]}&,RGBColor/@TextWords@"#f00 #ff7f00 #ff0 #0f0 #00f #4b0082 #8f00ff #fff"]

```

Thanks @CatsAreFluffy for shaving off 8 bytes & @njpipeorgan for a further 18 :)
> 12 votes

# Answer
## vim, ~~165~~ ~~142~~ 139

```
i<svg viewBox=0,0,400,200><cr><circle cx=2<C-n> cy=2<C-n> r=2<C-n> fill=red<cr>#ff7f00<cr>#ff0<cr>#0f0<cr>#00f<cr>indigo<cr>#8f00ff<cr>#fff<esc>2Gqq0y4f=jPBB10<C-x>@qq@qV2G:norm A /><cr>

```

Yeesh, this is clunky. There's got to be improvements that can be made.

Outputs as SVG, like my Pyth answer.

Thanks to @MyHamDJ for shaving off 3 bytes!
> 8 votes

# Answer
# HTML+SVG+ES6, 169

```
<svg width=400 viewBox=0,0,40,20 onload="this.innerHTML=`f00
ff7f00
ff0
0f0
00f
4b0082
8f00ff
fff`.replace(/.+/g,c=>`<circle cx=20 cy=20 r=${--r} fill=#${c} />`,r=21)"/>
```
> 8 votes

# Answer
# JavaScript (ES6), ~~171~~ 158 bytes

```
document.write`<svg width=400 height=200>${`f00
ff7f00
ff0
0f0
00f
4b0082
8f00ff
fff`.replace(/.+/g,c=>`<circle cx=200 cy=200 r=${i--}0 fill=#${c} />`,i=20)}`

```

Credit to @edc65 for the idea to convert

```
`[...].map((c,i)=>...)`

```

to

```
`...`.replace(/.+/g,c=>...,i=20)

```

It may look longer but the amount of bytes saved in compressing the array to a string is well worth the conversion. (It saves 13 bytes in this case)

## Demo

```
document.write`<svg width=400 height=200>${`f00
ff7f00
ff0
0f0
00f
4b0082
8f00ff
fff`.replace(/.+/g,c=>`<circle cx=200 cy=200 r=${i--}0 fill=#${c} />`,i=20)}`
```
> 7 votes

# Answer
# Ruby with Shoes, 155 bytes

```
Shoes.app(width:400,height:200){background'fff'
8.times{|i|stroke fill %w{f00 ff7f00 ff0 0f0 00f 4b0082 8f00ff fff}[i]
oval left:i*=10,top:i,radius:200-i}}

```

Sample output:
> 7 votes

# Answer
# HTML (162) + CSS (146)

```
body{height:200px;width:400px}div{height:100%;box-sizing:border-box;border-radius:50% 50% 0 0/100% 100% 0 0;border:solid;border-width:10px 10px 0}
```

```
<div style=color:red><div style=color:#FF7F00><div style=color:#FF0><div style=color:#0F0><div style=color:#00F><div style=color:#4B0082><div style=color:#8F00FF>
```

---

# HTML (224) + CSS (128)

```
body{height:200px;width:400px}div{height:100%;box-sizing:border-box;border-radius:50% 50% 0 0/100% 100% 0 0;padding:10px 10px 0}
```

```
<div style=background:red><div style=background:#FF7F00><div style=background:#FF0><div style=background:#0F0><div style=background:#00F><div style=background:#4B0082><div style=background:#8F00FF><div style=background:#FFF>
```
> 6 votes

# Answer
# LaTeX, 290 bytes

```
\documentclass{proc}\input tikz\begin{document}\def\z#1!#2!#3!#4!{\definecolor{t}{rgb}{#1,#2,#3}\fill[color=t](200pt,0)circle(#4pt);}\tikz{\clip(0,0)rectangle(400pt,200pt);\z1!0!0!200!\z1!.5!0!190!\z1!1!0!180!\z0!1!0!170!\z0!0!1!160!\z.29!0!.51!150!\z.56!0!1!140!\z1!1!1!130!}\end{document}

```

Try it here.

### Explanations

```
\documentclass{proc}
\input tikz
\begin{document}

    %Define macro "\z" with 4 arguments.
    % The first 3 arguments are rgb values for the color
    % Last argument is the radius in pt that we draw a full circle with

    \def\z#1!#2!#3!#4!
        {\definecolor{t}{rgb}{#1,#2,#3}
         \fill[color=t](200pt,0)circle(#4pt);}

    % Start a Tikz figure

    \tikz{

        % We only draw the top half of the circle

        \clip(0,0)rectangle(400pt,200pt);

        % Draw each circle from biggest to smallest

        \z1!0!0!200!
        \z1!.5!0!190!
        \z1!1!0!180!
        \z0!1!0!170!
        \z0!0!1!160!
        \z.29!0!.51!150!
        \z.56!0!1!140!

        % Draw a white circle last

        \z1!1!1!130!
    }
\end{document}

```
> 6 votes

# Answer
# SpecBAS - ~~318~~ 254 bytes

If we're drawing rainbows, then it seems like a good place to use the successor to ZX Spectrum BASIC.

```
1 p,k=20,x1=0,x2=400,y=200
2 FOR EACH s IN [16711680,16744192,16776960,65280,255,4915330,9371903]: PALETTE p,s: INC p: NEXT s
3 CLS 15: DRAW 0,200 TO 70,200: DRAW 330,200 TO 400,200
4 FOR i=1 TO 7
5 INK k: DRAW x1,y TO x2,y,-PI: DRAW x1+10,y TO x2-10,y,-PI: FILL x1+5,190
6 x1+=10,x2-=10,k+=1
7 NEXT i

```

Line 2 sets up the palette for the specific RGB values needed (and is probably not helping the byte count) as standard Spectrum colours didn't match up.

The `DRAW` command can take an extra parameter which makes it turn through a number of ~~degrees~~ radians between x1,y1 and x2,y2. Finally it finds a gap in the semicircles just drawn and flood fills with the current colour.
> 5 votes

# Answer
# Tcl/Tk, 263 bytes

```
canvas .c -bg #FFF -bo 0 -highlightt 0;pack .c -e 1 -f both;wm ge . 400x200;foreach {r c} {200 #FF0000 190 #FF7F00 180 #FFFF00 170 #00FF00 160 #0000FF 150 #4B0082 140 #8F00FF 130 #FFF} {.c cr o -$r -$r $r $r -outline $c -f $c};after 100 {.c x s -5 u;.c y s -10 u}

```

Alas, this kind of question always favors some esoteric languages... That said, Tcl/Tk really makes graphics operations all of: easy, short, and *readable*.

That said, I've sacrificed readability to crunch options down to as few characters as possible. I don't imagine crunching the list of colors will help much compared to code to unpack it...

For comparison, here's the uncrunched code (380 bytes):

```
canvas .c -bg #FFF -borderwidth 0 -highlightthickness 0
pack .c -expand yes -fill both
wm geometry . 400x200
foreach {r c} {
  200 #FF0000
  190 #FF7F00
  180 #FFFF00
  170 #00FF00
  160 #0000FF
  150 #4B0082
  140 #8F00FF
  130 #FFFFFF
} {
  .c create arc -$r -$r $r $r -extent 180 -outline $c -fill $c
}
after 100 {
  .c xview scroll -5 units
  .c yview scroll -10 units
}

```

The `after` command was unfortunately necessary since no scrolling (of the canvas's coordinate origin) can be done before the window is mapped to the screen.

Also, the crunched code actually draws a *full* rainbow (using a circle instead of an arc) and just relies on window clipping...

Anyway, I hope y'all enjoy. :O)
> 5 votes

# Answer
# JavaScript ~~271~~ 251

```
c=document.body.appendChild(document.createElement('canvas'))
x=c.getContext('2d')
c.width=400
r=c.height=200
for(i=0;i<8;x.beginPath(),x.arc(r,r,r-i*10,0,7),x.fillStyle="#"+"FF0000FF7F00FFFF0000FF000000FF4B00828F00FFFFFFFF".substr(i++*6,6),x.fill());
```
> 4 votes

# Answer
## Bubblegum, ~~139~~ 119 bytes

Hexdump:

```
00000000: b329 2e4b 5728 cb4c 2d77 caaf b035 d031  .).KW(.L-w...5.1
00000010: d031 3130 d031 3230 b0e3 b249 ce2c 4ace  .110.120...I.,J.
00000020: 4955 48ae b005 f215 922b c154 1198 4ccb  IUH......+.T..L.
00000030: ccc9 b12d 4a4d 51d0 c7ad ced0 12aa 4e39  ...-JMQ.......N9
00000040: 2dcd 3c0d 2884 4fad 0542 2d7e 85e6 3085  -.<.(.O..B-~..0.
00000050: 0604 149a c115 1aa4 e155 680a 5598 9997  .........Uh.U...
00000060: 9299 9e8f 57a9 09cc 4c0b a07f d2f0 1b6b  ....W...L......k
00000070: 8cf0 1148 2100 0a                        ...H!..

```

Sadly, this is shorter than my Pyth answer. :(

Generates the same SVG file.
> 4 votes

# Answer
## Java, 354 bytes

```
public void r() throws IOException{BufferedImage i=new BufferedImage(400,200,2);Graphics2D g=i.createGraphics();g.setStroke(new BasicStroke(10));int[]c={0xFF0000,0xFF7F00,0xFFFF00,0xFF00,255,0x4B0082,0x8F00FF};for(int v=0;v<7;v ++){g.setColor(new Color(c[v]));g.drawArc(v*10+5,v*10+5,390-v*20,390-v*20,0,360);}ImageIO.write(i,"PNG",new File("a.png"));}}

```

Just uses the `Graphics2D` class to draw 7 arcs, with an array to store the colors. I'm sure it can be improved further.

Ungolfed code:

```
public void ungolfed() throws IOException {
        BufferedImage i = new BufferedImage(400, 200, 2); // 2 is TYPE_INT_ARGB
        Graphics2D g = i.createGraphics();
        g.setStroke(new BasicStroke(10));
        int[] c = {0xFF0000, 0xFF7F00, 0xFFFF00, 0x00FF00, 0x0000FF, 0x4B0082, 0x8F00FF};
        for(int v = 0; v < 7; v ++) {
            g.setColor(new Color(c[v]));
            g.drawArc(v * 10 + 5, v * 10 + 5, 390 - v * 20, 390 - v * 20, 0, 360);
        }
        ImageIO.write(i, "PNG", new File("a.png"));
    }

```
> 4 votes

# Answer
## CSS, ~~244~~ ~~242~~ 240 bytes

```
body{width:400px;height:200px;background-image:radial-gradient(500px at bottom,#FFF 26%,#8F00FF 26%,#8F00FF 28%,#4B0082 28%,#4B0082 30%,#00F 30%,#00F 32%,#0F0 32%,#0F0 34%,#FF0 34%,#FF0 36%,#FF7F00 36%,#FF7F00 38%,red 38%,red 40%,#FFF 40%)}

```

Edit: Saved 2 bytes by working around a bug in Chrome. Saved a further 2 bytes thanks to @TrangOul.

Note: the snippet uses a `<div>` due to limitations of Stack Snippets.

```
div {
    width: 400px;
    height: 200px;
    background-image: radial-gradient(500px at bottom,
        #FFF 26%,
        #8F00FF 26%, #8F00FF 28%,
        #4B0082 28%, #4B0082 30%,
        #00F 30%, #00F 32%,
        #0F0 32%, #0F0 34%,
        #FF0 34%, #FF0 36%,
        #FF7F00 36%, #FF7F00 38%,
        red 38%, red 40%,
        #FFF 40%);
}
```

```
<div>
```
> 4 votes

# Answer
# C, 220 217 213 bytes

```
#define X printf("%c",s<169|s/401?y:s
i=8e4,t,y=255;main(s){for(puts("P6 400 200 255");i--;X/288?y:s<195?143:s<225?75:0),X<256|s/360?0:s/323?127:y),X<225&s/195?130:s<256?y:0))s=i/400,t=i%400-200,s=(s*s+t*t)/100;}

```

Output is PPM (the binary kind).

**Edit:** Saved a couple bytes thanks to @tucuxi.

**Edit 2:** Rearranged code to save even more.
> 4 votes

# Answer
# Google Blockly, 48 blocks, 75 bytes

Click the gif below to navigate to the solution, where you can get a closer look at how it works.
As for an explanation, I think an image is worth a thousand words, and thus a gif is worth a thousand images.

link to big readable gif

Note: I'm unsure how to count in Blockly, so I counted every block as 1 byte, and every variable the regular way, so that `0` == 1 byte, `530` == 3 bytes, `Arial` == 5 bytes and `bold` == 4 bytes.
I counted the special character I used to cut off the rainbow as 2 bytes. Please report any mistakes or suggestions of the byte count in the comments
> 4 votes

# Answer
# Postscript (87 bytes)

Hex dump:

```
00000000: 3188 0131 2030 2e35 3631 8800 3120 302e  1..1 0.561..1 0.
00000010: 3237 3888 0030 2e35 3188 0030 8801 3088  278..0.51..0..0.
00000020: 0130 8801 3188 0031 2030 2e35 8800 3188  .0..1..1 0.5..1.
00000030: 0030 87c8 0038 7b34 2031 9287 929d 87c8  .0...8{4 1......
00000040: 0030 2032 9258 3087 b400 9205 9216 9242  .0 2.X0........B
00000050: 880a 92a9 7d92 83                        ....}..

```

Output:
> 4 votes

# Answer
# Processing, ~~196~~ ~~186~~ ~~181~~ ~~179~~ ~~169~~ 163 bytes

```
int d=400,i=0;size(d,d/2);background(-1);int[]c={-65536,-33024,-256,#00ff00,#0000ff,#4b0082,#8f00ff,-1};for(noStroke();i<8;ellipse(200,200,d,d),d-=20)fill(c[i++]);

```

*Saved 10 bytes thanks to Kritixi Lithos*
*... and another 6 bytes thanks to dzaima*
> 3 votes

# Answer
# HTML + CSS, ~~310~~ 307 bytes

```
<b style=background:red><b style=background:#ff7f00><b style=background:#ff0><b style=background:lime><b style=background:blue><b style=background:indigo><b style=background:#8f00ff><b style=background:#fff;width:260px;height:130px><style>b{float:left;padding:10px 10px 0 10px;border-radius:300px 300px 0 0}
```

Super-duper invalid markup (may or may not look correct in your browser). Just wanted to see if it was even possible.
> 3 votes

# Answer
## PHP, 285 bytes

```
<?php $a=imagecreate(400,200);define("b",255);$c=array(b,b,b,b,0,0,b,127,0,b,b,0,0,b,0,0,0,b,75,0,130,143,0,b,b,b,b);for($i=0;$i<9;$i++){imagefilledellipse($a,200,200,420-$i*20,420-$i*20,imagecolorallocate($a,$c[$i*3],$c[$i*3+1],$c[$i*3+2]));}header("Content-type:png");imagepng($a);?>

```

Outputs:
> 3 votes

# Answer
# Bash + ImageMagick, ~~159~~ 125 characters

```
eval convert -size 401x201 xc: '-fill \#'{f00,ff7f00,ff0,0f0,00f,4b0082,8f00ff,fff}' -draw "circle 200,200 200,$[i++*10]"' x:

```

Sample output:
> 3 votes

# Answer
# Excel VBA, <sub>~~213~~ ~~202~~ ~~196~~ ~~192~~</sub> 172 Bytes

### Code

Anonymous VBE immediate window function that takes no input and outputs a rainbow, as a vector image, to the sheets(1) object

```
For i=0To 7:j=400-20*i:Set s=Sheet1.Shapes.AddShape(20,10*i,10*i,j,j):s.Fill.ForeColor.RGB=Array(255,32767,65535,65280,-31*4^8,8519755,&HE1008F,-1)(i):s.Line.Visible=0:Next

```

### Subroutine Version

```
Sub a
For i=0To 7
j=400-20*i
set s=Sheet1.Shapes.AddShape(20,10*i,10*i,j,j)
s.Fill.ForeColor.RGB=Array(255,32767,65535,65280,-31*4^8,8519755,&HE1008F,-1)(i)
s.Line.Visible=0
Next
End Sub

```

-11 bytes for removing `.Adjustments(3)=3/80` call and adding a 8th, white arc

-6 bytes for using `-1` over `&HFFFFFF`

-3 bytes for using `Sheet1` over `Sheets(1)`

-6 bytes for converting `with` statement to `set` statement

-14 bytes for converting from `Sub` to anonymous VBE function

### Output
> 3 votes

# Answer
# R, 184 170 bytes

Making an image with fixed pixel dimensions turns out to be surprisingly tricky with R, whose plotting functions are mostly intended for statisticians. In particular R leaves extra space for labels and coordinate axes unless you explicitly set margins as zero-width by calling `par`.

On the other hand some of the required colours (specifically red, yellow and blue) are found in the default palette, and can be referenced simply by integer indices.

```
png(,400,200)
par(mar=0*1:4)
plot(as.raster(outer(199:0,-199.5:200,function(y,x)c(rep("white",13),"#8F00FF","#4B0082",4,"green",7,"#FF7F00",2)[1+(x^2+y^2)^.5%%200/10])))

```
> 2 votes

# Answer
# Forth Salon Haiku (184 bytes)

I can't satisfy the dimension constraints with this format, but I thought it worth sharing anyway.

```
: ^ 2 ** ;
: b 0.9 * dup x .5 - ^ y 2.01 / ^
+ sqrt dup rot > swap rot .045
+ < * * + ;
0 .56 .2 b .29 .25 b 1 .4 b
1 .45 b 1 .5 b 0 1 .35 b 1 .4 b
0.5 .45 b 0 1 .2 b .51 .25 b
1 .3 b

```
> 2 votes

# Answer
## Perl, 175 + 1 = 176 bytes

```
perl -MSVG -E '$z=SVG->new(width=>4e2,height=>2e2);@x=qw/#fff #8f00ff indigo #00f #0f0 #ff0 #ff7f00 red/;$z->circle(cx=>200,cy=>200,r=>200-10*$a++,style=>{fill=>pop@x})for 1..8;say$z->xmlify'

```
> 1 votes

# Answer
# DIV Games Studio (184 bytes)

Not the shortest but quite simple. Uses the DIV default palette

```
PROGRAM r;
local
c[]=22,26,235,41,54,82,249,15,15;
BEGIN
set_mode(400200);
for(x=-80;x<80;x+=10)
y=399-x;
draw(5,c[abs(x)/10],15,0,x,x,y,y);
x+=70*(x<0);END
LOOP;FRAME;END
END

```

## Explanation

Define program start (named "r" to save space)

```
PROGRAM r;

```

setup palette lookup

```
local
c[]=22,26,235,41,54,82,249,15,15;

```

BEGIN program code

```
BEGIN

```

Set video mode to 400,200

```
set_mode(400200);

```

loop x (predefined variable) from -80 (which bg hack) to 80 ( 7 colours + white centre)

```
for(x=-80;x<80;x+=10)

```

define elipse constraints

```
y=399-x;

```

draw elipse - on the first iteration this draws a circle larger than the screen in full white (index -8)

draw(type (5=filled elipse), colour, opacity, x0,y0,x1,y1)

```
draw(5,c[abs(x)/10],15,0,x,x,y,y);

```

once first is done, bump x up to zero to start drawing red band

```
x+=70*(x<0);

```

end for loop

```
END

```

infinite loop, drawing screen.

```
LOOP;FRAME;END

```

end (matches BEGIN at top of program)

```
END

```
> 1 votes

# Answer
# PHP, 190 bytes

```
imagefill($a=imagecreatetruecolor($r=400,200),0,0,$w=0xffffff);foreach([255<<16,0xff7f00,$w-255,65280,255,4915330,9371903,$w]as$i)imagefilledellipse($a,200,200,$r,20+$r-=20,$i);imagepng($a);

```

Run it like this:

```
php -r 'imagefill($a=imagecreatetruecolor($r=400,200),0,0,$w=0xffffff);foreach([255<<16,0xff7f00,$w-255,65280,255,4915330,9371903,$w]as$i)imagefilledellipse($a,200,200,$r,20+$r-=20,$i);imagepng($a);' | display

```

Also working in theory at 179 bytes (but the image looks a tad messed up, bad GD):

```
php -r '$r=410;imagesetthickness($a=imagecreatetruecolor(400,200),10);foreach([255<<16,0xff7f00,0xffff00,65280,255,4915330,9371903]as$i)imagearc($a,200,200,$r-=20,$r,1,0,$i);imagepng($a);' | display

```

Also not a perfect image, but much better than the above (and @166 bytes):

```
php -d error_reporting=30709 -r '$a=imagecreatetruecolor($r=400,200);foreach([255<<16,0xff7f00,0xffff00,65280,255,4915330,9371903]as$i)for(;++$$i<21;)imageellipse($a,200,200,$r,$r--,$i);imagepng($a);' | display

```
> 1 votes

# Answer
# LibreLogo, 129 bytes

**Code:**

```
x=307 ps 7 fc [3]for i in [[5],0xff7f00,[11],65280,255,4915330,9371903][ x-=14 pc i circle x ]ps 0 pc [3]rt 180 fd 152 square 300

```

**Result:**

**Explanation:**

```
x = 307                                                          ; Circle Width = 307 pt
ps 7                                                             ; Pen Size = 7 pt
fc [3]                                                           ; Fill Color = #ffffff
for i in [[5], 0xff7f00, [11], 65280, 255, 4915330, 9371903] [   ; For each Rainbow Color
    x -= 14                                                      ; Circle Width -= 14 pt
    pc i                                                         ; Pen Color = Rainbow Color
    circle x                                                     ; Draw Circle (Circle Width)
]
ps 0                                                             ; Pen Size = 0
pc [3]                                                           ; Pen Color = #ffffff
rt 180                                                           ; Right 180°
fd 152                                                           ; Forward 152 pt
square 300                                                       ; Draw Square (300 pt)

```
> 1 votes

---
Tags: code-golf, graphical-output
---


title: BASKETBALL FRVR?

text:
# Question
Title: BASKETBALL FRVR?
You might already be familiar with the game: Basketball FRVR in facebook. There are two types of score you can make:

* **A virgin-shot:**(we call it so in our country :D) When the ball enters the basket without touching the rim or
* **A stale shot:** When the ball enters the basket, but after touching the rim.

The game is over once you miss a shot. Stale shot always scores 2 points.The first in a run of consecutive virgin-shots scores 3 points, the second scores 6 points, and subsequent ones score 9 points each.

For example,

```
Hits             Total score

S-V-V-V          2+3+6+9 = 20
S-V-V-V-V        2+3+6+9+9 = 29 (see how added score for consecutive virgin-
                                 shots
                                 saturates at the 5th hit)
S-V-S-V-V-S-V    2+3+2+3+6+2+3= 21

```

Using simple mathematics, it can easily be proven that any score greater than 1 `n>1` can be scored in the game

# The Challenge

For any given number `1<n<100`, output all the possible ways to score `n`.

# Rules:

* You can either write a complete program or function(s), snippets however are not acceptable.
* Hard-coding the output or loading from memory/other programs/website is strictly prohibited, you must compute the output in real-time.
* The output must be a well-separated collection of string of `S`s and `V`s. For eg: `['SVS','SSV','VSS']` or `{'SVS','SSV','VSS'}`.
* It is encouraged to, but the collection need not be sorted or contain only unique elements. Brownie points if you output sorted and unique collection of strings.

# Winning condition:

* This is so the shortest code in bytes wins.

# Input/Output (Test-cases)

```
2: {'S'}
3: {'V'}
4: {'SS'}
12: {'SSSSSS', 'VSSVS', 'VSVSS', 'VSSSV', 'SSVSV', 'SVSVS', 'SVSSV'}
16: {'SSSVSVS', 'SSSVSSV', 'VSSSSSV', 'SSVSSVS', 'SVVSV', 'VSSSSVS', 'SVSVV', 'SVSSSSV', 'VVSSV', 'VSVVS', 'SVSVSSS', 'SVSSSVS', 'VSSVSSS', 'SSVSSSV', 'SSSSSSSS', 'VVSVS', 'VSSSVSS', 'SVSSVSS', 'VSVSSSS', 'SSSSVSV', 'SSVSVSS', 'VSSVV'}

```

Thanks to Peter Taylor for improving this question

# Answer
# Jelly, 30 bytes

```
o2,5ṁo8‘
Hṗ@€⁾VSẎðOḂŒgÇ€FS=ðÐf

```

A monadic link returning a list of the strings (lists of characters).

**Try it online!** \- The footer calls the link and separates the entries by newlines since a full program's implicit output would smash them together.

### How?

```
o2,5ṁo8‘ - Link 1, helper to form shot scores: list of shots grouped by type (S=1 and V=0)
         -                                e.g. [[1,1],[0,0,0,0,0],[1,1],[0],[1,1]]
 2,5     - 2 paired with 5 = [2,5]
o        - logical or (vectorises)             [[1,1],[2,5,0,0,0],[1,1],[2,5],[1,1]]
    ṁ    - mould like the input                [[1,1],[2,5,0,0,0],[1,1],[2],[1,1]]
     o8  - logical or with 8                   [[1,1],[2,5,8,8,8],[1,1],[2],[1,1]]
       ‘ - increment                           [[2,2],[3,6,9,9,9],[2,2],[3],[2,2]]

Hṗ@€⁾VSẎðOḂŒgÇ€FS=ðÐf - Link: number, total score, n
H                     - halve n
    ⁾VS               - literal ['V','S']
 ṗ@€                  - Cartesian power with swapped @rguments for €ach
                      -   ...i.e. for each in [1,2,...,floor(half n)]
                      -   yielding all strings of Vs and Ss from length 1 to floor(half n)
       Ẏ              - tighten (from a list of lists of lists to a list of lists)
        ð         ðÐf - filter keep those entries for which this yields a truthy value:
         O            -   cast to ordinals (S->83, V->86)
          Ḃ           -   modulo 2         (S->1, V->0)
           Œg         -   group equal runs (e.g. [0,0,1,1,0] -> [[0,0],[1,1],[0]])
             Ç€       -   call the last link (1) as a monad for €ach (transform to scores)
               F      -   flatten (make one list of scores)
                S     -   sum (calculate the total score of the string)
                 =    -   equals right argument (n)?

```

The resulting order is actually lexicographical in reverse, to have it forward sorted just reverse it by appending .
> 4 votes

# Answer
## JavaScript (ES6), ~~73~~ 72 bytes

Prints all unique, lexically sorted combinations.

```
f=(n,p=0,s='')=>n?n>1&&f(n-2,0,s+'S')&f(n-(p-9?p+=3:9),p,s+'V'):alert(s)

```

### Test cases

In this snippet, `alert()` has been replaced by `console.log()` for user-friendliness.

```
f=(n,p=0,s='')=>n?n>1&&f(n-2,0,s+'S')&f(n-(p-9?p+=3:9),p,s+'V'):console.log(s)

;[2, 3, 4, 12, 16]
.forEach(n => { console.log('[' + n + ']'); f(n); })
```
> 4 votes

# Answer
# Python 3, ~~96~~ ~~95~~ ~~85~~ ~~77~~ 73 bytes

*-1 byte thanks to @notjagan*
*-4 bytes thanks to @xnor*

```
f=lambda x,s='',i=3:f(x-2,s+'S')+f(x-i,s+'V',3*(i<9)+i)if x>0 else[s]*-~x

```

Try it online!
> 3 votes

# Answer
# PHP\>=7.1, 158 bytes

```
function b($s="",$g=0){global$r,$i;$g-$i?$g>$i?:b($s."2",$g+2)&b($s.($n=$s[-1]>2?min(9,$s[-1]+3):3),$g+$n):$r[]=strtr($s,2369,SVVV);}$i=$argn;b();print_r($r);

```

PHP Sandbox Online

Expanded

```
function b($s="",$g=0){
  global$r,$i;
  $g-$i
    ?$g>$i
      ?
      :b($s."2",$g+2) # recursive call add a S
      &b($s.($n=$s[-1]>2?min(9,$s[-1]+3):3),$g+$n) # recursive call add a V
    :$r[]=strtr($s,2369,SVVV); # add to result array if reach score replace integers with S and V
}
$i=$argn; #short input variable
b(); #call the function
print_r($r); #print results

```
> 3 votes

# Answer
# Mathematica, 95 ~~102~~ ~~105~~ ~~112~~ bytes

```
If[#4==#2,Echo@#,If[#4>#2,#0[#<>"S",#2+2,0,#4];#0[#<>"V",#2+Min[3#3+3,9],#3+1,#4]]]&["",0,0,#]&

```

There should be a lot of golfing potential.

Bascially it is a recursive function that perform a DFS over all possible combinations.
> 1 votes

# Answer
# Haskell, 75 bytes

```
n#v|n<1=[[]|n==0]|n>0=(('S':)<$>(n-2)#3)++(('V':)<$>(n-v)#min(v+3)9)
f=(#3)

```

Call `f` with the total score value. Uses a fairly straightforward depth-first search to find all the solutions. Sadly, Haskell's precedence rules seem to be out to get me today, so there are lots of parentheses here.
> 1 votes

---
Tags: code-golf, combinatorics
---


title: Show me some fireworks!

text:
# Question
Title: Show me some fireworks!
**Given, in any way and order,**

* dimensions (in whichever order you want)
* a probability (in whatever format you want)
* number of iterations (you may choose whether to count the initial state or not)

**do *one* of the following:**

* animate, or
* output each step of, or
* return a list of states of

**a spaces-filled sky of those dimensions.**

**For each iteration:**

* every sky character has the given probability of becoming a `*`
* the eight characters that surround any `*` become
`\` `|` `/`
`-` `-`
`/` `|` `\`, if they don't become stars, however,
* if a character is within range of two `*`s, make it an `X`

### Example

The 7×22 sky (frame for clarity only – don't output the frame)

```
┌──────────────────────┐
│                      │
│                      │
│                      │
│                      │
│                      │
│                      │
│                      │
└──────────────────────┘

```

could with 1% probability become

```
┌──────────────────────┐
│  *                   │
│                      │
│                      │
│                      │
│                      │
│           *          │
│                      │
└──────────────────────┘

```

and the next step

```
┌──────────────────────┐
│ - - *                │
│ /|\                  │
│          *           │
│                      │
│          \|/         │
│          - -         │
│          /|\         │
└──────────────────────┘

```

and then

```
┌──────────────────────┐
│    - -               │
│    /|\  \|/          │
│         - -          │
│         /|\          │
│                      │
│      * *             │
│                      │
└──────────────────────┘

```

and

```
┌──────────────────────┐
│                      │
│                      │
│                      │
│                      │
│     \|X|/            │
│     - X -            │
│     /|X|\          * │
└──────────────────────┘

```

and so on

```
┌──────────────────────┐
│                      │
│                      │
│                      │
│                   *  │
│                      │
│                   \|/│
│                   - -│
└──────────────────────┘

```

# Answer
# ES6, 520 496 bytes

Clipping and everything else should work now.

```
(w,h,p,i,r=0,s=($=>{while(++r<i)for(j=0,_=$[r]=[],z=$[r-1]||[];j<w*h;){k=j+1,l='*',c=0
n=(j%w&&z[j-1]==l&&++c)|(k%w&&z[k]==l&&++c)?'-':' '
n=(z[j-w]==l&&++c)|(z[j+w]==l&&++c)?'|':n
n=(j%w&&z[j-w-1]==l&&++c)|(k%w&&z[k+w]==l&&++c)?'\\':n
n=(k%w&&z[k-w]==l&&++c)|(j%w&&z[j+w-1]==l&&++c)?'/':n
_[j++]=Math.random()<p?l:c>1?'X':n}})(x=[])||x)=>{c=document.body.children[0],r=0;while(++r<i)setTimeout((k=0)=>{for(r++,c.innerHTML='';k<h;)c.innerHTML+=s[r].slice(k*w,++k*w).join('')+'\n'},90*r);r=0}

```

View animation!

Saved 24 bytes thanks to Zacharý's tip.

## Old solution, 478 bytes (with clipping bug)

I think I got all the rules correct, however the solution has a clipping problem where everything exiting right/left wraps around one line lower/higher on the opposite side.

```
(w,h,p,i,r=0,s=($=>{while(++r<i)for(j=0,_=$[r]=[],z=$[r-1]||[];j<w*h;){c=0
n=(z[j-1]=='*'&&++c)|(z[j+1]=='*'&&++c)?'-':' '
n=(z[j-w]=='*'&&++c)|(z[j+w]=='*'&&++c)?'|':n
n=(z[j-w-1]=='*'&&++c)|(z[j+w+1]=='*'&&++c)?'\\':n
n=(z[j-w+1]=='*'&&++c)|(z[j+w-1]=='*'&&++c)?'/':n
_[j++]=Math.random()<p?'*':c>1?'X':n}})(x=[])||x)=>{c=document.body.children[0],r=0;while(++r<i)setTimeout((k=0)=>{for(r++,c.innerHTML='';k<h;)c.innerHTML+=s[r].slice(k*w,++k*w).join('')+'\n'},90*r);r=0}

```

View old.
> 5 votes

# Answer
# APL (Dyalog), 65 chars or 71 bytes\*

Prompts for dimensions (rows, columns), then for iterations (not counting initial state), then for probability (as *n* in ¹⁄).

```
⎕{1=?⍺⍺:'*'⋄2≤+/b←'*'=1↓4⌽,⍵:'X'⋄⊃b/'-/|\\|/-'}⌺3 3{⍺⍺⎕←⍵}⍣⎕⊢⎕⍴''

```

Try it online!

`⎕⍴''` prompt for input and use that to **r**eshape an empty string, padding with spaces as needed

yield that

`⍣⎕` prompt for input and apply the following function on the above () that many times:

…`{``}` derive a function using the below function as operand (*⍺⍺*), as follows:

`⎕←⍵` print the argument

`⍺⍺` apply the following function:

…`⌺3 3` apply the following function on each element's 3×3 Moore neighborhood:

`⎕{``}` get input and use it as operand (*⍺⍺*) to derive a new function

`?⍺⍺` random integer among the first *⍺⍺* integers

`1=` Boolean if equal to one

`:` if true:

`'*'` return a star

else:

`,⍵` ravel (flatten) the argument (the Moore neighborhood)

`4⌽` rotate it cyclically four steps to the left

`1↓` drop one element (the original center)

`'*'=` Boolean list where equal to a star

`b←` store that as *b*

`+/` sum that

`2≤` Boolean if two or higher

`:` if true:

`'X'` return an X

else:

`b/'-/|\\|/-'` use the *b* to to filter the string

pick the first one, if there are none, pick the prototype (a space)

---

<sup>* To run in Dyalog Classic, simply replace  with `⎕U233A` </sup>.
> 3 votes

---
Tags: code-golf, string, ascii-art, matrix, animation
---


# Question
Title: Counting from 1 to n without any consecutive numbers
## Goal

You are given an integer `n` (`n > 1`). You must output how many permutations of the integers `1` to `n` there are which start at `1`, end at `n`, and don't have two consecutive integers which differ by 1.

Alternatively, if you take the complete graph `K_n` and remove the edges of the path `1-2-3-...-n` you must count the Hamiltonian paths from `1` to `n` in the remaining graph.

The examples will use `f(n)` for a function that takes in `n` and outputs the number of valid permutations, but your submission can be a function or a program.

---

## Examples

For `n = 6`, a possible solution is `1-3-5-2-4-6`

However, `1-3-5-2-6-4` is not a valid solution since it does not end with `6`.

In fact, for `n = 6`, there are only 2 solutions (`1-4-2-5-3-6` is the other one).

Hence `f(6) = 2`.

---

For `n = 4` the only permutations which start in `1` and end in `4` are `1-2-3-4` and `1-3-2-4`. In both of them the `2` is adjacent to the `3`, giving consecutive integers which differ by 1. Therefore `f(4) = 0`.

---

## Test cases

```
f(6) = 2
f(4) = 0
f(8) = 68
f(13) = 4462848

```

---

## Winning criterion

This is code-golf, the shortest answer wins.

# Answer
# MATL, 16 bytes

```
qtq:Y@0&Yc!d|qAs

```

Try it online!

For inputs exceeding `12` it runs out of memory.

### Explanation

```
q      % Implicitly input n. Push n-1
tq     % Duplicate and subtract 1: pushes n-2
:      % Range [1 2 ... n-2]
Y@     % Matrix with all permutations, each in a row
0      % Push 0
&Yc    % Append n-1 and predend 0 to each row
!      % Tranpose
d      % Consecutive differences along each column
|      % Absolute value
q      % Subtract 1
A      % All: true if all values in each column are non-zero
s      % Sum. Implicitly display

```
> 6 votes

# Answer
# Mathematica, 58 bytes, polynomial(*n*) time

```
Abs[Sum[(k-1)Hypergeometric2F1[k,k-#,2,2](#-k)!,{k,#}]-1]&

```

### How it works

Rather than iterating over permutations with brute force, we use the inclusion–exclusion principle to count them combinatorially.

Let S be the set of all permutations of \[1, …, n\] with σ1 = 1, σ*n* = *n*, and let S*i* be the set of permutations σ ∈ S such that |σ*i* − σ*i* \+ 1| = 1. Then the count we are looking for is

|S| − |S1 ∪ ⋯ ∪ S*n* − 1| = ∑2 ≤ *k**n* \+ 1; 1 ≤ *i*2 \< ⋯ \< *i**k* − 1 \< *n* (−1)k − 2|S*i*2 ∩ ⋯ ∩ S*i**k* − 1|.

Now, |S*i*2 ∩ ⋯ ∩ S*i**k* − 1| only depends on *k* and on the number *j* of runs of consecutive indices in \[*i*1, *i*2, …, *i**k* − 1, *i**k*\] where for convenience we fix *i*1 = 0 and *i**k* = *n*. Specifically,

|S*i*2 ∩ ⋯ ∩ S*i**k* − 1| = 2*j* − 2(*n**k*)!, for 2 ≤ *j**k**n*,
|S*i*2 ∩ ⋯ ∩ S*i**k* − 1| = 1, for *j* = 1, *k* = *n* \+ 1.

The number of such index sets \[*i*1, *i*2, …, *i**k* − 1, *i**k*\] with *j* runs is

(*k* − 1C*j* − 1)(*n**k*C*j* − 2), for 2 ≤ *j**k**n*,
1, for *j* = 1, *k* = *n* \+ 1.

The result is then

(−1)*n* − 1 \+ ∑2 ≤ *k**n*2 ≤ *j**k* (−1)*k* − 2(*k* − 1C*j* − 1)(*n**k*C*j* − 2)2*j* − 2(*n**k*)!

The inner sum over *j* can be written using the hypergeometric 2F1 function:

(−1)*n* − 1 \+ ∑2 ≤ *k**n* (−1)*k*(*k* − 1)2F1(2 − *k*, *k**n*; 2; 2)(*n**k*)!

to which we apply a Pfaff transformation that lets us golf away the powers of −1 using an absolute value:

(−1)*n* − 1 \+ ∑2 ≤ *k**n* (−1)*n*(*k* − 1)2F1(*k*, *k**n*; 2; 2)(*n**k*)!
= |−1 + ∑1 ≤ *k**n* (*k* − 1)2F1(*k*, *k**n*; 2; 2)(*n**k*)!|.

### Demo

```
In[1]:= Table[Abs[Sum[(k-1)Hypergeometric2F1[k,k-#,2,2](#-k)!,{k,#}]-1]&[n],{n,50}]

Out[1]= {1, 0, 0, 0, 0, 2, 10, 68, 500, 4174, 38774, 397584, 4462848,

>    54455754, 717909202, 10171232060, 154142811052, 2488421201446,

>    42636471916622, 772807552752712, 14774586965277816, 297138592463202402,

>    6271277634164008170, 138596853553771517492, 3200958202120445923684,

>    77114612783976599209598, 1934583996316791634828454,

>    50460687385591722097602304, 1366482059862153751146376304,

>    38366771565392871446940748410, 1115482364570332601576605376898,

>    33544252621178275692411892779180, 1042188051349139920383738392594332,

>    33419576037745472521641814354312790,

>    1105004411146009553865786545464526206,

>    37639281863619947475378460886135133496,

>    1319658179153254337635342434408766065896,

>    47585390139805782930448514259179162696722,

>    1763380871412273296449902785237054760438426,

>    67106516021125545469475040472412706780911268,

>    2620784212531087457316728120883870079549134420,

>    104969402113244439880057492782663678669089779118,

>    4309132147486627708154774750891684285077633835734,

>    181199144276064794296827392186304334716629346180848,

>    7800407552443042507640613928796820288452902805286368,

>    343589595090843265591418718266306051705639884996218154,

>    15477521503994968035062094274002250590013877419466108978,

>    712669883315580566495978374316773450341097231239406211100,

>    33527174671849317156037438120623503416356879769273672584588,

>    1610762789255012501855846297689494046193178343355755998487686}

```
> 19 votes

# Answer
# Jelly, ~~17~~ 16 bytes

```
ṖḊŒ!ð1;;⁹IỊṀðÐḟL

```

A monadic link.

**Try it online!**

### How?

```
ṖḊŒ!ð1;;⁹IỊṀðÐḟL - Link: number n
Ṗ                - pop (implicit range build) -> [1,n-1]
 Ḋ               - dequeue -> [2,n-1]
  Œ!             - all permutations of [2,n-1]
    ð       ðÐḟ  - filter discard those entries for which this is truthy:
     1;          -   1 concatenated with the entry
       ;⁹        -   ...concatenated with right (n)
         I       -   incremental differences
          Ị      -   is insignificant (absolute value <=1)
           Ṁ     -   maximum
               L - length (the number of valid arrangements)

```
> 6 votes

# Answer
# 05AB1E, 17 bytes

```
L¦¨œʒ¹1Š)˜¥Ä1å_}g

```

Try it online!
> 5 votes

# Answer
# Japt, ~~19~~ 18 bytes

```
o2 á è_pU äÉ m²e>1

```

Test it online! I would not recommend testing on anything larger than `10`.

### Explanation

```
o2 á è_  pU äÉ  m²  e>1
o2 á èZ{ZpU ä-1 mp2 e>1}
                          : Implicit: U = input integer
o2                        : Create the range [2..U-1].
   á                      : Generate all permutations of this range.
     èZ{               }  : Check how many permutations Z return a truthy value:
        ZpU               :   Push U to the end of Z.
            ä-1           :   Push 1 to the beginning of Z, then take the difference
                          :   of each pair of items.
                m         :   Map each item X to
                 p2       :     X ** 2. This gives a number greater than 1 unless the
                          :     item is 1 or -1.
                    e>1   :   Return whether every item in this list is greater than 1.
                          :   This returns `true` iff the permutation contains no
                          :   consecutive pairs of numbers.
                          : Implicit: output result of last expression

```
> 5 votes

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

Saved 11 bytes thanks to @xnor.

Using the result for `Q_rec` on page 7 of @ChristiaanWesterbeek's find, we get

```
f 1=1
f n|n<6=0
f n=sum$zipWith((*).f)[n-5..][n-4,1,10-2*n,4,n-2]

```

I don't understand how their next result `ha` relates to this, but after speeding up (first by memoization, see earlier versions, then as below) I get their numbers.

While the above is okay for `n=20`, it is essentialy an example how not to do recursion. Here is a faster version (only for `n>=6`) that also would only need constant memory - if only the numbers didn't keep increasing...

```
f n=last$foldl(#)[1,0,0,0,0][6..n]
l#n=tail l++[sum$zipWith(*)l[n-4,1,10-2*n,4,n-2]]

```

That gives

```
Prelude> f 50
1610762789255012501855846297689494046193178343355755998487686
Prelude> f 500
659178618863924802757920269977240274180092211041657762693634630044383805576666007245903670780603497370173231423527767109899936008034229541700392144282505597945561328426013937966521561345817045884498867592832897938083071843810602104434376305964577943025310184523643816782047883794585616331928324460394146825636085453532404319881264974005968087265587062691285454120911586459406436421191277596121471930913837355151842093002557978076653884610826296845041929616496533544124347765641367732716560025553179112645454078955409181466212732427071306363820080109636358537270466838558068527692374178581063316309789026101221004745226182671038004326069705775312654329754698423385241664984156235692539255677944294995403233446243315371404887473868003155621849544566385172835597260848972758443874423271017007843907015007416644383573987606586308556317833384896267539628278571497402655322562624217658332870157802254043614726316296058329670971054977099155788604175817828380564156329839201579006169173002756295957371639199917376529472990059986681882194726437566769717959443857298155265292535858523609764515938314672724480762724541633037484152303637096

```

It's no problem to also get `f 5000` but I don't want to paste the result...

---

BTW, it's possible to not use fancy math and still not use (ultra) brute force. First, instead of looking at all permutations, look at partial permutations and only extend them when they are not already invalid. It's no use to look at all permutations starting with `1 6 5`. Second, some partial permutations like `1 3 5 7` and `1 5 3 7` have exactly the same valid continuations, so handle them together. Using these ideas, I could compute the values up to `n=16` in 0.3s.
> 5 votes

# Answer
# Python, 125 bytes

```
from itertools import*
lambda n:sum(p[-1]-p[0]==n-1and all(~-abs(x-y)for x,y in zip(p,p[1:]))for p in permutations(range(n)))

```
> 4 votes

# Answer
# Mathematica, 66 bytes

```
Count[Permutations@Range@#,x:{1,__,#}/;FreeQ[Differences@x,1|-1]]&

```

## Explanation

`Function` with first argument `#`.

```
Count[                                                             (* Count the number of *)
      Permutations@                                                (* permutations of *)
                   Range@#,                                        (* the list {1, ..., #} *)
                           x:{1,__,#}                              (* of the form {1, __, #} *)
                                     /;                            (* such that *)
                                             Differences@x,        (* the list of differences of consecutive elements *)
                                       FreeQ[                      (* is free of elements of the form *)
                                                           1|-1    (* 1 or -1 *)
                                                               ]]&

```
> 3 votes

# Answer
# Javascript (ES6), ~~100~~ ~~74~~ ~~72~~ 60 bytes

```
f=n=>n--<6?!n|0:f(n)*--n+4*f(n--)-2*f(n--)*--n+f(n)*++n+f(n)

```

Below is the version before the golf-mastery of @PeterTaylor

```
f=n=>n<6?n==1|0:(n-4)*f(n-5)+f(n-4)-2*(n-5)*f(n-3)+4*f(n-2)+(n-2)*f(n-1)

```

Thanks to the answer from @ChristianSievers that managed to draft a Haskell solution from a paper that I found after googling '0, 2, 10, 68, 500, 4174, 38774, 397584', here's a Javascript version that does not permutate too.

Usage

```
for (i=1; i<=20; i++) {
  console.log(i, f(i))
}

1 1
2 0
3 0
4 0
5 0
6 2
7 10
8 68
9 500
10 4174
11 38774
12 397584
13 4462848
14 54455754
15 717909202
16 10171232060
17 154142811052
18 2488421201446
19 42636471916622
20 772807552752712

```
> 3 votes

# Answer
# Python 3, ~~109~~ ~~107~~ 102 bytes

```
q=lambda s,x,n:sum(q(s-{v},v,n)for v in s if(v-x)**2>1)if s else x<n;f=lambda n:q({*range(2,n)},1,n-1)

```

Try it online!

Removed four bytes by not trying to one-line the function (as suggested by @shooqie) and another byte by replacing `abs` with a square. (Requires Python 3.5+)
> 1 votes

# Answer
# Brachylog, 26 bytes

```
{⟦₁pLh1&~tLs₂ᶠ{-ȧ>1}ᵐ}ᶜ|∧0

```

Try it online!

### Explanation

```
{                    }ᶜ       Output = count the number of outputs of:
 ⟦₁pL                           L is a permutation of [1, …, Input]
    Lh1                         The head of L is 1
       &~tL                     The tail of L is the Input
          Ls₂ᶠ                  Find all sublists of length 2 of L
              {    }ᵐ           Map on each sublist:
               -ȧ>1               The elements are separated by strictly more than 1
                       |      Else (no outputs to the count)
                        ∧0    Output = 0

```
> 1 votes

# Answer
# Python 2, 136 bytes

-10 bytes thanks to @ovs.

```
lambda n,r=range:sum(x[0]<1and~-n==x[-1]and 2+~any(abs(x[i]-x[i+1])<2for i in r(n-1))for x in permutations(r(n)))
from itertools import*

```

Try it online!
> 0 votes

# Answer
# Mathematica, 134 bytes

```
(s=Permutations@Range[2,#-1];g=Table[Join[Prepend[s[[i]],1],{#}],{i,Length@s}];Length@Select[Union@*Abs@*Differences/@g,FreeQ[#,1]&])&

```

test cases n: 2 to 12

> {0, 0, 0, 0, 2, 10, 68, 500, 4174, 38774, 397584}
> 0 votes

# Answer
# Python 2, 105 bytes

```
lambda n:reduce(lambda a,i:a+[i*a[-5]+a[-4]+2*(1-i)*a[-3]+4*a[-2]+(i+2)*a[-1]],range(2,n),[0,1]+4*[0])[n]

```

Try it online!

This is based on Philippe Flajolet's paper discovered by @Christiaan Westerbeek; it's much faster and two bytes shorter than my Python 3 solution which enumerates the possible permutations. (In Python 3, `reduce` has annoyingly been moved to `functools`.)

There is a much shorter version using numpy's dot product, but that overflows quite rapidly and requires numpy to have been imported. But for what it's worth:

```
lambda n:reduce(lambda a,i:a+[dot([i,1,2-2*i,4,i+2],a[-5:])],range(2,n),[0,1]+4*[0])[n]

```
> 0 votes

---
Tags: code-golf, permutations
---


title: "Hello, World", Even before it runs

text:
# Question
Title: "Hello, World", Even before it runs
> ***Warning: This challenge is only valid for languages with a compiler.***

Make a program (which is perfectly valid code) that outputs `Hello, World`, even before runtime.

How? Let me explain.

Many languages have a compiler. Some operations are made in the compile-time, and others, in runtime. You trick the compiler to output the text `Hello, World` in compile-time. The text can be anywhere, like the build log.(Not errors. sorry for invalidating all those answers. at least theres pragma tho)

> You can use C, C++ or C#, but I wouldn't encourage you to. It's simply a game breaker.

p.s. I wrote this challenge because the tag is both unused, and used wrong.

# Answer
> 5 votes
# C#, 51 bytes

Try it online

```
#warning Hello, World
class P{static void Main(){}}

```

Prints the following to the Error List (but still compiles):

```
warning CS1030: #warning: `Hello, World'

```

# Answer
> 3 votes
# FreePascal, 29 characters

```
begin{$INFO Hello, World}end.

```

Maybe other Pascal variants too, not sure whether the `$INFO` directive is FreePascal only or not.

Sample run:

```
bash-4.4$ fpc compile-time-message.pas
Free Pascal Compiler version 3.0.2+dfsg-2 [2017/04/09] for x86_64
Copyright (c) 1993-2017 by Florian Klaempfl and others
Target OS: Linux for x86-64
Compiling compile-time-message.pas
User defined: Hello, World
Linking compile-time-message
/usr/bin/ld.bfd: warning: link.res contains output sections; did you forget -T?
0 lines compiled, 0.0 sec

```

# Answer
> 3 votes
# C (gcc), ~~22~~ 18 bytes

```
Hello, World;main;

```

This compiles just fine with gcc (and clang), although the program it produces crashes immediately.

Try it online!

### Compiler output

gcc 6.3.1 produces the following debugging information.

```
.code.tio.c:1:1: warning: data definition has no type or storage class
 Hello, World;main;
 ^~~~~
.code.tio.c:1:1: warning: type defaults to ‘int’ in declaration of ‘Hello’ [-Wimplicit-int]
.code.tio.c:1:8: warning: type defaults to ‘int’ in declaration of ‘World’ [-Wimplicit-int]
 Hello, World;main;
        ^~~~~
.code.tio.c:1:14: warning: data definition has no type or storage class
 Hello, World;main;
              ^~~~
.code.tio.c:1:14: warning: type defaults to ‘int’ in declaration of ‘main’ [-Wimplicit-int]

```

---

# C (gcc), 15 bytes

```
Hello, World;

```

If compiling to an object file is allowed, this works just as well. The resulting file simply declares two global variables.

The byte count includes **+3 bytes** for the compiler flag `-c`.

Try it online!

### Compiler output

```
hw.c:1:1: warning: data definition has no type or storage class
 Hello, World;
 ^~~~~
hw.c:1:1: warning: type defaults to ‘int’ in declaration of ‘Hello’ [-Wimplicit-int]
hw.c:1:8: warning: type defaults to ‘int’ in declaration of ‘World’ [-Wimplicit-int]
 Hello, World;
        ^~~~~

```

---

# C (gcc), 20 bytes

```
main(Hello, World){}

```

This compiles to a program that exits cleanly.

Try it online!

### Compiler output

```
.code.tio.c:1:1: warning: return type defaults to ‘int’ [-Wimplicit-int]
 main(Hello, World){}
 ^~~~
.code.tio.c: In function ‘main’:
.code.tio.c:1:1: warning: type of ‘Hello’ defaults to ‘int’ [-Wimplicit-int]
.code.tio.c:1:1: warning: type of ‘World’ defaults to ‘int’ [-Wimplicit-int]

```

# Answer
> 1 votes
## Haskell, ~~25~~ 24 bytes

```
m@main=m

```

8 bytes from the code plus 16 bytes for the compiler flag `-W'Hello, World'`.

Gives the warning `unrecognised warning flag: -WHello, World` and compiles the program.

Depending on the shell (or the absence of a shell) you can omit the single quotes in the flag for two bytes less. TIO works this way.

### Haskell, TIO environment, 22 bytes

Try it online!

Edit: @Dennis saved a byte. Thanks!

# Answer
> 1 votes
## Perl, 15 bytes

14 bytes of code + `-w` flag.

```
"Hello, World"

```

When ran with `-w` flag, it produces the compile-time warnings:

```
$ perl -we '"Hello, World"'
Useless use of a constant ("Hello, World") in void context at -e line 1.

```

And if you wonder if it really happens at compile time, you can add `-c` flag, which causes the program to be compiled but not ran, and the warning is still here.

# Answer
> 0 votes
## GNU C, 31 bytes

Nothing clever here. I'm mostly posting it for reference.

```
main(){printf("Hello, World");}

```

GCC will throw the following warning at compilation time:

```
hello.c: In function ‘main’:
hello.c:1:8: warning: incompatible implicit declaration of built-in function ‘printf’ [enabled by default]
 main(){printf("Hello, World");}
        ^

```

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

```
main(){"Hello, World";}

```

Try it online!

Gives the warning:

```
warning: return type defaults to ‘int’ [-Wimplicit-int]
main(){"Hello, World";}
^~~~

```

---

# C (gcc), 38 bytes

```
#pragma message"Hello, World"
main(){}

```

Try it online!

Rather than using compiler warnings, this answer uses a built-in `pragma` directive that allows printing notes to stdout. Works in C and C++ (as I *think* all the rest of these do).

---

# C (gcc), 23 + 1 = 24 bytes

```
#define f"Hello, World"

```

Try it online!

Prints "Hello, World!" as part of an error message, which says:

```
warning: ISO C99 requires whitespace after the macro name
 #define f"Hello, World!"
          ^~~~~~~~~~~~~~~

```

This is a default warning in GCC; no flags need to be added to achieve this.

The extra byte comes from the `-c` flag, which successfully compiles the program without linking, which means it accepts not having a `main` function. However, the resulting output file cannot be executed. If this is unacceptable, then:

# C (gcc), 31 bytes

```
#define f"Hello, World"
main=0;

```

Try it online!

This will run, but will segfault every time. If *that*'s not acceptable, then:

# C (gcc), 32 bytes

```
#define f"Hello, World"
main(){}

```

Try it online!

# Answer
> 0 votes
# Scala, 36 bytes

```
object F extends App{"Hello, World"}

```

Try it online!

Gives the warning:

```
warning: a pure expression does nothing in statement position; you may be omitting necessary parentheses
object F{"Hello, World"}

```

---
Tags: code-golf, kolmogorov-complexity, compile-time
---


title: Sheet music ASCII-art generator

text:
# Question
Title: Sheet music ASCII-art generator
> **Note**: Anders Kaseorg warns me that this could be a duplicate of another previous question. It seems so, and I'm sorry I did not find that question before posting this one. Nonetheless, that question only received one answer and this one is simpler, just in case you all want to try this time. I'll understand if this question ends up being marked as duplicate, though.

### The challenge

Given an input like this:

```
8g 8Df 4cs 2C 1A

```

Write the shortest program/function that produces an output like this:

```
    /\                                         -o-
   | |
---|-|---------------------------------------------------|-|
   |/                                                    | |
---/|--------|\----b-*-----------------------------------|-|
  / |        | |    |                  o                 | |
-|--|--------|------|-----------------|------------------|-|
 | (| \      |      | |               |                  | |
-|--|--)----*-------|/---------|------|------------------|-|
  \ | /                        |      |                  | |
-----|-------------------------|-------------------------|-|
     |                         |
   *_/                      #-*-

```

### Rules

The output must consist of a five-line staff beginning with the drawing of a G-clef exactly as shown above, aligned to the left of the staff and leaving a single column after the starting of the staff.

```
    /\
   | |
---|-|--
   |/
---/|---
  / |
-|--|---
 | (| \
-|--|--)
  \ | /
-----|--
     |
   *_/
^
Single column

```

The notes must begin with a `*` or a `o` character depending on its type.

There must be exactly eight columns of separation every `*` or a `o` character:

```
    /\                                         -o-
   | |
---|-|---------------------------------------------------|-|
   |/                                                    | |
---/|--------|\----b-*-----------------------------------|-|
  / |        | |    |                  o                 | |
-|--|--------|------|-----------------|------------------|-|
 | (| \      |      | |               |                  | |
-|--|--)----*-------|/---------|------|------------------|-|
  \ | /                        |      |                  | |
-----|-------------------------|-------------------------|-|
     |                         |
   *_/                      #-*-
   ↑        ↑        ↑        ↑        ↑        ↑        ↑
   8 columns of separation

```

The staff must end with the terminator aligned to the right as shown in the example. The left bar of the terminator must be separated 8 columns from the last note.

The input will be a single string containing the notes (at least one, no empty inputs), each one separated by a whitespace (you can consider every note will be a proper one, so no need to check for errors). You can also take the input as an array of strings, with a note per element in the array. For each note, the first character will be the denominator of the note length (`1` for a whole note/semibreve, starts with `o`; `2` for a half note/minim, starts with `o`; `4` for a quarter note/crotchet, starts with `*`; and `8` for an eighth note/quaver, starts with `*`). The second character will be the note (see next table), and the third, optional character will be `f` or `F` for flat notes and `s` or `S` for sharp notes.

```
    ---    A (ledger line)
           G
--------   F
           E
--------   D
           C
--------   b
           a
--------   g
           f
--------   e
           d
    ---    c (ledger line)

```

Obviously, the input must respect the case for the notes, but you can choose the case of the `f` and `s` modifiers.

Notes `c` and `A` must add two `-` (ledger lines), one at each side, as they must extend the staff. Notes `d` and `G` are out of the staff but do not need ledger lines.

Flatten or sharpened notes must add `b` or `#` two positions at the left of the note.

The stems (if any) must be drawn with 4 vertical bars. Notes from `b` and above must draw the stem downwards and at the left side of the note. Notes from `a` and below must draw the stem upwards and at the right side of the note. Quavers must add the flag, always rightwards and exactly as shown, and do not need to be beamed if there are several of them in a row.

```
--------------------------

-----|\----b-*------------
     | |    |
-----|------|-------------
     |      | |
----*-------|/---------|--
    ↑↑                 |
----||------↑↑---------|--
    ||      ||         |
    ||      ||      #-*-
    |\      |\        ↑↑
    | Stem  | Note    | Stem
    Note    Stem      Note

```

As usual, your program/function can directly draw the output or return a string, array of strings, matrix of characters or any other reasonable format.

### Useful links

This is , so may the shortest program/function for each language win!

Bonus: try to write examples with famous melodies and let everyone try to guess which melody it is!

# Answer
# Charcoal, ~~180~~ ~~171~~ ~~168~~ 163 bytes

```
Ｆ⁵⁺⸿⸿×-⁺²⁷×⁸№θ ↑⁹←↙↓⁹Ｊ⁴¦⁹↑⁶↗¹↑²↖¹↓↙¹↓³↙²↓³ \Ｍ²↑(| ↘¹↙)↙¹↓²↙¹↑←_*Ｆ⪪θ «Ａ⌕AGFEDCbagfedc§ι¹λＪχλＡ⁺⁹χχ¿⁼³Ｌι§b#⁼§ι²s→Ｐ×³¬﹪λ²→Ｐ§o*›ι4¿›ι2¿›λ⁶«↗↑⁴¿›ι8«↘↘¹↓¹»»«↙↓⁴¿›ι8«↗↗¹↑¹

```

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

```
Ｆ⁵⁺⸿⸿×-⁺²⁷×⁸№θ ↑⁹←↙↓⁹

```

Print the stave.

```
Ｊ⁴¦⁹↑⁶↗¹↑²↖¹↓↙¹↓³↙²↓³ \Ｍ²↑(| ↘¹↙)↙¹↓²↙¹↑←_*

```

Print the clef.

```
Ｆ⪪θ «

```

Loop through each note.

```
Ａ⌕AGFEDCbagfedc§ι¹λ

```

Find the Y-coordinate of the note.

```
ＪχλＡ⁺⁹χχ

```

This is really sneaky: `χ` is a variable that is predefined to 10, which is exactly the X-coordinate of the first note's accidental, if it has one. After jumping to that position, 9 is added to it, representing the next note position.

```
¿⁼³Ｌι§b#⁼§ι²s→

```

Print the accidental, if there is one.

```
Ｐ×³¬﹪λ²→Ｐ§o*›ι4

```

Print the ledger lines if necessary and the note. In fact the line is printed on any even y-coordinate although printing it over the stave has no effect of course.

```
¿›ι2

```

Nothing more to do for semibreves.

```
¿›λ⁶«

```

For notes below the midpoint,

```
↗↑⁴

```

draw the stem upwards,

```
¿›ι8«↘↘¹↓¹

```

and the flag for quavers.

```
»»«

```

For notes above the midpoint,

```
↙↓⁴

```

draw the stem downwards,

```
¿›ι8«↗↗¹↑¹

```

and the flag for quavers.
> 9 votes

# Answer
# SOGL V0.12, ~~178~~ ~~175~~ ~~174~~ ~~173~~ ~~172~~ 171 bytes

```
l9*6«+@*@¶¹┐∑:@┌ŗ4Ο"γ;]∑«;‽ΗmzΖH+īN D‼,ΨU‛y‚_○¤└yΨšI‘7n2∆╬5;{" -o-”;l3=?Jζ2%Ƨ#bWGk+;}Jz7m««:U+;W7«κArBb3>?Ζo*ŗ}a2\?┌@ŗ}ē9*LI+a╬5b1>?4┐∙b8=?"■QD³‘┼}e9*5+a4-8a>?5+;2-;G↕№}╬5

```

Try it Here! (θ added for ease of use; To run as 171 bytes it expects the input to be on the stack)

As far as I can tell this works, but if you find any problems, tell me.

## Explanation:

### first part: canvas creation

```
l                                get the length of that array
 9*                              multiply by 9
   6«+                           add 12
      @*                         get that many spaces
        @¶                       push a space and a newline
          ¹                      put all the strings on the stack in an array
           ┐∑                    join with vertical bars
             :                   duplicate that string (which is a line with the ending barline but no staff)
              @┌ŗ                replace spaces with dashes (to make it a line with staff)
                 4Ο              encase 4 copies of the space lines in lines with the dashes
                   "...‘         push the G-clef without newlines
                        7n       split into an array of items of length 7
                          2∆╬5   at 1-indexed coordinates [2; -1] place the G-clef in the staff lines, extending the arrays size
                              ;  get the input split on spaces back on top of the stack

```

### second part: loop, note head placement

```
{                        loop over the input split on spaces
" -o-”                    push a template for a note head and leger lines
      ;                   get the input optop
       l3=?            }  if the length of the input is 3, then
           J                pop the last letter off from the input
            ζ               get its unicode point
             2%             modulo 2
               Ƨ#bW         get its index in "#b"
                   G        get the template ontop
                    k       remove its 1st letter
                     +      join the replaced input and the template
                      ;     get the input back ontop to be consisntent with how the if started

sidequest: parse the rest of the inputs
J                  pop the last letter off of the remaining input string (the note), leaving the note length as string on the stack below
 z                 push the lowercase alphabet
  7m               get its first 7 letters
    ««             put the first 2 at the end
      :            duplicate it
       U+          append it uppercased to the original
         ;W        get the notes letter ontop and get its 1-indexed index in that just created string
           7«κ     subtract it from 14
              A    save on variable A
               r   convert the note length to a number
                B  save on variable B

b3>?    }          if b>3 (aka if note length is either 4 or 8)
    Ζo*ŗ             replace "o" with "*"
         a2\?   }  if a divides by 2 (aka there isn't staff nor leger lines required)
             ┌@ŗ     replace "-" with " "

ē          push the value of variable E and after that increase it (default is user input number, which errors and defaults to 0)
 9*        multiply by 9
   LI+     increase by 11
      a    push variable a
       ╬5  at those positions (e*9+11, a) insert the note head template in the canvas

```

### third part: flags and stems

```
b1>?                      if b (note length)>1 (aka if the stem is needed at all)
    4┐∙                   get an array of 4 vertical bars
       b8=?       }       if b==8 (aka if the flag is needed)
           "■QD³‘           push "\    |"
                 ┼          add verically-down-then-horizontally-right

e9*                       push e*9 (now e starts with 1 as it's been increased) (the X coordinate for the flag)
   5+                     add 5 to it
     a4-                  push a-4 (the Y coordinate, 4 less than the note head as arrays get inserted from the top-left corner)
        8a>?         }    if 8>a (aka if the flag needs to be rotated)
            5+              add 5 to the Y coordinate
              ;2-;          subtract 2 from the X coordinate
                  G         get the stem&flag or stem ontop
                   ↕№       reverse it vertically and mirror characters
                      ╬5  insert the array of the stem and maybe flag at those coordinates

```
> 13 votes

# Answer
## JavaScript(ES6), ~~616~~ 527 bytes

Thanks @shaggy for removing almost 90 bytes

I had no idea about notes... until now, hope I got it right.

```
f=i=>i.map((v,p)=>(k[e=(w=q+12)*(l="AGFEDCbagfedc".search(v[1]))+p*9+12]="o*"[(s=v[0])>3|0],l<1|l>11&&(k[e-1]=k[e+1]="-"),(t=v[2])&&(k[e-2]="b#"[t>"f"|0]),--s&&[1,2,3,4].map(i=>(k[(b=l<8)?e+w*i-1:e-w*i+1]="|",s>6&&( b?k[e+w*4]="/":k[e-w*4+2]="\\",k[b?e+w*3+1:e-w*3+3]='|')))),k=[...`    /\\  ${s=" ".repeat(q=i.length*9)}
   | |  ${s}
---|-|--${l="-".repeat(q)+"|-|"}
   |/   ${t=s+"| |"}
---/|---${l}
  / |   ${t}
-|--|---${l}
 | (| \\ ${t}
-|--|--)${l}
  \\ | / ${t}
-----|--${l}
     |  ${s}
   *_/  ${s}`])&&k.join``

console.log(f(["8g","8Df","4cs","2C","1A"]))
```

```
.as-console-wrapper { max-height: 100% !important; top: 0 }
.as-console-row:after { display: none !important; }
```

**explanation**

```
f=i=>i.map((v,p)=>( // for each note

  k[e=(w=q+12)*(l="AGFEDCbagfedc".search(v[1]))+p*9+12]= // position in 1D array to set the note to
  "o*"[(s=v[0])>3|0], // note value (either o or *)

  l<1|l>11&&(k[e-1]=k[e+1]="-"), // add leger line

  (t=v[2])&&(k[e-2]="b#"[t>"f"|0]), // add sharp or flat

  --s&&[1,2,3,4].map(i=> // add the 4 stem lines
                     (k[(b=l<8)?e+w*i-1:e-w*i+1]="|", // durration over eigth note => add stem

                      s>6&&( // if to add a flag
                        b?k[e+w*4]="/":k[e-w*4+2]="\\", // add flag either on left or the right side

                        k[b?e+w*3+1:e-w*3+3]='|') // add the line after the flag
                     )
                    )
),
// template, extended to the final length with lines
k=[...`    /\\  ${s=" ".repeat(q=i.length*9)}
   | |  ${s}
---|-|--${l="-".repeat(q)+"|-|"}
   |/   ${t=s+"| |"}
---/|---${l}
  / |   ${t}
-|--|---${l}
 | (| \\ ${t}
-|--|--)${l}
  \\ | / ${t}
-----|--${l}
     |  ${s}
   *_/  ${s}`])&&k.join``

```
> 10 votes

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


title: Calculate Treewidth

text:
# Question
Title: Calculate Treewidth
The treewidth of an undirected graph is a very important concept in Graph Theory. Tons of graph algorithms have been invented which run fast if you have a decomposition of the graph with small treewidth.

The treewidth is often defined in terms of tree decompositions. Here's a graph and a tree decomposition of that graph, courtesy of Wikipedia:

A tree decomposition is a tree where each vertex is associated with a subset of the vertices of the original graph, with the following properties:

* Every vertex in the original graph is in at least one of the subsets.
* Every edge in the original graph has both of its vertices in at least one of the subsets.
* All of the vertices in the decomposition whose subsets contain a given original vertex are connected.

You can check that the above decomposition follows these rules. The width of a tree decomposition is the size of its largest subset, minus one. Therefore, it is two for the above decomposition. The treewidth of a graph is the smallest width of any tree decomposition of that graph.

---

In this challenge, you will be given a connected, undirected graph, and you must find its treewidth.

While finding tree decompositions is hard, there are other ways to calculate the treewidth. The Wikipedia page has more info, but one method of calculating treewidth not mentioned there which is often used in algorithms to calculate the treewidth is the minimum elimination ordering width. See here for a paper using this fact.

In an elimination ordering, one eliminates all of the vertices of a graph one at a time. When each vertex is eliminated, edges are added connecting all of that vertex's neighbors to each other. This is repeated until all of the vertices are gone. The elimination ordering width is the largest number of neighbors that any vertex which is being eliminated has during this process. The treewidth is equal to the minimum over all orderings of the elimination ordering width. Here is an example program using this fact to calculate the treewidth:

```
import itertools
def elimination_width(graph):
    max_neighbors = 0
    for i in sorted(set(itertools.chain.from_iterable(graph))):
        neighbors = set([a for (a, b) in graph if b == i] + [b for (a, b) in graph if a == i])
        max_neighbors = max(len(neighbors), max_neighbors)
        graph = [edge for edge in graph if i not in edge] + [(a, b) for a in neighbors for b in neighbors if a < b]
    return max_neighbors

def treewidth(graph):
    vertices = list(set(itertools.chain.from_iterable(graph)))
    min_width = len(vertices)
    for permutation in itertools.permutations(vertices):
        new_graph = [(permutation[vertices.index(a)], permutation[vertices.index(b)]) for (a, b) in graph]
        min_width = min(elimination_width(new_graph), min_width)
    return min_width

if __name__ == '__main__':
    graph = [('a', 'b'), ('a', 'c'), ('b', 'c'), ('b', 'e'), ('b', 'f'), ('b', 'g'),
            ('c', 'd'), ('c', 'e'), ('d', 'e'), ('e', 'g'), ('e', 'h'), ('f', 'g'), ('g', 'h')]
    print(treewidth(graph))

```

---

Examples:

```
[(0, 1), (0, 2), (0, 3), (2, 4), (3, 5)]
1

[(0, 1), (0, 2), (1, 2), (1, 4), (1, 5), (1, 6), (2, 3), (2, 4), (3, 4), (4, 6), (4, 7), (5, 6), (6, 7)]
2

[(0, 1), (0, 3), (1, 2), (1, 4), (2, 5), (3, 4), (3, 6), (4, 5), (4, 7), (5, 8), (6, 7), (7, 8)]
3

[(0, 1), (0, 2), (0, 3), (0, 4), (1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)]
4

```

---

You will receive the graph as input, and you must return the treewidth as output. The input format is flexible. You may take a list of edges, an adjacency map, or an adjacency matrix as input. If you'd like to use another input format, ask in the comments. You may assume the input is connected, and you may build that assumption into your input format, e.g. by using a list of edges.

EDIT: Built-in operations which calculate treewidth are not allowed. I apologize for not specifying this up front.

Shortest code wins.

# Answer
# Octave, 195 bytes

```
function x=F(a)r=rows(a);P=perms(s=1:r);x=r;for m=s;b=a;n=0;for z=P(m,:);(T=sum(b)(z))&&{b|=(k=accumarray(nchoosek(find(b(z,:)),2),1,[r r]))|k';n=max(T,n);b(z,:)=0;b(:,z)=0}{4};end;x=min(x,n);end

```

A function that takes as input an adjacency matrix. It consumes large amount of memory so it is useless if number of vertices is more than 10-12.

* there is no need to `endfunction` however it should be added to tio.

Try it online!

Ungolfed:

```
function min_width = treewidth(graph_adj)
    Nvertices = rows(graph_adj)
    Permutations = perms(1:Nvertices);                                                            % do not try it for large number of vertices
    min_width = Nvertices;
    for v = 1:Nvertices;
        new_graph=graph_adj;
        max_neighbors=0;
        for p = Permutations(v,:)
            Nneighbors=sum(new_graph)(p);
            if(Nneighbors)>0
                connection=accumarray(nchoosek(find(new_graph(p,:)),2),1,[Nvertices Nvertices]);  % connect all neighbors
                new_graph|=connection|connection';                                                % make the adjacency matrix symmetric
                new_graph(p,:)=0;new_graph(:,p)=0;                                                % eliminate the vertex
                max_neighbors=max(Nneighbors,max_neighbors);
            end
        end
        min_width=min(min_width,max_neighbors);
    end
end

```
> 7 votes

# Answer
# SageMath , ~~29 bytes~~ noncompeting\*

```
lambda L:Graph(L).treewidth()

```

\*This answer posted before OP's change of the question that "Builtins are banned", so I maked it noncompeting .

Online Demo!
> 5 votes

# Answer
# Haskell (Lambdabot), ~~329~~ ~~321~~ 245 bytes

Here's my solution, thanks to the flexibility of the input it works on graphs with graphs containing any type that is an instance of `Eq`.

```
(&)=elem
l=length
t n g s=last$minimum[max(t n g b)$t(n++b)g$s\\b|b<-filterM(\_->[0>1,1>0])s,l b==div(l s)2]:[l[d|d<-fst g,not$d&n,d/=s!!0,(d&)$foldr(\x y->last$y:[x++y|any(&y)x])[s!!0]$join(>>)[e|e<-snd g,all(&(s!!0:d:n))e]]|1==l s]
w=t[]<*>fst

```

Try it online!

### Ungolfed version:

```
type Vertex a = a
type Edge a   = [Vertex a]
type Graph a  = ([Vertex a],[Edge a])

vertices = fst
edges = snd

-- This corresponds to the function w
treeWidth :: (Eq a) => Graph a -> Int
treeWidth g = recTreeWidth g [] (vertices g)

-- This is the base case (length s == 1) of t
recTreeWidth graph left [v] =
    length [ w | w <- vertices graph
               , w `notElem` left
               , w /= v
               , w `elem` reachable (subGraph w)
           ]

  where subGraph w = [ e | e <- edges graph, all (`elem` v:w:left) e ]

        reachable g = foldr accumulateReachable [v] (g>>g)
        accumulateReachable x y = if any (`elem` y) x
                                  then x++y
                                  else y

-- This is the other case of t
recTreeWidth graph left sub =
  minimum [ comp sub' | sub' <- filterM (const [False,True]) sub
                      , length sub' == div (length sub) 2
          ]

  where comp b = max (recTreeWidth graph left b)
                     (recTreeWidth graph (left++b) (sub\\b))

```
> 5 votes

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