# Question
Title: What did I just play? Translate guitar fingerings to chords
Related: Music: what's in this chord?, Notes to Tablature, Generating guitar tabs?, Translate number pairs to guitar notes

Given a guitar fingering, output the chord it represents. You can use standard input and output, or write a function that returns a string.

The input fingerings will be classifiable as one of the following chords, to be expressed as follows (if the root note were C):

* major triad: `C`
* minor triad: `Cm`
* (dominant) seventh: `C7`
* minor seventh: `Cm7`

The chord might be inverted, so you can't rely on the lowest note being the root. Nor can you rely on this being an easy or common fingering in the real world. More generally, your program's output must ignore the octaves of the pitches, and treat all pitches that correspond to the same musical note (i.e., `A`) as equal.

This is , so the shortest code in bytes wins.

# Input format

The input is a series of 6 values that indicate, for each string of a 6-string guitar in standard tuning (E A D G B E), which fret that string will be played at. It could also indicate that the string is not played at all. The "zeroth" fret is also known as the open position, and fret numbers count up from there. Assume the guitar has 21 fret positions, such that the highest fret position is number 20.

For example, the input `X 3 2 0 1 0` means placing ones fingers at the following positions at the top of the guitar's neck:

```
(6th) |---|---|---|---|---
      |-X-|---|---|---|---
      |---|---|---|---|---
      |---|-X-|---|---|---
      |---|---|-X-|---|---
(1st) |---|---|---|---|---

```

and strumming the 2nd through the 6th strings. It corresponds to this ASCII tab:

```
e |-0-|
B |-1-|
G |-0-|
D |-2-|
A |-3-|
E |---|

```

You have some flexibility in choosing the kind of input you want: each fret position can be expressed as a string, or a number. Guitar strings that are not played are commonly indicated with an `X`, but you can choose a different sentinel value if that makes it easier for you (such as `-1` if you're using numbers). The series of 6 fret positions can be input as any list, array, or sequence type, a single space-separated string, or as standard input—once again, your choice.

You can rely on the input corresponding to one of the 4 chord types mentioned above.

Please explain in your post what form of input your solution takes.

# Output format

You must either return or print to standard output a string describing the chord the fingering is for. This string is composed of two parts concatenated together. Capitalization matters. Trailing whitespace is allowed.

The first part indicates the root note, one of `A`, `A#`/`Bb`, `B`, `C`, `C#`/`Db`, `D`, `D#`/`Eb`, `E`, `F`, `F#`/`Gb`, `G`, or `G#`/`Ab`. (I'm using `#` instead of , and `b` instead of , to avoid requiring Unicode.) Root notes that can be expressed without a sharp or flat must be expressed without them (never output `B#`, `Fb`, or `Dbb`); those that cannot must be expressed with a single sharp or flat symbol (i.e. either `C#` or `Db`, but never `B##`). In other words, you must minimize the number of accidentals (sharps or flats) in the note's name.

The second part indicates the type of chord, either empty for a major triad, `m` for a minor triad, `7` for the dominant seventh, or `m7` for the minor seventh. So a G major is output simply as `G`, while a D♯ minor seventh could be output as either `D#m7` or `Ebm7`. More examples can be found in the test cases at the end.

# Theory & hints

## Musical notes

The chromatic scale has 12 pitches per octave. When tuned to equal temperament, each of these pitches is equally distant from its neighbors1. Pitches that are 12 semitones apart (an octave) are considered to be the same musical note. This means we can treat notes like integers modulo 12, from 0 to 11. Seven of these are given letter names2 from A to G. This isn't enough to name all 12 pitches, but adding accidentals fixes that: adding a ♯ (sharp) to a note makes it one semitone higher, and adding a ♭ (flat) makes it one semitone lower.

## Chords

A chord is 2 or more notes played together. The type of chord depends on the relationships between the notes, which can be determined by the distances between them. A chord has a root note, as mentioned earlier. We'll treat the root note as 0 in these examples, but this is arbitrary, and all that matters in this challenge is the distance between notes in modulo arithmetic. There will always be one unique chord type for the answer, either a triad or a seventh chord. The root note will not always be the lowest-frequency pitch; choose the root note such that you can describe the chord as one of the four following chord types:

* A **major triad** is a chord with the notes `0 4 7`.
* A **minor triad** is a chord with the notes `0 3 7`.
* A **dominant (or major/minor) seventh** chord has the notes `0 4 7 10`.
* A **minor (or minor/minor) seventh** chord has the notes `0 3 7 10`.3

## Guitar tuning

Standard tuning on a 6-string guitar starts with E on the lowest string, and then hits notes at intervals of 5, 5, 5, 4, then 5 semitones going up the strings. Taking the lowest E as 0, this means strumming all the strings of the guitar gives you pitches numbered `0 5 10 15 19 24`, which modulo 12 is equivalent to `0 5 10 3 7 0`, or the notes `E A D G B E`.

# Worked examples

If your input is `0 2 2 0 0 0`, this corresponds to the notes `E B E G B E`, so just E, B, and G. These form the chord `Em`, which can be seen by numbering them with the root as E, giving us `0 3 7`. (The result would be the same for `X 2 X 0 X 0`, or `12 14 14 12 12 12`.)

If your input is `4 4 6 4 6 4`, numbering these with a root of C♯ gives `7 0 7 10 4 7`, or `0 4 7 10`, so the answer is `C#7` (or `Db7`). If it was instead `4 4 6 4 5 4`, the numbering would give `7 0 7 10 3 7`, or `0 3 7 10`, which is `C#m7` (or `Dbm7`).

# Test cases

```
X 3 2 0 1 0  --->  C
0 2 2 0 0 0  --->  Em
X 2 X 0 X 0  --->  Em
4 4 6 4 6 4  --->  C#7  (or Db7)
4 4 6 4 5 4  --->  C#m7 (or Dbm7)
0 2 2 1 0 0  --->  E
0 0 2 2 2 0  --->  A
X X 4 3 2 2  --->  F#   (or Gb)
3 2 0 0 0 1  --->  G7
X X 0 2 1 1  --->  Dm7
3 3 5 5 5 3  --->  C
4 6 6 5 4 4  --->  G#   (or Ab)
2 2 4 4 4 5  --->  B7
0 7 5 5 5 5  --->  Am7
7 6 4 4 X X  --->  B
8 6 1 X 1 3  --->  Cm
8 8 10 10 9 8 -->  Fm
0 19 5 16 8 7 -->  Em
6 20 0 3 11 6 -->  A#   (or Bb)
X 14 9 1 16 X -->  G#m  (or Abm)
12 14 14 12 12 12 --> Em
15 14 12 12 12 15 --> G
20 X 20 20 20 20  --> Cm7
X 13 18 10 11 10  --> A#7 (or Bb7)

```

---

1by the logarithms of their frequencies

2or, in solfège, names like *do, re, mi*. In this challenge, use the letter names.

3This could also be called a major sixth chord, with a different choice of root note. In this challenge, call it by its minor seventh name.

# Answer
# MATL, ~~115~~ 114 bytes

```
[OAXICO]+tZN~)Y@!"@t1)XH- 12\XzXJK7hm?O.]JI7hm?'m'.]J[KCX]m?'7'.]J[ICX]m?'m7'.]]'FF#GG#AA#BCC#DD#E'l2741B~QY{HX)wh

```

Input format is `[N 3 2 0 1 0]`, where `N` indicates unused string.

The output string always uses `#`, not `b`.

Try it online! Or verify all test cases, in two parts to avoid the online compiler timing out:

### Explanation

```
[OAXICO]            % Push [0 5 10 3 7 0]. This represents the pitch of each open
                    % string relative to the lowest string, modulo 12
+                   % Add to implicit input. May contain NaN's, for unused strings
tZN~)               % Remove NaN's
Y@!                 % Matrix of all permutations, each in a column
"                   % For each column
  @                 %   Push current column
  t1)               %   Duplicate and get first entry
  XH                %   Copy into clipboard H
  - 12\             %   Subtract. This amounts to considering that the first note
                    %   of the current permutation is the root, and computing
                    %   all intervals with respect to that
  12\               %   Modulo 12
  Xz                %   Remove zeros
  XJ                %   Copy into clipboard J
  K7hm?             %   Are all intervals 4 or 7? If so: it's a major chord
    O               %     Push 0 (will become space when converted to char)
    .               %     Break for loop
  ]                 %   End if
  J                 %   Push array of nonzero intervals again
  I7hm?             %   Are all intervals 3 or 7? If so: it's a minor chord
    'm'             %     Push this string
    .               %     Break for loop
  ]                 %   End if
  J                 %   Push array of nonzero intervals again
  [KCX]m?           %   Are all intervals 4, 7 or 10? If so: it's a dominant-7th
                    %   chord
    '7'             %     Push this string
    .               %     Break for loop
  ]                 %   End if
  J                 %   Push array of nonzero intervals again
  [ICX]m?           %   Are all intervals 3, 7 or 10? If so: it's a minor 7th chord
    'm7'            %     Push this string
    .               %     Break for loop
  ]                 %   End if
]                   % End for. The loop is always exited via one of the 'break'
                    % statements. When that happens, the stack contains 0, 'm',
                    % '7' or 'm7', indicating the type of chord; and clipboard H
                    % contains a number that tells the root note using the lowest
                    % string as base (1 is F, 2 is F# etc)
'FF#GG#AA#BCC#DD#E' % Push this string. Will be split into strings of length 1 or 2
l                   % Push 1
2741B~Q             % Push [1 2 1 2 1 2 1 1 2 1 2 1] (obtained as 2741 in binary,
                    % negated, plus 1)
Y{                  % Split string using those lengths. Gives a cell array of
                    % strings: {'F', 'F#', ..., 'E'}
H                   % Push the identified root note
X)                  % Index into cell array of strings
wh                  % Swap and concatenate. Implicitly display

```
> 9 votes

# Answer
**MS-DOS .COM file (179 bytes)**

The file (here displayed as HEX):

```
fc be 81 00 bf 72 01 31 db b9 06 00 51 e8 73 00
59 e2 f9 b9 0c 00 be 48 01 ad 39 c3 74 0d 40 75
f8 d1 fb 73 03 80 c7 08 e2 ec c3 31 db 88 cb 8a
87 59 01 e8 42 00 8a 87 65 01 e8 3b 00 81 c6 08
00 ac e8 33 00 ac eb 30 91 00 89 00 91 04 89 04
ff ff 00 00 6d 00 37 00 6d 37 42 41 41 47 47 46
46 45 44 44 43 43 00 23 00 23 00 23 00 00 23 00
23 00 04 09 02 07 0b 04 84 c0 74 06 b4 02 88 c2
cd 21 c3 8a 0d 47 ac 3c 20 76 fb 30 ed 3c 41 73
22 2c 30 72 0b 86 c5 b4 0a f6 e4 00 c5 ac eb ed
88 e8 00 c8 30 e4 b1 0c f6 f1 88 e1 b8 01 00 d3
e0 09 c3

```

The input is given via command line. Invalid input will lead to invalid program behaviour!

The assembler code looks like this:

```
.text
.code16
ComFileStart:
    cld
    mov $0x81, %si
    mov $(TuneTable-ComFileStart+0x100), %di
    xor %bx, %bx
    # 6 strings: Build the mask of played tones
    mov $6, %cx
NextStringRead:
    push %cx
    call InsertIntoMask
    pop %cx
    loop NextStringRead

    # Check all base tones...
    mov $12, %cx
TestNextTone:
    mov $0x100+ChordTable-ComFileStart, %si
TestNextChord:
    lodsw
    # Is it the chord we are searching for?
    cmp %ax, %bx
    je FoundChord
    # Is it the end of the table?
    inc %ax
    jnz TestNextChord
    # Transpose the chord we really play
    # and go to the next tone
    # This code rotates the low 12 bits of
    # BX one bit right
    sar $1, %bx
    jnc NoToneRotated
    add $8, %bh
NoToneRotated:
    loop TestNextTone
EndOfProgram:
    ret

FoundChord:
    # Get and print the tone name
    xor %bx, %bx
    mov %cl, %bl
    mov (ToneNamesTable+0x100-1-ComFileStart)(%bx),%al
    call printChar
    mov (ToneNamesTable+0x100+12-1-ComFileStart)(%bx),%al
    call printChar
    # Get the chord name suffix and print it
    add $(ChordNamesTable-ChordTable-2),%si
    lodsb
    call printChar
    lodsb
    # Note: Under MS-DOS 0x0000 is the first word on
    # the stack so the "RET" of printChar will jump
    # to address 0x0000 which contains an "INT $0x21"
    # (end of program) instruction
    jmp printChar

ChordTable:
    # Major, Minor, Major-7, Minor-7
    .word 0x91, 0x89, 0x491, 0x489, 0xFFFF
ChordNamesTable:
    .byte 0,0,'m',0,'7',0,'m','7'
ToneNamesTable:
    .ascii "BAAGGFFEDDCC"
    .byte 0,'#',0,'#',0,'#',0,0,'#',0,'#',0
TuneTable:
    .byte 4,9,2,7,11,4

#
# Subfunction: Print character AL;
#              Do nothing if AL=0
#
printChar:
    test %al, %al
    jz noPrint
    mov $2, %ah
    mov %al, %dl
    int $0x21
noPrint:
    ret

#
# Subfunction: Get one finger position
#              and insert it into a bit mask
#              of tones being played
#
# Input:
#
#   [DS:DI] =
#        Tuning of current string (0=C, 1=C#, ..., 11=B)
#        Actually only 2=D, 4=E, 7=G, 9=A and 11=B are used
#
#   DS:SI = Next character to read
#
#   DF = Clear
#
# Input and Output:
#
#    BX = Bit mask
#    DI = Will be incremented
#
# Destroys nearly all registers but SI and BX
#
InsertIntoMask:
    mov (%di), %cl
    inc %di
SkipSpaces:
    lodsb
    cmp $' ', %al
    jbe SkipSpaces
# Now evaluate each digit
    xor %ch, %ch
GetNextDigit:
    # Number = 10*Number+Digit
    cmp $'A', %al
    jae DigitIsX
    sub $'0', %al
    jb DigitsDone
    xchg %al, %ch
    mov $10, %ah
    mul %ah
    add %al, %ch
    lodsb
    jmp GetNextDigit
DigitsDone:
    # Add the tune of the string
    # and perform modulus 12
    mov %ch, %al
    add %cl, %al
    xor %ah, %ah
    mov $12, %cl
    div %cl
    mov %ah, %cl
    mov $1, %ax
    shl %cl, %ax
    or %ax, %bx
DigitIsX:
    ret

```

> Test cases:
>
> ```
> 6 20 0 3 11 6 -->  A#   (or Bb)
>
> ```

I already saw two piano players playing together "four handed" on a piano.

This test case is the first time I read about guitar players doing this!

Even with right-hand tapping you cannot play a cord like this!
> 4 votes

# Answer
# Ruby, 129 bytes

As previous version but uses a single loop, with ternary operator to sequence between the parsing step and output step. Some other minor modifications were required to make this work.

```
->a{r=0
18.times{|j|j<6?a[j]&&r|=8194<<(6--~j%5+a[j]*7)%12:(r/=2)&11==3&&puts("CGDAEBF"[j%7]+?#*(j/13)+['',?m,?7,'m7'][r>>9&3])}}

```

# Ruby, 136 bytes

Llamda function accepts an array of 6 numbers as an argument and outputs to stdout. Unused string is represented by a falsy value (the only falsy values in ruby are `nil` and `false`.)

```
->a{r=0
6.times{|j|a[j]&&r|=4097<<(6--~j%5+a[j]*7)%12}
12.times{|j|r&11==3&&puts("FCGDAEB"[j%7]+?#*(j/7)+['',?m,?7,'m7'][r>>9&3]);r/=2}}

```

**Explanation**

I use a representation of the 12 pitches based on the circle of fifths . This means each pitch is followed by the pitch 7 semitones higher (or 5 semitones lower) giving the sequence `F C G D A E B F# C# G# D# A#`. There are 2 advantages to this. One is that all the sharps appear together. The other is that the open-string notes of the 5 string bass appear together: GDAEB (the guitar is related but slightly more complex, see below).

The first loop runs 6 times. The expression `6--~j%5`(equivalently `6-(j+1)%5`) gives the note values for the open strings: `E=5 A=4 D=3 G=2 B=6 E=5`. To this we add the fret number multiplied by 7 (as can be seen above, adding one semitone moves us 7 places forward in the sequence.) Then we take the whole thing modulo 12 and make a bitmap of the notes that are present (we use `4097<<note value` to give 2 consecutive octaves.)

Having composed the bitmap, we are ready to search the chord and output it.

We are interested in the following notes:

```
Note       position in      position in             Note      position in
           semitone domain  circle of fifths                  circle of fifths
Root       0                0                       Root      0
Minor 3rd  3                9                       Fifth     1
Major 3rd  4                4                       Sixth     3
Fifth      7                1                       Major 3rd 4
Sixth      9                3                       Minor 3rd 9
Minor 7th  10               10                      Minor 7th 10

```

Starting by checking for chord F, we test to see if the root and fifth are present: bits 0 and 1 (counting from least significant: the 1's and 2's bits.) In order to reject sixth chords we also need to check that the sixth is absent: bit 3 (8's bit.) so we check that `r&&11==3` and if so we print the chord.

We ignore the major third, and rely entirely on bit 9 (minor third) and bit 10 (minor 7th) to work out the chord type. The expression `r>>9&3` is used to pick the correct chord type from an array.

At the end of the loop, we shift the bitmap right one bit `r/=2` to test the possible chord roots in sequence: `F C G D A E B F# C# G# D# A#`.

**Ungolfed in test program**

```
f=->a{                            #Accept array of 6 numbers as argument.
  r=0                             #Setup an empty bitmap.

  6.times{|j|                     #For each string
    a[j]&&                        #if the fret value is truthy (not nil or false)
    r|=4097<<(6--~j%5+a[j]*7)%12  #calculate the note value in the circle of fifths and add to the bitmap.
  }

  12.times{|j|                    #For each possible root note
    r&11==3&&                     #if root and fifth are present (bits 0 and 1) and sixth is absent (bit 3)
    puts("FCGDAEB"[j%7]+?#*(j/7)+ #output the note name and a sharp symbol if necessary, followed by
    ['',?m,?7,'m7'][r>>9&3])      #m and/or 7 as indicate by bits 9 and 10.
    r/=2
  }
}

print 1;f[[nil,3,2,0,1,0]]       #  C
print 2;f[[0,2,2,0,0,0]]         #  Em
print 3;f[[nil,2,nil,0,nil,0]]   #  Em
print 4;f[[4,4,6,4,6,4]]         #  C#7
print 5;f[[4,4,6,4,5,4]]         #  C#m7
print 6;f[[0,2,2,1,0,0]]         #  E
print 7;f[[0,0,2,2,2,0]]         #  A
print 8;f[[nil,nil,4,3,2,2]]     #  F#
print 9;f[[3,2,0,0,0,1]]         #  G7
print 10;f[[nil,nil,0,2,1,1]]    #  Dm7
print 11;f[[3,3,5,5,5,3]]        #  C
print 12;f[[4,6,6,5,4,4]]        #  G#
print 13;f[[2,2,4,4,4,5]]        #  B7
print 14;f[[0,7,5,5,5,5]]        #  Am7
print 15;f[[7,6,4,4,nil,nil]]    #  B
print 16;f[[8,6,1,nil,1,3]]      #  Cm
print 17;f[[8,8,10,10,9,8]]      #  Fm
print 18;f[[0,19,5,16,8,7]]      #  Em
print 19;f[[6,20,0,3,11,6]]      #  A#
print 20;f[[nil,14,9,1,16,nil]]  #  G#m
print 21;f[[12,14,14,12,12,12]]  #  Em
print 22;f[[15,14,12,12,12,15]]  #  G
print 23;f[[20,nil,20,20,20,20]] #  Cm7
print 24;f[[nil,13,18,10,11,10]] #  A#7

```
> 3 votes

# Answer
# Javascript (ES6), ~~335~~ 333 bytes

Love this challenge and PPCG SE! This is my first golf - suggestions welcome as I'm sure it could be improved a lot. (knocked off 2 bytes as I had included f= in the count)

Function `f` takes an array of strings, representing numbers and 'X', like `f(['X','3','2','0','1','0'])` and returns a chord (natural or sharp) like `E#m7`. Newlines added for clarity (not included in byte count)

```
f=c=>[s=new Map([[435,''],[345,'m'],[4332,7],[3432,'m7']]),
n=[...new Set(c.map((e,i)=>e?(+e+[0,5,10,3,7,0][i])%12:-1)
.filter(e=>++e).sort((a,b)=>a>b))],d=[...n,n[0]+12].reduce(
(a,c,i)=>i?[...a,(c-n[i-1]+12)%12]:[],0).join``.repeat(2),
m=+d.match(/(34|43)(5|32)/g)[0],'E0F0F#0G0G#0A0A#0B0C0C#0D0D#'
.split(0)[n[d.indexOf(m)]]+s.get(m)][4]

```

Usage example:

```
console.log(f(['0','2','2','0','0','0'])); // Em

```

To run test cases:

```
tests=`X 3 2 0 1 0 ---> C
0 2 2 0 0 0 ---> Em
X 2 X 0 X 0 ---> Em
4 4 6 4 6 4 ---> C#7 (or Db7)
4 4 6 4 5 4 ---> C#m7 (or Dbm7)`; // and so on...

tests.split`\n`.forEach(e=>{
    console.log(`Test: ${e}
      Result: ${f(e.split(' ').slice(0,6))}`)
})

```

Ungolfed version with explanation:

```
f = (c) => {
    s = new Map([
        [435,''], [345,'m'], [4332,7], [3432,'m7']
    ]) /* Each key in s describes the intervals (semitones)
          between consecutive notes in a chord, when it is
          reduced to a single octave, including the interval
          from highest back to lowest. The values describe
          the corresponding chord suffix. E.g. C-E-G has
          intervals C-4-E-3-G-5-C. 435=major=no suffix. */

    n = [ ...new Set(
        c.map(
         (e,i) => e ? ( +e + [0,5,10,3,7,0][i] )%12 : -1
         ).filter( (e) => ++e ).sort( (a,b) => a>b )
        ) ] /* take the input array, c, and transform each fret
               position into a note. remove non-notes (-1), sort
               in tone order, remove duplicates. An input of
               positions X 13 18 10 11 10 becomes notes
               (-1) 6 4 1 6 10 then 1 4 6 10. */

    d = [ ...n, n[0] + 12 ].reduce(
        (a,c,i) => i ? [ ...a, (c - n[i-1] + 12)%12 ] : [], 0
    ).join``.repeat(2)
    /* convert the note array, n, into an interval string, d,
       including the lowest note repeated above it to capture
       all intervals. Repeat it twice so that, regardless of the
       inversion played, the intervals will appear in root order
       somewhere. E.g. notes 1-4-6-10 and 13 (1+12)
       become intervals 3 2 4 3, and string for searching
       32433243 */

    m = +d.match( /(34|43)(5|32)/g )[0];
      /* m is the matched chord pattern. In this case, 4332. */

    return 'E0F0F#0G0G#0A0A#0B0C0C#0D0D#'.split(0)[
    n[ d.indexOf(m) ]
    /* get the position in the interval string where the root
       interval first occurs. this corresponds to the position
       of the chord root note in the note array, n. convert this
       number 0-12 to a note name E - D# */
    ] + s.get(m)
       /* add the suffix corresponding to the matched
       chord interval pattern */
}

```
> 2 votes

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


title: Compute the kangaroo sequence

text:
# Question
Title: Compute the kangaroo sequence
### Backstory

Disclaimer: May contain made up information about kangaroos.

Kangaroos traverse several stages of development. As they grow older and stronger, they can jump higher and longer, and they can jump more times before they get hungry.

In stage **1**, the kangaroo is very little and cannot jump at all. Despite this, is constantly requires nourishment. We can represent a stage **1** kangaroo's activity pattern like this.

```
o

```

In stage **2**, the kangaroo can make small jumps, but not more than **2** before it gets hungry. We can represent a stage **2** kangaroo's activity pattern like this.

```
 o o
o o o

```

After stage **2** the kangaroo improves quickly. In each subsequent stage, the kangaroo can jump a bit higher (1 unit in the graphical representation) and twice as many times. For example, a stage **3** kangaroo's activity pattern looks like this.

```
  o   o   o   o
 o o o o o o o o
o   o   o   o   o

```

All that jumping requires energy, so the kangaroo requires nourishment after completing each activity pattern. The exact amount required can be calculated as follows.

1. Assign each **o** in the activity pattern of a stage **n** kangaroo its height, i.e., a number from **1** to **n**, where **1** corresponds to the ground and **n** to the highest position.
2. Compute the sum of all heights in the activity pattern.

For example, a stage **3** kangaroo's activity pattern includes the following heights.

```
  3   3   3   3
 2 2 2 2 2 2 2 2
1   1   1   1   1

```

We have five **1**'s, eight **2**'s, and four **3**'s; the sum is **5·1 + 8·2 + 4·3 = 33**.

### Task

Write a full program or a function that takes a positive integer **n** as input and prints or returns the nutritional requirements per activity of a stage **n** kangaroo.

This is ; may the shortest answer in bytes win!

### Examples

```
 1 ->     1
 2 ->     7
 3 ->    33
 4 ->   121
 5 ->   385
 6 ->  1121
 7 ->  3073
 8 ->  8065
 9 -> 20481
10 -> 50689

```

# Answer
> 8 votes
# Jelly, 6 bytes

```
²’æ«’‘

```

Uses the formula (*n*2 \- 1) 2*n* \- 1 \+ 1 to compute each value. @Qwerp-Derp's was kind enough to provide a proof.

Try it online! or Verify all test cases.

## Explanation

```
²’æ«’‘  Input: n
²       Square n
 ’      Decrement
  æ«    Bit shift left by
    ’     Decrement of n
     ‘  Increment

```

# Answer
> 17 votes
# Coffeescript, 19 bytes

```
(n)->(n*n-1<<n-1)+1

```

Edit: Thanks to Dennis for chopping off 6 bytes!

The formula for generating Kangaroo numbers is this:

## Explanation of formula:

The number of `1`'s in `K(n)`'s final sum is `2^(n - 1) + 1`.

The number of `n`'s in `K(n)`'s final sum is `2^(n - 1)`, so the sum of all the `n`'s is `n * 2^(n - 1)`.

The number of any other number (`d`) in `K(n)`'s final sum is `2^n`, so the sum of all the `d`'s would be `d * 2^n`.

* Thus, the sum of all the other numbers `= (T(n) - (n + 1)) * 2^n`, where `T(n)` is the triangle number function (which has the formula `T(n) = (n^2 + 1) / 2`).

Substituting that in, we get the final sum

```
  (((n^2 + 1) / 2) - (n + 1)) * 2^n
= (((n + 1) * n / 2) - (n + 1)) * 2^n
= ((n + 1) * (n - 2) / 2) * 2^n
= 2^(n - 1) * (n + 1) * (n - 2)

```

When we add together all the sums, we get `K(n)`, which equals

```
  (2^(n - 1) * (n + 1) * (n - 2)) + (2^(n - 1) + 1) + (n * 2^(n - 1))
= 2^(n - 1) * ((n + 1) * (n - 2) + n + 1) + 1
= 2^(n - 1) * ((n^2 - n - 2) + n + 1) + 1
= 2^(n - 1) * (n^2 - 1) + 1

```

... which is equal to the formula above.

# Answer
> 7 votes
# Java 7, 35 bytes

```
int c(int n){return(n*n-1<<n-1)+1;}

```

# Answer
> 6 votes
# Jelly, 4 bytes

```
ŒḄ¡S

```

Try it online! or verify all test cases.

### How it works

```
ŒḄ¡S  Main link. Argument: n (integer)

ŒḄ    Bounce; turn the list [a, b, ..., y, z] into [a, b, ..., y, z, y, ..., b, a].
      This casts to range, so the first array to be bounced is [1, ..., n].
      For example, 3 gets mapped to [1, 2, 3, 2, 1].
  ¡   Call the preceding atom n times.
      3 -> [1, 2, 3, 2, 1]
        -> [1, 2, 3, 2, 1, 2, 3, 2, 1]
        -> [1, 2, 3, 2, 1, 2, 3, 2, 1, 2, 3, 2, 1, 2, 3, 2, 1]
   S  Compute the sum.

```

# Answer
> 5 votes
# Python 2, ~~25~~ 23 bytes

```
lambda x:(x*x-1<<x-1)+1

```

Used miles's formula.

Thanks to Jonathan Allan for -2 bytes.

# Answer
> 4 votes
# Lua, 105 bytes

```
s=tonumber(arg[1])e=1 for i=1,s>1 and 2^(s-1)or 0 do e=e+1 for j=2,s-1 do e=e+j*2 end e=e+s end print(e)

```

De-golfed:

```
stage = tonumber(arg[1])
energy = 1
for i = 1, stage > 1 and 2 ^ (stage - 1) or 0 do
    energy = energy + 1
    for j = 2, stage - 1 do
        energy = energy + j * 2
    end
    energy = energy + stage
end
print(energy)

```

Entertaining problem!

# Answer
> 4 votes
# CJam, 11 bytes

```
ri_2#(\(m<)

```

Try it Online.

Explanation:

```
r           e# Get token.       ["A"]
 i          e# Integer.         [A]
  _         e# Duplicate.       [A A]
   2#       e# Square.          [A A^2]
     (      e# Decrement.       [A A^2-1]
      \     e# Swap.            [A^2-1 A]
       (    e# Decrement.       [A^2-1 A-1]
        m<  e# Left bitshift.   [(A^2-1)*2^(A-1)]
          ) e# Increment.       [(A^2-1)*2^(A-1)+1]
            e# Implicit output.

```

# Answer
> 4 votes
# Actually, 8 bytes

```
;²D@D╙*u

```

Try it online!

Explanation:

This simply computes the formula `(n**2 - 1)*(2**(n-1)) + 1`.

```
;²D@D╙*u
;         duplicate n
 ²        square (n**2)
  D       decrement (n**2 - 1)
   @      swap (n)
    D     decrement (n-1)
     ╙    2**(n-1)
      *   product ((n**2 - 1)*(2**(n-1)))
       u  increment ((n**2 - 1)*(2**(n-1))+1)

```

# Answer
> 4 votes
# GolfScript, 11 bytes

```
~.2?(2@(?*)

```

Try it online!

Thanks Martin Ender (8478) for removing 4 bytes.

Explanation:

```
            Implicit input                 ["A"]
~           Eval                           [A]
 .          Duplicate                      [A A]
  2         Push 2                         [A A 2]
   ?        Power                          [A A^2]
    (       Decrement                      [A A^2-1]
     2      Push 2                         [A A^2-1 2]
      @     Rotate three top elements left [A^2-1 2 A]
       (    Decrement                      [A^2-1 2 A-1]
        ?   Power                          [A^2-1 2^(A-1)]
         *  Multiply                       [(A^2-1)*2^(A-1)]
          ) Increment                      [(A^2-1)*2^(A-1)+1]
            Implicit output                []

```

# Answer
> 3 votes
## Mathematica, 15 bytes

```
(#*#-1)2^#/2+1&

```

There is no bitshift operator, so we need to do the actual exponentiation, but then it's shorter to divide by 2 instead of decrementing the exponent.

# Answer
> 3 votes
# C, 26 bytes

As a macro:

```
#define f(x)-~(x*x-1<<~-x)

```

As a function (27):

```
f(x){return-~(x*x-1<<~-x);}

```

# Answer
> 3 votes
# 05AB1E, 7 bytes

```
n<¹<o*>

```

Try it online!

**Explanation**

```
n<        # n^2
     *    # *
  ¹<o     # 2^(n-1)
      >   # + 1

```

# Answer
> 2 votes
# MATL, 7 bytes

```
UqGqW*Q

```

Uses the formula from other answers.

Try it online!

```
U    % Implicit input. Square
q    % Decrement by 1
G    % Push input again
q    % Decrement by 1
W    % 2 raised to that
*    % Multiply
Q    % Increment by 1. Implicit display

```

# Answer
> 2 votes
# C#, 18 bytes

```
n=>(n*n-1<<n-1)+1;

```

Anonymous function based on Qwerp-Derp's excellent mathematical analysis.

Full program with test cases:

```
using System;

namespace KangarooSequence
{
    class Program
    {
        static void Main(string[] args)
        {
            Func<int,int>f= n=>(n*n-1<<n-1)+1;

            //test cases:
            for (int i = 1; i <= 10; i++)
                Console.WriteLine(i + " -> " + f(i));
            /* will display:
            1 -> 1
            2 -> 7
            3 -> 33
            4 -> 121
            5 -> 385
            6 -> 1121
            7 -> 3073
            8 -> 8065
            9 -> 20481
            10 -> 50689
            */
        }
    }
}

```

# Answer
> 2 votes
## Batch, 30 bytes

```
@cmd/cset/a"(%1*%1-1<<%1-1)+1"

```

Well, it beats Java anyway.

# Answer
> 2 votes
# Oasis, 9 bytes

```
2n<mn²<*>

```

I'm surprised there isn't a built-in for `2^n`.

Try it online!

### Explanation:

```
2n<m        # 2^(n-1) (why is m exponentiation?)
    n²<     # n^2-1
       *    # (2^(n-1))*(n^2-1)
        >   # (2^(n-1))*(n^2-1)+1

```

# Answer
> 1 votes
## Racket 33 bytes

Using formula explained by @Qwerp-Derp

```
(+(*(expt 2(- n 1))(-(* n n)1))1)

```

Ungolfed:

```
(define (f n)
  (+ (*(expt 2
            (- n 1))
      (-(* n n)
        1))
    1))

```

Testing:

```
(for/list((i(range 1 11)))(f i))

```

Output:

```
'(1 7 33 121 385 1121 3073 8065 20481 50689)

```

# Answer
> 1 votes
# Pyth, 8 bytes

```
h.<t*QQt

```

pyth.herokuapp.com

Explanation:

```
     Q   Input
      Q  Input
    *    Multiply
   t     Decrement
       t Decrement the input
 .<      Left bitshift
h        Increment

```

# Answer
> 1 votes
# Ruby, 21 bytes

@Qwerp-Derp basically did the heavy lifting.

Because of the precedence in ruby, it seems we need some parens:

```
->(n){(n*n-1<<n-1)+1}

```

# Answer
> 1 votes
# Scala, 23 bytes

```
(n:Int)=>(n*n-1<<n-1)+1

```

Uses bit shift as exponentiation

# Answer
> 1 votes
## R, 26 bytes

Shamelessly applying the formula

```
n=scan();2^(n-1)*(n^2-1)+1

```

# Answer
> 1 votes
# , 11 bytes

```
1-<:2&*1-*:

```

Based on the same formula found earlier.

Try it online!

## Explanation

```
1-<:2&*1-*:  Input: integer n
         *:  Square n
       1-    Subtract it from 1
  <:         Decrement n
    2&*      Multiply the value 1-n^2 by two n-1 times
1-           Subtract it from 1 and return

```

# Answer
> 0 votes
# Groovy (22 Bytes)

```
{(it--**2-1)*2**it+1}

```

Does not preserve `n`, but uses the same formula as all others in this competition. Saved 1 byte with decrements, due to needed parenthesis.

## Test

```
(1..10).collect{(it--**2-1)*2**it+1}

```

> \[1, 7, 33, 121, 385, 1121, 3073, 8065, 20481, 50689\]

# Answer
> 0 votes
# JS-Forth, 32 bytes

Not super short, but it's shorter than Java. This function pushes the result onto the stack. This requires JS-Forth because I use `<<`.

```
: f dup dup * 1- over 1- << 1+ ;

```

**Try it online**

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


title: Implement SHA-256

text:
# Question
Title: Implement SHA-256
Given a sequence of bytes, output the SHA-256 hash value of the sequence.

## The SHA-256 Algorithm

The following pseudocode is taken from the Wikipedia page for SHA-2.

```
Note 1: All variables are 32 bit unsigned integers and addition is calculated modulo 2^32
Note 2: For each round, there is one round constant k[i] and one entry in the message schedule array w[i], 0 ≤ i ≤ 63
Note 3: The compression function uses 8 working variables, a through h
Note 4: Big-endian convention is used when expressing the constants in this pseudocode,
    and when parsing message block data from bytes to words, for example,
    the first word of the input message "abc" after padding is 0x61626380

Initialize hash values:
(first 32 bits of the fractional parts of the square roots of the first 8 primes 2..19):
h0 := 0x6a09e667
h1 := 0xbb67ae85
h2 := 0x3c6ef372
h3 := 0xa54ff53a
h4 := 0x510e527f
h5 := 0x9b05688c
h6 := 0x1f83d9ab
h7 := 0x5be0cd19

Initialize array of round constants:
(first 32 bits of the fractional parts of the cube roots of the first 64 primes 2..311):
k[0..63] :=
   0x428a2f98, 0x71374491, 0xb5c0fbcf, 0xe9b5dba5, 0x3956c25b, 0x59f111f1, 0x923f82a4, 0xab1c5ed5,
   0xd807aa98, 0x12835b01, 0x243185be, 0x550c7dc3, 0x72be5d74, 0x80deb1fe, 0x9bdc06a7, 0xc19bf174,
   0xe49b69c1, 0xefbe4786, 0x0fc19dc6, 0x240ca1cc, 0x2de92c6f, 0x4a7484aa, 0x5cb0a9dc, 0x76f988da,
   0x983e5152, 0xa831c66d, 0xb00327c8, 0xbf597fc7, 0xc6e00bf3, 0xd5a79147, 0x06ca6351, 0x14292967,
   0x27b70a85, 0x2e1b2138, 0x4d2c6dfc, 0x53380d13, 0x650a7354, 0x766a0abb, 0x81c2c92e, 0x92722c85,
   0xa2bfe8a1, 0xa81a664b, 0xc24b8b70, 0xc76c51a3, 0xd192e819, 0xd6990624, 0xf40e3585, 0x106aa070,
   0x19a4c116, 0x1e376c08, 0x2748774c, 0x34b0bcb5, 0x391c0cb3, 0x4ed8aa4a, 0x5b9cca4f, 0x682e6ff3,
   0x748f82ee, 0x78a5636f, 0x84c87814, 0x8cc70208, 0x90befffa, 0xa4506ceb, 0xbef9a3f7, 0xc67178f2

Pre-processing:
append the bit '1' to the message
append k bits '0', where k is the minimum number >= 0 such that the resulting message
    length (modulo 512 in bits) is 448.
append length of message (without the '1' bit or padding), in bits, as 64-bit big-endian integer
    (this will make the entire post-processed length a multiple of 512 bits)

Process the message in successive 512-bit chunks:
break message into 512-bit chunks
for each chunk
    create a 64-entry message schedule array w[0..63] of 32-bit words
    (The initial values in w[0..63] don't matter, so many implementations zero them here)
    copy chunk into first 16 words w[0..15] of the message schedule array

    Extend the first 16 words into the remaining 48 words w[16..63] of the message schedule array:
    for i from 16 to 63
        s0 := (w[i-15] rightrotate 7) xor (w[i-15] rightrotate 18) xor (w[i-15] rightshift 3)
        s1 := (w[i-2] rightrotate 17) xor (w[i-2] rightrotate 19) xor (w[i-2] rightshift 10)
        w[i] := w[i-16] + s0 + w[i-7] + s1

    Initialize working variables to current hash value:
    a := h0
    b := h1
    c := h2
    d := h3
    e := h4
    f := h5
    g := h6
    h := h7

    Compression function main loop:
    for i from 0 to 63
        S1 := (e rightrotate 6) xor (e rightrotate 11) xor (e rightrotate 25)
        ch := (e and f) xor ((not e) and g)
        temp1 := h + S1 + ch + k[i] + w[i]
        S0 := (a rightrotate 2) xor (a rightrotate 13) xor (a rightrotate 22)
        maj := (a and b) xor (a and c) xor (b and c)
        temp2 := S0 + maj

        h := g
        g := f
        f := e
        e := d + temp1
        d := c
        c := b
        b := a
        a := temp1 + temp2

    Add the compressed chunk to the current hash value:
    h0 := h0 + a
    h1 := h1 + b
    h2 := h2 + c
    h3 := h3 + d
    h4 := h4 + e
    h5 := h5 + f
    h6 := h6 + g
    h7 := h7 + h

Produce the final hash value (big-endian):
digest := hash := h0 append h1 append h2 append h3 append h4 append h5 append h6 append h7

```

## Reference implementation

Here is a reference implementation, in Python 3:

```
#!/usr/bin/env python3

import sys

# ror function modified from http://stackoverflow.com/a/27229191/2508324
def ror(val, r_bits):
   return (val >> r_bits) | (val << (32-r_bits)) % 2**32

h = [0x6a09e667, 0xbb67ae85, 0x3c6ef372, 0xa54ff53a, 0x510e527f, 0x9b05688c, 0x1f83d9ab, 0x5be0cd19]

k = [0x428a2f98, 0x71374491, 0xb5c0fbcf, 0xe9b5dba5, 0x3956c25b, 0x59f111f1, 0x923f82a4, 0xab1c5ed5,
   0xd807aa98, 0x12835b01, 0x243185be, 0x550c7dc3, 0x72be5d74, 0x80deb1fe, 0x9bdc06a7, 0xc19bf174,
   0xe49b69c1, 0xefbe4786, 0x0fc19dc6, 0x240ca1cc, 0x2de92c6f, 0x4a7484aa, 0x5cb0a9dc, 0x76f988da,
   0x983e5152, 0xa831c66d, 0xb00327c8, 0xbf597fc7, 0xc6e00bf3, 0xd5a79147, 0x06ca6351, 0x14292967,
   0x27b70a85, 0x2e1b2138, 0x4d2c6dfc, 0x53380d13, 0x650a7354, 0x766a0abb, 0x81c2c92e, 0x92722c85,
   0xa2bfe8a1, 0xa81a664b, 0xc24b8b70, 0xc76c51a3, 0xd192e819, 0xd6990624, 0xf40e3585, 0x106aa070,
   0x19a4c116, 0x1e376c08, 0x2748774c, 0x34b0bcb5, 0x391c0cb3, 0x4ed8aa4a, 0x5b9cca4f, 0x682e6ff3,
   0x748f82ee, 0x78a5636f, 0x84c87814, 0x8cc70208, 0x90befffa, 0xa4506ceb, 0xbef9a3f7, 0xc67178f2]

s = sys.stdin.read().encode()
msg = [int(x,2) for c in s for x in '{:08b}'.format(c)]
msg.append(1)
while len(msg) % 512 != 448:
    msg.append(0)
msg.extend([int(x,2) for x in '{:064b}'.format(len(s) * 8)])

for i in range(len(msg)//512):
    chunk = msg[512*i:512*(i+1)] # sloth love chunk
    w = [0 for _ in range(64)]
    for j in range(16):
        w[j] = int(''.join(str(x) for x in chunk[32*j:32*(j+1)]),2)
    for j in range(16, 64):
        s0 = ror(w[j-15], 7) ^ ror(w[j-15], 18) ^ (w[j-15] >> 3)
        s1 = ror(w[j-2], 17) ^ ror(w[j-2], 19) ^ (w[j-2] >> 10)
        w[j] = (w[j-16] + s0 + w[j-7] + s1) % 2**32
    work = h[:]
    for j in range(64):
        S1 = ror(work[4], 6) ^ ror(work[4], 11) ^ ror(work[4], 25)
        ch = (work[4] & work[5]) ^ (~work[4] & work[6])
        temp1 = (work[7] + S1 + ch + k[j] + w[j]) % 2**32
        S0 = ror(work[0], 2) ^ ror(work[0], 13) ^ ror(work[0], 22)
        maj = (work[0] & work[1]) ^ (work[0] & work[2]) ^ (work[1] & work[2])
        temp2 = (S0 + maj) % 2**32
        work = [(temp1 + temp2) % 2**32] + work[:-1]
        work[4] = (work[4] + temp1) % 2**32
    h = [(H+W)%2**32 for H,W in zip(h,work)]

print(''.join('{:08x}'.format(H) for H in h))

```

## Restrictions

* The usage of builtins which compute SHA-256 hashes or otherwise trivialize the challenge is forbidden
* The input and output may be in any reasonable format (encoded in a single-byte encoding, base64, hexadecimal, etc.)

## Test cases

```
<empty string> -> e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855
abc -> ba7816bf8f01cfea414140de5dae2223b00361a396177a9cb410ff61f20015ad
Hello, World! -> c98c24b677eff44860afea6f493bbaec5bb1c4cbb209c6fc2bbb47f66ff2ad31
1234 -> 03ac674216f3e15c761ee1a5e255f067953623c8b388b4459e13f978d7c846f4

```

# Answer
# , ~~458~~ ~~445~~ ~~443~~ ~~438~~ ~~435~~ ~~430~~ 421 bytes

```
3 :0
B=.32#2
A=.B&#:
P=.+&#.
'H K'=.A<.32*&2(-<.)2 3%:/p:i.64
for_m._512]\(,(1{.~512|448-#),(,~B)#:#)y
do.w=.(,B#:(15&|.~:13&|.~:_10|.!.0])@(_2&{)P/@,(25&|.~:14&|.~:_3|.!.0])@(_15&{),_7 _16&{)^:48]_32]\m
'a b c d e f g h'=.H=.8{.H
for_t.i.64
do.u=.A]P/((e<g)~:e*f),h,(~:/26 21 7|."{e),t{&>K;w
v=.A(a*b)P(c*a~:b)P~:/30 19 10|."{a
h=.g
g=.f
f=.e
e=.A]d P u
d=.c
c=.b
b=.a
a=.A]u P v
end.
H=.A]H P a,b,c,d,e,f,g,:h
end.
,H
)

```

Try it online!

This is a monadic verb that takes a list of bits as input and outputs a list of bits. On TIO, conversion from string to list of bits for the input and list of bits to hexadecimal is implemented for convenience. To test other input, just modify the text in the `input` field.
> 8 votes

# Answer
## Python 2, 633 bytes

```
n=range
f=2**32
q=512
r=lambda v,b:v%f>>b|(v<<32-b)%f
t=int
g=lambda e:[t(x**e%1*f)for x in n(2,312)if 383**~-x%x==1]
h=g(.5)
k=g(1/3.)
m=map(t,input())
l=len(m)
m+=[1]+[0]*((447-l)%q)+map(t,'{:064b}'.format(l))
for i in n(l/q+1):
 c=m[q*i:][:q];w=[t(`c[j*32:][:32]`[1::3],2) for j in n(16)];x=h[:8]
 for j in n(48):a,o=w[j+1],w[j+14];w+=[(w[j]+(r(a,7)^r(a,18)^(a>>3))+w[j+9]+(r(o,17)^r(o,19)^(o>>10)))%f]
 for j in n(64):a,o=x[::4];d=x[7]+(r(o,6)^r(o,11)^r(o,25))+(o&x[5]^~o&x[6])+k[j]+w[j];e=(r(a,2)^r(a,13)^r(a,22))+(x[1]&a|x[2]&a|x[1]&x[2]);x=[d+e]+x[:7];x[4]+=d
 h=[(H+W)%f for H,W in zip(h,x)]
print''.join('%08x'%H for H in h)

```

This solution is the result of a collaboration between myself, Leaky Nun, and Mars Ultor. As such, I've made it community wiki out of fairness. It takes input as a binary string wrapped in quotes (e.g. `'011000010110001001100011'` for `abc`) and outputs a hex string.
> 9 votes

# Answer
## Python 2, 519 bytes

```
Q=2**32
G=lambda e:[int(x**e%1*Q)for x in range(2,312)if 383**~-x%x<2]
H=G(.5)[:8]
r=lambda v,b:v>>b|v<<32-b
M=input()
l=len(M)
M+=bin(l|1<<(447-l)%512+64)[2:]
while M:j=0;a,b,c,d,e,f,g,h=H;exec"H+=int(M[:32],2),;M=M[32:];"*16+"x=H[-15];y=H[-2];H+=(H[-16]+H[-7]+(r(y,17)^r(y,19)^y>>10)+(r(x,7)^r(x,18)^x/8))%Q,;"*48+"u=(r(e,6)^r(e,11)^r(e,25))+(e&f^~e&g)+h+G(1/3.)[j]+H[j+8];X=a,b,c,d,e,f,g,h=(u+(r(a,2)^r(a,13)^r(a,22))+(a&b^a&c^b&c))%Q,a,b,c,(d+u)%Q,e,f,g;j+=1;"*64;H=tuple(a+b&Q-1for a,b in zip(H,X))
print"%08x"*8%H

```

I was working off the pseudocode, but some parts just ended up being the same as the golfed reference Mego posted since there's not much to golf (e.g. the constant tables, for which the only real golf was a `<2` instead of `==1`). Over 100 bytes down though, but I'm sure there's still more to be gotten.

Input/output is also string of bits to hex string.
> 9 votes

# Answer
## C, ~~1913~~ 1822 bytes (just for fun)

```
#define q unsigned
#define D(a,c)x->b[1]+=a>1<<33-1-c;a+=c;
#define R(a,b)(a>>b|a<<32-b)
#define S(x,a,b,c)(R(x,a)^R(x,b)^x>>c)
#define W(i,a)i=x->s[a];
#define Y(i,a)x->s[a]+=i;
#define Z(_,a)h[i+a*4]=x->s[a]>>(24-i*8);
#define J(a)x->d[a]
#define T(_,a)x->d[63-a]=x->b[a/4]>>8*(a%4);
#define Q(_,a)x->s[a]=v[a];
#define A(F)F(a,0)F(b,1)F(c,2)F(d,3)F(e,4)F(f,5)F(g,6)F(h,7)
#define G(a,b)for(i=a;i<b;++i)
typedef struct{q char d[64];q l,b[2],s[8];}X;q k[]={0x428a2f98,0x71374491,0xb5c0fbcf,0xe9b5dba5,0x3956c25b,0x59f111f1,0x923f82a4,0xab1c5ed5,0xd807aa98,0x12835b01,0x243185be,0x550c7dc3,0x72be5d74,0x80deb1fe,0x9bdc06a7,0xc19bf174,0xe49b69c1,0xefbe4786,0x0fc19dc6,0x240ca1cc,0x2de92c6f,0x4a7484aa,0x5cb0a9dc,0x76f988da,0x983e5152,0xa831c66d,0xb00327c8,0xbf597fc7,0xc6e00bf3,0xd5a79147,0x06ca6351,0x14292967,0x27b70a85,0x2e1b2138,0x4d2c6dfc,0x53380d13,0x650a7354,0x766a0abb,0x81c2c92e,0x92722c85,0xa2bfe8a1,0xa81a664b,0xc24b8b70,0xc76c51a3,0xd192e819,0xd6990624,0xf40e3585,0x106aa070,0x19a4c116,0x1e376c08,0x2748774c,0x34b0bcb5,0x391c0cb3,0x4ed8aa4a,0x5b9cca4f,0x682e6ff3,0x748f82ee,0x78a5636f,0x84c87814,0x8cc70208,0x90befffa,0xa4506ceb,0xbef9a3f7,0xc67178f2},v[]={0x6a09e667,0xbb67ae85,0x3c6ef372,0xa54ff53a,0x510e527f,0x9b05688c,0x1f83d9ab,0x5be0cd19};a(X*x){q a,b,c,d,e,f,g,h,i,t,z,m[64];G(z=0,16)m[i]=J(z++)<<24|J(z++)<<16|J(z++)<<8|J(z++);G(i,64)m[i]=S(m[i-2],17,19,10)+m[i-7]+S(m[i-15],7,18,3)+m[i-16];A(W);G(0,64){t=h+(R(e,6)^R(e,11)^R(e,25))+(e&f^~e&g)+k[i]+m[i];z=(R(a,2)^R(a,13)^R(a,22))+(a&b^a&c^b&c);h=g;g=f;f=e;e=d+t;d=c;c=b;b=a;a=t+z;}A(Y)}i(X*x){x->l=*x->b=x->b[1]=0;A(Q)}p(X*x,char*w,q l){q t,i;G(0,l){J(x->l)=w[i];if(++x->l==64){a(x);D(*x->b,512)x->l=0;}}}f(X*x,char*h){q i=x->l;if(i<56){J(i++)=128;G(i,56)J(i)=0;}else{J(i++)=128;G(i,64)J(i)=0;a(x);G(0,56)J(i)=0;}D(*x->b,x->l*8)A(T)a(x);G(0,4){A(Z)}}

```

I took the reference implementation and started golfing, my target was under 2k.

Can be improved if somebody knows how to generate the constants (cube root of primes, I can't think of any golf-friendly way).

Usage:

```
X ctx;
unsigned char hash[32];

i(&ctx);                    // initialize context
p(&ctx,text,strlen(text));  // hash string
f(&ctx,hash);               // get hash

```
> 5 votes

---
Tags: code-golf, hashing
---


# Question
Title: Convert human readable time interval to date components
# Challenge

Write the shortest program that converts a human readable time interval to date components of the form:

```
{±YEARS|±MONTHS|±DAYS|±HOURS|±MINUTES|±SECONDS}

```

# Sample cases

Each test case is two lines, input followed by output:

```
1 year 2 months 3 seconds
{1|2|0|0|0|3}

-2 day 5 year 8months
{5|8|-2|0|0|0}

3day 9     years 4 seconds -5 minute 4 years 4 years -3seconds
{17|0|3|0|-5|1}

```

# Rules

* You can not use `strtotime` or any built-in function that does the whole job.
* Shortest code wins (bytes)
* You can print your output to `stdout` or a file, the result can also be returned by a function, it's up to you
* The token can be in singular or plural form.
* The components may be in a random order
* There may be no white space between the number and the token
* Sign is optional when the time interval is positive (input and output)
* If a component appears more than once the values should be added
* Each component has its own sign
* The components should be handled separately (e.g. `80 minutes` remains as 80 in the output)
* The input is guaranteed to be lower case

Happy Golfing!

# Answer
> 3 votes
# CJam, 60 bytes

After being stuck in the 60's for a long time, I finally managed to squeeze this down to 60 bytes. Good enough! Ship it!

Try it online

Squished:

```
'{0a6*q[{_A,s'-+#)!{"ytdhic"#:I){]'0+iA/I_3$=@+t[}*}*}/'|*'}

```

Expanded and commented:

```
'{              "Add '{' to output";
0a6*            "Initialize time to a list of 6 zeros";
q               "Read the input";
[               "Open an empty numeric character buffer";
{               "For each character in the input:";
  _               "Append the character to the numeric character buffer";
  A,s'-+#)!       "Check if the character is not part of a number";
  {               "If so:";
    "ytdhic"#:I     "Remove the character from the numeric character buffer and
                     convert it to the corresponding time unit index, or -1 if
                     not recognized
                     (Time units are recognized by a character in their name
                     that does not appear before the recognition character
                     in any other name)";
    ){              "Repeat (time unit index + 1) times:";
      ]'0+iA/         "Close the numeric character buffer and parse it as an
                       integer (empty buffer is parsed as 0)";
      I_3$=@+t        "Add the integer to the value of the indexed time unit";
      [               "Open an empty numeric character buffer";
    }*              "End repeat
                     (This is used like an if statement, taking advantage of
                     the fact that iterations after the first have no effect)";
  }*              "End if";
}/              "End for";
'|*             "Insert a '|' between each time unit value (implicitly added to
                 output)";
'}              "Add '}' to output";

```

I initially started using a token-based approach, but that got pretty firmly stuck at... 61 bytes. Sigh. So I totally changed gears and switched to this character-based approach, which is much more interesting anyways.

My parsing method works by adding any valid numeric characters reached (`0`-`9` and `-`) to a buffer and parsing the buffer as an integer when a certain character from one of the time unit names is reached. Those characters are `y`, `t`, `d`, `h`, `i`, and `c`, which all satisfy the conditions that they appear in a time unit name and don't appear before the recognition character in any other time unit name. In other words, when one of these time unit recognition characters is reached, the numeric buffer will be filled with the last number seen if this actually signals a time unit, or the numeric buffer will be empty if this just appears in, but shouldn't signal, some other time unit. In either case, the numeric buffer is parsed as an integer, or 0 if it was empty, and this is added to the corresponding time unit value. Thus recognition characters appearing in other time units after their recognition character have no effect.

Other crazy hacks include:

* Abusing loops so numeric characters are left on the stack (which acts as the numeric character buffer) "for free."
* Repeating a block zero or multiple times instead of conditionally because the loop is more compact than an if statement, and iterations after the first have no effect.

---

For anyone curious about my token-based solution that got stuck at 61 bytes, I'll post it here as well. I never got around to expanding or commenting it, though.

### CJam, 61 bytes

```
'{0a6*q'm-'{,64/~m*{:X/XS**}/S%2/{~0="yodhis"#_3$=@i+t}/'|*'}

```

# Answer
> 10 votes
# Perl: 61 characters

Thanks to @nutki.

```
s/-?\d+ *m?(.)/$$1+=$&/ge;$_="{y|o|d|h|i|s}";s/\w/${$&}+0/ge

```

Sample run:

```
bash-4.3$ perl -pe 's/-?\d+ *m?(.)/$$1+=$&/ge;$_="{y|o|d|h|i|s}";s/\w/${$&}+0/ge' <<< '1 year 2 months 3 seconds'
{1|2|0|0|0|3}

bash-4.3$ perl -pe 's/-?\d+ *m?(.)/$$1+=$&/ge;$_="{y|o|d|h|i|s}";s/\w/${$&}+0/ge' <<< '-2 day 5 year 8months'
{5|8|-2|0|0|0}

bash-4.3$ perl -pe 's/-?\d+ *m?(.)/$$1+=$&/ge;$_="{y|o|d|h|i|s}";s/\w/${$&}+0/ge' <<< '3day 9     years 4 seconds -5 minute 4 years 4 years -3seconds'
{17|0|3|0|-5|1}

```

### My poor efforts: ~~78~~ 77 characters

```
s/([+-]?\d+) *(..)/$a{$2}+=$1/ge;$_="{ye|mo|da|ho|mi|se}";s/\w./$a{$&}||0/ge

```

# Answer
> 6 votes
# Python 2, 99 bytes

```
import re
f=lambda I:"{%s}"%"|".join(`sum(map(int,re.findall("(-?\d+) *m?"+t,I)))`for t in"yodhis")

```

This is a lambda function which takes in a string and simply uses a regex to extract the necessary numbers.

Thanks to Martin for pointing out that `\s*` could just be `<space>*`. It's easy to forget that regexes match spaces literally...

# Answer
> 5 votes
# Ruby, ~~119~~ ~~106~~ ~~86~~ ~~85~~ 84 bytes

One byte saved thanks to Sp3000.

```
->i{?{+"yodhis".chars.map{|w|s=0;i.scan(/-?\d+(?= *m?#{w})/){|n|s+=n.to_i};s}*?|+?}}

```

This is an unnamed function, which takes the input as a string, and returns the result (also as a string). You can test it by assigning it to `f`, say, and calling it like

```
f["3day 9     years 4 seconds -5 minute 4 years 4 years -3seconds"]

```

# Answer
> 4 votes
# JavaScript 100 ~~105 112~~

**Edit** Adding template strings (first implemented dec 2014, so valid for this challenge) - at time I was not aware of them

**Edit** Eureka, at last I got the meaning of `m?` in all the other answers!

```
s=>s.replace(/(-?\d+) *m?(.)/g,(a,b,c)=>o['yodhis'.search(c)]-=-b,o=[0,0,0,0,0,0])&&`{${o.join`|`}}`

```

**Test**

```
F=
s=>s.replace(/(-?\d+) *m?(.)/g,(a,b,c)=>o['yodhis'.search(c)]-=-b,o=[0,0,0,0,0,0])&&`{${o.join`|`}}`

;['1 year 2 months 3 seconds','-2 day 5 year 8months'
,'3day 9     years 4 seconds -5 minute 4 years 4 years -3seconds']
.forEach(i=>console.log(i,F(i)))
```

# Answer
> 3 votes
# R, 197 bytes

I realize this isn't a competitive entry at all, I mostly just wanted to come up with a solution in R. Any help shortening this is of course welcome.

```
function(x){s="{";for(c in strsplit("yodhis","")[[1]])s=paste0(s,ifelse(c=="y","","|"),sum(as.numeric(gsub("[^0-9-]","",str_extract_all(x,perl(paste0("(-?\\d+) *m?",c)))[[1]]))));s=paste0(s,"}");s}

```

Like Martin's answer, this is an unnamed function. To call it, assign it to `f` and pass a string.

This is pretty hideous, so let's take a look at an un-golfed version.

```
function(x) {
    s <- "{"
    for (c in strsplit("yodhis", "")[[1]]) {
        matches <- str_extract_all(x, perl(paste0("(-?\\d+) *m?", c)))[[1]]
        nums <- gsub("[^0-9-]", "", matches)
        y <- sum(as.numeric(nums))
        s <- paste0(s, ifelse(c == "y", "", "|"), y)
    }
    s <- paste0(s, "}")
    return(s)
}

```

Based on the structure alone it's easy to see what's going on, even if you aren't too familiar with R. I'll elaborate on some of the stranger looking aspects.

`paste0()` is how R combines strings with no separator.

The `str_extract_all()` function comes from Hadley Wickham's `stringr` package. R's handling of regular expressions in the base package leaves much to be desired, which is where `stringr` comes in. This function returns a list of regular expression matches in the input string. Notice how the regex is surrounded in a function `perl()`--this is just saying that the regex is Perl-style, not R-style.

`gsub()` does a find-and-replace using a regex for each element of the input vector. Here we're telling it to replace everything that isn't a number or minus sign with an empty string.

And there you have it. Further explanation will be gladly provided upon request.

# Answer
> 2 votes
# Cobra - 165

```
def f(s='')
    l=int[](6)
    for i in 6,for n in RegularExpressions.Regex.matches(s,'(-?\\d+) *m?['yodhis'[i]]'),l[i]+=int.parse('[n.groups[1]]')
    print'{[l.join('|')]}'

```

# Answer
> 2 votes
# C++14, 234 229 bytes

***Edit:*** cut down 5 bytes by using old style declaration instead of `auto`.

I know the winner has already been chosen, and that this would be the longest submission so far, but I just had to post a C++ solution, because I bet nobody expected one at all :)

To be honest, I'm pretty much happy with how short it turned out to be (by C++ measurements, of course), and I'm sure it can't get any shorter that this (with just one remark, see below). It is also quite a nice collection of features new to C++11/14.

No third-party libraries here, only standard library is used.

The solution is in a form of lambda function:

```
[](auto&s){sregex_iterator e;auto r="{"s;for(auto&t:{"y","mo","d","h","mi","s"}){int a=0;regex g("-?\\d+ *"s+t);decltype(e)i(begin(s),end(s),g);for_each(i,e,[&](auto&b){a+=stoi(b.str());});r+=to_string(a)+"|";}r.back()='}';s=r;};

```

Ungolfed:

```
[](auto&s)
{
    sregex_iterator e;
    auto r="{"s;
    for(auto&t:{"y","mo","d","h","mi","s"})
    {
        int a=0;
        regex g("-?\\d+\\s*"s+t);
        decltype(e)i(begin(s),end(s),g);
        for_each(i,e,[&](auto&b)
        {
            a+=stoi(b.str());
        });
        r+=to_string(a)+"|";
    }
    r.back()='}';
    s=r;
}

```

For some reason, I had to write

```
regex g("-?\\d+\\s*"s+t);
decltype(e)i(begin(s),end(s),g);

```

instead of just

```
decltype(e)i(begin(s),end(s),regex("-?\\d+\\s*"s+t));

```

because the iterator would only return one match if I pass in a temporary object. This doesn't seem right to me, so I wonder if there's a problem with GCC's regex implementation.

Full test file (compiled with GCC 4.9.2 with `-std=c++14`):

```
#include <iostream>
#include <string>
#include <regex>

using namespace std;

int main()
{
    string arr[] = {"1 year 2 months 3 seconds",
                    "-2 day 5 year 8months",
                    "3day 9     years 4 seconds -5 minute 4 years 4 years -3seconds"};
    for_each(begin(arr), end(arr), [](auto&s){sregex_iterator e;auto r="{"s;for(auto&t:{"y","mo","d","h","mi","s"}){int a=0;auto g=regex("-?\\d+ *"s+t);decltype(e)i(begin(s),end(s),g);for_each(i,e,[&](auto&b){a+=stoi(b.str());});r+=to_string(a)+"|";}r.back()='}';s=r;});
    for(auto &s : arr) {cout << s << endl;}
}

```

Output:

```
{1|2|0|0|0|3}
{5|8|-2|0|0|0}
{17|0|3|0|-5|1}

```

# Answer
> 0 votes
# PHP, 141 bytes

```
preg_match_all("#(.?\d+)\s*m?(.)#",$argv[1],$m);$r=[0,0,0,0,0,0];foreach($m[1]as$i=>$n)$r[strpos(yodhis,$m[2][$i])]+=$n;echo json_encode($r);

```

takes input from first command line argument; uses `[,]` for output instead of `{|}`. Run with `-r`.

**breakdown**

```
preg_match_all("#(.?\d+)\s*m?(.)#",$argv[1],$m);    # find intervals.
# (The initial dot will match the sign, the space before the number or a first digit.)
$r=[0,0,0,0,0,0];                   # init result
foreach($m[1]as$i=>$n)              # loop through matches
    $r[strpos(yodhis,$m[2][$i])]+=$n;   # map token to result index, increase value
echo json_encode($r);               # print result: "[1,2,3,4,5,6]"

```

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


# Question
Title: Fill the rows, columns, and diagonals of an NxN grid with 1 through N
# Task

Given input N, generate and output an NxN grid where each row, column and the two diagonals contain the numbers 1 to `N` (or 0 to `N`−1 if that's easier).

## Input

The input is a positive integer `N`. It represents the number of columns and rows in the grid. For this problem, you can assume `N` will be a reasonable size, `4 ≤ N ≤ 8` or (`1 ≤ N ≤ 8` if you go for the bonus below).

## Output

The output will be the `N`×`N` grid. In the grid, each row only contains the numbers 1 to `N`, each column only contains the numbers 1 to `N`, and the two diagonals of length `N` (the one from `(0,0)` to `(N-1,N-1)` and the one from `(0,N-1)` to `(N-1, 0)`) only contain the numbers 1 to `N`. You can use the numbers 0 to `N−1`. For each `N`, there are many possible solutions, you only need to print the first one you find. You don't need to print spaces between the numbers.

## Constraints

Your code should be able to repeatably produce results for `N >= 7`. That is, if you're able to actually run and get a solution for `N = 7` from your code each time, you're good. In terms of an absolute limit, your code should be able to solve for `N = 7` in under 10 minutes each time you run it (i.e., if you depend on random numbers, for the worst case, your code should still finish in under 10 minutes for `N = 7`).

## Examples

* **Input:** `4`

**One possible output:**

```
1 2 3 4
3 4 1 2
4 3 2 1
2 1 4 3

```
* **Input:** `5`

**One possible output:**

```
1 2 3 4 5
5 3 1 2 4
2 5 4 3 1
4 1 2 5 3
3 4 5 1 2

```
* **Input:** `8`

**One possible output:**

```
1 2 3 4 5 6 7 8
2 3 1 5 4 8 6 7
4 1 2 3 7 5 8 6
6 4 7 8 1 2 3 5
7 5 8 2 6 3 4 1
5 8 4 6 2 7 1 3
8 7 6 1 3 4 5 2
3 6 5 7 8 1 2 4

```

## Scoring

This is , so the shortest code in bytes wins, with one exception. For inputs `N = 2, 3` there are no valid solutions. If your code can handles this (run to completion without outputting anything for these cases, or outputting an empty string), and still handles `N = 1` (outputs `1` for it), take 20% off your byte count.

# Answer
# Python 3, ~~275~~ 260 Bytes\*0.8= ~~220~~ 208 Bytes

Recursive/backtracking approach. `R` is the recursive function, `l` is the coLumn, `w` is the roW, `K` is the next entry.

I chose to put it in a 1d array and pretty-print it at the end to make indices simpler.

```
r=range
n=(int)(input())
def R(A,I):
 l=I%n;w=I//n
 if I==n*n:[print(A[i*n:i*n+n])for i in r(n)];exit()
 for K in r(n):
  if all([all([A[i*n+l]!=K,w!=l or A[i+n*i]!=K,w!=n-1-l or A[n*i+n-i-1]!=K])for i in r(w)]+[A[w*n+i]!=K for i in r(l)]):R(A+[K],I+1)
R([],0)

```

Ungolfed version:

```
def Recurse(A,I,n):
 column=I%n
 row=I//n
 if I==n*n:
     [print(*A[i*n:i*n+n])for i in range(n)] # output
     exit() #end recursion
 for K in range(n):
    # try every possibility. Test if they satisfy the constraints:
    # if so, move the index on. If none of them do, we'll return None.
    # if a child returns None, we'll move onto the next potential child:
    # if all of them fail it will backtrack to the next level.
    if all([
        all([
            A[i*n+column]!=K, # column constraint
            row!=column or A[i+n*i]!=K, # diagonal constraint
            row!=n-1-column or A[n*i+n-i-1]!=K # antidiagonal constraint
            ]) for i in range(row)
        ]+[
            A[row*n+i]!=K for i in range(column) # row constraint
            ]):
        Recurse(A+[K],I+1,n)

Recurse([],0,(int)(input()))

```
> 3 votes

# Answer
# Funciton, non-competitive

# UPDATE! Massive performance improvement! *n* = 7 now completes in under 10 minutes! See explanation at bottom!

This was good fun to write. This is a brute-force solver for this problem written in Funciton. Some factoids:

* It accepts an integer on STDIN. Any extraneous whitespace breaks it, including a newline after the integer.
* It uses the numbers 0 to *n* − 1 (not 1 to *n*).
* It fills the grid “backwards”, so you get a solution where the bottom row reads `3 2 1 0` rather than where the top row reads `0 1 2 3`.
* It correctly outputs `0` (the only solution) for *n* = 1.
* Empty output for *n* = 2 and *n* = 3.
* When compiled to an exe, takes about 8¼ minutes for *n* = 7 (was about one hour before the performance improvement). Without compiling (using the interpreter) it takes about 1.5 times as long, so using the compiler is worth it.
* As a personal milestone, this is the first time I wrote a whole Funciton program without first writing the program in a pseudocode language. I did write it in actual C# first though.
* (However, this is not the first time I made a change to massively improve the performance of something in Funciton. The first time I did that was in the factorial function. Swapping the order of the operands of the multiplication made a huge difference because of how the multiplication algorithm works. Just in case you were curious.)

Without further ado:

```
            ┌────────────────────────────────────┐           ┌─────────────────┐
            │                                  ┌─┴─╖ ╓───╖ ┌─┴─╖   ┌──────┐    │
            │                    ┌─────────────┤ · ╟─╢ Ӂ ╟─┤ · ╟───┤      │    │
            │                    │             ╘═╤═╝ ╙─┬─╜ ╘═╤═╝ ┌─┴─╖    │    │
            │                    │               └─────┴─────┘   │ ♯ ║    │    │
            │                  ┌─┴─╖                             ╘═╤═╝    │    │
            │     ┌────────────┤ · ╟───────────────────────────────┴───┐  │    │
          ┌─┴─╖ ┌─┴─╖   ┌────╖ ╘═╤═╝ ┌──────────┐         ┌────────┐ ┌─┴─╖│    │
          │ ♭ ║ │ × ╟───┤ >> ╟───┴───┘        ┌─┴─╖       │ ┌────╖ └─┤ · ╟┴┐   │
          ╘═╤═╝ ╘═╤═╝   ╘══╤═╝          ┌─────┤ · ╟───────┴─┤ << ╟─┐ ╘═╤═╝ │   │
    ┌───────┴─────┘ ┌────╖ │            │     ╘═╤═╝         ╘══╤═╝ │   │   │   │
    │     ┌─────────┤ >> ╟─┘            │       └───────┐      │   │   │   │   │
    │     │         ╘══╤═╝            ┌─┴─╖   ╔═══╗   ┌─┴─╖ ┌┐ │   │ ┌─┴─╖ │   │
    │     │           ┌┴┐     ┌───────┤ ♫ ║ ┌─╢ 0 ║ ┌─┤ · ╟─┤├─┤   ├─┤ Ӝ ║ │   │
    │     │   ╔═══╗   └┬┘     │       ╘═╤═╝ │ ╚═╤═╝ │ ╘═╤═╝ └┘ │   │ ╘═╤═╝ │   │
    │     │   ║ 1 ╟───┬┘    ┌─┴─╖       └───┘ ┌─┴─╖ │   │      │   │   │ ┌─┴─╖ │
    │     │   ╚═══╝ ┌─┴─╖   │ ɓ ╟─────────────┤ ? ╟─┘   │    ┌─┴─╖ │   ├─┤ · ╟─┴─┐
    │     ├─────────┤ · ╟─┐ ╘═╤═╝             ╘═╤═╝   ┌─┴────┤ + ╟─┘   │ ╘═╤═╝   │
  ┌─┴─╖ ┌─┴─╖       ╘═╤═╝ │ ╔═╧═╕ ╔═══╗ ┌───╖ ┌─┴─╖ ┌─┴─╖    ╘═══╝     │   │     │
┌─┤ · ╟─┤ · ╟───┐     └┐  └─╢   ├─╢ 0 ╟─┤ ⌑ ╟─┤ ? ╟─┤ · ╟──────────────┘   │     │
│ ╘═╤═╝ ╘═╤═╝   └───┐ ┌┴┐   ╚═╤═╛ ╚═╤═╝ ╘═══╝ ╘═╤═╝ ╘═╤═╝                  │     │
│   │   ┌─┴─╖ ┌───╖ │ └┬┘   ┌─┴─╖ ┌─┘           │     │                    │     │
│ ┌─┴───┤ · ╟─┤ Җ ╟─┘  └────┤ ? ╟─┴─┐   ┌─────────────┘                    │     │
│ │     ╘═╤═╝ ╘═╤═╝         ╘═╤═╝   │   │╔════╗╔════╗                      │     │
│ │       │  ┌──┴─╖ ┌┐   ┌┐ ┌─┴─╖ ┌─┴─╖ │║ 10 ║║ 32 ║    ┌─────────────────┘     │
│ │       │  │ << ╟─┤├─┬─┤├─┤ · ╟─┤ · ╟─┘╚══╤═╝╚╤═══╝ ┌──┴──┐                    │
│ │       │  ╘══╤═╝ └┘ │ └┘ ╘═╤═╝ ╘═╤═╝     │ ┌─┴─╖ ┌─┴─╖ ┌─┴─╖                  │
│ │     ┌─┴─╖ ┌─┴─╖  ┌─┴─╖  ┌─┴─╖ ╔═╧═╕     └─┤ ? ╟─┤ · ╟─┤ % ║                  │
│ └─────┤ · ╟─┤ · ╟──┤ Ӂ ╟──┤ ɱ ╟─╢   ├───┐   ╘═╤═╝ ╘═╤═╝ ╘═╤═╝                  │
│       ╘═╤═╝ ╘═╤═╝  ╘═╤═╝  ╘═══╝ ╚═╤═╛ ┌─┴─╖ ┌─┴─╖   │     └────────────────────┘
│         └─────┤      │            └───┤ ‼ ╟─┤ ‼ ║   │        ┌──────┐
│               │      │                ╘═══╝ ╘═╤═╝   │        │ ┌────┴────╖
│               │      │                      ┌─┴─╖   │        │ │ str→int ║
│               │      └──────────────────────┤ · ╟───┴─┐      │ ╘════╤════╝
│               │          ┌─────────╖        ╘═╤═╝     │    ╔═╧═╗ ┌──┴──┐
│               └──────────┤ int→str ╟──────────┘       │    ║   ║ │ ┌───┴───┐
│                          ╘═════════╝                  │    ╚═══╝ │ │ ┌───╖ │
└───────────────────────────────────────────────────────┘          │ └─┤ × ╟─┘
           ┌──────────────┐                                  ╔═══╗ │   ╘═╤═╝
╔════╗     │ ╓───╖ ┌───╖  │                              ┌───╢ 0 ║ │   ┌─┴─╖ ╔═══╗
║ −1 ║     └─╢ Ӝ ╟─┤ × ╟──┴──────┐                       │   ╚═╤═╝ └───┤ Ӂ ╟─╢ 0 ║
╚═╤══╝       ╙───╜ ╘═╤═╝         │                       │   ┌─┴─╖     ╘═╤═╝ ╚═══╝
┌─┴──╖ ┌┐ ┌───╖ ┌┐ ┌─┴──╖ ╔════╗ │                       │ ┌─┤   ╟───────┴───────┐
│ << ╟─┤├─┤ ÷ ╟─┤├─┤ << ║ ║ −1 ║ │                       │ │ └─┬─╜ ┌─┐ ┌─────┐   │
╘═╤══╝ └┘ ╘═╤═╝ └┘ ╘═╤══╝ ╚═╤══╝ │                       │ │   └───┴─┘ │   ┌─┴─╖ │
  │         └─┘      └──────┘    │                       │ └───────────┘ ┌─┤ ? ╟─┘
  └──────────────────────────────┘         ╓───╖         └───────────────┘ ╘═╤═╝
                               ┌───────────╢ Җ ╟────────────┐                │
      ┌────────────────────────┴───┐       ╙───╜            │
      │                          ┌─┴────────────────────┐ ┌─┴─╖
    ┌─┴─╖                      ┌─┴─╖                  ┌─┴─┤ · ╟──────────────────┐
    │ ♯ ║ ┌────────────────────┤ · ╟───────┐          │   ╘═╤═╝                  │
    ╘═╤═╝ │                    ╘═╤═╝       │          │     │              ┌───╖ │
┌─────┴───┘    ┌─────────────────┴─┐   ┌───┴───┐    ┌─┴─╖ ┌─┴─╖          ┌─┤ × ╟─┴─┐
│              │                 ┌─┴─╖ │   ┌───┴────┤ · ╟─┤ · ╟──────────┤ ╘═╤═╝   │
│              │ ┌───╖ ┌───╖  ┌──┤ · ╟─┘ ┌─┴─┐      ╘═╤═╝ ╘═╤═╝        ┌─┴─╖ │     │
│         ┌────┴─┤ ♭ ╟─┤ × ╟──┘  ╘═╤═╝   │ ┌─┴─╖ ┌───╖└┐ ┌──┴─╖      ┌─┤ · ╟─┘     │
│         │      ╘═══╝ ╘═╤═╝ ┌───╖ │     │ │ × ╟─┤ Ӝ ╟─┴─┤ ÷% ╟─┐    │ ╘═╤═╝ ┌───╖ │
│   ┌─────┴───┐     ┌────┴───┤ Ӝ ╟─┴─┐   │ ╘═╤═╝ ╘═╤═╝   ╘══╤═╝ │    │   └───┤ Ӝ ╟─┘
│ ┌─┴─╖ ┌───╖ │     │ ┌────╖ ╘═╤═╝   │   └───┘   ┌─┴─╖      │   │    └────┐  ╘═╤═╝
│ │ × ╟─┤ Ӝ ╟─┘     └─┤ << ╟───┘   ┌─┴─╖ ┌───────┤ · ╟───┐  │ ┌─┴─╖ ┌───╖ │    │
│ ╘═╤═╝ ╘═╤═╝         ╘══╤═╝   ┌───┤ + ║ │       ╘═╤═╝   ├──┴─┤ · ╟─┤ × ╟─┘    │
└───┤     └────┐ ╔═══╗ ┌─┴─╖ ┌─┴─╖ ╘═╤═╝ │ ╔═══╗ ┌─┴─╖ ┌─┴─╖  ╘═╤═╝ ╘═╤═╝      │
  ┌─┴─╖ ┌────╖ │ ║ 0 ╟─┤ ? ╟─┤ = ║  ┌┴┐  │ ║ 0 ╟─┤ ? ╟─┤ = ║    │     │ ┌────╖ │
  │ × ╟─┤ << ╟─┘ ╚═══╝ ╘═╤═╝ ╘═╤═╝  └┬┘  │ ╚═══╝ ╘═╤═╝ ╘═╤═╝    │     └─┤ << ╟─┘
  ╘═╤═╝ ╘═╤══╝ ┌┐     ┌┐ │     │     └───┘       ┌─┴─╖   ├──────┘       ╘═╤══╝
    │     └────┤├──┬──┤├─┘     ├─────────────────┤ · ╟───┘                │
    │          └┘┌─┴─╖└┘       │     ┌┐   ┌┐     ╘═╤═╝ ┌┐   ┌┐            │
    └────────────┤ · ╟─────────┘   ┌─┤├─┬─┤├─┐     └───┤├─┬─┤├────────────┘
                 ╘═╤═╝             │ └┘ │ └┘ │         └┘ │ └┘
                   └───────────────┘    │    └────────────┘

```

# Explanation of the first version

The first version took about an hour to solve *n* = 7. The following explains mostly how this slow version worked. At the bottom I will explain what change I made to get it to under 10 minutes.

## An excursion into bits

This program needs bits. It needs lots of bits, and it needs them in all the right places. Experienced Funciton programmers already know that if you need *n* bits, you can use the formula

which in Funciton can be expressed as

When doing my performance optimization, it occurred to me that I can calculate the same value much faster using this formula:

I hope you’ll forgive me that I didn’t update all the equation graphics in this post accordingly.

Now, let’s say you don’t want a contiguous block of bits; in fact, you want *n* bits at regular intervals every *k*-th bit, like so:

```
                                 LSB
                                  ↓
00000010000001000000100000010000001
                            └──┬──┘
                               k

```

The formula for this is fairly straight-forward once you know it:

In the code, the function `Ӝ` takes values *n* and *k* and calculates this formula.

## Keeping track of used numbers

There are *n*² numbers in the final grid, and each number can be any of *n* possible values. In order to keep track of which numbers are permitted in each cell, we maintain a number consisting of *n*³ bits, in which a bit is set to indicate that a particular value is taken. Initially this number is 0, obviously.

The algorithm begins in the bottom-right corner. After “guessing” the first number is a 0, we need to keep track of the fact that the 0 is no longer permitted in any cell along the same row, column and diagonal:

```
LSB                               (example n=5)
 ↓
 10000 00000 00000 00000 10000
 00000 10000 00000 00000 10000
 00000 00000 10000 00000 10000
 00000 00000 00000 10000 10000
 10000 10000 10000 10000 10000
                             ↑
                            MSB

```

To this end, we calculate the following four values:

* **Current row:** We need *n* bits every *n*-th bit (one per cell), and then shift it to the current row *r*, remembering every row contains *n*² bits:
* **Current column:** We need *n* bits every *n*²-th bit (one per row), and then shift it to the current column *c*, remembering every column contains *n* bits:
* **Forward diagonal:** We need *n* bits every... (did you pay attention? Quick, figure it out!)... *n*(*n*+1)-th bit (well done!), but only if we’re actually on the forward diagonal:
* **Backward diagonal:** Two things here. First, how do we know if we’re on the backward diagonal? Mathematically, the condition is *c* = (*n* − 1) − *r*, which is the same as *c* = *n* \+ (−*r* − 1). Hey, does that remind you of something? That’s right, it’s two’s complement, so we can use bitwise negation (very efficient in Funciton) instead of the decrement. Second, the formula above assumes that we want the least significant bit to be set, but in the backward diagonal we don’t, so we have to shift it up by... do you know?... That’s right, *n*(*n* − 1).

This is also the only one where we potentially divide by 0 if *n* = 1. However, Funciton doesn’t care. 0 ÷ 0 is just 0, don’t you know?

In the code, the function `Җ` (the bottom one) takes *n* and an *index* (from which it calculates *r* and *c* by division and remainder), calculates these four values and `or`s them together.

## The brute-force algorithm

The brute-force algorithm is implemented by `Ӂ` (the function at the top). It takes *n* (the grid size), *index* (where in the grid we’re currently placing a number), and *taken* (the number with *n*³ bits telling us which numbers we can still place in each cell).

This function returns a sequence of strings. Each string is a full solution to the grid. It’s a complete solver; it would return all solutions if you let it, but it returns them as a lazy-evaluated sequence.

* If *index* has reached 0, we’ve successfully filled the whole grid, so we return a sequence containing the empty string (a single solution that covers none of the cells). The empty string is `0`, and we use the library function  to turn that into a single-element sequence.
* The check described under *performance improvement* below happens here.
* If *index* has not yet reached 0, we decrement it by 1 to get the index at which we now need to place a number (call that *ix*).

We use  to generate a lazy sequence containing the values from 0 to *n* − 1.

Then we use `ɓ` (monadic bind) with a lambda that does the following in order:

+ First look at the relevant bit in *taken* to decide whether the number is valid here or not. We can place a number *i* if and only if *taken* & (1 \<\< (*n* × *ix*) \<\< *i*) isn’t already set. If it is set, return `0` (empty sequence).
    + Use `Җ` to calculate the bits corresponding to the current row, column and diagonal(s). Shift it by *i* and then `or` it onto *taken*.
    + Recursively call `Ӂ` to retrieve all solutions for the remaining cells, passing it the new *taken* and the decremented *ix*. This returns a sequence of incomplete strings; each string has *ix* characters (the grid filled in up to index *ix*).
    + Use `ɱ` (map) to go through the solutions thusly found and use  to concatenate *i* to the end of each. Append a newline if *index* is a multiple of *n*, otherwise a space.

## Generating the result

The main program calls `Ӂ` (the brute forcer) with *n*, *index* = *n*² (remember we fill the grid backwards) and *taken* = 0 (initially nothing is taken). If the result of this is an empty sequence (no solution found), output the empty string. Otherwise, output the first string in the sequence. Note that this means it will evaluate only the first element of the sequence, which is why the solver doesn’t continue until it has found all solutions.

## Performance improvement

(For those who already read the old version of the explanation: the program no longer generates a sequence of sequences that needs to be separately turned into a string for output; it just generates a sequence of strings directly. I’ve edited the explanation accordingly. But that wasn’t the main improvement. Here it comes.)

On my machine, the compiled exe of the first version took pretty much exactly 1 hour to solve *n* = 7. This was not within the given time limit of 10 minutes, so I didn’t rest. (Well, actually, the reason I didn’t rest was because I had this idea on how to massively speed it up.)

The algorithm as described above stops its search and backtracks every time that it encounters a cell in which all the bits in the *taken* number are set, indicating that nothing can be put into this cell.

However, the algorithm will continue to futilely fill the grid *up to* the cell in which all those bits are set. It would be much faster if it could stop as soon as **any** yet-to-be-filled-in cell already has all the bits set, which already indicates that we can never solve the rest of the grid no matter what numbers we put in it. But how do you efficiently check whether **any** cell has its *n* bits set without going through all of them?

The trick starts by adding a single bit per cell to the *taken* number. Instead of what was shown above, it now looks like this:

```
LSB                               (example n=5)
 ↓
 10000 0 00000 0 00000 0 00000 0 10000 0
 00000 0 10000 0 00000 0 00000 0 10000 0
 00000 0 00000 0 10000 0 00000 0 10000 0
 00000 0 00000 0 00000 0 10000 0 10000 0
 10000 0 10000 0 10000 0 10000 0 10000 0
                                       ↑
                                      MSB

```

Instead of *n*³, there are now *n*²(*n* \+ 1) bits in this number. The function that populates the current row/column/diagonal has been changed accordingly (actually, completely rewritten to be honest). That function will still populate only *n* bits per cell though, so the extra bit we just added will always be `0`.

Now, let’s say we are halfway through the calculation, we just placed a `1` in the middle cell, and the *taken* number looks something like this:

```
                 current
LSB              column           (example n=5)
 ↓                 ↓
 11111 0 10010 0 01101 0 11100 0 11101 0
 00011 0 11110 0 01101 0 11101 0 11100 0
 11111 0 11110 0[11101 0]11100 0 11100 0    ← current row
 11111 0 11111 0 11111 0 11111 0 11111 0
 11111 0 11111 0 11111 0 11111 0 11111 0
                                       ↑
                                      MSB

```

As you can see, the top-left cell (index 0) and the middle-left cell (index 10) are now impossible. How do we most efficiently determine this?

Consider a number in which the 0th bit of each cell is set, but only up to the current index. Such a number is easy to calculate using the familiar formula:

What would we get if we added these two numbers together?

```
LSB                                               LSB
 ↓                                                 ↓
 11111 0 10010 0 01101 0 11100 0 11101 0           10000 0 10000 0 10000 0 10000 0 10000 0        ╓───╖
 00011 0 11110 0 01101 0 11101 0 11100 0     ║     10000 0 10000 0 10000 0 10000 0 10000 0            ║
 11111 0 11110 0 11101 0 11100 0 11100 0  ═══╬═══  10000 0 10000 0 00000 0 00000 0 00000 0  ═════   ╓─╜
 11111 0 11111 0 11111 0 11111 0 11111 0     ║     00000 0 00000 0 00000 0 00000 0 00000 0  ═════   ╨
 11111 0 11111 0 11111 0 11111 0 11111 0           00000 0 00000 0 00000 0 00000 0 00000 0          o
                                       ↑                                                 ↑
                                      MSB                                               MSB

```

The result is:

```
             OMG
              ↓
        00000[1]01010 0 11101 0 00010 0 00011 0
        10011 0 00001 0 11101 0 00011 0 00010 0
═════   00000[1]00001 0 00011 0 11100 0 11100 0
═════   11111 0 11111 0 11111 0 11111 0 11111 0
        11111 0 11111 0 11111 0 11111 0 11111 0

```

As you can see, the addition overflows into the extra bit that we added, but only if all the bits for that cell are set! Therefore, all that’s left to do is to mask out those bits (same formula as above, but \<\< *n*) and check if the result is 0:

```
00000[1]01010 0 11101 0 00010 0 00011 0    ╓╖    00000 1 00000 1 00000 1 00000 1 00000 1         ╓─╖ ╓───╖
10011 0 00001 0 11101 0 00011 0 00010 0   ╓╜╙╖   00000 1 00000 1 00000 1 00000 1 00000 1        ╓╜ ╙╖    ║
00000[1]00001 0 00011 0 11100 0 11100 0   ╙╥╥╜   00000 1 00000 1 00000 0 00000 0 00000 0  ═════ ║   ║  ╓─╜
11111 0 11111 0 11111 0 11111 0 11111 0   ╓╜╙╥╜  00000 0 00000 0 00000 0 00000 0 00000 0  ═════ ╙╖ ╓╜  ╨
11111 0 11111 0 11111 0 11111 0 11111 0   ╙──╨─  00000 0 00000 0 00000 0 00000 0 00000 0         ╙─╜   o

```

If it is not zero, the grid is impossible and we can stop.

* **Screenshot** showing solution and running time for *n* = 4 to 7.
> 22 votes

# Answer
# Haskell, 790\*0.80=632 bytes

```
import Data.List
import Control.Monad
import Data.Array
s r=let{h as bs=[(a,b)|a<-as,b<-bs];(&)m k=(\(Just x)->x)$lookup k m;j=Just;n=Nothing;c=[1..r];q=delete;u=h[1..r]c;o=[(s,[u |u<-[h[1..r][c]|c<-c]++[h[r]c|r<-[1..r]]++[zip[1..r][1..r],zip[1..r][r,r-1..1]],s`elem`u])|s<-u];k=foldr(>=>)j;a p d g0=k[t p d2|d2<-q d(g0!p)]g0;t p d g0|not(d`elem`(g0!p))=j g0|[]<-v=n|[d2]<-v=k[t s2 d2|s2<-[(s,delete s$nub(concat(o&s)))|s<-u]&p]g1|True=k[l[s|s<-u,not(d`elem`v)]|u<-o&p]g1 where{v=q d(g0!p);g1=g0//[(p,v)];l[]_=n;l[d3]g=a d3 d g;l _ r=j r};w g0|and[case g0!s of{[_]->True;_->False}|s<-u]=j g0|True=msum[a s' d g0>>=w|d<-g0!s']where(_,s')=minimumBy(\(a,_)(b,_)->compare a b)[(l,s)|s<-u,let v=g0!s;l=length v,l>1]}in fmap(fmap(\[x]->x))$w$array((1,1),(r,r))[((i,j),[1..r])|i<-[1..r],j<-[1..r]]

```

I noticed this problem is very similar to sudoku. I remember an old sudoku solver I wrote in Haskell based on this other one in Python. This is my first code golf post or attempt.

This fulfills the bonus because it returns `Nothing` for `n=2,3` and `Just <result>` for `n>=4`, where `<result>` is a 2D array of integral values.

See here for online interpreter. That code is actually longer than the one in the post because the online interpreter has more strict requirements as to what forms a complete program (rules say a submission can be a function). This submission takes input as a function argument.
> 7 votes

# Answer
## Pyth, 41 bytes

```
#Km.SQQI.AmqQl{d+.TK.Tm,@@Kdd@@Kt-QddQB;K

```

```
#                                      ;   # while(True)
 Km.SQQ                                    # K = random QxQ 2d list
       I                               ;   # if ...
        .A                                 # all of...
          m                          Q     # map(range(Q))...
                +                          # concat
                 .TK                       # transpose K
                    .Tm,@@Kdd@@Kt-Qdd      # diagonals of K
                      m             d      # map(range(d))
                       ,                   # 2-elem list of...
                        @@Kdd              # K[n][n]
                             @@Kt-Qd       # and K[len(K)-n-1][n]
                    .T                     # transpose
           qQl{d                           # subarrays have no dups...
                                      B;   # ... then, break
                                        K  # output final result

```

Brute force ftw!

Since this basically keeps trying random shuffles until it works (well, it keeps trying `n * [shuffle(range(n))]`), it takes a really, really long time. Here are some test runs to give you an idea of how long it takes:

```
llama@llama:~$ time echo 4 | pyth <(echo '#Km.SQQI.AmqQl{d+.TK.Tm,@@Kdd@@Kt-QddQB;K')
[[2, 1, 0, 3], [0, 3, 2, 1], [3, 0, 1, 2], [1, 2, 3, 0]]
echo 4  0.00s user 0.00s system 0% cpu 0.001 total
pyth <(echo '#Km.SQQI.AmqQl{d+.TK.Tm,@@Kdd@@Kt-QddQB;K')  0.38s user 0.00s system 96% cpu 0.397 total

```

That's only 4x4, and it runs in a little under half a second. I'm actually cheating because this is the best out of a few trials—most of them take over a second or two.

I've yet to get a timing on 5x5 (it ran to completion once, but that was in a REPL and I wasn't timing it).

Note that the rule for the time limit was only edited into the question after this answer was posted.
> 4 votes

# Answer
# SWI-Prolog, 326\*0.80 = 260.8 bytes

```
:-use_module(library(clpfd)).
a(N):-l(N,R),m(l(N),R),append(R,V),V ins 1..N,transpose(R,C),d(0,R,D),maplist(reverse,R,S),d(0,S,E),m(m(all_distinct),[R,C,[D,E]]),m(label,R),m(p,R).
l(L,M):-length(M,L).
d(X,[H|R],[A|Z]):-nth0(X,H,A),Y is X+1,(R=[],Z=R;d(Y,R,Z)).
p([H|T]):-write(H),T=[],nl;write(' '),p(T).
m(A,B):-maplist(A,B).

```

*Edit: saved 16 bytes thanks to @Mat*

### Usage

Call `a(5).` in your interpreter for `N=5`. This returns `false` for `N=2` or `N=3`.

Since it uses the CLPFD library this is not pure bruteforce. This program can find a solution for `N=20` in about 15 seconds on my computer.

### Ungolfed + explanations:

This basically works like a Sudoku solver, except that the blocks constraints are replaced with the diagonals constraints.

```
:-use_module(library(clpfd)).      % Import Constraints library

a(N):-
    l(N,R),                        % R is a list of length N
    maplist(l(N),R),               % R contains sublists, each of length N
    append(R,V),
    V ins 1..N,                    % Each value in the matrix is between 1 and N
    maplist(all_distinct,R),       % Values must be different on each row
    transpose(R,C),
    maplist(all_distinct,C),       % Values must be different on each column
    d(0,R,D),
    maplist(reverse,R,S),
    d(0,S,E),
    all_distinct(D),               % Values must be different on the diagonal
    all_distinct(E),               % Values must be different on the "anti"-diagonal
    maplist(label,R),              % Affects actual values to each element
    maplist(p,R).                  % Prints each row

l(L,M):-length(M,L).               % True if L is the length of M

d(X,[H|R],[A|Z]):-nth0(X,H,A),Y is X+1,(R=[],Z=R;d(Y,R,Z)). % True if the third argument is the diagonal of the second argument

p([H|T]):-write(H),T=[],nl;write(' '),p(T).  % Prints a row separated by spaces and followed by a new line

```
> 3 votes

# Answer
# CJam, 87 bytes - 20% bonus = 69.6 bytes

```
qi__"@I/l
ŤˏūȻ
܀ᅀ൹৽჈͚
㑢鴑慚菥洠㬝᚜
"N/=:i0+\,m!f=`1LL](4e<=

```

Hardcodes the answers. Contains some unprintables. Works for `N = 1` through `N = 8`.

Basically, each line in that mysterious string contains indices into the list of permutations of `range(N)`, encoded as Unicode characters.

`=:i0+\,m!f=` indexes into the list of permutations, adding a 0 to the end of the list of indices first, representing the bottom row `0 1 2 ... N-1`. For `N < 4`, the resulting 2D array is nonsense.

``1LL]` creates a list `[N, pretty output, 1, "", ""]`. Then, `(4e<=` pops the first element out of this list, `N`, and retrieves the `min(N, 4) % 4`th element from the rest of it. For `N >= 4`, that's the output, and otherwise it's the special-case outputs for the first three cases.

Try it here.
> 2 votes

# Answer
# C++, 672\*0.80 645\*0.80 = 516 bytes

```
#include <iostream>
int **b,**x,**y,*d,*a,n;
#define R(i) for(i=0;i<n;i++){
#define E(e) e=new int[n];
int f(int c,int r) {int i=0,p=c-1;if(r>=n)return 1;if(c == n + 1)return f(1,r+1);R(i)int m=r==i,s=r+i==n-1;if(!b[r][i]&&!x[r][p]&&!(m&&d[p])&&!(s&&a[p])&&!y[i][p]){b[r][i]=c;x[r][p]=1;y[i][p]=1;if(m)d[p]=1;if(s)a[p]=1;if(f(c+1,r))return 1;b[r][i]=0;x[r][p]=0;y[i][p]=0;if(m)d[p]=0;if(s)a[p]=0;}}return 0;}
int main(){std::cin>>n;int i=0,j=0;b=new int*[n];x=new int*[n];y=new int*[n];E(d);E(a);R(i)E(b[i]);E(x[i]);E(y[i]); d[i]=0;a[i]=0;R(j)b[i][j]=0;x[i][j]=0;y[i][j]=0;}}if(f(1,0)){R(i)R(j)std::cout<<b[i][j];}std::cout<<std::endl;}}}

```

Try it online here

Since a couple answers have already been posted, I thought I would post the golfed version of the code I used to generated the output for the examples. This is my first time answering a , so all feedback is welcomed. :)

## Ungolfed + explanations:

Essentially, the code is brute-forcing a solution. It starts in the first row, with 0. It starts in the first spot, if that spots passes all the checks, it moves onto to the next number. If it fills the row, it moves onto the next row. If it's done all of the rows, that means a solution has been found. If the spot doesn't pass all of the checks, it moves onto the next spot. If it's done the row, then it backtracks, as a number in one of the previous rows prevents a solution from being possible.

```
#include <iostream>

// global variables to save bytes on passing these are function arguments
int **b, // this will store the state of the board
    **x, // if x[i][j] is true, row i of b contains the number j
    **y, // if y[i][j] is true, column i of b contains the number j
    *d,  // if d[i] the main diagonal of b contains i
    *a,  // if a[i] the antidiagonal of a contains i
    n;

// preprocessor to save bytes on repeated statements
#define R(i) for(i=0;i<n;i++){
#define E(e) e=new int[n];

// Recursively looks for a solution
// c - the current number to insert in row r
// r - the current row to fill
int f (int c, int r) {
        int i=0,p=c-1;
        if (r >= n) return 1;             // we are done
        if (c == n + 1) return f(1,r+1);  // this row is full, move to the next row
        R(i)                              // go through the positions in this row,
                                                                            // trying to fill them with c
                int m=r==i, s=r+i==n-1;   // check if this position (r,i) is on ones
                                                                            // of the diagonals
                // if this spot isn't filled, and the row (r), column (i) and diagonals
                // (if it's on the diagonal) doesn't contain the number, fill the spot
                if (!b[r][i] && !x[r][p] && !(m&&d[p]) && !(s&&a[p]) && !y[i][p]) {
                        // fill the spot, and indicate that this row, column and diagonals
                        // contain this number, c
                        b[r][i]=c; x[r][p]=1; y[i][p]=1;
                        if (m) d[p]=1; if (s)a[p]=1;

                        // move onto to the next number, if you find a solution, stop
                        if (f(c+1,r)) return 1;

                        // with this number in this spot, a solution is impossible, clear
                        // its, and clear the checks
                        b[r][i]=0; x[r][p]=0; y[i][p]=0;
                        if (m) d[p]=0; if (s) a[p]=0;
                }
        }

        return 0; // a solution wasn't found
}

int main() {
        std::cin >> n; // get n from STDIN

        // initialization
        int i=0,j=0;
        b=new int*[n]; x=new int*[n]; y=new int*[n];
        E(d); E(a);
        R(i)
                E(b[i]); E(x[i]); E(y[i]); // initialization the inner arrays of b, x, y
                d[i]=0; a[i]=0;

                R(j)
                        b[i][j]=0; x[i][j]=0; y[i][j]=0; // ensure each point is initialized as 0
                }
        }

        // find a solution starting at the top-left corner and print it if it finds one
        if (f(1,0)) {
                R(i)
                        R(j)
                                std::cout<<b[i][j];
                        }
                        std::cout<<std::endl;
                }
        }
}

```
> 0 votes

# Answer
## Clojure, ~~(215 + 258) * 0.8 = 378.4~~ (174 + 255) * 0.8 = 343.2

Split into two parts: error counting `S` and an anonymous function which does the actual optimization via Tabu search.

Update: shorter `S` (counts distinct values within groups), less optimal starting state (no shuffle).

```
(defn S[I n](count(mapcat set(vals(apply merge-with concat(flatten(for[R[(range n)]i R j R v[[(I(+(* n i)j))]]][{[1 i]v}{[2 j]v}(if(= i j){3 v})(if(=(- n 1 i)j){4 v})])))))))
#(if-let[s({1[0]2()3()}%)]s(loop[I(vec(for[R[(range %)]i R j R]i))P #{}](let[[s I](last(sort-by first(for[R[(range(count I))]i R j R I[(assoc(assoc I i(I j))j(I i))]:when(not(P I))][(S I %)I])))](if(=(*(+(* % 2)2)%)s)(partition % I)(recur I(conj P I))))))

```

Single core benchmarks (in milliseconds) for 4, 5, 6 and 7 run 3 times:

```
[[  131.855337   132.96267    138.745981]
 [ 1069.187325  1071.189488  1077.339372]
 [ 9114.736987  9206.65368   9322.656693]
 [36546.309408 36836.567267 36928.346312]]

```

Original:

```
(defn S[I n](apply +(flatten(for[p(concat(partition n I)(for[p(apply map vector(partition n(range(count I))))](map I p))[(take-nth(inc n)I)][(rest(butlast(take-nth(dec n)I)))])](remove #{1}(vals(frequencies p)))))))
#(if-let[s({1[0]2()3()}%)]s(loop[I(vec(flatten(map shuffle(repeat %(range %)))))P #{}](let[[s I](first(sort-by first(for[R[(range(count I))]i R j R I[(assoc(assoc I i(I j))j(I i))]:when(not(P I))][(S I %)I])))](if(= s 0)(partition % I)(recur I(conj P I))))))

```

I wish `S` was shorter, but because it only counts occurrences of more than one / partition the stopping criterion is simple `(= s 0)`.

Many CPU cycles are wasted for non-useful swaps, for example it doesn't improve the score if you swap `2` with `2`, and you don't need to swap numbers between rows as they all have distinct values to begin with.

Benchmarks with Intel 6700K (in milliseconds):

```
(defn S[I n]( ... )
(def F #( ... ))

(defmacro mytime[expr]
  `(let [start# (. System (nanoTime)) ret# ~expr]
     (/ (double (- (. System (nanoTime)) start#)) 1000000.0)))

(pprint(vec(for[n[4 5 6 7]](vec(sort(repeatedly 5 #(mytime (F n)))))))

[[  43.445902   45.895107   47.277399   57.681634    62.594037]
 [ 222.964582  225.467034  240.532683  330.237721   593.686911]
 [2285.417473 2531.331068 3002.597908 6361.591714  8331.809410]
 [3569.62372  4779.062486 5725.905756 7444.941763 14120.796615]]

```

Multithreaded with `pmap`:

```
[[   8.881905  16.343714   18.87262  18.9717890   22.194430]
 [  90.963870 109.719332  163.00299  245.824443  385.365561]
 [ 355.872233 356.439256 1534.31059 2593.482767 3664.221550]
 [1307.727115 1554.00260 2068.35932 3626.878526 4029.543011]]

```
> 0 votes

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