title: Convert between Music clefs

text:
# Question
Title: Convert between Music clefs
*Before you leave, you do not have to understand much musical notation to do this challenge.*

**EXPLANATION**

In standard sheet music, double clefs go across the page serving as reference points to the notes, letting you know what note should be played. If you are not already familiar with the treble and bass clef, here is a description from Wikipedia:

> A clef is a musical symbol used to indicate the pitch of written notes. Placed on one of the lines at the beginning of the stave, it indicates the name and pitch of the notes on that line. This line serves as a reference point by which the names of the notes on any other line or space of the stave may be determined.

In the image above, the top half of the lines is the Treble clef, denoted with a

The bottom half is the Bass clef, denoted with a

As you can see on the treble clef a note on the bottom-most line is an **E**. (I am not counting notes outside of the clef lines for this challenge) On the bass clef, the lowest line is a **G**. To complete this challenge, you must do the following:

**CHALLENGE**

Given an input in one of the following forms (your choice), convert it to the opposite clef. Whether it is the Treble or Bass clef can be a Truthey/Falsey value in your language (not just any two values), e.g.

**F# T** or **F# True** or **F# Treble**

but not

**F# -1** or **F# 4**

Spaces and capitalization are optional, Flats will not appear, and trailing whitespace is not allowed.

```
Input          Expected Output
E   Treble     G
F   Treble     A
F#  Treble     A#
G   Treble     B
G#  Treble     C
A   Treble     C
A#  Treble     C#
B   Treble     D
C   Treble     E
C#  Treble     F
D   Treble     F
D#  Treble     F#
E   Treble     G
F   Treble     A
F#  Treble     A#
G   Bass       E
G#  Bass       F
A   Bass       F
A#  Bass       F#
B   Bass       G
C   Bass       A
C#  Bass       A#
D   Bass       B
D#  Bass       C
E   Bass       C
F   Bass       D
F#  Bass       D#
G   Bass       E
G#  Bass       F
A   Bass       F
A#  Bass       F#

```

Be forewarned, this is not a trivial constant difference challenge. Look closely at the inputs and outputs. If you look at a piano,

the black keys are sharps, denoted by #. Note that there is not an E# or a B#. This means that if you are given **G#** on the Bass clef, instead of returning **E#**, you need to return **F**

This is , so the smallest byte-count wins.

# Answer
# Jelly,  ~~35~~  34 bytes

I have a feeling some arithmetic may win over this method.

```
ØAḣ7µW€ż;€”#$Ẏ
Ç”C4¦”F⁵¦
Ñi+_⁸?4ị¢

```

**Try it online!**

A full program taking 1) the clef indicator `0` or `1` for Bass or Treble respectively and 2) the note; and printing the resulting note.

Would be 31 bytes if `-4` and `4` were acceptable as the clef indicator input values (then `Ñi+_⁸?4ị¢` can become `Ñi+⁸ị¢`) but this has been clarified as not allowed unless -4 is falsey and 4 is truthy, which is not the case for Jelly.

### How?

Builds a keyboard with phantom `B#` and `E#` keys, finds the index of the input, offsets that by `4` in the required direction, indexes back into a keyboard with those phantom keys replaced by their required results (the key above them):

```
ØAḣ7µW€ż;€”#$Ẏ - Link 1, keyboard with phantoms: no inputs
ØA             - alphabet yield        -> ['A', 'B', ..., 'Z']
   7           - literal seven
  ḣ            - head                  -> ['A','B','C','D','E','F','G']
    µ          - new monadic chain, call that K
     W€        - wrap €ach             -> ["A","B","C","D","E","F","G"] ("" being lists of characters)
            $  - last two links as a monad:
          ”#   -   character '#'
        ;€     -   concatenate to €ach -> ["A#","B#","C#","D#","E#","F#","G#"]
       ż       - zip together          -> [["A","A#"],["B","B#"],["C","C#"],["D","D#"],["E","E#"],["F","F#"],["G","G#"]]
             Ẏ - tighten               -> ["A","A#","B","B#","C","C#","D","D#","E","E#","F","F#","G","G#"]

Ç”C4¦”F⁵¦ - Link 2, keyboard with phantoms replaced: no inputs
Ç         - call the last link (1) as a monad  ["A","A#","B","B#","C","C#","D","D#","E","E#","F","F#","G","G#"]
    ¦     - sparse application:
   4      - ...to index: literal four
 ”C       - ...action: character 'C'    -> ["A","A#","B","C","C","C#","D","D#","E","E#","F","F#","G","G#"]
        ¦ - sparse application:
       ⁵  - ...to index: literal ten
     ”F   - ...action: character 'F'    -> ["A","A#","B","C","C","C#","D","D#","E","F","F","F#","G","G#"]

Ñi+_⁸?4ị¢ - Main link: integer, clef (1 Treble / 0 Bass); list of characters, key
                                      e.g. 0; "D#"
Ñ         - next link (1) as a monad (no atom for next link as a nilad, but this works here anyway)
          -                               ["A","A#","B","B#","C","C#","D","D#","E","E#","F","F#","G","G#"]
 i        - first index of key in that    8
      4   - literal four
     ?    - if:
    ⁸     - ...condition: chain's left argument, clef
  +       - ...then: addition
   _      - ...else: subtraction          4
        ¢ - next link as a nilad          ["A","A#","B","C","C","C#","D","D#","E","F","F","F#","G","G#"]
       ị  - index into                    "C"

```
> 5 votes

# Answer
# Befunge, ~~70~~ 64 bytes

```
~0~:70p##~+2%00p+"A"-~7%2++7%:3%2%00g*:10p+"A"+,00g!10g+#@_"#",@

```

Try it online!

The input should be in the form `C# Treble` or `F Bass`, although the clef can simply be the first letter (i.e. `T` or `B`), since the rest of the input is ignored anyway.

**Explanation**

```
~0        Read the note and push a zero (the purpose of this will become apparent later).
~:70p     Read the following sharp or space and write that out as the next instruction.

```

As a result of this code modification, the next sequence of instructions will take one of two forms:

```
##~       The first # jumps over the second, and thus we perform the read instruction.
 #~       But if there's only one #, we'll ending up skipping the read instruction.

```

At this point the stack either contains `note,0,sharp,space` or `note,0,space`.

```
+2%       Add the top two stack items mod 2, returning 1 if we read a sharp, else 0 if not.
00p       Save this 'sharp' boolean for later use.

```

At this point the stack either contains `note,0` or just `note` (with an implicit zero below).

```
+         By adding the top two items, we combine the 0 (if present) onto the note below.
"A"-      We can then subtract 'A' to convert the note into a number in the range 0 to 6.
~7%2+     Read the T/B clef, then mod 7 and add 2, returning 2 or 5 (the conversion offset).
+7%       Add that offset to our note number, then mod 7, to get the converted note number.
:3%2%     Make a dup, and calculate mod 3 mod 2 to determine the special cases (B# or E#).
00g*      Multiply that by the 'sharp' boolean, since we only care if the input was sharp.
:10p      Duplicate and save this special case boolean for later.
+         Now add it to the note number, since the special cases need to be offset by 1.
"A"+,     Then we can finally convert the number back into a character and output it.
00g!10g+  Now we check if the original note was not sharp, or if this was a special case.
#@_       If so, we exit immediately.
"#",@     Otherwise, we output a '#'.

```
> 9 votes

# Answer
# Python 2, 77 bytes

Function which prints to `STDOUT`. `True` converts bass to treble, and `False` converts treble to bass.

```
def f(n,c):N=ord(n[0])-63-4*c;M=-~N%3<1<len(n);print chr((N+M)%7+65)+n[1:2-M]

```

**Try it online!**

Explanation:

* The first statement, `N=ord(n[0])-63-4*c;`, calculates the index (0 to 7) of the new note's letter, disregarding sharps.
    + `ord(N[0])-63-4*c` gets the current letter's index, and adds or subtracts 2 depending on the value of `c` (variable to toggle conversion direction)
* The next statement, `M=-~N%3<1<len(n);` calculates whether or not this variable will need to be adjusted. For example, if the new note is `E`, and the original note had a sharp, this will need to be adjusted to an `F`. The chained inequality works as follows:
    + `-~N%3<1` checks whether the new note's index is in the sequence `3n-1`. This will only yield true for `E` and `B`, the two notes which do not have a sharp.
    + `1<len(n)` checks if the original note had a sharp (this would make the string's length larger than 1). This is necessary as, if there was no sharp, there is no need to adjust the new note letters.
    + This sets the value of `M` to either `True` or `False`, which can be used in calculation as `1` and `0` respectively, so to perform the adjustment we need only add M to N and modulo by 7.
* The final statement creates and outputs the final result.
    + `chr((N+M)%7+65)` adds the adjustment if necessary, then converts the value from an index back to a character.
    + `+n[1:2-M]` will append a sharp symbol if both `M=0` (no adjustment was made) and the original value also had a sharp.
> 3 votes

# Answer
# Perl 5, 56 bytes

```
$_=<>;s/./chr 65+(-4*<>+ord$&)%7/e;s/B#/C/;s/E#/F/;print

```

Reads the note and clef as two lines from STDIN and prints the new note to STDOUT. The clef is `0` for treble and `1` for bass.
> 3 votes

# Answer
# JavaScript (ES6) 74 bytes

Takes input in currying syntax `(note)(clef)` where `clef` is `0` for *bass* and `1` for *treble*.

```
n=>c=>'FC.DAFCGDAEBF'[k=(parseInt(n,36)*15+!n[1]*90+c)%98%13]+(k<5?'#':'')

```

### Demo

```
let f =

n=>c=>'FC.DAFCGDAEBF'[k=(parseInt(n,36)*15+!n[1]*90+c)%98%13]+(k<5?'#':'')

;[1, 0].forEach(c => {
  [ 'E', 'F', 'F#', 'G', 'G#', 'A', 'A#', 'B', 'C', 'C#', 'D', 'D#' ].forEach(n => {
    console.log(
      (n + '  ').slice(0, 3) +
      ['Bass  ', 'Treble'][c] +
      ' --> ' +
      f(n)(c)
    )
  })
})
```

### How?

This is actually slightly less fun than my previous version, but the underlying lookup table is now `F#,C#,(unused),D#,A#,F,C,G,D,A,E,B,F` which allows to shorten the **#** condition while avoiding the *NUL* character trick -- which was a bit border-line, I suppose.

---

# Previous version ~~76~~ 75 bytes

```
n=>c=>'ACCDFF.CDEFGABCDE'[k=parseInt(4*!!n[1]+c+n,21)%24%17]+'\0#'[45>>k&1]

```

### Demo

```
let f =

n=>c=>'ACCDFF.CDEFGABCDE'[k=parseInt(4*!!n[1]+c+n,21)%24%17]+'\0#'[45>>k&1]

;[1, 0].forEach(c => {
  [ 'E', 'F', 'F#', 'G', 'G#', 'A', 'A#', 'B', 'C', 'C#', 'D', 'D#' ].forEach(n => {
    console.log(
      (n + '  ').slice(0, 3) +
      ['Bass  ', 'Treble'][c] +
      ' --> ' +
      f(n)(c)
    )
  })
})
```

### How?

The input **(n, c)** is processed through the following steps:

1. We first evaluate `4 * !!n[1] + c + n` where `!!n[1]` is **true** (coerced to **1**) if the note contains a **#**, and **false** (coerced to **0**) otherwise. The expression `4 * !!n[1] + c` results in a numeric value which is added in front of the string **n**.
2. Implicit step: leading zeros and trailing **#** are ignored by `parseInt()`. For instance, `"5G#"` is actually parsed as `"5G"`.
3. We convert the new string to a decimal value by parsing it as a base-21 quantity.
4. We apply modulo 24.
5. We apply modulo 17.

Below is the summary table for all possible input pairs, along with the expected output. Note that a **#** must be added to the output if the final result is **0**, **2**, **3** or **5**. Hence the use of the binary mask **101101** (**45** in decimal).

```
 n   | c | (1)   | (2)   | (3) | (4) | (5) | Output
-----+---+-------+-------+-----+-----+-----+-------
"E"  | 1 | "1E"  | "1E"  |  35 |  11 |  11 | "G"
"F"  | 1 | "1F"  | "1F"  |  36 |  12 |  12 | "A"
"F#" | 1 | "5F#" | "5F"  | 120 |   0 |   0 | "A#"
"G"  | 1 | "1G"  | "1G"  |  37 |  13 |  13 | "B"
"G#" | 1 | "5G#" | "5G"  | 121 |   1 |   1 | "C"
"A"  | 1 | "1A"  | "1A"  |  31 |   7 |   7 | "C"
"A#" | 1 | "5A#" | "5A"  | 115 |  19 |   2 | "C#"
"B"  | 1 | "1B"  | "1B"  |  32 |   8 |   8 | "D"
"C"  | 1 | "1C"  | "1C"  |  33 |   9 |   9 | "E"
"C#" | 1 | "5C#" | "5C"  | 117 |  21 |   4 | "F"
"D"  | 1 | "1D"  | "1D"  |  34 |  10 |  10 | "F"
"D#" | 1 | "5D#" | "5D"  | 118 |  22 |   5 | "F#"
-----+---+-------+-------+-----+-----+-----+-------
"E"  | 0 | "0E"  | "E"   |  14 |  14 |  14 | "C"
"F"  | 0 | "0F"  | "F"   |  15 |  15 |  15 | "D"
"F#" | 0 | "4F#" | "4F"  |  99 |   3 |   3 | "D#"
"G"  | 0 | "0G"  | "G"   |  16 |  16 |  16 | "E"
"G#" | 0 | "4G#" | "4G"  | 100 |   4 |   4 | "F"
"A"  | 0 | "0A"  | "A"   |  10 |  10 |  10 | "F"
"A#" | 0 | "4A#" | "4A"  |  94 |  22 |   5 | "F#"
"B"  | 0 | "0B"  | "B"   |  11 |  11 |  11 | "G"
"C"  | 0 | "0C"  | "C"   |  12 |  12 |  12 | "A"
"C#" | 0 | "4C#" | "4C"  |  96 |   0 |   0 | "A#"
"D"  | 0 | "0D"  | "D"   |  13 |  13 |  13 | "B"
"D#" | 0 | "4D#" | "4D"  |  97 |   1 |   1 | "C"

```
> 3 votes

# Answer
# Java 8, 119 bytes

```
n->b->(b?"C D E F G A B C# F F# A# C":"F G A B C D E F# A# C D# F").split(" ")["A B C D E F G A#C#D#F#G#".indexOf(n)/2]

```

**Explanation:**

Try it here.

```
n->b->         // Method with String and boolean parameters and String return-type
  (b?          //  If it's Treble:
    "C D E F G A B C# F F# A# C"
               //   Use this String
   :           //  Else (it's Bass):
    "F G A B C D E F# A# C D# F")
               //   Use this String
  .split(" ")  //  Split this String by spaces,
   [           //  and then get the item at index:
    "A B C D E F G A#C#D#F#G#".indexOf(n)
               //   Get the index of the String on the left,
    /2]        //   and divide this by 2
               // End of method (implicit / single-line return-statement)

```
> 2 votes

# Answer
# , 111 bytes

```
function(k,C,N=paste0(LETTERS[2:15%/%2],c("","#")))sub("E#","F",sub("B#","C",N[which(k==N[(4:17+6*C)%%14+1])]))

```

Try it online!

Ungolfed:

```
function(k,C){
  N=paste0(LETTERS[2:15%/%2],c("","#")) # Generate a vector of the notes, including E# and B#
  M=N[(4:17+6*C)%%14+1])                # Create a copy that's cycled either up 4 or down 4
  P=N[which(k==M)]                      # Look up the input note in the complementary vector
  P=sub("B#","C",P)                     # Replace B# with C
  P=sub("E#","F",P)                     # Replace E# with F
}

```
> 0 votes

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


# Question
Title: Number of values between input and next highest square
Given a positive square number as input. Output the number of values between the input and next highest square.

### Example

Input: 1

Output: 2

Reason: The numbers 2 and 3 are between 1 and 4, the next highest square

Input: 4

Output: 4

Reason: The numbers 5, 6, 7, 8 are between 4 and 9

# Answer
> 8 votes
## Jelly, 2 bytes

```
½Ḥ

```

Try it online!

Port of my Mathematica answer (take square root, then double). This is limited to inputs which can be represented exactly as a floating-point number. If that's an issue, the three-byte solution `Æ½Ḥ` works for arbitrary squares (which Dennis posted first but then deleted).

# Answer
> 12 votes
# Brain-Flak, ~~38~~, 22 bytes

```
{([[]](({})))}{}([]<>)

```

Try it online!

I'm *very* proud of this answer. IMO, one of my best brain-flak golfs.

## How does it work?

As many other users have pointed out, the answer is simply *sqrt(n) * 2*. However, calculating the square root in brain-flak is very very nontrivial. Since we know the input will always be a square, we can optimize. So we write a loop that subtracts

```
1, 3, 5, 7, 9...

```

from the input, and track how many times it runs. Once it hits 0, the answer is simply the last number we subtracted minus one.

Originally, I had pushed a counter on to the other stack. However, we can use the main stack itself as a counter, by increasing the stack height.

```
#While TOS (top of stack, e.g. input) != 0:
{

    #Push:
    (

      #The negative of the height of the stack (since we're subtracting)
      [[]]

      #Plus the TOS pushed twice. This is like incrementing a counter by two
      (({}))
    )

#Endwhile
}

#Pop one value off the main stack (or in other words, decrement our stack-counter)
{}

#And push the height of the stack onto the alternate stack
([]<>)

```

In python-y pseudocode, this is basically the following algorithm:

```
l = [input]
while l[-1] != 0:   #While the back of the list is nonzero
    old_len = len(l)
    l.append(l[-1])
    l.append(l[-1] - old_len)

l.pop()

print(len(l))

```

# Answer
> 9 votes
## Mathematica, 8 bytes

```
2Sqrt@#&

```

Try it online! (Using Mathics.)

The difference between **n2** and **(n+1)2** is always **2n+1** but we just want the values between them excluding both ends, which is **2n**.

This can potentially be shortened to `2#^.5&` depending on precision requirements.

# Answer
> 3 votes
# Julia 0.5, 8 bytes

```
!n=2n^.5

```

Try it online!

# Answer
> 2 votes
# dc, 5

```
?2*vp

```

Try it online.

---

Previously I misread the question. This version works for any positive integer input, not just perfect squares:

# dc, 12

```
?dv1+d*1-r-p

```

Try it online.

# Answer
> 2 votes
# Jelly,  ~~7~~  6 bytes

*I missed the "input will be square" caveat, but this will work for all non-negative integers...* Martin Ender already gave the 2 byte solution.

```
½‘Ḟ²’_

```

A monadic link returning the count.

**Try it online!**

# Answer
> 2 votes
# Japt, ~~5~~ 3 bytes

```
¬*2

```

Try it online!

Square root of the input, then multiply by 2.

# Answer
> 2 votes
# Brain-Flak, 20 bytes

*Shout out to DJMcMayhem's amazing (albiet slightly longer) answer here*

```
{({}()[({}()())])}{}

```

Try it online!

## Explanation

This code works by counting down from the square number by odd increments. Since every square is the sum of consecutive odd numbers this will reach 0 in n1/2 steps. The trick here is we actually keep track of our steps in an *even* number and use a static `()` to offset it to the appropriate odd number. Since the answer is 2n1/2, this even number will be our answer. So when we reach 0 we remove the zero and our answer is sitting there on the stack.

# Answer
> 1 votes
# Mathematica, 17 bytes

```
(Sqrt@#+1)^2-#-1&

```

Try it online!

# Answer
> 1 votes
# Octave, ~~25~~ 10 bytes

```
@(n)2*n^.5

```

Try it online!

Saved 15 bytes by using Martin's much better approach. The range consists of `2*sqrt(n)` elements. The function does exactly that: Multiplies `2` with the root of the input.

# Answer
> 1 votes
# Add++, ~~22~~ 20 bytes

```
+?
_
S
+1
^2
-1
-G
O

```

Try it online!

Do you want to know how it works? Well, fear not! I'm here to educate you!

```
+?   Add the input to x (the accumulator)
_    Store the input in the input list
S    Square root
+1   Add 1
^2   Square
-1   Subtract 1
-G   Subtract the input
O    Output as number

```

# Answer
> 1 votes
# Jelly, 7 bytes

```
½‘R²Ṫ_‘

```

Try it online!

Explanation:

```
½‘R²Ṫ_    Input:              40
½         Square root         6.32455532...
 ‘        Increment           7.32455532...
  R       Range               [1, 2, 3, 4, 5, 6, 7]
   ²      Square              [1, 4, 9, 16, 25, 36, 49]
    Ṫ     Tail                49
     _‘   Subtract input+1    8

```

# Answer
> 1 votes
# Python 3, 16 bytes

```
lambda n:2*n**.5

```

Try it online!

# Answer
> 1 votes
# Ohm, 2 bytes

```
√d

```

Try it online!

# Answer
> 1 votes
## JavaScript ES6, 10 bytes

```
n=>n**.5*2

```

Try it online! `Math.sqrt` is pretty long which is why we use `**.5`

# Answer
> 1 votes
# TI-Basic, 3 bytes

```
2√(Ans

```

Simplest approach...

# Answer
> 1 votes
# MATL (~~8~~ 7 bytes)

I'm sure this can be reduced significantly (edit: thanks Luis), but a naive solution is:

```
X^QUG-q

```

Try it online!

## Explanation:

```
X^   % Take the square root of the input (an integer)
QU  % Square the next integer to find the next square
G-   % Subtract the input to find the difference
q    % Decrement solution by 1 to count only "in between" values.

```

# Answer
> 1 votes
# 05AB1E, 2 bytes

Try it online!

Another port of Martin Ender's submission ...

# Answer
> 0 votes
# QBIC, ~~19~~ 9 bytes

```
?sqr(:)*2

```

*Saved a bunch by copying @MartinEnder's approach.*

No TIO link for QBIC, unfortunately.

## Explanation

```
?          PRINT
 sqr( )    The square root of
     :     the input
        *2 doubled

```

# Answer
> 0 votes
# Pari/GP, 9 bytes

```
n->2*n^.5

```

Try it online!

# Answer
> 0 votes
# PHP, 44 bytes

```
<?=count(range($argn,(sqrt($argn)+1)**2))-2;

```

Try it online!

# Answer
> 0 votes
## Alice, 10 bytes

```
2/*<ER
o@i

```

Try it online!

### Explanation

Again, computes **2 sqrt(n)**. The layout saves two bytes over the standard solution:

```
/o
\i@/2RE2*

```

Breakdown of the code, excluding redirection of the IP:

```
2    Push 2 for later.
i    Read all input.
i    Try reading more input, pushes "".
2    Push 2.
R    Negate to get -2.
E    Implicitly discard the empty string and convert the input to an integer.
     Then take the square root of the input. E is usually exponentiation, but
     negative exponents are fairly useless in a language that only understands
     integers, so negative exponents are interpreted as roots instead.
*    Multiply the square root by 2.
o    Output the result.
@    Terminate the program.

```

# Answer
> 0 votes
# Go, 56 bytes

```
import."math"
func f(n float64)float64{return 2*Sqrt(n)}

```

Try it online!

# Answer
> 0 votes
# 05AB1E, ~~4~~ 3 bytes

Crossed out 4 is still 4 :c

```
t2*

```

Try it online!

# Answer
> 0 votes
# Actually, 3 bytes

```
√2*

```

Try it online!

# Answer
> 0 votes
# Retina, 21 bytes

```
.+
$*
(^1?|11\1)+
$1

```

Try it online! Explanation: Works by taking the square root of the number based on @MartinEnder's triangular number solver. After matching the square number, `$1` is the difference between the square number and the previous square number, in unary. We want the next difference, but exclusive, which is just 1 more. To achieve this, we count the number of null strings in `$1`.

# Answer
> 0 votes
# Cubix, ~~22~~ 18 bytes

```
+@UOI0),c?;^..u;;/

```

Try it online!

Watch it online!

A port of Martin Ender's solution. Since Cubix only supports integer arithmetic, computing the square root is literally just trying every number until we hit the square root, so this approach only works since the input is a perfect square.

Expands to the following cube:

```
    + @
    U O
I 0 ) , c ? ; ^
. . u ; ; / . .
    . .
    . .

```

```
I       # read in input [n^2]
0       # push 0 [n^2, 0]
Main loop:
)       # increment [n^2, 1]
,       # divide, rounding to zero [n^2, 1, n^2]
c       # bitwise xor -- zero if equal, positive if not
?       # turn right if positive, go straight if zero [n^2,1,n^2,___]
 nonzero branch:
  /      # reflect IP direction
  ;;     # pop top two off stack [n^2, 1]
  u      # right-hand U-turn
  (re-enter main loop)
 zero branch: stack is [n^2, n, n, 0]
  ;      # pop top of stack [n^2, n, n]
  ^      # go north
  +      # add top two elements [n^2, n, n, 2n]
  U      # left-hand u-turn
  O      # output as int
  @      # terminate program

```

# Answer
> 0 votes
# T-SQL, 22 bytes

```
SELECT 2*SQRT(a)FROM t

```

Input is via a pre-existing table, per our standards.

# Answer
> 0 votes
# Java (OpenJDK 9) / JShell, 17 bytes

```
n->2*Math.sqrt(n)

```

Try it online!

Note: This would require `import java.util.function.*;` to get `IntFunction<T>` in Java 8 or Java 9, but the `java.util.function` package is imported by default in JShell.

# Answer
> 0 votes
# Haskell, 9 bytes

```
(*2).sqrt

```

Try it online

Input and output will be treated as Float values.

# Answer
> 0 votes
# Noether, 7 bytes

```
I.5^2*P

```

**Try it here!**

Just the same as every other answer: outputs two times the square root.

# Answer
> 0 votes
# S.I.L.O.S, 26 bytes

```
readIO
i=2*i^.5
printInt i

```

Try it online!

Straightforward port of Martin Ender's Mathematica answer.

# Answer
> 0 votes
# C#, 24 bytes

```
n=>System.Math.Sqrt(n)*2

```

# Answer
> 0 votes
# Perl 6, 12 bytes

```
*.sqrt.Int*2

```

Try it

---

If it had to work with positive numbers that aren't squares:

```
{+($_^..^(.sqrt.Int+1)²)}

```

Try it

# Answer
> 0 votes
## CJam, ~~11~~ 10 bytes

```
ri_mQ)_*-~

```

Explanation:

```
ri e# Read integer: | 16
_  e# Duplicate:    | 16 16
mQ e# Square root:  | 16 4
)  e# Increment:    | 16 5
_* e# Square:       | 16 25
-  e# Subtract:     | -9
~  e# Bitwise NOT:  | 8

```

## Alternative Solution, 6 bytes

```
rimQ2*

```

Explanation:

```
ri e# Read integer: | 16
mQ e# Square root:  | 4
2* e# Times 2:      | 8

```

# Answer
> 0 votes
# **Pyth, 4 bytes**

```
y@Q2

```

Explanation:

```
     # Implicit copy input to Q
y    # Multiply by 2
 @Q2 # Square-root of Q
     # Implicit print

```

# Answer
> 0 votes
# Charcoal, 7 bytes

```
Ｉ×²ＸＮ·⁵

```

Try it online!

## Explanation

```
Ｉ         Cast (int -> str)
  ×²       Multiplied by 2
    ＸＮ·⁵ N to the power of .5 (Square root of N)

```

# Answer
> 0 votes
**C#, 42 bytes**

```
int b=(int)Math.Sqrt(n);b=(b+1)*(b+1)-n-1;

```

Try it online!

# Answer
> 0 votes
# Dyalog APL, 6 bytes

```
2×*∘.5

```

I can't believe this hasn't been posted yet. A variant with the same byte count:

```
+⍨*∘.5

```

Both of them work by doubling the square root.

# Answer
> 0 votes
# NewStack, 3 bytes

```
2√ᵢ

```

## The breakdown:

```
 √ᵢ    Append the square root of the input.
2      Multiply it by two.

```

## Why this works:

To find how many numbers `N` are in between the square number `x` and the next square number `m`, we first need to find a formula for `m`.

Since `x` is a square number, `√x` will be an integer. And `√x + 1` will equal `√m`.

Therefore `m` = `(√x + 1)^2` = `x + 2√x + 1`

The amount of numbers in between `x` and `m` will just equal their difference minus 1.

`N` = `m - x - 1` = `(x + 2√x + 1) - x - 1`

So we've concluded

`N` = `2√x`

# Answer
> 0 votes
# Plain English ~~129~~ 98 bytes

```
To put a n number's d into a r number:
Put the square root of the n in the r.
Add the r to the r.

```

Ungolfed:

```
To put a number's delta into a result number:
Put the square root of the number in the result.
Add the result to the result.

```

The Plain English IDE is available at github.com/Folds/english. The IDE runs on Windows. It compiles to 32-bit x86 code.

# Answer
> 0 votes
# J, 4 bytes

```
+:%:

    e.g. +:%: 9  ====>  6

```

# Answer
> 0 votes
# Excel, 9 bytes

```
=2*A1^0.5

```

---

To handle all cases (not only squares): 21 bytes

```
=INT(A1^0.5+1)^2-A1-1

```

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


title: Pick-flatten a list

text:
# Question
Title: Pick-flatten a list
Consider the process of "picking" a nested list. Picking is defined as follows:

* If the argument is a list, take an element from the list at random (uniformly), and pick from that.
* If the argument is not a list, simply return it.

An example implementation in Python:

```
import random
def pick(obj):
    if isinstance(obj, list):
        return pick(random.choice(obj))
    else:
        return obj

```

For simplicity, we assume that nested lists only contain integers or further nested lists.

Given any list, it is possible to create a flattened version which is indistinguishable by `pick`, i.e. picking from it yields the same results, with the same probability.

For example, "pick-flattening" the list

```
[1, 2, [3, 4, 5]]

```

yields the list

```
[1, 1, 1, 2, 2, 2, 3, 4, 5]

```

. The reason simply flattening is invalid is because elements of sub-lists have a lower probability of being chosen, e.g. in the list `[1, [2, 3]]` the 1 has a 2/4 = 1/2 chance of being chosen while 3 and 4 both have a 1/4 chance each.

Also note that picking from a singleton list is equivalent to picking from its element, and that picking from an empty list has no meaning.

## The Challenge

Given a nested list of nonnegative integers, return a flattened list of nonnegative integers from which picking yields the same results with the same probability.

This is , so the shortest valid answer (measured in bytes) wins.

## Specifications

* The inputs `[2, 3, 4]`, `[2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4]`, and `[2, [3, 3], [[4]]]` are equivalent (i.e. they should give equivalent results).
* The outputs `[2, 2, 2, 2, 3, 3, 3, 3]` and `[2, 3]` are equivalent (i.e. either one could be output).
* You can assume only numbers in the inclusive range 1-100 will be present in the lists.
* You can assume the top-level input will be a list, i.e. `2` is not a valid input.
* You can use any reasonable representation of nested lists, for example:
`[1, [2, 3]]`, `1 {2 3}`, `"[ 1 [ 2 3 ] ]"`, etc.
* Instead of a list, you can output a multiset or a mapping, or, since only numbers in the range 1-100 are allowed, a length-100 list of integers representing quantities.

## Test Cases

Note that the listed outputs are only one valid possibility; see specifications for what constitutes a valid input or output.

```
format:
input -> output
[3]                          -> [3]
[1, [1, 1]]                  -> [1]
[1, [2, 3]]                  -> [1, 1, 2, 3]
[2, 3, [4, [5, 5, 6], 6, 7]] -> [2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 4, 4, 4, 5, 5, 6, 6, 6, 6, 7, 7, 7]
[[1, 1, 2], [2, 3, 3]]       -> [1, 2, 3]
[[1, 1, 2], [2, 3, 3, 3]]    -> [1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3]

```

# Answer
# Wolfram Language (Mathematica), ~~41~~ 20 bytes

```
Flatten@*Tuples//@#&

```

Try it online! Ignore the many warnings, it all works out in the end.

## How it works

For a list of depth 2 such as `{{1,2},{3},{4,5,6}}`, `Tuples` will generate the list `{{1,3,4},{1,3,5},{1,3,6},{2,3,4},{2,3,5},{2,3,6}}` corresponding to all the ways to pick an element from `{1,2}` *and* pick an element from `{3}` *and* pick an element from `{4,5,6}`.

If we `Flatten` this, then we get all the elements with the correct frequencies, because picking an element from *one* of `{1,2}`, `{3}` or `{4,5,6}` is equivalent to picking an element from all of them, then choosing which one to keep.

We use `//@` to apply this at all levels of the input. In the process, Mathematica complains a lot, because it's turning atoms such as `17` into `Tuples[17]`, which is really not supposed to be a thing. But these simplify to the right result later on (`Tuples` is happy to treat `Tuples[17]` as a list of length 1, even if it has a head other than `List`), so the complaining is irrelevant.
> 8 votes

# Answer
# Python 2, ~~105~~ ~~102~~ 99 bytes

```
g=lambda y=[],*z:[w+[n]for n in y for w in g(*z)]or[y]
f=lambda x:x<[]and[x]or sum(g(*map(f,x)),[])

```

Try it online!
> 6 votes

# Answer
# Jelly, ~~9~~ 8 bytes

```
ß€Œp$¬¡F

```

Try it online!

### How it works

```
ß€Œp$¬¡F  Main link. Argument: x (array or positive integer)

     ¬    Compute elementwise logical NOT of x: a non-empty array for a non-empty array, 0 for a positive integer.
      ¡   Apply the link to the left once if ¬ returned a non-empty
          array, zero timed if it returned 0.
    $     Monadic chain:
ß€            Map the main link over x.
  Œp          Take the Cartesian product.
       F  Flatten the result.

```
> 4 votes

# Answer
# Jelly, 10 bytes

```
L€P⁸ṁ€ẎµÐL

```

Try it online!
> 1 votes

# Answer
# Python 2, 128 bytes

```
def f(l,p=0):m=reduce(int.__mul__,[i*0<[]or len(i)for i in l]);return p*(p==l)or f(sum([(([i],i)[i*0>0]*m)[:m]for i in l],[]),l)

```

Try it online!

Port of my Jelly answer.

-12 thanks to Jonathan Frech.
> 1 votes

# Answer
# C (gcc), 234 223 bytes

```
h[9][101];o[101];n[9];l;L;e;main(x){for(;(x=scanf("%d",&e))>=0;x?++h[l][e],++n[l]:(e=getchar())-'['?e-']'?0:--l:++l>L&&++L);for(e=1,l=L+1;l--;){for(x=101;--x;o[x]+=e*h[l][x]);e*=n[l];}while(o[x]--?printf("%d ",x):++x<101);}

```

Try it online!

**Explanation:**

```
h[9][101];  // <- number occurences per nesting level
o[101];     // <- number occurences in "flattened" array
n[9];       // <- number of entries per nesting level
l;          // <- current nesting level
L;          // <- max nesting level
e;          // <- multi-purpose temporary
main(x){    // x: multi-purpose temporary
    for(;
            // while not EOF try reading number
            (x=scanf("%d",&e))>=0;

            // number was read?
            x

                // then increment occurence and # entries in level
                ?++h[l][e],++n[l]

                // else read any character ... if not [
                :(e=getchar())-'['

                    // if not ]
                    ?e-']'

                        // do nothing
                        ?0

                        // else decrement nesting level
                        :--l

                    // else increment nesting level and adjust max level
                    :++l>L&&++L);

    // init factor in e to 1, iterate over nesting level from innermost
    for(e=1,l=L+1;l--;){

        // iterate over all numbers
        for(x=101;
                --x;

                // add factor times occurence on current level to output
                o[x]+=e*h[l][x]);

        // multiply factor by number of entries on current level
        e*=n[l];
    }

    // iterate over all numbers and output count times
    while(o[x]--?printf("%d ",x):++x<101);
}

```
> 1 votes

# Answer
# Python 2, ~~144~~ 139 bytes

```
def f(A,p):[F.append((len(A)*p,a))if a*0<[]else f(a,len(A)*p)for a in A]
F=[];f(input(),1);R=[]
for v in F:R+=max(F)[0]/v[0]*[v[1]]
print R

```

Try it online!
> 0 votes

# Answer
# JavaScript (ES6), ~~132~~ 131 bytes

```
f=A=>(_=(a,m)=>[].concat(...a.map(m)),n=1,A=A.map(a=>a.map?f(a):[a]),_(A,a=>n*=a.length),_(A,a=>_(a.map(x=>Array(n/a.length).fill(x)))))

```

```
f=A=>(_=(a,m)=>[].concat(...a.map(m)),n=1,A=A.map(a=>a.map?f(a):[a]),_(A,a=>n*=a.length),_(A,a=>_(a,x=>Array(n/a.length).fill(x))))

console.log( f( [3] ) )
console.log( f( [1, [1, 1]] ) )
console.log( f( [1, [2, 3]] ) )
console.log( f( [2, 3, [4, [5, 5, 6], 6, 7]] ) )
console.log( f( [[1, 1, 2], [2, 3, 3]] ) )
console.log( f( [[1, 1, 2], [2, 3, 3, 3]] ) )
console.log( f( [1, 2, [3, 4, 5], [6, 7]] ) )
```
> 0 votes

---
Tags: code-golf, number, array, combinatorics, probability-theory
---


title: Finding the smallest sets

text:
# Question
Title: Finding the smallest sets
Consider three sets `A`, `B` and `C` each containing `n` integers. From this we can make the set

```
S_n = {a * b + c | a in A, b in B, c in C}.

```

Given an `n`, there are one or more minimal sized `S_n` which depend on which sets `A,B and C` have been chosen.

The sets can contain any `n` distinct integers (positive, zero or negative). There is no need for them to be consecutive integers or for the sets to be equal to each other for example. `A = {-1, 0, 5, 10, 27}, B = {2, 5, 6, 10, 14} and C = {-23, 2, 100, 1000,10000}` is acceptable (although not a good idea) for example.

**Task**

The task is to write code to find the smallest set `S_n` it can for each `n` from `1` to `20`.

For each `n` from `1` to `20` your code should output the chosen `A`, `B` and `C` along with the resulting size of `S_n`

**Score**

Your score will be the sum of the sizes of the `S_n` you create. That is it will be a sum of twenty numbers.

The lower the score the better.

**Examples**

If `A = B = C = {1, 2, 3, 4}` then `S_4 = {2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20}` which is of size `19`.

This is however in no way optimal. For example, `A = B = C = {-1, 0, 1, 2}` gives `S_4 = {0, 1, 2, 3, 4, 5, 6, -1, -3, -2}` which is of size `10`.

**Timings**

As I will need to run your code to verify the output, please make sure it takes no more than 30 minutes and 4GB of RAM to run on a normal desktop.

**Notes**

Your code must actually compute the output. You are not allowed to hardcode precomputed answers into your code.

# Answer
> 7 votes
# Rust, score ~~1412~~ 1411

### `src/main.rs`

```
extern crate gmp;

use std::collections::BinaryHeap;
use std::collections::hash_map::{HashMap, Entry};
use gmp::mpz::Mpz;

fn visit(
    queue: &mut BinaryHeap<(i32, i32, i32, Mpz, Mpz)>,
    visited: &mut HashMap<(i32, Mpz), i32>,
    score: i32,
    h: i32,
    k: i32,
    d: Mpz,
    c: Mpz,
) {
    match visited.entry((k, d.clone())) {
        Entry::Occupied(mut e) => {
            if *e.get() < score {
                e.insert(score);
                queue.push((score, h, k, d, c));
            }
        }
        Entry::Vacant(e) => {
            e.insert(score);
            queue.push((score, h, k, d, c));
        }
    }
}

fn main() {
    let mut total = 0;
    for n in 1..21 {
        let a_range = n / 2 - n + 1..n / 2 + 1;
        let min_ab = a_range.start * (a_range.end - 1);
        let mut ab = Mpz::zero();
        for a in a_range.clone() {
            for b in a_range.clone() {
                ab.setbit((a * b - min_ab) as usize);
            }
        }

        let heuristic = |k: i32, d: &Mpz| if k == n {
            0
        } else {
            k + 1 - n -
                (0..d.bit_length())
                    .map(|i| (&ab & !(d >> i)).popcount())
                    .min()
                    .unwrap() as i32
        };

        let mut queue = BinaryHeap::new();
        let mut visited = HashMap::new();

        let (k1, d1) = (0, Mpz::zero());
        let h1 = heuristic(k1, &d1);
        visit(&mut queue, &mut visited, h1, h1, k1, d1, Mpz::zero());
        while let Some((score, h, k, d, c)) = queue.pop() {
            if k == n {
                println!("n={} |S|={}", n, -score);
                println!("  A={:?}", a_range.clone().collect::<Vec<_>>());
                println!("  B={:?}", a_range.clone().collect::<Vec<_>>());
                println!(
                    "  C={:?}",
                    (0..c.bit_length())
                        .filter(|&i| c.tstbit(c.bit_length() - 1 - i))
                        .collect::<Vec<_>>()
                );
                total += -score;
                break;
            }

            let kd = (k, d);
            if score < visited[&kd] {
                continue;
            }
            let (k, d) = kd;

            let (k1, d1) = (k, &d >> 1);
            let h1 = heuristic(k1, &d1);
            visit(
                &mut queue,
                &mut visited,
                score - h + h1,
                h1,
                k1,
                d1,
                &c << 1,
            );

            let (k1, d1) = (k + 1, (&d | &ab) >> 1);
            let h1 = heuristic(k1, &d1);
            visit(
                &mut queue,
                &mut visited,
                score - h - (&ab & !&d).popcount() as i32 + h1,
                h1,
                k1,
                d1,
                &c << 1 | Mpz::one(),
            );
        }
    }

    println!("total={}", total);
}

```

### `Cargo.toml`

```
[package]
name = "small"
version = "0.1.0"
authors = ["Anders Kaseorg <andersk@mit.edu>"]

[dependencies]
rust-gmp = "0.5.0"

```

Compile and run with `cargo run --release`.

### Output

```
n=1 |S|=1
  A=[0]
  B=[0]
  C=[0]
n=2 |S|=3
  A=[0, 1]
  B=[0, 1]
  C=[0, 1]
n=3 |S|=5
  A=[-1, 0, 1]
  B=[-1, 0, 1]
  C=[0, 1, 2]
n=4 |S|=10
  A=[-1, 0, 1, 2]
  B=[-1, 0, 1, 2]
  C=[0, 1, 2, 3]
n=5 |S|=13
  A=[-2, -1, 0, 1, 2]
  B=[-2, -1, 0, 1, 2]
  C=[0, 1, 2, 3, 4]
n=6 |S|=21
  A=[-2, -1, 0, 1, 2, 3]
  B=[-2, -1, 0, 1, 2, 3]
  C=[0, 2, 3, 4, 5, 6]
n=7 |S|=25
  A=[-3, -2, -1, 0, 1, 2, 3]
  B=[-3, -2, -1, 0, 1, 2, 3]
  C=[0, 2, 3, 5, 6, 7, 8]
n=8 |S|=35
  A=[-3, -2, -1, 0, 1, 2, 3, 4]
  B=[-3, -2, -1, 0, 1, 2, 3, 4]
  C=[0, 3, 4, 6, 7, 8, 10, 11]
n=9 |S|=39
  A=[-4, -3, -2, -1, 0, 1, 2, 3, 4]
  B=[-4, -3, -2, -1, 0, 1, 2, 3, 4]
  C=[0, 3, 4, 6, 7, 8, 10, 11, 14]
n=10 |S|=53
  A=[-4, -3, -2, -1, 0, 1, 2, 3, 4, 5]
  B=[-4, -3, -2, -1, 0, 1, 2, 3, 4, 5]
  C=[0, 1, 4, 5, 6, 9, 10, 11, 14, 15]
n=11 |S|=58
  A=[-5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5]
  B=[-5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5]
  C=[0, 1, 4, 5, 6, 9, 10, 11, 14, 15, 19]
n=12 |S|=74
  A=[-5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6]
  B=[-5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6]
  C=[0, 4, 5, 6, 9, 10, 11, 12, 15, 16, 17, 21]
n=13 |S|=80
  A=[-6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6]
  B=[-6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6]
  C=[0, 4, 5, 6, 9, 10, 11, 12, 15, 16, 17, 21, 22]
n=14 |S|=100
  A=[-6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7]
  B=[-6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7]
  C=[0, 1, 6, 7, 8, 12, 13, 14, 15, 19, 20, 21, 26, 27]
n=15 |S|=106
  A=[-7, -6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7]
  B=[-7, -6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7]
  C=[0, 5, 6, 7, 11, 12, 13, 14, 18, 19, 20, 21, 25, 26, 27]
n=16 |S|=128
  A=[-7, -6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8]
  B=[-7, -6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8]
  C=[0, 6, 7, 8, 13, 14, 15, 16, 20, 21, 22, 23, 28, 29, 30, 36]
n=17 |S|=135
  A=[-8, -7, -6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8]
  B=[-8, -7, -6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8]
  C=[0, 6, 7, 8, 13, 14, 15, 16, 20, 21, 22, 23, 28, 29, 30, 36, 44]
n=18 |S|=161
  A=[-8, -7, -6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
  B=[-8, -7, -6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
  C=[0, 7, 8, 9, 15, 16, 17, 18, 23, 24, 25, 26, 27, 32, 33, 34, 35, 41]
n=19 |S|=167
  A=[-9, -8, -7, -6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
  B=[-9, -8, -7, -6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
  C=[0, 7, 8, 9, 15, 16, 17, 18, 23, 24, 25, 26, 27, 32, 33, 34, 35, 41, 42]
n=20 |S|=197
  A=[-9, -8, -7, -6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
  B=[-9, -8, -7, -6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
  C=[0, 1, 8, 9, 10, 11, 17, 18, 19, 20, 21, 26, 27, 28, 29, 30, 36, 37, 38, 46]
total=1411

```

On my laptop, this used about 8 minutes and about 1.5 GiB of memory.

### How it works

We assume (without any particular justification) that *A* and *B* are the obvious range of consecutive integers centered at 0 or ½, then do an A\* search for an optimal *C* given *A* and *B*.

# Answer
> 2 votes
# Axiom, score 1466

```
)time on

g(a:List INT,b:List INT,c:List INT):List INT==
   s:List INT:=[]
   for i in 1..#a repeat
     for j in 1..#b repeat
       for h in 1..#c repeat
            s:=cons(a.i*b.j+c.h, s)
   removeDuplicates(s)

inc(a:List INT, b:INT):List INT==
    #a=0=>a
    i:=1; len:=#a
    repeat
       if i>len then
             for j in 1..len repeat a.j:=0
             return a
       if i<len then
         if a.i<a.(i+1) then
               if a.i<b then
                          a.i:=a.i+1
                          for j in 1..(i-1) repeat a.j:=0
                          break
               for j in 1..i repeat a.j:=0
       else
         if a.i<b then
                   a.i:=a.i+1
                   for j in 1..(len-1) repeat a.j:=0
                   break
       i:=i+1
    a

f(n:PI):List List INT==
   a:List INT:=[0];  b:List INT:=[0];   c :List INT:=[0]
   aix:List INT:=[]; cmin:List INT:=[]; cp:List INT:=[ ]
   s:List INT :=[ ];   c1:List INT:=[0]; smin:INT
   -- costruisce gli insiemi a,b
   i:=1
   for j in 1..n-1 repeat
      if member?(i,a) then (a:=cons(-i,a);b:=cons(-i,b);i:=i+1)
      else                 (a:=cons( i,a);b:=cons( i,b))
   if n=1 then return [a,b,c,[0],[1]]
   a:=sort(a)
   c :=copy(a); cmin:=copy(a); cp:=copy(a)
   for i in 1..n repeat c.i:=i-3
   for i in 1..n repeat aix:=cons(0, aix)
   -- ottimizzati per i vari casi... si parte da particolari insiemi c
   -- da cui fare le variazioni
   if n>=8         then c.n:=c.n+2
   if n=10 or n=13 then c.(n-1):=c.(n-1)+2
   if n=9  or n=16 or n=19 then (c.(n-2):=c.(n-2)+1; c.(n-1):=c.(n-1)+1; c.n:=c.n+1)
   smin:=n*n+10
   repeat
       for i in 1..n repeat cp.i:=c.i+aix.i
       k:=# g(a,b,cp)
       if k<smin then
                smin:=k;
                for i in 1..n repeat cmin.i:=cp.i
                --output ["assign",c,aix,cmin, k]
       inc(aix, 3)
       --output aix
       i:=0;repeat(i:=i+1;if i>n or aix.i~=0 then break)
       if i>n then break
   [sort(a),sort(b),sort(cmin),g(a,b,cmin),[smin]]

h(n:PI):NNI==
    k:=0
    r:List List INT:=[]
    for i in 1..n repeat
         r:=f(i)
         output [i,r.5.1,r.1,r.3]
         k:=k+r.5.1
    k

```

The sets would be A=B=\[-n/2..n/2\] if n%2==0 else A=B=\[-n/2..((n/2)+1)\]

The set C is the sum of the array as \[-2,-1,..(n-2)\] to one array arr\[\] of this kind \[0,0,0,0,0\] or \[0,1,1,1,2\] or \[0,0,0,0,3\] so that array it has property

```
 arr[i] <= arr[i+1] for i in 1..n-1

```

If you want to be more precise or you PC is more fast you can try to increase '3' in 'inc(aix, 3)' that increase the number of arrays for the C set variation and so it would increase the result precision.

In the results the string printed is

```
 [n, |{a*b+c for a in A for b in B for c in C}|,A,C]

```

where B=A and |S| is the number of element of S

```
(6) -> h 20
   [1,1,[0],[0]]
   [2,3,[0,1],[- 2,- 1]]
   [3,5,[- 1,0,1],[- 2,- 1,0]]
   [4,10,[- 1,0,1,2],[- 2,- 1,0,1]]
   [5,13,[- 2,- 1,0,1,2],[- 2,- 1,0,1,2]]
   [6,21,[- 2,- 1,0,1,2,3],[- 2,- 1,0,1,2,3]]
   [7,25,[- 3,- 2,- 1,0,1,2,3],[- 2,- 1,0,1,2,3,4]]
   [8,35,[- 3,- 2,- 1,0,1,2,3,4],[- 2,- 1,1,2,3,5,6,9]]
   [9,39,[- 4,- 3,- 2,- 1,0,1,2,3,4],[- 2,1,2,4,5,6,8,9,12]]
   [10,53,[- 4,- 3,- 2,- 1,0,1,2,3,4,5],[- 2,- 1,2,3,4,6,7,8,11,12]]
   [11,59,[- 5,- 4,- 3,- 2,- 1,0,1,2,3,4,5],[- 2,- 1,0,2,3,4,5,7,8,9,12]]
   [12,76,[- 5,- 4,- 3,- 2,- 1,0,1,2,3,4,5,6],[- 2,- 1,0,3,4,5,6,8,9,10,11,14]]
   [13, 82, [- 6,- 5,- 4,- 3,- 2,- 1,0,1,2,3,4,5,6],[- 2,- 1,0,3,4,5,6,8,9,10,11,14,15]]
   [14, 103, [- 6,- 5,- 4,- 3,- 2,- 1,0,1,2,3,4,5,6,7],[- 2,- 1,0,3,4,5,6,7,9,10,11,12,13,16]]
   [15, 110, [- 7,- 6,- 5,- 4,- 3,- 2,- 1,0,1,2,3,4,5,6,7],[- 2,- 1,0,1,4,5,6,7,8,10,11,12,13,14,17]]
   [16, 134, [- 7,- 6,- 5,- 4,- 3,- 2,- 1,0,1,2,3,4,5,6,7,8],[- 2,- 1,0,1,4,5,6,7,8,9,11,12,13,15,16,19]]
   [17, 142, [- 8,- 7,- 6,- 5,- 4,- 3,- 2,- 1,0,1,2,3,4,5,6,7,8],[- 2,- 1,0,1,4,5,6,7,8,9,11,12,13,14,15,16,19]]
   [18, 169, [- 8,- 7,- 6,- 5,- 4,- 3,- 2,- 1,0,1,2,3,4,5,6,7,8,9],[- 2,- 1,0,1,2,3,4,6,7,8,9,10,11,12,15,16,17,20]]
   [19, 178, [- 9,- 8,- 7,- 6,- 5,- 4,- 3,- 2,- 1,0,1,2,3,4,5,6,7,8,9],[- 2,- 1,0,1,2,5,6,7,8,9,10,11,13,14,15,16,18,19,22]]
   [20, 208, [- 9,- 8,- 7,- 6,- 5,- 4,- 3,- 2,- 1,0,1,2,3,4,5,6,7,8,9,10],[- 2,- 1,0,1,2,3,4,5,7,8,9,10,11,12,13,14,17,18,19,22]]

   (6)  1466
                                                    Type: PositiveInteger
      Time: 0.03 (IN) + 910.75 (EV) + 0.02 (OT) + 24.00 (GC) = 934.80 sec

```

# Answer
> 2 votes
## SQL Server, 1495

```
declare @N int=20;
--set @N=40;
with
  n as(select 1 n union all select n+1 from n where n<@N),
  s as(select n,n/2-n+1 m from n union all select n,m+1 from s where m<n/2),
  t as(select n,m,row_number()over(partition by n order by m) p from s),
  a as(select n,m a,p from t),
  b as(select n,m b,p from t),
  c as(select n,m c,p from t),
  u as(
    select a.n,count(distinct a*b+c) q
    from a,b,c
    where b.n=a.n and c.n=a.n
    group by a.n
  )
select u.n,a,b,c,q,sum(distinct q) N
from u,a,b,c
where a.n=u.n and b.n=u.n and c.n=u.n and b.p=a.p and c.p=a.p
group by grouping sets((u.n,a,b,c,q),());

```

The solution can be verified here.

Excuse me for the output is in the tabular form.

# Answer
> 2 votes
# C, score ~~1448~~ 1431

```
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define P printf
#define R return
#define F for

int cmp(const void*a,const void*b)
{int aa, bb;
 aa=*(int*)a; bb=*(int*)b;
 R aa>bb?1:(aa<bb?-1:0);
}

void show(int* a,unsigned n){unsigned i;P("[ ");F(i=0;i<n;++i) P("%d ", a[i]);P("]");}

// l'insieme "a" deve essere del tipo {0,1} {-1,0,1} {-1,0,1,2} {-2,-1,0,1,2} ecc di numero elementi n
// l'insieme "c" e' un insieme di numero elementi n
// l'insieme a cui "r" punta sarà *r={x*y+z : x in a, y in a, z in c }
// ritorna -1 per errore altrimenti il numero di elementi
// di {x*y+z : x in a, y in a, z in c }

int g(int**r,int*a,int*c,unsigned n)
{static int *arrs,*res;
 static unsigned  alen;
 unsigned i,j,k,m,v,vv,len;

 if(a==0||c==0||n<=0||n>128) R -1;
 len=n*n*n;
 if(alen<n)
    {if(arrs) free(arrs);  // leaks: arrs and res remain until the program end
     if(res ) free(res);
     arrs=0; res=0; alen=0;
     arrs=malloc(sizeof(int)*len);
     if(arrs==0)             R -1;
     res =malloc(sizeof(int)*len);
     if(res==0)
         {free(arrs); arrs=0;R -1;}
     alen=n;
    }
 v=0;
 F(k=0;k<n;++k) arrs[v++]=c[k]; // il caso 0

 F(m=0;m<n&&a[m]<0;++m);// da una parte i positivi dall'altra i negativi; m punta a 0
                        // il caso 0 non e' trattato
 F(i=0;i<m;++i)    // positivi per negativi
   F(j=m+1;j<n;++j)
      F(k=0;k<n;++k)
         if(-a[i]<=a[j]) arrs[v++]=a[i]*a[j]+c[k];
 F(i=m+1;i<n;++i)  // positivi per positivi
   F(j=i;j<n;++j)
      F(k=0;k<n;++k)
          arrs[v++]=a[i]*a[j]+c[k];
 qsort(arrs,v,sizeof(int),cmp);
 res[0]=arrs[0];  // elimina i doppioni
 F(vv=1,i=1; i<v; ++i)
       if(arrs[i-1]!=arrs[i]) res[vv++]=arrs[i];
 *r=res;
 R vv;
}

int inc(int* a,int len,int b)
{int i,j;
 if(len<1||b<1)R 1;
 F(i=0;;)
   {if(i>=len)
         {F(j=0;j<len;++j)a[j]=0;
          R 1;
         }
    if(i==len-1||a[i]<a[i+1])
               {if(a[i]<b)
                   {a[i]+=1;
                    F(j=0;j<i;++j)a[j]=0;
                    break;
                   }
               }
    i+=1;
   }
 R 0;
}

// a,b,c,cmin sono array e devono avere size n
// s          e' un array deve avere size n*n*n
//            come risultato la sua lunghezza e' *slen
//
int f(int* a,int* b,int* cmin,int* s,int* slen, int n)
{int i,j,k, *c, *aix, *cp, smin, *rs;

 if(slen)*slen=0;
 if(n<1||a==0||b==0||cmin==0||s==0||slen==0)R -1;

 // costruisce a e b
 j=-n/2;
 if(n%2==0)++j;
 F(i=0;i<n;++i,++j) s[i]=cmin[i]=a[i]=b[i]=j;
 // {-x..x}  oppure {-x..(x+1)}

 *slen=n;
 if(n==1)R 1; // caso di un solo elemento
 c  =malloc(sizeof(int)*(n+1)); // **
 if(c==0)R -1;
 aix=malloc(sizeof(int)*(n+1)); // **
 if(aix==0){free(c);R -1;}
 cp =malloc(sizeof(int)*(n+1)); // **
 if(cp==0){free(aix);free(c);R -1;}

 F(i=0;i<n;++i){cp[i]=aix[i]=0;c[i]=i;}
 if(n>=16)//16
    {c[n-1]=c[n-1]+3;c[n-2]=c[n-2]+3;c[n-3]=c[n-3]+3;}
 F(smin=n*n+10;;)
    {cp[0]=c[0];
     F(i=1;i<n;++i) cp[i]=c[i]+aix[i-1];
     k=g(&rs,a,cp,n);
     if(k<smin){F(smin=k,i=0;i<n;++i) cmin[i]=cp[i];
                //P("Assign: %d,  ", k);
                //show(aix,n);P(",");
                //P("Cmin=");show(cmin,n);P("\n");
               }
     //show(aix,n);P("\n");
     if(inc(aix,n-1,7))break;
    }
 free(cp);free(aix);free(c);
 k=g(&rs,a,cmin,n);
 if(k==-1)R -1;
 F(i=0;i<k;++i)s[i]=rs[i];
 *slen=k;
 R k;
}

unsigned h(unsigned nmax)
{time_t                             ti, tf;
 double  dft;
 int i,j, *a, *b, *cmin, *s, slen, rlen, r;
 unsigned                            n,len;
 if(nmax>128||nmax<1)R -1;
 len =nmax*nmax*nmax+1;
 s   =malloc(sizeof(int)*len);      // **
 a   =malloc(sizeof(int)*(nmax+1)); // **
 b   =malloc(sizeof(int)*(nmax+1)); // **
 cmin=malloc(sizeof(int)*(nmax+1)); // **
 if(s==0||a==0||b==0||cmin==0){free(s);free(a);free(b);free(cmin);R -1;}
 ti=time(0);
 F(n=1,r=0;n<=nmax;++n)
    {rlen=f(a,b,cmin,s,&slen,n);
     if(rlen!=-1)
         {P("%d %d", n, rlen); show(cmin,n);P("\n");}
     else break;
     r+=rlen;
    }
 tf=time(0);
 dft=difftime(tf, ti);
 P("Result=%d  secondi=%.0f  minuti=%.0f\n", r, dft, dft/60.0);
free(s);free(a);free(b);free(cmin);
 R r;
}

int main(){h(20); R 0;}

```

It would be the same +/- algo of Axiom implementation

results

```
1 1[ 0 ]
2 3[ 0 1 ]
3 5[ 0 1 2 ]
4 10[ 0 1 2 3 ]
5 13[ 0 1 2 3 4 ]
6 21[ 0 1 2 3 4 5 ]
7 25[ 0 1 2 3 4 5 6 ]
8 35[ 0 1 3 4 5 7 8 11 ]
9 39[ 0 3 4 6 7 8 10 11 14 ]
10 53[ 0 1 4 5 6 8 9 10 13 14 ]
11 59[ 0 1 2 4 5 6 7 9 10 11 14 ]
12 75[ 0 1 2 5 6 7 8 11 12 13 17 18 ]
13 81[ 0 1 2 5 6 7 8 11 12 13 14 17 18 ]
14 101[ 0 1 2 3 6 7 8 9 10 13 14 15 16 20 ]
15 107[ 0 1 2 3 6 7 8 9 10 13 14 15 16 20 21 ]
16 130[ 0 1 2 6 7 8 9 10 13 14 15 16 17 21 22 23 ]
17 137[ 0 1 2 3 7 8 9 10 11 15 16 17 18 19 23 24 25 ]
18 163[ 0 1 2 3 7 8 9 10 11 12 16 17 18 19 20 25 26 27 ]
19 171[ 0 1 2 3 4 8 9 10 11 12 13 17 18 19 20 21 26 27 28 ]
20 202[ 0 1 2 3 7 8 9 10 11 12 13 17 18 19 20 21 22 27 28 29 ]
Result=1431  secondi=618  minuti=10

```

# Answer
> 1 votes
# Python 2, score 1495

```
f=lambda n:range(-n/2+1,n/2+1)
f_A=f_B=f_C=f

def comb_set(A, B, C):
	return sorted({a*b+c for a in A for b in B for c in C})

def S(n):
	return comb_set(f_A(n), f_B(n), f_C(n))

```

Try it online!

A simple baseline of having each set be a length-n interval centered around 0, slightly unbalanced for even n. The TIO has Python code to compute your score.

```
1   1
2   3
3   5
4   10
5   13
6   21
7   25
8   36
9   41
10  55
11  61
12  78
13  85
14  105
15  113
16  136
17  145
18  171
19  181
20  210

Total: 1495

```

The size is `(n*n+1)/2` for odd n and `(n*n+n)/2` for even n.

# Answer
> 1 votes
# C++, score 1411

Conjecturing A and B are consecutive integers centered near 0, simply use simulated annealing to find C.

Source:

```
#include <algorithm>
#include <iostream>
#include <random>
#include <bitset>
#include <cmath>

using namespace std;

using bools = bitset<270>;
using irand = uniform_int_distribution<int>;
ranlux48 gen;
uniform_real_distribution<double> frand(0, 1);

int evaluate(const bools& a, const vector<int>& v)
{
    bools t = a;
    for (int i : v) t |= a << i;
    return t.count();
}

vector<int> best;
int best_score, prev_score;

void transition(double Temp, int Q, const bools& a, vector<int>& now)
{
    int rep, pos, tmp;
    do rep = irand(1, Q)(gen); while (find(now.begin(), now.end(), rep) != now.end());
    pos = irand(0, now.size() - 1)(gen);
    tmp = now[pos];
    now[pos] = rep;
    int now_score = evaluate(a, now);
    if (now_score <= prev_score || frand(gen) < exp((double)(prev_score - now_score))) {
        prev_score = now_score;
        if (now_score < best_score) best_score = now_score, best = now;
    }
    else now[pos] = tmp;
}

int main()
{
    int score = 0;
    for (int N = 1; N <= 20; N++) {
        gen.seed(0);
        int first = -N / 2, last = first + N, Q = N * 3;
        bools st;

        for (int i = first; i < last; i++)
            for (int j = first; j < last; j++)
                st[i * j + last * last] = true;

        vector<int> lst;
        for (int i = 1; i < N; i++) lst.push_back(i);

        best = lst;
        prev_score = best_score = evaluate(st, lst);

        if (N != 1)
            for (double Temp = 70.; Temp > 0; Temp -= 3e-5) transition(Temp, Q, st, lst);
        sort(best.begin(), best.end());
        cout << "N = " << N << "; |S| = " << best_score << endl;
        cout << " A = B = {";
        for (int i = first; i < last; i++) cout << i << (i != last - 1 ? ", " : "}\n");
        cout << " S = {0";
        for (int i : best) cout << ", " << i;
        cout << "}\n";

        score += best_score;
    }
    cout << "Score: " << score << endl;
}

```

Results:

```
N = 1; |S| = 1
 A = B = {0}
 S = {0}
N = 2; |S| = 3
 A = B = {-1, 0}
 S = {0, 1}
N = 3; |S| = 5
 A = B = {-1, 0, 1}
 S = {0, 1, 2}
N = 4; |S| = 10
 A = B = {-2, -1, 0, 1}
 S = {0, 1, 2, 3}
N = 5; |S| = 13
 A = B = {-2, -1, 0, 1, 2}
 S = {0, 1, 2, 3, 4}
N = 6; |S| = 21
 A = B = {-3, -2, -1, 0, 1, 2}
 S = {0, 1, 2, 3, 4, 5}
N = 7; |S| = 25
 A = B = {-3, -2, -1, 0, 1, 2, 3}
 S = {0, 1, 2, 3, 4, 5, 6}
N = 8; |S| = 35
 A = B = {-4, -3, -2, -1, 0, 1, 2, 3}
 S = {0, 3, 4, 6, 7, 10, 11, 14}
N = 9; |S| = 39
 A = B = {-4, -3, -2, -1, 0, 1, 2, 3, 4}
 S = {0, 3, 4, 6, 7, 8, 10, 11, 14}
N = 10; |S| = 53
 A = B = {-5, -4, -3, -2, -1, 0, 1, 2, 3, 4}
 S = {0, 1, 4, 5, 6, 9, 10, 11, 14, 15}
N = 11; |S| = 58
 A = B = {-5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5}
 S = {0, 1, 4, 5, 6, 9, 10, 11, 14, 15, 19}
N = 12; |S| = 74
 A = B = {-6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5}
 S = {0, 4, 5, 6, 9, 10, 11, 12, 15, 16, 17, 21}
N = 13; |S| = 80
 A = B = {-6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6}
 S = {0, 6, 10, 11, 12, 15, 16, 17, 18, 21, 22, 23, 27}
N = 14; |S| = 100
 A = B = {-7, -6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6}
 S = {0, 5, 6, 7, 11, 12, 13, 14, 18, 19, 20, 21, 25, 26}
N = 15; |S| = 106
 A = B = {-7, -6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7}
 S = {0, 5, 6, 7, 11, 12, 13, 14, 18, 19, 20, 21, 25, 26, 32}
N = 16; |S| = 128
 A = B = {-8, -7, -6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7}
 S = {0, 6, 7, 8, 13, 14, 15, 16, 21, 22, 23, 24, 29, 30, 31, 37}
N = 17; |S| = 135
 A = B = {-8, -7, -6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8}
 S = {0, 6, 7, 8, 13, 14, 15, 16, 21, 22, 23, 24, 29, 30, 31, 37, 45}
N = 18; |S| = 161
 A = B = {-9, -8, -7, -6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8}
 S = {0, 7, 8, 9, 14, 15, 16, 17, 18, 22, 23, 24, 25, 26, 31, 32, 33, 40}
N = 19; |S| = 167
 A = B = {-9, -8, -7, -6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
 S = {0, 7, 8, 9, 15, 16, 17, 18, 23, 24, 25, 26, 27, 32, 33, 34, 35, 41, 42}
N = 20; |S| = 197
 A = B = {-10, -9, -8, -7, -6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
 S = {0, 8, 9, 10, 16, 17, 18, 19, 20, 25, 26, 27, 28, 29, 35, 36, 37, 38, 45, 46}
Score: 1411

```

With -O2 on my computer, it takes 50 secs to compute all the results.

# Answer
> 0 votes
# Mathematica, score 1495

```
z = 0;
For[n = 1, n <= 20, n++,
r = Range[n] - Ceiling[n/2];
Print["S_n size=", x = (s = Length@#;
  Length@
   Union@Flatten@
     Table[#[[i]]*#[[j]] + #[[k]], {i, s}, {j, s}, {k, s}]) &[r],
"  ", "A=B=C=", r]; z = z + x]
Print["SCORE=", z]

```

> S\_n size=1 A=B=C={0}
> S\_n size=3 A=B=C={0,1}
> S\_n size=5 A=B=C={-1,0,1}
> S\_n size=10 A=B=C={-1,0,1,2}
> S\_n size=13 A=B=C={-2,-1,0,1,2}
> S\_n size=21 A=B=C={-2,-1,0,1,2,3}
> S\_n size=25 A=B=C={-3,-2,-1,0,1,2,3}
> S\_n size=36 A=B=C={-3,-2,-1,0,1,2,3,4}
> S\_n size=41 A=B=C={-4,-3,-2,-1,0,1,2,3,4}
> S\_n size=55 A=B=C={-4,-3,-2,-1,0,1,2,3,4,5}
> S\_n size=61 A=B=C={-5,-4,-3,-2,-1,0,1,2,3,4,5}
> S\_n size=78 A=B=C={-5,-4,-3,-2,-1,0,1,2,3,4,5,6}
> S\_n size=85 A=B=C={-6,-5,-4,-3,-2,-1,0,1,2,3,4,5,6}
> S\_n size=105 A=B=C={-6,-5,-4,-3,-2,-1,0,1,2,3,4,5,6,7}
> S\_n size=113 A=B=C={-7,-6,-5,-4,-3,-2,-1,0,1,2,3,4,5,6,7}
> S\_n size=136 A=B=C={-7,-6,-5,-4,-3,-2,-1,0,1,2,3,4,5,6,7,8}
> S\_n size=145 A=B=C={-8,-7,-6,-5,-4,-3,-2,-1,0,1,2,3,4,5,6,7,8}
> S\_n size=171 A=B=C={-8,-7,-6,-5,-4,-3,-2,-1,0,1,2,3,4,5,6,7,8,9}
> S\_n size=181 A=B=C={-9,-8,-7,-6,-5,-4,-3,-2,-1,0,1,2,3,4,5,6,7,8,9}
> S\_n size=210 A=B=C={-9,-8,-7,-6,-5,-4,-3,-2,-1,0,1,2,3,4,5,6,7,8,9,10}
> SCORE=1495

---
Tags: code-challenge, optimization, restricted-time, set-theory, restricted-memory
---


title: Randomized Brainfuck Compiler

text:
# Question
Title: Randomized Brainfuck Compiler
Joe is your average BF developer. He is about to check in his code changes to their repository when he gets a call from his boss. "Joe! The new client's machine is broken! The brainfuck interpreter sets all the cells to random values before program execution. No time to fix it, your code will have to deal with it." Joe doesn't think much of it, and is about to write a program to set the first million cells to zero, when his boss interrupts him again - "... and don't think about using brute force, the code has to be as small as possible." Now you have to help poor Joe!

## Specifications

* You will get some valid brainfuck code as input
* Your program will then modify the code so that it should work on a randomized brainfuck interpreter
* This means that before program execution, the cells can be set to any value.
* The new program should have the exact same behavior no matter the initial conditions.
* The interpreter will have max-cell value of 255 with wrapping, and an infinite length tape.

## Scoring

Your score is **10 times the compiler size in bytes** plus the **sum of the test case sizes**. Lowest score obviously wins.To mitigate against test-case optimization, I reserve the right to change the test-cases around if I suspect anything, and probably will do so before picking a winner.

## Test Cases

(I got these from the esolangs page and this webpage: http://www.hevanet.com/cristofd/brainfuck/). Also thanks to @Sparr for the last test case.

* Hello World: `++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]<-]>>.>---.+++++++..+++.>>.<-.<.+++.------.--------.>>+.>++.`
* Reverse Input: `>,[>,]<[.<]`
* Powers of Two (Infinite Stream): `>++++++++++>>+<+[[+++++[>++++++++<-]>.<++++++[>--------<-]+<<]>.>[->[
<++>-[<++>-[<++>-[<++>-[<-------->>[-]++<-[<++>-]]]]]]<[>+<-]+>>]<<]`
* Squares Under 10000: `++++[>+++++<-]>[<+++++>-]+<+[>[>+>+<<-]++>>[<<+>>-]>>>[-]++>[-]+>>>+[[-]++++++>>>]<<<[[<++++++++<++>>-]+<.<[>----<-]<]<<[>>>>>[>>>[-]+++++++++<[>-<-]+++++++++>[-[<->-]+[<<<]]<[>+<-]>]<<-]<<-]`
* Fibonacci Stream: `>++++++++++>+>+[[+++++[>++++++++<-]>.<++++++[>--------<-]+<<<]>.>>[[-]<[>+<-]>>[<<+>+>-]<[>+<-[>+<-[>+<-[>+<-[>+<-[>+<-[>+<-[>+<-[>+<-[>[-]>+>+<<<-[>+<-]]]]]]]]]]]+>>>]<<<]`
* ASCII Sequence till input: `,[.[>+<-]>-]` (This one requires varying cell numbers based on the input)

# Answer
> 8 votes
# sed, 46 byte compiler

```
s/</<</g
s/>/>[->[-]>[-]+<<]>/g
s/^/[-]>[-]+</

```

I didn't notice that the output was also supposed to be golf until after writing the program, so I will go for the short compiler. Also it was far too much work to test, so please notify if it does not function correctly :)

# Answer
> 2 votes
## C++

Compiler size : 630 bytes ( -10 bytes thanks to Zacharý )
Hello World compile result size : 139
Square under 10000 : 319

Compiler :

```
#include<string>
#include<map>
#include<stack>
#define B break
#define C case
#define S 30000
#define R m[(p<0)?(p%S)+S:p]
using s=std::string;using P=std::pair<int,int>;s a(s c){char m[S];memset(m,0,S);int p=0,i=0;P r{0,0};std::map<int,int>j;std::stack<int>t;for(int d=0;d<c.size();++d){if(c[d]==91)t.push(d);if(c[d]==93){j[d]=t.top();j[t.top()]=d;t.pop();}}while(i<c.size()){switch(c[i]){C'>':++p;B;C'<':--p;B;C'+':++R;B;C'-':--R;B;C'[':if(!R)i=j[i];B;C']':i=j[i]-1;B;default:B;}++i;r.first=p<r.first?p:r.first;r.second=p>r.second?p:r.second;}s n;for(int i=r.first;i<r.second;++i){n+="[-]>";}n+="[-]"+s(r.second,60)+c;return n;}

```

The randomized brainfuck interpreter :

```
void interpret(const std::string& code) {
    char memory[30000];
    for (int i = 0; i < 30000; ++i)
        memory[i] = std::rand()%256;
    int memPtr = 0, insPtr = 0;
    std::map<int, int> jump_map;

    {
        std::stack<int> jstack;
        for (int i = 0; i < code.size(); ++i) {
            if (code[i] == '[')
                jstack.push(i);
            if (code[i] == ']') {
                jump_map[i] = jstack.top();
                jump_map[jstack.top()] = i;
                jstack.pop();
            }
        }
    }
    while (insPtr < code.size()) {
        switch (code[insPtr]) {
        case '>': ++memPtr; break;
        case '<': --memPtr; break;
        case '+': ++memory[memPtr]; break;
        case '-': --memory[memPtr]; break;
        case '.': std::cout << memory[memPtr]; break;
        case ',': std::cin >> memory[memPtr]; break;
        case ']': if (memory[memPtr] != 0) insPtr = jump_map[insPtr]; break;
        case '[': if (memory[memPtr] == 0) insPtr = jump_map[insPtr]; break;
        default:break;
        }
        ++insPtr;
    }
}

```

Some notes :

* The compiler will execute the program to determine the memory cells that are used. If your program is an infinite loop, the compiler will loop infinitely.

# Answer
> 1 votes
# rs, 33 bytes, Score: 2659

Mostly just a simple port of the `sed` answer.

```
</<<
>/>[->[-]>[-]+<<]>
[-]>[-]+<

```

---
Tags: code-golf, brainfuck, metagolf
---