title: Playing with the musical turtle

text:
# Question
Title: Playing with the musical turtle
My two kids like to play with the following toy:

The colored areas with the shapes inside can be touched and the turtle then lights the area and plays a sound or says the name of the color or the shape inside. The middle button changes the mode. There is one mode in which the areas play different musical notes when touched, with a twist: if the kid touches three consecutive areas clockwise, a special melody 1 is played. If the three consecutive areas touched are placed counterclockwise, a special melody 2 is played.

### The challenge

Let's simulate the internal logic of the toy. Given a string with 3 presses of the kid, return two distinct, coherent values if the three presses are for consecutive areas (clockwise or counterclockwise) and a third distinct value if they are not.

### Details

* The input areas will be named with a character each, which can be their color: `ROYGB` for red, orange, yellow, green and blue; or their shape: `HSRTC` for heart, square, star (`R`), triangle and circle. Case does not matter, you can choose to work with input and output just in uppercase or in lowercase.
* The program will receive a string (or char array or anything equivalent) with three presses. Examples (using the colors): `RBO`, `GYO`, `BBR`, `YRG`, `YGB`, `ORB`...
* The program will output three distinct, coherent values to represent the three possible outcomes: a first value if the combination does not trigger a special melody, a second value if the combination triggers the clockwise special melody, and a third value if the combination triggers the counterclockwise special melody. Example: `0` for no special combination, `1` for the melody triggered by a clockwise combination and `-1` for the melody triggered by a counterclockwise combination.
* You do not need to worry about handling wrong input.

### Test cases

```
Input   Output      // Input based on colors
--------------
RBO     0           // No special combination
GYO     -1          // Counterclockwise melody triggered
BBR     0           // No special combination
YRG     0           // No special combination
YGB     1           // Clockwise melody triggered
ORB     -1          // Counterclockwise melody triggered
OOO     0           // No special combination
BRO     1           // Clockwise melody triggered

```

This is , so may the shortest code for each language win!

# Answer
# Java 8, ~~48~~ ~~39~~ 33 bytes

```
s->"ROYGBRO BGYORBG".indexOf(s)|7

```

-6 bytes thanks to *@RickHitchcock*, so make sure to upvote him as well!

Takes uppercase color as input-String. Outputs `-1` for none, `7` for clockwise, and `15` for counterclockwise.

Try it online.

**Explanation:**

```
s->      // Method with String parameter and integer return-type
   "ROYGBRO BGYORBG".indexOf(s)
         //  Get the index of the input in the String "ROYGBRO BGYORBG",
         //  which will result in -1 if the input is not a substring of this String
    |7   //  Then take a bitwise-OR 7 of this index, and return it as result

```

---

**Old 39 bytes answer:**

```
s->(char)"ROYGBRO BGYORBG".indexOf(s)/7

```

Takes uppercase color as input-String. Outputs `9362` for none, `0` for clockwise, and `1` for counterclockwise.

Try it online.

**Explanation:**

```
s->      // Method with String parameter and integer return-type
   (char)"ROYGBRO BGYORBG".indexOf(s)
         //  Get the index of the input in the String "ROYGBRO BGYORBG",
         //  which will result in -1 if the input is not a substring of this String
         //  And cast it to a char (-1 becomes character with unicode value 65535)
    /7   //  Integer-divide it by 7 (the char is implicitly converted to int doing so)

```
> 12 votes

# Answer
# JavaScript (ES6), 41 bytes

Takes color initials as input. Returns `2` for none, `true` for clockwise or `false` for counterclockwise.

```
s=>~(x='ROYGBRO_ORBGYOR'.search(s))?x<5:2

```

Try it online!
> 6 votes

# Answer
# Python 2, 36 bytes

```
lambda i:'ROYGBRO ORBGYOR'.find(i)/7

```

`-1` \- None
`0` \- Clockwise
`1` \- Counterclockwise

Try it online!
> 6 votes

# Answer
# 05AB1E, ~~15~~ 11 bytes

Saved 4 bytes thanks to *Kevin Cruijssen* and *Magic Octopus Urn*.

Uses shapes.
Output `[0, 0]` for *none*, `[1, 0]` for *clockwise* and `[0, 1]` for *counter-clockwise*

```
Â‚.•ÌöJη•så

```

Try it online! or as a Test suite

**Explanation**

```
Â‚            # pair the input with its reverse
  .•ÌöJη•     # push the string "hsrtchs"
         så   # check if the input or its reverse is in this string

```
> 5 votes

# Answer
# Wolfram Language (Mathematica), ~~42~~ 36 bytes

```
{"ROYGBRO","ORBGYOR"}~StringCount~#&

```

Try it online!

Counts the number of times the input appears in both `"ROYGBRO"` and `"ORBGYOR"`. Returns `{1,0}` for clockwise, `{0,1}` for counterclockwise, and `{0,0}` for no special combination.

At the cost of only one more byte, we can get outputs of `0` for nothing, `1` for clockwise, and `2` for counterclockwise with `"ROYGBRO.ORBGYORBGYOR"~StringCount~#&`.
> 4 votes

# Answer
## Excel, 29 bytes

```
=FIND(A1,"ROYGBRO_RBGYORB")<6

```

Uppercase colours as input.

Returns `#VALUE!` for no pattern, `TRUE` for clockwise, `FALSE` for anti-clockwise.

Can wrap in `IFERROR( ,0)` for `+11 bytes` to handle exception , and return '0' for no-pattern cases instead.
> 4 votes

# Answer
# JavaScript (ES6), 32 bytes

```
s=>'ROYGBRO_ORBGYOR'.search(s)|7

```

Returns -1 if no combination, 15 if counterclockwise, 7 if clockwise.

```
let f =
s=>'ROYGBRO_ORBGYOR'.search(s)|7

console.log(f('RBO')) // -1
console.log(f('GYO')) // 15
console.log(f('BBR')) // -1
console.log(f('YRG')) // -1
console.log(f('YGB')) // 7
console.log(f('ORB')) // 15
console.log(f('OOO')) // -1
console.log(f('BRO')) // 7
```
> 4 votes

# Answer
# x86 machine code, ~~39~~ 36 bytes

```
00000000: f30f 6f29 b815 0000 0066 0f3a 6328 0c89  ..o).....f.:c(..
00000010: c883 c807 c352 4f59 4742 524f 2042 4759  .....ROYGBRO BGY
00000020: 4f52 4247                                ORBG

```

Assembly:

```
section .text
	global func
func:					;the function uses fastcall conventions
					;no stack setup needed because we don't need to use stack
	movdqu xmm5,[ecx]		;Move DQword (16 bytes) from 1st arg to func(ecx) to SSE reg
	mov eax, msg			;Load address of constant str 'msg' into eax
	PcmpIstrI xmm5, [eax], 1100b	;Packed Compare String Return Index, get idx of [eax] in xmm5
	mov eax, ecx			;Move returned result into reg eax
	or eax, 7			;Bitwise OR eax with 7 to get consistent values
	ret				;return to caller, eax is the return register
	msg db 'ROYGBRO BGYORBG'

```

Try it online!

Output is `23` for none, `7` for clockwise, and `15` for counter-clockwise. Based on @RickHitchcock 's answer.

Edit 1: Saved 3 bytes by using an SSE string comparison instruction instead of using libc.

Edit 2: Use proper calling convention for SSE (use XMM5 instead of XMM2) and improve formatting on Bash.
> 4 votes

# Answer
# Python 2, ~~45~~ 43 bytes

```
lambda i,a='ROYGBRO':(i in a)-(i[::-1]in a)

```

Try it online!

With ideas from and serious credit to @DeadPossum

-2 with thanks to @JoKing. Now outputs -1 = counterclockwise, 0 = none, 1 = clockwise.

My original effort is below for historical purposes.

# Python 2, ~~52~~ 51 bytes

```
lambda i,a='ROYGBRO':((0,1)[i[::-1]in a],2)[i in a]

```

Try it online!

0 = none, 1 = counterclockwise, 2 = clockwise
> 3 votes

# Answer
# APL(Dyalog), ~~22~~ 18 bytes

```
+/(⍷-⍷∘⌽)∘'ROYGBRO'

```

*-4 bytes thanks to @ngn*

Takes a string of color initials. Outputs 0 for no special pattern, -1 for counterclockwise, 1 for clockwise.

Try it online!
> 3 votes

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

```
$_=ROYGBRO=~/$_/-ORBGYOR=~/$_/

```

Try it online!
> 3 votes

# Answer
# Python 2,  ~~35~~  36 bytes

+1 - for some reason I thought all buttons would be distinct \>\_\<

*Developed independently from what I have just seen (and now up-voted) by Dead Possum*

```
lambda s:'ORBGYO.BROYGBR'.find(s)/7

```

**Try it online!**
> 3 votes

# Answer
# Stax, ~~14~~ 13 bytes

```
ù♀e▌d─█£F'♦O▬

```

Run and debug it

The output is

* 1 for no special combination
* 2 for counter-clockwise melody
* 3 for clockwise melody
> 2 votes

# Answer
# Jelly, 12 bytes

```
,Ṛẇ€“¤ƈẎṬ%Ȥ»

```

Try it online!

-4 thanks to Jonathan Allan.

Clockwise: `[1, 0]`
Counter-clockwise: `[0, 1]`
Other: `[0, 0]`
> 2 votes

# Answer
# Pip, 19 bytes

```
Y"ROYGBRO"OaNyaNRVy

```

Outputs `10` for clockwise, `01` for counterclockwise, `00` for neither. Try it online!

### Explanation

```
                     a is 1st cmdline argument
Y"ROYGBRO"           Yank that string into y variable
           aNy       Count of occurrences of a in y
          O          Output without newline
                RVy  y reversed
              aN     Count of occurrences of a in that string
                     Print (implicit)

```
> 2 votes

# Answer
# , 21 bytes

```
-&(OR@E.&'ROYGBRO')|.

```

Try it online!

### How it works

```
-&(OR@E.&'ROYGBRO')|.  Monadic 2-verb hook. Input: a string.

                   |.  Map over [input string, input string reversed]:
      E.&'ROYGBRO'     Find exact matches of input in 'ROYGBRO'
  (OR@            )    Reduce with OR; is it a substring of 'ROYGBRO'?
-&                     Reduce with -; result is 1 for CW, -1 for CCW, 0 otherwise

```

Achieves maximum amount of function reuse.
> 2 votes

# Answer
# , 38 bytes

```
grep(scan(,''),c('ROYGBRO','ORBGYOR'))

```

Try it online!

Returns :

* No special combination : `integer(0)`
* Counterclockwise melody triggered : `2`
* Clockwise melody triggered : `1`
> 1 votes

# Answer
# Charcoal, 18 bytes

```
≔ROYGBROηＩ⁻№ηθ№⮌ηθ

```

Try it online! Link is to verbose version of code. Explanation:

```
 ROYGBRO            Literal string
≔       η           Assign to variable
            η   η   Value of variable
               ⮌    Reversed
             θ   θ  Input string
           №  №     Count matches
          ⁻         Subtract
         Ｉ          Cast to string
                    Implicitly print

```
> 1 votes

# Answer
# Common Lisp, 68 bytes

```
(defun x(s)(cond((search s "ROYGBRO")1)((search s "BGYORBG")-1)(0)))

```

Try it online!
> 1 votes

# Answer
# Clean, 63 bytes

```
import StdEnv,Text
$s=map((>)0o indexOf s)["ROYGBRO","BGYORBG"]

```

Try it online!

`[True, True]` for no special noises, `[True, False]` for counterclockwise, `[False, True]` for clockwise.
> 1 votes

# Answer
# Japt, ~~17~~ 14 bytes

Takes the colours as input, in lowercase. Returns `0` for clockwise, `1` for counterclockwise or `-1` if there's no combo.

```
`ygß`ê qÔbøU

```

Try it

---

## Expanation

```
`...`            :Compressed string "roygbrow"
     ê           :Palindromise
       qÔ        :Split on "w"
         b       :Index of the first element
          ø      : That contains
           U     :  The input string

```
> 0 votes

# Answer
# Ruby, ~~53~~ 36 bytes

```
->n{"\a\fDch+".index(""<<n%111)&./3}

```

Try it online!

Input: a 3-digit integer, where the digits represent colors:

* 1 - red
* 2 - orange
* 3 - yellow
* 4 - green
* 5 - blue

Output:0 for clockwise, 1 for counterclockwise, `nil` otherwise.
> 0 votes

# Answer
# C (gcc), 55 bytes

Returns 0 for none, -1 for CCW and 1 for CW.

```
f(char*s){s=!strstr("ORBGYOR",s)-!strstr("ROYGBRO",s);}

```

Try it online!
> 0 votes

---
Tags: code-golf, string, subsequence, classification
---


title: Generating Brainf*** NOPs

text:
# Question
Title: Generating Brainf*** NOPs
Sometimes when writing brainfuck code, you feel the need to make it longer than needed to *encourage* debugging. You could do it by just plopping a `><` in there, but what fun is that? You'll need something longer and less NOPey to confuse anybody reading your code.

## Quick introduction to Brainfuck

> Brainfuck is an esoteric programming language created in 1993 by Urban Müller, and notable for its extreme minimalism. (Wikipedia)

Brainfuck is a language based on eight commands: `+-><,.[]`. The code is run on something like a Turing machine: an infinite tape on which values can be changed. In this challenge, we'll focus on the first four:

```
+    increment the value at the pointer
-    decrement the value at the pointer
>    move the pointer right
<    move the pointer left

```

## Brainfuck NOPs

A brainfuck NOP is a sequence of brainfuck characters that, when executed from any state, leads to no change in the state. They consist of the four characters mentioned above.

## The Challenge

The challenge is to write a program or function that, when executed, generates a random brainfuck NOP of the given length.

## Input

You will receive as input a nonnegative even integer `n`. (NOPs are impossible for odd `n`.)

## Output

You will output a random brainfuck NOP of the length `n`.

## Rules

* The definition of NOP: when the output of the program is inserted at any point in a brainfuck program, the behavior of said program must not change in any way. In other words, it must not change the state of the interpreter.
    + Note that for example `+>-<` is incorrect, since it changes the values of the two cells without changing them back. Please test your solution for these before posting.
    + Also note that `+>-<->+<` is a NOP that can't be reduced to nothing just by removing `><` `<>` `+-` `-+`. Thus, you can't use an algorithm that just inserts these inside each other.
* Every valid NOP of the length `n` must have a nonzero chance of appearing in the output. The distribution does not have to be uniform, though.
* The brainfuck interpreter in question has a doubly infinite tape of arbitrary precision cells. That is, you can go infinitely to the both directions, and increment/decrement each cell indefinitely.
* The program must finish **within 1 minute for `n` = 100** on my machine, so no generating all possible NOPs and picking one.
* If given invalid input (non-integer, negative, odd, etc.) you may do anything you'd like, including crash.

## Scoring

This is , so the shortest answer in bytes wins.

## Examples

Here are all valid outputs for `n` = 4:

```
++--    +-+-    +--+    --++    -+-+    -++-
>><<    ><><    ><<>    <<>>    <><>    <>><
><+-    ><-+    <>+-    <>-+
>+-<    >-+<    <+->    <-+>
+><-    -><+    +<>-    -<>+
+-><    -+><    +-<>    -+<>

```

Here are a few possible outputs for `n` = 20:

```
+>>->+<->-<<<->>++<<
>+>-<+<->+-<>->+<-<+
+--+-++--++-+--+-++-
>>>>>>>>>+-<<<<<<<<<

```

# Answer
> 12 votes
## CJam, ~~62~~ 59 bytes

*Thanks to nhahtdh for saving 3 bytes.*

Because there is no requirement for any particular distribution as long as each no-op appears with finite probability, we can simplify this a lot by simply generating string containing a balanced number of `-+` and `<>`, respectively, testing if it's a NOP and sorting it if it isn't.

Of course, for longer inputs, this will almost always result in sorted output, but you can test the code with some input like `8` to see that it can in principle produce any NOP of the given length.

```
ri_0a*\2/{;"-+<>":L2/mR}%smr:SL["Xa.Xm"3/2e*L]z:sers~0-S$S?

```

Try it online.

# Answer
> 17 votes
## CJam, ~~118~~ 116 bytes

This got slightly out of hand... especially the second half seems like it should be very golfable.

```
ri2/_)mr:R-"<>"R*mr_'=fm0\{1$+}%+__&e`]:\{mr1aa..+}*\@](\z:~\{~\("+-"*mr1$3$e=[{_,)mr_2$<@@>}*+]@@f{`1$`={(}@?\}W<}/

```

Test it here.

This handles `N = 100` pretty much instantly. I don't have time to write the full breakdown of the code now, so here is the algorithm:

* Generate a random balanced string of `<` and `>` with random (even) length between `0` and `N` inclusive.
* Riffle the tape head positions into this array. E.g. `"<>><"` becomes `[0 '< -1 '> 0 '> 1 '< 0]`.
* Get a list of all positions reached in the process.
* For each such position initialise an empty string. Also determine how many pairs of characters are left to reach a string of length `N`.
* For each remaining pair append `+-` to the string of a random position.
* Shuffle all of those strings.
* For each position determine how often that position occurs in the riffled array, and split the corresponding string into that many (random-length) chunks.
* In the riffled array, replace the occurrences of the position with its random chunks.

Done. This is based on the observation that:

* Any NOP must have an equal amount of `<` and `>` to return the tape head to the original position.
* The code will be a NOP as long as each tape cell is incremented as often as decremented.

By distributing random but balanced amounts of `+`s and `-`s between all the places where the tape head is on a given cell, we ensure that we find every possible NOP.

# Answer
> 4 votes
## Mathematica, 350 bytes

```
Quiet@(For[a="+",If[{##4}=={},#3!=0||Union@#!={0},Switch[#4,"+",#0[ReplacePart[#,#2->#[[#2]]+1],#2,#3,##5],"-",#0[ReplacePart[#,#2->#[[#2]]-1],#2,#3,##5],">",#0[#~Append~0,#2+1,#3+1,##5],"<",If[#2<2,#0[#~Prepend~0,1,#3-1,##5],#0[#,#2-1,#3-1,##5]]]]&@@{{0},1,0}~Join~Characters@a,a=""<>RandomSample@Flatten@RandomChoice[{{"+","-"},{">","<"}},#/2]];a)&

```

Way too long? Yes. Do I even care? Not until someone else posts a valid answer.

# Answer
> 2 votes
# Python 3, 163 bytes

```
from random import*
n=int(input())
p=0;d=[0]*n;a=choices(b'+-<>',k=n)
for c in a:d[p]+=c%2*(44-c);p+=~c%2*(c-61)
if p|any(d):a=n//2*b'+-'
print(*map(chr,a),sep='')

```

Try it online!

Full program that prints results to STDOUT. The line that runs BF code might be golfable.

Adopted Tyilo's approach; if the generated BF code is not a NOP, discard it altogether and fall back to `'+-'` repeated.

# Answer
> 2 votes
# Python 3, 177 bytes

```
from random import*
n=int(input())
r=[0]*n*3
p=0
a=[43,45]
s=choices(a+[60,62],k=n)
for c in s:p+=~c%2*(c-61);r[p]+=c%2*(44-c)
if any(r+[p]):s=a*(n//2)
print(*map(chr,s),sep='')

```

Try it online!

I used code from Bubbler's answer for the BF simulation.

# Answer
> 1 votes
# JavaScript (Node.js), 160 bytes

```
n=>[...s=c(i=n,t=c(n/2,r=[],f=_=>'+-'),f=_=>'+-<>'[Math.random()*4|0])].map(_=>_<'<'?(r[i]=_+1-~r[i]-1):(i+=_<'>'||-1))|r.some(eval)|i-n?t:s;c=n=>n?c(n-1)+f():r

```

Try it online!

# Answer
> 1 votes
# Wolfram Language (Mathematica), 224 bytes

```
(s=RandomSample[##&@@@Table["<"">",(r=RandomInteger)[#/2]]];While[(g=Length@s)<#,s=Insert[s=Insert[s,"+",i=r@g+1],"-",RandomChoice@@Select[GatherBy[0~Range~++g,Count[#,"<"]-Count[#,">"]&@Take[s,#]&],!FreeQ[#,i]&]+1]];""<>s)&

```

Try it online!

Here is the un-golfed (or rather, pre-golfed) version:

```
Function[{n},
 k = RandomInteger[n/2];
 s = RandomSample[## & @@@ Table["<" ">", k]];
 While[Length[s] < n,
   s = Insert[s, "+", i = RandomInteger[Length[s]] + 1];
   p = GatherBy[Range[0, Length[s]],
     Count[#, "<"] - Count[#, ">"]& @ Take[s, #]&];
   j = RandomChoice @@ Select[p, ! FreeQ[#, i] &]];
   s = Insert[s, "-", j + 1];
   ];
 ""<>s]

```

We first pick a random number of `<`'s and `>`'s to use, and generate a random list with an equal number of each.

To fill in the rest of the characters, we pick a position in which to add a `+`, then find a position where the pointer points to the same location and add a `-` there.

Repeat until the list has length `n`, and stringify the result.

---
Tags: code-golf, random, brainfuck, code-generation, balanced-string
---


title: Count arrays that make unique sets

text:
# Question
Title: Count arrays that make unique sets
This question has a similar set up to Find an array that fits a set of sums although is quite different in its goals.

Consider an array `A` of length `n`. The array contains only positive integers. For example `A = (1,1,2,2)`. Let us define `f(A)` as the set of sums of all the non-empty contiguous subarrays of `A`. In this case `f(A) = {1,2,3,4,5,6}`. The steps to produce `f(A)` are as follows:

The subarrays of `A` are `(1), (1), (2), (2), (1,1), (1,2), (2,2), (1,1,2), (1,2,2), (1,1,2,2)`. Their respective sums are `1,1,2,2,2,3,4,4,5,6`. The set you get from this list is therefore `{1,2,3,4,5,6}`.

We call an array `A` **unique** if there is no other array `B` of the same length such that `f(A) = f(B)`, except for the array `A` reversed. As an example, `f((1,2,3)) = f((3,2,1)) = {1,2,3,5,6}` but there is no other array of length `3` that produces the same set of sums.

We will only consider arrays where the elements are either a given integer `s` or `s+1`. E.g. if `s=1` the arrays would only contain `1` and `2`.

**Task**

The task, for a given `n` and `s` is to count the number of unique arrays of that length. You can assume that `s` is between `1` and `9`.

You should not count the reverse of an array as well as the array itself.

**Examples**

`s = 1`, the answer is always `n+1`.

`s = 2`, the answers counting from `n = 1` up are:

```
2,3,6,10,20,32,52,86

```

`s = 8`, the answers counting from `n = 1` up are:

```
2,3,6,10,20,36,68,130

```

**Score**

For a given `n`, your code should output the answer for all values of `s` from `1` to `9`. Your score is the highest value of `n` for which this completes in one minute.

**Testing**

I will need to run your code on my ubuntu machine so please include as detailed instructions as possible for how to compile and run your code.

**Leaderboard**

* **n = 24** by Anders Kaseorg in **Rust** (34 seconds)
* **n = 16** by Ourous in **Clean** (36 seconds)
* **n = 14** by JRowan in **Common Lisp** (49 seconds)

# Answer
> 5 votes
# Rust, n ≈ 24

Requires nightly Rust for the convenient `reverse_bits` feature. Compile with `rustc -O unique.rs` and run with (e.g.) `./unique 24`.

```
#![feature(reverse_bits)]
use std::{collections::HashMap, env, mem, process};

type T = u32;
const BITS: u32 = mem::size_of::<T>() as u32 * 8;

fn main() {
    let args = env::args().collect::<Vec<_>>();
    assert!(args.len() == 2);
    let n: u32 = args[1].parse().unwrap();
    assert!(n > 0);
    assert!(n <= BITS);
    let mut unique = (2..=9).map(|_| HashMap::new()).collect::<Vec<_>>();
    let mut sums = vec![0 as T; n as usize];
    for a in 0 as T..=!0 >> (BITS - n) {
        if a <= a.reverse_bits() >> (BITS - n) {
            for v in &mut sums {
                *v = 0;
            }
            for i in 0..n {
                let mut bit = 1;
                for j in i..n {
                    bit <<= a >> j & 1;
                    sums[(j - i) as usize] |= bit;
                }
            }
            for s in 2..=9 {
                let mut sums_s =
                    vec![0 as T; ((n + (n - 1) * s) / BITS + 1) as usize].into_boxed_slice();
                let mut pos = 0;
                let mut shift = 0;
                let mut lo = 0;
                let mut hi = 0;
                for &v in &sums {
                    lo |= v << shift;
                    if BITS - shift < n {
                        hi |= v >> (BITS - shift);
                    }
                    shift += s;
                    if shift >= BITS {
                        shift -= BITS;
                        sums_s[pos] = lo;
                        pos += 1;
                        lo = hi;
                        hi = 0;
                    }
                }
                if lo != 0 || hi != 0 {
                    sums_s[pos] = lo;
                    pos += 1;
                    if hi != 0 {
                        sums_s[pos] = hi;
                    }
                }
                unique[s as usize - 2]
                    .entry(sums_s)
                    .and_modify(|u| *u = false)
                    .or_insert(true);
            }
        }
    }
    let mut counts = vec![n + 1];
    counts.extend(
        unique
            .iter()
            .map(|m| m.values().map(|&u| u as T).sum::<T>())
            .collect::<Vec<_>>(),
    );
    println!("{:?}", counts);
    process::exit(0); // Avoid running destructors.
}

```

# Answer
> 2 votes
**Common Lisp SBCL, N = 14**

call function (goahead n s)

```
    (defun sub-lists(l m &optional(x 0)(y 0))
  (cond; ((and(= y (length l))(= x (length l)))nil)
        ((= y (length l))m)
        ((= x (length l))(sub-lists l m 0(1+ y)))
    (t (sub-lists l (cons(loop for a from x to (+ x y)

             when (and(nth (+ x y)l)(nth a l)(< (+ x y)(length l)))
                ;   while (nth a l)
             ;while(and(< (+ x y)(length l))(nth a l))
                    collect (nth a l))m) (1+ x)y))
    ))
(defun permutations(size elements)
  (if (zerop size)'(())
 (mapcan (lambda (p)
                    (map 'list (lambda (e)
                           (cons e p))
                         elements))
     (permutations (1- size) elements))))
(defun remove-reverse(l m)
  (cond ((endp l)m)
    ((member (reverse (first l))(rest l) :test #'equal)(remove-reverse (rest l)m))
    (t (remove-reverse (rest l)(cons (first l)m)))))
(defun main(n s)
  (let((l (remove-reverse (permutations n `(,s ,(1+ s)))nil)))

  (loop for x in l
     for j = (remove 'nil (sub-lists x nil))
       collect(sort (make-set(loop for y in j
        collect (apply '+ y))nil)#'<)
     )
  ))
(defun remove-dups(l m n)
  (cond ((endp l)n)
        ((member (first l) (rest l) :test #'equal)(remove-dups(rest l)(cons (first l) m) n))
    ((member (first l) m :test #'equal)(remove-dups(rest l)m n))
    (t(remove-dups (rest l) m (cons (first l) n))))

  )
(defun goahead(n s)
  (loop for a from 1 to s
  collect(length (remove-dups(main n a)nil nil))))
(defun make-set (L m)
  "Returns a set from a list. Duplicate elements are removed."
  (cond ((endp L) m)
    ((member (first L) (rest L)) (make-set (rest L)m))
    ( t (make-set (rest L)(cons (first l)m)))))

```

here is the run times

```
CL-USER> (time (goahead 14 9))
Evaluation took:
  34.342 seconds of real time
  34.295000 seconds of total run time (34.103012 user, 0.191988 system)
  [ Run times consist of 0.263 seconds GC time, and 34.032 seconds non-GC time. ]
  99.86% CPU
  103,024,254,028 processor cycles
  1,473,099,744 bytes consed

(15 1047 4893 6864 7270 7324 7328 7328 7328)
CL-USER> (time (goahead 15 9))
Evaluation took:
  138.639 seconds of real time
  138.511089 seconds of total run time (137.923824 user, 0.587265 system)
  [ Run times consist of 0.630 seconds GC time, and 137.882 seconds non-GC time. ]
  99.91% CPU
  415,915,271,830 processor cycles
  3,453,394,576 bytes consed

(16 1502 8848 13336 14418 14578 14594 14594 14594)

```

# Answer
> 2 votes
# Clean

Certainly not the most efficient approach, but I'm interested in seeing how well a naive by-value filter does.

That said, there's still a bit of improvement to be made using this method.

```
module main
import StdEnv, Data.List, System.CommandLine

f l = sort (nub [sum t \\ i <- inits l, t <- tails i])

Start w
	# ([_:args], w) = getCommandLine w
	= case map toInt args of
		[n] = map (flip countUniques n) [1..9]
		_ = abort "Wrong number of arguments!"

countUniques 1 n = inc n
countUniques s n = length uniques
where
	lists = [[s + ((i >> p) bitand 1) \\ p <- [0..dec n]] \\ i <- [0..2^n-1]]
	pairs = sortBy (\(a,_) (b,_) = a < b) (zip (map f lists, lists))
	groups = map (snd o unzip) (groupBy (\(a,_) (b,_) = a == b) pairs)
	uniques = filter (\section = case section of [a, b] = a == reverse b; [_] = True; _ = False) groups

```

Place in a file named `main.icl`, or change the top line to `module <your_file_name_here>`.

Compile with `clm -h 1500m -s 50m -fusion -t -IL Dynamics -IL StdEnv -IL Platform main`.

You can get the version TIO (and myself) use from the link in the heading, or a more recent one from here.

---
Tags: combinatorics, fastest-code
---


title: ASCII Bookshelves

text:
# Question
Title: ASCII Bookshelves
You know those stackable shelves that are basically just wooden boxes that can be stacked together? We're going to simulate building some bookshelves out of those with some ASCII art.

Our books are all *conveniently* uniform in size, and all look like the following:

```
|X|
|X|
|X|

```

The bookshelves are individual boxes, always three characters high on the inside (enough to fit a book standing upright), composed of `|` characters on the left and right, `-` characters for the top and bottom, and wide enough to fit `X` books (where `X` is an input integer). For example, here's a bookshelf of size `3`:

```
|---------|
|         |
|         |
|         |
|---------|

```

because you can fit `3` books into it like so

```
|---------|
||X||X||X||
||X||X||X||
||X||X||X||
|---------|

```

The input is going to be two strictly positive integers, `X` and `Y`, where `X` is the width of the shelves we have (measured in books), and `Y` is how many books we have to stack. If we have more books than fit on a single shelf, we need to add more shelves to the top. For example, here is input `4 wide / 6 books`:

```
|------------|
||X||X|      |
||X||X|      |
||X||X|      |
|------------|
|------------|
||X||X||X||X||
||X||X||X||X||
||X||X||X||X||
|------------|

```

If `Y % X > 0`, meaning the number of books is not an integer multiple of the shelf size, the remainder books should go on the top-most left-most position (as in the case with `4 6`, above) and the remaining part of that shelf filled in with spaces.

### Input

* Two strictly positive integers in any convenient format, each `>0`.
* You can take the input in either order (e.g., size of shelves first, then number of books, or vice versa). Please state in your submission the input order.
* You can safely assume that neither input will be larger than your language's default `[int]` size (or equivalent).

### Output

The resulting ASCII art representation of the books and bookshelves.

### Rules

* Leading or trailing newlines or whitespace are all optional, so long as the characters themselves line up correctly.
* Either a full program or a function are acceptable. If a function, you can return the output rather than printing it.
* If possible, please include a link to an online testing environment so other people can try out your code!
* Standard loopholes are forbidden.
* This is so all usual golfing rules apply, and the shortest code (in bytes) wins.

### Further Examples

```
6 wide / 2 books
|------------------|
||X||X|            |
||X||X|            |
||X||X|            |
|------------------|

2 wide / 6 books
|------|
||X||X||
||X||X||
||X||X||
|------|
|------|
||X||X||
||X||X||
||X||X||
|------|
|------|
||X||X||
||X||X||
||X||X||
|------|

4 wide / 9 books
|------------|
||X|         |
||X|         |
||X|         |
|------------|
|------------|
||X||X||X||X||
||X||X||X||X||
||X||X||X||X||
|------------|
|------------|
||X||X||X||X||
||X||X||X||X||
||X||X||X||X||
|------------|

```

# Answer
## JavaScript (ES6), ~~100~~ ~~99~~ 98 bytes

Takes the width `w` and the number of books `b` in currying syntax `(w)(b)`.

```
w=>g=(b,s=`|${'-'.repeat(w*3)}|
`,r=s.replace(/---/g,_=>b&&b--?'|X|':'   '))=>(b?g(b)+s:s)+r+r+r+s

```

### Formatted and commented

```
w =>                                // main function: takes width 'w' as input, returns 'g'
  g = (                             // g = recursive function with:
    b,                              //   - b = number of books
    s = `|${'-'.repeat(w * 3)}|\n`, //   - s = top/bottom of shell, filled with '-'
    r = s.replace(                  //   - r = pattern of the current row of books,
      RegExp('---', 'g'),           //         using 's' as a template and updating
      _ => b && b-- ? '|X|' : '   ' //         'b' while building it
    )                               // NB: 'r' must be defined in the scope of 'g',
  ) =>                              //     otherwise it would be overwritten by
    (                               //     subsequent calls
      b ?                           // if there are remaining books:
        g(b) + s                    //   do a recursive call and append shell top
      :                             // else:
        s                           //   just append shell top
    ) + r + r + r + s               // append book rows and shell bottom

```

### Test cases

```
let f =

w=>g=(b,s=`|${'-'.repeat(w*3)}|
`,r=s.replace(/---/g,_=>b&&b--?'|X|':'   '))=>(b?g(b)+s:s)+r+r+r+s

console.log(f(6)(2))
console.log(f(2)(6))
console.log(f(4)(9))
```
> 14 votes

# Answer
# Bash (+utilities), ~~130~~, ~~108~~, 106 bytes

A single, continuous, shell pipeline to render your bookshelves.

Changelog:

* Optimized first sed expression a bit, -12 bytes (Thx @Riley !)
* Replaced `printf + seq` with a raw `printf`, -10 bytes
* Refactored the second sed expression, -2 bytes

**Golfed**

```
printf %$2s\\n|fold -$1|sed "s/ /|X|/g;:;/.\{$[$1*3]\}/!s/$/ /;t;h;s/./-/gp;x;p;p;p;x"|sed 's/.*/|&|/'|tac

```

---

```
$./shelf 6 8
|------------------|
||X||X|            |
||X||X|            |
||X||X|            |
|------------------|
|------------------|
||X||X||X||X||X||X||
||X||X||X||X||X||X||
||X||X||X||X||X||X||
|------------------|

```

Try It Online !

**How It Works**

`$./shelf 2 3`

`printf %$2s\\n` \- generate n whitespace characters, one per book (shown as `_`)

`___`

`fold -$1` \- fold them by the shelf length

```
__
_

```

`sed "s/ /|X|/g;"` \- replace `_` with `X`, add book covers

```
|X||X|
|X|

```

`:;/.\{$[$1*3]\}/!s/$/ /;t` \- right pad with spaces (shown as `_`)

```
|X||X|
|X|___

```

`h;s/./-/gp;x;p;p;p;x` \- triplicate each line, and add `---` before and after it.

```
------
|X||X|
|X||X|
|X||X|
------
------
|X|
|X|
|X|
------

```

`sed 's/.*/|&|/'|tac` \- wrap lines in `| |`, reverse with tac

```
|------|
||X|   |
||X|   |
||X|   |
|------|
|------|
||X||X||
||X||X||
||X||X||
|------|

```
> 9 votes

# Answer
# Python 2, ~~133~~ ~~113~~ 105 bytes

I'm sure there's a better way...

```
X,Y=input()
k='|'+'---'*X+'|'
while Y:g=Y%X or X;print k+'\n'+('|'+'|X|'*g+'   '*(X-g)+'|'+'\n')*3+k;Y-=g

```

Input is taken `width, books`

-20 bytes thanks to @ovs for noticing an unnecessary lambda function!
-8 bytes thanks to @ovs for shortening the input.
> 6 votes

# Answer
## Batch, 261 bytes

```
@set/an=~-%1%%%2+1,b=%1-n
@set s=
@set t=
@for /l %%i in (1,1,%2)do @call set t=---%%t%%&if %%i gtr %n% (call set s=%%s%%   )else call set s=%%s%%X
@for %%s in ("|%t%|" "|%s:X=|X|%|" "|%s:X=|X|%|" "|%s:X=|X|%|" "|%t%|")do @echo %%~s
@if %b% gtr 0 %0 %b% %2

```

Uses my trick from my Batch answer to Let's play tennis to easily print lots of `|` characters.
> 6 votes

# Answer
# Haskell, 100 bytes

`x#y` returns the string for width `x` and `y` books.

```
s?n=[1..n]>>s
x#y|x<y=x#(y-x)++x#x|w<-"---"?x,b<-"|X|"?y++"   "?(x-y)=[w,b,b,b,w]>>=('|':).(++"|\n")

```

Try it online!

The main function/operator is `#`. When `x<y` it splits the books into `y-x` and `x`, then recurses. When `x>=y`, `w` and `b` are the two line types, minus the outer `|`s and the newline.

The helper operator `s?n` concatenates `n` copies of the string `s`.
> 5 votes

# Answer
# PowerShell, ~~149~~ 134 bytes

```
param($w,$b)$s="|$('-'*$w*3)|"
if($a=$b%$w){,$s+,"|$('|X|'*$a)$(' '*3*($w-$a))|"*3+$s}
if($b-=$a){(,$s+,"|$('|X|'*$w)|"*3+$s)*($b/$w)}

```

Try it online!

Takes input `$w`idth and `$b`ooks. Sets string `$s` to be one of the horizontal shelves. Then we have two `if` statements.

The first checks whether we have "remainder" books. If so, we output the shelf, the (number of books plus number of spaces)`*3`, and another shelf.

Next, we see if we still have books remaining after removing the remainders (`$a`). Same sort of setup, except we're using `$w` number of books. Since at this point, `$b` is guaranteed to be a multiple of `$w` (because we removed the remainder, `$a`), we don't need to worry about rounding.

*Removed the `[math]::Floor()` call, saving 15 bytes*

All of these strings are left on the pipeline, and implicit `Write-Output` happens at program completion.
> 5 votes

# Answer
# Python 3, 142 bytes

Still working on it. `b` is for 'number of books' and `w` is for shelf width.

```
def s(b,w):
 R=b%w
 B='|\n'
 I='|'
 X='|X|'
 d=I+3*w*'-'+B
 f=I+X*w+B
 p=I+R*X+3*(w-R)*' '+B
 print(R and d+3*p+d or" ")+b//w*(d+3*f+d))

```
> 4 votes

# Answer
# CJam, ~~62~~ 61 bytes

```
q~1a*W$/W$f{0e]}{{"|X|"S3*?}%s__'-3*W$*_}%1m>W%"|
|"*"||"\*o;

```

Takes input as `width books`

Try it online!

**Explanation**

```
q~           Read and eval input (pushes width W and books B to the stack)
1a*          Push an array containing  the number 1 B times
W$/          Split it into chunks of size W
W$f{0e]}     Pad each chunk to width W by adding 0's to the right (the last chunk might be
              shorter than W)
{            Apply the following to each chunk:
 {            Apply the following to each number in the chunk:
  "|X|"S3*?    Push "|X|" if the number is 1, or "   " if it's 0
 }%           (end of block)
 s            Stringify (joins with no separator)
 __           Duplicate twice (each shelf is 3 identical lines)
 '-3*W$*_     Push a string containing '-' repeated 3×W times, then duplicate it
}%           (end of block)
              At this point we have an array containing sequences of 3 identical lines
              each followed by two lines of -'s
1m>          Rotate the array 1 to the right; brings the final line of -'s to the start
W%           Reverse the array, so that the top shelf is the partially empty one
"|\n|"*      Join the array with the string "|\n|", to build the sides of the shelves
"||"\*       Join the string "||" with the shelf string (adds the first and last | chars)
o            Print the result
;            Pop and discard W

```
> 4 votes

# Answer
# AHK, 208 bytes

```
AutoTrim,Off
w=%1%
b=%2%
f:=Mod(b,w)
Loop,%w%
s=%s%---
s=|%s%|`n
If (f>0) {
Loop,%f%
t=%t%|X|
Loop,% w-f
t=%t% ` ` `
t=|%t%|`n
t:=s t t t s
}
Loop,%w%
r=%r%|X|
r=|%r%|`n
Loop,% (b-f)/w
t:=t s r r r s
Send,%t%

```

There are a few things frustating me from golfing further:

* AutoHotkey doesn't have a built-in repeat function
* You can't directly use the passed in arguments (`%1%` & `%2%`) in math functions because those expect variable or number input and it will assume the unescaped `1` to be the number one rather than the variable name
* I am not very good at golfing

An easier to read version of the above looks like this:

```
AutoTrim,Off
w=%1%
b=%2%
f:=Mod(b,w)

Loop,%w%
   s=%s%---
s=|%s%|`n

If (f>0) {
   Loop,%f%
      t=%t%|X|
   Loop,% w-f
      t=%t% ` ` `
   t=|%t%|`n
   t:=s t t t s
}

Loop,%w%
   r=%r%|X|
r=|%r%|`n

Loop,% (b-f)/w
   t:=t s r r r s

Send,%t%

```

If a `Loop` doesn't use brackets `{}`, then only the next line is part of the loop. If setting a variable's value using `:=` instead of `=`, you can drop the percent sign escape characters. Tilde n is the newline character.
> 3 votes

# Answer
# Java 7, ~~230~~ ~~224~~ 222 bytes

```
String c(int w,int b){String r="",n="|\n",z="|";int i=0,j,k,t=b%w<1?w:b%w,x=b/w+(t!=w?1:0);for(;i++<w;z+="---");z+=n;for(i=0;i<x;i++){r+=z;for(j=0;j++<3;r+=n){r+="|";for(k=0;k<w;r+=i<1&k++>=t?"   ":"|X|");}r+=z;}return r;}

```

**Explanation:**

```
String c(int w, int b){                // Method with two integer parameters and String return-type
  String r = "",                       //  The return-String
         n = "|\n",                    //  Part that's used multiple times in the code
         z = "|";                      //  Shelf part of the book-boxes
  int i = 0, j, k,                     //  Indexes used in the for-loops
      t = b%w < 1 ? w : b%w,           //  Books on top shelf
      x = b/w + (t != w ? 1 : 0);      //  Amount of shelves
  for(; i++ < w; z += "---"); z += n;  //  Create the shelf-part ("|---|"; with w times "---")
  for(i = 0; i < x; i++){              //  Loop over the rows
    r += z;                            //   Append the result with the shelf-part
    for(j = 0; j++ < 3; ){             //   Loop three times (the height of the books & boxes)
      r += "|";                        //    Append the result-String with "|"
      for(k = 0; k < w;                //    Loop over the columns
          r +=                         //     And append the result-String with:
           i < 1                       //      If this is the first row:
           & k++ >= t ?                //      And the current column is larger or equal to the amount of books in the top shelf
             "   "                     //       Use an empty space
           :                           //      Else:
             "|X|"                     //       Use the book-part
            );                         //    End of columns loop
         r += n;                       //    Append the result-String with a "|" and a new-line
       }                               //   End of the loop of three
      r += z;                          //   Append the result-String with the shelf-part
    }                                  //  End of rows loop
    return r;                          //  Return the result-String
 }                                     // End of method

```

**Test code:**

Try it here.

```
class M{
  static String c(int w,int b){String r="",n="|\n",z="|";int i=0,j,k,t=b%w<1?w:b%w,x=b/w+(t!=w?1:0);for(;i++<w;z+="---");z+=n;for(i=0;i<x;i++){r+=z;for(j=0;j++<3;r+=n){r+="|";for(k=0;k<w;r+=i<1&k++>=t?"   ":"|X|");}r+=z;}return r;}

  public static void main(String[] a){
    System.out.println(c(6, 2));
    System.out.println(c(2, 6));
    System.out.println(c(4, 9));
  }
}

```

**Output:**

```
|------------------|
||X||X|            |
||X||X|            |
||X||X|            |
|------------------|

|------|
||X||X||
||X||X||
||X||X||
|------|
|------|
||X||X||
||X||X||
||X||X||
|------|
|------|
||X||X||
||X||X||
||X||X||
|------|

|------------|
||X|         |
||X|         |
||X|         |
|------------|
|------------|
||X||X||X||X||
||X||X||X||X||
||X||X||X||X||
|------------|
|------------|
||X||X||X||X||
||X||X||X||X||
||X||X||X||X||
|------------|

```
> 3 votes

# Answer
# PowerShell, 109 bytes

```
param($w,$b)for(;$b;$b-=$c){if(!($c=$b%$w)){$c=$w}($l="|$('-'*$w*3)|")
,"|$('|X|'*$c)$(' '*($w-$c)*3)|"*3
$l}

```

Less golfed test script:

```
$f = {

param($w,$b)
for(;$b;$b-=$c){
    if(!($c=$b%$w)){$c=$w}
    ($l="|$('-'*$w*3)|")
    ,"|$('|X|'*$c)$(' '*($w-$c)*3)|"*3
    $l
}

}

@(
    ,(6, 2,
    "|------------------|",
    "||X||X|            |",
    "||X||X|            |",
    "||X||X|            |",
    "|------------------|")

    ,(2, 6,
    "|------|",
    "||X||X||",
    "||X||X||",
    "||X||X||",
    "|------|",
    "|------|",
    "||X||X||",
    "||X||X||",
    "||X||X||",
    "|------|",
    "|------|",
    "||X||X||",
    "||X||X||",
    "||X||X||",
    "|------|")

    ,(4, 9,
    "|------------|",
    "||X|         |",
    "||X|         |",
    "||X|         |",
    "|------------|",
    "|------------|",
    "||X||X||X||X||",
    "||X||X||X||X||",
    "||X||X||X||X||",
    "|------------|",
    "|------------|",
    "||X||X||X||X||",
    "||X||X||X||X||",
    "||X||X||X||X||",
    "|------------|")
) | % {
    $w,$b,$expected = $_
    $result = &$f $w $b
    "$result"-eq"$expected"
    $result
}

```

Output:

```
True
|------------------|
||X||X|            |
||X||X|            |
||X||X|            |
|------------------|
True
|------|
||X||X||
||X||X||
||X||X||
|------|
|------|
||X||X||
||X||X||
||X||X||
|------|
|------|
||X||X||
||X||X||
||X||X||
|------|
True
|------------|
||X|         |
||X|         |
||X|         |
|------------|
|------------|
||X||X||X||X||
||X||X||X||X||
||X||X||X||X||
|------------|
|------------|
||X||X||X||X||
||X||X||X||X||
||X||X||X||X||
|------------|

```

## PowerShell, 109 bytes, alternative

```
param($w,$b)for(;$b;$b-=$c){($l="|$('---'*$w)|")
,"|$('|X|'*($c=(($b%$w),$w-ne0)[0]))$('   '*($w-$c))|"*3
$l}

```
> 2 votes

# Answer
# Python 2, ~~120~~ 118 bytes

```
i,j=input()
a=j%i
n='|\n'
x='|'+'---'*i+n
print(x+('|'+'|x|'*a+' '*(i-a)*3+n)*3,'')[a<1]+(x+('|'+'|x|'*i+n)*3)*(j/i)+x

```

Try it online!

Have been meaning to have a go at this one for the last few days. Now that I have finally got time to do it there's already a shorter Python answer. Oh well, just posted as an alternative.

Input taken as width,books
> 1 votes

# Answer
# SOGL, 64 bytes

```
be%→M"Q└ƨS‘*ač;┼→S%‘A |e3* -* |++M?tMSeM-9*@*a+┼Ot}be÷:?{teSa┼Ot

```

Explanation: First function:

```
   →M  define function M which pushes
b      the book amount
  %    mod
 e     the bookshelf width

```

second function:

```
           →S  create function S (example input: 3)          [3]
"Q└ƨS‘         push the string "|||XXX|||" (the book)        [3, "|||XXX|||"]
      *        multiply by the number on stack (book count)  ["|||XXX||||||XXX||||||XXX|||"]
       a       push variable A (later defined "|||")         ["|||XXX||||||XXX||||||XXX|||", "|||"]
        č      chop into char array                          ["|||XXX||||||XXX||||||XXX|||", ["|", "|", "|"]]
         ;     swap top 2 on stack                           [["|", "|", "|"], "|||XXX||||||XXX||||||XXX|||"]
          ┼    horizontally append                           [["||X||X||X|", "||X||X||X|", "||X||X||X|"]]

```

this function expects a number (book count) on stack and outputs the bookshelfs books

```
["||X||X||X|",
 "||X||X||X|",
 "||X||X||X|"]

```

Further down example given is e=3 (bookshelf width) and b=8 (book amount)

```
%‘A              var A = "|||"
    |            push "|"                      ["|"]
     e3*         push E * 3                    ["|", 9]
         -*      push that many "-"es          ["|", "---------"]
            |+   append "|"                    ["|", "---------|"]
              +  prepend the "|"               ["|---------|"]

```

this is the bookshelf top/bottom line and always stays on the stack first part (half-empty bookshelf)

First main part

```
M?               }               if the modulo != 0
  tM                             output the bookshelf top/bottom line
    S                            execute the S function width the modulo
     eM-                         push bookshelf width - modulo (empty space count)
        9*                       multiply by 9 (books are 3x3 so 3x3 spaces)
          @*                     get that many spaces
            a+                   append to that "|||"
              ┼                  horizontally append
               O                 output
                t                output the bookshelf top/bottom line

```

And the last part

```
be÷            floor divide book amout by width (full shelves)
   :?          if not 0 (a bug makes all loops execute once)
     {         repeat
      t        output the bookshelf top/bottom line
       eS      execute S with shelf width (full shelf)
         a┼    horizontally append "|||"
           O   output
            t  output the bookshelf top/bottom line

```
> 1 votes

# Answer
# Java (JDK), 124 bytes

```
s->b->{for(int i=0;i++<(b-~s)/s*5;)System.out.printf("|%-"+s*3+"s|%n",i%5<2?"-".repeat(s*3):"|X|".repeat(i<5&b%s>0?b%s:s));}

```

Try it online!

## Credits
> 1 votes

# Answer
# PHP\>=7.1, 138 Bytes

```
for([,$w,$b]=$argv;$i<ceil($b/$w)*5;)echo str_pad("|".str_repeat(["","|X|"][$t=($i+1)%5>1],$i++<5&&$b%$w?$b%$w:$w),$w*3+1,"- "[$t])."|\n";

```

Online Version
> 0 votes

# Answer
# Canvas, 33 bytes

```
|X|３＊×⁷３×⇵-×|３＊×╫│；２２╋Ｐ
％？％⁸｝÷［⁷⁸

```

Try it here!

Explanation (some characters have been replaced to look more monospace):

```
|X|3*×⁷3×⇵-×|3*×╫│;22╋P  helper function. Prints a shelf with X books
|X|                      push "|X|"
   3*                    repeat it 3 times vertically
     ×                   repeat that horizontally by the item (X) below on the stack
      ⁷3×                push width * 3
         ⇵               ceiling divide that by 2
          -×             repeat "-" that many times
            |3*          repeat "|" vertically 3 times (aka "|¶|¶|")
               ×         prepend that to the dashes (aka ¼ of a bookshelf)
                ╫│       quad-palindromize with horizontal overlap of the remainder
                           taken before and vertical overlap of 1
                  ;      get the books on top
                   22╋   and at coordinates (2;2) in the shelf, place them in
                      P  print that whole thing

%?%⁸}÷[⁷⁸
%?  }      if width%amount (!= 0)
  %⁸         execute the helper function with width%amount on the stack
     ÷[    repeat floor(width/amount) times
       ⁷     push width
        ⁸    execute the helper function

```
> 0 votes

# Answer
# Pip `-n`, 45 bytes

```
Wb-:yPPZ['-X3Xa"|X|"X(Yb%a|a).sX3Xa-yRL3]WR'|

```

Takes the width and book count, respectively, as command-line arguments. Try it online!

### Explanation

We run a loop to print the shelves one by one from top to bottom. At each iteration, we update `b` (the number of books to print) by subtracting `y` (the number of books printed on that iteration). When `b` reaches 0, the loop exits.

```
Wb-:yPPZ['-X3Xa"|X|"X(Yb%a|a).sX3Xa-yRL3]WR'|
                                               a is 1st cmdline arg (shelf width); b is 2nd cmdline
                                                 arg (# books); s is space; y is ""
                                               Note that "" becomes zero in numeric contexts
Wb-:y                                          While b decremented by y is nonzero:
                       b%a|a                    b mod a, or a if that quantity is zero
                      Y                         Yank that value into y
                     (      )                   This is the number of books on the current shelf
               "|X|"                            Book-spine string
                    X                           Repeated y times
                                  a-y           Number of empty slots on the current shelf
                              sX3X              Three spaces for each slot
                             .                  Concatenate to the book-spines string
                                     RL3        Make a list of 3 copies of that string
         '-X3Xa                                 3*a hyphens
        [                               ]       Put that string and the above list in a list
                                         WR'|   Wrap all strings in the nested list in |
      PZ                                        Palindromize the outer list (adding a copy of the
                                                hyphens to the end of it)
     P                                          Print, joining all sublists on newlines (-n flag)

```

Because that's a little involved, here's an example of the first iteration when `a = 3, b = 8`:

```
Yb%a|a       2
"|X|"X ^     "|X||X|"
^ .sX3Xa-y   "|X||X|   "
^ RL3        ["|X||X|   ";"|X||X|   ";"|X||X|   "]
['-X3Xa ^ ]  ["---------";["|X||X|   ";"|X||X|   ";"|X||X|   "]]
^ WR'|       ["|---------|";["||X||X|   |";"||X||X|   |";"||X||X|   |"]]
PZ ^         ["|---------|";["||X||X|   |";"||X||X|   |";"||X||X|   |"];"|---------|"]

```

which then prints as

```
|---------|
||X||X|   |
||X||X|   |
||X||X|   |
|---------|

```
> 0 votes

# Answer
# Pyth, 56 bytes

```
M++GHGV_fTs*V,]Q1.DEQjCg*5\|smgL\-*L3?d"|X|""   ".[*]1N0

```

Accepts shelf width, book count as separate arguments in that order. Try it online here, or verify all the test cases at once here.

```
M++GHGV_fTs*V,]Q1.DEQjCg*5\|smgL\-*L3?d"|X|""   ".[*]1N0Q   Implicit: Q=1st arg, E=2nd arg
                                                            Trailing Q inferred
M                                                           Define a function, g(G,H):
 ++GHG                                                        Return G + H + G
                 .DEQ                                       Divmod E by Q, yields [E//Q, E%Q]
             ,]Q1                                           [[Q], 1]
           *V                                               Vectorised multiply the two previous results
                                                              This yields Q repeated E//Q times, then E%Q
          s                                                 Flatten
        fT                                                  Filter out falsey values (i.e. trailing 0 if present)
       _                                                    Reverse (to put partially filled shelf on top)
      V                                                     For N in the above:
                                                    ]1        [1]
                                                   *  N       Repeat the above N times
                                                 .[    0Q     Pad the above on the right with 0, to length Q
                             m                                Map the above, as d, using:
                                     ?d"|X|""   "               If d != 0, yield "|X|", else "   "
                                  *L3                           Multiply each char by 3
                                                                  Yields ['|||','XXX','|||'] or ['   ','   ','   ']
                              gL\-                              Use g to wrap each element in '-'
                            s                                 Flatten
                       g*5\|                                  Use g to add '|||||' to start and end of the above
                      C                                       Transpose
                     j                                        Join on newlines, implicit print

```
> 0 votes

# Answer
# Forth (gforth), 622 bytes (minimized (remove comments, indentation, 1-char word names) to 303 bytes)

My first play with Forth :)

```
: bar 124 EMIT ;

: delimline ( width -- )
    bar
    3 * 0 DO 45 EMIT LOOP
    bar CR
;

: bookline ( width books -- )
    bar
    DUP 0 DO bar 88 EMIT bar LOOP
    2DUP = IF
        DROP DROP
    ELSE
        - 0 do 3 SPACES LOOP
    THEN
    bar CR
;

: shelf ( width books -- )
    DUP 0 = IF
        DROP DROP
    ELSE
        OVER delimline
        3 0 DO OVER OVER bookline LOOP
        DROP delimline
    THEN
;

: stack ( width books -- )
    CR
    OVER OVER OVER MOD shelf
    OVER /
    DUP 0 = IF
        DROP DROP
    ELSE
        0 DO DUP DUP shelf LOOP
    THEN
;

6 2 stack
2 6 stack
3 5 stack
4 4 stack

```

Try it online!

# Output

```

|------------------|
||X||X|            |
||X||X|            |
||X||X|            |
|------------------|

|------|
||X||X||
||X||X||
||X||X||
|------|
|------|
||X||X||
||X||X||
||X||X||
|------|
|------|
||X||X||
||X||X||
||X||X||
|------|

|---------|
||X||X|   |
||X||X|   |
||X||X|   |
|---------|
|---------|
||X||X||X||
||X||X||X||
||X||X||X||
|---------|

|------------|
||X||X||X||X||
||X||X||X||X||
||X||X||X||X||
|------------|

```
> 0 votes

---
Tags: code-golf, ascii-art, packing
---


title: Choose the Most Dramatic Outcome

text:
# Question
Title: Choose the Most Dramatic Outcome
The premise of this is simple: A 10% chance is pretty unlikely, but everyone knows that a one-in-a-million chance is a sure thing!

So, write code that implements the following "dramatic" probability rules:

* Take in a floating point *P* from 0 to 1 representing the unmodified chance of some plot-related event, and a boolean representing whether we're in the climax or not.
* Determine *P'* on these conditions:
    + If 0 \< *P* ≤ 10-3 then *P'* = 1.
    + If .999 ≤ *P* \< 1 then *P'* = 0.
    + If *P* = 0 and we're in the climax, then the heroes will likely get a last-minute sudden advantage and *P'* = .9.
    + If *P* = 1 and we're in the climax, then the villain will unveil an as-yet-unseen superweapon and *P'* = .1.
    + Otherwise, *P'* = *P*.
* Return truthy or falsey based on *P'* as the chance of truth. For example, if *P'* = .7, then you should return truthy 70% of the time and falsey 30% of the time.

Shortest code in bytes wins!

# Answer
> 0 votes
# 05AB1E,  ~~44~~  42 bytes

Crossed out  44  is no longer 44 :)

```
_i90*ë¹₄*©1›i1₄®-‹i¹т*ë¹iiTëтë0ëт]5°<Ý₄/Ω›

```

Port of my Java 8 answer. First input is `P`, second input is `0`/`1` for truthy/falsey whether there is a climax.

Try it online.

**Explanation:**

```
_i                     # If the first (implicit) input is exactly 0:
  90                   #  Push 90
    *                  #  Multiply it with the second (implicit) input (0 if 0, 90 if 1)
 ë                     # Else:
  ¹₄*                  #  Push the first input, and multiply it by 1000
     ©                 #  Save it in the register (without popping)
      1›i              #  If it's larger than 1 (so input larger than 0.001):
          ₄®-          #   Push 1000, and subtract the value from the register
         1   ‹i        #   If it's smaller than 1 (so input smaller than 0.999):
               ¹т*     #    Push the first input multiplied by 100
              ë        #   Else:
               ¹i      #    If the first input is exactly 1:
                 i     #     If the second (implicit) input is 1:
                  T    #      Push 10
                 ë     #     Else:
                  т    #      Push 100
                ë      #    Else:
                 0     #     Push 0
          ë            #  Else:
           т           #   Push 100
   ]                   # Close all if-else clauses
    5°                 # Push 100000 (10**5)
      <                # Decrease it by 1: 99999
       Ý               # Create a list in the range [0,99999]
        ₄/             # Divide it by 1000: [0,0.001,0.002,...,99.997,99.998,99.999]
          Ω            # Take a random value from the list
           ›           # Check if the earlier value is larger than this random value
                       # (and output implicitly)

```

05AB1E has no builtin for a random decimal value in the range `[0, 1)`, so I use `5°<Ý₄/` to generate a list in the range `[0,99.999]` in steps of `0.001` and then `Ω` to take a random value from that list (and I use percentages `[0, 100]` instead of decimals `[0, 1]` in the rest of my code).

# Answer
> 1 votes
# , 86 bytes

```
function(a,b,d=a*(1-a))runif(1)<="if"(d,"if"(d>999e-6,a,1-round(a)),"if"(b,.9-.8*a,a))

```

Try it online!

`a` is P' and `b` is 1 or 0 for "in the climax" or not.

If `a` is 0 or 1, then `d` will be 0, in which case if `b` is 0 just return `a`, otherwise `.9` minus `.8*a`.

Otherwise if `a` is not near 0 or 1, d will be "far" from 0 so return `a`. Otherwise `1-round(a)` will take `a` to the "opposite" 0 or 1.

Then see if a random selection from `[0,1]` is less than or equal to the resulting probability.

The link does a little simulation for all the possible scenarios to demonstrate that it all seems to work.

# Answer
> 1 votes
# C (gcc), 82 bytes

Zero bytes of source code. Use the preprocessor directive:

```
-Df(p,c)=rand()<~(1<<31)*(c&p==0?.9:p==1&c?.1:(p<=1e-3|p>=.999)&p!=1&p!=0?p<.1:p)

```

Try it online!

Very little to explain about it; `p` is the probability, `c` the climax boolean. Main golfing trick is `~(1<<31)`, which seems to be the equivalent to `RAND_MAX` for gcc. The usual C golfing tricks go straight out the window with floating points.

# Answer
> 1 votes
# Java 8, 65 bytes

```
P->C->Math.random()<(P==0?C?.9:0:P>.001?P<.999?P:P==1?C?.1:1:0:1)

```

Try it online.

**Explanation:**

We have the following scenario combinations to consider:

```
P=0, C=falsey             → 100% falsey
P=0, C=truthy             → 90% truthy; 10% falsey
P=(0,0.001], C=either     → 100% truthy
P=(0.001,0.999), C=either → (P*100)% truthy; (100-P*100)% falsey
P=[0.999,1), C=either     → 100% falsey
P=1, C=truthy             → 10% truthy; 90% falsey
P=1, C=falsey             → 100% truthy

```

Which gives us the following code:

```
P->C->           // Method with double and boolean parameters and boolean return-type
  Math.random()  //  Random value in the range [0, 1)
   <(P==0?       //  If P is 0:
      C?         //   And there is a climax:
       .9        //    Check if the random value is smaller than 0.9 (90% true)
      :          //   Else:
       0         //    Check if the random value is smaller than 0 (0% true)
    :P>.001?     //  Else-if P is larger than 0.001:
      P<.999?    //   If P is smaller than 0.999, so in range (0.001,0.999):
       P         //    Check if the random value is smaller than P (P*100% true)
      :P==1?     //   Else-if P is 1:
       C?        //    And there is a climax:
        .1       //     Check if the random value is smaller than 0.1 (10% true)
       :         //    Else:
        1        //     Check if the random value is smaller than 1 (100% true)
      :          //   Else, so P is in the range [0.999,1):
       0         //    Check if the random value is smaller than 0 (0% true)
    :            //  Else, so P is in the range (0,0.001]:
     1)          //   Check if the random value is smaller than 1 (100% true)

```

# Answer
> 1 votes
# Perl 6, 54 bytes

```
{(($/=1-$^p min$p)??.001>=$/||$/!!$^c*.9)>rand^^$p>.5}

```

Try it online!

### Explanation

```
{
 (
  ($/=1-$^p min$p)    # Compute min(p,1-p) and store in $/
  ??                  # if $/ > 0
    .001>=$/||        #   if $/ <= 0.001 then 1
    $/                #   else $/
  !!$^c*.9            # else 0.9 * climax
 )>rand               # Random Bool with given probability
 ^^$p>.5              # Flip if p > 0.5
}

```

# Answer
> 0 votes
# Perl 5 `-pl`, 61 bytes

```
$_=(!$_?<>?.9:0:$_==1?<>?.1:1:$_<=.001||($_<.999&&$_))>rand<>

```

Try it online!

Input is on two lines. First line is P; second line is 0 if not in climax, 1 if in climax.

# Answer
> 0 votes
# Python 3, 118 bytes

```
from random import *
def f(p,c):
if c:
 if p==1:p=.9
 if p==0:p=.1
if p<1e-3:p=1
if p>.999:p=0
return random()<p

```

Inputs: p is initial probability, c is climax

---
Tags: code-golf, decision-problem, probability-theory
---


title: Minimum 1's to get 1-expression for n

text:
# Question
Title: Minimum 1's to get 1-expression for n
### Background

Challenge is inspired by this question.

The 1-expression is a formula that in which you add and multiply the number 1 any number of times. Parenthesis is allowed, but concatenating 1's (e.g. 11) is not allowed.

Here is an example to get the 1-expression for \\$19\\$:

```
(1+1)*(1+1)*(1+1+1+1)+1+1+1 = 19

```

Total number of \\$1\\$'s is \\$11\\$ but there is shorter than this:

```
(1+1)*(1+1+1)*(1+1+1)+1 = 19

```

Total number of \\$1\\$'s is \\$9\\$.

### Program

Given a positive integer `n` output the minimum 1's to get the 1-expression for `n`.

**Notes:**

* For reference, the sequence is A005245.
* This is so shortest answer in each language wins!

### Test cases

```
Input -> Output | 1-Expression
1 -> 1 | 1
6 -> 5 | (1+1+1)*(1+1)
22 -> 10 | (1+1)*((1+1+1+1+1)*(1+1)+1)
77 -> 14 | (1+1)*(1+1)*((1+1+1)*(1+1+1)*(1+1)+1)+1
214 -> 18 | ((((1+1+1)*(1+1)*(1+1)+1)*(1+1)*(1+1)+1)*(1+1)+1)*(1+1)
2018 -> 23 | (((1+1+1)*(1+1)+1)*(1+1+1)*(1+1+1)*(1+1)*(1+1)*(1+1)*(1+1)+1)*(1+1)

```

# Answer
> 1 votes
# Wolfram Language (Mathematica), ~~76~~ 71 bytes

```
If[#<2,1,Min[#+Reverse@#&/@{#0/@Range[#-1],#0/@Most@Rest@Divisors@#}]]&

```

Try it online!

The recursive approach: define `f[n]` to be the minimum of `f[k]+f[n-k]`over all `k` less than `n`, and `f[d] + f[n/d]`over all divisors of `n` (other than `1` and `n` itself).

---
Tags: code-golf, number
---


title: Find an array that fits a set of sums

text:
# Question
Title: Find an array that fits a set of sums
Consider an array `A` of length `n`. The array contains only positive integers. For example `A = (1,1,2,2)`. Let us define `f(A)` as the set of sums of all the non-empty contiguous subarrays of `A`. In this case `f(A) = {1,2,3,4,5,6}`. The steps to produce `f(A)` are as follows:

The subarrays of `A` are `(1), (1), (2), (2), (1,1), (1,2), (2,2), (1,1,2), (1,2,2), (1,1,2,2)`. Their respective sums are `1,1,2,2,2,3,4,4,5,6`. The set you get from this list is therefore `{1,2,3,4,5,6}`.

**Task**

Given a set of sums `S` given in sorted order containing only positive integers and an array length `n`, your task is to output at least one array `X` such that `f(X) = S`.

For example, if `S = {1,2,3,5,6}` and `n = 3` then a valid output is `X = (1,2,3)`.

If there is no such array `X` your code should output any constant value.

**Examples**

Input: `n=4, S = (1, 3, 4, 5, 6, 8, 9, 10, 13)`, possible output: `X = (3, 5, 1, 4)`

Input: `n=6, S = (2, 3, 4, 5, 7, 8, 9, 10, 12, 14, 17, 22)`, possible output: `X = (5, 3, 2, 2, 5, 5)`

Input: `n=6, S = (2, 4, 6, 8, 10, 12, 16)`, possible output: `X = (4, 2, 2, 2, 2, 4)`

Input: `n=6, S = (1, 2, 3, 4, 6, 7, 8, 10, 14)`, possible output: `X = (4, 2, 1, 1, 2, 4)`

Input: `n=10, S = (1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 14, 15, 16, 17, 18, 19, 20, 23, 24, 25)`, possible output: `X = (1, 1, 3, 1, 2, 1, 2, 5, 4, 5)`.

Input: `n=15, S = (1, 2, 3, 4, 6, 7, 8, 9, 10, 11, 13, 14, 15, 16, 17, 18, 20, 21, 22, 23, 24, 25, 26, 27, 28, 30, 31)`, possible output: `X = (1, 2, 1, 3, 3, 1, 3, 3, 1, 3, 3, 1, 2, 1, 3)`.

**Input and output format**

Your code can take input and give output in any easily human read format you find convenient. However, please show the output of testing it on the examples in the question.

**Running time**

You must be able to run the code to completion for all the examples in the question. It should in principle be correct for `n` up to `15` but you do not need to prove it would be fast enough for all inputs.

# Answer
> 7 votes
# Husk, 20 bytes

```
ḟȯ⁰¦ṁ∫ṫ!¡Sof~Λ€∫×:¹g

```

Try it online!

Returns one solution, or an empty list if it doesn't exist. The last test case (`n=15`) finishes in 3.8 seconds on TIO.

## Explanation

The program has two parts. In the first part (`¡` and to the right of it), we construct an infinite list whose `k`th element is a list containing all length-`k` lists whose slice sums are in `S`. We do this inductively, starting from the 1-element slices of `S`, and at each step prepending each element of `S` to each list, and keeping those whose prefix sums are in `S`. In the second part (`!` and to the left of it), we take the `n`th element of the list, which contains length-`n` lists. Of these, we select the first one whose slice sums actually contain every element of `S`.

In the code, let's first replace `o` and `ȯ` (which compose two and three functions into one) by parentheses for clarity.

```
¡S(f~Λ€∫)×:¹g  First part. Input is a list, say S=[1,2,3]
            g  Group equal adjacent elements: [[1],[2],[3]]
¡              Iterate function:
                Argument is a list of lists, say [[1,1],[1,2],[2,1]]
         ×      Mix (combine two lists in all possible ways)
          :     by prepending
           ¹    with the list S: [[1,1,1],[1,1,2],[2,1,1],[1,2,1],[2,1,2],[3,1,1],[2,2,1],[3,1,2],[3,2,1]]
   f            Filter by condition:
        ∫        Cumulative sums: [[1,2,3],[1,2,4],[2,3,4],[1,3,4],[2,3,5],[3,4,5],[2,4,5],[3,4,6],[3,5,6]]
     ~Λ          All of the numbers
 S     €         are elements of S: [[1,1,1]]
                 Only this list remains, since the other cumulative sums contain numbers not from S.
               Result of iteration: [[[1],[2],[3]],[[1,1],[1,2],[2,1]],[[1,1,1]],[],[],[]...

ḟ(⁰¦ṁ∫ṫ)!      Second part. Implicit input, say n=2.
        !      Take nth element of above list: [[1,1],[1,2],[2,1]]
ḟ              Find first element that satisfies this:
                Argument is a list, say [1,2]
      ṫ         Tails: [[1,2],[2]]
    ṁ           Map and concatenate
     ∫          cumulative sums: [1,3,2]
 ȯ ¦            Does it contain all elements of
  ⁰             S? Yes.
               Result is [1,2], print implicitly.

```

There are some parts that need more explanation. In this program, the superscripts `⁰¹` both refer to the first argument `S`. However, if `α` is a function, then `α¹` means "apply `α` to `S`", while `⁰α` means "plug `S` to the second argument of `α`". The function `¦` checks whether its first argument contains all elements of the second (counting multiplicities), so `S` should be its second argument.

In the first part, the function that `¡` uses can be interpreted as `S(f~Λ€∫)(×:)¹`. The combinator `S` behaves like `Sαβγ -> (αγ)(βγ)`, which means that we can simplify it to `(f~Λ€∫¹)(×:¹)`. The second part, `×:¹`, is "mix with `S` by prepending", and its result is passed to the first part. The first part, `f~Λ€∫¹`, works like this. The function `f` filters a list by a condition, which in this case is `~Λ€∫¹`. It receives a list of lists `L`, so we have `~Λ€∫¹L`. The combinator `~` behaves like `~αβγδε -> α(βδ)(γε)`: the first argument is passed to `β`, the second to `γ`, and the results are combined with `α`. This means that we have `Λ(€¹)(∫L)`. The last part `∫L` is just the cumulative sums of `L`, `€¹` is a function that checks membership in `S`, and `Λ` takes a condition (here `€¹`) and a list (here `∫L`), and checks that all elements satisfy it. Put simply, we filter the results of the mixing by whether their cumulative sums are all in `S`.

# Answer
> 6 votes
# Ruby, 135 bytes

```
->a,n{r=w=1;r+=1until w=(s=a[0,r]).product(*[s]*~-n).find{|x|x.sum==a.max&&a==[]|(1..n).flat_map{|r|x.each_cons(r).map(&:sum)}.sort};w}

```

Try it online!

Use a breadth-first search. n=10 works on TIO, n=15 takes longer than a minute, but works on my machine.

# Ruby, 147 bytes

```
->a,n{r=w=1;r+=1until w=([a[-1]-a[-2]]).product(*[s=a[0,r]]*~-n).find{|x|x.sum==a.max&&a==[]|(1..n).flat_map{|r|x.each_cons(r).map(&:sum)}.sort};w}

```

Try it online!

Optimized version, works on TIO for n=15 (~20 sec)

Actually, this is the beginning of a non-brute-force approach. I hope somebody will work on it and find a complete solution.

### First ideas:

* The sum of the output array is the last element (max) of the input array.
* The sum of the output array minus the first (or the last) element, is the second last element of the input array.
* If an array is a solution, then the reverse array is a solution too, so we can assume the first element is the difference between the last 2 elements of the input array.
* The second element can be the difference between second and third or second and fourth last element of the input array.

Which brings us to the next optimization:

# Ruby, 175 bytes

```
->a,n{r=w=1;r+=1until w=([a[-1]-a[-2]]).product([a[-2]-a[-3],a[-2]-a[-4]],*[s=a[0,r]]*(n-2)).find{|x|x.sum==a.max&&a==[]|(1..n).flat_map{|r|x.each_cons(r).map(&:sum)}.sort};w}

```

Try it online!

~8.5 seconds on TIO. Not bad...

...and so on (to be implemented)

# Answer
> 5 votes
# Haskell, ~~117~~ 111 bytes

6 bytes saved thanks to @nimi!

```
f r i n s|n<1=[r|r==[]]|1<2=[y:z|y<-s,t<-[y:map(y+)i],all(`elem`s)t,z<-f[a|a<-r,all(a/=)t]t(n-1)s]
n&s=f s[]n s

```

Try it online!

This computes all solutions. The helper function `f` builds them incrementally, the `r` argument contains the values of \\$ S \\$ that were not yet seen, the `i` argument contains the sums that include the newest element, `n` is the remaining number of elements that are needed, and `s` is always the given set.

When `n` is zero (golfed to `n<1`) the list must be ready, so we check if all values have been seen. If not, we return an empty list to indicate no solutions, else we return a singleton list containing an empty list, to which the chosen elements will be prepended. This case could also have been handled with the additional equations

```
f [] _ 0 _=[[]]
f _ _ 0 _=[]

```

If `n` is not zero, we return

```
[y:z|y<-s,t<-[y:map(y+)i],all(`elem`s)t,z<-f[a|a<-r,all(a/=)t]t(n-1)s]
 ^1^ ^2^^ ^......3......^ ^.....4.....^ ^.............5.............^

```

This is the list of (1) lists where the first element (2) comes from `s` and the rest (5) comes from the recursive call, under the condition (4) that all new sums are in `s`. The new sums are computed in (3) - note that `t` is drawn from a singleton list, an ugly golfing hack for what in idiomatic Haskell would be `let t=y:map(y+)i`. The recursive call (5) gets as new `r` set the old one without those elements that appear among the new sums `t`.

The main function `&` calls the helper function saying that we still have to see all values (`r=s`) and that there are no sums yet (`i=[]`).

For seven more bytes, we can restrict the computation to only give the first result (if any), which is much faster and handles all test cases in less than 2 seconds.

Try it online! (this is the first result only variation of the old version)

# Answer
> 3 votes
# Clean, 177 bytes

```
import StdEnv,Data.List
$s n=find(\a=sort(nub[sum t\\i<-inits a,t<-tails i|t>[]])==s)(?{#u\\u<-s|u<=(last s)-n}(last s)n)
?e s n|n>1=[[h:t]\\h<-:e|h<=s-n,t<- ?e(s-h)(n-1)]=[[s]]

```

Try it online!

Takes about 40 seconds on my machine for the `n=15` test case, but it times out on TIO.

# Clean, 297 bytes

```
import StdEnv,Data.List
$s n=find(\a=sort(nub[sum t\\i<-inits a,t<-tails i|t>[]])==s)(~[u\\u<-s|u<=(last s)-n](last s)n(reverse s))
~e s n a|n>4=let u=a!!0-a!!1 in[[u,h:t]\\h<-[a!!1-a!!2,a!!1-a!!3],t<- ?e(s-u-h)(n-2)]= ?e s n
?e s n|n>1=[[h:t]\\h<-e,t<- ?(takeWhile((>=)(s-n-h))e)(s-h)(n-1)]=[[s]]

```

Try it online!

This one includes some optimisations made by G B as well as some of my own. I think a few of them can be made more generic, so I'll add an explanation once that's done.

It takes about 10 seconds on my machine, 40 seconds on TIO.

# Answer
> 3 votes
# Python 3, 177 bytes

```
from itertools import*
s,n=eval(input())
for[*t]in combinations(s[:-2],n-2):
  a=[*map(int.__sub__,t+s[-2:],[0,*t,s[-2]])];
  {sum(a[p//n:p%n+1])for p in range(n*n)}^{0,*s}or-print(a)

```

Try it online!

(some newlines/spaces added to avoid readers having to scroll the code)

A direct port of my Jelly answer (with some modifications, see "note" section below)

Local run result:

```
[user202729@archlinux golf]$ printf '%s' "from itertools import*
s,n=eval(input())
for[*t]in combinations(s[:-2],n-2):a=[*map(int.__sub__,t+s[-2:],[0,*t,s[-2]])];{sum(a[p//n:p%n+1])for p in range(n*n)}^{0,*s}or-print(a)" > a.py
[user202729@archlinux golf]$ wc -c a.py
177 a.py
[user202729@archlinux golf]$ time python a.py<<<'([1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 14, 15, 16, 17, 18, 19, 20, 23, 24, 25], 10)' 2>/dev/null
[1, 4, 1, 1, 1, 1, 1, 7, 7, 1]

real    0m3.125s
user    0m3.119s
sys     0m0.004s
[user202729@archlinux golf]$ time python a.py<<<'([1, 2, 3, 4, 6, 7, 8, 9, 10, 11, 13, 14, 15, 16, 17, 18, 20, 21, 22, 23, 24, 25, 26, 27, 28, 30, 31], 15)' 2>/dev/null
[3, 1, 2, 1, 3, 3, 1, 3, 3, 1, 3, 3, 1, 2, 1]

real    11m36.093s
user    11m33.941s
sys     0m0.387s
[user202729@archlinux golf]$

```

---

I heard that `itertools` is verbose, but my best `combinations` implementation is even more verbose:

```
c=lambda s,n,p:s and c(s[1:],n-1,p+s[:1])+c(s[1:],n,p)or[]if n else[p]

```

---

*Note*.

* Using division/modulo in `a[p//n:p%n+1]` takes about 2x longer, but saves some bytes.
* This is a bit different from the Jelly answer -- the Jelly answer iterates backwards.
* Thanks to `combinations` returning an iterator, this is more memory-friendly.

# Answer
> 2 votes
# Jelly, 35 bytes

```
Ẇ§QṢ⁼³
;³ṫ-¤0;I
ṖṖœcƓ_2¤¹Ṫ©ÇÑ¬Ʋ¿ṛ®Ç

```

Try it online!

Run locally: (n=15 takes more than 1 GB of RAM)

```
aaa@DESKTOP-F0NL48D MINGW64 ~/jellylanguage (master)
$ time python scripts/jelly fu z '[1,2,3,4,5,6,7,8,9,10,11,12,14,15,16,17,18,19,20,23,24,25]'<<<10
[8, 6, 2, 1, 1, 1, 1, 3, 1, 1]
real    0m1.177s
user    0m0.000s
sys     0m0.015s

aaa@DESKTOP-F0NL48D MINGW64 ~/jellylanguage (master)
$ time python scripts/jelly fu z '[1, 2, 3, 4, 6, 7, 8, 9, 10, 11, 13, 14, 15, 16, 17, 18, 20, 21, 22, 23, 24, 25, 2
6, 27, 28, 30, 31]'<<<15
[3, 1, 2, 1, 3, 3, 1, 3, 3, 1, 3, 3, 1, 2, 1]
real    12m24.488s
user    0m0.000s
sys     0m0.015s

```

(actually I ran the UTF8-encoded version, which takes more than 35 bytes, but the result is the same anyway)

This solution uses short-circuit to reduce the run-time.

Without short-circuiting, this code takes roughly \\$\binom {|S|-2}{n-2} \times \left( \frac {n^3}6 + n^2\log{n^2} \right)\\$ operations, which evaluates to \\$\binom {26-2}{15-2} \times \left( \frac {15^3}6 + 15^2\log{15^2} \right) \approx 5.79 \times 10^9\\$, however due to the inefficiency of Python and Jelly, it takes forever to complete. Thanks to short-circuiting, it can finish much sooner.

### Explanation

We note that the sums of all non-empty prefixes are present in the input, and they are strictly increasing. We can also assume that the largest and second-largest element is a prefix sum.

Therefore, we can consider all ways to choose \\$n-2\\$ distinct elements from first \\$|S|-2\\$ elements (there are \\$\binom {|S|-2}{n-2}\\$ such lists), compute the consecutive differences to recover the elements; then check if it's valid naively (get all \\$n^2\\$ subarrays, compute the sum, uniquify. Total length of the subarrays is about \\$n^3 \over 6\\$)

---

Untested (but should have identical performance)

# Jelly, 32 bytes

```
Ṫ©ÑẆ§QṢ⁻³
;³ṫ-¤ŻI
ṖṖœcƓ_2¤¹Ñ¿ṛ®Ç

```

Try it online!

---

More inefficient version (without short circuit):

# Jelly, 27 bytes

```
Ẇ§QṢ⁼³
ṖṖœcƓ_2¤µ;³ṫ-¤0;I)ÑƇ

```

Try it online!

For the n=15 test, it takes up to 2GB RAM and does not terminate after ~37 minutes.

---

*note*: `Ẇ§` may be replaced with `ÄÐƤẎ`. It may be more efficient.

# Answer
> 1 votes
# APL(NARS), chars 758, bytes 1516

```
r←H w;i;k;a;m;j
   r←⊂,w⋄→0×⍳1≥k←↑⍴w⋄a←⍳k⋄j←i←1⋄r←⍬⋄→C
A: m←i⊃w⋄→B×⍳(i≠1)∧j=m⋄r←r,m,¨∇w[a∼i]⋄j←m
B: i+←1
C: →A×⍳i≤k

G←{H⍵[⍋⍵]}

r←a d w;i;j;k;b;c
   k←↑⍴w ⋄b←⍬⋄r←0 ⋄j←¯1
A: i←1⋄j+←1⋄→V×⍳(i+j)>k
B: →A×⍳(i+j)>k⋄c←+/w[i..(i+j)]⋄→0×⍳∼c∊a⋄→C×⍳c∊b⋄b←b,c
C: i+←1⋄→B
V: →0×⍳∼a⊆b
   r←1

r←a F w;k;j;b;m;i;q;x;y;c;ii;kk;v;l;l1;i1;v1
   w←w[⍋w]⋄r←a⍴w[1]⋄l←↑⍴w⋄k←w[l]⋄m←8⌊a-2⋄b←¯1+(11 1‼m)⋄j←2⋄i←1⋄x←↑⍴b⋄i1←0⋄v1←⍬
I: i1+←1⋄l1←w[l]-w[l-i1]⋄v1←v1,w[1+l-i1]-w[l-i1]⋄→I×⍳(l1=i1)∧l>i1⋄→B
E: r←,¯1⋄→0
F: i←1⋄q←((1+(a-2)-m)⍴0),(m⍴1),0⋄r+←q
A:   i+←1⋄j+←1⋄→E×⍳j>4000
B:   →F×⍳i>x⋄q←((1+(a-2)-m)⍴0),b[i;],0⋄q+←r⋄v←q[1..(a-1)]⋄→A×⍳0>k-y←+/v
   q[a]←k-y⋄→A×⍳l1<q[a]⋄→A×⍳∼q⊆w⋄→A×⍳∼l1∊q⋄→A×⍳∼v1⊆⍦q⋄c←G q∼⍦v1⋄ii←1⋄kk←↑⍴c⋄→D
C:   →Z×⍳w d v1,ii⊃c⋄ii+←1
D:   →C×⍳ii≤kk
   →A
Z: r←v1,ii⊃c

```

The function G in G x (with the help of H function) would find all the permutations of x. The function d in x d y find if the y array generate following the exercise array x returning a Boolean value. The function F in x F y would return the array r of length x, such that y d r is true (=1) A little long as implementation, but it is this one that calculate all case in test less time... The last case for n=15 it run 20 second only... i have to say this not find many solutions, return just one solution (at last it seems so) in less time (not explored test for different inputs...) 16+39+42+8+11+11+18+24+24+54+11+12+7+45+79+69+12+38+26+72+79+27+15+6+13(758)

```
  6 F (2, 3, 4, 5, 7, 8, 9, 10, 12, 14, 17, 22)
5 3 2 2 5 5
  6 F (2, 4, 6, 8, 10, 12, 16)
4 2 2 2 2 4
  6 F (1, 2, 3, 4, 6, 7, 8, 10, 14)
4 2 1 1 2 4
  10 F (1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 14, 15, 16, 17, 18, 19, 20, 23, 24, 25)
1 1 3 1 2 3 5 1 3 5
  15 F (1, 2, 3, 4, 6, 7, 8, 9, 10, 11, 13, 14, 15, 16, 17, 18, 20, 21, 22, 23, 24, 25, 26, 27, 28, 30, 31)
1 2 1 3 3 1 3 3 1 3 3 1 2 1 3
  ww←(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 14, 15, 16, 17, 18, 19, 20, 23, 24, 25)
  ww≡dx 1 1 3 1 2 3 5 1 3 5
1

```

---
Tags: code-golf, array
---


# Question
Title: Can the number be split into powers of 2?
Yesterday while playing with my kid I noticed the number in his toy train:

So we have $$4281$$ that can be split into $$4-2-8-1$$ or $$2^2-2^1-2^3-2^0$$

So simple challenge: given a non-negative number as input, return consistent truthy and falsey values that represent whether or not the string representation of the number (in base 10 and without leading zeroes) can be somehow split into numbers that are powers of 2.

Examples:

```
4281      truthy (4-2-8-1)
164       truthy (16-4 or 1-64)
8192      truthy (the number itself is a power of 2)
81024     truthy (8-1024 or 8-1-02-4)
101       truthy (1-01)
0         falsey (0 cannot be represented as 2^x for any x)
1         truthy
3         falsey
234789    falsey
256323    falsey (we have 256 and 32 but then 3)
8132      truthy (8-1-32)

Tests for very large numbers (not really necessary to be handled by your code):
81024256641116  truthy (8-1024-256-64-1-1-16)
64512819237913  falsey

```

This is , so may the shortest code for each language win!

# Answer
# 05AB1E, ~~9~~ 8 bytes

```
Ýos.œåPZ

```

-1 byte thanks to *@Emigna* by using `Z` (max) for the list of 0s and 1s to mimic an `any` command for `1` (truthy).

Try it online or verify all test cases. (NOTE: The `т` in the header is `100` to only get the first 100 power of 2 numbers, instead of the first input amount of power of 2 numbers. It works with the input amount of power of 2 as well, but is pretty inefficient and might timeout on TIO if the input is large enough.)

**Explanation:**

```
Ý            # Create a list in the range [0,n], where n is the (implicit) input
             # (or 100 in the TIO)
             #  i.e. 81024 → [0,1,2,3,...,81024]
 o           # Raise 2 to the `i`'th power for each `i` in the list
             #  → [1,2,4,8,...,451..216 (nr with 24391 digits)]
  s          # Swap to take the input
   .œ        # Create each possible partition of this input
             #  i.e. 81024 → [["8","1","0","2","4"],["8","1","0","24"],...,["8102","4"],["81024"]]
     å       # Check for each if it's in the list of powers of 2
             #  → [[1,1,0,1,1],[1,1,0,0],...,[0,1],[0]]
      P      # Check for each inner list whether all are truthy
             #  → [0,0,1,0,0,0,0,1,0,0,0,0,0,0,0,0]
       Z     # Take the maximum (and output implicitly)
             #  → 1 (truthy)

```
> 11 votes

# Answer
# JavaScript (Node.js), 54 bytes

```
f=(v,o=10)=>v&v-1|!v?v>o?f(v%o)&f(v/o|0)|f(v,o*10):0:1

```

Try it online!
> 8 votes

# Answer
# JavaScript (Node.js), ~~69~~ ~~64~~ 58 bytes

```
f=(x,m=10,q=!(x%m&x%m-1|!x))=>x<m?q:q&&f(x/m|0)||f(x,10*m)

```

Try it online!

Input as number. The logic part is quite convoluted, so no idea how to untangle it and get rid of `q`.

-11 bytes by golfing the power-of-2 check.
> 6 votes

# Answer
# Jelly, 9 bytes

```
ŒṖḌl2ĊƑ€Ẹ

```

Check out the test suite!

---

### Alternative

Doesn't work for the large test cases due to precision issues.

```
ŒṖḌæḟƑ€2Ẹ

```

Check out the test suite!

### How?

**Program I**

```
ŒṖḌl2ĊƑ€Ẹ     Full program. N = integer input.
ŒṖ            All possible partitions of the digits of N.
  Ḍ           Undecimal (i.e. join to numbers).
   l2         Log2. Note: returns (-inf+nanj) for 0, so it doesn't fail.
     ĊƑ€      For each, check if the logarithm equals its ceil.
        Ẹ     Any. Return 0 if there are no truthy elements, 1 otherwise.

```

**Program II**

```
ŒṖḌæḟƑ€2Ẹ     Full program. N = integer input.
ŒṖ            All possible partitions of the digits of N.
  Ḍ           Undecimal (i.e. join to numbers).
     Ƒ€       For each partition, check whether its elements are invariant under...
   æḟ  2      Flooring to the nearest power of 2.
        Ẹ     Any. Return 0 if there are no truthy elements, 1 otherwise.

```
> 6 votes

# Answer
# JavaScript (Node.js), ~~75~~ 69 bytes

-6 bytes thanks @Arnauld. At most 32-bit support

```
f=x=>+x?[...x].some((_,i)=>(y=x.slice(0,++i))&~-y?0:f(x.slice(i))):!x

```

Try it online!

Input as a string.
> 5 votes

# Answer
# Python 2, ~~72~~ 70 bytes

```
f=lambda n,m=10:n>=m/10and(n%m&n%m-1<1and(n/m<1or f(n/m))or f(n,m*10))

```

Try it online!
> 5 votes

# Answer
# JavaScript, 59 bytes

```
s=>eval(`/^(${(g=x=>x>s?1:x+'|0*'+g(x+x))(1)})+$/`).test(s)

```

Try it online!

Builds a regex like `/^(1|0*2|0*4|0*8|0*16|0*32|…|0*1)+$/` of powers of 2, and tests it on `s`.

Only works up to the precision of JavaScript numbers, of course: eventually the terms in the regex will look like `1.2345678e30` (or `Inf`). But since powers of 2 are easy to represent accurately in floating-point, they'll never be *wrong* integers, which would be more disqualifying, I think.

@tsh saved 14 bytes. Neato!
> 5 votes

# Answer
# Python 2, 85 bytes

```
f=lambda n:bin(int(n)).count('1')==1or any(f(n[:i])*f(n[i:])for i in range(1,len(n)))

```

Try it online!
> 4 votes

# Answer
# Perl 6, ~~28~~ ~~24~~ 23 bytes

*-4 bytes thanks to Jo King*

```
{?/^[0*@(2 X**^32)]+$/}

```

Try it online!

Handles powers up to 231.
> 4 votes

# Answer
# APL(NARS), 154 chars, 308 bytes

```
∇r←f w;g;b;z;k
   g←{⍵≤0:1⋄t=⌊t←2⍟⍵}⋄→A×⍳∼w≤9⋄r←g w⋄→0
A: z←w⋄b←0⋄k←1
B: b+←k×10∣z⋄z←⌊z÷10
   →C×⍳∼g b⋄r←∇z⋄→0×⍳r
C: k×←10⋄→B×⍳z≠0
   r←0
∇
h←{⍵=0:0⋄f ⍵}

```

The function for the exercise it is h. The algorithm not seems exponential or factorial... test:

```
  h¨ 4281 164 8192 81024 101
1 1 1 1 1
  h¨ 0 1 3 234789 256323 8132
0 1 0 0 0 1
  h 81024256641116
1
  h 64512819237913
0

```
> 3 votes

# Answer
# Python 2, 57 bytes

```
f=lambda n,k=10:k<11*n>n%k&n%k-1<(n<k)|f(n/k)|f(n,10*k)*n

```

Try it online!
> 3 votes

# Answer
# Python 2, 86 bytes

```
lambda n:re.match('^(%s)*$'%'|'.join('0*'+`1<<k`for k in range(n)),`n`)and 0;import re

```

Try it online!
> 2 votes

# Answer
# Ruby, 55 bytes

```
->n{a=*b=1;a<<b*=2until b>n;n.to_s=~/^(0*(#{a*?|}))*$/}

```

Try it online!

Output is `0` if true and `nil` if false.
> 2 votes

# Answer
# Ruby, 49 bytes

```
->n{n.to_s=~/^(0*(#{(0..n).map{|x|2**x}*?|}))*$/}

```

Try it online!

Only works in theory. Takes forever for large values of `n`
> 2 votes

# Answer
# Red, 212 211 bytes

```
func[n][g: func[x][(log-2 do x)% 1 = 0]repeat i 2 **((length? s: form n)- 1)[b: a:
copy[] k: i foreach c s[append b c if k % 2 = 0[alter a g rejoin b
b: copy[]]k: k / 2]append a g form c if all a[return on]]off]

```

Try it online!

Another long submission, but I'm not comletely dissatisfied, because there is no built-in for finding all substrings in Red.

## More readable:

```
f: func [ n ] [
    g: func [ x ] [ (log-2 do x) % 1 = 0 ]
    repeat i 2 ** ((length? s: form n) - 1) [
        b: a: copy []
        k: i
        foreach c s [
            append b c
            if k % 2 = 0 [
                append a g rejoin b
                b: copy []
            ]
            k: k / 2
        ]
        append a g form c
        if all a[ return on ]
    ]
    off
]

```
> 2 votes

# Answer
# PHP, 101 bytes

Can´t seem to get this below 100; but I could get it *to* 100 if `101` was a falsy case.

```
function f($s){for($x=.5;$s>=$x*=2;)if(preg_match("/^$x(.*)$/",$s,$m)?!~$m[1]||f(+$m[1]):0)return 1;}

```

returns \\$NULL\\$ for falsy and \\$1\\$ for truthy. Try it online.

**variations:**

```
for($x=.5;$s>=$x*=2;)
while($s>=$x=1<<$i++)   # yields notices "undefined variable $i"

?!~$m[1]||f(+$m[1]):0
?~$m[1]?f(+$m[1]):1:0

```

# PHP 5 or older, 95 bytes

```
function f($s){while($s>=$x=1<<$i++)if(ereg("^$x(.*)$",$s,$m)?$m[1]>""?f(+$m[1]):1:0)return 1;}

```
> 2 votes

# Answer
# Axiom, 198 bytes

```
G(a)==(a<=1=>2>1;x:=log_2 a;x=floor x)
F(n)==(n<=9=>G n;z:=n;b:=0;k:=1;repeat(b:=b+k*(z rem 10);z:=z quo 10;if G b and F z then return 2>1;k:=k*10;z<=0=>break);1>1)
H(n:NNI):Boolean==(n=0=>1>1;F n)

```

ungolf and test

```
g(a)==(a<=1=>2>1;x:=log_2 a;x=floor x)
f(n)==
   n<=9=>g n
   z:=n;b:=0;k:=1
   repeat
      b:=b+k*(z rem 10);z:=z quo 10;
      if g b and f z then return 2>1
      k:=k*10
      z<=0=>break
   1>1
h(n:NNI):Boolean==(n=0=>1>1;f n)

(15) -> [[i,h i] for i in [4281,164,8192,81024,101]]
   (15)  [[4281,true],[164,true],[8192,true],[81024,true],[101,true]]
                                                      Type: List List Any
(16) -> [[i,h i] for i in [0,1,3,234789,256323,8132]]
   (16)  [[0,false],[1,true],[3,false],[234789,false],[256323,false],[8132,true]]
                                                      Type: List List Any
(17) -> [[i,h i] for i in [81024256641116, 64512819237913]]
   (17)  [[81024256641116,true],[64512819237913,false]]
                                                      Type: List List Any
(18) -> h 44444444444444444444444444
   (18)  true
                                                            Type: Boolean
(19) -> h 44444444444444444128444444444
   (19)  true
                                                            Type: Boolean
(20) -> h 4444444444444444412825444444444
   (20)  false
                                                            Type: Boolean
(21) -> h 2222222222222244444444444444444412822222222222210248888888888882048888888888888888
   (21)  true
                                                            Type: Boolean
(22) -> h 222222222222224444444444444444441282222222222225128888888888882048888888888888888
   (22)  true
                                                            Type: Boolean

```
> 2 votes

# Answer
# Powershell, 56 bytes

```
$x=(0..63|%{1-shl$_})-join'|0*'
"$args"-match"^(0*$x)+$"

```

Test script:

```
$f = {

    $x=(0..63|%{1-shl$_})-join'|0*'
    "$args"-match"^(0*$x)+$"

}

@(
    ,(4281            ,$true)
    ,(164             ,$true)
    ,(8192            ,$true)
    ,(81024           ,$true)
    ,(101             ,$true)
    ,(0               ,$false)
    ,(1               ,$true)
    ,(3               ,$false)
    ,(234789          ,$false)
    ,(256323          ,$false)
    ,(8132            ,$true)
    ,("81024256641116"  ,$true)
    ,("64512819237913"  ,$false)
) | % {
    $n, $expected = $_
    $result = &$f $n
    "$($result-eq$expected): $result <- $n"
}

```

Output:

```
True: True <- 4281
True: True <- 164
True: True <- 8192
True: True <- 81024
True: True <- 101
True: False <- 0
True: True <- 1
True: False <- 3
True: False <- 234789
True: False <- 256323
True: True <- 8132
True: True <- 81024256641116
True: False <- 64512819237913

```

Explanation:

Builds a regex like `^(0*1|0*2|0*4|0*8|0*16|0*32|…)+$` of powers of 2, and tests it on arguments.
> 2 votes

# Answer
# Japt `-!`, 12 bytes

Takes input as a string.

```
ÊÆòXÄÃex_&ZÉ

```

Try it
> 1 votes

# Answer
## C# 157 bytes

```
bool P(string s,int i=1)=>i>=s.Length?((Func<ulong,bool>)((x)=>(x!=0)&&((x&(x-1))==0)))(ulong.Parse(s)):(P(s,i+1)||(P(s.Substring(0,i))&&P(s.Substring(i))));

```

You can Try it online
> 1 votes

# Answer
# APL(NARS), 70 chars, 140 bytes

```
P←{k←↑⍴⍵⋄x←11 1‼k k⋄y←⍵⋄∪{x[⍵;]⊂y}¨⍳↑⍴x}
f←{⍵=0:0⋄∨/∧/¨y=⌊y←2⍟⍎¨¨P⍕⍵}

```

test:

```
  f¨ 4281 164 8192 81024 101
1 1 1 1 1
  f¨ 0 1 3 234789 256323 8132
0 1 0 0 0 1
  f 126
0

```

i not try to do other more big numbers... i have to note that P is not normal partition, but it is one partition where all element are subset that have member all consecutive, for example

```
  ⎕fmt P 'abc'
┌4──────────────────────────────────────────────────┐
│┌1─────┐ ┌2─────────┐ ┌2─────────┐ ┌3─────────────┐│
││┌3───┐│ │┌2──┐ ┌1─┐│ │┌1─┐ ┌2──┐│ │┌1─┐ ┌1─┐ ┌1─┐││
│││ abc││ ││ ab│ │ c││ ││ a│ │ bc││ ││ a│ │ b│ │ c│││
││└────┘2 │└───┘ └──┘2 │└──┘ └───┘2 │└──┘ └──┘ └──┘2│
│└∊─────┘ └∊─────────┘ └∊─────────┘ └∊─────────────┘3
└∊──────────────────────────────────────────────────┘

```

note that is absent the element ((ac) (b)) or better ,,¨('ac')'b'

```
  ⎕fmt ,,¨('ac')'b'
┌2─────────┐
│┌2──┐ ┌1─┐│
││ ac│ │ b││
│└───┘ └──┘2
└∊─────────┘

```
> 1 votes

# Answer
# POSIX ERE, 91 bytes

```
(0*([1248]|16|32|64|128|256|512|1024|2048|4096|8192|16384|32768|65536|131072|262144|524288))+

```

This is totally cheating, based on the text *large numbers (not really necessary to be handled by your code)* in the question; it handles all values in the size range of the examples. Obviously can be extended up to full range of 32- or 64-bit integer types at the expense of size. I mainly wrote it as a demonstration of how the problem naturally fits the tool. A fun exercise would be rewriting it as a program that generates the ERE for arbitrary range then matches against it.
> 1 votes

# Answer
# C (gcc), `-DA=asprintf(&c,` \+ 108 = 124 bytes

```
p,c;f(a,i){c="^(0*(1";for(i=0;i<31;)A"%s|%d",c,1<<++i);A"%s))+$",c);regcomp(&p,c,1);a=!regexec(&p,a,0,0,0);}

```

Try it online!

This builds a regex of the powers of 2 up to 2\**32, and then matches the input string against it.
> 1 votes

# Answer
# JavaScript (Node.js), 56 bytes

```
f=(x,c=v=1)=>x<v?x.match('^('+c+')+$'):f(x,c+'|'+(v*=2))

```

Try it online!
> 0 votes

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


title: Optimize my wings order

text:
# Question
Title: Optimize my wings order
This tweet lists the possible orders for Wings of a Chinese restaurant1:

When ordering Pizza I usually calculate what size gives me the best Pizza-price ratio which is a simple calculation. However minimizing the price of an order at this restaurant isn't such a simple task, so I'd like to be prepared for my next order there.

# Challenge

Given an integer greater or equal to \\$4\\$, your task is to return one possible order which minimizes the price (overall cheapest) and the number of deals.

# Example

If I were to order \\$100\\$ Wings, it turns out the best bargain will cost \\$$111.20\\$. However there are multiple orders which will cost that amount, namely:

```
[50,50],[25,25,50],[25,25,25,25]

```

Since the first order will use the least amount of deals (\\$2\\$) the result will be `[50,50]`.

# Rules

* Input will be some integer \\$n \geq 4\\$
* Output will be a list/array/... of order sizes that sum up to \\$n\\$ and minimize the order's price
    + you may choose to return all possible orders

# Testcases

```
4 -> [4]  (4.55)
23 -> [23]  (26.10)
24 -> [6,18],[9,15],[12,12]  (27.20)
31 -> [6,25]  (34.60)
32 -> [4,28],[6,26],[7,25]  (35.75)
33 -> [4,29],[5,28],[6,27],[7,26],[8,25]  (36.90)
34 -> [6,28],[9,25]  (38.00)
35 -> [35]  (39.15)
125 -> [125]  (139.00)
200 -> [25,50,125]  (222.40)
201 -> [26,50,125]  (223.55)
250 -> [125,125]  (278.00)
251 -> [26,50,50,125]  (279.15)
418 -> [15,28,125,125,125],[18,25,125,125,125]  (465.20)
1001 -> [26,50,50,125,125,125,125,125,125,125]  (1113.15)
12345 -> [15,80,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125],[25,70,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125],[45,50,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125,125]  (13728.10)

```

**Note:** These testcases list *all* possible outputs including the price, you're only required to output *one* and you're **not** required to output the price!

---

1: You can find the data as a CSV here.

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

Returns the order as a space-separated string.

```
f=n=>n?(x=n>128|n==125?125:n>50?n<54?25:n-70?302256705>>n-80&n>79&n<109?80:50:n:n-24&&n-49?n<31|n%5<1?n:25:9)+' '+f(n-x):''

```

Try it online!

## How?

Given a number \\$n\\$ of wings, we recursively apply the following strategy.

### High values: \\$n\>128\\$ or \\$n=125\\$

For high values, our best option is to buy \\$125\\$ wings. So that's what we're doing as long as \\$n\\$ is greater than or equal to \\$129\\$ or when \\$n\\$ is exactly equal to \\$125\\$.

We can't do that for \\$125 \< n \< 129\\$ because we'd be left with less than \\$4\\$ wings to buy, which is not possible.

### Low values: \\$n\<31\\$

For \\$n\<31\\$, the best deal is to buy all remaining wings at once, except for \\$n=24\\$ which must be purchased as either \\$2\times 12\\$, \\$18+6\\$ or \\$15+9\\$. We arbitrarily buy \\$9\\$ wings in that case.

### Range \\$31 \le n \le 50\\$

In this range, buying \\$25\\$ wings usually leads to an optimal order. But the following exceptions apply:

* If \\$n\\$ is a multiple of \\$5\\$, we must buy all remaining wings at once.
* If \\$n=49\\$, the best deals are \\$40+9\\$ and \\$28+21\\$. We arbitrarily buy \\$9\\$ wings in that case.

### Range \\$51 \le n \le 53\\$

We can't buy \\$50\\$ wings in that range or we'll be left with less than \\$4\\$ wings. Our best option is to buy \\$25\\$ of them instead. (We *could* buy \\$2\times26\\$ wings for \\$n=52\\$, but buying \\$25+27\\$ is just as good.)

### Range \\$54 \le n \le 128\\$ with \\$n \neq 125\\$

In this range, buying \\$50\\$ wings usually leads to an optimal order. But the following exceptions apply:

* If \\$n=70\\$, we must buy all of them at once.
* If \\$n\\$ is in \\$\\{80,86,89,92,98,105,108\\}\\$, we must buy \\$80\\$ wings. These values are encoded with the following bitmask, where the least significant bit is mapped to \\$80\\$ and the most significant one to \\$108\\$:

$$10010000001000001001001000001\_{(2)} = 302256705\_{(10)}$$

# Answer
> 4 votes
# JavaScript (Node.js), ~~112~~ ~~108~~ ~~106~~ 105 bytes

```
f=n=>n?(x=n>128|n==125?125:n>53&n!=70?1629>>n/3+6&n<99==n%3/2?80:50:~n%25?n>30&&n%5?25:n:9)+' '+f(n-x):''

```

Try it online!

Optimized from Arnauld's answer

# Differences

* 51≤n≤53 is merged into 31≤n≤50 (8 bytes save)
* Rewrite the bitmap (3 bytes save)
* Rearrange some logic (~~4~~ ~~6~~ 7 bytes saved)

# Answer
> 2 votes
# Retina 0.8.2, ~~160~~ 155 bytes

```
.+
$*
{`\b(1{80}(?=((111){2,6}|1{25}|1{28})?$)|1{70}$|1{9}(?=.{15}$|.{40}$)|(1{5}){6,9}$|1{26,29}$|1{4,23}$|1{125}|1{50}|1{25})+$
$1,$&
(1+),\1(1*)$
$.1,$2

```

Try it online! Link includes header that tests all values from \\$ n \\$ down to 1, remove it if you only want to test \\$ n \\$ itself. Uses @Arnauld's algorithm. Edit: Saved 5 bytes by purchasing 95 wings as 80 + 15 instead of 50 + 45. Explanation:

```
.+
$*

```

Convert to unary.

```
{`

```

Repeat until no more deals can be purchased.

```
{`\b(1{80}(?=((111){2,6}|1{25}|1{28})?$)|1{70}$|1{9}(?=.{15}$|.{40}$)|(1{5}){6,9}$|1{26,29}$|1{4,23}$|1{125}|1{50}|1{25})+$
$1,$&

```

Find a way of purchasing deals and capture and duplicate one of the deals.

```
(1+),\1(1*)$
$.1,$2

```

Convert the captured deal to decimal and subtract it from \\$ n \\$.

Deals are purchased under the following conditions:

```
1{80}(?=((111){2,6}|1{25}|1{28})?$)

```

Purchase 80 wings if that leaves 0, 6, 9, 12, 15, 18, 25 or 28 wings.

```
1{70}$

```

Purchase 70 wings if that's all we need.

```
1{9}(?=.{15}$|.{40}$)

```

Purchase 9 wings if that leaves 15 or 40 wings.

```
(1{5}){6,9}$

```

Purchase 30, 35, 40 or 45 wings if that's all we need.

```
1{26,29}$

```

Purchase 26, 27, 28 or 29 wings if that's all we need.

```
1{4,23}$

```

Purchase 4 to 23 wings if that's all we need.

```
1{125}|1{50}|1{25}

```

Purchase 125, 50 or 25 wings if we can and if we can still purchase more wings exactly. Note that we have these options at the end of the alternation so that the exact purchases are tested first.

---
Tags: code-golf, optimization, integer-partitions
---