title: Music: what's in this chord?

text:
# Question
Title: Music: what's in this chord?
# Input

The symbol of any triadic chord (see http://en.wikipedia.org/wiki/Chord\_(music)#Triads).

# Output

The notes constituting the given chord.

# Examples

Input: `AM` Output: `A C# E`

Input: `C#m` Output: `C# E G#`

Input: `Db+` Output: `C# F A`

Input: `C0` Output: `C D# F#`

# Bonuses

**-50** if you can also deal with seventh chords

**-150** for actually playing the sound of the chord

**-150** for using printable characters to show how to play the chord on a piano; example for `AM`:

```
┌─┬─┬┬─┬─┬─┬─┬┬─┲┱─┬─┬─┲━┱┬─┲━┱─┬─┬┬─┬┬─┬─┐
│ │ ││ │ │ │ ││ ┃┃ │ │ ┃ ┃│ ┃ ┃ │ ││ ││ │ │
│ │ ││ │ │ │ ││ ┃┃ │ │ ┃ ┃│ ┃ ┃ │ ││ ││ │ │
│ │ ││ │ │ │ ││ ┃┃ │ │ ┃ ┃│ ┃ ┃ │ ││ ││ │ │
│ └┬┘└┬┘ │ └┬┘└┲┛┗┱┘ │ ┗┯┛└┲┛ ┃ └┬┘└┬┘└┬┘ │
│  │  │  │  │  ┃  ┃  │  │  ┃  ┃  │  │  │  │
└──┴──┴──┴──┴──┺━━┹──┴──┴──┺━━┹──┴──┴──┴──┘

```

**-100** for using printable characters to show how to play the chord on a guitar; example for `AM`:

```
x   o   o   o   o   o
┌───┬───┬───┬───┬───┐
│   │   │   │   │   │
├───┼───┼───┼───┼───┤
│   │   │   │   │   │
├───┼───┼───┼───┼───┤
│   │   █   █   █   │
├───┼───┼───┼───┼───┤
│   │   │   │   │   │

```

(see https://en.wikipedia.org/wiki/Box-drawing\_character)

# Rules

* The result must be a command-line program or script.
* The input and output can be in any form, as long as it follows a music notation standard.
* A guitar or piano representation is considered valid if and only if it contains the three (triadic) or four (seventh) required notes and nothing else. The same note can be present several times in the chord.
* External libraries are not allowed, except for sound generation (in which case the `#include`, `import`... directives are not added to the character count).
* This is code golf, the shortest code wins!

# A little bit of music theory...

In modern Western tonal music, every octave is made of twelve successive notes, often noted:

`A` `A#` `B` `C` `C#` `D` `D#` `E` `F` `F#` `G` `G#`

Or:

`La` `La#` `Si` `Do` `Do#` `Re` `Re#` `Mi` `Fa` `Fa#` `Sol` `Sol#`

In this system, we consider that two successive notes (e.g. `A` and `A#`, or `E` and `F`) are separated by one semitone. Also, the notes are kind of "looping": what immediately follows `G#` is `A`.

A chord is constituted by a few (2, 3, 4, sometimes more) notes that "sound good together". For instance, triadic chords contain three different notes, and seventh chords contain four different notes.

Let's define the four triadic chords as:

* **Major triad**: contains the root of the chord (in this question, the note given as input), the major third for the root (4 semitones higher than the root), and the perfect fifth for the root (7 semitones higher than the root); this can be symbolized 0-4-7
* **Minor triad**, symbolized 0-3-7
* **Augmented triad**, symbolized 0-4-8
* **Diminished triad**, symbolized 0-3-6

So for example, if you want to make a *C major triad*, noted `C`, `CM`, `Cmaj`, you will need three noted:

* 0: the *root*, in this case a `C`
* 4: the *minor third*, 4 semitones higher than the root; that's an `E`
* 7: the *perfect fifth*, 7 semitones higher than the root: a `G`

This is what the `0-4-7`, `0-3-7`, `0-4-8` and `0-3-6` notations used above mean! For the seventh chords, use the following pattern:

That's it for today! Now, amaze me with amazing code... If you have any question, add some comments below.

# Answer
# BBC BASIC

Emulator at bbcbasic.co.uk

# Rev 1, 340 - 150 keyboard - 150 playing = 40

Here's the latest version, in which I managed to include the following enhancements while lengthening by only a few more characters.

**Input can be edited comfortably on the screen before pressing return** (I was using GET$ before to get single keypresses, because BBC Basic does not let you access a single character from a string as if the string was an array. Now I use the rather bulky MID$ function to extract a string of one character from within the string.

**Both sides of keyboard displayed as well as the full line between E and F.**

To compensate for the characters added by the above, I rearranged the program to eliminate unnecessary print statements, and deleted some white space which at first sight looked like it couldnt be deleted. IN BBC Basic all built in functions are reserved words, and you can put a variable name right before them with no space in between. Variable names are not allowed to start with a reserved word. In order to make the program less confusing to read I changed all variables to lower case.

Although the presentation looks much better, the following program is actually  ~~fully golfed already.~~  (See correction below.) Generally newlines and colons are interchangeable, except when an IF statement is used. In that case all statements on the same line (separated by colons) with be executed conditionally. Statements after the newline are not controlled by the IF and will always be executed.

**Program rev 1 340 characters**

```
  a$="C#D#EF#G#A#B0Mm+"
  INPUTx$
  r=INSTR(a$,LEFT$(x$,1))-1
  c=INSTR(a$,MID$(x$,2,1))
  IFc=2c=INSTR(a$,MID$(x$,3)):r=r+1
  t=(r+4-c MOD2)MOD12
  f=(r+c DIV2)MOD12
  v=1
  FORn=-1TO11
  c=1-(n<0ORn=4ORn=11)*5
  b$=MID$(a$,n+1,1)
  IFb$="#"c=11:b$=MID$(a$,n,1)+b$
  c$=MID$("   _______--|__",c,5)
  IFr=n ORt=n ORf=n c$=c$+b$:SOUNDv,-15,100+n*4,99:v=v+1
  PRINTc$
  NEXT

```

CORRECTION: RT Russell's BBC BASIC for Windows allows you to eliminate some newlines and colons, bringing the total down to 327, see below. Also it tokenises the keywords into single characters before saving, bringing it down to 279.

```
  a$="C#D#EF#G#A#B0Mm+"INPUTx$
  r=INSTR(a$,LEFT$(x$,1))-1c=INSTR(a$,MID$(x$,2,1))IFc=2c=INSTR(a$,MID$(x$,3))r=r+1
  t=(r+4-c MOD2)MOD12f=(r+c DIV2)MOD12v=1FORn=-1TO11c=1-(n<0ORn=4ORn=11)*5b$=MID$(a$,n+1,1)IFb$="#"c=11b$=MID$(a$,n,1)+b$
  c$=MID$("   _______--|__",c,5)IFr=n ORt=n ORf=n c$=c$+b$SOUNDv,-15,100+n*4,99v=v+1
  PRINTc$
  NEXT

```

**Output rev 1**

# Rev 0, 337 - 150 keyboard - 150 playing = 37

```
A$="C#D#EF#G#A#B0Mm+":X$=GET$:R=INSTR(A$,X$)-1:X$=GET$:IF X$="#"R=R+1:X$=GET$
C=INSTR(A$,X$):T=(R+4-C MOD2)MOD12:F=(R+C DIV2)MOD12:V=1:PRINT"______"
FORN=0 TO 11
C=1-(N=4)*12:B$=MID$(A$,N+1,1): IF B$="#" C=7: B$=MID$(A$,N,1)+B$
PRINT MID$("    __---|________",C,6);:IF(R-N)*(T-N)*(F-N)=0 PRINT B$;:SOUND V,-15,100+N*4,99:V=V+1
PRINT
NEXT

```

This is a similar concept to my Arduino answer, but I always knew I could beat that byte count with BBC basic. Only recognises sharps, but considers B# invalid,you must put C. This could be fixed if it was really considered important.

I abandoned the idea of guitar and concentrated on improving the keyboard. It now runs from C to B, and I've added in the left side of the keyboard and the line between E and F. That costs 28 characters. The right hand side wouldn't be much more.

Here's some sample output, an A# diminished chord (which has a pretty freaky sound in this inversion) and a B major chord. Note that the input is not echoed to the screen. As per the Arduino answer, turn the screen anticlockwise to view.

**Ungolfed version**

```
A$="C#D#EF#G#A#B0Mm+"                              :REM Note names and chord type names fit very conveniently in the same string.
X$=GET$                                            :REM Get a character
R=INSTR(A$,X$)-1                                   :REM Root note = position of that char in A$. INSTR starts counting at 1, but we want 0, so subtract.
X$=GET$                                            :REM If the root note is natural, the next character will be the chord type. But...
IF X$="#"R=R+1:X$=GET$                             :REM If this char is # we need to increment the root, and get another char for chord type.
C=INSTR(A$,X$)                                     :REM C encodes for chord type
T=(R+4-C MOD2)MOD12                                :REM even C means major third, odd C means minor third
F=(R+C DIV2)MOD12                                  :REM "Mm" gives C=14,15 meaning C DIV2=7 (perfect fifth.) C=13,16 give diminished and augmented: 6,8.
V=1                                                :REM V is the sound channel number ("voice")
PRINT"______"                                      :REM left side of keyboard for cosmetic reasons
FORN=0 TO 11                                       :REM at the start of each iteration initialise C to 1, to point to the 4 spaces/2 underscores in the string below for drawing white notes.
  C=1-(N=4)*12                                     :REM if the note is E, add 12 so it points to the 6 underscores to draw the line between E and F.
  B$=MID$(A$,N+1,1)                                :REM load B$ with the name of the current note.
  IF B$="#" C=7: B$=MID$(A$,N,1)+B$                :REM if the character encountered is a sharp, update C to point the characters for drawing a sharp. Find the previous character in A$ and join it to the beginning of B$ to complete the note name.
  PRINT MID$("    __---|________",C,6);            :REM print the key (6 characters.)
  IF(R-N)*(T-N)*(F-N)=0 PRINT B$;:SOUND V,-15,100+N*4,99:V=V+1  :REM if N is equal to R,T or F, print the note name beside the key, play the note and increment the channel number for the next note.
  PRINT                                            :REM print a carriage return. It may be possible to golf this line out.
NEXT

```
> 5 votes

# Answer
As you can tell, I didn't try to golf this at all. I'm a music geek, and a pet peeve of mine is when people write things using the wrong enharmonics (e.g. saying that a C diminished chord is C D# F# instead of C Eb Gb), so I wrote this program that gets the enharmonics right. It does so by representing each note as the number of perfect fifths above F.

For what it's worth, if you want to distinguish enharmonics, any musical interval can be represented nicely in a computer program as a number of perfect fifths and a number of octaves. An augmented fourth, for example, is 6 perfect fifths and -3 octaves, and a diminished fifth is -6 perfect fifths and 4 octaves.

# Haskell, 441 characters

```
import Data.List

notes = "FCGDAEB"

fromNum x = [notes !! (mod x 7)] ++ if x < 0 then replicate (-(div x 7)) 'b' else replicate (div x 7) '#'

toNum (x:xs) = y + 7 * if isPrefixOf "b" xs then -length xs else length xs
    where Just y = elemIndex x notes

chord xs = unwords . map (fromNum . \x -> toNum (init xs) + x) $ case last xs of 'A' -> [0,4,8]; 'M' -> [0,4,1]; 'm' -> [0,-3,1]; 'd' -> [0,-3,-6]

main = getLine >>= putStrLn . chord

```

Some example invocations:

```
jaspers:junk tswett$ ./chord
AM
A C# E
jaspers:junk tswett$ ./chord
C#m
C# E G#
jaspers:junk tswett$ ./chord
DbA
Db F A
jaspers:junk tswett$ ./chord
Cd
C Eb Gb
jaspers:junk tswett$ ./chord
A#M
A# C## E#
jaspers:junk tswett$ ./chord
Dbm
Db Fb Ab

```
> 9 votes

# Answer
# Python3 - 315 char

First time in codegolf! Only supports minor, major, diminished and augmented chords right now.

```
z=["C","C#","D","D#","E","F","F#","G","G#","A","A#","B"];y=[1,2,4,5,6]
def q(a):print(z[a%12])
a=input();k=(ord(a[0])+3)%7;j=k;m=4;s=0;f=7;
for i in y:
    if(k>=i):j+=1
if('#'in a):j+=1
if('b'in a):j-=1
if('m'in a or'0'in a):m=3
if('+'in a or"aug"in a):f=8
if('0'in a or"dim"in a):f=6;m=3
if('ma'in a):m=4
q(j);q(j+m);q(j+f);

```
> 5 votes

# Answer
# Arduino

Input/output is sent to / received from the Arduino via a COM port. A user can interact with this via a terminal, or the serial monitor in the Arduino IDE. As you may have guessed from my choice of platform, I am planning to include the actual playing of the chord (though I haven't done it yet.)

I have tackled the keyboard bonus successfully, and I have tried to tackle the guitar, with limited success.

The chord box comes in at 130 bytes, which is too long to be worth it. Therefore I have tried another way, just printing the fret numbers Tab style. Currently this is 81 bytes for a bonus of 81-100=-19. **If this approach is deemed valid I can try and improve on it.**

The chords used are all D-type shapes with the root on the 2nd string, fifth on the 3rd string, and third on the 1st and 4th strings. The 5th and 6th strings are not used and I mark this with X's on the right of the chord box (the left would be more usual, but examples marked on the right can be found.)

Because the program considers F to be the lowest note (for compatability with the keyboard while avoiding excessively high frets with this chord shape) the highest chord is an E (with root on the 17th fret.) See example output.

The keyboard is more successful in terms of golfing. It runs from F-E rather than C-B for the reasons described above. It must be viewed by turning the screen 90% anticlockwise, when you can clearly see the outlines of the black notes, and the demarcation between the white notes with `---`. The line between B an C could be extended with some `____` for a few more bytes.

I will try playing the notes next. This will be interesting because, although I believe the Arduino Uno has 3 internal timers, only one note at a time can be played using the built in tone command. There is an external library function which uses all the hardware timers (which will mess up the serial, but it won't be needed at that stage anyway.) Alternatively I may try to produce the tones in softare.

If I am successful with that, I will golf it down but I don't think it will be the overall winner.

**Ungolfed code**

```
String p="F#G#A#BC#D#E -Mm+",y,d[]=
{"    ","---|"},n="\n";

void setup() {
  Serial.begin(9600);
  Serial.setTimeout(99999);
}

void loop(){
  char x[9]; int r,t,f,i,c=1;
  Serial.readBytesUntil(13,x,9);
  Serial.println(x);
  r=p.indexOf(x[0]);
  if (x[1]==35|x[1]==98){c=2;r+=x[1]==35?1:-1;}
  f=p.indexOf(x[c])/2;
  t=4-p.indexOf(x[c])%2;

  //chord box
  y=n;for(i=24;i--;)y+=d[1]+(i%4?"":" \n");
  y[89]=y[107]='X'; y[t*4-10]=y[t*4+52]=y[f*4+14]=y[28]='O';
  Serial.print("\t "+String(r+6)+y);

  f+=r;t+=r;

  //tab style
  Serial.println(String(t+1)+n+String(r+6)+n
  +String(f-2)+n+String(t+3)+"\nX\nX\n");

  f%=12;t%=12;

  //piano
  for(i=0;i<12;i++){
    c=0;
    y=String(p[i]);
    if(y=="#") {c=1;y=p[i-1]+y;}
    Serial.println(d[c]+"__"+((r-i&&t-i&&f-i)?"":y));
  }
}

```

**Sample output** The lower the spacing between the lines of text, the better this looks. Therefore it looks great when I am actually editing the post, but horrible in the grey box after posting. Instead I've posted a screenshot of the Arduino serial monitor which is of intermediate line spacing (and hence display quality.)
> 5 votes

# Answer
# Python 506(unicode as 1 char)-150(sound)-150(keyboard) = 206

For sound playing, it uses `pygame.midi`. Note that the `pygame.midi.get_default_output_id()` method don't work very well. So you may try changing the line `o=Output(get_default_output_id())` to `o=Output(1)`, `o=Output(2)`, etc. Usually the correct value is between 0 and 5.

```
c=input()
s='C D EF G A B'.index(c[0])+{'#':1,'b':-1,'':0}[c[1:-1]]
m='0mM+'.index(c[-1])
t=s+3+m//2
R=[list(x)for x in['┌─'+'─┬─'*13+'─┐']+['│'+'  │'*14]*5+['└─'+'─┴─'*13+'─┘']]
i=3
for d in[3,6,3,3,6]*2:q=slice(i-1,i+2);R[0][q]='┬─┬';R[1][q]=R[2][q]=R[3][q]='│ │';R[4][q]='└┬┘';i+=d
X=[2]+[1,2,1,2,3,1,2,1,2,1,2,3]*2
from pygame.midi import*
init()
o=Output(get_default_output_id())
for s in[s,t,t+3+m%2]:R[[5,3][s%12 in[1,3,6,8,10]]][sum(X[:s+1])]='o';o.note_on(s+60,127,1)
for r in R:print(''.join(r))

```

## Results

```
goooolf> python chords2.py
CM
┌─┬─┬┬─┬─┬─┬─┬┬─┬┬─┬─┬─┬─┬┬─┬─┬─┬─┬┬─┬┬─┬─┐
│ │ ││ │ │ │ ││ ││ │ │ │ ││ │ │ │ ││ ││ │ │
│ │ ││ │ │ │ ││ ││ │ │ │ ││ │ │ │ ││ ││ │ │
│ │ ││ │ │ │ ││ ││ │ │ │ ││ │ │ │ ││ ││ │ │
│ └┬┘└┬┘ │ └┬┘└┬┘└┬┘ │ └┬┘└┬┘ │ └┬┘└┬┘└┬┘ │
│ o│  │ o│  │ o│  │  │  │  │  │  │  │  │  │
└──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┘
goooolf> python chords2.py
Cm
┌─┬─┬┬─┬─┬─┬─┬┬─┬┬─┬─┬─┬─┬┬─┬─┬─┬─┬┬─┬┬─┬─┐
│ │ ││ │ │ │ ││ ││ │ │ │ ││ │ │ │ ││ ││ │ │
│ │ ││ │ │ │ ││ ││ │ │ │ ││ │ │ │ ││ ││ │ │
│ │ ││o│ │ │ ││ ││ │ │ │ ││ │ │ │ ││ ││ │ │
│ └┬┘└┬┘ │ └┬┘└┬┘└┬┘ │ └┬┘└┬┘ │ └┬┘└┬┘└┬┘ │
│ o│  │  │  │ o│  │  │  │  │  │  │  │  │  │
└──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┘
goooolf> python chords2.py
Dm
┌─┬─┬┬─┬─┬─┬─┬┬─┬┬─┬─┬─┬─┬┬─┬─┬─┬─┬┬─┬┬─┬─┐
│ │ ││ │ │ │ ││ ││ │ │ │ ││ │ │ │ ││ ││ │ │
│ │ ││ │ │ │ ││ ││ │ │ │ ││ │ │ │ ││ ││ │ │
│ │ ││ │ │ │ ││ ││ │ │ │ ││ │ │ │ ││ ││ │ │
│ └┬┘└┬┘ │ └┬┘└┬┘└┬┘ │ └┬┘└┬┘ │ └┬┘└┬┘└┬┘ │
│  │ o│  │ o│  │ o│  │  │  │  │  │  │  │  │
└──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┘
goooolf> python chords2.py
D+
┌─┬─┬┬─┬─┬─┬─┬┬─┬┬─┬─┬─┬─┬┬─┬─┬─┬─┬┬─┬┬─┬─┐
│ │ ││ │ │ │ ││ ││ │ │ │ ││ │ │ │ ││ ││ │ │
│ │ ││ │ │ │ ││ ││ │ │ │ ││ │ │ │ ││ ││ │ │
│ │ ││ │ │ │o││ ││o│ │ │ ││ │ │ │ ││ ││ │ │
│ └┬┘└┬┘ │ └┬┘└┬┘└┬┘ │ └┬┘└┬┘ │ └┬┘└┬┘└┬┘ │
│  │ o│  │  │  │  │  │  │  │  │  │  │  │  │
└──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┘
G+
┌─┬─┬┬─┬─┬─┬─┬┬─┬┬─┬─┬─┬─┬┬─┬─┬─┬─┬┬─┬┬─┬─┐
│ │ ││ │ │ │ ││ ││ │ │ │ ││ │ │ │ ││ ││ │ │
│ │ ││ │ │ │ ││ ││ │ │ │ ││ │ │ │ ││ ││ │ │
│ │ ││ │ │ │ ││ ││ │ │ │ ││o│ │ │ ││ ││ │ │
│ └┬┘└┬┘ │ └┬┘└┬┘└┬┘ │ └┬┘└┬┘ │ └┬┘└┬┘└┬┘ │
│  │  │  │  │ o│  │ o│  │  │  │  │  │  │  │
└──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┘
goooolf> python chords2.py
Am
┌─┬─┬┬─┬─┬─┬─┬┬─┬┬─┬─┬─┬─┬┬─┬─┬─┬─┬┬─┬┬─┬─┐
│ │ ││ │ │ │ ││ ││ │ │ │ ││ │ │ │ ││ ││ │ │
│ │ ││ │ │ │ ││ ││ │ │ │ ││ │ │ │ ││ ││ │ │
│ │ ││ │ │ │ ││ ││ │ │ │ ││ │ │ │ ││ ││ │ │
│ └┬┘└┬┘ │ └┬┘└┬┘└┬┘ │ └┬┘└┬┘ │ └┬┘└┬┘└┬┘ │
│  │  │  │  │  │ o│  │ o│  │ o│  │  │  │  │
└──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┘
goooolf> python chords2.py
C#0
┌─┬─┬┬─┬─┬─┬─┬┬─┬┬─┬─┬─┬─┬┬─┬─┬─┬─┬┬─┬┬─┬─┐
│ │ ││ │ │ │ ││ ││ │ │ │ ││ │ │ │ ││ ││ │ │
│ │ ││ │ │ │ ││ ││ │ │ │ ││ │ │ │ ││ ││ │ │
│ │o││ │ │ │ ││ ││ │ │ │ ││ │ │ │ ││ ││ │ │
│ └┬┘└┬┘ │ └┬┘└┬┘└┬┘ │ └┬┘└┬┘ │ └┬┘└┬┘└┬┘ │
│  │  │ o│  │ o│  │  │  │  │  │  │  │  │  │
└──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┘
goooolf> python chords2.py
EbM
┌─┬─┬┬─┬─┬─┬─┬┬─┬┬─┬─┬─┬─┬┬─┬─┬─┬─┬┬─┬┬─┬─┐
│ │ ││ │ │ │ ││ ││ │ │ │ ││ │ │ │ ││ ││ │ │
│ │ ││ │ │ │ ││ ││ │ │ │ ││ │ │ │ ││ ││ │ │
│ │ ││o│ │ │ ││ ││o│ │ │ ││ │ │ │ ││ ││ │ │
│ └┬┘└┬┘ │ └┬┘└┬┘└┬┘ │ └┬┘└┬┘ │ └┬┘└┬┘└┬┘ │
│  │  │  │  │ o│  │  │  │  │  │  │  │  │  │
└──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┘

```
> 5 votes

# Answer
# J - 82 char

Self-contained, reads from console input. If you need stdin, change the final `1` to a `3`. Claiming no bonuses, and only covering the triads.

```
+/&(0 3 6++/\_3{.#:'0mM+'i.{:e)&.((,~C`Db`D`Eb`E`F`Gb`G`Ab`A`Bb`B)i.;:)}:e=.1!:1]1

```

Instead of a sharp note e.g. `C#` you must use the equivalent flat name `Db`. (Correcting for this would inflate the code by more than a bit.) The four types of chords are `0` for diminishing, `m` for minor, `M` for major, and `+` for augmented.

The logic is as follows: we use the last character to add an offset to the base 0-3-6, which selects the kind of third and fifth. Meanwhile, we use the note to find where in the scale to pull the notes from. The `;:` both makes the note compatible with indexing into the scale at the start, and later (by `&.`) turns the pulled notes into a space separated string.

Example usage:

```
   +/&(0 3 6++/\_3{.#:'0mM+'i.{:e)&.((,~C`Db`D`Eb`E`F`Gb`G`Ab`A`Bb`B)i.;:)}:e=.1!:1]1
AM
A Ch E
   +/&(0 3 6++/\_3{.#:'0mM+'i.{:e)&.((,~C`Db`D`Eb`E`F`Gb`G`Ab`A`Bb`B)i.;:)}:e=.1!:1]1
Ab0
Ab B D
   +/&(0 3 6++/\_3{.#:'0mM+'i.{:e)&.((,~C`Db`D`Eb`E`F`Gb`G`Ab`A`Bb`B)i.;:)}:e=.1!:1]1
B+
B Eb G
   +/&(0 3 6++/\_3{.#:'0mM+'i.{:e)&.((,~C`Db`D`Eb`E`F`Gb`G`Ab`A`Bb`B)i.;:)}:e=.1!:1]1
Em
E G B

```
> 3 votes

# Answer
# Javascript, 224 char

```
n=prompt();a="A0A#0B0C0C#0D0D#0E0F0F#0G0G#".split(0);x=1;r=a.indexOf(n[0]);n[1]=="#"&&(r++,x++);n[1]=="b"&&(r--,x++);s=r+4;l=r+7;(n[x]=="m"||n[x]==0)&&s++;s%=12;n[x]=="+"&&l++;n[x]==0&&l--;l%=12;alert(a[r]+" "+a[s]+" "+a[l])

```

This is my first code golf. I think it can be shorter, but I can't find any bytes to save.

Supports major, `m` for minor, `0` for diminished, `+` for augmented, or 37 more bytes for `dim`, `aug`.
> 2 votes

# Answer
## Python (143 134 chars)

```
n,a='A A# B C C# D D# E F F# G G#'.split(),input();m,i=ord(a[-1])-42,n.index(a[:-1])
print(n[i],n[(i+4-m//2)%12],n[(i-4+(-m//2))%12])

```

My first golf challenge :), don't know if some more bytes can be shaved off.
The notation used here is * aug / + maj / , min / - dim
I deserve a bonus point for having the constant 42 in the code :P
> 2 votes

# Answer
## Scala 537 chars - 50

```
import java.util.Scanner
object C extends App{
val c=Map("M"->145,"m"->137,"+"->273,"0"->73,"7"->1169,"M7"->2193,"m7"->1161,"Mm7"->2185,"+7"->1297,"+M7"->2321,"07"->585,"7b5"->1097)
val n=List("A","A#","B","C","C#","D","D#","E","F","F#","G","G#")
val o=List("","Bb","Cb","B#","Db","","Eb","Fb","E#","Gb","","Ab")
val s=new Scanner(System.in).nextLine
val v=s indexWhere{c=>c!='#'&&c!='b'&&(c<'A'||c>'G')}
val (u,m)=s splitAt v
val x=n.indexOf(u)max o.indexOf(u)
val k=c(m)
for(i<-0 to 11)if((k&(1<<i))!=0)print(n((i+x)%12)+" ")
println}

```
> 2 votes

# Answer
# Python 3: 257 - 150 = 107

Just 25 chars too long to beat the J solution! Oh well. There are some neat ideas here, I think.

```
I='AaBCcDdEFfGg'*2
Q='0123456789.,'*2
K="""-1#_2
-,#_0
-9#_.
____8
-6#_7
-4#_5
____3"""
r,*R,q=input()
r=I.find(r)+bool(R)
p=str.replace
for x in[0]+[8,4,7,3,6]['+Mm0'.find(q):][:2]:K=p(K,Q[x+r],I[x+r].upper())
for x in Q:K=p(K,x,' ')
print(p(K,' #','  '))

```

Input is like the examples, though you must use sharp names instead of flat names. (e.g. Gb must be F#)

Output is a single octave of a piano, seen from above and to the left, with note names superimposed. Should be just a tiny stretch of the imagination.

```
$ echo C#m | python3 chords.py
-  _
-G#_
-  _
____
-  _E
-C#_
____

```
> 1 votes

# Answer
# Raku, 216 bytes

Shorter than my original Scala solution and spells pitches correctly to boot.

```
for $*IN.lines {m:P5/([A-G])(\#*)(b*)([Mm+0])/;my \r=4613502.comb[$0.ord-65]+7*($1.comb-$2.comb);put %(:M<0 4 1>,:m<0 -3 1>,"+",<0 4 8>,0,<0 -3 -6>){$3}.map({"FCGDAEB".comb[($/=r+$_)%7]~(<b #>)[$/>0]x abs($/div 7)})}

```

Try it online!
> 1 votes

# Answer
# Haskell, 273 chars

```
n(s,a)="CCDDEFFGGAABB"!!(s+1-a):["b#"!!a|" b b  b b b "!!s/=' ']
t p=[(s,a)|s<-[11,10..0],a<-[0,1],n(s,a)==p]!!0
m(s,d)=n(mod s 12,d-3)
c q=[n(a,x),m(a+d,d),m(a+d+e,e)]where
 (a,x)=t$init q;f=lookup(last q).zip"0mM+";Just d=f[3,3,4,4];Just e=f[3,4,3,4]
main=print.c=<<getLine

```

## Results

```
C0 ->["C","Eb","Gb"]   Cm ->["C","Eb","G"]    CM ->["C","E","G"]     C+ ->["C","E","G#"]
C#0->["C#","F","G"]    C#m->["C#","F","G#"]   C#M->["C#","F","Ab"]   C#+->["C#","F","A"]
D0 ->["D","F","Ab"]    Dm ->["D","F","A"]     DM ->["D","F#","A"]    D+ ->["D","F#","A#"]
D#0->["D#","Gb","A"]   D#m->["D#","Gb","A#"]  D#M->["D#","G","Bb"]   D#+->["D#","G","B"]
E0 ->["E","G","Bb"]    Em ->["E","G","B"]     EM ->["E","G#","B"]    E+ ->["E","G#","C"]
F0 ->["F","Ab","B"]    Fm ->["F","Ab","C"]    FM ->["F","A","C"]     F+ ->["F","A","C#"]
F#0->["F#","A","C"]    F#m->["F#","A","C#"]   F#M->["F#","A#","Db"]  F#+->["F#","A#","D"]
G0 ->["G","Bb","Db"]   Gm ->["G","Bb","D"]    GM ->["G","B","D"]     G+ ->["G","B","D#"]
G#0->["G#","B","D"]    G#m->["G#","B","D#"]   G#M->["G#","C","Eb"]   G#+->["G#","C","E"]
A0 ->["A","C","Eb"]    Am ->["A","C","E"]     AM ->["A","C#","F"]    A+ ->["A","C#","F"]
A#0->["A#","Db","F"]   A#m->["A#","Db","F"]   A#M->["A#","D","F"]    A#+->["A#","D","F#"]
B0 ->["B","D","F"]     Bm ->["B","D","F#"]    BM ->["B","D#","Gb"]   B+ ->["B","D#","G"]

```
> 0 votes

---
Tags: code-golf, music
---


title: How many semitones

text:
# Question
Title: How many semitones
# Guidelines

### Task

Given two notes, inputted as strings or lists/arrays, calculate how many semitones apart they are (inclusive of the notes themselves), outputting as a number.

**Explanation of a semitone:**

A semitone is one step up or down the keyboard. An example is C to C#. As you can see below the note C is on a white note and C# is the black note just one above it. Semitones are the leaps from a black note to the next white note, up or down, except for:

* B to C
* C to B
* E to F
* F to E

##

### Examples

`'A, C' -> 4`

`'G, G#' -> 2`

`'F#, B' -> 6`

`'Bb, Bb' -> 13`

---

### Rules

* The largest distance between two notes is 13 semitones.
* The second inputted note will always be above the first inputted note.
* You can take input as either a string, or an array/list. If you take it as a string, the notes will be comma-separated (e.g. `String -> 'A, F'`, `Array -> ['A', 'F']`).
* You can assume that you will always be given two valid notes.
* Sharps will be denoted as `#` and flats will be denoted as `b`
* Your code must support enharmonic equivalents (e.g. It must support both F# and Gb)
* Your code does not need to support notes that are named with, but can be named without a sharp or flat (i.e. You do not need to support E#, or Cb). Bonus points if your code does support it though.
* Your code does not need to support double sharps or double flats.
* You can assume that if you get the both the same notes, or same pitch (e.g. 'Gb, Gb' or 'A#, Bb'), the second not will be exactly one octave above the first.
* This is code golf so the answer with the least amount of bytes wins.

# Answer
> 7 votes
# Python 2, 66 bytes

```
r=1
for s in input():r=cmp(s[1:]+s,s)-ord(s[0])*5/3-r
print-r%12+2

```

Try it online!

---

**Python 2, 68 bytes**

```
lambda s,t:13-(q(s)-q(t))%12
q=lambda s:ord(s[0])*5/3+cmp(s,s[1:]+s)

```

Try it online!

# Answer
> 7 votes
# JavaScript (ES6), 78 bytes

*Saved 1 byte thanks to @Neil*

Takes the notes in currying syntax `(a)(b)`.

```
a=>b=>((g=n=>'0x'+'_46280ab_91735'[parseInt(n+3,36)*2%37%14])(b)-g(a)+23)%12+2

```

### Test cases

```
let f =

a=>b=>((g=n=>'0x'+'_46280ab_91735'[parseInt(n+3,36)*2%37%14])(b)-g(a)+23)%12+2

console.log(f('A')('C'))   // 4
console.log(f('G')('G#'))  // 2
console.log(f('F#')('B'))  // 6
console.log(f('Bb')('Bb')) // 13
```

### Hash function

The purpose of the hash function is to convert a note into a pointer in a lookup table containing the semitone offsets (C = 0, C# = 1, ..., B = 11), stored in hexadecimal.

We first append a **'3'** to the note and parse the resulting string in base-36, leading to an integer **N**. Because **'#'** is an invalid character, it is simply ignored, along with any character following it.

Then we compute:

```
H(N) = ((N * 2) MOD 37) MOD 14

```

Below is a summary of the results.

```
 note | +'3' | parsed as | base 36->10 |   *2  | %37 | %14 | offset
------+------+-----------+-------------+-------+-----+-----+--------
  C   |  C3  |    c3     |         435 |   870 |  19 |   5 |  0x0
  C#  |  C#3 |    c      |          12 |    24 |  24 |  10 |  0x1
  Db  |  Db3 |    db3    |       17247 | 34494 |  10 |  10 |  0x1
  D   |  D3  |    d3     |         471 |   942 |  17 |   3 |  0x2
  D#  |  D#3 |    d      |          13 |    26 |  26 |  12 |  0x3
  Eb  |  Eb3 |    eb3    |       18543 | 37086 |  12 |  12 |  0x3
  E   |  E3  |    e3     |         507 |  1014 |  15 |   1 |  0x4
  F   |  F3  |    f3     |         543 |  1086 |  13 |  13 |  0x5
  F#  |  F#3 |    f      |          15 |    30 |  30 |   2 |  0x6
  Gb  |  Gb3 |    gb3    |       21135 | 42270 |  16 |   2 |  0x6
  G   |  G3  |    g3     |         579 |  1158 |  11 |  11 |  0x7
  G#  |  G#3 |    g      |          16 |    32 |  32 |   4 |  0x8
  Ab  |  Ab3 |    ab3    |       13359 | 26718 |   4 |   4 |  0x8
  A   |  A3  |    a3     |         363 |   726 |  23 |   9 |  0x9
  A#  |  A#3 |    a      |          10 |    20 |  20 |   6 |  0xa
  Bb  |  Bb3 |    bb3    |       14655 | 29310 |   6 |   6 |  0xa
  B   |  B3  |    b3     |         399 |   798 |  21 |   7 |  0xb

```

### About flats and sharps

Below is the proof that this hash function ensures that a note followed by a **'#'** gives the same result than the next note followed by a **'b'**. In this paragraph, we use the prefix **@** for base-36 quantities.

For instance, **Db** will be converted to **@db3** and **C#** will be converted to **@c** (see the previous paragraph). We want to prove that:

```
H(@db3) = H(@c)

```

Or in the general case, with **Y = X + 1**:

```
H(@Yb3) = H(@X)

```

*@b3* is *399* in decimal. Therefore:

```
H(@Yb3) =
@Yb3 * 2 % 37 % 14 =
(@Y * 36 * 36 + 399) * 2 % 37 % 14 =
((@X + 1) * 36 * 36 + 399) * 2 % 37 % 14 =
(@X * 1296 + 1695) * 2 % 37 % 14

```

*1296* is congruent to *1* modulo *37*, so this can be simplified as:

```
(@X + 1695) * 2 % 37 % 14 =
((@X * 2 % 37 % 14) + (1695 * 2 % 37 % 14)) % 37 % 14 =
((@X * 2 % 37) + 23) % 37 % 14 =
((@X * 2 % 37) + 37 - 14) % 37 % 14 =
@X * 2 % 37 % 14 =
H(@X)

```

A special case is the transition from **G#** to **Ab**, as we'd expect **Hb** in order to comply with the above formulae. However, this one also works because:

```
@ab3 * 2 % 37 % 14 = @hb3 * 2 % 37 % 14 = 4

```

# Answer
> 4 votes
# Perl, ~~39~~ 32 bytes

Includes `+1` for `p`

Give the start and end notes as two lines on STDIN

```
(echo "A"; echo "C") | perl -pe '$\=(/#/-/b/-$\+5/3*ord)%12+$.}{'; echo

```

Just the code:

```
$\=(/#/-/b/-$\+5/3*ord)%12+$.}{

```

# Answer
> 4 votes
# Japt, 27 bytes

```
®¬x!b"C#D EF G A"ÃrnJ uC +2

```

Test it online! Takes input as an array of two strings.

Also works for any amount of sharps or flats on any base note!

### Explanation

```
®¬x!b"C#D EF G A"ÃrnJ uC +2   Let's call the two semitones X and Y.
®                Ã            Map X and Y by
 ¬                              splitting each into characters,
  x                             then taking the sum of
   !b"C#D EF G A"               the 0-based index in this string of each char.
                                C -> 0, D -> 2, E -> 4, F -> 5, G -> 7, A -> 9.
                                # -> 1, adding 1 for each sharp in the note.
                                b -> -1, subtracting 1 for each flat in the note.
                                B also -> -1, which happens to be equivalent to 11 mod 12.
                                The sum will be -2 for Bb, 2 for D, 6 for F#, etc.
                              Now we have a list of the positions of the X and Y.
                  rnJ         Reduce this list with reversed subtraction, starting at -1.
                              This gets the difference Y - (X - (-1)), or (Y - X) - 1.
                      uC      Find the result modulo 12. This is 0 if the notes are 1
                              semitone apart, 11 if they're a full octave apart.
                         +2   Add 2 to the result.

```

# Answer
> 2 votes
# Perl 5 \+ `-p`, 66 bytes

```
s/,/)+0x/;y/B-G/013568/;s/#/+1/g;s/b/-1/g;$_=eval"(-(0x$_-1)%12+2"

```

Try it online!

Takes comma-separated values. Does also work for Cb, B#, E#, Fb and multiple #/b.

Explanation:

```
# input example: 'G,G#'
s/,/)+0x/; # replace separator with )+0x (0x for hex) => 'G)+0xG#'
y/B-G/013568/; # replace keys with numbers (A stays hex 10) => '8)+0x8#'
s/#/+1/g; s/b/-1/g; # replace accidentals with +1/-1 => '8)+0x8+1'
$_ = eval # evaluate => 2
    "(-(0x$_-1)%12+2" # add some math => '(-(0x8)+0x8+1-1)%12+2'

```

Explanation for eval:

```
(
    - (0x8) # subtract the first key => -8
    + 0x8 + 1 # add the second key => 1
    - 1 # subtract 1 => 0
) % 12 # mod 12 => 0
+ 2 # add 2 => 2
# I can't use % 12 + 1 because 12 (octave) % 12 + 1 = 1, which is not allowed

```

# Answer
> 2 votes
# Ruby, 56 bytes

```
->a{a.map!{|s|s.ord*5/3-s[-1].ord/32}
13-(a[0]-a[1])%12}

```

Try it online!

The letters are parsed according to their ASCII code times `5/3` as follows (this gives the required number of semitones plus an offset of 108)

```
A    B    C    D    E    F    G
108  110  111  113  115  116  118

```

The last character (`#`, `b` or the letter again) is parsed as its ASCII code divided by 32 as follows

```
# letter (natural) b
1  { --- 2 --- }   3

```

This is subtracted from the letter code.

Then the final result is returned as `13-(difference in semitones)%12`

# Answer
> 2 votes
# Stax, 25 24 bytes

```
╝─°U┤ƒXz☺=≡eA╕δ┴╬\¿☺zt┼§

```

Run and debug it online

The corresponding ascii representation of the same program is this.

```
{h9%H_H32/-c4>-c9>-mrE-v12%^^

```

Effectively, it calculates the keyboard index of each note using a formula, then calculates the resulting interval.

1. Start from the base note, A = 2, B = 4, ... G = 14
2. Calculate the accidental offset `2 - code / 32` where `code` is the ascii code of the last character.
3. Add them together.
4. If the result is \> 4, subtract 1 to remove B#.
5. If the result is \> 7, subtract 1 to remove E#.
6. Modularly subtract the two resulting note indexes, and add 1.

# Answer
> 1 votes
# Python 3, 95 bytes

```
lambda a,b:(g(b)+~g(a))%12+2
g=lambda q:[0,2,3,5,7,8,10][ord(q[0])-65]+" #".find(q.ljust(2)[1])

```

Try it online!

-14 bytes thanks to user71546

# Answer
> 1 votes
## Batch, ~~136~~ 135 bytes

```
@set/ac=0,d=2,e=4,f=5,g=7,a=9,r=24
@call:c %2
:c
@set s=%1
@set s=%s:b=-1%
@set/ar=%s:#=+1%-r
@if not "%2"=="" cmd/cset/a13-r%%12

```

Explanation: The substitutions in the `c` subroutine replace `#` in the note name with `+1` and `b` with `-1`. As this is case insensitive, `Bb` becomes `-1-1`. The variables for `C`...`A` (also case insensitive) are therefore chosen to be the appropriate number of semitones away from `B=-1`. The resulting string is then evaluated, and @xnor's trick of subtracting the result from the value gives the desired effect of subtracting the note values from each other. Edit: Finally I use @Arnauld's trick of subtracting the modulo from 13 to achieve the desired answer, saving 1 byte.

# Answer
> 1 votes
# Jelly, 28 bytes

```
O64_ṠH$2¦ḅ-AḤ’d5ḅ4µ€IḞṃ12FṪ‘

```

A monadic link accepting a list of two lists of characters and returning an integer.

**Try it online!** or see all possible cases.

### How?

Performs some bizarre arithmetic on the ordinals of the input characters to map the notes onto the integers zero to twelve and then performs a base-decompression as a proxy for modulo by twelve where zero is then replaced by 12 then adds one.

```
O64_ṠH$2¦ḅ-AḤ’d5ḅ4µ€IḞṃ12FṪ‘ - Main link, list of lists    e.g. [['F','#'],['B']]  ...or [['A','b'],['G','#']]
                  µ€         - for €ach note list          e.g.  ['F','#'] ['B']          ['A','b'] ['G','#']
O                            - { cast to ordinal (vectorises)    [70,35]   [66]           [65,98]   [71,35]
 64                          -   literal 64
   _                         -   subtract (vectorises)           [-6,29]   [-2]           [-1,-34]  [-7,29]
        ¦                    -   sparse application...
       2                     -   ...to indices: [2] (just index 2)
      $                      -   ...do: last two links as a monad:
    Ṡ                        -          sign                     [-6,1]    [-2]           [-1,-1]   [-7,1]
     H                       -          halve                    [-6,-0.5] [-2]           [-1,-0.5] [-7,0.5]
         ḅ-                  -   convert from base -1            5.5       -2             0.5       7.5
           A                 -   absolute value                  5.5       2              0.5       7.5
            Ḥ                -   double                          11.0      4              1.0       15.0
             ’               -   decrement                       10.0      3              0.0       14.0
              d5             -   divmod by 5                     [2.0,2.0] [0,3]          [0.0,0.0] [2.0,4.0]
                ḅ4           -   convert from base 4             10.0      3              0.0       12.0
                             - } -->                             [10.0,3]                 [0.0,12.0]
                    I        - incremental differences           [-7.0]                   [12.0]
                     Ḟ       - floor (vectorises)                [-7]                     [12]
                      ṃ12    - base decompress using [1-12]      [[5]]                    [[1,12]]
                         F   - flatten                           [5]                      [1,12]
                          Ṫ  - tail                              5                        12
                           ‘ - increment                         6                        13

```

---

### Also at 28 bytes...

A (not so direct) port of xnor's Python 2 answer...

```
O×5:3z60_Ṡ¥2¦60U1¦Fḅ-‘N%12+2

```

Try all possible cases

# Answer
> 0 votes
# CJam, 67 bytes

```
l',/~)@)@{ciW*50+_z/}_@\~@@~-@@{ci65- 2*_9>-_3>-}_@\~@@~12+\- 12%+)

```

Online interpreter: http://cjam.aditsu.net/

# Answer
> 0 votes
# Raku, 121 bytes

I write quite a lot of music in EDOs other than 12 so I implemented an option to choose a particular EDO.

```
{1+(round($^c*log2(3))*([-](map {m:P5/([A-G])(\#*)(b*)/;4613502.comb[$0.ord-65]+7*($1.comb-$2.comb)},($^b,$^a)))%$c||$c)}

```

No TIO link because TIO has an outdated Rakudo, so here are some examples:

```
f("A", "C", 12) # => 4
f("Bb", "Bb", 12) # => 13
f("F#", "B", 19) # => 9
f("G", "G#", 31) # => 3
f("C", "Dbb", 31) # => 2

```

---
Tags: code-golf, music
---


title: Decode Factor Trees

text:
# Question
Title: Decode Factor Trees
In case you missed Encode Factor Trees, here is the definition of a Factor Tree:

> * The empty string is 1.
> * Concatenation represents multiplication.
> * A number *n* enclosed in parentheses (or any paired characters) represents the *n*th prime number, with 2 being the first prime number.
>     + Note that this is done recursively: the *n*th prime is the factor tree for *n* in parentheses.
> * The factors of a number should be ordered from smallest to largest.
>
> For example, here are the factor trees for 2 through 10:
>
> ```
> ()
> (())
> ()()
> ((()))
> ()(())
> (()())
> ()()()
> (())(())
> ()((()))
>
> ```

This challenge uses a similar format; however, this challenge is to *decode* these structures.

# Test Cases

Shamelessly ~~stolen~~ *repurposed* from the last challenge.

In addition to the 9 above…

```
()()((()))((())) => 100
(()(()(()))) => 101
(()())(((())))(()(())) => 1001
(((((((()))))))) => 5381
(()())((((()))))(()()(())(())) => 32767
()()()()()()()()()()()()()()() => 32768

```

# Rules

* The paired characters in the input are your choice of parentheses, brackets, braces, or angle brackets. I may allow other formats (e.g. XML tags) if asked.
* You should be able to handle Factor Trees for any number from 2 to 215 or 32768.
* Since this is , the shortest answer in bytes wins.

# Answer
## Wolfram Language (Mathematica), ~~52~~ 45 bytes

```
ToExpression@*StringReplace[{"["->"Prime[1"}]

```

Try it online!

Input uses brackets.

Transforms the input into a Mathematica expression that computes the result. We do this simply by replacing `[` with `Prime[1`. This works because concatenation *is* multiplication in Mathematica.
> 10 votes

# Answer
# Prolog (SWI), ~~134~~ ~~128~~ ~~127~~ 124 bytes

*This answer is part of a collaboration between myself and 0'. We both worked on this together, the only reason I'm posting it is because I won Rock, Paper, Scissors.*

```
\Q-->{Q=1};"(",\N,")",\B,{findnsols(N,I,(between(2,inf,I),\+ (between(3,I,U),0=:=I mod(U-1))),L)->append(_,[Y],L),Q is Y*B}.

```

Try it online!

## Explanation

This answer is a perfect exemplar of what makes golfing in prolog fun.

---

This answer uses Prologs powerful system for definite clause grammars. Here is our grammar ungolfed a bit.

```
head(1)-->[].
head(Q)-->"(",head(N),")",head(B),{prime(N,Y),Q is Y*B}.
isprime(I):- \+ (between(3,I,U),0 =:= I mod(U-1)).
prime(N,Y):-
  findnsols(N,I,(
    between(2,inf,I),
    isprime(I)
  ),L),
  append(_,[Y],L),!.

```

The first construction rule is:

```
head(1)-->[].

```

This tells Prolog that the empty string corresponds to 1.

Our second rule of construction is a tiny bit more complex.

```
head(Q)-->"(",head(N),")",head(B),{prime(N,Y),Q is Y*B}.

```

This tells us that any non empty string contains parentheses around a clause with these same rules, to the right of a clause with these same rules.

It also tells us that the value of this clause (`Q`) follows the rule:

```
{prime(N,Y),Q is Y*B}

```

Breaking this down, `Q` is the product of 2 numbers `Y` and `B`. `B` is just the value of the clause to the left and `Y` is the `N`th prime where `N` is the value of the clause inside the parentheses.

This rule covers both of the formation rules of the factor tree

* Concatenation multiplies
* Enclosure takes the nth prime

---

Now for the predicate definitions. In the ungolfed version there are two predicates at play (in my actual code I've forward chained the predicates away). The two relevant predicates here are `isprime/1`, which matches a prime number, and `prime/2`, which, given `N` and `Y`, matches iff `Y` is the `N`th prime. First we have

```
isprime(I):- \+ (between(3,I,U),0 =:= I mod(U-1)).

```

This works of a pretty standard definition of primality, we insist that there is no number between 2 and `I`, including 2 but not `I` that divides `I`.

The next predicate is also pretty simple

```
prime(N,Y):-
  findnsols(N,I,(
    between(2,inf,I),
    isprime(I)
  ),L),
  append(_,[Y],L),!.

```

We use `findnsols` to find the first `N` numbers that are prime, we then return the last one. The trick here is that while `findnsols` is not guaranteed to find the *smallest* `N` primes, because of the way SWI handles `between` it will always find smaller primes sooner. This however means we have to cut to prevent it from finding more primes.

---

### The golfs

We can forward reason in our code twice. Since `isprime` is only used once its definition can be moved inside of `prime`. The next one is to move `prime` directly inside of the DCG, however since we use a cut in `prime` to prevent `findnsols` from producing too many primes we have a bit of an issue. The cut, cuts the entire DCG instead of just the bit we want. After a bit of documentation digging we found that `once/1` could be used to cut just this portion but not the entire DCG. However more documentation digging revealed that the `->` operator could also be used to perform a similar task. The `->` operator is roughly equivalent to `,!,` so we moved our cut to the other side of `append/3` and replaced it with `->`.

In SWI-Prolog predicates (and rules) can be give operators as names which allows us to drop the parentheses normally required. Thereby we can save 6 bytes by calling the rule `\`.
> 9 votes

# Answer
# Python 3, ~~125~~ 110 bytes

```
lambda s:eval(s.replace("]","1]*").replace("[","p[1*")+"1")
p=2,
k=P=1
while k<1e4:
 if P%k:p+=k,
 P*=k*k;k+=1

```

Try it online!

Uses xnor's implementation of the Wilson Theorem method to generate primes. Substitutes `()` with `[]`.
> 2 votes

# Answer
# JavaScript (ES6), 98 bytes

Inspired by notjagan's Python answer. Turns the input expression into a huge and ugly executable string.

```
s=>eval(s.split`)(`.join`)*(`.split`(`.join`(g=(n,k)=>(C=d=>n%--d?C(d):k-=d<2)(++n)?g(n,k):n)(1,`)

```

Merging the `C` and `g` functions into a single one may save some bytes, but it would require even more recursion.

### Test cases

```
let f =

s=>eval(s.split`)(`.join`)*(`.split`(`.join`(g=(n,k)=>(C=d=>n%--d?C(d):k-=d<2)(++n)?g(n,k):n)(1,`)

;[
  "()",                             // 2
  "(())",                           // 3
  "()()",                           // 4
  "((()))",                         // 5
  "()(())",                         // 6
  "(()())",                         // 7
  "()()()",                         // 8
  "(())(())",                       // 9
  "()((()))",                       // 10
  "()()((()))((()))",               // 100
  "(()(()(())))",                   // 101
  "(()())(((())))(()(()))",         // 1001
  "(((((((())))))))",               // 5381
  "(()())((((()))))(()()(())(()))", // 32767
  "()()()()()()()()()()()()()()()"  // 32768
]
.forEach(s => console.log(s, '-->', f(s)))
```
> 1 votes

# Answer
# Jelly, 15 bytes

```
OḂ;ṪÆN×ṪƲ1ṛ?¥ƒ1

```

Try it online!

```
OḂ                 Codepoints odd or even? ('(' -> 0, ')' -> 1)
             ƒ     Reduce starting from
              1    one (implicitly treated as a singleton list):
  ;         ¥       append:
        Ʋ ṛ?         if right argument (is parenthesis closing?):
   Ṫ                  pop last element from left argument,
    ÆN                get nth prime,
       Ṫ              pop the next last element
      ×               and multiply.
                     Else:
         1            1.

```

Essentially interprets a stack language where `(` means "push 1" and `)` means "pop n, multiply top of stack by n-th prime", starting with a stack containing a single 1, outputting the single remaining stack item at the end.
> 1 votes

# Answer
# Stax, ~~12~~ 11 bytes

```
ÄKWα╛⌠ï_☻!■

```

Run and debug it

-1 thanks to Razetime

Translation of my Jelly answer. I felt I ought to try this in a stack-based language. First choice was 05AB1E, but I couldn't quite figure out `i`...

```
O+k|e1{v|6*}?    Unpacked representation

O+               Prepend 1 to the input. (strings = codepoint lists, mostly)
  k              Reduce that array by the rest of the program:
   |e            Even? ('(' -> 0, ')' -> 1)
            ?    If so,
     1           push 1, else
      {    }     perform:
       v         decrement,
        |6       0-indexed nth prime,
          *      multiply.

```

The way Stax's reduce operates on the stack is by pushing the first element of the top of the stack, then for each remaining element pushing that and evaluating the block it closes (which is the entire program if there is no block to close). Unfortunately, there doesn't seem to be any alternative which skips the special treatment for the first element--preferably after performing `s`--but there is a builtin for "tuck 1 under top of stack", so it works out anyways.
> 1 votes

---
Tags: code-golf, number, primes, balanced-string
---


title: Type-check an expression

text:
# Question
Title: Type-check an expression
Given an infix expression, determine whether all constants are of the same type.

Operators will consist only of these **dyadic** operators: `+-/*`

Your program or function should take a valid expression string as input, and output a truthy value if the constants in the expression are of the same time, and a falsey value otherwise.

The expression will consist solely of constants, and may contain any of the following types:

* String, of the form `"String"` (Always double quotes, can be empty, no escape characters, may contain any ASCII text)
* Integer, of the form `14` (Always positive or zero)
* Float, of the form `7.3f` (Always positive or zero, always has a decimal component, eg `14.0f`)
* Byte, of the form `0x42` (`0-255`, Always 2 hexadecimal characters)
* Boolean, of the form `true` (`true` or `false`, case insensitive)

The expression will not contain parentheses, as order of operation doesn't affect type when no type coercion is present.

A lone constant with no operators is a valid expression.

An empty expression is not a valid expression.

You may assume that the expression string contains no whitespace outside of string literals.
*Note: Alternatively you may assume that there will always be spaces between constants and operators, as seen in the testcases. If you make this assumption, please specify as such in your answer*

You do not have to handle invalid expressions such as `1 +`.

# Scoring

This is , so fewest bytes wins!

# Test cases

*(Whitespace added for readability)*

```
2 + 3
True

"Hello" / "World"
True

true * false
True

"Hello" + 4
False

"Hello" + "4"
True

3 + 2.4f / 8
False

0xff * 0xff
True

0xff + 2
False

6
True

" " + ""
True

"4 + false" + "word"
True

```

# Answer
> 11 votes
# JavaScript (ES6),  ~~79 77~~  75 bytes

*Saved 2 bytes thanks to @ExpiredData*

Expects whitespace around operators. Returns a Boolean value.

```
s=>![/".*?"/g,/0x../g,/\S+f/g,/\d/,/e/i].filter(e=>s!=(s=s.split(e)+''))[1]

```

Try it online!

### How?

1. We remove all strings, using `/".*?"/g`
2. We remove all bytes, using `/0x../g`
3. We remove all floats, using `/\S+f/g`
4. We look for a remaining digit with `/\d/`; if we do find one, there must be at least one integer
5. We look for a remaining `"e"` or `"E"` with `/e/i`; if we do find one, there must be at least one Boolean value

All removed expressions are actually replaced with a comma, which is harmless.

We filter out the regular expressions causing no change to the input string and test whether less than two of them remain at the end of the process.

# Answer
> 3 votes
# Perl 5 `-p`, 73 bytes

```
for$f(qw/".*?" \d+.\d+f 0x.. ....?e \d+/){s/$f//gi&&last}$_=/^[+\/* -]*$/

```

Try it online!

**How?**

Attempt to remove strings, floats, hex, boolean, and integers, in that order. Stop as soon as something is removed. After stopping, check to see if the remaining string consists only of operators and whitespace. It if does, the trype check is true; if not, it's false.

**First attempt: Perl 5 `-MList::Util=all` `-p`, 99 bytes**

```
s/".*?"/!/g;for$f(qw/! \d+ \d+\.\d+f 0x[0-9a-f]{2} (true|false)/){$\||=all{/^$f$/i}/[^+\/* -]+/g}}{

```

Try it online!

# Answer
> 3 votes
# Jelly, ~~30~~ 23 bytes

```
ṣ”"ŒœḢYŒlḲŒœḢeþ@“.e¶x”E

```

Try it online!

A monadic link that takes a string as input and returns 1 for true and 0 for false (Jelly’s boolean values). Expects whitespace around operators.

I’ve added a few new test cases to the TIO including one with three operators and one with mixed case for booleans.

### Explanation

```
ṣ”"                     | Split input at double-quotes
   Œœ                   | Split into two lists, one of odd indices and one even. The even indices will have the contents of the quoted bits in the input (if any)
     Ḣ                  | Keep only the odd-indexed items
      Y                 | Join with newlines (so now all quoted strings in input are a single newline)
       Œl               | Convert to lower case (so that booleans are case insensitive)
         Ḳ              | Split at spaces
          ŒœḢ           | As before just take odd indices
             eþ@“.e¶x”  | Check for each section which they contain of .e¶x (respectively floats, booleans, strings and hex; integers will have none of these)
                      E | Check each section is equal (will return true for single section)

```

# Answer
> 1 votes
# C# (Visual C# Interactive Compiler), ~~113~~ ~~111~~ 109 bytes

```
n=>@""".*?"" 0x.. \S+f \d e|E".Split().Single(x=>n!=(n=System.Text.RegularExpressions.Regex.Replace(n,x,"")))

```

Port of Arnauld's javascript answer. Is 72 bytes with the flag `/u:System.Text.RegularExpressions.Regex`.

Try it online!

# Answer
> 1 votes
# 05AB1E, ~~50~~ 24 bytes

```
'"¡āÉÏ»lð¡āÉÏε".e
x"Så}Ë

```

-26 bytes by making a port of *@NickKennedy*'s Jelly answer, so make sure to upvote him!!

Expects input with spaces at the operands.

Try it online or verify all (plus some more) test cases.

**Explanation:**

```
'"¡         '# Split the (implicit) input-string by '"'
   āÉÏ       # Only keep all values at 0-based even indices
      »      # Join them by newlines
       l     # Converted to lowercase (for `true`/`false`)
ð¡           # Split by spaces (NOTE: `#` cannot be used here, since inputs without
             # operands wouldn't be wrapped inside a list)
  āÉÏ        # Keep all values at 0-based even indices again
     ε".e
     x"Så}   # Check for each item for each of [".","e","\n","x"] if it's in the item
          Ë  # Check if all inner lists are the same
             # (which is output implicitly as result)

```

# Answer
> 1 votes
# Japt `-!`, 36 bytes

```
`".*?" 0x.. %S+f %d e|E`¸è@UÀ(U=rXÃÉ

```

Try it

# Answer
> 0 votes
# Python 2, 102 bytes

```
import re
def f(s):
	m=map(eval,re.split('[*+-/]',s))
	return all(map(lambda t:type(t)==type(m[0]),m))

```

Try it online!

Not entirely sure how to represent some of these types in Python. For example, 0xff and 2 are both treated as integers. And 2.4f isn't a valid type in Python, I think. Capitalized True and False for testing Booleans.

Edit: Grammar

# Answer
> 0 votes
# Stax, 26 bytes

```
ïd"┬Z\¡►L!8$lm╗╕╤☻ú≡╝ò6Å>^

```

Run and debug it

This program expects spaces around the operators. In general, it works by applying a few transformations to the input such that the maximum character for each expression type is distinct.

Unpacked, ungolfed, and commented, it looks like this.

```
i           suppress automatic evaluation of input
'"/2::'s*   replace quoted strings with 's'
.\d'9R      replace all digits with '9'
.ez|t       replace 'e' with 'z'
j2::        split on spaces, and discard alternating groups (operators)
{|Mm        calculate the maximum character in each remaining group
:u          resulting array contains exactly one distinct value

```

Run this one

# Answer
> 0 votes
# Haskell, 140 Bytes

```
r(a:t)|a=='"'=a:r(tail$snd$span(/=a)t)|elem a"+-*/"=r t|0<1=a:r t
r n=n
f x|z<-[last$'i':(filter(`elem`t)"fex\"")|t<-words$r x]=all(==z!!0)z

```

# Answer
> 0 votes
# JavaScript: 69 bytes.

```
a=>{b=a.split(/\+|\-|\*|\//);return typeof eval(b[0])==typeof eval(b[1])}

```

## Remarks

* `eval` is a dangerous operation.
* I used bad JavaScript practices in the process, like implicit globals and auto-semicolons.

## Explanation

* `b = ...` sets the variable `b` to the array created by splitting `a` based on the dyadic operations
* `return ...` returns `true` if the types of the return values of `eval` match, `false` otherwise.

---
Tags: code-golf, string, decision-problem, parsing
---


title: It's Not 2015 Anymore!

text:
# Question
Title: It's Not 2015 Anymore!
## The Rules

* Each submission must be a full program or a function.
* The program must take all instances of the string `2015` from the input (1 string), replace it with `<s>2015</s>*` (with \<s\> or \<strike\>). At the end, if there has been at least one `2015` in the string, you must add a newline and this string: `*2016. I'm a year early!`
* The program must not write anything to STDERR.
* The input will not contain `<s>2015</s>` or `<strike>2015</strike>`.

Note that there must be an interpreter so the submission can be tested.
* Submissions are scored in *bytes*, in an appropriate (pre-existing) encoding, usually (but not necessarily) UTF-8. Some languages, like Folders, are a bit tricky to score - if in doubt, please ask on Meta.
* This is , so shortest code wins

## Examples

**Input:**

```
Hello! The date is 2015-12-24.
```

**Output:**

```
Hello! The date is ~~2015~~*-12-24.
*2016. I'm a year early!
```

**Input:**
```
foo bar baz quux
```

**Output:**

```
foo bar baz quux
```

**Input:**

```
12320151203205120151294201511271823
```

**Output:**

```
123~~2015~~*12032051~~2015~~*1294~~2015~~*11271823
*2016. I'm a year early!
```

**Input:**

```
 Hello. The year is 2015...
2015.5...
```

**Output:**

```
 Hello. The year is ~~2015~~*...
~~2015~~*.5...
*2016. I'm a year early!
```

## The Snippet

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

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

```

```
var QUESTION_ID=68372,OVERRIDE_USER=45162;function answersUrl(e){return"http://api.stackexchange.com/2.2/questions/"+QUESTION_ID+"/answers?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+ANSWER_FILTER}function commentUrl(e,s){return"http://api.stackexchange.com/2.2/answers/"+s.join(";")+"/comments?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+COMMENT_FILTER}function getAnswers(){jQuery.ajax({url:answersUrl(answer_page++),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){answers.push.apply(answers,e.items),answers_hash=[],answer_ids=[],e.items.forEach(function(e){e.comments=[];var s=+e.share_link.match(/\d+/);answer_ids.push(s),answers_hash[s]=e}),e.has_more||(more_answers=!1),comment_page=1,getComments()}})}function getComments(){jQuery.ajax({url:commentUrl(comment_page++,answer_ids),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){e.items.forEach(function(e){e.owner.user_id===OVERRIDE_USER&&answers_hash[e.post_id].comments.push(e)}),e.has_more?getComments():more_answers?getAnswers():process()}})}function getAuthorName(e){return e.owner.display_name}function process(){var e=[];answers.forEach(function(s){var r=s.body;s.comments.forEach(function(e){OVERRIDE_REG.test(e.body)&&(r="<h1>"+e.body.replace(OVERRIDE_REG,"")+"</h1>")});var a=r.match(SCORE_REG);a&&e.push({user:getAuthorName(s),size:+a[2],language:a[1],link:s.share_link})}),e.sort(function(e,s){var r=e.size,a=s.size;return r-a});var s={},r=1,a=null,n=1;e.forEach(function(e){e.size!=a&&(n=r),a=e.size,++r;var t=jQuery("#answer-template").html();t=t.replace("{{PLACE}}",n+".").replace("{{NAME}}",e.user).replace("{{LANGUAGE}}",e.language).replace("{{SIZE}}",e.size).replace("{{LINK}}",e.link),t=jQuery(t),jQuery("#answers").append(t);var o=e.language;/<a/.test(o)&&(o=jQuery(o).text()),s[o]=s[o]||{lang:e.language,user:e.user,size:e.size,link:e.link}});var t=[];for(var o in s)s.hasOwnProperty(o)&&t.push(s[o]);t.sort(function(e,s){return e.lang>s.lang?1:e.lang<s.lang?-1:0});for(var c=0;c<t.length;++c){var i=jQuery("#language-template").html(),o=t[c];i=i.replace("{{LANGUAGE}}",o.lang).replace("{{NAME}}",o.user).replace("{{SIZE}}",o.size).replace("{{LINK}}",o.link),i=jQuery(i),jQuery("#languages").append(i)}}var ANSWER_FILTER="!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe",COMMENT_FILTER="!)Q2B_A2kjfAiU78X(md6BoYk",answers=[],answers_hash,answer_ids,answer_page=1,more_answers=!0,comment_page;getAnswers();var SCORE_REG=/<h\d>\s*([^\n,]*[^\s,]),.*?([\d.]+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/,OVERRIDE_REG=/^Override\s*header:\s*/i;
```

```
body{text-align:left!important}#answer-list,#language-list{padding:10px;width:290px;float:left}table thead{font-weight:700}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="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><div id="language-list"> <h2>Winners 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><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
# Stax, 36 bytes

```
ç┼↕+∙n7↔Qq┼╩↓╣ÇÖú];ⁿX£╞bëi⌐ñ▼Z♀φ6╛(<

```

Run and debug it

Unpacked, ungolfed, and commented, it looks like this.

```
_               push all of standard input
2015X           push 2015 and store it in the x register
$/c             split string on "2015", and copy the result
"<s>`x</s>*"*P  join with "<s>2015</s>*" and print
D!C             stop executing if split resulted in more than 1 element
'*p             print "*" without newline
|Xp             increment x register and print without newline
                print unterminated compressed literal ". I'm a year early!"
`Q_RUWZ)O-C!

```

Run this one
> 0 votes

# Answer
# JavaScript ES6, ~~84 76~~ 75 bytes

```
s=>(q=s.replace(/2015/g,"<s>$&</s>*"))+(s<q?`
*2016. I'm a year early!`:"")

```

This is pretty well golfed for JavaScript imo.

---

This works by taking the input and replacing all instances of `2015` with `<s>$&</s>*` where `$&` is the value matched, but in this case, that's always `2015`. Then, if the input is different from `q`, it'll add the `*2016...` string, otherwise, It'll add a blank string (nothing).
> 13 votes

# Answer
# Ruby, 69 bytes

```
$><<gets.gsub(/2015/,'<s>\&</s>*')
puts"*2016. I'm a year early!"if$&

```
> 5 votes

# Answer
# Jolf, 60 bytes

Two parts, again.

```
oHρi"2015"+pd"s'$&'*"
oH                    set H
  ρi"2015"             to input string, replaced all 2015 with
           pd"s'$&'    $& crossed out. (pd is an apply tag function)
          +        *" append an asterisk

    v-- unprintable
+H|&?=Hi+S"*2016. I\'m a year early!'"
+H|&?=Hi                            '" add ↓ to H if H != i; otherwise add empty string ('")
        +S"*2016. I\'m a year early!'  a newline plus that string
                                       implicit printing

```

Try it here! Bonus points for actually crossing out the text and conforming to the output examples? :3
> 4 votes

# Answer
## Python, 97 bytes

```
a=raw_input();b=a.replace('2015','<s>2015</s>*');print a;
if a!=b:print"*2016. I'm a year early!"

```

This takes input from stdin, replaces any instances of 2015 with a strike, and prints the 2016 message if the two strings don't match.
> 3 votes

# Answer
## Mathematica, 98 bytes

```
a="2015";StringReplace[#,a->"<s>2015</s>*"]<>If[#~StringCount~a>0,"
*2016. I'm a year early!",""]&

```

Once again, Mathematica's string processing uses many bytes...
> 2 votes

# Answer
## Pyth, ~~52~~ ~~51~~ 50 bytes

```
I-
:z"2015""<s>2015</s>*"z." ytµbðï«»±é¢þnl¶Vû

```

Test Suite.
> 2 votes

# Answer
# , 49 chars / 93 bytes

```
a=ïę ḟ*ṁ,`<s>$&</s>*”)+(a≠ï?ɘƂ联Ӏఈ쁬Πā␎䁛␐줄쁰ꖈᲠ䉠耀#:⬯

```

`Try it here (Firefox only).`

Really straightforward. `a=ïę ḟ*ṁ,'<s>$&</s>*”)` nests all instances of 2015 (represented here as the result of 31\*65) in strikethrough tags. Then, append the last string ('compressed' here) accordingly.
> 2 votes

# Answer
# TeaScript, 59 bytes

```
(q=xg2015,"<s>$&</s>*"))+(x<q?`
*2016. I'm a year early!`:u

```

Try it online

## Explanation

```
(q=        // Assign `q` to...
   xg      // input.replace
     2015  // 2015 with.
     "..." // The string
)) +       // Add to..

(x<q?      // If the input is different from replacement
     "..." // Add string to the end
    :u     // Otherwise empty string

```
> 2 votes

# Answer
## Japt, 51 bytes

```
Y=Ur2015"<s>$&</s>*")¥U?U:Y+`
*2016. I'm a ye e§!

```

Try it online!
> 2 votes

# Answer
# 05AB1E, ~~42~~ 40 bytes

```
Ž7ç©åi®®"<s>ÿ</s>*".:®>“*ÿ. I'm€…‚Œ‰€!“»

```

Try it online!

*-2 thanks to Grimy*

## Explanation

```
Ž7ç©åi®®"<s>ÿ</s>*".:®>“*ÿ. I'm€…‚Œ‰€!“» Full Program
Ž7ç©                                     Pushes 2015 and copies it to the register
    å                                    Checks if 2015 occurs in the input
     i                                   If yes, do the following steps, else
                                          finish and output the input
      ®®"<s>ÿ</s>*"                      Pushes 2015 and "<s>2015</s>*"
                   .:                    Replaces all instances of 2015 by
                                          </s>2015</s> in the input
                     ®>“*ÿ. I'm€…‚Œ‰€!“  Push "*2016. I'm a year early!"
                                       » Concatenate both strings with a newline in between

```
> 2 votes

# Answer
# Arturo, ~~83~~ 79 bytes

```
$[s][r:replace s"2015""<s>2015</s>*"if r<>s['r++"\n*2016. I'm a year early!"]r]

```
> 2 votes

# Answer
## (f)lex, 104 bytes

File `2015.l`:

```
 int n=0;
%%
"2015" ++n+puts("<s>2015</s>*");
%%
main(){yylex();n&&puts( "*2016. I'm a year early!\n");}

```

...no trailing newline.

Build:

```
$ flex -o 2015.c 2015.l
$ gcc 2015.c -o 2015 -lfl

```

Run:

```
$ ./2015 <<<'Hello! The date is 2015-12-24.'
Hello! The date is <s>2015</s>*-12-24.
*2016. I'm a year early!
$ ./2015 <<<'foo bar baz quux'
foo bar baz quux
$ ./2015 <<<'12320151203205120151294201511271823'
123<s>2015</s>*12032051<s>2015</s>*1294<s>2015</s>*11271823
*2016. I'm a year early!

```

I ran this using `flex` and `gcc` on Debian8, but I see no reason why it should fail in other environments using `lex` and/or a different C compiler.
> 1 votes

# Answer
# C#, 152 bytes

```
class A{static void Main(string[]a){System.Console.Write(a[0].Replace("2015","<s>2015</s>*")+(a[0].Contains("2015")?"\n*2016. I'm a year early!":""));}}

```

Basic solution. Takes the string as the first argument.
> 1 votes

# Answer
# Gema, 57 bytes

```
2015=<s>$0</s>*@set{a;*2016. I'm a year early\!}
\Z=${a;}

```

Sample run:

```
bash-4.3$ gema -f not-2015.gema <<< 'Hello! The date is 2015-12-24.'
Hello! The date is <s>2015</s>*-12-24.
*2016. I'm a year early!

bash-4.3$ gema -f not-2015.gema <<< 'foo bar baz quux'
foo bar baz quux

bash-4.3$ gema -f not-2015.gema <<< '12320151203205120151294201511271823'
123<s>2015</s>*12032051<s>2015</s>*1294<s>2015</s>*11271823
*2016. I'm a year early!

```
> 1 votes

# Answer
# PowerShell, ~~81~~ 79 bytes

<sup>-2 bytes thanks to mazzy</sup>

```
param($n)($z=$n-replace2015,'<s>$&</s>*')+"
*2016. I'm a year early!"*($z-ne$n)

```

Try it online!

Just a replace on the input and a conditional append with the 2016 line. You don't need many quotes or spaces in PowerShell either.
> 1 votes

# Answer
# Retina, ~~49 45 64 61 60~~ 54 bytes

```
s`2015.+
$&¶*2016. I'm a year early!
\`2015
<s>$&</s>*

```

After numerous attempts I think this is the shortest Retina solution

---

The first line matches `2015`, the second line replaces the previous match (`2015`) with `<s>$&</s>*` where `$&` is the match's value or in this case, `2015`.

The `\` removes the trailing newline from the output. The ``` starts the regex. `$` matches the end specifying we're trying to add a string to the end. The last line simply adds the string where  becomes a newline. Retina uses the ISO-8859-1 encoding in which the  is one byte

Try it online
> 0 votes

# Answer
## ROOP, 110 bytes

```
 1I
 CW
 |%|
 V !
H
' "<s>2015</s>*"
2R !
0 #V
1 G #
5V #"\n*2016. I'm a year early!"
'| M #
 -V #

  #W
   O#

```

This uses the `R` operator to replace all occurrences of the string `2015` in the input to `<s>2015</s>*`.Then, there is a comparison -- if the input string and the new one are different, then 1 is returned. Otherwise, 0 is returned. Then, `M` repeats the string `\n*2016. I'm a year early` that many times, i.e. if there are no changes, the string is blank, otherwise, the string is `\n*2016. I'm a year early`. Then, the strings are printed and the program terminates.

Above there is a 1 which is moved to the left and then falls to the operator H, which ends the program.
> 0 votes

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

```
lambda x:(b:=x.replace('2015','<s>2015<s>*'))+"\n*2016. I'm a year early!"*(b>x)

```

Try it online!

*Saved 8 bytes thanks to squid*
> 0 votes

# Answer
# Perl 5 `-p`, 53 bytes

```
$\="\n*2016. I'm a year early!"if s|2015|<s>$&</s>*|g

```

Try it online!
> 0 votes

# Answer
# JavaScript: 62 bytes

```
x=>x.replace('2015','<s>2015</s>')+"\n*2016. I'm a year early!"

```
> 0 votes

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


title: CamelCase2snake_case()

text:
# Question
Title: CamelCase2snake_case()
Write a function to convert CamelCased text to snake\_case: `FunctionForHTMLManipulation` becomes `function_for_html_manipulation`

The input text will be a single suitable identifier in many languages. It must start with an English letter, then be followed by any number of English letters or digits. No other characters (spaces, symbols, etc.) are allowed.

Each "word" within the CamelCased text will start with a capital letter unless at the beginning of the text or immediately after a digit, and be followed by zero or more letters, all of the same case. Groups of digits will be considered as separate words but pass through unchanged.

In other words, a lowercase letter followed by an uppercase letter indicates a word break. Any letter and digit next to each other indicates a word break. An uppercase letter followed by another uppercase letter and a lowercase letter indicates a word break.

`...lU...` =\> `...l_u...`
`...l9...` =\> `...l_9...`
`...U9...` =\> `...u_9...`
`...9l...` =\> `...9_l...`
`...9U...` =\> `...9_u...`
`...UUl...` =\> `...u_ul...`

Both `Buy24Beers` and `buy24beers` become `buy_24_beers`.
`MacDonaldAndObrian` becomes `mac_donald_and_obrian`.
`MACDonaldAndOBrian` becomes `mac_donald_and_o_brian`.

# Answer
## Retina, ~~61~~ 37 bytes

```
r1>`[A-Z]?[a-z]+|[A-Z]+|\d+
_$&
T`L`l

```

Try it online! (Slightly modified to run a full test suite.)

### Explanation

Instead of finding word boundaries to insert underscores, we simply match each word and prepend a `_`. Matching words from the left is a bit annoying because of the `UUl` rule, but using .NET's right-to-left matching we can easily match words greedily. To avoid a leading `_`, we make use of Retina's limits.

```
r1>`[A-Z]?[a-z]+|[A-Z]+|\d+
_$&

```

The `r` activates right-to-left mode, the `1>` tells Retina to process everything except the first match (counting from left to right). Then there's four types of "words": `Ulll`, `lll`, `UUU`, `ddd`. These are easily matched with the given pattern. The substitution just writes a `_` followed by the word itself.

```
T`L`l

```

This simply turns upper case into lower case to complete the transformation.
> 9 votes

# Answer
# JavaScript (ES6), 79 bytes

```
s=>s.match(/[A-Z]+(?=[A-Z][a-z]|\d|$)|[A-Z]?[a-z]+|\d+/g).join`_`.toLowerCase()

```
> 6 votes

# Answer
## JavaScript (ES6), 89 bytes

```
s=>s.replace(/\d(?=\D)|\D(?=\d)|[a-z](?=[A-Z])|[A-Z](?=[A-Z][a-z])/g,"$&_").toLowerCase()

```
> 3 votes

# Answer
# Lua, 135 bytes

```
function snake(s)return s:gsub('%f[^%l]%u','_%1'):gsub('%f[^%a]%d','_%1'):gsub('%f[^%d]%a','_%1'):gsub('(%u)(%u%l)','%1_%2'):lower()end

```

Try it online!

This solution benefits from Lua's shorthand notation for C's character classes (lowercase `%l`, uppercase `%u`, alphabetic `%a`, digit `%d`), frontier notation (`%f[]`), and from the whole match being added as the implicit first capture in the absence of any other captures.
> 3 votes

# Answer
# Powershell, 77 bytes

*Based on Neil's answer.*

```
$args-creplace'\d(?=\D)|\D(?=\d)|[a-z](?=[A-Z])|.(?=[A-Z][a-z])','$&_'|% *wer

```

Less golfed test script:

```
$f = {

$args-creplace'\d(?=\D)|\D(?=\d)|[a-z](?=[A-Z])|.(?=[A-Z][a-z])','$&_'|% toLower

}

@(
    ,("Buy24Beers", "buy_24_beers")
    ,("buy24beers", "buy_24_beers")
    ,("MacDonaldAndObrian", "mac_donald_and_obrian")
    ,("MACDonaldAndOBrian", "mac_donald_and_o_brian")
    ,("BigD", "big_d")
) | % {
    $s,$expected = $_
    $result = &$f $s
    "$($result-ceq$expected): $result"
}

```

Output:

```
True: buy_24_beers
True: buy_24_beers
True: mac_donald_and_obrian
True: mac_donald_and_o_brian
True: big_d

```
> 2 votes

# Answer
# Retina, 62 bytes

Shamelessly translated from the JavaScript solution.

```
\d(?=\D)|\D(?=\d)|[a-z](?=[A-Z])|[A-Z](?=[A-Z][a-z])
$&_
T`L`l

```

Try it online!
> 1 votes

# Answer
# PowerShell, 68 92 bytes

Briefly deleted, +24 bytes for using the wrong RegEx.

```
($args-creplace'\d(?=\D)|\D(?=\d)|[a-z](?=[A-Z])|.(?=[A-Z][a-z])','$&_').Trim('_').ToLower()

```

Try it online!

Basically the same as the JavaScript solutions.
> 1 votes

# Answer
# Python 2, 82 bytes

```
lambda x:re.sub('(\d+|.([A-Z]*|[a-z]*)(?![a-z]))(?!$)','\\1_',x).lower()
import re

```

Try it online!
> 1 votes

# Answer
# Raku, 61 bytes

```
{S:g:P5/\d+|[A-Z]+(?=[A-Z]|\d)|[A-Z][a-z]*/{$/.lc~"_"}/.chop}

```

Try it online!
> 1 votes

# Answer
# Factor, 140 bytes

```
[ R/ [a-z][A-Z][a-z]/ [ dup from>> swap dup to>> swap seq>> subseq R/ [A-Z][a-z]/ [ "_" prepend ] re-replace-with ] re-replace-with >lower ]

```

Ungolfed:

```
: slice>subseq ( slice -- subseq )
dup from>> swap dup to>> swap seq>> subseq ;

: camel-case>snake-case ( string -- string' )
    R/ [a-z][A-Z][a-z]/ [
        slice>subseq R/ [A-Z][a-z]/
        [ "_" prepend ] re-replace-with
    ] re-replace-with >lower ;

```
> 0 votes

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


title: Vandalizing Marquees

text:
# Question
Title: Vandalizing Marquees
A marquee is a low-tech board that allows customizable letters. For example, here is a marquee:

```
SALE ON SNEAKERS

```

However, someone might come along and vandalize it by removing letters to send a different message:

```
S     N    AKE

```

Given two non-empty string inputs, an original message and a new message, determine whether the new message can be created by removing characters from the original message. Spaces left by removal can be compressed, as above, or left in, as in `the` becoming `t e` by removing the `h`. Both messages will only contain letters and spaces, case is up to you.

# Test Cases

```
"the", "the" -> true
"the", "t e" -> true
"the", "te" -> true
"te", "t e" -> false
"then i walked", "the" -> true
"then i walked", "niald" -> true
"abcde", "abj" -> false
"a b c d e", "abcde" -> true
"y today", "yt" -> true
"sale on sneakers", "snake" -> true
"today", "toad" -> false
"today", "tyy" -> false
"the sale on sneakers", "t e snake" -> true
"this is a sign", "th s i  a s  n" -> true
"the sale on sneakers", "the salon sneakers" -> true
"the sale on sneakers", "the sal  on sneakers" -> true
"a   b   c", "abc" -> true
"a   bc", "a  b  c" -> false
"a   b   c", "a       c" -> true
"a   b   c", "a        c" -> false
"the", " the" -> false
"the", " h " -> true
"the", "h" -> true

```

# Answer
> 12 votes
# Brachylog, 7 bytes

```
{|∧Ṣ}ᵐ⊇

```

Try it online!

I should not be surprised to learn that it's considerably faster if I put the  at the end. Takes the original marquee through the input and the target through the output.

```
{   }ᵐ     The input variable, with each element
 |         possibly
  ∧Ṣ       replaced by a space,
      ⊇    has the output variable as a subsequence.

```

Can also go the other way around, for another two bytes: `{|Ṣ∧l₁}ᵐ⊆`

# Answer
> 8 votes
# , 25 bytes

```
rxin~[:,'.*',"#:rplc&' .'

```

Try it online!

*Note: TIO link not working because it's an older version of J, but this works locally for me on J901*

* `rxin~ ...` The whole verb is dyadic J hook, asking if the right argument, after being transformed by the `...` phrase, is a regex match in the left argument.
* `rplc&' .'` The transformation of the right arg (the leftover marquee letters) first replaces all spaces with a `.`, since a space has to match something.
* `[:,'.*',"#:` This phrase simply inserts `.*` between each of the letters, so that we match "removed and collapsed letters" too. It works by zipping `,.` the string `'.*'` with each character of the right arg, and then flattening the result `[:,`.

# Answer
> 7 votes
# Python 3.8, ~~50~~ 46 bytes

```
lambda a,b:''in[b:=b[b[:1]in' '+c:]for c in a]

```

Try it online!

The code is simply a modification of @xnor's answer to a similar challenge: Is string X a subsequence of string Y?

# Answer
> 6 votes
# Scala, 54 bytes

```
_./:(Set(""))(for(p<-_;c=_;q<-Seq(""," ",c))yield p+q)

```

Try it online! (The output says `true` when a test passes, it prints `false` and throws an exception otherwise).

Times out for the later inputs, but appears to work otherwise.

Input is curried. First it takes the original message, and returns a `Set[String]` containing possible messages. However, the `Set` also acts like a `String => Boolean`, so it accepts the new message as its second input.

```
_./:(        //Fold over original message
  Set("")    //Accumulator will eventually hold all possible messages
)(           //Cartesian-product-ish for comprehension
  for(
    p <- _   //For every possible message p already in the accumulator
    c = _    //Current character
    q <- Seq( //Sequence of possible cases:
      "",     //Delete the character, don't keep a space
      " ",    //Delete the character, leave a space
      c       //Keep the character
    )
  ) yield p + q //Add each case q to p
)

```

# Answer
> 5 votes
# Wolfram Language (Mathematica), ~~26~~ 23 bytes

```
FreeQ[#|" "|___?h&/@#]&

```

Try it online!

Input two lists of characters, curried, as `f[original][new]`. Returns `False` if the target can be reached, and `True` if it cannot.

Quite slow.

Normally `___` matches any sequence of zero or more elements. When subject to `?` (`PatternTest`), it only matches if the test yields `True` for all elements of the sequence; since the test `h` is undefined, this only occurs when the sequence is empty.

```
                  /@#   (* if each letter of the original message*)
      #|" "|___?h&      (*  is still present, changed to a space, or missing *)
FreeQ[               ]& (* check that this does not describe the new message *)

```

# Answer
> 5 votes
# Haskell, 43 bytes

```
(a:b)!(c:d)=b!([c|a/=c,c>' ']++d)
_!y=y==[]

```

Try it online!

This is just a modified version of the Levenshtein distance calculation. Instead of normal edits our permitted edits are:

* Remove a character from string \\$a\\$
* Replace a character from string \\$a\\$ with space.

I use one clever-ish trick. Because two cases only differ by whether the head is maintained, we can use a list comprehension to create the two cases in situ.

So

```
(a:b)!(c:d)|a/=c&&c>' '=b!(c:d)|1>0=b!d

```

(this could be shorter anyway but I've structured it like this for illustrative purposes)

becomes

```
(a:b)!(c:d)=b!([c|a/=c,c>' ']++d)

```

# Answer
> 4 votes
# Perl 5 `-pl`, 26 bytes

```
y/ /./;s//.*/g;$_=<>=~/$_/

```

Try it online!

Takes the new resulting message first, followed by the original message, on separate lines.

# Answer
> 4 votes
# K (ngn/k), 26 bytes

-3 bytes by converting to tacit form

```
{(1_t_x;!0)@^t:(x?y)*~^y}/

```

Try it online!

Returns `!0` if the marquee can't be vandalized, and some sort of string if it can be. To better standardize the output, `~(!0)~` can be inserted at the start of the function, i.e. `{~(!0)~x{(1_t_x;!0)@^t:(x?y)*~^y}/y}`.

* `{...}/` use a reduction, seeded with the original marquee text, running over the text to test
* `~^y` check if the current character in the input to test is not `" "`. (`" "` is the null character, so we can test this by using `~^`, i.e. not null)
* `*` multiply this by...
* `(x?y)` the index of the first match in the (remaining) marquee text. This will return `0N` (also a null) if the character is not present. `0N*1` remains `0N`, whereas `0N*0` results in `0`.
* `t:` store this in variable `t`
* `(...)@^t` index into the list, using whether or not `t` is null. If it is null, the second item will be selected. If it is not null, it'll be the first item.
* `(1_t_x;!0)` `!0` here is a sentinel value, used to indicate that the test text is invalid (because it contains at least one invalid character, or is too long, etc etc.). `t_x` drops `t` characters from the beginning of the (remaining) marquee text. To make sure the modified test text lines up, we always want to remove at least one character, hence the `1_`.

# Answer
> 4 votes
# C (gcc), ~~55~~ 51 bytes

```
f(char*a,char*b){for(;*a;)*a++-*b&*b-32||b++;b=*b;}

```

Try it online!

-Saved 4 thanks to @Davide

* Output 0 if can be vandalized, truth if not.
* we iterate Marquee(a) until end of one of the two inputs : we increment result(b) if current letters are equal or if we need a space. Finally we return \*b which is \0 if compatible

# Answer
> 4 votes
# Jelly, 20 19 bytes

```
ßḢxn⁶anʋ¥@Ḣ};ʋɗṆ}ȧ?

```

Try it online!

Dyadic link that takes the original string as the left argument and the new string as the right argument. Uses something similar to @WheatWizerd's modified Levenstein algorithm, so it's very fast, unlike a brute force solution.

## Explanation

I admit this explanation is more confusing that the code itself.

```
ßḢxn⁶¥anʋ@Ḣ};ʋɗṆ}ȧ?   Main dyadic link
                  ?   If
                 ȧ    both strings are non-empty
              ɗ       then (
ß                       Recursively apply this link to the left string
             ʋ          and to (
 Ḣ                        First character of the left string, removing it from the string
          Ḣ}              First character of the right string, removing it from the string
        ¥                 Apply this dyad to them
         @                in reverse (
  x                         Repeat the left character
       ʋ                    this many times (
   n⁶                         Is the left character not a space?
     a                        And
      n                       are the characters not equal?
       ʋ                    )
        ¥                 )
            ;             Join the result with the right string
             ʋ          )
              ɗ       )
               Ṇ}     else return the logical negation of the right string

```

# Answer
> 3 votes
# Python 3, ~~79~~ \\$\cdots\\$ ~~73~~ 70 bytes

Saved a byte thanks to Jonah!!!
Saved 3 bytes thanks to dingledooper!!!
Saved 2 bytes thanks to caird coinheringaahing!!!
Saved 3 bytes thanks to Arnauld!!!

```
lambda m,v:match(sub(*' .',sub('(^|\S)',r'\1.*',v)),m)
from re import*

```

Try it online!

Returns a truthy value if the new message can be created by removing characters from the original message or `None` otherwise.

# Answer
> 3 votes
# Retina, 24 bytes

```
~(0G`
.
[ $&]?
^
$¶
$
$$

```

Try it online! Takes newline-separated input, but link includes test suite that converts from comma-separated input on newline-separated test cases. Explanation:

```
~(`

```

Interpret the output of the rest of the program as a program (specifically a Count stage) and execute that on the original input.

```
0G`

```

Keep the original marquee.

```
.
[ $&]?

```

Replace each character with an optional character class of itself or space.

```
^
$¶
$
$$

```

Anchor the list of character classes to ensure that the match starts at the beginning of the vandalised marquee and ends at the end of the input.

# Answer
> 3 votes
# Python 3, 69 89 86 bytes

```
def p(s,v,a=1):
 for c in v:_,x,s=s.partition(c);a*=c==x;s=(s," "+s)[x!=" "]
 return a

```

Try it online!

*Dropped to 86 thanks to Danis*

I haven't posted just a function before, but I think that's allowed for this one from reading the description? This returns `1|0` not `True|False` so I'll have to add a few more bytes if that's a requirement.

It just relies on the `partition` call to throw away characters from the front of the original string. And if the next character in the "vandalized" string isn't found the `a*=c==x` statement zeros out the accumulated answer.

Sadly... I missed the rule that when a character is replaced, it can match a blank the comes after it in the "vandalized" string. Accommodating that added more code.

# Answer
> 3 votes
# Ruby, 38 bytes

```
->o,s{o[/#{s.tr(" ",?.).chars*".*"}/]}

```

Try it online!

Outputs a string for truthy values, otherwise `nil` for falsey.

# Answer
> 3 votes
# Charcoal, 24 bytes

```
≔⪪⮌Ｓ¹θＵＭＳ∧∧θ№⁺ ι§θ±¹⊟θ¬θ

```

Try it online! Link is to verbose version of code. Takes input as the new and original messages and outputs a Charcoal boolean, i.e. `-` if the transformation is possible, nothing if not. Inspired by my answer to Speed of Lobsters. Explanation:

```
≔⪪⮌Ｓ¹θ

```

Get the new message and reverse it and split it into characters (so we can pop from the list).

```
ＵＭＳ∧∧θ№⁺ ι§θ±¹⊟θ

```

Loop over the original message, and pop the next character from the new message if it is a space or the next character from the original message.

```
¬θ

```

Check whether the list is now empty.

# Answer
> 2 votes
# Bash \+ coreutils, ~~53~~ 51 bytes

```
grep -q `sed -E 's/ /./g;s/(.)/.*\1.*/g'<<<$2`<<<$1

```

Try it online!

Rough port of Jonah's J answer using regex, I am sure there is a better way.

Takes two strings as arguments in the order of the test cases.

Exit code is 0 for a match, 1 for a mismatch.

# Answer
> 1 votes
# , ~~105~~ 104 bytes

```
function(a,b){for(x in el(strsplit(gsub(" ",".",b),""))){c=sub(paste0(".*?",x),"",a);if(a==c)T=F;a=c};T}

```

Try it online!

# Answer
> 1 votes
# 05AB1E, ~~22~~ 14 bytes

```
v¬DyQsðQ~i¦]õQ

```

First input is the original message, second input the new message.

Modification of my 05AB1E answer for the *Speed of Lobsters* challenge (thanks *@Neil* for the tip, resulting in -8 bytes).

Try it online or verify a few more test cases.

**Explanation:**

```
v            # Loop over the characters `y` of the (implicit) input original_message:
 ¬           #  Get the first character without popping the string
             #  (which uses the implicit input new_message the first iteration)
  D          #  Duplicate this first character
         i   #  If
   yQ        #  this first character is equal to the current character `y`
        ~    #  OR
     sðQ     #  this first character is a space:
          ¦  #   Remove this first character from the new_message
]            # Close both the if-statement and loop
 õQ          # And check if the new_message is now empty
             # (after which the result is output implicitly)

```

# Answer
> 1 votes
# Raku, 62 bytes

```
->\a,\b {a~~/<{join ".*",map {" "eq$_??"."!!"'$_'"},b.comb}>/}

```

Try it online!

---
Tags: code-golf, string, decision-problem, subsequence
---


title: Close(st) Binary Boxes

text:
# Question
Title: Close(st) Binary Boxes
## Challenge:

Given a list of non-negative integers, determine by how much you should increase each item to create the closest binary box with the resulting integer-list.

**What is a binary box?**

A binary box is where the first and last rows consists of `1`-bits; the first and last columns consist of `1`-bits; and everything else (if applicable) consists of `0`-bits. Some examples of binary boxes, with their corresponding integer-list below it:

```
                                             111
              1111                           101                           1111111
      111     1001        11      11111      101                           1000001
11    101     1001        11      10001      101         1111111           1000001
11    111     1111        11      11111      111         1111111   1   11  1111111

[3,3] [7,5,7] [15,9,9,15] [3,3,3] [31,17,31] [7,5,5,5,7] [255,255] [1] [3] [127,65,65,127]

```

**Example I/O:**

* If the input is `[0,2]`, the output would be `[3,1]`, because `[3,3]` is the closest binary box to reach by increasing numbers: `[0+3,2+1]`.
* If the input is `[3,4,1]`, the output would be `[4,1,6]`, because `[7,5,7]` is the closest binary box to reach by increasing numbers: `[3+4,4+1,1+6]`.
* If the input is `[2]`, the output would be `[1]`, because `[3]` is the closest binary box to reach by increasing numbers: `[2+1]`.

## Challenge rules:

* The goal is to find the closest binary box. If the input is `[1,2,3]` the output should be `[2,1,0]`; so `[62,31,60]` wouldn't be allowed as output, even though it does form a binary box as well.
* I/O can be taken in any reasonable format. Can be a list/array/stream of integers; read one by one from STDIN; etc. **You are not allowed to take the input-integers as binary-strings.**
* The input-integers are guaranteed to be non-negative; and the output-integers may not be negative.
* If the input is already a binary-box of itself, you can choose to output a corresponding list of 0s, or the result for the next binary-box in line. I.e. input `[3,3,3]` may result in both `[0,0,0]` or `[4,2,4]`.

The first/last rows of the binary-boxes with binary `111...111` form the OEIS sequences A000042 (literal) and A000225: \\$a(n)=2^n-1\\$ (as base-10 integers).
The middle rows of the binary-boxes with binary `100...001` form the OEIS sequences A000533 (literal) and A083318: \\$a(n)=2^n+1\\$ (as base-10 integers).

## General rules:

* This is , so shortest answer in bytes wins.
Don't let code-golf languages discourage you from posting answers with non-codegolfing languages. Try to come up with an as short as possible answer for 'any' programming language.
* Standard rules apply for your answer with default I/O rules, so you are allowed to use STDIN/STDOUT, functions/method with the proper parameters and return-type, full programs. Your call.
* Default Loopholes are forbidden.
* If possible, please add a link with a test for your code (i.e. TIO).
* Also, adding an explanation for your answer is highly recommended.

## Test cases:

```
Input:  [0,2]
Output: [3,1]

Input:  [3,4,1]
Output: [4,1,6]

Input:  [2]
Output: [1]

Input:  [3,3,3]
Output: [0,0,0] OR [4,2,4]

Input:  [1,27,40]
Output: [62,6,23]

Input:  [7,20,6,44,14]
Output: [120,45,59,21,113]

Input:  [7,20,6,33,14]
Output: [56,13,27,0,49]

Input:  [7,2,6,3,14]
Output: [8,7,3,6,1]

Input:  [1,0,1]
Output: [0,1,0]

Input:  [1,2,3]
Output: [2,1,0]

Input:  [0]
Output: [1]

Input:  [6,6,6]
Output: [9,3,9]

```

# Answer
> 3 votes
# 05AB1E, ~~25~~ ~~21~~ 18 bytes

-4 bytes thanks to Kevin Cruijssen!

```
[NoD<Id¦¦s.ø~I-Wd#

```

Try it online! or Try all cases!

**Commented**:

```
[                    # infinite loop, for N=0,1, ...
 No                  # push 2**N
   D                 # duplicate this value
    <                # decrement
     Id              # push a list of 1's in the same length as the input
       ¦¦            # remove the first 2 elements
         s           # swap to 2**N-1
          .ø         # surround the list of 1's to get a new list of the same length as the input
                     #  => [2**N-1, 1, ..., 1, 2**N-1]
            ~        # bitwise OR with 2**N, this is now the binary grid of width N+1
                     #  => [2**n|2**N-1, 2**N|1, ..., 2**N|1, 2**N|2**N-1]
             I-      # subtract the input list element-wise from the binary grid
               W     # take the minimum without popping the list
                d    # if this is non-negative
                 #   # break the infinite loop and implicitly print the list

```

# Answer
> 5 votes
# APL (Dyalog Extended), <sup>~~47 46~~</sup> 48 bytes

```
{x←0⋄⍵{x≡|x⊢←⍺-⍨⊥(1@1)∘⌽∘⍉⍣4⊢0×⍵:x⋄⍺∇⍵⍪0}⊤⍵+~×⍵}

```

Try it online!

A dfn which takes a vector as its right argument.

Outputs a list of 0's if the input is already a binary-box.

+2 bytes after a fix.(Thanks, Arnauld)

## Explanation

```
{x←0⋄⍵{x≡|x⊢←⍺-⍨⊥(1@1)∘⌽∘⍉⍣4⊢0×⍵:x⋄⍺∇⍵⍪0}⊤⍵+~×⍵}
 x←0                                             set var x to 0(required for extended)
      {x≡|x⊢←⍺-⍨⊥(1@1)∘⌽∘⍉⍣4⊢0×⍵:x⋄⍺∇⍵⍪0}        call the following recursive function with
                                          ⍵+~×⍵  add !(signum(input)) to itself
                                                 (special casing for [0])
                                         ⊤       converted to binary matrix
     ⍵                                           and the input list as right arg
                                :                If:
                             0×⍵                 the matrix converted to zeroes
                 (1@1)∘⌽∘⍉⍣4⊢                    with 1s added on each side
                ⊥                                convert from binary
             ⍺-⍨                                 subtract from the input
          x⊢←                                    assign to x
       x≡|                                       if x matches its absolute value
                                 x               then return x
                                  ⋄⍺∇⍵⍪0         otherwise add a row of zeroes, and try again

```

# Answer
> 3 votes
# JavaScript (ES6),  ~~72~~  71 bytes

Outputs a list of 0's if the input is already a binary-box.

```
a=>(g=k=>/-/.test(b=a.map((v,i)=>(i/a[i+1]?k^k/2|1:k)-v))?g(k-~k):b)(1)

```

Try it online!

### Commented

```
a =>                   // a[] = input array
(g = k =>              // g is a recursive function taking a bit mask k
                       // of the form (2 ** n) - 1
  /-/.test(            // test whether there is a minus side in the ...
    b = a.map(         //   ... array b[] defined as the result of this map()
      (v, i) =>        //   for each value v at position i in a[]:
      ( i / a[i + 1] ? //     if this is neither the first nor the last item
                       //     (i.e. i is not equal to 0 and a[i + 1] is defined):
          k ^ k / 2    //       use the vertical borders
          | 1          //       e.g. (0b111111 XOR (0b111111 >> 1)) OR 1 = 0b100001
        :              //     else:
          k            //       use the horizontal border (i.e. the full bit mask k)
      ) - v            //     subtract v
    )                  //   end of map()
  )                    // end of test()
  ?                    // if there's a minus sign:
    g(k - ~k)          //   try again with 2 * k + 1
  :                    // else:
    b                  //   success: return b[]
)(1)                   // initial call to g with k = 1

```

# Answer
> 3 votes
# Python 3.8, 95 bytes

```
f=lambda s,n=1:(b:=[x-y for x,y in zip(([n|n-1]+[n|1]*(len(s)-2))*2,s)])*(min(b)>=0)or f(s,n*2)

```

Try it online!

**Commented**:

```
f=lambda s,n=1:           # f is a recursive function taking two arguments:
                          # a list of integers: s, and the current power of 2: n
                          # it tries all binary boxes with the correct number of rows
                          # until it finds one where all row numbers are >= the values in s

     (b:= ... )           # construct a list of differences between row numbers and s
   * (min(b)>=0)          # if there is no negative value in this list, return it
  or f(s,n*2)             # otherwise try the next power of 2

[x-y for x,y in zip(...,s)])] # take the differences of each pair of row numbers and integers in s

 [n|n-1]                  # the first and last row are equal to n|n-1;
                          # example: n=8, n|n-1 = 8|7 = 0b1000|0b0111 = 0b1111 = 15
+[n|1]*(len(s)-2)         # the middle rows are n|1
                          # example: n=8, n|1 = 8|1 = 0b1000|0b0001 = 0b1001 = 9
 (...)*2                  # repeat this list twice to get the first row twice,
                          # zip will ignore all extra elements

```

# Answer
> 2 votes
# Charcoal, ~~39~~ 37 bytes

```
≔¹ζ≔⁻¹θηＷ‹⌊η⁰«≦⊗ζ≔Ｅθ⁻⎇﹪λ⊖Ｌθ⊕ζ⊖⊗ζκη»Ｉη

```

Try it online! Link is to verbose version of code. Explanation: I tried directly calculating the correct box size, but there were too many edge cases.

```
≔¹ζ

```

Start with a box of width 1.

```
≔⁻¹θη

```

See whether this box can hold the input.

```
Ｗ‹⌊η⁰«

```

Repeat until a large enough box is found.

```
≦⊗ζ

```

Increase the size of the box.

```
≔Ｅθ⁻⎇﹪λ⊖Ｌθ⊕ζ⊖⊗ζκη

```

Calculate the box and subtract the original input.

```
»Ｉη

```

Output the final increments.

# Answer
> 1 votes
## Python 3.8+, 91 bytes

```
f=lambda b,n=1:f(b,n*2)if min(u:=r_[(t:=2*n-1),b[2:]*0+n|1,t]-b)<0else u
from numpy import*

```

The parameter `b` must be a numpy array of integers.

Therefore, no try it online.

Recurse with `n` take values `1, 2, 4, 8,...`, and construct the array

```
r_[
(t:=2*n-1),  #first line
b[2:]*0+n|1, #middle lines, all values are n|1, length=len(b[2:])
t            #last line, same as first line
]

```

being the binary boxes, then return the first one that is no smaller than `b`.

# Answer
> 1 votes
# 05AB1E, ~~25~~ ~~31~~ ~~25~~ 26 bytes

+6 for bug fix for input \[1,0,1\]

-6 thanks to Kevin Cruijssen

+1 for bug fix for single-element lists

```
d¸∞εoIg<и¨>y>o<.ø}«.ΔI@P}α

```

Try it online! or Try all cases

# Answer
> 1 votes
# C (gcc), ~~181~~ ~~175~~ 166 bytes

-6 bytes thanks to Kevin Cruijssen
-9 bytes thanks to ceilingcat

```
i,j,m;f(n,l)int*n;{for(i=m=0;i<l;i++)if(m<n[i])for(j=1;(j*=2)<(m=n[i]););for(i=0,m-2&&(j/=2);++i<l-1;)n[i]>j+1?j*=2:0;for(i=l;i--;)n[i]=j-n[i]+(!i|i==l-1|m<4?j-1:1);}

```

Try it online!

---
Tags: code-golf, number, integer, binary
---