title: Sort a concatenated sequence

text:
# Question
Title: Sort a concatenated sequence
Consider a sequence based on recurrence relations, `f(n) = f(n-1)+f(n-2)`, starting with `f(1) = x1, f(2) = x2`. For `x1 = 2, x2 = 1`, the sequence begins like this:

```
2  1  3  4  7  11  18  29  47  76  123  199  322  521  843

```

Concatenating this into a string will give:

```
213471118294776123199322521843

```

Now, divide this list into the smallest possible numbers that gives `y(n) > y(n-1)`. Start with the first number, then the second etc. The first output number should always be a single digit. Pad the last number with the required number of zeros.

```
2 13 47 111 829 4776 12319 93225 218430

```

You will get two numbers, `(x1, x2)` as input, on any convenient format, and the challenge is to output the sorted list.

**Rules:**

* Function and programs are OK
* The initial sequence shall have exactly 15 numbers (The last number is `f(15)`).
* `x1` and `x2` are non-negative (zero is possible).
* The output can be on any convenient format
* The output vector `y` must be created so that `y2 > y1`.
    + First the smallest possible `y1`, then the smallest possible `y2`, then `y3` and so on.
* If `x1 = x2 = 0` then output 15 zeros (on the same format as other output, i.e. not `000000000000000`).

**Examples**:

```
Input: 1 1
Output: 1  12  35  81  321  345  589  1442  3337 7610

Input: 3 2
Output: 3  25  71  219  315  0811 3121  23435 55898 145300
                             |
                             Optional leading zero
Input: 0 0
Output: 0  0  0  0  0  0  0  0  0  0  0  0  0  0  0

```

The shortest code in bytes wins. Please include a link to an online interpreter if possible.

# Answer
> 1 votes
# Pyth, 56 bytes

```
LsgM.:sMb2?sQsM.WyHX_1Z`0u?yGX_1GHaGHjkhM.u,eNsN14QYmZ15

```

Test suite

**Explanation:**

First, we check whether the input is precisely `0, 0`. If so, print 15 zeros.

Otherwise, we produce the sequence, with `jkhM.u,eNsN14Q`. This is similar to the standard Pyth algorithm for the Fibonacci sequence.

Next, we reduce over this string. The accumulator is a list of strings, representing each number in the divided sequence. At each reduction step, we take the next character, and check whether the accumulator is in order, using the helper function `y`, defined with `LsgM.:sMb2`, which is truthy iff the input is out of order. If it is in order, we append the next character to the list as its own number. If not, we add the next character to the end of last string. This is accomplished with `u?yGX_1GHaGH ... Y`.

Next, we perform a functional while loop. The loop continues until the running list is in order, reusing the helper function. At each step, a `0` is added to the end of the last string in the list. This is accomplished with `.WyHX_1Z`0`.

Finally, the strings are converted to integers, with `sM`, and printed.

---

# Pyth, 51 bytes

```
LsgM.:sMb2?sQsM.WyHX_1Z`0hf!yT_./jkhM.u,eNsN14QmZ15

```

I believe this works, but it is far too slow to test - it's a brute force solution for dividing the string.

---

I will be making some improvements to the `X` function, but the above code works in the version of Pyth that was most recent when the question was posted.

# Answer
> 5 votes
# JavaScript ES6, 127 ~~135~~

```
(a,b)=>eval("for(n=r=[],v=13,o=a+n+b;v--;a=b,b=t)o+=t=b+a;for(d of o+'0'.repeat(99))(n+=d)>+v&&(r.push(v=n),n='');+v?r:[...o]")

```

**Test**

```
F=(a,b)=>eval("for(n=r=[],v=13,o=a+n+b;v--;a=b,b=t)o+=t=b+a;for(d of o+'0'.repeat(99))(n+=d)>+v&&(r.push(v=n),n='');+v?r:[...o]")

// less golfed

U=(a,b)=>{
  for(n=r=[], o=a+n+b, v=13; v--; a=b, b=t)
    o+= t= b+a;
  for(d of o+'0'.repeat(99))
    if ((n+=d) > +v)
      r.push(v=n), n='';
  return +v ? r : [...o]
}

function test(){
  var i = I.value.match(/\d+/g)
  O.textContent = i.length > 1 ? F(+i[0],+i[1]) : ''
}
test()
```

```
A,B : <input id=I value='0 1' oninput='test()'>
<pre id=O></pre>
```

# Answer
> 2 votes
## JavaScript ES6, ~~187~~ ~~180~~ ~~187~~ ~~184~~ ~~182~~ ~~179~~ ~~175~~ ~~172~~ ~~165~~ ~~160~~ ~~155~~ 154 bytes

```
(a,b)=>eval('d=""+a+b;for(i=-12,j=1;++i<99;)i<2?(c=b,d+=b=a+b,a=c,r=a?[d[0]]:"0,".repeat(15)):(f=+d.slice(j,i))>r[r.length-1]?(r.push(f),j=++i-1):d+=0;r')

```

I get similar results when run it for `1,1` and `3,2` test cases. `0,0` has taken an excess 26 bytes...

De-golf + converted to ES5 + demo:

```
function s(a, b) {
  d = "" + a + b;
  for (i = -12, j = 1; ++i < 99;)
    i < 2 ?
      (c = b, d += b = a + b, a = c, r = a ? [d[0]] : "0,".repeat(15))
    : (f = +d.slice(j, i)) > r[r.length - 1] ?
      (r.push(f), j = ++i - 1)
      : d += 0;
  return r
}
document.write(
   s(1,1)+"<br>"+
   s(3,2)+"<br>"+
   s(0,0)
)
```

# Answer
> 1 votes
# JavaScript (ES6), 162 bytes

```
(a,b)=>(k=[...Array(15).keys(y="")],p=-1,z=k.map(_=>0),a|b?[...k.map(f=n=>n--?n?f(n)+f(n-1):b:a).join``,...z].map(d=>+(y+=d)>p?(p=y,y=" ",p):"").join``:z.join` `)

```

## Explanation

```
(a,b)=>(
  k=[...Array(15).keys(y="")],     // k = array of numbers 0 to 14, initialise y
  p=-1,                            // initialise p to -1 so that 0 is greater than p
  z=k.map(_=>0),                   // z = array of 15 zeroes
  a|b?[                            // if a and b are not 0
      ...k.map                     // for range 0 to 14
      (f=n=>n--?n?f(n)+f(n-1):b:a) // recursive sequence function (0 indexed)
      .join``,                     // join result of f(0) to f(14) as a string
      ...z                         // append zeroes for padding
    ].map(d=>                      // for each digit of concatenated result
      +(y+=d)                      // append the digit to the current number y
      >p?(                         // if the current number is greater than the previous p
        p=y,                       // set previous to the current number
        y=" ",                     // reset y (with space as a separator)
        p                          // output the current number (with space at the start)
      ):""                         // else add nothing to the output
    )
    .join``                        // return the output as a string
  :z.join` `                       // return a bunch of zeroes if a and b are 0
)

```

## Test

```
var solution = (a,b)=>(k=[...Array(15).keys(y="")],p=-1,z=k.map(_=>0),a|b?[...k.map(f=n=>n--?n?f(n)+f(n-1):b:a).join``,...z].map(d=>+(y+=d)>p?(p=y,y=" ",p):"").join``:z.join` `)
```

```
x1 = <input type="number" id="x1" value="3" /><br />
x2 = <input type="number" id="x2" value="2" /><br />
<button onclick="result.textContent=solution(+x1.value,+x2.value)">Go</button>
<pre id="result"></pre>
```

# Answer
> 1 votes
## Haskell, ~~165~~ ~~159~~ ~~152~~ ~~142~~ 141 bytes

```
w=take 15
x#y=x:scanl(+)y(x#y)
0%0=w[0,0..]
x%y=g(-1)(w(x#y)++0%0>>=show)(-1)
g _""_=[]
g b l@(h:t)a|b>a=b:g 0l b|1<2=g(max 0b*10+read[h])t a

```

Usage example: `3 % 2` -\> `[3,25,71,219,315,811,3121,23435,55898,145300]`.

Online demo (with a `main` wrapper).

How it works:

```
w=take 15
x#y=x:scanl(+)y(x#y)              -- fibonacci sequence generator for x and y

0%0=w[0,0..]                      -- special case 0%0
x%y=g(-1)(w(x#y)++0%0>>=show)(-1) -- calculate fib sequence, add some extra 0 and
                                  -- flatten all digits into a single string.
                                  -- start calculating the resulting sequence

g _""_=[]                         -- if we don't have digits left, stop.
                                  -- the final 0 in the second parameter is ignored.
g b l@(h:t)a
  |b>a=b:g 0l b                   -- if the current number is greater than the
                                  -- previous one, take it and start over.
  |1<2=g(max 0b*10+read[h])t a    -- otherwise add the next digit and retry.
                                  -- The "max" fixes the initial call with -1.

```

# Answer
> 1 votes
# Mathematica, 192 bytes

```
f[{0,0}]:=0~Table~15
f@l_:=(t=0;q={};If[#>0,q~Join~{10^⌈Log10[t/#]⌉#},q]&[Last@#]&@FoldList[If[#>t,AppendTo[q,t=#];0,#]&[10#+#2]&,0,Flatten@IntegerDigits@SequenceFoldList[#+#2&,l,Range@13]])

```

Test cases:

```
f[{2, 1}]
(* {2, 13, 47, 111, 829, 4776, 12319, 93225, 218430} *)
f[{3, 2}]
(* {3, 25, 71, 219, 315, 811, 3121, 23435, 55898, 145300} *)
f[{0, 0}]
(* {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0} *)

```

The lengths of the function names are killing me.

# Answer
> 1 votes
# K (ngn/k), 61 bytes

```
(|/<':){@[x;t-1;(0^x t)+10*]_t:1+*&~0>':x}/.',/$13{x,+/-2#x}/

```

Try it online!

* `.',/$13{x,+/-2#x}/` builds the sequence, converting it into a list of (integer) digits
* `(|/<':)` is used as the while condition, causing iteration to continue so long as there is any number in the list smaller than its predecessor
* `t:1+*&~0>':x` identifies the index immediately after the first value less than or equal to its predecessor
* `@[x;t-1;(0^x t)+10*]` is used to merge numbers in the list together; e.g. `1 2` becomes `12 2`. Since indexing a list out of bounds returns a null, we zero-fill with `0^`. This handles the last iteration, where we may need to append additional 0's
* `@[...]_t` removes the "leftover" value at index `t` from the left-hand-side list (e.g. `12 2` becomes `12`)

# Answer
> 0 votes
## PowerShell, ~~167~~ 166 bytes

```
param($x,$w)if($w-lt($x-eq0)){"0`n"*15;exit}[char[]]("$x"+-join(0..13|%{$w;$w=$x+($x=$w)}))|%{$z+="$_";if(+$z-gt$y){($y=$z);$z=""}};if($z){while(+$z-lt$y){$z+="0"}$z}

```

Saved a byte by eliminating the `$s` variable and just feeding the output loop directly.

### Ungolfed and commented:

```
param($x,$w)           # Take input parameters as x and w
if($w-lt($x-eq0)){     # If x=0, ($x-eq0)=1, so $w-lt1 implies w=0 as well
  "0`n"*15             # Print out 15 0's separated by newlines
  exit                 # And exit program
}                      # otherwise ...
[char[]](              # Construct the sequence string as a char-array
"$x"+-join(            # Starting with x and concatenated with a joined array
  0..13|%{             # Loop
    $w                 # Add on w
    $w=$x+($x=$w)      # Recalculate for next loop iteration
  }
))|%{                  # Feed our sequence as a char-array into a loop
  $z+="$_"             # z is our output number, starts with the first digit
  if(+$z-gt$y){        # If z is bigger than y (initialized to 0)
    ($y=$z)            # Set y equal to z and print it
    $z=""              # Reset z to nothing to start building the next number
  }
}
if($z){                # If there is remaining digits, we need to pad zeroes
  while(+$z-lt$y){     # Until z is bigger than y
    $z+="0"            # Tack on a zero
  }
  $z                   # Print the final number
}

```

# Answer
> 0 votes
# Perl 6, 107 bytes

```
{$_=@=(|@_,*+*...*)[^15].join.comb;.sum??[.shift,{last if !@$_;until (my$a~=.shift//0)>$^b {};$a}...*]!!$_} # 107

```

### Usage:

```
# give it a lexical name for ease of use
my &code = {...}

# use ｢eager｣ because the anonymous block returns a lazy array
# and ｢say｣ doesn't ask it to generate the values
say eager code 2, 1;
# [2 13 47 111 829 4776 12319 93225 218430]
say eager code 1, 1;
# [1 12 35 81 321 345 589 1442 3337 7610]
say eager code 3, 2;
# [3 25 71 219 315 0811 3121 23435 55898 145300]
say eager code 0, 0;
# [0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
say eager code 0, 1;
# [0 1 12 35 81 321 345 589 1442 3337 7000]

```

### Explanation

creates a Fibonacci like sequence, starting with the arguments (`@_`) slipped (`|`) in

```
|@_,*+*...*

```

takes the first 15 elements of that sequence

```
(…)[^15]

```

combines that into a single string (`.join`), splits it into a sequence of individual characters (`.comb`) and stores that in the "default" scalar (`$_`) after coercing the sequence into a mutable array, by first storing it in an anonymous array (`@`)

```
$_=@=(…)[^15].join.comb;

```

it finds the sum of the values in the default scalar, and if that is zero returns the default scalar, which will contain an array of 15 zeros

```
.sum?? … !!$_

```

if the sum isn't zero, it creates a list by first shifting off the first element in the default scalar

```
.shift, …

```

followed by generating the rest of the values, checking it against the previous one (`$^b`)
if the default scalar runs out of values, use 0 instead (`//0`)

```
…,{ … ;until (my$a~=.shift//0)>$^b {};$a}...*

```

stopping when there is no elements left in the default scalar

```
…,{last if !@$_; … }...*

```

# Answer
> 0 votes
# Jelly, 39 bytes

```
-.ị
ÇSṭƊ13¡DFŒṖḌ<ƝṖẠƊƇḢṪ×⁵ṭƲÇ>/$¿µṁS?15

```

Try it online!

This is unbelievably inefficient, both time-wise and memory-wise. You can see it in action for up to \\$f(11)\\$ on TIO, but it times out if you include up to \\$f(15)\\$. Luckily, the run time does not heavily depend on the input, so is generally constant. However, Python will usually error due to memory restrictions

## How it works

This works by generating all partitions of the digits of the sequence and keeping those which are strictly ascending, ignoring the last element. Due to the way Jelly generates the partitions of a list, this yields the intended array as the first such partition.

```
-.ị - Helper link. Takes an array, A, on the left
-.  - Yield -0.5
  ị - Take the -0.5th element of A, which returns the last 2 elements

ÇSṭƊ13¡DFŒṖḌ<ƝṖẠƊƇḢṪ×⁵ṭƲÇ>/$¿µṁS?15 - Main link. Takes [a,b] on the left
                                ?   - If statement:
                               S    -   Condition: sum (i.e. a ≠ 0, b ≠ 0)
                             µ      -   If:
   Ɗ                                -     Define a monad f(A):
Ç                                   -       Take the last two elements of A
 S                                  -       Take their sum
  ṭ                                 -       Tack the sum to the end of A
    13¡                             -     Repeat f(A) 13 times, starting with A = [a, b]
       D                            -     Convert to digits
        F                           -     Flatten into an array, D
         ŒṖ                         -     Yield all partitions of D
           Ḍ                        -     Convert arrays back to decimals
                Ɗ                   -     Define a monad g(A):
             Ɲ                      -       Over overlapping pairs of A:
            <                       -         Is less than?
              Ṗ                     -       Remove the last
               Ạ                    -       All true?
                 Ƈ                  -     Keep the partitions which are true under g(A)
                  Ḣ                 -     Take the first one, P
                            ¿       -     While loop:
                           $        -       Condition:
                        Ç           -         Last 2 elements of P
                         >/         -         First is greater than the second
                       Ʋ            -       Body:
                   Ṫ                -         Last element of P
                    ×⁵              -         Times 10
                      ṭ             -         Tack to the end of P
                              ṁ  15 -   Else: Repeat to length 15

```

# Answer
> 0 votes
# Stax, <sup>~~53~~</sup> 52 bytes

```
Ü⌐↓├¶cRU!>πf_╙ⁿεd╔╘≥↔IQ┘┼▐↓▒Φ╙ε☺ÉL╚Jö┤Å☺╠╓§j╨áuf░╢A╬

```

Run and debug it

Not too well optimized, can probably be shortened a lot.

However, pretty proud that I managed to make it work for all the testcases.

It uses the X and Y registers to store previous values while comparing them in the loop, then pushes X to stack when the Y is greater than it.

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


title: Implement the Enigma Machine

text:
# Question
Title: Implement the Enigma Machine
The Enigma machine is a fairly complex cipher machine used by the Germans and others to encrypt their messages. It is your job to implement this machine\*.

# Step 1, Rotation

Our enigma machine has 3 slots for rotors, and 5 available rotors for each of these slots. Each rotor has 26 different possible positions (from `A` to `Z`). Each rotor has a predefined *notch position*:

```
Rotor  Notch
------------
1      Q
2      E
3      V
4      J
5      Z

```

On keypress the following steps occur:

1. The rotor in Slot 1 rotates
2. If the rotor in Slot 1 moves past its notch, then it rotates the rotor in Slot 2.
3. If the rotor in Slot 2 is in its notch (but didn't just move there), both rotor 2 and 3 rotate once.

*If we are using rotors 1,3,5 and they are in positions `P,U,H` then the sequence of positions is: `P,U,H` \> `Q,U,H` \> `R,V,H` \> `S,W,I`*

# Step 2, Substitution

Each of the rotors performs a simple character substitution. The following is a chart of each of the rotors in the `A` position:

```
  ABCDEFGHIJKLMNOPQRSTUVWXYZ
  --------------------------
1 EKMFLGDQVZNTOWYHXUSPAIBRCJ
2 AJDKSIRUXBLHWTMCQGZNPYFVOE
3 BDFHJLCPRTXVZNYEIWGAKMUSQO
4 ESOVPZJAYQUIRHXLNFTGKDCMWB
5 VZBRGITYUPSDNHLXAWMJQOFECK
R YRUHQSLDPXNGOKMIEBFZCWVJAT

```

*Rotor 1 in position T is `PAIBRCJEKMFLGDQVZNTOWYHXUS`, which would substitute the letter `C` for `I`.*

After the three rotors perform their substitution, the *reflector* is hit (listed as `R` above). It performs its own substitution, and then reflects the signal back through the rotors. The rotors then perform a reverse substitution in reverse order.

*Reverse substitution means that instead of Rotor 1 substituting `A` with `E`, it substitutes `E` with `A`*

*Slots are filled with rotors 1,2,3 all in position `A`. The letter `Q` follows the path `Q>X>V>M` through the rotors. `M` reflects to `O`, which then follows the reverse path of `O>Z>S>S`. Therefore, `A` is substituted with `S`.*

# Input/Output

You are passed:

1. A list of 3 rotors (as integers)
2. A list of 3 starting rotor positions (as letters)
3. A string that needs to be encrypted.

You can assume that your input will be well formed, and all characters will be uppercase letters, no spaces.

You must return the encrypted string.

You can optionally accept the rotors, notches, and reflectors as input. For those that don't can take off 95 bytes from their score, as `95 = ceil(log2(26 letters ^(26*6 rotors +5 notches))/8 bytes)`

# Test cases

```
Rotor Position Input              Output
4,1,5 H,P,G    AAAAAAAAA          PXSHJMMHR
1,2,3 A,A,A    PROGRAMMINGPUZZLES RTFKHDOCCDAHRJJDFC
1,2,3 A,A,A    RTFKHDOVZSXTRMVPFC PROGRAMRXGVGUVFCES
2,5,3 U,L,I    GIBDZNJLGXZ        UNCRAUPSCTK

```

My implementation can be found on Github. I've tested it, but I may have bugs in my implementation (which would mean that my test cases are likely wrong).

<sub>\*I've tried to make this as accurate as possible, but due to the variations between machines, I may have some details wrong. However, your task is to implement what I've described, even if I'm inaccurate. I'm not including the plugboard for simplicity</sub>

# Answer
> 21 votes
# Jelly, ~~42~~ ~~38~~ 37 bytes

```
="⁵Ḣ€Ṗ1;ṙ@"µɼ⁶ṭØAiịɗƒµ®Ṛi@ịØAɗƒ
ḷ⁹©Ç€

```

Try it online!

Verify each test case

This is *extremely* liberal with the input format. It takes input in the following way:

* The three rotors (the strings, not the numbers) as the first command line argument, each rotated so that the starting points are the first characters
* The message as the second command line argument
* The 3 specific notches as the third command line argument
* The reflector as the fourth command line argument

In the above TIO link, the Footer converts a triple of numbers (the rotors) into the rotor strings, then rotates them to the correct order, so that you don't have to do it yourself.

However, for 45 bytes we can have a program which takes input in the following way:

* The message, on STDIN
* The three rotors (as the strings) as the first command line argument
* The 3 specific notches as the second command line argument
* The reflector as the third command line argument
* The three starting points for the rotors as the fourth command line argument

Again, the Footer converts the rotors from integers to the corresponding strings.

Finally, if we want to go all the way and just accept 3 inputs (the rotors, as integers, the starting positions and the message (thus have -95 to our score)), we get a score of 44

---

## How it works

As they all use the same underlying algorithm, I'll just explain the 38 byte version in full, and I'll cover how the other two versions adapt the inputs to match the shortest version. For this explanation: `M` is the message, `R` are the three rotor strings, `N` are the notches, `F` is the reflector and `C` is the value in the register (initially 0).

```
ḷ⁹©Ç€ - Main link. Takes M on the left and R on the right
 ⁹    - Yield R
  ©   - And copy it into the register. C = R
ḷ     - Discard R and yield M
    € - Over each character in M:
   Ç  -   Call the helper link
        Implicitly output the final result

="⁵Ḣ€Ṗ1;ṙ@"µɼ⁶ṭØAiịɗƒµ®Ṛi@ịØAɗƒ - Helper link. Takes a character X on the left

="⁵Ḣ€Ṗ1;ṙ@"µɼ                   - Rotate the rotors
            ɼ                   - Yield C, run the following on it, save the result to C:
           µ                    -   Initially, C = R, the list of rotors
  ⁵                             -   Yield the notches, N
 "                              -   Pair each notch with each rotor, then:
=                               -     Vectorised equality
   Ḣ€                           -   Take the head of each
                                      This yields a triple of bits [a, b, c]
                                      which indicate which rotor hits its notch
     Ṗ                          -   Remove c as rotor 3 has no affect
      1;                        -   Prepend 1 as rotor 1 always moves; [1, a, b]
          "                     -   Pair 1 with rotor 1, a with rotor 2 and b with rotor 3,
                                        then for each pair:
        ṙ@                      -     Rotate the rotor if the bit is 1

             ⁶ṭØAiịɗƒ           - Send the character through the rotors
             ⁶                  - Yield the reflector F
              ṭ                 - Tack it to the end of the rotors, call this C'
                   ɗ            - Group the previous 3 links into a dyad f(U, L):
                                   where U is a character and L a list of characters
               ØA               -   "ABC...XYZ"
                 i              -   Index of U in the alphabet
                  ị             -   Index into L
                    ƒ           - Starting with X, reduce C' by the dyad f(U, L)
                                  As C is a triple of lists of characters, this returns
                                  A = f(f(f(f(X, C[1]), C[2]), C[3]), F), a single character

                     µ®Ṛi@ịØAɗƒ - Send A back through the rotors
                     µ          - Begin a new link with A as the argument
                             ɗ  - Group the previous 3 links into a dyad g(U, L)
                        i@      -   Index of U in L, i
                          ịØA   -   i'th letter of the alphabet
                      ®         - Yield C
                       Ṛ        - Reverse C
                              ƒ - Starting with A, reduce rev(C) by the dyad g(U, L)
                                      This yields g(g(g(A, C[3]), C[2]), C[1]),
                                      which is our intended result

```

## How the other 2 work

### The 45 byte version

Taking a look at the code, we notice that the only thing that's changed is that the last line is now

```
ṙ"©⁶O_65¤ṛɠÇ€

```

The difference between this version and the 37 byte version is how the rotors are taken as input:

> The three rotors (the strings, not the numbers) as the first command line argument, **each rotated so that the starting points are the first characters**

> The three rotors (as the strings) as the first command line argument

The new bits here just rotate the rotors for us and take `M` from STDIN:

```
ṙ"©⁶O_65¤ṛɠÇ€ - Main link. Takes R on the left
        ¤     - Create a nilad:
   ⁶          -   The 3 starting points of the rotors
    O         -   Converted to char points
     _65      -   Minus 65
 "            - Zip with each rotor:
ṙ             -   Rotate the rotor that many steps
  ©           - Save this to the register
          ɠ   - Read M from STDIN
         ṛ    - Discard the rotors and yield M
           Ç€ - Call the helper link on each character of M

```

### The 139 byte version

Let's take a look at the full code:

```
="³ị“QEVJZ”¤Ḣ€Ṗ1;ṙ@"µɼ“¡ƝḋœṚṗḶw⁸Aß`’œ?ØA¤ṭØAiịɗƒµ®Ṛi@ịØAɗƒ
ị“F.⁻wṣḊ£tọḅɱ“¥AṡḌỴịk⁼UH9“Ñɱ½#Ẋʋẹ¹⁼UṢ“KzBpñÇḅẊẎḳḣ“¡j5ɼ}ṡỴb\£BṆ’œ?ØAṙ"©⁴O_65¤ṛɠÇ€

```

Try it online!

This is very similar to our 45 byte version. In fact, here's what's different in the first lines, with everything that is unchanged, replaced with `.`

```
..³ị“QEVJZ”¤..........“¡ƝḋœṚṗḶw⁸Aß`’œ?ØA¤.................

```

Furthermore, you'll note that the end of the first line is `ṙ"©⁴O_65¤ṛɠÇ€`, which is the first line of the 45 byte version, meaning that there are really only three changes. In this case, those changes are because of the changes to the input system. Here's the first 2:

* \\$\to\\$ `³ị“QEVJZ”¤`. Rather than take the notches as input, we use the rotor list (`³`) to ndex into the string of notches `“QEVJZ”`. The `¤` is simply a precedence marker, telling the program to treat this as a constant
* \\$\to\\$ `“¡ƝḋœṚṗḶw⁸Aß`’œ?ØA¤`. Again, this is changing an input into program data, the reflector in this case. `¤` Once again acts as a precedence marker. However, we have 3 new commands here:

+ `œ?` is a dyad which takes 2 arguments - on the left, an integer `x`, and on the right a string, `s` \- and returns the `x`'th permutation of `s`
    + `ØA` we've already encountered, and is the uppercase alphabet. In this context, it acts as the right argument to `œ?`
    + `“¡ƝḋœṚṗḶw⁸Aß`’` is the compressed integer \\$383316524290458478707255597\\$, which is the left argument to `œ?`

Together, this returns the \\$383316524290458478707255597\\$th permutation of the uppercase alphabet, or the string `"YRUHQSLDPXNGOKMIEBFZCWVJAT"`

The final change is the entire start of the last line:

```
ị“F.⁻wṣḊ£tọḅɱ“¥AṡḌỴịk⁼UH9“Ñɱ½#Ẋʋẹ¹⁼UṢ“KzBpñÇḅẊẎḳḣ“¡j5ɼ}ṡỴb\£BṆ’œ?ØA

```

Here, we have a list of massive compressed numbers:

```
“F.⁻wṣḊ£tọḅɱ“¥AṡḌỴịk⁼UH9“Ñɱ½#Ẋʋẹ¹⁼UṢ“KzBpñÇḅẊẎḳḣ“¡j5ɼ}ṡỴb\£BṆ’

```

Each  marks the beginning of a new compressed number, and the entire list is

```
[67892310845892591685803413, 5023890671354916271018308, 16834429128340685633834184, 72949485053238139997554738, 340670280577577536609579431]

```

We then take the three integers which correspond to the three rotor inputs with , and then use `œ?ØA` to generate the alphabet permutations we want for each rotor. Finally, these permutations are fed into the rest of the program, already covered above.

# Answer
> 13 votes
# Python 3, 403 bytes

I think this is working correctly. The rotors passed to it:

```
def z(p,o,m,f,g,h):
 O=ord;b=lambda a:a[1:]+a[:1];d=lambda a:chr(a+O('A'));e=lambda a:O(a)-O('A');i=[list(g[i-1])for i in p];j=[f[i-1]for i in p];i=[x[e(y):]+x[:e(y)]for x,y in zip(i,o)];k=[]
 for l in m:
  if i[0][0]==j[0]:i[1]=b(i[1])
  elif i[1][0]==j[1]:i[1]=b(i[1]);i[2]=b(i[2])
  i[0]=b(i[0]);c=l
  for n in i:c=n[e(c)]
  c=h[e(c)]
  for n in reversed(i):c=d(n.index(c))
  k+=[c]
 return''.join(k)

```

`f` is the notch, `g` is the rotors and `h` is the reflector.

Ungolfed:

```
shift = lambda rotor: rotor[1:] + rotor[:1]
letter = lambda num: chr(num + ord('A'))
number = lambda chr: ord(chr) - ord('A')

def encode(rotors, rotorStart, message, defaultRotors, reflector, rotorNotchPositions):
    usedRotors = [list(defaultRotors[i - 1]) for i in rotors]
    notches = [rotorNotchPositions[i - 1] for i in rotors]
    usedRotors = [rotor[number(offset):] + rotor[:number(offset)] for rotor, offset in zip(usedRotors, rotorStart)]

    sub = []

    for char in message:
        # print([''.join(rotor) for rotor in usedRotors])
        if usedRotors[0][0] == notches[0]:
            usedRotors[1] = shift(usedRotors[1])
        elif usedRotors[1][0] == notches[1]:
            usedRotors[1] = shift(usedRotors[1])
            usedRotors[2] = shift(usedRotors[2])

        usedRotors[0] = shift(usedRotors[0])

        c = char
        for rotor in usedRotors:
            c = rotor[number(c)]
        c = reflector[number(c)]
        for rotor in reversed(usedRotors):
            c = letter(rotor.index(c))
        sub += [c]
        print([''.join(rotor) for rotor in usedRotors], char, c, message)

    return ''.join(sub)

rotorNotchPositions = 'QEVJZ'
*defaultRotors, reflector = [
    #ABCDEFGHIJKLMNOPQRSTUVWXYZ#
    "EKMFLGDQVZNTOWYHXUSPAIBRCJ",  # 1
    "AJDKSIRUXBLHWTMCQGZNPYFVOE",  # 2
    "BDFHJLCPRTXVZNYEIWGAKMUSQO",  # 3
    "ESOVPZJAYQUIRHXLNFTGKDCMWB",  # 4
    "VZBRGITYUPSDNHLXAWMJQOFECK",  # 5
    "YRUHQSLDPXNGOKMIEBFZCWVJAT"   # R
]

#             Rotor       Position        Input                 Output
assert encode((4, 1, 5), ('H', 'R', 'G'), 'AAAAAAAAA',
              defaultRotors, reflector, rotorNotchPositions) == 'PXSHJMMHR'
assert encode((1, 2, 3), ('A', 'A', 'A'), 'PROGRAMMINGPUZZLES',
              defaultRotors, reflector, rotorNotchPositions) == 'RTFKHDOCCDAHRJJDFC'
assert encode((1, 2, 3), ('A', 'A', 'A'), 'RTFKHDOVZSXTRMVPFC',
              defaultRotors, reflector, rotorNotchPositions) == 'PROGRAMRXGVGUVFCES'
assert encode((2, 5, 3), ('U', 'L', 'I'), 'GIBDZNJLGXZ',
              defaultRotors, reflector, rotorNotchPositions) == 'UNCRAUPSCTK'

```

I think this is working, but it produces a different output, due to what (I think) is a bug in the reference impl.

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


title: Brainf*** Golfer

text:
# Question
Title: Brainf*** Golfer
One of easiest code written by a programming language is a program printing sequence of characters (ex. "Hello, world!"). However,   programming languages like Brainfuck, even this simplest code is quite annoying to write.

Your task is to write a program (don't have to written in brainfuck), which prints a (minimum-length) Brainfuck program printing the given text.

## Input

A sequence of characters (between `1` and `255`) is given by any format (variable, argument, stdin, file, ...).

## Output

Output is a valid (no non-matching `[` and `]`) brainfuck code (assume unsigned 8-bit wrapping cell and unlimited number of cells to left and right) printing exact string that was given as input.

For example, one possible output for input `A` is `++++++++[<++++++++>-]<+.`.

Your program shouldn't take long time (`>2m`) to run.

The BF program shouldn't take long time (`>10s`) to run.

## Scoring

*(Notice : current scoring method may change, since it is not easy to calculate...)*

The length of program (generating BF code) itself *doesn't* matter. However, hard-coding BF codes in the program code is not OK. Only acceptable range (ex. a BF code printing a single character `0x01` : `+.`) of BF codes might be hard-coded.

The score is sum of length of BF codes printing these strings.

* A string `Hello, world!` appended with a single `0x0A` (`\n`) (i.e. the "Hello, world!" program)
* Single character from `0x01` ~ `0xFF`
    + Sum of length of these 255 BF codes are multiplied by `1/16`, rounded, and added to the score.
* List of first 16 strings, generated by splitting a random sequence of bytes generated on 11-11-11 by `0x00`, removing all zero-length strings.
* Lenna.png, removing all `0x00`s.
* Lyrics of the song 99 bottles of beer, starting with `99 bottles~`, newlines are `0x0A`, paragraphs are separated by two `0x0A`s, and no newline character at the end.
* Other strings you may provide.

Your program may include calculating the score of itself.

Of-course, lowest-score code will be the winner.

# Answer
In Java, computes a short BF snippet which can convert any number to any other number. Each output byte is generated by either transforming the last output byte or a fresh 0 on the tape.

The snippets are generated in three ways. First by simple repetitions of `+` and `-` (e.g. `++++` converts 7 to 11), by combining known snippets (e.g. if A converts 5 to 50 and B converts 50 to 37, then AB converts 5 to 37) and simple multiplications (e.g. `[--->+++++<]` multiplies the current number by 5/3). The simple multiplications take advantage of wraparound to generate unusual results (e.g. `--[------->++<]>` generates 36 from 0, where the loop executes 146 times, with a total of 4 descending and 1 ascending wraparounds).

I'm too lazy to compute my score, but it uses about 12.3 BF operations per byte on `Lenna.png`.

```
import java.io.*;

class shortbf {
    static String repeat(String s, int n) {
        StringBuilder b = new StringBuilder();
        for (int i = 0; i < n; i++) b.append(s);
        return b.toString();
    }

    // G[x][y]: BF code that transforms x to y.
    static String[][] G = new String[256][256];
    static {
        // initial state for G[x][y]: go from x to y using +s or -s.
        for (int x = 0; x < 256; x++) {
            for (int y = 0; y < 256; y++) {
                int delta = y - x;
                if (delta > 128) delta -= 256;
                if (delta < -128) delta += 256;

                if (delta >= 0) {
                    G[x][y] = repeat("+", delta);
                } else {
                    G[x][y] = repeat("-", -delta);
                }
            }
        }

        // keep applying rules until we can't find any more shortenings
        boolean iter = true;
        while (iter) {
            iter = false;

            // multiplication by n/d
            for (int x = 0; x < 256; x++) {
                for (int n = 1; n < 40; n++) {
                    for (int d = 1; d < 40; d++) {
                        int j = x;
                        int y = 0;
                        for (int i = 0; i < 256; i++) {
                            if (j == 0) break;
                            j = (j - d + 256) & 255;
                            y = (y + n) & 255;
                        }
                        if (j == 0) {
                            String s = "[" + repeat("-", d) + ">" + repeat("+", n) + "<]>";
                            if (s.length() < G[x][y].length()) {
                                G[x][y] = s;
                                iter = true;
                            }
                        }

                        j = x;
                        y = 0;
                        for (int i = 0; i < 256; i++) {
                            if (j == 0) break;
                            j = (j + d) & 255;
                            y = (y - n + 256) & 255;
                        }
                        if (j == 0) {
                            String s = "[" + repeat("+", d) + ">" + repeat("-", n) + "<]>";
                            if (s.length() < G[x][y].length()) {
                                G[x][y] = s;
                                iter = true;
                            }
                        }
                    }
                }
            }

            // combine number schemes
            for (int x = 0; x < 256; x++) {
                for (int y = 0; y < 256; y++) {
                    for (int z = 0; z < 256; z++) {
                        if (G[x][z].length() + G[z][y].length() < G[x][y].length()) {
                            G[x][y] = G[x][z] + G[z][y];
                            iter = true;
                        }
                    }
                }
            }
        }
    }
    static void generate(String s) {
        char lastc = 0;
        for (char c : s.toCharArray()) {
            String a = G[lastc][c];
            String b = G[0][c];
            if (a.length() <= b.length()) {
                System.out.print(a);
            } else {
                System.out.print(">" + b);
            }
            System.out.print(".");
            lastc = c;
        }
        System.out.println();
    }

    static void genFile(String file) throws IOException {
        File f = new File(file);
        int len = (int)f.length();
        byte[] b = new byte[len];
        InputStream i = new FileInputStream(f);
        StringBuilder s = new StringBuilder();
        while (true) {
            int v = i.read();
            if (v < 0) break;
            if (v == 0) continue; // no zeros
            s.append((char)v);
        }
        generate(s.toString());
    }
    public static void main(String[] args) throws IOException {
        genFile(args[0]);
    }
}

```
> 18 votes

# Answer
Well here's about the worst possible solution, although a rather nice looking one in Brainfuck itself:

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

```

Score is probably the worst we are likely to see without intentionally making it bad.

Working on calculating actual score.
> 14 votes

# Answer
**Score: ~~4787486~~ ~~4143940~~ 4086426** (without randomly generated data)

(4085639 of that are from Lenna.png. That's 99.98%)

I don't get the part with the random data. Don't I need an account which I have to pay for to get the data?

Pretty naive. Here's the generated code for "1Aa" (49, 65, 97) with a little documentation:

```
                   // field 0 and 1 are loop counters.
                   // The fields 2, 3 and 4 are for "1", "A" and "a"
++++++++++[        // do 10 times
    >
    ++++++++++[    // do 10 times
        >          // "1" (49) is below 50 so we don't need to do anything here
        >+         // When the loops are done, this part will have increased the value of field 3 by 100 (10 * 10 * 1)
        >+         // same as above
        <<<-       // decrease inner loop counter
    ]
    >+++++         // this will add 50 (10 * 5) to field 2, for a total of 50
    >----          // subtract 40 from field 3, total of 60
    >              // Nothing done, value stays at 100
    <<<<-          // decrease outer loop counter
]
>>-.               // subtract 1 from field 2, total now: 49, the value for "1"
>+++++.            // add 5 to field 3, makes a total of 65, the value for "A"
>---.              // subtract 3 from field 4, total of 97, the value for "a"

```

The Java code is a bit ugly but it works. The generated instruction per input byte ratio is probably better the higher the average byte value is.

If you want to run it, you have to put Lenna.png in the same directory as the .class file. It prints the score to console and writes the generated BF code into a file called "output.txt".

```
import java.io.File;
import java.io.FileInputStream;
import java.io.FileWriter;
import java.io.IOException;
import java.util.Arrays;

public class BrainFuckGenerator {
    public static CharSequence generate(byte[] bytes) {
        final StringBuilder brainfuckBuilder = new StringBuilder();
        for(int j = 0; j<10; j++)
                brainfuckBuilder.append("+");

        brainfuckBuilder.append("[>");

        for(int j = 0; j<10; j++)
            brainfuckBuilder.append("+");

        brainfuckBuilder.append("[");

        final StringBuilder singles = new StringBuilder();
        final StringBuilder tens = new StringBuilder();
        final StringBuilder goBack = new StringBuilder();

        for(byte b: bytes) {
            brainfuckBuilder.append(">");
            for(int j=0; j<(b/100); j++) {
                brainfuckBuilder.append("+");
            }

            tens.append(">");
            if((b - (b/100)*100)/10 <= 5) {
                for(int j=0; j<(b - (b/100)*100)/10; j++) {
                    tens.append("+");
                }
            } else {
                brainfuckBuilder.append("+");
                for(int j=0; j<10 - (b - (b/100)*100)/10; j++) {
                    tens.append("-");
                }
            }

            singles.append(">");
            if(b%10 <= 5) {
                for(int j=0; j<b%10; j++) {
                    singles.append("+");
                }
            } else {
                tens.append("+");
                for(int j=0; j<10 - (b%10); j++) {
                    singles.append("-");
                }
            }
            singles.append(".");

            goBack.append("<");
        }
        goBack.append("-");

        brainfuckBuilder
            .append(goBack)
            .append("]")
            .append(tens)
            .append("<")
            .append(goBack)
            .append("]>")
            .append(singles);

        return brainfuckBuilder;
    }

    public static void main(String[] args) {
        /* Hello, World! */
        int score = score("Hello, world!"+((char)0xA));

        /* 255 single chars */
        int charscore = 0;
        for(char c=1; c<=0xff; c++)
            charscore += score(String.valueOf(c));

        score += Math.round(((double)charscore)/16);

        /* Lenna */
        final File lenna = new File("Res/Lenna.png");
        final byte[] data = new byte[(int)lenna.length()];
        int size = 0;
        try(FileInputStream input = new FileInputStream(lenna)) {
            int i, skipped=0;
            while((i = input.read()) != -1)
                if(i == 0)
                    skipped++;
                else
                    data[size++ - skipped] = (byte)(i&0xff);
        } catch (IOException e) {
            e.printStackTrace();
        }

        score += score(Arrays.copyOf(data, size), "Lenna");

        /* 99 Bottles */
        final StringBuilder bottleBuilder = new StringBuilder();
        for(int i=99; i>2; i--) {
            bottleBuilder
                .append(i)
                .append(" bottles of beer on the wall, ")
                .append(i)
                .append(" bottles of beer.")
                .append((char) 0xa)
                .append("Take one down and pass it around, ")
                .append(i-1)
                .append(" bottles of beer on the wall.")
                .append((char) 0xa)
                .append((char) 0xa);

        }

        bottleBuilder
            .append("2 bottles of beer on the wall, 2 bottles of beer.")
            .append((char) 0xa)
            .append("Take one down and pass it around, 1 bottle of beer on the wall.")
            .append((char) 0xa)
            .append((char) 0xa)
            .append("No more bottles of beer on the wall, no more bottles of beer. ")
            .append((char) 0xa)
            .append("Go to the store and buy some more, 99 bottles of beer on the wall.");

        score(bottleBuilder.toString(), "99 Bottles");
        System.out.println("Total score: "+score);
    }

    private static int score(String s) {
        return score(s, null);
    }

    private static int score(String s, String description) {
        final CharSequence bf = generate(s.getBytes());
        try(FileWriter writer = new FileWriter("Res/output.txt", true)) {
            writer.write((description == null ? s : description));
            writer.write(NL);
            writer.write("Code:");
            writer.write(NL);
            writer.write(bf.toString());
            writer.write(NL+NL);
        } catch (IOException e) {
            e.printStackTrace();
        }
        return bf.length();
    }

    private static int score(byte[] bytes, String description) {
        final CharSequence bf = generate(bytes);
        try(FileWriter writer = new FileWriter("Res/output.txt", true)) {
            if(description != null) {
                writer.write(description);
                writer.write(NL);
            }
            writer.write("Code:");
            writer.write(NL);
            writer.write(bf.toString());
            writer.write(NL+NL);
        } catch (IOException e) {
            e.printStackTrace();
        }
        return bf.length();
    }

    private static final String NL = System.getProperty("line.separator");
}

```

~~I'm going to make some small improvements but probably not much.~~ Done.
> 8 votes

# Answer
I'm not sure how good it is, but I had fun writing this. (In Clojure...)

```
(ns bf.core)
(def input "Hello world!")
(defn abs [x] (if (and (< x 0) (= (type x) (type 1))) (* x -1) x))
(defn sqrt? [x y] (if (= (* y y) x) true false) )
(defn sqrt [x] (for [y (range x) :when (sqrt? x y)] y) )
(defn broot [x]
;  Run this using trampoline, e.g., (trampoline broot 143)
  (if (< x 2) nil)
  (let [y (sqrt x)]
    (if (not= (seq y) nil)
      (first y)
      (broot (dec x) )
      )
    )
  )
(defn factor [x]
  (if (<= x 2) x)
  (for [y (range (- x 1) 1 -1)
        :when (= ( type (/ x y) ) (type 1) )
        ]
    y)
  )

(defn smallest_factors [x]
  (let [ facts (factor x) ]
  (if (= (count facts) 2) facts)
  (if (< (count facts) 2) (flatten [facts facts])
    (let [ y (/ (dec (count facts) ) 2)
          yy (nth facts y)
          z (inc y)
          zz (nth facts z)
          ]
      (if (= (* yy zz) x ) [yy zz] [yy yy])
      )
    )
    )
  )

(defn smallestloop [x]
  (let [ facts (smallest_factors x)
        fact (apply + facts)
        sq (trampoline broot x)
        C (- x (* sq sq) )]
    (if (and (< fact (+ (* 2 sq) C) ) (not= fact 0))
      facts
      [sq sq C])
    )
  )
(def lastx nil)
;Finally!
(defn buildloop [x]
  (if (nil? lastx)
     (let [pluses (smallestloop x)]
       (apply str
              (apply str (repeat (first pluses) \+))
              "[>"
              (apply str (repeat (second pluses) \+))
              "<-]>"
              (if (and (= (count pluses) 3) (> (last pluses) 0))
                (apply str(repeat (last pluses) \+))
              )
              "."
              )
    )
    (let [diff (abs (- x lastx) )]
      (if (< diff 10)
        (if (> x lastx)
          (apply str
               (apply str (repeat diff \+))
               "."
                 )
          (apply str
                 (apply str (repeat diff \-))
                 "."
                 )
          )
        (let [signs (smallestloop diff)]
          (apply str
             "<"
             (apply str (repeat (first signs) \+))
             "[>"
             (if (> x lastx)
               (apply str (repeat (second signs) \+))
               (apply str (repeat (second signs) \-))
             )
             "<-]>"
             (if (and (= (count signs) 3) (> (last signs) 0))
               (if (> x lastx)
                 (apply str(repeat (last signs) \+))
                 (apply str(repeat (last signs) \-))
               )
             )
             "."
           )
         )
        )
      )
    )
  )
(for [x (seq input)
  :let [y (buildloop (int x))]
      ]
  (do
   (def lastx (int x))
   y
   )
  )

```

There are probably more efficient solutions, and more elegant ones, but this follows my thought pattern somewhat linearly, so it was easiest.
> 8 votes

# Answer
# Python 3.x

Well, I'm not going to win any prizes for the shortest output code but maybe for the program to generate the code...

```
x=input();o=''
for i in x:
 a=ord(i)
 o+="+"*a+".[-]"
print(o)

```

'Hello, World!\n':

```
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.[-]++++
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
+++++++++++++++++.[-]+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
+++++++++++++++++++++++++++++++++++++++++++++++++.[-]+++++++++++++++++++++++++++
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
+.[-]+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
++++++++++++++++++++++++++++++++++++.[-]++++++++++++++++++++++++++++++++++++++++
++++.[-]++++++++++++++++++++++++++++++++.[-]++++++++++++++++++++++++++++++++++++
+++++++++++++++++++++++++++++++++++++++++++++++++++.[-]+++++++++++++++++++++++++
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
++++++.[-]++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
++++++++++++++++++++++++++++++++++++++++++++.[-]++++++++++++++++++++++++++++++++
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.[-]
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
++++++++++++++++++++.[-]+++++++++++++++++++++++++++++++++.[-]++++++++++.[-]

```
> 8 votes

# Answer
# BrainF\**k

I'm a pretty bad BF programmer, so this answer is probably pretty inefficient. I'm unsure of the score, but it should perform slightly better than the existing answer on your average text. Rather than zeroing the cell out after every character, this one will "adjust" to a new character with subtraction if the previous character given is larger.

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

```

(Note, this is code I wrote a long time ago, and have repurposed for this competition. I sincerely hope I've done the conversion correctly, but if it fails for any input let me know.)

A version showing the state of the tape throughout the code:

```
>>++++++[-<+++++++>]<+>             [0 '+' 0]
                                           ^
>+++++[-<+++++++++>]                [0 '+' '-' 0]
                                               ^
>+++++[-<+++++++++>]<+>             [0 '+' '-' '.' 0]
                                                   ^
>,[-<+>>>>>>+<<<<<]                 [0 '+' '-' '.' a 0 0 0 0 0 a]
                                                     ^
<[-<<<.>>>]<.>>+>                   [0 '+' '-' '.' 0 1 0 0 0 0 a]
                                                       ^
,[[-<<+>>>+>>+<<<]                  [0 '+' '-' '.' b 1 0 b 0 b a]
                                    [b is not 0]       ^
>>>>[-<<+>>]<[->+<]                 [0 '+' '-' '.' b 1 0 b a 0 b]
                                                             ^
<<[->-[>]<<]

<[->->[-<<<<<<.>>>>>>]<<]

>+[-<<->>>[-<<<<<<.>>>>>>]<]        [0 '+' '-' '.' b 0 0 0 0 0 b]
                                                       ^|^
                                    [OUTPUT ONE CHARACTER BY THIS POINT]
<<<[>]<<.>[-]>                      [0 '+' '-' '.' 0 0 0 0 0 0 b]
                                                     ^
+>,]                                [End when b == 0]
                                    [GOAL: '+' '-' '.' b 1 0 b a 0 a]

```

Generated code for `Hello, World!`:

```
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.+++++++++++++++++++++++++++++.+++++++..+++.-------------------------------------------------------------------.------------.+++++++++++++++++++++++++++++++++++++++++++++++++++++++.++++++++++++++++++++++++.+++.------.--------.-------------------------------------------------------------------.

```

*This is my first answer on CG.SE! If I've screwed something up, let me know!*
> 6 votes

# Answer
## \>\<\>

```
i:&v
.21<>i:0(?;:&:@(4g62p$:&-01-$:@0(?*l2=?~02.
>:?!v"+"o1-
"."~<.15o
+-

```

I wrote this in response to a question marked for a duplicate, and even though this isn't the greatest golf (for this specific question, at least) I figured it'd be kind of a waste if I didn't share it in all of its disgustingly gibberish-y glory. Really, I'm half-surprised it even works. I'll take any suggestions to golf it down since that was my main goal in its creation.

As a side note, in the second line the beginning three characters `.21` could be replaced with `v` followed by two spaces if that makes it any easier to read. I don't like to see spaces in my \>\<\> programs because that means there's wasted space (literally). It also is a remnant from one of many prototypes.

The way it functions is really simple, and quite frankly I'd have a difficult time thinking of a way to implement another algorithm. It prints however many "+"s need to be printed for the first character, and then prints more "+"s or "-"s as needed for each additional character, separating each section with periods. What I find cool about the program is that it modifies its own source code so that it prints "+" or "-" (it replaces the "+" on line 3 with the appropriate character after determining whether the current character is greater than or less than the previous one).

Output for `Hello, World!`:

```
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.+++++++++++++++++++++++++++++.+++++++..+++.-------------------------------------------------------------------.------------.+++++++++++++++++++++++++++++++++++++++++++++++++++++++.++++++++++++++++++++++++.+++.------.--------.-------------------------------------------------------------------.

```

I might score this the way it was intended to be scored, but I'm almost positive I'd lose and I don't entirely know how to read something like lenna.png in \>\<\>.

If this answer interests you and you'd like an explanation, by all means ask, but for now I'll leave it without one just because of how twisty and turny it is.

EDIT 1: It's been a while but I was able to golf off 2 bytes with an almost complete overhaul of the way the program decides whether to print a plus or a minus. It's a somewhat disappointing return for a large overhaul but at least it works.
> 4 votes

# Answer
# Kotlin

First I must admit that about half of this is shamelessly stolen from Keith Randel's answer. I literally copied and pasted his code for finding multiplications into mine. It is very well done. I have made 2 modifications to his code.

1. It is very easy to reverse the direction of any of the transitions Keith's code produces. All you have to do is replace `<` with `>` and `>` with `<`. Ex. `+[->++<]>` becomes `+[-<++>]<`. This means that equally, good code\* that only uses 2 cells can be produced.
2. The second thing I did was to add a hash. To add a hash the code simply includes a `>` after the `.`. Then for all subsequent characters, the program calculates if the code to move to the hash (such as `<<<.>>>`) is shorter than the regular code to produce this output. To find the locations for the hash the program loops through each character of the input and checks if hashing that character decreases the length of the program. It only hashes each type of character once which is slightly inefficient but is necessary to make the program not run like a snail.

Speaking of time complexity my program is quadratic time as opposed to Keith's which is linear. This is because the full code for any hash configuration has to be generated for each character. It is still possible to stop the algorithm early and get a better result than you started with as each cache only improves the score.

So how good does it do. Theoretically, it always does better than Keith's however, this isn't quite true. Keith's code can get to zero from any number simply by inserting a `>` but mine cannot because it would move too far from the hash. As a result, some of my transitions are slightly longer than Keith's meaning I actually achieve a lower score on `Lenna.png`. However since most of the transitions where starting with zero instead are very small or very large if you only include letters in the printable ASCII range 32 to 126 my program does beat Keith's. So although it can be worse my algorithm is better in practice. Lets look at some numbers.

### Numbers

```
Lenna.png (no 0s), 471470 characters

Keith:  5832730 bf chars,  12.37 bf chars / input
Me:    <5894582 bf chars, <12.5  bf chars / input

Keith + 0.13

```

```
Lenna.png (32 to 126), 174177 characters

Keith:  2022451 bf chars,  11.61 bf chars / input
Me:    <1977716 bf chars,  11.25 bf chars / input

Me + 0.36

```

```
Hello, World!\n, 14 characters

Keith:      139 bf chars, 9.93 bf chars / input
Me:         139 bf chars, 9.93 bf chars / input

Even

```

```
I went to the store today, 25 characters

Keith:      265 bf chars, 10.6 bf chars / input
Me:         190 bf chars,  7.6 bf chars / input

Me + 3

```

```
447 characters of Lorem Ipsum

Keith:     4427 bf chars,  9.9 bf chars / input
Me:        3017 bf chars, 6.75 bf chars / input

Me + 3.15

```

```
1001 random lowercase letters

Keith:     8035 bf chars, 8.03 bf chars / input
Me:        7028 bf chars, 7.02 bf chars / input

Me + 1.01

```

### Code

```
const val CELL_SIZE = 256
const val WRAPPING = true

enum class Direction {
    LEFT, RIGHT;

    fun opposite() = when (this) {
        LEFT -> RIGHT
        RIGHT -> LEFT
    }
}

data class Transition(
    val code: String,
    val startD: Direction,
    val endD: Direction,
) {
    fun plus(t: Transition) = if (endD == t.startD) {
        Transition(code + t.code, t.startD, t.endD)
    } else {
        val r = t.reverse()
        Transition(code + r.code, t.startD, r.endD)
    }

    fun reverse(): Transition {
        val newCode = code.replace(">", "|").replace("<", ">").replace("|", "<")
        return Transition(newCode, startD.opposite(), endD.opposite())
    }
}

var simpleTransitions = {
    val list = Array(CELL_SIZE) { start ->
        Array(CELL_SIZE) { end ->
            var delta = end - start
            if (WRAPPING) when {
                delta > CELL_SIZE / 2 -> delta -= CELL_SIZE
                delta < -CELL_SIZE / 2 -> delta += CELL_SIZE
            }
            val char = if (delta > 0) "+" else "-"
            Transition(char.repeat(abs(delta)), Direction.LEFT, Direction.LEFT)
        }
    }

    //check for multiplication
    for (x in 0..255) {
        for (n in 1..39) {
            for (d in 1..39) {
                var j = x
                var y = 0
                for (i in 0..255) {
                    if (j == 0) break
                    j = j - d + 256 and 255
                    y = y + n and 255
                }
                if (j == 0) {
                    val s = "[" + "-".repeat(d) + ">" + "+".repeat(n) + "<]>"
                    if (s.length < list[x][y].code.length) {
                        list[x][y] = Transition(s, Direction.LEFT, Direction.RIGHT)
                    }
                }
                j = x
                y = 0
                for (i in 0..255) {
                    if (j == 0) break
                    j = j + d and 255
                    y = y - n + 256 and 255
                }
                if (j == 0) {
                    val s = "[" + "+".repeat(d) + ">" + "-".repeat(n) + "<]>"
                    if (s.length < list[x][y].code.length) {
                        list[x][y] = Transition(s, Direction.LEFT, Direction.RIGHT)
                    }
                }
            }
        }
    }

    for (i in 0 until CELL_SIZE) {
        if (list[i][0].code.length > 3) list[i][0] = Transition("[-]", Direction.LEFT, Direction.LEFT)
    }

    var change = true
    while (change) {
        change = false
        for (i in 0 until CELL_SIZE) {
            for (j in 0 until CELL_SIZE) {
                for (k in 0 until CELL_SIZE) {
                    if (list[i][j].code.length + list[j][k].code.length < list[i][k].code.length) {
                        list[i][k] = list[i][j].plus(list[j][k])
                        change = true
                    }
                }
            }
        }
    }

    println("done")
    list
}()

fun generate(s: String, cells: Int): String {
    var caches: MutableList<Boolean> = MutableList(s.length) { false }
    var currentCost = generateFromCache(s, caches)
    val changes: MutableMap<Char, Int> = mutableMapOf()

    if (cells > 2) {
        for ((i, c) in s.withIndex()) {
            val newCaches = caches.mapIndexed { index, b -> if (s[index] == c) false else b }.toMutableList()
            var lowest: Char? = null
            if (newCaches.count { it } >= cells - 2) {
                lowest = changes.minByOrNull { it.value }!!.key
                newCaches[newCaches.withIndex().indexOfFirst { it.value && s[it.index] == lowest }] = false
            }
            newCaches[i] = true
            val newCost = generateFromCache(s, newCaches)
            if (newCost.length < currentCost.length) {
                println(newCost.length)
                changes[c] = currentCost.length - newCost.length
                currentCost = newCost
                caches = newCaches
                if (lowest != null) changes.remove(lowest)
            }
        }
    }

    return currentCost
}

```
> 2 votes

# Answer
my JavaScript solution it\`s quick and dirty :)

output for `Hello World\n`

```
++++++++++[>+++++++>++++++++++>+++++++++++>+++>+++++++++>+<<<<<<-]>++.>+.>--..+++.>++.>---.<<.+++.------.<-.>>+.>>.

```

Source:

```
BfGen("Hello World!\n");
// ++++++++++[>+++++++>++++++++++>+++++++++++>+++>+++++++++>+<<<<<<-]>++.>+.>--..+++.>++.>---.<<.+++.------.<-.>>+.>>.
// Length of BF code: 115
// Score: 8.846153846153847

function BfGen(input) {
    function StringBuilder() {
        var sb = {};

        sb.value = '';
        sb.append = (txt) => sb.value += txt;

        return sb;
    }

    function closest (num, arr) {
        var arr2 = arr.map((n) => Math.abs(num-n))
        var min = Math.min.apply(null, arr2);
        return arr[arr2.indexOf(min)];
    }

    function buildBaseTable(arr) {
        var out = StringBuilder();
        out.append('+'.repeat(10));
        out.append('[')
        arr.forEach(function(cc) {
            out.append('>');
            out.append('+'.repeat(cc/10));
        });
        out.append('<'.repeat(arr.length));
        out.append('-');

        out.append(']');
        return out.value;
    }

    var output = StringBuilder();

    var charArray = input.split('').map((c) =>c.charCodeAt(0));
    var baseTable = charArray.map((c) => Math.round(c/10) * 10).filter((i, p, s) => s.indexOf(i) === p);

    output.append(buildBaseTable(baseTable));

    var pos = -1;
    charArray.forEach(function (charCode) {
        var bestNum = closest(charCode, baseTable);
        var bestPos = baseTable.indexOf(bestNum);

        var moveChar = pos < bestPos? '>' : '<';
        output.append(moveChar.repeat(Math.abs(pos - bestPos)))
        pos = bestPos;

        var opChar = baseTable[pos] < charCode? '+': '-';
        output.append(opChar.repeat(Math.abs(baseTable[pos] - charCode)));
        output.append('.');
        baseTable[pos] = charCode;
    });

    console.log(output.value)
    console.log('Length of BF code: ' + output.value.length);
    console.log('Score: ' + output.value.length / input.length);
}

```
> 1 votes

# Answer
# Python 3

```
print("".join("+"*ord(i)+".[-]"for i in input()))

```

This is essentially just an slightly improved version of icedvariables' answer. (-1 Byte from Wheat Wizard, -5 from FatalError, -2 from jez)
> 1 votes

# Answer
I built something in Java. Didn't calculate the score. Texts with 3 or less characters are encoded with a multiplication per letter e.g. "A" = `++++++++[>++++++++<-]>+.`. Texts with more than 3 characters are encoded with a calculated list which is split into 3 areas. The first area is x times 49, then plus x times 7 and finally plus x. For example "A" is 1\*49 + 2\*7 + 2

```
public class BFbuilder {
    public static void main(String[] args) {
        String text = "### INSERT TEXT HERE ###";

        if (text.length()<=3){
            String result = "";
            for (char c:text.toCharArray()) {
                result += ">";
                if (c<12) {
                    for (int i=0;i<c;i++) {
                        result += "+";
                    }
                    result += ".>";
                } else {
                    int root = (int) Math.sqrt(c);
                    for (int i = 0; i<root;i++) {
                        result += "+";
                    }
                    result += "[>";
                    int quotient = c/root;
                    for (int i = 0; i<quotient;i++) {
                        result += "+";
                    }
                    result += "<-]>";
                    int remainder = c - (root*quotient);
                    for (int i = 0; i<remainder;i++) {
                        result += "+";
                    }
                    result += ".";
                }
            }
            System.out.println(result.substring(1));
        } else {
            int[][] offsets = new int[3][text.length()];
            int counter = 0;
            String result = "---";

            for(char c:text.toCharArray()) {
                offsets[0][counter] = c/49;
                int temp = c%49;
                offsets[1][counter] = temp/7;
                offsets[2][counter] = temp%7;
                counter++;
            }

            for (int o:offsets[0]) {
                switch (o) {
                case 0: result+=">--";
                break;
                case 1: result+=">-";
                break;
                case 2: result+=">";
                break;
                case 3: result+=">+";
                break;
                case 4: result+=">++";
                break;
                case 5: result+=">+++";
                break;
                }
            }
            result += ">+[-[>+++++++<-]<+++]>----";
            for (int o:offsets[1]) {
                switch (o) {
                case 0: result+=">---";
                break;
                case 1: result+=">--";
                break;
                case 2: result+=">-";
                break;
                case 3: result+=">";
                break;
                case 4: result+=">+";
                break;
                case 5: result+=">++";
                break;
                case 6: result+=">+++";
                break;
                }
            }
            result += ">+[-[>+++++++<-]<++++]>----";
            for (int o:offsets[2]) {
                switch (o) {
                case 0: result+=">---";
                break;
                case 1: result+=">--";
                break;
                case 2: result+=">-";
                break;
                case 3: result+=">";
                break;
                case 4: result+=">+";
                break;
                case 5: result+=">++";
                break;
                case 6: result+=">+++";
                break;
                }
            }
            result += ">+[-<++++]>[.>]";
            System.out.println(result);
        }
    }
}

```

The provided String "### INSERT TEXT HERE ###" becomes `--->-->-->-->-->->->->->->->-->->->->->-->->->->->-->-->-->-->+[-[>+++++++<-]<+++]>---->++>++>++>+>>+>+>->+>++>+>++>->++>++>+>>->+>->+>++>++>++>+[-[>+++++++<-]<++++]>---->--->--->--->+>>-->+++>+++>++>--->+>--->+++>+>--->+>->+++>++>+++>+>--->--->--->+[-<++++]>[.>]`

"Hello, World!" becomes `--->->>>>>-->-->->>>>>-->+[-[>+++++++<-]<+++]>---->>--->-->-->-->+++>+>++>-->->-->--->+>+[-[>+++++++<-]<++++]>---->->>>>+++>->+>>+++>->>->++>+[-<++++]>[.>]`
> 1 votes

---
Tags: code-challenge, kolmogorov-complexity, brainfuck, metagolf
---


title: Leon's shooting range problem

text:
# Question
Title: Leon's shooting range problem
# Leon's story

Leon is a professional sling shooter and he comes to a shooting range everyday to practice. A casual target is not a challenge for him anymore so before shooting he first covers the target of radius `1.0` with `k` rectangle stickers. He then fires `n` shots that cannot hit the stickers.

What's special about Leon is that he always shoots randomly but with a uniform distribution.

Leon everyday takes on a bigger challenge and puts more stickers. However he started noticing that **shooting takes too much time** now so he decided to ask you for the best strategy.

---

# Task

Implement a program which will randomly pick `n` points with the **lowest time complexity** possible. Each point should be inside a circle target, and none of them lands in any of `k` rectangle stickers.

**Input:**

List of `k` rectangles in whatever form fits you.

Eg. where each rectangle is a list of:

```
[x_min, x_max, y_min, y_max]

```

The list could be:

```
[[0.1, 0.3, -0.2, 0.1], [-0.73, -0.12, 0.8, 1.4]]

```

**Output:**

List of coordinates of `n` points in whatever form fits you.

**Rules:**

* Points have to be picked randomly with uniform distribution
* Every point lays inside a circle
* None of the points lays inside a rectangle sticker
* Stickers can overlap each other
* Circle's radius is equal to `1.0` and its center is at coordinates `(0.0, 0.0)`
* Every coordinate is in form of floating point number
* For edge cases - choose whatever fits you

---

**EDIT:** Thanks to @Luis Mendo and @xnor it turned out that one more rule might be useful. * With each new sticker `1/4` of the remaining board will be covered. This means that having `k` stickers the uncovered part of the target will be `(3/4)^k` of the whole.

---

## Rating

**The best time complexity wins!**

**EDIT:**

For the sake of rating we will assume that `k` and `n` are linearly proportional, meaning that `O(k^2 + n)` will be rated equally to `O(k + n^2)`

# Answer
> 5 votes
# Area-based algorithm, \\$O(k^2+n\log(k))\\$

Our general strategy is to instead select points (outside the sticker rectangles) from the square (-1,-1) to (1,1), then repeat if we don't get a point within the circle. On average, we will have to select \\$\frac{4}{\pi}\\$ points from the square for each point in the circle.

The runtime is not depend on rectangle coverage, but it does depend on measures of rectangle intersection (denoted `L` in the complexity analysis in the code). For the listed complexity, I use \\$L=O(k)\\$, which is probably not tight. If \\$L=O(\log(k))\\$ can be proven, then the complexity is \\$O((k+n)\log(k))\\$ (see `get_heights` for an algorithmic alternative).

Define "open area" to be the area that points could be generated in. Recall that we are using a square instead of a circle, so the total area is piece-wise linear in x.

1. Precompute the total open height function \\$h(x)\\$ (this is piece-wise constant, so store the change at each transition: either the start or end of a new rectangle). Similarly, pre-compute the cumulative areas \\$\int\_{-1}^{x} h(x)\\$, which is piece-wise linear, so once again store the value at each transition. This can be done in \\$O(k \log(k))\\$ time
2. Precompute the intervals on which y coordinates can be distributed for a given x (again, only storing this interval on each transition). This might be able to be done in \\$O(k \log(k))\\$, but this algorithm only succeeds at \\$O(k^2)\\$ time
3. Generate points. For each point: (average \\$\frac{4}{\pi} n\\$ times for a total runtime of \\$O(n\log(k))\\$

a. Choose a random value \\$r\\$ for the area (\\$O(1)\\$)

b. Find \\$x\\$ such that \\$\int\_{-1}^{x} h(t) dt = r\\$. This is accomplished through binary search on the pre-computed heights \\$h\\$ and cumulative areas \\$\int h\\$, so this is done in \\$O(\log(k))\\$ time

c. Choose a random value \\$y\\$ for the given x such that (x,y) is in an open area. Through similar binary search as 3b, this is done in \\$O(\log(k))\\$ time

d. Reject the point if it is outside the circle (constant factor 4/pi)

The total runtime is \\$O(k\log(k)) + O(k^2) + O(n\log(k)) = O(k^2+n\log(k))\\$

In the following example images, I used the same n=10000, so more rectangle coverage meant a higher density of points.

Full python code below, including matplotlib display:

```
import math
import random
# for binary search
import bisect
# matplotlib for plotting the output points
import matplotlib.pyplot as plt
import matplotlib

def find_le(ls, x):
    # find_le is O(log(|ls|))
    # Find rightmost value less than or equal to x in ls
    i = bisect.bisect_right(ls, x)
    return i-1, ls[i-1]

class Interval:
    def __init__(self, lo, hi):
        # each range is tuple (lo, hi)
        # ranges shall be sorted in ascending order
        # each range does not overlap with other ranges
        self.ranges = [(lo, hi)]

    def remove(self, lo, hi):
        new_ranges = []
        for self_range in self.ranges:
            if lo <= self_range[0] <= hi < self_range[1]:
                new_ranges.append((hi, self_range[1]))
            elif self_range[0] < lo <= self_range[1] <= hi:
                new_ranges.append((self_range[0], lo))
            elif self_range[0] < lo < hi < self_range[1]:
                new_ranges.append((self_range[0], lo))
                new_ranges.append((hi, self_range[1]))
            elif lo <= self_range[0] < self_range[1] <= hi:
                pass
            elif hi <= self_range[0] or self_range[1] <= lo:
                # no overlap
                new_ranges.append(self_range)
        self.ranges = new_ranges

    def cache_lengths(self):
        # If L is the number of subintervals of this Interval
        # then cache_lengths is O(L) ⊂ O(k)

        # in cum_lengths, (0.6, 0.7) means that the total length to the
        # left of x=0.7 in this interval is 0.6
        self.cum_lengths = [(0, -1)]
        last_length = 0
        for self_range in self.ranges:
            length = self_range[1] - self_range[0]
            self.cum_lengths.append((last_length, self_range[0]))
            last_length += length
        self.total_length = last_length

    def random_point(self):
        # If L is the number of subintervals of this Interval
        # then random_point is O(log(L)) ⊂ O(log(k))
        r = random.random()*self.total_length
        # This find_le is O(log(L))
        i, (length_left, x_left) = find_le(self.cum_lengths, (r,))
        return (r - length_left) + x_left

    def __repr__(self):
        return "I" + str(self.ranges)

def interval_complement(rects):
    # O(L) where L is the length of rects list
    interval = Interval(-1, 1)
    for rect in rects:
        interval.remove(rect.bottom, rect.top)
    return interval

class Rect:
    def __init__(self, left, right, bottom, top):
        self.left = min(left, right)
        self.right = max(left, right)
        self.bottom = min(bottom, top)
        self.top = max(bottom, top)
        self.width = self.right - self.left
        self.height = self.top - self.bottom

    def __repr__(self):
        return f"Rect({self.left}, {self.right}, {self.bottom}, {self.top})"

    def overlap(self, others):
        # returns vertical (y) overlap between self and other rects
        total_overlap = 0
        # https://pyinterval.readthedocs.io/en/latest/guide.html#operations is
        # looking so tempting right now, but unions/merges would
        # require Principle Inclusion-Exclusion which can be k^2 worst case
        starts = sorted(others, key=lambda rect: rect.bottom, reverse=True)
        ends = sorted(others, key=lambda rect: rect.top, reverse=True)
        active_rects = set()
        overlap_start = self.bottom
        while ends:
            if starts and starts[-1].bottom < ends[-1].top:
                active_rect = starts.pop()
                if not active_rects and active_rect.bottom > self.bottom:
                    # This is the start of an overlap interval
                    overlap_start = active_rect.bottom
                active_rects.add(active_rect)
            else:
                active_rect = ends.pop()
                active_rects.remove(active_rect)

                if not active_rects:
                    # This is the end of an overlap interval
                    # Rare cases of negative = started and ended below start of self
                    total_overlap += max(0, min(active_rect.top, self.top) - overlap_start)
        return total_overlap

    def as_matplotlib_rect(self):
        return matplotlib.patches.Rectangle((self.left, self.bottom), self.width, self.height)

def get_heights(rects):
    # get_heights is O(k log(k)) total
    # Sorting: O(k log(k))
    # Use these lists as a queue
    starts = sorted(rects, key=lambda rect: rect.left, reverse=True)
    ends = sorted(rects, key=lambda rect: rect.right, reverse=True)
    # list of tuples (open height starting at x, x, open intervals starting at x)
    heights = [(2, -1, Interval(-1,1))]
    active_rects = set()
    while ends:
        # inner loop performed once for k left edges and k right edges,
        # so this is O(k)
        if starts and starts[-1].left < ends[-1].right:
            # next x-pos is the start of a new rect
            rect = starts.pop()
            height_diff = rect.height - rect.overlap(active_rects)
            height = heights[-1][0] - height_diff
            active_rects.add(rect)
            # interval_complement is O(L) so this is O(k^2), not sure if it is O(k log(k))
            heights.append((height, rect.left, interval_complement(active_rects)))
        else:
            # next x-pos is the end of an old rect
            rect = ends.pop()
            active_rects.remove(rect)
            # rect.overlap is O(L) as well
            height_diff = rect.height - rect.overlap(active_rects)
            # Two choices to get O(k log(k)):
               # 1. prove that |active_rects| is O(log(k)) under the given approaches
               # 2. avoid using interval_complement on each transition using some increments approach, and avoid doing rect.overlap on each transition
            height = heights[-1][0] + height_diff
            heights.append((height, rect.right, interval_complement(active_rects)))
    heights.append((2, 1, Interval(-1,1)))
    # cum_areas is the cumulative areas from -1 to x (of not rects)
    # Not subtracting curve because we will be sampling from square
    cum_areas = [(0, -1, Interval(-1, 1))]
    last_height = 2
    for height, x, interval in heights[1:]:
        last_area, last_x, _ = cum_areas[-1]
        new_area = (x-last_x)*last_height
        cum_areas.append((last_area + new_area, x, interval))
        last_height = height
    return (heights, cum_areas)

def random_pick_points(rects, num_points):
    # random_pick_points is O((n+k) log(k))
    # Step 1. Precompute heights: O(k log (k))
    heights, cum_areas = get_heights(rects)
    total_area = cum_areas[-1][0]
    points = []
    # Step 2. Precompute vertical intervals: O(k)
    for _, _, y_interval in cum_areas:
        y_interval.cache_lengths()
    # Step 3. Sample points outside rects and within circle
    # Total time complexity of this loop is O(n log(k))
    while len(points) < num_points:
        # This loop is reached average (4/pi)*n = O(n) times
        # Each occurence has complexity O(log(k))
        # Step 3a. Choose a random area value
        area = random.random()*total_area
        # Step 3b. Choose the x value such that area is the total area
        # outside rects and within 2x2 square to the left of x
        # There are 2k+1 total cum_areas so this find_le is O(log(k))
        i, (area_left, x_left, y_interval) = find_le(cum_areas, (area,))
        height, _, _ = heights[i]
        x = x_left + (area - area_left) / height
        # Step 3c. Choose a y value uniformly in the open spaces of that x value
        # Interval.random_point() is O(log(k))
        y = y_interval.random_point()
        # Step 3d. Rejection sample until points are inside the circle
        # On average, takes constant 4/pi random points to land within the circle
        if x*x + y*y < 1:
            points.append((x, y))
    # Done!
    return points

def display_points(rects, points):
    fig, ax = plt.subplots(1)
    ax.plot(*zip(*points), 'ko', markersize=1, alpha=0.5)
    ax.axis([-1, 1, -1, 1])
    ax.add_collection(
        matplotlib.collections.PatchCollection(
            [rect.as_matplotlib_rect() for rect in rects],
            facecolor = 'r', edgecolor='None', alpha=0.5
        )
    )
    plt.show()

def display_random_points(rects, num_points):
    points = random_pick_points(rects, num_points)
    display_points(rects, points)

def random_rects(k):
    return [Rect(*[random.random()*2-1 for _ in range(4)]) for i in range(k)]

k = 20
# rects = random_rects(k)
# print("Rects:", rects)
n = 10000
# print("Points:", random_pick_points(rects, n))
display_random_points(random_rects(k), n)

```

Try it online I guess, if you can read a list of points.

---
Tags: math, code-challenge, geometry, fastest-algorithm
---