title: Output numbers up to 2^n-1, "sorted"

text:
# Question
Title: Output numbers up to 2^n-1, "sorted"
Take a positive integer **n** as input, and output (some of the) decimal numbers that can be created using **n** bits, ordered in the following way:

First list all the numbers that can be created with only one `1`, and the rest `0` in the binary representation (sorted), then all the numbers that can be created with two **consecutive** `1`, the rest `0`, then three **consecutive** `1` and so on.

Let's see what this looks like for **n=4**:

```
0001  -  1
0010  -  2
0100  -  4
1000  -  8
0011  -  3
0110  -  6
1100  -  12
0111  -  7
1110  -  14
1111  -  15

```

So, the output for **n=4** is: **1, 2, 4, 8, 3, 6, 12, 7, 14, 15** (optional output format).

# Test cases:

```
n = 1
1

n = 2
1 2 3

n = 3
1, 2, 4, 3, 6, 7

n = 8
1, 2, 4, 8, 16, 32, 64, 128, 3, 6, 12, 24, 48, 96, 192, 7, 14, 28, 56, 112, 224, 15, 30, 60, 120, 240, 31, 62, 124, 248, 63, 126, 252, 127, 254, 255

n = 17
1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 3, 6, 12, 24, 48, 96, 192, 384, 768, 1536, 3072, 6144, 12288, 24576, 49152, 98304, 7, 14, 28, 56, 112, 224, 448, 896, 1792, 3584, 7168, 14336, 28672, 57344, 114688, 15, 30, 60, 120, 240, 480, 960, 1920, 3840, 7680, 15360, 30720, 61440, 122880, 31, 62, 124, 248, 496, 992, 1984, 3968, 7936, 15872, 31744, 63488, 126976, 63, 126, 252, 504, 1008, 2016, 4032, 8064, 16128, 32256, 64512, 129024, 127, 254, 508, 1016, 2032, 4064, 8128, 16256, 32512, 65024, 130048, 255, 510, 1020, 2040, 4080, 8160, 16320, 32640, 65280, 130560, 511, 1022, 2044, 4088, 8176, 16352, 32704, 65408, 130816, 1023, 2046, 4092, 8184, 16368, 32736, 65472, 130944, 2047, 4094, 8188, 16376, 32752, 65504, 131008, 4095, 8190, 16380, 32760, 65520, 131040, 8191, 16382, 32764, 65528, 131056,16383, 32766, 65532, 131064, 32767, 65534, 131068, 65535, 131070, 131071

```

This is , so the shortest code in **each language** wins!

**Good explanations are highly encouraged**, also for solutions in "regular languages"!

# Answer
> 38 votes
# Python, 53 bytes

```
f=lambda n,i=1:n*[f]and[i]+f(n-1,2*i)+i%2*f(n-1,i-~i)

```

Try it online!

The recursive function generates the sorted list as a pre-order walk down this tree (example with `n=4`):

```
      1
     / \
    2   3
   /   / \
  4   6   7
 /   /   / \
8   12  14  15

1 2 4 8 3 6 12 7 14 15

```

Left branches double the value, and right branches do `i->i*2+1` and exist only for odd `i`. So, the pre-order walk for non-leaves is `T(i)=[i]+T(i*2)+i%2*T(i*2+1)`.

The tree terminates at depth `n`, where `n` is the input. This is achieved by decrementing `n` with each step down and stopping when it is 0.

An alternative strategy would be to terminate on values that `i` exceeds `2**n`, rather than tracking depth. I found this to be one byte longer:

```
f=lambda n,i=1:2**n/i*[f]and[i]+f(n,2*i)+i%2*f(n,i-~i)
f=lambda n,i=1:[f][i>>n:]and[i]+f(n,2*i)+i%2*f(n,i-~i)

```

# Answer
> 18 votes
# Jelly, 6 bytes

```
Ḷ2*ẆS€

```

This qualifies for the imaginary bonus.

Try it online!

### How it works

```
Ḷ2*ẆS€  Main link. Argument: n

Ḷ       Unlength; yield [0, ..., n-1].
 2*     Yield [2**0, ..., 2**(n-1)].
   Ẇ    Sliding window; yield all subarrays of consecutive elements.
        The subarrays are sorted by length, then from left to right.
    S€  Map the sum atom over the substrings.

```

# Answer
> 9 votes
# Mathematica, 40 bytes

```
Join@@Table[2^j(2^i-1),{i,#},{j,0,#-i}]&

```

Every number in the desired list is the difference of two powers of 2, so we simply generate them in order using `Table` and then flatten the list. I think this earns Stewie Griffin's imaginary bonus :)

## Mathematica, 35 bytes

```
Tr/@Rest@Subsequences[2^Range@#/2]&

```

A port of Dennis's Jelly algorithm. I didn't know about `Subsequences` before this! (I also didn't see that miles had posted this exact answer ... go upvote it!)

# Answer
> 8 votes
## JavaScript (ES6), ~~59~~ ~~58~~ 55 bytes

```
for(q=prompt(n=1);p=q--;n-=~n)for(m=n;p--;m*=2)alert(m)

```

A full program that takes input through a prompt and alerts each number in succession. This also qualifies for the imaginary bonus.

### Test snippet

(Note: uses `console.log` instead of `alert`)

```
for(q=prompt(n=1);p=q--;n-=~n)for(m=n;p--;m*=2)console.log(m)
```

# Answer
> 7 votes
## JavaScript (ES6), ~~55~~ 51 bytes

Returns a space-separated list of integers.

```
n=>(F=k=>k>>n?--j?F(k>>j|1):'':k+' '+F(k*2))(1,j=n)

```

Imaginary bonus friendly.

### Formatted and commented

```
n => (                    // main function, takes n as input
  F = k =>                // recursive function, takes k as input
    k >> n ?              // if k is greater or equal to 1 << n:
      --j ?               //   decrement j ; if j is > 0:
        F(k >> j | 1)     //     do a recursive call with an additional bit set
      :                   //   else
        ''                //     stop recursion
    :                     // else
      k + ' ' + F(k * 2)  //   append k to output and do a recursive call with k * 2
  )(1, j = n)             // start the recursion with k = 1 and j = n

```

### Test cases

```
let f =

n=>(F=k=>k>>n?--j?F(k>>j|1):'':k+' '+F(k*2))(1,j=n)

console.log(f(1))
console.log(f(2))
console.log(f(3))
console.log(f(8))
console.log(f(17))
```

# Answer
> 6 votes
# Python 2, ~~64~~ 61 bytes

<sup>-3 bytes thanks to Dennis</sup>

```
n=2**input()
j=i=1
while j<n:
 print i;i*=2
 if i/n:i=j=2*j+1

```

Try it online!

# Answer
> 6 votes
# Mathematica, 35 bytes

```
Tr/@Rest@Subsequences[2^Range@#/2]&

```

# Answer
> 5 votes
# Python 2, ~~65~~ ~~63~~ 58 bytes

```
lambda n:[(2<<k/n)-1<<k%n for k in range(n*n)if k/n+k%n<n]

```

Try it online!

# Answer
> 5 votes
# Haskell, 37 bytes

```
f n=[2^b-2^(b-a)|a<-[1..n],b<-[a..n]]

```

Try it online!

# Answer
> 4 votes
# Groovy, ~~90~~ 89 bytes

```
{(0..<2**it).collect{0.toBinaryString(it)}.sort{it.count("1")}.collect{0.parseInt(it,2)}}

```

Binary conversion is so dumb in groovy.

*-1 thanks to Gurupad Mamadapur*

# Answer
> 4 votes
## Haskell, 47 bytes

```
f n=[1..n]>>= \b->take(n-b+1)$iterate(2*)$2^b-1

```

Usage example: `f 4` -\> `[1,2,4,8,3,6,12,7,14,15]`. Try it online!.

How it works: for each number `b` in `[1..n]`, start with `2^b-1` and repeatedly double the value and take `n-b+1` elements from this list.

# Answer
> 4 votes
# 05AB1E, 6 bytes

```
L<oŒéO

```

Try it online! or as a Test suite

**Explanation**

Uses the sublist-sum trick as shown in Dennis' Jelly answer

```
L       # range [1 ... input]
 <      # decrement each
  o     # raise 2 to each power
   Œ    # get all sublists
    é   # sort by length
     O  # sum

```

# Answer
> 3 votes
# Pyth, 7 bytes

```
sM.:^L2

```

Try it online.

Uses Dennis's algorithm.

# Answer
> 3 votes
# Bash \+ Unix utilities, 51 bytes

```
dc<<<2i`seq -f%.f $[10**$1-1]|grep ^1*0*$|sort -r`f

```

Try it online!

The input n is passed in an argument.

Use seq to print all numbers with n or fewer digits. (These are base-10 numbers, so there are lots of extra numbers here. It's wasteful and time-consuming, but this is code golf!)

The call to grep keeps only those numbers that consist precisely of 1s followed by 0s.

Then use sort -r to sort these in reverse lexicographical order.

Finally, dc is set to base 2 input -- it pushes the sorted numbers on a stack and then prints the stack from top to bottom. (This prints the last item pushed first, etc., which is why I'm using sort -r instead of just sort.)

Corrected a bug: I had omitted the option -f%.f to seq, which is required for integer counts from 1000000 on. (Thanks to @TobySpeight for pointing out that there was a problem.)

# Answer
> 2 votes
# Mathematica/Mathics, 69 bytes

```
{0,1}~Tuples~#~SortBy~Count@1/.n:{a=0...,1..,a}:>Print@Fold[#+##&,n]&

```

Try it online!

# Answer
> 2 votes
# Python, ~~61~~ 59 bytes

```
lambda n:[2**-~i-1<<j for i in range(n)for j in range(n-i)]

```

Try it online!

# Answer
> 2 votes
## Japt, 11 bytes

```
o@o!²ãXÄ mx

```

Test it online!

### Explanation

This pretty much uses @Dennis's approach:

```
o@ o!²  ãXÄ  mx
oX{o!p2 ãX+1 mx}
                  // Implicit: U = input integer
oX{            }  // Create the range [0...U) and map each item X by this function:
   o              //   Create the range [0...U)
    !p2           //     and map each item Z to 2.p(Z); that is, 2**Z.
                  //     (p2 would map each item Z to Z.p(2); ! reverses the arguments.)
        ãX+1      //   Get all overlapping slices of length X + 1.
             mx   //   Map each of these slices Z through Z.x(); that is, sum each slice.
                  // Implicit: output result of last expression

```

# Answer
> 2 votes
# Perl 6, 38 bytes

```
->\n{map {|(2**$_-1 X+<0..n-$_)},1..n}

```

### How it works

```
->\n{                                }  # A lambda with argument n.
                                 1..n   # Numbers from 1 to n.
     map {                     },       # Replace each one with a list:
            2**$_-1                     #   2 to that power minus 1,
                    X+<                 #   bit-shifted to the left by each element of
                       0..n-$_          #   the range from 0 to n minus the number.
          |(                  )         #   Slip the list into the outer list.

```

I.e. it constructs the numbers like this:

```
1 2 4 8 = (2^1)-1 bit-shifted to the left by 0 1 2 3 places
3 6 12  = (2^2)-1 bit-shifted to the left by 0 1 2   places
7 14    = (2^3)-1 bit-shifted to the left by 0 1     places
15      = (2^4)-1 bit-shifted to the left by 0       places     ← n rows
             ↑                                     ↑
             n                                     n-1

```

The code:

---

# Perl 6, 44 bytes

```
->\n{map {|(2**$_-1,* *2...^*>2**n-1)},1..n}

```

This was my first approach before I thought of the (actually simpler) bit-shift solution above.

### How it works

```
->\n{                                      }  # A lambda with argument n.
                                       1..n   # Numbers from 1 to n.
     map {                           }        # Replace each one with:
            2**$_-1                              # 2 to that power minus 1,
                   ,* *2                         # followed by the result of doubling it,
                        ...^                     # repeated until (but not including)
                            *>2**n-1             # it's larger than 2^n-1.
          |(                        )            # Slip the list into the outer list.

```

I.e. it constructs the numbers like this:

```
1 2 4 8 = (2^1)-1, times 2, times 2, times 2
3 6 12  = (2^2)-1, times 2, times 2
7 14    = (2^3)-1, times 2
15      = (2^4)-1                                ← n rows
             ↑                       ↑
             n                       as many columns as possible in
                                     each row without exceeding (2^n)-1

```

# Answer
> 2 votes
**Haskell ~~59~~ 46 Bytes**

I started out with `f n=[0..n]>>= \b->take(n-b).iterate(*2).sum.map(2^)$[0..b]`

from nimi's answer above gained the insight that `sum.map(2^)$[0..x]` can be condensed down to `2^x-1`

Ending up with

`e n=[1..n]>>= \x->map(\y->2^y*(2^x-1))[0..n-x]`

**\[1..n\]** -- list with number of consecutive bits we want to cycle through\`

**\>\>=** --roughly translated for each element in list on left pass it into the function on right and concatenate all results

**\x -\>** -- lambda function declaration with one argument

**map x y**-- applies function x to all members of the list y

In our case x = **(\y-\>2^y\*(2^x-1))** -- another lambda function 2^y\*(2^x-1)). This formula arises from multiplication by two adding a zero to right in binary(example 0001 to 0010). 2^x - 1 is the number of bits we are working with. so for 11 we have 2^0\*3(i.e. dont shift at all) == 0011, then 2^1\*3 = 0110 then 2^2\*3 - 1100.

**\[0..n-x\]** Builds the list of how many times we can shift the bits. If we are working with a single 1 then looking at 0001 we want to shift 3 times (4-1). If we are working two 11 we want 4-2 and so on.

# Answer
> 2 votes
# Python 3, 59 bytes

Note: this was made independently of ovs's and Dennis's solutions, even though it is very similar to both.

```
lambda n:[(2<<i)-1<<j for i in range(n)for j in range(n-i)]

```

How it works:

```
for i in range(n)for j in range(n-i)  # Iterate over number of ones, then number of places
                                      # shifted over. i = ones, j = shifts

(2<<i)                                # Create a one followed by i zeroes
      -1                              # Subtract one from above to get i ones.
        <<j                           # Shift j places.

```

Try it online!

Tips (both coding and cash) are always welcome!

# Answer
> 2 votes
# PHP, ~~59 56~~ 53 bytes

```
for(;$p>($k*=2)?:($p=1<<$argn)>$k=$i+=$i+1;)echo$k,_;

```

takes input from STDIN; run with `-R`.

**breakdown**

```
for(;$p>($k*=2)         // 3. inner loop: shift-0 $k while $k<$p (false in first iteration)
    ?:
    ($p=1<<$argvn)      // 1. init $p=2^N, outer loop:
    >$k=$i+=$i+1        // 2. shift-1 $i while $i<$p, init $k to new $i
;)
    echo$k,_;           // 4. print $k

```

# Answer
> 1 votes
# Python 3, 91 bytes

```
a=int(input())
print(*[int('1'*-~b,2)<<c for b in range(a)for c in range(a-b)],sep=', ')

```

Full program, with comma+space separated output, as specified.

Explanation:

Star notation unpacks lists. So `print(*[1,2,3])` is the same as `print(1,2,3)`. Pass the `int()` constructor a string of consecutive '1's.

`-~b` evaluates to `b+1`, but you don't have to surround it with brackets when multiplying a string.

Bitshift the produced integer an increasing number of times. `print()` has the optional sep argument, specifying the string to put in between each item in an unpacked list.

# Answer
> 1 votes
# , 19 bytes

```
(0-.~&,>:+/\2&^)@i.

```

This uses the same method in @Dennis' solution.

Try it online!

## Explanation

```
(0-.~&,>:+/\2&^)@i.  Input: integer n
                 i.  Range [0, 1, ..., n-1]
(              )@    Operate on that range
            2&^        Compute 2^x for each x in that range
       >:              Increment each in that range
           \           For each overlapping sublist of size (previous) in powers of 2
         +/              Reduce by addition
 0                     The constant 0
     &,                Flatten each
  -.~                  Remove zeroes

```

# Answer
> 1 votes
# MATL, ~~19~~ 18 bytes

*1 byte saved thanks to @Luis*

```
:q2w^XJfP"J@YC2&sv

```

**Try it Online**

# Answer
> 1 votes
## QBIC, 37 bytes - imaginary bonus = still 37 bytes...

```
:[a|e=2^b-1┘while e<2^a┘?e┘e=e*2┘wend

```

Shame I haven't built `while-wend` into QBIC yet... Explanation:

```
:       Get N from the command line
[a|     For b = 1 to N; The sequence is reset N times
e=2^b-1 Set the first number of this sub-sequence (yields 1, 3, 7, 15 ...)
┘       Line-break - syntactic separation of commands because there's no command for WHILE yet.
while   Pure QBasic code - lower-case is not (really) interpreted by QBIC
e<2^a   Continue as long as we don't exceed the maximum value
┘?e     Print the number in the sequence
┘e=e*2  Double the number
┘wend   And loop as long as we're not exceeding maximum, reset the sequence otherwise.
        FOR loop auto-closed by QBIC

```

---

EDIT: QBIC now has support for `WHILE`:

```
:[a|e=2^b-1≈e<2^a|?e┘e=e*2

```

This is only 26 bytes! Here's the `WHILE`:

```
≈e<2^a|          ≈ = WHILE, and the TRUE condition is everything up to the |
       ...       Loop code goes here
          ]      Close construct: adds a WEND instruction
                 In the program above, this is done implicitly because of EOF.

```

# Answer
> 1 votes
# Java 7, 108 bytes

```
static void x(int i){int a=0,t=1<<i,b;while((a=(a<<1)+1)<t){b=a;do System.out.println(b);while((b<<=1)<t);}}

```

Doubles the initial value as long as the result is smaller than `2^n`. Afterwards, updates the initial value to be `(initial_value * 2) + 1` and starts again from there until it eventually reaches `(2^n)-1`.

e.g. for `n=4`:

```
0001 -> init
0010
0100
1000
return, double init and add one
0011 -> init
0110
1100
return, double init and add one
0111 -> init
1110
return, double init and add one
1111 -> init
done

```

Try it online!

# Answer
> 1 votes
## Ruby, 50 bytes

```
->r{1.upto(r){|x|p a=2**x-1;p a while(a*=2)<2**r}}

```

I tried some "clever" approaches, but this seems to be the shortest (literally follow the instructions)

### Explanation:

Each iteration starts with 2^n-1 and multiplies by 2 until the upper limit is reached. Nothing fancy, just basic math.

# Answer
> 1 votes
# , ~~69~~ ~~48~~ 46 bytes

```
n=scan();for(i in 1:n)print((2^i-1)*2^(i:n-i))

```

Each decimal number corresponding to `i in 1..n` ones in binary system is multiplied by `2^(0..n-i)`, i.e first `n-i+1` powers of two (1, 2, 4, ...).

Try it online!

# Answer
> 1 votes
# Stax, 9 bytes

```
übg▓}╥é►╪

```

Run and debug online!

## Explanation

> Imaginary bonus if someone does this without any form of base conversion (using plain old maths).

Well, there are no base conversion here.

Uses the unpacked version (10 bytes) to explain.

```
m|2vx_-DQH
m             For input=`n`, loop over `1..n`
 |2v          Power of two minus one
    x_-D      Do `n-j` times, where `j` is the current 1-based loop index
        Q     Output the current value
         H    And double it

```

# Answer
> 0 votes
## Batch, 92 - 0 = 92 bytes

```
@for /l %%i in (1,1,%1)do @for /l %%j in (%%i,1,%1)do @cmd/cset/a"(1<<%%i)-1<<%%j-%%i"&echo(

```

Subtracting 0 for @StewieGriffin's imaginary bonus.

# Answer
> 0 votes
# C, 69 bytes

New way:

```
m;s;f(n){for(m=1;m<<=1<=1<<n;)for(s=m-1;s<1<<n;s*=2)printf("%d ",s);}

```

previous 72 bytes solution:

```
i;s;f(n){for(i=1;i<=n;++i){for(s=(1<<i)-1;s<1<<n;s*=2)printf("%d ",s);}}

```

# Answer
> 0 votes
# Perl 5, 51 bytes

```
map{$_=2**$_-1;do{say}while($_*=2)<2**$l}1..($l=<>)

```

Try it online!

---
Tags: code-golf, sorting, base-conversion, binary
---


title: Creating a function over multiple lines

text:
# Question
Title: Creating a function over multiple lines
I'm attempting to create a function over multiple lines.

# Parameters of the challenge:

1. Function returns 'barbarian'
2. Only 2 characters per line
3. 40 lines maximum. I keep trying to use a fat arrow to declare my function, but fat arrows don't seem to work if you don't have them connected.

Source of Challenge: https://www.codewars.com/kata/multi-line-task-plus-plus-hello-world

My current work:

```
f=
(
)=>

'\
b\
a\
r\
b\
a\
r\
i\
a\
n\
s\
'

```

This works, but the ')=\>' is 3 characters long. I really just want to know how it is possible to even stretch out the creation of a function. I can't find any info on it anywhere as it's obviously not very practical.

# Answer
Here is a 38 line solution:

```
f=
[]
[
'\
m\
a\
p'
][
'\
c\
o\
n\
s\
t\
r\
u\
c\
t\
o\
r'
]`
r\
e\
t\
u\
r\
n\
'\
b\
a\
r\
b\
a\
r\
i\
a\
n\
'`

```

It creates a function using the `Function` constructor, which it accesses from `[].map.constructor` using subscript notation (`[]['map']['constructor']`). This is the method JSFuck uses to create functions.
> 9 votes

# Answer
# 35 Lines

```
f=
0[
c=
'\
c\
o\
n\
s\
t\
r\
u\
c\
t\
o\
r'
][
c]
`
r\
e\
t\
u\
r\
n\
'\
b\
a\
r\
b\
a\
r\
i\
a\
n'
`

```

Try it online!

Uses the fact that `0` is a number, the constructor of `0` is `Number`, and the constructor of `Number` is `Function`.

# 32 Lines

```
0[
c=
'\
c\
o\
n\
s\
t\
r\
u\
c\
t\
o\
r'
][
c]
`
f=
_\
=>
'\
b\
a\
r\
b\
a\
r\
i\
a\
n'
`(
)

```

Try it online!

This essentially runs

```
Function(`
f=
_=>
'barbarian'`)()

```

which uses the IIFE structure. Added bonus is that we can line-break some parts in the function body to reduce the line count.

# 24 Lines

```
f=
''
[
'\
t\
r\
i\
m'
][
'\
b\
i\
n\
d'
]`
b\
a\
r\
b\
a\
r\
i\
a\
n`

```

Try it online!

Inline version:

```
f=''['trim']['bind']`
barbarian`

```

Since all we want is to return a string, we can get away with a string method bound to a string. By using `trim`, we can also safely leave a beginning newline.
> 16 votes

---
Tags: code-challenge, restricted-source, tips, source-layout, javascript
---


# Question
Title: Simple single-player board game, expected score distribution
This is the first problem I've posted here; please post criticisms in comments.

## Summary

A game board consists of a starting space, an ending space, and between them are `N` spaces, each with an instruction. You begin on the starting space with `0` points to your credit. Flip a coin or roll a die to choose the number `1` or `2`. Move forward that many spaces. Now look at the instruction on the space you landed on. The possible instructions consist of "Do nothing", "Score `x` points", and "Move forward `y` spaces and obey the instruction there". `x` and `y` are positive. After obeying the instruction, go back to the coin flip. When you land on or pass the ending square, the game is over.

Given a description of a game board (number of squares, instruction on each space) your code should calculate the probability distribution of possible ending scores. It's irrelevant how many turns are taken before the end.

## Input

* An unambiguous representation (in whatever format you desire, though numbers should be human-readable) of the instruction on each space. Numbers should be human-readable.

## Output

* A list of pairs of each possible score and the probability of obtaining that score (either an exact fraction or a real number accurate to at least four decimal places). Can be returned or output. It's optional to include scores that have 0 probability of occurring.

## Scoring the entries

1. They must be correct to be considered; wrong answers don't count.
2. Code size. If you golf it please also post an ungolfed version; if you use a golfing language please post a good explanation.

## Examples

### Easy

* Input

```
3

1
F2
1

```
* Output

```
0 0.5    // rolled a 2 on first turn, game over
1 0.25   // rolled a 1 then a 1
2 0.25   // rolled a 1 then a 2

```

### Complex

* Input

```
16

2
1
0
5
10
F3
5
15
1
0
3
F3
5
0
0
5

```
* Output

```
7   0.0234375
8   0.0078125
9   0.01171875
10  0.03515625
11  0.01171875
12  0.048828125
13  0.015625
14  0.015625
15  0.0732421875
16  0.0322265625
17  0.06005859375
18  0.015625
19  0.01171875
20  0.087890625
21  0.046875
22  0.0654296875
23  0.009765625
24  0.0107421875
25  0.064453125
26  0.0380859375
27  0.0380859375
28  0.001953125
29  0.0029296875
30  0.044677734375
31  0.023681640625
32  0.0281982421875
33  0.00390625
34  0.0029296875
35  0.015869140625
36  0.017333984375
37  0.0177001953125
38  0.0078125
39  0.0087890625
40  0.013916015625
41  0.015625
42  0.0096435546875
43  0.00390625
44  0.009033203125
45  0.0155029296875
46  0.010009765625
47  0.00567626953125
49  0.003662109375
50  0.0067138671875
51  0.003662109375
52  0.00274658203125

```

# Answer
# Stax, ~~56~~ 55 bytesCP437

```
üZÄ^3Γ╥£X╜T∩L╖á↨→╘Oïë╢Δ╥∙Eü╦5├jC╩XpN◘╘♥«╟╝☻y╞╘wé↔Ioÿ≈⌐─

```

Run and debug online!

Warning: Takes a long time (around 5 minutes in my box) to run the large example.

*Credits to the almighty rubber duck for -1 byte.*

Input is a list of numbers. `Scoring x points` is represented by `-x`, and `Move y steps forward and follow the instruction there` is represented by `y`. So for example the small test case will be represented as `[-1,2,-1]`.

Outputs in rational number, the output for the large case is like this:

```
7 3/128
8 1/128
9 3/256
10 9/256
11 3/256
12 25/512
13 1/64
14 1/64
15 75/1024
16 33/1024
17 123/2048
18 1/64
19 3/256
20 45/512
21 3/64
22 67/1024
23 5/512
24 11/1024
25 33/512
26 39/1024
27 39/1024
28 1/512
29 3/1024
30 183/4096
31 97/4096
32 231/8192
33 1/256
34 3/1024
35 65/4096
36 71/4096
37 145/8192
38 1/128
39 9/1024
40 57/4096
41 1/64
42 79/8192
43 1/256
44 37/4096
45 127/8192
46 41/4096
47 93/16384
49 15/4096
50 55/8192
51 15/4096
52 45/16384

```

## Alternative version

Calculates the probability recursively instead of enumerating every possibility. Much faster. Not really golfed.

`00\sn+~]]01\]]+Yd;%{;%=zi^]?i]+ys@iXd{{dx2<;x|i-v@1<+!C_E2u*s;x@0|m-s\mm:f;i({i+|i=!Ci2+mys@{{B;x@0|m-+rm+F{o{h}/{hh0_{H+F\m]ys+YdFUUv\ys@:fo{h}/mhh0_{H+F\J`

Try and debug online!

The two different algorithms give the same result.

## Explanation

Uses the unpacked version to explain. The size of the game board is stored in register `x`. The current position on the board is stored in register `y`. There is an extra flag (boolean) denoted `bFlip` that is stored on the stack, used to indicate the type of last instruction.

The complete unpacked version is 66 bytes.

```
X|2{v:Bx)0Y1~s{^,*y+Ycx>{d1~}{v;@c1<c~{-}{y+Yd}?}?F,dmo|RmNx|2u*+J

```

I will explain it part by part.

```
X|2{v:Bx)0Y1~s{     F,dm
X|2                        `2^x`
   {v                  m    For `[0..2^x-1]` do the following
     :Bx)                   Binary representation of the current loop index
                            Padded with zeros to make the length `l`.
                            Each binary represents a sequence of coin flip outcomes
         0Y1~s              Initialize `y` and current score to `0`, and `bFlip` to true
              {     F       Play the game as indicated by the sequence of coin flip outcomes
                     ,d     Clean up: remove `bFlip` from the stack.

```

The block that plays the game:

```
{^,*y+Ycx>{d1~}{v;@c1<c~{-}{y+Yd}?}?F
{                                   F    The loop as stated above
 ^                                       Increment current flip result
                                         Map the original [0,1] to [1,2], denote this as `n`.
  ,*                                     If last instruction is of the type `Score k points` (`k` may be `0`)
    y+Y                                      Move forward `n` steps and save the new current position to register `y`.
       cx>{   }{                  }?     If already moved past the end
           d1~                               Mark this instruction as `Score 0 points` (or `Do nothing`)
                                         Else
                v;@                          Get current instruction
                   c1<c~                     Get the type of current instruction and remember it
                        { }{    }?           If the current instruction is `Score k points`
                         -                       Score `k` points
                                             Else
                            y+Yd                 Move forward as the instruction indicates

```

After executing this, we have a list with `2^x` elements containing the scores of all possible coin flips, with equal probabilities. The rest of the program is just converting them to the output.

```
o|RmNx|2u*+J
o|R             Convert to a list of pairs of [element, count of appearance]
   m            Map the array elements with the rest of the program, output the results on separate lines
    Nx|2u*+     Divide the count of appearance by `2^x` to get probability
           J    Join the two elements with a space

```
> 3 votes

# Answer
# Perl 5, `-a0` ~~111~~ 108 bytes

Input format: Give the instructions separated by white-space (newline works) on STDIN including the starting cell represented by `0`. The `jump` is indicated by an `F` **after** the number. So the example input becomes:

```
0
1
2F
1

```

With correct output

```
0 0.5
1 0.25
2 0.25

```

```
#!/usr/bin/perl -a0
@1=1;$n++,map{$i=0;for$a(@$n){${$n+$_>@F?z:$n+$_}[$i+++$']+=$a/2}}/F/?($`)x2:(/|/,2)for@F;say$z++," $_"for@z

```

Try it online!
> 1 votes

---
Tags: code-golf, random, board-game, probability-theory
---


title: The greedy cutter

text:
# Question
Title: The greedy cutter
iBug recently got a long bar made of composite, yet valuable materials. The bar is so long that iBug can't easily sell it for credits, so he wants to cut it. The bar is made of such fragile and magic materials that, if a part is broken, all parts of the bar made of the same material will break, too, making it hard to cut arbitrarily.

iBug wants to cut the bar into as many pieces as possible. He also loves very short programs and code-golfing, so he made an abstract analysis of his problem.

iBug's magic bar is represented as a string (or an array or a sequence of characters if you prefer), like this:

```
aaabbccccccbbbaaacccccaabbbaaaaa

```

Each letter in the string represents one magic material. The bar always matches the RegEx `^\w*$`, so there may be up to 63 materials in the bar. A "part" is a consecutive sequence of any characters that are not separated by spaces.

iBug wants you to write a program that calculates the maximum parts that he could get, if zero or more character sets are fully removed (replaced by spaces), and tell iBug that number.

---

Example 1:

```
In:  aaabbccccccbbbaaacccccaabbbaaaaa
Out: 4

```

Description: If `b` is fully removed from the bar, iBug could get 4 parts. He can also get 4 parts by removing `b` and `c`, as is shown below

```
aaabbccccccbbbaaacccccaabbbaaaaa  # Original string
aaa  cccccc   aaacccccaa   aaaaa  # Remove 'b'
aaa           aaa     aa   aaaaa  # Remove 'b' and 'c'

```

And that's the maximum number of parts iBug can get from this bar

Example 2:

```
In:     111aa___9999____aaa99111__11_a_aa999
Result: 111aa   9999    aaa99111  11 a aa999
Out:    6

```

Description: By removing only the underscore, iBug can get 6 parts from the bar and that's the maximum.

Example 3:

```
In:  __________
Out: 1

```

Description: What? You wanna cut this? It's only possible to get 1 part if you don't cut it at all.

Example 4:

```
In:
Out: 0

```

Description: There's nothing to cut, so zero.

---

There's also some rules that iBug want the programs to obey:

1. iBug dislikes standard loopholes and they are forbidden.
2. As long as it works, it need not be a full program. A function that takes input from a parameter and gives output via return value is also accepted.
3. Flexible input and output are allowed. Your program or function can take a string, or an array of characters, or whatever you find easiest to deal with. You can give the output by printing the number or returning it.

---

### Sample test cases (but not limited to these)

```
aaabbbaaa           = 2
123456789           = 5
AaAaAaAa            = 4
aaabcccdedaaabefda  = 6
________            = 1
(empty)             = 0

```

Since this is a , the shortest program (in bytes) in each language wins!

---

### Extra

iBug highly appreciates if you can provide an explanation for your program, even though it does not affect your scoring (it's still length in bytes).

# Answer
# Haskell, ~~73 71~~ 70 bytes

```
x#z|z==x=' '|1<2=z
f x=maximum$length(words x):[f$(c#)<$>x|c<-x,c>' ']

```

Thanks to Laikoni for saving 1 byte!

Try it online!
> 8 votes

# Answer
## JavaScript (ES6), ~~109~~ 90 bytes

```
f=s=>Math.max((s.match(/\s+/g)||[]).length,...[...s].map(c=>c>` `&&f(s.split(c).join` `)))
```

```
<input oninput=o.textContent=/\s/.test(this.value)?``:f(this.value)><pre id=o>0
```

Somewhat slow on the `123456789` test case. Previous 109-byte answer wasn't limited to `!/\s/`:

```
f=
s=>(g=a=>Math.max(a.filter(s=>s).length,...[...a.join``].map(c=>g([].concat(...a.map(s=>s.split(c)))))))([s])
```

```
<input oninput=o.textContent=f(this.value)><pre id=o>0
```
> 6 votes

# Answer
# Python 2, ~~111~~ ~~93~~ 72 bytes

-21 bytes thanks Kirill L.

```
f=lambda s:max([len(s.split())]+[f(s.replace(c,' '))for c in s if'/'<c])

```

Try it online!
> 4 votes

# Answer
# Ruby, ~~98 89 75 64~~ 61 bytes

```
f=->s{[s.split.size,*s.scan(/\w/).map{|c|f[s.tr c,' ']}].max}

```

Try it online!

smaller and slower than before!

Basically a port of @Neil's Javascript answer

### Ungolfed and annotated

```
def f(input_string)
    # splits by / +/ by default
    size0 = input_string.split.size
    # an array of all non-space characters in input_string
    characters = input_string.scan(/\w/)
    size1 = characters.map {|i|
        # all letters and digits and _ are "bigger" than /, space isn't
        if i > '/'
            # tr replaces every occurrence of i in input_string with space
            next_string = input_string.tr(i, ' ')
            f(next_string) # recursive call
        else
            0
        end
    }
    # max value between size0 and any element in size1
    return [size0, *size1].max
end

```

Try it online!
> 3 votes

# Answer
# Jelly,  ~~13~~  11 bytes

~~Too many 2-byte instructions~~
-2 thanks to Zgarb (use the outer product quick `þ` \>.\<)

```
eþŒPŒr¬S€ṀḢ

```

A monadic link accepting a list of characters and returning a non-negative integer.

**Try it online!**

### How?

For each subsequence of the input (the sets we may remove, plus redundant equivalents) gets an existence list to identify which are removed then effectively finds how many runs of zeros remain and yields the maximum. The last part works in a slightly odd way since I found it golfier than more naive alternatives - it finds the runs as `[element, count]` pairs, negates to identify zeros as ones, sums finds the maximum then takes the head (the sum of elements rather than of counts).

```
eþŒPŒr¬S€ṀḢ - Link: list of characters        e.g. "aabcde"
  ŒP        - power-set - gets all subsequences    ["","a","a","b",...,"bd",...,"aabcde"]
 þ          - outer-product with:
e           -   exists in?                         [[0,0,0,0,0,0],[1,1,0,0,0,0],[1,1,0,0,0,0],[0,0,1,0,0,0],..,[0,0,1,0,1,0]...,[1,1,1,1,1,1]]
    Œr      - run-length encode                    [[[0,6]],[[1,2],[0,4]],[[1,2],[0,4]],[[0,2],[1,1],[0,3]],...,[[0,2],[1,1],[0,1],[1,1],[0,1]],...,[[1,6]]]
      ¬     - NOT                                  [[[1,0]],[[0,0],[1,0]],[[0,0],[1,0]],[[1,0],[0,0],[1,0]],...,[[1,0],[0,0],[1,0],[0,0],[1,0]],...,[[0,0]]]
        €   - for €ach:
       S    -   sum                                [[1,0],[1,0],[1,0],[2,0],...,[3,0],...,[0,0]]
         Ṁ  - maximum                              [3,0]
          Ḣ - head                                 3

```
> 3 votes

# Answer
# Perl 5, (older versions), `-p -I.`, ~~52~~ ~~49~~ 43 bytes

Old style counting: `+3` for `-p`: `46` bytes (because it **must** be in a program, it can't be run using `-e`)

`barsplit.pl`:

```
#!/usr/bin/perl -pI.
$G[split]+=s%\S%do$0for s/$&/ /rg%eg;$_=$#G

```

Run with the string on STDIN:

```
echo aaabcccdedaaabefda | ./barsplit.pl; echo

```

Try it online!

The `-I.` option is there to make this also work on recent perls where by default `.` is no more in `@INC`. In older versions of perl that option is not needed. I tested that on an older machine that still had `perl 5.20`, so the score is based on that (otherwise I should also count the `.` argument to `-I`)

Fast version (`49` bytes):

```
#!/usr/bin/perl -pI.
$G[split]+=s%.%$$_++||do$0for s/$&/ /rg%eg;$_=$#G

```
> 2 votes

# Answer
# Husk, ~~12~~ 11 bytes

```
▲mȯ#€0gM€¹Ṗ

```

Try it online! This works by brute force and is quite slow. Add `u` to the right end to make it run faster, without changing the semantics.

## Explanation

```
▲mȯ#€0gM€¹Ṗ  Implicit input, say S = "abddccbdcaab"
          Ṗ  Powerset of S: P = ["","a","b","ab","d","ad"...,"abddccbdcaab"]
 m           Map this function over P:
              Argument is a subsequence, say R = "acc"
       M ¹    Map over S
        €     index of first occurrence in R: [1,0,0,0,2,2,0,0,2,1,1,0]
      g       Group equal elements: [[1],[0,0,0],[2,2],[0,0],[2],[1,1],[0]]
  ȯ#          Count the number of groups
    €0        that contain 0: 3
▲            Take maximum of the results: 4

```
> 2 votes

# Answer
# Wolfram Language (Mathematica), 77 bytes

```
Max@Table[Tr[1^StringSplit[#,(##|##)..&@@s]],{s,Subsets@Union@Characters@#}]&

```

Try it online!
> 0 votes

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


title: RGB to Xterm Color Converter

text:
# Question
Title: RGB to Xterm Color Converter
256-color Xterm-compatible terminals add 240 colors on top of the usual 16 system colors. Colors 16-231 use 6 levels (0, 95, 135, 175, 215, 255) of red, green, and blue, ordered lexicographically. Colors 232-255 are simply 24 levels of gray (8...238 by 10s). To get a better idea of what I'm talking about, see this table.

# The Challenge

Your goal is to make a program or function that takes, as input, rgb values, and outputs the number corresponding with the closest Xterm color to that rgb value. **Since the 16 system colors (colors 0-15) are often customizable, you will be excluding them from this conversion.**

To better define what the "closest" color is, use the Manhattan distance along red, green, and blue components. For example, `rgb(10, 180, 90)` is 20 units away from `rgb(0, 175, 95)` (color 35) because `abs(10 - 0) + abs(180 - 175) + abs(90 - 95) == 20`. If the input color is equally between two or more Xterm colors, output the Xterm color with the highest index.

# Examples

```
 R   G   B     Xterm
  0   0   0 ==> 16
 95 135   0 ==> 64
255 255 255 ==> 231
238 238 238 ==> 255

 90 133 140 ==> 66
218 215 216 ==> 188
175 177 178 ==> 249

175   0 155 ==> 127
 75  75  75 ==> 239
 23  23  23 ==> 234
115 155 235 ==> 111

```

# Rules

* Standard loopholes are forbidden
* Your program or function is allowed to take rgb values in any reasonable format, including:
    + Separate arguments for red, green, and blue
    + A list, tuple, dictionary, or similar
    + Delimiter-separated string or stdin
    + Hex colors (e.g. `#ff8000`)
* You may assume that all r, g, and b, values will be integers between 0 and 255.
* Since the 16 system colors are to be excluded from the mapping, all outputs should be in the range 16...255.

This is , so shortest code wins.

# Answer
# Haskell, 132 bytes

```
v=0:[95,135..255]
f c=snd$maximum[(-sum(abs<$>zipWith(-)c x),i)|(i,x)<-zip[16..]$[[r,g,b]|r<-v,g<-v,b<-v]++[[g,g,g]|g<-[8,18..238]]]

```

Try it online!

Takes input as a list of integers `[red, green, blue]`.

Fairly straightforward implementation. First I build a list of the Xterm colors we're using with two list comprehensions concatenated together. The first of which handles colors 16-231 by triple iterating over `v` which contains the values those colors use. The second one just iterates over the grey values and puts them in all three slots. Then I index it with zip (starting at 16) and make a pair with the manhattan distance (negated) and that index and take the maximum. I used maximum because we're tie-breaking on the largest index and this way saves me one extra `-`.
> 4 votes

# Answer
# Ruby, ~~280~~ ~~180~~ ~~166~~ ~~164~~ 155 bytes

```
->c{d=0,95,135,175,215,255
a=(0..239).map{|n|n<216?[d[n/36],d[(n%36)/6],d[n%6]]:[n*10-2152]*3}.map{|t|t.zip(c).map{|a,b|(a-b).abs}.sum}
a.rindex(a.min)+16}

```

Try it online!

A lambda taking the input color as an array of integers.

I had more trouble generating the Xterm colors than I expected! I'm prepared to be outgolfed ~~embarrassingly~~ modestly in that area. I used base conversion as a kind of compression, ~~but the only way I know to do so in Ruby is through `Integer#to_s`~~ which is a little bit awkward.

-100 bytes: Read the problem more carefully, and ignore the 16 system colors ^\_^;

-14 bytes: Use hand base conversion instead of `.to_s(6)`

-2 bytes: Skip square brackets when declaring array

-9 bytes: Create list of Xterm colors with only one `map`; this also saves a plus sign and a pair of parens.

```
->c{
  d=0,95,135,175,215,255                 # d is the set of possible RGB values
  a=(0..239).map{|n|                     # Create the array of Xterm triplets
    n<216 ? [d[n/36],d[(n%36)/6],d[n%6]] # Convert x from base 6 to base d, or
          : [n*10-2152]*3                #   create a uniform triplet
  }.map{|t|
    t.zip(c).map{|a,b|(a-b).abs}.sum     # Map from triplets to Manhattan distance
  }
  a.rindex(a.min) +                      # Find the last index of the lowest distance
  16                                     # Offset for the exluded system colors
}

```
> 3 votes

# Answer
# Kotlin, ~~299~~ ~~290~~ ~~267~~ 265 bytes

```
(16..255).associate{it to if(it<232)(it-16).let{i->listOf(0,95,135,175,215,255).let{l->listOf(l[i/36],l[(i/6)%6],l[i%6])}}else(8..238 step 10).toList()[it-232].let{listOf(it,it,it)}}.minBy{(k,v)->(it.zip(v).map{(a,b)->kotlin.math.abs(a-b)}.sum()*256)+(256-k)}!!.key

```

## Beautified

```
(16..255).associate {
    it to if (it < 232) (it - 16).let { i ->
            listOf(0, 95, 135, 175, 215, 255).let { l ->
                listOf(
                        l[i / 36],
                        l[(i / 6) % 6],
                        l[i % 6])
            }
        } else (8..238 step 10).toList()[it - 232].let { listOf(it, it, it) }
}.minBy { (k, v) ->
    (it.zip(v).map { (a, b) -> kotlin.math.abs(a - b) }.sum() * 256) + (256 - k)
}!!.key

```

## Test

```
data class Test(val r: Int, val g: Int, val b: Int, val out: Int)

val test = listOf(
        Test(0, 0, 0, 16),
        Test(95, 135, 0, 64),
        Test(255, 255, 255, 231),
        Test(238, 238, 238, 255),

        Test(90, 133, 140, 66),
        Test(218, 215, 216, 188),
        Test(175, 177, 178, 249),

        Test(175, 0, 155, 127),
        Test(75, 75, 75, 239),
        Test(23, 23, 23, 234),
        Test(115, 155, 235, 111)
)
fun z(it:List<Int>): Int =
(16..255).associate{it to if(it<232)(it-16).let{i->listOf(0,95,135,175,215,255).let{l->listOf(l[i/36],l[(i/6)%6],l[i%6])}}else(8..238 step 10).toList()[it-232].let{listOf(it,it,it)}}.minBy{(k,v)->(it.zip(v).map{(a,b)->kotlin.math.abs(a-b)}.sum()*256)+(256-k)}!!.key

fun main(args: Array<String>) {
    for (i in test) {
        val r = z(listOf(i.r, i.g, i.b))
        println("$i ${i.out} ==> $r")
    }
}

```

## TIO

TryItOnline
> 2 votes

# Answer
# Stax, 41 bytes

```
¬ÿ▒ú╘Σt∙Æ9φ☻ùí&BQq═IÜH∩Å╧♥f⌠óH]╨⌡≤@■Q‼Hr¼

```

Run and debug online!

ASCII version of 50 bytes:

```
"4GOW_g"{52-5*m3|^24{A*vv]3*m+{;\{E:-m|+mc|m|IH16+

```
> 2 votes

# Answer
# C (gcc), ~~202 192 157 150 (141 bugged) 138~~ 134 bytes

```
l,m,t,i;a(c,x){x=abs(c-=i>215?i*10-2152:x*40+!!x*55);}f(r,g,b){for(i=l=240;i--;t=a(r,i/36)+a(g,i/6%6)+a(b,i%6),t<l?l=t,m=i:1);i=m+16;}

```

Thanks @ceilingcat

Try it online!
> 1 votes

# Answer
## Batch, 266 bytes

```
@set/ax=15,m=999
@set s=for %%b in (0 95 135 175 215 255)do @
@%s:b=r%%s:b=g%%s%call:c %* %%r %%g %%b
@for /l %%g in (8,10,238)do @call:c %* %%g %%g %%g
@echo %n%
:c
@set/ax+=1,r=%4-%1,g=%5-%2,b=%6-%3
@set/ad=%r:-=%+%g:-=%+%b:-=%
@if %d% leq %m% set/an=x,m=d

```
> 1 votes

---
Tags: code-golf, color
---


title: Number of sums of factors

text:
# Question
Title: Number of sums of factors
Given a positive integer **n \> 1** determine how many numbers can be made by adding integers greater than 1 whose product is **n**. For example if **n = 24** we can express **n** as a product in the following ways

```
24 = 24             -> 24            = 24
24 = 12 * 2         -> 12 + 2        = 14
24 = 6 * 2 * 2      -> 6 + 2 + 2     = 10
24 = 6 * 4          -> 6 + 4         = 10
24 = 3 * 2 * 2 * 2  -> 3 + 2 + 2 + 2 = 9
24 = 3 * 4 * 2      -> 3 + 4 + 2     = 9
24 = 3 * 8          -> 3 + 8         = 11

```

We can get the following numbers this way:

```
24, 14, 11, 10, 9

```

That is a total of 5 numbers, so our result is 5.

# Task

Write a program or function that takes **n** as input and returns the number of results that can be obtained this way.

This is a question so answers will be scored in bytes, with fewer bytes being better.

## OEIS sequence

OEIS A069016

# Answer
# Brachylog, 8 bytes

```
{~×≜+}ᶜ¹

```

Try it online!

## Explanation

```
{    }ᶜ¹  Count unique results of this predicate:
 ~×       Create list of numbers whose product is the input.
   ≜      Label the list, forcing it to take a concrete value.
    +     Take its sum.

```

I'm not entirely sure why  only produces lists with elements above 1, but it seems to do so, which works great in this challenge.
> 6 votes

# Answer
# Gaia, ~~9~~ ~~14~~ 13 bytes

Bug fixed at the cost of 5 bytes thanks to Jonathan Allan, then 1 byte golfed.

```
ḍfḍ¦e¦Π¦¦Σ¦ul

```

Try it online! or try as a test suite

### Explanation

```
ḍ              Prime factors
 f             Permutations
  ḍ¦           Get the partitions of each permutation
    e¦         Dump each list of partitions (1-level flatten the list)
      Π¦¦      Product of each partition
         Σ¦    Sum each group of products
           u   Deduplicate
            l  Length

```
> 4 votes

# Answer
# Jelly,  ~~11 15~~  14 bytes

+4 bytes fixing up a bug (maybe a better way?)
-1 byte by abusing symmetry

```
ÆfŒ!ŒṖ€ẎP€S€QL

```

A monadic link taking and returning positive integers

**Try it online!** or see a test suite

### How?

*Updating...*

```
ÆfŒ!ŒṖ€ẎP€S€QL - Link: number, n      e.g. 30
Æf             - prime factors of n        [2,3,5]
  Œ!           - all permutations          [[2,3,5],[2,5,3],[3,2,5],[3,5,2],[5,2,3],[5,3,2]]
    ŒṖ€        - all partitions for €ach   [[[[2],[3],[5]],[[2],[3,5]],[[2,3],[5]],[[2,3,5]]],[[[2],[5],[3]],[[2],[5,3]],[[2,5],[3]],[[2,5,3]]],[[[3],[2],[5]],[[3],[2,5]],[[3,2],[5]],[[3,2,5]]],[[[3],[5],[2]],[[3],[5,2]],[[3,5],[2]],[[3,5,2]]],[[[5],[2],[3]],[[5],[2,3]],[[5,2],[3]],[[5,2,3]]],[[[5],[3],[2]],[[5],[3,2]],[[5,3],[2]],[[5,3,2]]]]
       Ẏ       - tighten                   [[[2],[3],[5]],[[2],[3,5]],[[2,3],[5]],[[2,3,5]],[[2],[5],[3]],[[2],[5,3]],[[2,5],[3]],[[2,5,3]],[[3],[2],[5]],[[3],[2,5]],[[3,2],[5]],[[3,2,5]],[[3],[5],[2]],[[3],[5,2]],[[3,5],[2]],[[3,5,2]],[[5],[2],[3]],[[5],[2,3]],[[5,2],[3]],[[5,2,3]],[[5],[3],[2]],[[5],[3,2]],[[5,3],[2]],[[5,3,2]]]
        P€     - product for €ach          [[30],[6,5],[10,3],[2,3,5],[30],[10,3],[6,5],[2,5,3],[30],[6,5],[15,2],[3,2,5],[30],[15,2],[6,5],[3,5,2],[30],[10,3],[15,2],[5,2,3],[30],[15,2],[10,3],[5,3,2]]
               -   ...this abuses the symmetry saving a byte over P€€
          S€   - sum €ach                  [30,11,13,10,30,13,11,10,30,11,17,10,30,17,11,10,30,13,17,10,30,17,13,10][10,17,11,30,10,17,13,30,10,13,11,30,10,13,17,30,10,11,13,30,10,11,17,30]
            Q  - de-duplicate              [30,11,13,10,17]
             L - length                    5

```
> 2 votes

# Answer
# Python 2, 206 bytes

```
k=lambda n,i=2:n/i*[k]and[k(n,i+1),[i]+k(n/i)][n%i<1]
def l(t):
 r=[sum(t)]
 for i,a in enumerate(t):
    for j in range(i+1,len(t)):r+=l(t[:i]+[a*t[j]]+t[i+1:j]+t[j+1:])
 return r
u=lambda n:len(set(l(k(n))))

```

Try it online!

## Explanation

```
    # Finds the prime factors
k=lambda n,i=2:n/i*[k]and[k(n,i+1),[i]+k(n/i)][n%i<1]
    # Function for finding all possible numbers with some repetition
def l(t):
    # Add the current sum
 r=[sum(t)]
    # For each number in the current factors
 for i,a in enumerate(t):
    # For all numbers further back in the current factors, find all possible numbers when we multiply together two of the factors
    for j in range(i+1,len(t)):r+=l(t[:i]+[a*t[j]]+t[i+1:j]+t[j+1:])
 return r
    # Length of set for distinct elements
u=lambda n:len(set(l(k(n))))

```
> 1 votes

# Answer
# Python 3, 251 bytes

```
lambda n:1 if n==1else len(set(sum(z)for z in t(f(n))))
f=lambda n:[]if n==1else[[i]+f(n//i)for i in range(2,n+1)if n%i==0][0]
t=lambda l:[l] if len(l)==1else[[l[0]]+r for r in t(l[1:])]+[r[:i]+[l[0]*e]+r[i+1:]for r in t(l[1:])for i,e in enumerate(r)]

```

Try it online!

The design is basic:

1. factorize n into its prime factors (a prime factor may appear several times : `16 -> [2,2,2,2]`). That's the function `f`.
2. compute the partitions of the list of prime factors, and multiply the factors in each partition. The partitions are found as in https://stackoverflow.com/a/30134039, and the products are computed on the fly. That's the function `t`.
3. The final function gets the products of each partition of n and sums them, the get the number of different values.

The result for `2310=2*3*5*7*11` is `49`.

**EDIT** : Maybe needs fix, but I don't have time to look at it now (I'm in a hurry). Hint: is the result correct for `2310=2*3*5*7*11` ? I dont' think so.

**EDIT2** : Huge fix. See above. Previous (buggy) version was: Try it online!

`f` computes the factors (, with a `(0, n)` instead of `(1, n)` as first element.

The lambda splits each factor in "sub-factors" and sums the those "sub-factors".
> 1 votes

# Answer
# Mathematica, 110 bytes

```
If[#==1,1,Length@Union[Tr/@Select[Array[f~Tuples~{#}&,Length[f=Rest@Divisors[s=#]]]~Flatten~1,Times@@#==s&]]]&

```
> 1 votes

# Answer
# JavaScript (ES6) 107 bytes

```
f=(n,o,s=0,i=2,q=n/i)=>(o||(o={},o[n]=t=1),i<n?(q>(q|0)|o[e=s+i+q]||(o[e]=t+=1),f(q,o,s+i),f(n,o,s,i+1)):t)

```

**Ungolfed:**

```
f=(n,                                 //input
   o,                                 //object to hold sums
   s=0,                               //sum accumulator
   i=2,                               //start with 2
   q=n/i                              //quotient
  )=>(
  o||(o={},o[n]=t=1),                 //if first call to function, initialize o[n]
                                      //t holds the number of unique sums
  i<n?(                               //we divide n by all numbers between 2 and n-1
    q>(q|0)|o[e=s+i+q]||(o[e]=t+=1),  //if q is integer and o[s+i+q] is uninitialized,
                                      //... make o[s+i+q] truthy and increment t
    f(q,o,s+i),                       //recurse using q and s+i
    f(n,o,s,i+1)                      //recurse using n with the next i
  ):t                                 //return t
)

```

**Test cases:**

```
f=(n,o,s=0,i=2,q=n/i)=>(o||(o={},o[n]=t=1),i<n?(q>(q|0)|o[e=s+i+q]||(o[e]=t+=1),f(q,o,s+i),f(n,o,s,i+1)):t)

s= [];

for(i = 1; i <= 103 ; i++) {
  s.push(f(i));
}

console.log(s.join`, `)
```

To verify that the function calculates the correct sums, we can output the keys of the object instead of `t`:

```
f=(n,o,s=0,i=2,q=n/i)=>(o||(o={},o[n]=t=1),i<n?(q>(q|0)|o[e=s+i+q]||(o[e]=t+=1),f(q,o,s+i),f(n,o,s,i+1)):Object.keys(o))

console.log(f(24));  //9, 10, 11, 14, 24
```
> 1 votes

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


title: Crazy but Rational Bases

text:
# Question
Title: Crazy but Rational Bases
We have many challenges based on base 10, base 2, base 36, or even base -10, but what about all the other rational bases?

# Task

Given an integer in base 10 and a rational base, return the integer in that base (as an array, string, etc.).

# Process

It's difficult to imagine a rational base, so let's visualize it using Exploding Dots:

Consider this animation, expressing 17 in base 3:

Each dot represents a unit, and boxes represent digits: the rightmost box is the one's place, the middle box is the 3^1 place, and the leftmost box is the 3^2 place.

We can begin with 17 dots at the one's place. However, this is base 3, so the ones place has to be less than 3. Therefore, we "explode" 3 dots and create a dot on the box to the left. We repeat this until we end up with a stable position with no explodable dots (i.e. 3 dots in the same box).

So 17 in base 10 is 122 in base 3.

---

A fractional base is analogous to exploding some number of dots to more than one dots. Base 3/2 would be exploding 3 dots to create 2.

Expressing 17 in base 3/2:

So 17 in base 10 is 21012 in base 3/2.

---

Negative bases work similarly, but we must keep track of signs (using so-called anti-dots, equal to -1; represented by an open circle).

Expressing 17 in base -3:

**Note, there are extra explosions to make the sign of all the boxes the same (ignoring zeros).**

Thus, 17 in base 10 is 212 in base -3.

Negative rational bases work similarly, in a combination of the above two cases.

# Rules

* No standard loopholes.
* The sign of each "digit" in the output must be the same (or zero).
* The absolute value of all digits must be less than the absolute value of the numerator of the base.
* You may assume that the absolute value of the base is greater than 1.
* You may assume that a rational base is in its lowest reduced form.
* You may take the numerator and the denominator of the base separately in the input.
* If a number has multiple representations, you may output any one of them. (e.g. 12 in base 10 can be `{-2, -8}` and `{1, 9, 2}` in base -10)

# Test cases:

Format: `{in, base} -> result`

```
{7, 4/3}        ->  {3, 3}
{-42, -2}       ->  {1, 0, 1, 0, 1, 0}
{-112, -7/3}    ->  {-6, -5, 0, -1, 0}
{1234, 9/2}     ->  {2, 3, 6, 4, 1}
{60043, -37/3}  ->  {-33, -14, -22, -8}

```

Since some inputs may have multiple representations, I recommend testing the output using this Mathematica snippet on TIO.

This is , so submissions with shortest byte counts in each language win!

---

For more information on exploding dots, visit the global math project website! They have a bunch of cool mathy stuff!

# Answer
> 6 votes
# Python 2, 42 39 bytes

```
n,a,b=input()
while n:print n%a;n=n/a*b

```

Try it online!

Thanks to @xnor for finding the shorter form.

Obsolete version (42 bytes):

```
f=lambda n,a,b:n and[n%a]+f(n/a*b,a,b)or[]

```

Try it online!

Parameters: input, numerator (with sign) and denominator.

Returns an array, lowest digit first.

This just works because the division and modulo in Python follows the sign of the denominator, so we don't have to care about same signs explicitly.

Test case output:

```
f(7, 4, 3)       == [3, 3]
f(-42, -2, 1)    == [0, -1, -1, -1, -1, -1, -1]
f(-112, -7, 3)   == [0, -1, 0, -5, -6]
f(1234, 9, 2)    == [1, 4, 6, 3, 2]
f(60043, -37, 3) == [-8, -22, -14, -33]

```

# Answer
> 4 votes
# Aheui (esotope), 91 bytes

```
벙수벙섞벙석
희빠챠쌳뻐삭빠빠싻싸삯라망밣밭따맣사나삮빠싸사땨

```

Try it online!

Takes `integer`, `numerator of base`, and `denominator of base`.

Due to the limitation of the TIO interpreter, each input must end with a newline.

Implementation of @Bubbler's Python 2 answer. Luckily, this Aheui interpreter is written in Python, so we can use the same trick.

# Answer
> 3 votes
# 05AB1E, ~~11~~ 10 bytes

```
[D_#²‰`,³*

```

Try it online!

Takes `integer`, `numerator of base` and `denominator of base` like all answers. Since 05AB1E interpreter is written in Python(?), Bubbler's Python 2 answer trick can be used in 05AB1E too.

**Explanation**

```
[D_#²‰`,³*
[                                        Infinite Loop
 D_#                                     If the number is 0, exit loop (implicit input
                                         in the first iteration)
     ²                                   Get the numerator of base
      ‰                                  Divmod
       `                                 Push all elements into the stack
        ,                                Print the remainder
         ³                               Get the denominator of base
          *                              Multiply it.

```

So the program works roughly the same as this Python code:

```
i1, i2, i3 = input()
stack = []
while 1:
 stack = (stack or [i1])
 stack += [stack[-1]]
 if not stack[-1]: break
 stack += [i2]
 stack = stack[:-2] + [divmod(stack[-2], stack[-1])]
 stack = stack[:-1] + list(stack[-1])
 print stack[-1]
 stack = stack[:-1]
 stack += [i3]
 stack = stack[:-2] + [stack[-2] * stack[-1]]

```

11 \> 10 Thanks Neil

---
Tags: code-golf, number-theory, integer, base-conversion
---


title: Generate a special period image

text:
# Question
Title: Generate a special period image
Construct a program or function that takes input in form of

```
<width>, <height>, <color1>, <color2>

```

and generates an output such that first row alternates between pixels of color `<color1>` and `<color2>` with a period of `<height>`. For each row that follows, the period shall be `<height> - <row number>`. Note that `<color1>` always begins the row.

### Sample Output

Input `120, 6, #000000, #FFFF00`:

Input `80, 50, #000000, #FFFF00`:

(Sample output has been scaled for clarity)

This is , so the shortest valid entry in bytes wins.

# Answer
## JavaScript (ES6), 177 bytes

```
g=
(w,h,f,b)=>`<svg${s=` width=${w} height=`+h}><rect${s} fill=${b} />`+[...Array(h)].map((_,i)=>`<line stroke=${f} stroke-dasharray=${h-i} x1=0 y1=${i} x2=${w} y2=${i} />`).join``
```

```
Width: <input id=w value=80 type=number min=1><br>Height: <input id=h value=50 type=number min=1><br>Foreground: <input id=f value=#000000><br>Background: <input id=b value=#FFFF00><br><input type=button value=Go! onclick=o.innerHTML=g(+w.value,+h.value,f.value,b.value)><div id=o>
```

Outputs an HTML5-compatibile SVG image.
> 6 votes

# Answer
# Tcl/Tk, 143

# ~~147~~ ~~150~~ ~~151~~

```
proc P {w h b c} {set p [image c photo -w $w -h $h]
time {incr y
set x 0
time {$p p -t $x $y [expr {[incr x]/($h-$y+1)%2?$c:$b}]} $w} $h
set p}

```

Returns the image which can be tested, by putting it on a `canvas` widget, writing on a file, may be on the clipboard, etc.

# Code for testing

```
set w 960
set h 540
pack [canvas .c -w $w -he $h -highlightt 0]
.c cr image 0 0 -image [P $w $h #00ffff #ffbf32] -anchor nw

```
> 5 votes

# Answer
# Excel VBA, ~~129~~ 122 Bytes

Anonymous VBE immediate window function that takes input from range `[A1:D1]` and outputs to the range `[A2].Resize([B1],[A1])`

```
Cells.RowHeight=48:For Each r in[Offset(A2,,,B1,A1)]:r.Interior.Color=IIf((r.Column-1)\([B1]-R.Row+2)Mod 2,[D1],[C1]):Next

```

## Far More Interesting Version, 160 bytes

Presented w/ newlines in place of `:` characters for readability

In this version the snippet `[Let(r,Offset(A1,,,B1,A1),If(IsOdd((Column(r)-1)/(B1-Row(r)+2)),C1,D1))]` alone is able to calculate the array of values, and all other code is used to output this array as colors to the range `[Offset(A1,,,B1,A1)]`.

```
Cells.RowHeight=48
[Offset(A2,,,B1,A1)]=[Let(r,Offset(A2,,,B1,A1),If(IsOdd((Column(r)-1)/(B1-Row(r)+2)),C1,D1))]
For Each r In Cells
r.Interior.Color=r
r="
Next

```

Perhaps this approach my prove fruitful for further improvement?

## Output

Output for input `160, 90, 0xBDD7EE, 0xDDEBF7`:
> 4 votes

# Answer
# Mathematica, 52 bytes

```
Image@Table[If[Mod[j,2i]>i,#4,#3],{i,-#2,-1},{j,#}]&

```

Sample input:

```
Image@Table[If[Mod[j,2i]>i,#4,#3],{i,-#2,-1},{j,#}]&[120,6,Black,Yellow]

```
> 3 votes

# Answer
# C (gcc), ~~155~~ 143 bytes

Prints a Portable PixMap (.ppm) to stdout.

```
x,y,z;f(w,h,r,g,b,R,G,B){for(y=~0,printf("P3 %d %d 255",w,h);y++<~-h;)for(x=~0;x++<~-w;)z=(x/(h-y)%2),printf("\n%d %d %d ",z?R:r,z?G:g,z?B:b);}

```

Try it online!

### Output

* Input: `80, 50, #ad00df, #f17e18`

*(Image converted and resized.)*
> 3 votes

# Answer
# MATL, ~~34~~ ~~32~~ 29 bytes

-3 bytes thanks to Luis Mendo

```
XJx:P"1Hh@Y"1Jyn/XkX"J:)]viYG

```

Try it at MATL Online
> 2 votes

# Answer
# Java 8, 321 + 42 = 363 bytes

```
import java.awt.*;import java.awt.image.*;
(w,h,a,b)->{BufferedImage i=new BufferedImage(w,h,1);Graphics2D g=(Graphics2D)i.getGraphics();g.setColor(new Color(a));g.fillRect(0,0,w,h);g.setColor(new Color(b));for(int j=h;j>0;g.drawLine(0,h-j,w,h-j--))g.setStroke(new BasicStroke(1,0,0,1,new float[]{j},j));javax.imageio.ImageIO.write(i,"png",new java.io.File("a"));}

```

Outputs to a PNG file named `a` (no extension).

Surrounding code used to run the lambda: Try it online!

## Ungolfed

```
(w,h,a,b)->{
    BufferedImage i=new BufferedImage(w,h,1);
    Graphics2D g=(Graphics2D)i.getGraphics();
    g.setColor(new Color(a));
    g.fillRect(0,0,w,h);
    g.setColor(new Color(b));
    for(int j=h;j>0;g.drawLine(0,h-j,w,h-j--))
        g.setStroke(new BasicStroke(1,0,0,1,new float[]{j},j));
    javax.imageio.ImageIO.write(i,"png",new java.io.File("a"));
}

```

## Result

Inputs: `80, 50, 0xFF00FF, 0xFFFF00`.
> 1 votes

# Answer
# SOGL V0.12, 83 bytes

```
..¹Cbe¹"εģνļ▲I-℮eīÆoHι⅛ļJd⁾)⁶f°┌²‘→e∫Ab∫Ƨ01a∙H∑bmWrcwιFHea-¹"S⁸▒Μ¬NrηA¤Y_⅓ļpPboā⁵‘→

```

Try it Here!

SOGL was made in Processing.. So I took advantage of that using  \- execute as JavaScript. Could easily be many bytes less (at least 30) if SOGL had *anything* made for graphics.

Uncompressed strings:

```
..¹Cbe¹"__processing0.hidden=0;cp.size(ŗ,ŗ)”→e∫Ab∫Ƨ01a∙H∑bmWrcwιFHea-¹"cp.stroke(ŗ);cp.point(ŗ,ŗ)”→

```

Explanation:

```
..¹C       save the first 2 inputs as an array on variable C
be¹        save next input - width - on B, next input - height - on E, and wrap both in an array
"__processing0.hidden=0;cp.size(ŗ,ŗ)”→
           execute "__processing0.hidden=0;cp.size(ŗ,ŗ)" as JavaScript - show the canvas and set the size to the corresponding items in the array

e∫A        repeat height times, saving 1-indexed counter on A
  b∫       repeat width times, pushing 1-indexed counter
    Ƨ01    push "01"
    a∙     multiply vertically A times             - ["01", "01", "01",...]
    H      rotate anticlockwise                    - ["000...","111..."]
    ∑      join together                           - "000..111.."
    bm     mold to the length of width             - "00011100011100"
    W      get the counterth letter of that string - "1"
    r      convert to number                       - 1
    cw     get that item from the variable C
    ι      remove the array from the stack
    FH     push current loops counter minus 1
    ea-    push e-a - height-outerLoopsCounter
    ¹      wrap the 3 items in an array - [itemInC (color), counter-1 (x position), height-outerLoopsCounter (y position)]

    "cp.stroke(ŗ);cp.point(ŗ,ŗ)”→
           execute "cp.stroke(ŗ);cp.point(ŗ,ŗ)" as JavaScript, replacing ŗ with the corresponding item from the array

```
> 1 votes

# Answer
# SmileBASIC, 84 bytes

```
DEF C W,H,C,D
FOR J=1TO H
FOR I=0TO W-1N=1AND I/J
GPSET I,H-J,C*!N+D*N
NEXT
NEXT
END

```

The color of a pixel at `(x,height-y)` is `[color1,color2][x/y & 1]`
> 1 votes

# Answer
# Python 2, ~~123~~ 101 bytes

```
w,h,c,C=input()
print'P3',w,h,255
for i in range(h):
 for j in range(w):print`[c,C][j/(h-i)%2]`[1:-1]

```

Try it online!

Prints a .ppm to output as in Jonathan's answer.
> 0 votes

# Answer
# JavaScript (ES6) + HTML5, 138 bytes

```
(w,h,a,b)=>{with(c.width=w,c.getContext`2d`)for(c.height=y=h;~--y;)for(x=w;~--x;)fillStyle=x/(h-y)%2<1?a:b,fillRect(x,y,1,1)}

```

```
<canvas id=c>

```

```
f=
(w,h,a,b)=>{with(c.width=w,c.getContext`2d`)for(c.height=y=h;~--y;)for(x=w;~--x;)fillStyle=x/(h-y)%2<1?a:b,fillRect(x,y,1,1)}
```

```
#c{display:block
```

```
<input id=w value=80>
<input id=h value=50>
<input id=a value=#000>
<input id=b value=#FF0>
<input value=go type=button onclick=f(w.value,h.value,a.value,b.value)>
<canvas id=c>
```

The function outputs by operating on the `<canvas id=c>`.

Starting from the bottom right of the canvas, the nested `for` loop iterates to the left and up, and checks the condition `x/(h-y)%2<1` for the pixel at `x,y`. If the condition is `true`, it colors that pixel with `color1`, else `color2`.
> 0 votes

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


title: Compress to Impress

text:
# Question
Title: Compress to Impress
Inspired by both the challenge "Unique is Cheap" by *@Laikoni*, where the score is based on the challenge itself, as well as the JavaScript (ES6) answer of *@ETHproductions* for the "Palindrome Compression" challenge, where he uses a pretty cool compression method for the palindrome-flag, upper/lower case indication, and letters.

# Challenge:

You will create two programs/function: a compress program/function, and a decompress program/function.

### Compress program/function:

Given the characters used in your own source code (both the compress and decompress source code combined) as only possible input, use any kind of bit-compression method of your choice and output the resulting `0`s and `1`s of the bit-compression of this input.

The amount of bits (`0`s and `1`s) outputted must be as short as possible, and **this amount will be the score of your answer**.

The idea is to have a nice balance between the different kind of characters used in your own source code, the size of your programs/functions, and the type of bit-compression you've used. Or to quote *@RobertFraser* in this comment:

> This is a great example of the fundamentals of engineering. Taking a problem description, thinking about different ways to solve it, and making tradeoffs between requirements (ie how many bits to dedicate to various styles), etc

## Challenge rules:

* The compressor and decompressor program/function should be in the same programming language.
* You must provide both a compression and decompression program/function, and the amount of `0`s and `1`s your compression program outputs for both programs/functions combined (concatted) as input will be your score.
* The compression must - obviously - work for all characters used in your source code of both your compression and decompression program/function, in any order or amount. (It can have undefined behavior for any characters not in your source code.)
* Input-type doesn't necessarily have to be a string. It could also be a list/array/stream of characters, and it can be as program argument, STDIN, etc. Your call.
Same applies to the output. Can be returned from a function or printed to STDOUT. Can be a single string, integer-array, etc.
* Your compression program must output at least one `0` or `1` (so an empty `cat` program for both the compression and decompression program isn't possible).
* Your source code may not only contain `0`s and `1`s already, excluding no-ops (to prevent programming languages that print their own source code by default, where both the compression and decompression programs can be a single `0` or `1`, and the no-ops part is to prevent this behavior with an unused comment; sorry binary-based programming languages which only use `0`s and `1`s as source code).
* Although you'll have to support an input of 0 or more of the character-pool used in your programs/functions, you don't have to support an empty input. So you can assume every input will be at least 1 character.
* A possible input can be larger than your compression and decompression sizes combined.
* If for whatever reason your compression method is order-depended and has a shorter output when your input is `DecompressionProgramCompressionProgram` instead of `CompressionProgramDecompressionProgram`, you are allowed to choose either order of concatting of your programs/function for your score.

## Example:

Let's say the compression program is `ABC`, and the decompression program is `123aBc`. For any input containing zero or more of the character-pool `123ABCab`, it should be able to correctly compress those characters to `0`s and `1`s, and be able to decompress these `0`s and `1`s back into the correct characters. Some valid example inputs for these two programs can be: `ABC123aBc` (of course); `A`; `1Ca`; `22222b1121221b`; etc.

## General rules:

* Standard rules apply for your answer, so you are allowed to use STDIN/STDOUT, functions/method with the proper parameters, full programs. Your call.
* Default Loopholes are forbidden.
* If possible, please add a link with a test for your code.
* Also, please add an explanation if necessary.

## Example of an answer:

> # Java 8, score 1440 bits, 180 (87 + 93) bytes
>
> Here a very bad implementation in Java 8, where each character is simply printed as 8-bit binary String.
>
> **Compression function:**
>
> Input provided as `java.util.stream.IntStream`.
>
> ```
> s->s.forEach(c->System.out.print("".format("%8s",Long.toString(c,2)).replace(' ','0')))
>
> ```
>
> Try it online.
>
> **Decompression function:**
>
> Input provided as `String`.
>
> ```
> s->{for(Integer i=0;i<s.length();System.out.printf("%c",i.parseInt(s.substring(i,i+=8),2)));}
>
> ```
>
> Try it online.

# Answer
> 2 votes
# Jelly, score 350, 39 + 30 = 69 bytes

# Compressor: Jelly, 39 bytes

```
“iÐ€;⁴⁾¤8Bz0ZUṖFs5Ḅị”;⁾“”¤iÐ€;⁴BUz0ZUṖF

```

Try it online!

# Decompressor: Jelly, 30 bytes

```
s5Ḅị“iÐ€;⁴⁾¤8Bz0ZUṖFs5Ḅị”;⁾“”¤

```

Try it online!

# Answer
> 2 votes
# Java (OpenJDK 9), score 702 bits, 88 (42 + 46) bytes

## Compressor, 42 bytes

```
$->new java.math.BigInteger($).toString(2)

```

Try it online!

## Decompressor, 46 bytes

```
$->new java.math.BigInteger($,2).toByteArray()

```

Try it online!

# Answer
> 0 votes
# Pyt, score 179 bits, 9+10=19 bytes

Compressor:

```
←6!58*-Ĩɓ

```

Try it online!

Decompressor:

```
←2Ĩ6!58*-Ṕ

```

Try it online!

---
Tags: string, code-challenge, binary, compression, encoding
---


title: Tips for golfing in Logo

text:
# Question
Title: Tips for golfing in Logo
Logo is a programming language that was designed back in 1967 that has great potential for creating graphics in relatively few bytes compared to other languages.

Logo is an educational programming language that utilizes Turtle Graphics.

There are multiple interesting implementations of Logo including:

In addition, multiple Logo interpreters can be found online.

This page is intended to be a hub for code golf regarding any implementation of the Logo programming language.

Source: The Great Logo Adventure (1998) by Jim Muller

# Answer
# LibreLogo

**Shorten Color Definitions:**

It is documented that colors can be defined by name, identifier, RGB value, or HEX code.

In the majority of cases, if you have the opportunity to use an identifier for a color constant, that is typically the shortest option.

On the other hand, a little known fact is that you can also use the decimal value to define a color, and you can occasionally save bytes.

**Color Chart:**

```
+------------------------------------------------------------------------+   +-------------+
| Name                | Identifier | RGB           | HEX      | Decimal  |   | Best Option |
|------------------------------------------------------------------------|   |-------------|
| "BLACK"             | [0]        | [0,0,0]       | 0x000000 | 0        |   | 0           |
| "SILVER"            | [1]        | [192,192,192] | 0xc0c0c0 | 12632256 |   | [1]         |
| "GRAY"/"GREY"       | [2]        | [128,128,128] | 0x808080 | 8421504  |   | [2]         |
| "WHITE"             | [3]        | [255,255,255] | 0xffffff | 16777215 |   | [3]         |
| "MAROON"            | [4]        | [128,0,0]     | 0x800000 | 8388608  |   | [4]         |
| "RED"               | [5]        | [255,0,0]     | 0xff0000 | 16711680 |   | [5]         |
| "PURPLE"            | [6]        | [128,0,128]   | 0x800080 | 8388736  |   | [6]         |
| "FUCHSIA"/"MAGENTA" | [7]        | [255,0,255]   | 0xff00ff | 16711935 |   | [7]         |
| "GREEN"             | [8]        | [0,128,0]     | 0x008000 | 32768    |   | [8]         |
| "LIME"              | [9]        | [0,255,0]     | 0x00ff00 | 65280    |   | [9]         |
| "OLIVE"             | [10]       | [128,128,0]   | 0x808000 | 8421376  |   | [10]        |
| "YELLOW"            | [11]       | [255,255,0]   | 0xffff00 | 16776960 |   | [11]        |
| "NAVY"              | [12]       | [0,0,128]     | 0x000080 | 128      |   | 128         |
| "BLUE"              | [13]       | [0,0,255]     | 0x0000ff | 255      |   | 255         |
| "TEAL"              | [14]       | [0,128,128]   | 0x008080 | 32896    |   | [14]        |
| "AQUA"              | [15]       | [0,255,255]   | 0x00ffff | 65535    |   | [15]        |
| "PINK"              | [16]       | [255,192,203] | 0xffc0cb | 16761035 |   | [16]        |
| "TOMATO"            | [17]       | [255,99,71]   | 0xff6347 | 16737095 |   | [17]        |
| "ORANGE"            | [18]       | [255,165,0]   | 0xffa500 | 16753920 |   | [18]        |
| "GOLD"              | [19]       | [255,215,0]   | 0xffd700 | 16766720 |   | [19]        |
| "VIOLET"            | [20]       | [148,0,211]   | 0x9400d3 | 9699539  |   | [20]        |
| "SKYBLUE"           | [21]       | [135,206,235] | 0x87ceeb | 8900331  |   | [21]        |
| "CHOCOLATE"         | [22]       | [210,105,30]  | 0xd2691e | 13789470 |   | [22]        |
| "BROWN"             | [23]       | [165,42,42]   | 0xa52a2a | 10824234 |   | [23]        |
| "INVISIBLE"         | [24]       | N/A           | N/A      | N/A      |   | [24]        |
+------------------------------------------------------------------------+   +-------------+

```
> 3 votes

# Answer
# LibreLogo

**Use Abbreviated Commands:**

Abbreviated commands, also called "short names," are used across most implementations of Logo.

Here is the full list of abbreviated commands for LibreLogo.

```
+-----------------------------------------------+
| Full Command    | Short Command | Bytes Saved |
|-----------------------------------------------|
| forward 10      | fd 10         | 5           |
| back 10         | bk 10         | 2           |
| left 90         | lt 90         | 2           |
| right 90        | rt 90         | 3           |
| penup           | pu            | 3           |
| pendown         | pd            | 5           |
| position 0      | pos 0         | 5           |
| heading 0       | seth 0        | 3           |
| hideturtle      | ht            | 8           |
| showturtle      | st            | 8           |
| clearscreen     | cs            | 9           |
| pensize 10      | ps 10         | 5           |
| pencolor 0      | pc 0          | 6           |
| fillcolor 0     | fc 0          | 7           |
| picture [ ... ] | pic [ ... ]   | 4           |
+-----------------------------------------------+

```
> 2 votes

# Answer
# LibreLogo

**Random Numbers:**

Use `any` instead of `random` when possible.

*Random Integer (0 - 9):*

```
x = int random 10     ; 17 bytes
x = int(ps any)       ; 15 bytes

```

*Random Floating-Point Number (0 - 9):*

```
x = random 10         ; 13 bytes
x = (ps any)          ; 12 bytes

```

*Directly Assigned to Setting:*

```
pensize random 10     ; 17 bytes
ps random 10          ; 12 bytes
ps any                ; 6 bytes

```
> 0 votes

# Answer
# LibreLogo

**Use `PAGESIZE` to your Advantage:**

> `PAGESIZE` is a variable that is dependent on the Paper Format in LibreOffice Writer and returns an array containing the `[width, height]` of the page in points (`pt`).

This could be useful for a variety of situations, but I personally found it useful for generating a number without using the digits `[0-9]`.

https://help.libreoffice.org/Writer/LibreLogo\_Toolbar#PAGESIZE

---

**Value Chart:**

```
+-------------------------------------------------------------------+
| Paper Format           | PAGESIZE                                 |
|-------------------------------------------------------------------|
| A6                     | [297.35433070866145, 419.75433070866137] |
| A5                     | [419.75433070866137, 595.4456692913386]  |
| A4                     | [595.4456692913386, 841.6913385826772]   |
| A3                     | [841.6913385826772, 1190.8913385826772]  |
| B6 (ISO)               | [354.2456692913386, 498.95433070866136]  |
| B5 (ISO)               | [498.95433070866136, 708.4913385826771]  |
| B4 (ISO)               | [708.4913385826771, 1000.8]              |
| Letter                 | [612.0, 792.0]                           |
| Legal                  | [612.0, 1008.0]                          |
| Long Bond              | [612.0, 936.0]                           |
| Tabloid                | [792.0, 1224.0]                          |
| B6 (JIS)               | [362.8913385826771, 516.2456692913386]   |
| B5 (JIS)               | [516.2456692913386, 728.6456692913387]   |
| B4 (JIS)               | [728.6456692913387, 1031.7543307086614]  |
| 16 Kai                 | [521.2913385826771, 737.2913385826771]   |
| 32 Kai                 | [368.64566929133855, 521.2913385826771]  |
| Big 32 Kai             | [396.7086614173228, 575.2913385826771]   |
| User                   | CURRENT PAGE SIZE                        | ← Current Paper Format
| DL Envelope            | [311.7543307086614, 623.5086614173229]   |
| C6 Envelope            | [323.29133858267716, 459.3543307086614]  |
| C6/5 Envelope          | [323.29133858267716, 649.4456692913386]  |
| C5 Envelope            | [459.3543307086614, 649.4456692913386]   |
| C4 Envelope            | [649.4456692913386, 918.7086614173228]   |
| #6¾ Envelope           | [261.35433070866145, 468.0]              |
| #7¾ (Monarch) Envelope | [279.35433070866145, 540.0]              |
| #9 Envelope            | [279.35433070866145, 639.3543307086613]  |
| #10 Envelope           | [297.35433070866145, 684.0]              |
| #11 Envelope           | [324.0, 747.3543307086613]               |
| #12 Envelope           | [342.0, 792.0]                           |
| Japanese Postcard      | [283.69133858267713, 419.75433070866137] |
+-------------------------------------------------------------------+

```
> 0 votes

---
Tags: code-golf, tips
---


title: Sparse Protractor

text:
# Question
Title: Sparse Protractor
Given some positive integer `n`, design a protractor with the fewest number of marks that lets you measure all angles that are an integral multiple of `2π/n` (each in a single measurement).

### Details

As an output, you may output a list of integers in the range `0` to `n-1` (or `1` to `n`) that represent the position of each mark. Alternatively you can output a string/list of length `n` with a `#` at the position of each mark and a `_` (underscore) where there is none. (Or two different characters if more convenient.)
**Example:** For `n = 5` you need exactly 3 marks to be able to measure all angles `2π/5, 4π/5, 6π/5, 8π/5, 2π` by setting (for example) one mark at `0`, one mark at `2π/5` and one mark at `6π/5`. We can encode this as a list `[0,1,3]` or as a string `##_#_`.

### Examples

Note that the outputs are not necessarily unique.

```
n:  output:
 1  [0]
 2  [0,1]
 3  [0,1]
 4  [0,1,2]
 5  [0,1,2]
 6  [0,1,3]
 7  [0,1,3]
 8  [0,1,2,4]
 9  [0,1,3,4]
10  [0,1,3,6]
11  [0,1,3,8]
20  [0,1,2,3,6,10]

```

PS: This is similar to the sparse ruler problem, but instead of a linear scale (with two ends) we consider a circular (angular) scale.

PPS: This script should compute one example of a set of marks for each `n`. Try it online!

PPPS: As @ngn pointed out, this problem is equivalent to finding a minimal difference base of a cyclic group of order `n`. The minimal orders are listed in http://oeis.org/A283297 and some theoretical bounds are found in https://arxiv.org/pdf/1702.02631.pdf

# Answer
# MATL, 20 bytes

```
:qGZ^!"G:q@&-G\m?@u.

```

This runs out of memory on TIO for inputs beyond `8`.

Try it online!

### How it works

This generates the Cartesian power of `[0 1 ... n-1]` with exponent `n`, and uses a loop to test each Cartesian tuple. The test consists in computing all pairwise differences of element if the tuple, and seeing if those differences modulo `n` include *all* numbers `0`, `1`, ..., `n-1`.

As soon as a Cartesian tuple fulfilling the condition is found the loop is exited, and the *unique* entries in that tuple are printed as the solution.

This works because given ***u*** \> ***v***, a *sufficient set* of tuples with ***u*** *unique* entries are guaranteed to be tested *earlier* than any tuple with ***v*** unique entries. A "sufficient set" means that if none of the tuples in that set are a solution then no other tuple with the same number of unique entries is a solution.

For example, for `n = 3` the Cartesian tuples are as shown below, where each row is a tuple:

```
0 0 0
0 0 1
0 0 2
0 1 0
0 1 1
0 1 2
0 2 0
 ···
2 2 1
2 2 2

```
* The first tuple, `0 0 0`, is the only relevant tuple with `1` unique value. Even if `1 1 1` and `2 2 2` will appear much later, `0 0 0` is a solution if and only if those are. So the singleton set formed by the tuple `0 0 0` is a sufficient set for ***u*** = `1`.
* The second and third tuples, namely `0 0 1`and `0 0 2`, form a sufficient set for ***u*** = `2`; that is, they cover all cases with `2` unique values. The fourth tuple, `0 1 0`, will never be selected as solution, because `0 0 1` will have been tested first. Similarly, the tuple `0 2 0` will never be selected because it appears later than `0 0 2`. Tuples such as `2 2 1` will never be selected as solution because the `0 0 1` is equivalent (modulo `n` and up to duplicated values) and appears first.
* Etc.

Commented code:

```
:q         % Push [0 1 ... n-1], where n is the input (implicit)
GZ^        % Cartesian power with exponent n. Gives an (n^n) × n matrix
           % where each row is a Cartesian tuple
!          % Transpose. Now each Cartesian tuple is a column
!"         % For each column (that is, each Cartesian tuple)
  G:q      %   Push [0 1 ... n-1] (*)
  @        %   Push current column
  &-       %   Matrix of pairwise differences (**)
  G\       %   Modulo n, element-wise
  m        %   Ismember function: for each entry in (*), gives true iff
           %   it is present in (**)
  ?        %   If all entries are true
    @      %     Push current column
    u      %     Unique entries. This is the solution
    .      %     Break loop
           %   End (implicit)
           % End (implicit)
           % Display (implicit)

```
> 5 votes

# Answer
# Jelly, 13 bytes

```
ŒPðṗ2I%QLðÐṀḢ

```

Try it online!

### How it works

```
ŒPðṗ2I%QLðÐṀḢ  Main link. Argument: n (integer)

ŒP             Powerset; generate all subsequences of [1, ..., n].
  ð       ÐṀ   Begin a dyadic chain. Call it with all subsequences S as left
               argument and n as right one. Return the array of all sequences for
               which the chain returns the maximal result, i.e., [0, ..., n-1].
   ṗ2              Cartesian power 2; generate all pairs of elements of S.
     I             Increments; map each pair [x, y] to [y-x].
      %            Map each [y-x] to [(y-x)%n].
       Q           Unique; deduplicate the array of modular difference singletons.
        L          Take the length.
         ð     Begin a new, dyadic chain.
               Left argument: S' (filted subsequences). Right argument: n
            Ḣ  Take the first element of S'.
               Since S was sorted by length, so is S', so the first element of S'
               is the shortest subsequence that satisfies the condition.

```
> 4 votes

# Answer
# Stax, ~~26~~ 21 bytes

```
Åæ4&╕u◙╩►s∙Φ▬═(0~ d+Q

```

Run and debug online!

~~Right now the online version fails for input `20` but this bug has been fixed and is yet to be deployed to the online interpreter~~  Deployed. Beware it takes some time to run the `20` case.

## Explanation

Turns out that due to way pairwise difference is calculated, I don't need to worry about the equivalence of `k` and `x-k` here. Saving 5 bytes.

Uses the unpacked version to explain.

```
rS{%o~{;i@c:2{E-x%mu%x<wm
r                            [0..`x`], where `x` is input
 S                           Powerset
  {%o~                       Sort by length
      {;i@             w     For each element in the powerset
          c:2                All pairs
             {    m          Map each pair `[p,q] to
              E-                 `q-p`
                x%               `(q-p)%x`
                   u%        Count of unique modulo differences
                     x<      Loop until the count of unique modulo differences is larger than the input(`n`)
                             Now we have found a valid set in the powerset
                        m    Output the members of the set,one element per line.

```

By enforcing the requirement that `0` and `1` both be members of the answer, we can generate the powerset with `[2..x]` instead of `[0..x]` and then add the `0` and `1` manually to every element in the powerset. It is more efficient but need to handle the input `1` specially and costs more bytes.
> 3 votes

# Answer
# Jelly, 17 bytes

```
_þ¹F%³³Ḷ¤ḟ
ŒPÇÐḟḢ

```

Try it online!

-1 byte thanks to Mr. Xcoder
> 2 votes

# Answer
# Python 2, 148 bytes

```
from itertools import*
def f(n):
 r=range(n)
 for i in r:
  for p in combinations(r,i+1):
   if all(any((y+x)%n in p for y in p)for x in r):return p

```

Try it online!
> 0 votes

---
Tags: code-golf, math, number-theory, geometry, abstract-algebra
---


title: Balanced Zero-One Encoding

text:
# Question
Title: Balanced Zero-One Encoding
# Task

Encode a string that entirely consists of uppercase alphabets (`A-Z`) using only zeros and ones, using your own favorite scheme. But the rule isn't that simple!

# Rules

1. Your program/function must correctly handle any valid input string of **length 8**.
2. The results must have the same length for all inputs.
3. The results must be distinct for distinct inputs.
4. The results must be as short as possible.
5. The results must be zero-one balanced (have number of ones **similar** to that of zeros). They don't have to be equal (i.e. perfectly balanced), but your score will be penalized for that.

You don't have to provide a program/function that decodes your encoding.

# Input and Output

* You can decide to accept any set of 26 distinct **printable ASCII characters** instead of `A-Z`.
* You can decide to output any pair of distinct **printable ASCII characters** instead of `0` and `1`.
* You are **not allowed to output an integer** instead of a bit string, since it may have leading zeros and it's unclear if you actually met the rule 2.
* If you decide to deviate from the default (`A-Z` input and `01` output), you must specify the input/output character sets in your submission.

# Scoring

* Base score: Code size, or 1 if your program happens to be empty.
* Penalties
    + Penalty for length: multiply `1.5 ** (encoded length - 42)`
    + There is no bonus for being shorter; 42 is the minimal length for a perfectly balanced encoding of 8-length strings with alphabet size 26.
    + Penalty for being unbalanced: multiply `2 ** max(abs(ones - zeros) for every valid input of length 8)`, where `ones` and `zeros` are the counts of 1 and 0 in each output, respectively.
    + Your submission must either show a worst-case example (input/output) or theoretical explanation on the penalty value.
* The lowest score wins.

# Example Submission

## Hypothetical esolang, 0 Bytes, Score 74733.8906

Here is a hypothetical esolang, where an empty program prints out all the ASCII codes of input's characters in binary.

```

```

For example, if you give `AAAAAAAA` as input, the program will print `1000001` 8 times in a row, i.e. `10000011000001100000110000011000001100000110000011000001`.

The input alphabet is chosen to be `CEFGIJKLMNQRSTUVXYZabcdefh`. This way, all of the chars are converted to seven digits in binary, and the zero-one counts differ only by one per char (they all have three 1's and four 0's or vice versa when converted to binary).

The output length is always 56, and the worst-case unbalance occurs on the inputs like `CCCCCCCC`, where zeros appear 8 more times than ones.

Therefore, the score of this submission is `1.5 ** (56 - 42) * 2 ** 8 == 74733.8906`.

# Answer
# Jelly, 18 bytes

```
2Ḷx21Œ!Q
O_65ḅ26ị¢

```

Try it online!

-1 byte thanks to caird coinheringaahing

might remember to re-add the explanation since it was restructured for golfing
> 4 votes

# Answer
# Stax, 11 bytes, 0 penalty, Score 11

This program uses `[0-9A-P]` for input and `[01]` for output.

```
ö■▄←·ï↨≡⌐╠H

```

Run and debug it online \- click the run button to start. The first four test cases run in milliseconds. The fifth in seconds. The sixth in millenia.

The corresponding ascii representation of this program is this.

```
A$21*,26|bD|N

```

It leans heavily on the `|N` instruction, which gets the subsequent permutation of an array.

```
A$21*           "10" repeated 21 times
     ,26|b      get input and decode it as a base 26 number
          D|N    ... that many times get the next lexicographic permutation

```

All outputs are permutations of the initial string. It has 21 zeroes and 21 ones. Therefore, all outputs are 42 characters, and perfectly balanced.
> 4 votes

# Answer
## Pyth, ~~20~~ ~~19~~ 14 bytes, Max Diff: 0, Length: 64, Score: ~~149636.5528~~ ~~142154.7251~~ 104745.5869

```
sm@S.{.p*`T4xG

```

Try it online!

Uses the lower case alphabet (`[a-z]`) instead of uppercase. Can use uppercase by replacing `G` with `rG1`, at the cost of 2 bytes.

I could have translated HyperNeutrino's Python 3 answer for a better score, but frankly, I want an answer that actually works.
> 3 votes

# Answer
# Python 2, ~~779~~ 645 bytes, Max(Diff) = 0, Length = 48, Score = 7346.95

```
def f(s):
 a,b=0,""
 for i in s:a=a*26+ord(i)-65
 a+=56*252**4
 for i in range(5):b=bin((int("4lnk28t9vtqgfrpfda9uyfrjhcjwjvno6aec2nwegi0g4mnublc05dher8fjm4s5gh55lu87a4itmc74t6tozcsfdbxkg82frwljy0wam1jht98g2j0bma021v5d48pwq0fklv0n1ltrxft1fpk5gt5mx5fj4p2mjqqpvcylt1xayxf1iwdmyoxgfvl7oui1oo6147bm9rqpqut9ns8hhjc77t3pqy48otovrsm1t4mmleumspkuef66ma1vi0l4mtkwaeeizuvvds9fro3vhc0mrn6ox17rdpk7xw747qf28934u5jci5q1qj81i7dyf7rf0x7hb19xm93xhxsgh4w8ifs6fhynsddbo9j938ewfvhjlbpiz50n5hanmno6c89blyx50e89z7vjq2ho2r2u2wwyu4q18kv4fi1nhmfbgjbnkdayr5kblaped4fo5u97bi9a67d89irxa0r9cinmnohfgjmh5fhkcr33",36)>>a%252*10)&1023)[2:].rjust(10,"0")+b;a/=252
 return b[2:]

```

Try it online!

The magic number `4lnk28t9vtqgfrpfda9uyfrjhcjwjvno6aec2nwegi0g4mnublc05dher8fjm4s5gh55lu87a4itmc74t6tozcsfdbxkg82frwljy0wam1jht98g2j0bma021v5d48pwq0fklv0n1ltrxft1fpk5gt5mx5fj4p2mjqqpvcylt1xayxf1iwdmyoxgfvl7oui1oo6147bm9rqpqut9ns8hhjc77t3pqy48otovrsm1t4mmleumspkuef66ma1vi0l4mtkwaeeizuvvds9fro3vhc0mrn6ox17rdpk7xw747qf28934u5jci5q1qj81i7dyf7rf0x7hb19xm93xhxsgh4w8ifs6fhynsddbo9j938ewfvhjlbpiz50n5hanmno6c89blyx50e89z7vjq2ho2r2u2wwyu4q18kv4fi1nhmfbgjbnkdayr5kblaped4fo5u97bi9a67d89irxa0r9cinmnohfgjmh5fhkcr33` (in base 36), or its decimal equivalent `382136276621246556626597379364678993894472503063952720559883124988542417847157286833446006767955087631166943136913765901237281892296575754126024183763829277879554548743231384272055945084065681774297483130020386641869860456147616177702938121538230311395513497506285733567467605871232294046704309941152721616618474501854355102646152223338484615876165254236449912858255665248186687952137487016925761633237335983620006273901509768720506129789443353730706676483647298576692613113269388239830925662977837917272690235355742330377154505179476767457756888107428475384947712227312747517748632498691058764154580934614231152483398774630508576533263098942260213967880819240793990219283490212843120923539516962682466148372296338428497778127570401190309339992457562121354271`, encodes all 252 permutations of 5 `0`s and 5 `1`s.

The algorithm first converts `A-Z` into `0-25` and treat it as a base-26 number, then add `56*252**4`.

Then, the number is converted to a 5-digit base-252 number, and substitute with the corresponding permutation of 5 `0`s and 5 `1`s.

After that, delete the first 2 bits, which is guaranteed to be `01`. Then we have encoded the string to a 48-bit string, which consists of exactly 24 `0`s and 24 `1`s.
> 2 votes

# Answer
# Perl 5, 55 bytes, max diff 0, length 42, score ~~56~~ 55

This works but will take a long but doable time (`ZZZZZZZZ` took 2.5 days on my computer). Memory is no problem.

Uses `A-Z` as input and `1` and `A` as encoding characters. They are always perfectly balanced. Skips the first `26^7 = 8031810176` balanced combinations representing string shorter than 8 characters, but that's OK since there are `538257874440` available and I use `208827064575` and `208827064575 + 8031810176 < 538257874440`.

However it actually "counts" up to to the target combination which will take very long. That's why in the TIO link I only used a too short input string (which are also supported) to demonstrate that the output is correct. Will work up to a bit more than `AAAAAA` before TIO times out.`ZZZZZZZZ` should be about `26^3 = 17576` times slower.

```
#!/usr/bin/perl -ap
$_=1x21 .($i=A)x21;s/(A*)(1*)1A/$2$1A1/ until"@F"eq$i++

```

Try it online!

The decoder is almost the same:

```
#!/usr/bin/perl -ap
$_=1x21 .($\=A)x21;s/(A*)(1*)1A/$2$1A1/,$\++until"@F"eq$_}{

```

Try it online!
> 2 votes

# Answer
## JavaScript (ES8), score 22186.623779296875

```
f=
s=>s.replace(/./g,(c,i)=>(i%2*127^c.charCodeAt()).toString(2).padStart(7,0))
```

```
<input oninput=o.textContent=f(this.value)><pre id=o>
```

For even length input, always outputs 3.5\* of zeros and ones, so it only pays the 1.5 \** 14 penalty. Supported characters: `'+-.3569:<GKMNSUVYZ\cefijlqrtx`.
> 2 votes

# Answer
# Jelly, 16 bytes

```
42ɠO%ḅ26ịœcH$ạ‘Ṭ

```

Uses `+,-./0123456789:;<=>?@ABCD` for input and returns a list of ones and zeroes.

This attempts to build a list of 538,257,874,440 combinations in memory, so you'll need a large amount of RAM to run it as is...

Try it online! (testable; input length 3, output length 18)

### How it works

```
42ɠO%ḅ26ịœcH$ạ‘Ṭ  Main link. No arguments.

42                Set the argument and the return value to 42.
  ɠ               Read one line from STDIN.
   O              Ordinal; map ['+', ..., 'D'] to [43, ..., 69].
    %             Take the code points modulo 42, mapping [43, ..., 69] to
                  [1, ..., 26].
     ḅ26          Convert the result from base 26 to integer.
            $     Combine the two links to the left into a monadic chain.
           H          Halve; yield 21.
         œc           Generate all 21-combinations of [1, ..., 42].
                  There are 538,257,874,440 of these combinations. The first
                  269,128,937,220 begin with a 1.
        ị         Retrieve the combination at the index to the left.
                  [26, 26, 26, 26, 26, 26, 26, 26] in bijective base 26 equals
                  217,180,147,158 in decimal, so the retrieved combination will
                  begin with a 1.
              ‘   Increment; yield 43.
             ạ    Absolute difference; map [1, ..., 42] to [42, ..., 1].
                  The combination now begins with a 42.
               Ṭ  Untruth; turn the combination into a Boolean list, with 1's
                  at the specified indices and 0's elsewhere.
                  Since the maximum of the combination is 42, this list will have
                  exactly 42 items, 21 of which will be 1's.

```
> 2 votes

# Answer
# Python 3, ~~985~~ 135 bytes, Max Diff 0, Length 42, score 135

```
lambda s:C(int(s,26),21,20)
B=lambda x,y:y<1or-~x*B(x+1,y-1)//y
def C(n,o,z):p=B(o,z);x=n>=p;return z+1and[x]+C(n-p*x,o-x,z-1+x)or[1]*o

```

Try it online!

Courtesy of Bubbler

Ungolfed code:

```
import math

def binomial(x, y):
    return math.factorial(x) // math.factorial(y) // math.factorial(x - y)

def string_to_int(input_str):
    result = 0
    for i in range(0,8):
        result += (ord(input_str[i])-65)%26 * pow(26,i)
    return result

def counting_function(target, ones, zeros):
    if zeros > 0:
        position = binomial(ones+zeros-1,zeros-1)
    else:
        position = 1
    if target > position:
        if ones > 0:
            print("1", end='')
            ones -= 1
            counting_function(target-position,ones,zeros)
    else:
        if zeros > 0:
            print("0", end='')
            zeros -= 1
            counting_function(target,ones,zeros)
        elif ones > 0:
            print("1", end='')
            ones -= 1
            counting_function(target,ones,zeros)

input_str = input("Input string (A-Z): ")
input_int = string_to_int(input_str)+1
target = input_int
ones = 21
zeros = 21
counting_function(target, ones, zeros)
print("")

```

Since other approaches seem quite inefficient, I've tried to make a time-optimal one. It is clealy O(N) in N bits of encoding, which is big-O optimal.

Hint: try to think of Pascal's triangle for this one (this diagram reveals it)

Sample outputs:

```
Input:  AAAAAAAA
Output: 000000000000000000000111111111111111111111

```

```
Input:  ZZZZZZZZ
Output: 011001000000011010011000111010110110111110

```

Execution time: \< 0.013 s (roughly constant for all inputs)
> 2 votes

# Answer
# Python 3, 75 bytes, Max Diff 0, Length 42, Score 112

```
lambda s:sorted({*permutations("01"*21)})[int(s,26)]
from itertools import*

```

Try it online!

This only works in theory because of memory constraints. There are `538257874440` distinct balanced zero-one strings of length 42 and `208827064575` possible inputs, so some of the possible outputs will not be used.

-37 bytes thanks to @recursive
> 1 votes

# Answer
# \>\<\>, 75 bytes, Max Diff 0, Length 42, score 75

```
0i:0(?v'A'-$dd+*+!
.")1+.\1+:0$:2%:}:@-2,@+$bl"
[ab+-?\$:?vv~3
~~]>n<v$-1<>

```

Try it online!

Fair warning, this will take a very *very* ***very*** long time to complete even for the trivial `AAAAAAAA` case. Runs through each binary representations of a counter until the (base 26 representation of the input)'th binary number with 21 `1`s is reached. If you want to test the program somewhat you can replace the `ab+` on the third line with `1` which will return the nth binary number with just a single `1`, Try it online!
> 1 votes

# Answer
# C++, 146 Bytes, 42 maxlength, 0 unbalance, score 146

```
#include<algorithm>
long long i,s;int f(char*I,char*O){for(O[i=42]=s=0;i--;i<8?s=s*26+I[i]:0)O[i]=i%2|48;for(;s--;)std::next_permutation(O,O+42);}

```

Works for any continious 26 char, but warning it runs an unacceptable time
> 1 votes

---
Tags: string, code-challenge, balanced-string, encoding
---