# Question
Title: Largest and smallest values from concatenated integers
This problem is from Five programming problems every Software Engineer should be able to solve in less than 1 hour which itself is an interesting read. The first few problems are trivial, but the fourth one can be a bit more interesting.

> Given a list of integers separated by a single space on standard input, print out the largest and smallest values that can be obtained by concatenating the integers together on their own line.

For example:

Input:

```
5 56 50

```

Output:

```
50556
56550

```

Various points of order:

* The order of the results are smallest then largest.
* *Only* the smallest and largest values may be printed out (iterating over all the variations and printing them out isn't valid).
* There will always be two or more integers in the list.
* It is possible for the largest and smallest results to be the same. In the case of input `5 55`, the number `555` should be printed twice.
* The integers are not necessarily distinct. `5 5` is valid input.
* Leading `0`s on integers are ***not*** valid input. You will ***not*** need to account for `05 55`.

As this is code golf, shortest entry wins.

# Answer
# CJam, ~~14~~ 13 bytes

```
qS/e!:s$(N@W=

```

Pretty straight forward. This is how it works:

```
qS/                  e# Split the input on spaces
   e!                e# Get all permutations of the input numbers
     :s              e# Join each permutation order into a single string
       $             e# Sort them. This sorts the strings based on each digit's value
        (N@W=        e# Choose the first and the last out of the array separated by '\n'

```

Try it online here
> 10 votes

# Answer
# Pyth, 14 13 bytes

```
hJSmsd.pcz)eJ

```

Generates all permutations and sorts them, printing the first and last element.
> 5 votes

# Answer
# Python 2, ~~104~~ 99 bytes

Yep.

```
from itertools import*;z=[''.join(x)for x in permutations(raw_input().split())];print min(z),max(z)

```

Edit: thanks to xnor for -5 bytes!
> 4 votes

# Answer
# Mathematica, ~~64~~ 58 bytes

```
Print/@Sort[""<>#&/@Permutations@StringSplit@#][[{1,-1}]]&

```

This defines an unnamed function taking a string and printing the two lines. It's pretty straightforward as the others: get all permutations, join them together, sort them and print the first and last result.

Six bytes saved thanks to alephalpha.
> 3 votes

# Answer
# JavaScript (ES6) ~~54 72~~ 85

~~That's easier than it seems. Just sort them lexicographically. The good news is: that's exactly how plain javascript sort works.~~Well ... no, that's wrong ... still a (more convoluted) lexicograph compare can do the job.

Note: having a and b numeric, a+\[b\] is a shortcut for a+''+b, as we need a string concatenation and not a sum.
Note 2: the newline inside \`\` is significant and must be counted

**Edit** Don't argue with a moderator (...just kidding)

**Edit2** Fixed I/O format using popups (see Default for Code Golf: Input/Output methods)

```
// Complete program with I/O
// The sorting function is shorter as input are strings

alert((l=prompt().split(' ')).sort((a,b)=>a+b>b+a).join('')+`
`+l.reverse().join(''))

// Testable function (67 chars)
// With an integer array parameter, the sorting function must convert to string

F=l=>(l.sort((a,b)=>a+[b]>b+[a]).join('')+`
`+l.reverse().join(''))

```

**Test** In Firefox / FireBug console

```
F([50, 2, 1, 9])
F([5,56,50])
F([52,36,526])
F([52,36,525])
F([52,36,524]

```

> 12509
> 95021
>
> 50556
> 56550
>
> 3652526
> 5265236
>
> 3652525
> 5255236
>
> 3652452
> 5252436
> 2 votes

# Answer
## J, 34 <sup>~~36~~, ~~42~~</sup> bytes

simple brute force:

```
h=:3 :'0 _1{/:~;"1":&.>y A.~i.!#y'

h 5 50 56
50556
56550

h 50 2 1 9
12509
95021

```
> 2 votes

# Answer
# Haskell, 98 bytes

```
import Data.List
g=sort.map concat.permutations.words
h i=unlines[g i!!0,last$g i]
main=interact h

```

Split input string at spaces, concatenate every permutation and sort. Print first and last element.
> 1 votes

# Answer
# Julia, 77 bytes

```
v->(Q=extrema([int(join(x)) for x in permutations(v)]);print(Q[1],"\n",Q[2]))

```

This creates an unnamed function that accepts a vector as input and prints the minimum and maximum of the permutations of the joined elements. To call it, give it a name, e.g. `f=v->...`.

Ungolfed + explanation:

```
function f(v)
    # Create an integer vector of the joined permutations using comprehension,
    # then get the minimum and maximum as a tuple using extrema().

    Q = extrema([int(join(x)) for x in permutations(v)])

    # Print the minimum and the maximum, separated by a newline.
    print(Q[1], "\n", Q[2])
end

```

Suggestions are welcome!
> 1 votes

# Answer
# Javascript (*ES6*) 134

Sadly, there's no built-in permutation function in JS :(

```
f=(o,y,i,a)=>y?o.concat(a[1]?a.filter((k,j)=>j^i).reduce(f,[]).map(z=>y+z):y):(q=o.split(' ').reduce(f,[])).sort().shift()+`
`+q.pop()
```

```
<!-- Snippet Demo (Firefox only) -->

<input id="input" value="5 56 50" />
<input type="button" onclick="output.innerHTML=f(input.value)" value="Run" />
<pre id="output"></pre>
```
> 1 votes

# Answer
## R, 59 bytes

```
write(range(combinat:::permn(scan(),paste,collapse="")),"")

```
> 1 votes

# Answer
# Ruby 75

Not my 'native' language, but one I thought I'd give a try at... thus this could (possibly) use some golfing tips. Still, not a bad entrant.

```
puts STDIN.read.split(" ").permutation.map{|x|x.join}.sort.values_at(0,-1)

```

I wouldn't say it is *elegant* other that everything is built in to the language. It should be fairly obvious exactly how this works.
> 1 votes

# Answer
# Perl, ~~79~~ 70B (68+2)

`use Math::Combinatorics;say for(sort map{join'',@$_}permute@F)[0,-1]`

Call with `echo 13 42 532 3 6|perl -M5.10.0 -an scratch.pl`. There's a +2 byte penalty for `-an`. Shame about the length of the module name...
> 1 votes

# Answer
# 05AB1E, 8 bytes

```
#œJ{¬sθ»

```

Try it online.

**Explanation:**

```
#         # Split the (implicit) input by spaces
 œ        # Get all permutations of this list
  J       # Join each permutation together to a single string
   {      # Sort this list
    ¬     # Push the first item (without popping the list)
     s    # Swap to get the list again
      θ   # Pop and push its last item
       »  # And join all (both) values on the stack by newlines
          # (after which the result is output implicitly)

```
> 1 votes

# Answer
# Scala, 90 bytes

```
val x=Console.in.readLine.split(" ").permutations.map(_.mkString).toSeq
print(x.min,x.max)

```

Try it online!
> 1 votes

# Answer
# JavaScript (ES6), 85 bytes

```
F=a=>(c=a.split(" ").sort((b,a)=>b+a-(a+b)),`${c.join("")}
${c.reverse().join("")}`)

```

**usage:**

```
F("50 2 1 9")
/*
    12509
    95021
*/

```
> 0 votes

# Answer
# Stax, 11 bytes

```
ú∙n90≤╣*.vâ

```

Run and debug it

Link is to unpacked version of code.

## Explanation

```
L|T{$mc|MP|mp implicit input
L             put all inputs in a list
 |T           get the unique orders of the list of inputs
   {$m        convert each list to string
      c       duplicate the array of strings
       |mP    print the minimum element
          |mp print the maximum element

```
> 0 votes

# Answer
# Jelly, 6 bytes

```
Œ!VṢ.ị

```

Try it online!

Input and output as lists of integers. +3 bytes to input with spaces and output with newlines

## How it works

```
Œ!VṢ.ị - Main link. Takes a list L on the left e.g. [5, 56, 50]
Œ!     - All permutations of L                      [[5, 56, 50], [5, 50, 56], [56, 5, 50], [56, 50, 5], [50, 5, 56], [50, 56, 5]]
  V    - Concatenate each into numbers              [55650, 55056, 56550, 56505, 50556, 50565]
   Ṣ   - Sort                                       [50556, 50565, 55056, 55650, 56505, 56550]
    .ị - Take the first and last elements           [56550, 50556]

```
> 0 votes

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


title: Golf me a polygonal loader

text:
# Question
Title: Golf me a polygonal loader
Codidact post, CGCC Sandbox, Codidact Sandbox

Given three positive integers as input, animate an ascii-art polygonal loading symbol on the screen.

## Intro

You will be given three inputs, \\$n\\$, \\$l\\$, and \\$d\\$...

\\$n\\$ (one of \\$3\\$, \\$4\\$, \\$6\\$, or \\$8\\$), is the number of sides of a polygon:

```
                           * * *
                          *     *
                * * *    *       *
               *     *   *       *
  *    * * *  *       *  *       *
 * *   *   *   *     *    *     *
* * *  * * *    * * *      * * *

```

\\$l\\$ is the side length to use. (The above all use \\$l = 3\\$, the minimum possible value).

You may use any printable ASCII character other than space instead of `*`.

\\$d\\$ is the load length and is less than the perimeter.

The task is to create a loading animation as follows:

1. Make the first frame of the animation by starting at any one of the topmost corners and drawing the perimeter until its length is \\$d\\$.
2. Make the next frame by shifting this partial perimeter by 1 clockwise.
3. Repeat step 2 ad-infinitum.

For example, \\$n=3,l=3,d=4\\$ would result in the following steps:

```
  *                          *       *        *
   *  ->    *  ->  *    ->  *   ->  * *  ->  * *  -> . . .
  * *    * * *    * * *    * *     *            *

```

## Example

Here is a solution made by Hakerh400: Try It Online!

## Further details(important):

* You are guaranteed that \\$n∊(3,4,6,8)\\$
* You are guaranteed that \\$l≥3.\\$ You are guaranteed that \\$d\<(l-1)×n.\\$
* There must be a delay of at least 0.1 s between each step. You can have a delay of up to 10 seconds.
* Your language is allowed to output a list of steps infinitely if and only if it cannot clear the screen or do something similar.
* If so, there must be at least 2 newlines between each step.
* This is not .

## Scoring

This is . Shortest answer in each language wins.

# Answer
> 3 votes
# JavaScript (V8), ~~353~~ 318 bytes

```
f=(n,l,d,o=0)=>{w=[...{3:'330231',4:'42240220',6:'423313021131',8:'4233231302112131'}[n]]
a=Array(3*l).fill().map(_=>Array(4*l).fill` `)
x=n==4?0:l,y=0
for(i=0;i<d+o;++i){a[y][x]=i>=o?'*':' '
j=~~(i/(l-1))%n*2
x+=w[j]-2
y+=w[j+1]-2}(c=console).clear()
c.log(a.join`
`.replace(/,/g,''))
setTimeout(_=>f(n,l,d,o+1),100)}

```

Try it online!

On the tio.run it displays all output instantly, but in the browser console it animates as it should.

```
f=(n,l,d,o=0)=>{w=[...{3:'330231',4:'42240220',6:'423313021131',8:'4233231302112131'}[n]]
a=Array(3*l).fill().map(_=>Array(4*l).fill` `)
x=n==4?0:l,y=0
for(i=0;i<d+o;++i){a[y][x]=i>=o?'*':' '
j=~~(i/(l-1))%n*2
x+=w[j]-2
y+=w[j+1]-2}(c=console).clear()
c.log(a.join`
`.replace(/,/g,''))
setTimeout(_=>f(n,l,d,o+1),100)}
f(3,3,4)

```

# Answer
> 3 votes
# JavaScript (ES8), 265 bytes

```
(n,l,d)=>setInterval(_=>(g=i=>i<q?g(i+1,(m[y-=634%~(D+=i%l?0:+("02112122230"[(n*12^i/l)%43%29]||1))-2>>1]=m[y]||[...''.padEnd(l*4)])[x-=D<4?D-1:5-D]=(i+j)%q<d?0:" "):C.log(m.reverse().map(r=>r.join``).join`
`))(y=D=!++j,(C=console).clear(x=l*3,m=[])),j=100,q=n*--l)

```

Try it online!

### Snippet

```
f=

(n,l,d)=>setInterval(_=>(g=i=>i<q?g(i+1,(m[y-=634%~(D+=i%l?0:+("02112122230"[(n*12^i/l)%43%29]||1))-2>>1]=m[y]||[...''.padEnd(l*4)])[x-=D<4?D-1:5-D]=(i+j)%q<d?0:" "):C.log(m.reverse().map(r=>r.join``).join`
`))(y=D=!++j,(C=console).clear(x=l*3,m=[])),j=100,q=n*--l)

console.log = s => o.innerHTML = s; f(3, 5, 9)
```

```
<pre id="o"></pre>
```

# Answer
> 2 votes
# Charcoal, ~~69~~ 65 bytes

```
ＮθＮηＮζ≔⁰εＲＷφ¹«≦⊖εＦ§⪪”)″‴Byε=μχ？⟦⌕r”8θＦ⊖η«≦⊕ε✳Ｉκ⁺§ *‹﹪ε×⊖ηθζ× №04κ

```

Try it online! Link is to verbose version of code with 100× speed-up (`φ` replaced with `χ`) so that you can get results in a reasonable amount of time; each frame is separated by `␛ [2J␛ [0;0H`. Explanation:

```
ＮθＮηＮζ

```

Input `n`, `l` and `d` as numbers.

```
≔⁰ε

```

Keep track of how many frames have passed and which step we are on the current frame.

```
ＲＷφ¹«

```

Every second, run the rest of the code and refresh the screen.

```
≦⊖ε

```

Decrement the frame/step counter, so that each frame starts a step later than the previous.

```
Ｆ§⪪”)″‴Byε=μχ？⟦⌕r”8θ

```

Look up the direction vectors for the appropriate shape in a compressed string and loop over them.

```
Ｆ⊖η«

```

Loop over the length of each side.

```
≦⊕ε

```

Increment the frame/step counter.

```
✳Ｉκ⁺§ *‹﹪ε×⊖ηθζ× №04κ

```

Print a `*` if the frame/step counter is within the input length, plus a further space for a horizontal movement.

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


title: Maximum Concatenated Product

text:
# Question
Title: Maximum Concatenated Product
We are given a list of integers p1, ..., pk (not necessarily distinct) where each has a value between 1 and 9, inclusive. Using each of the p1, ..., pk exactly once, we can form concatenations of digits, to achieve a new list of numbers; we then output the product of this new list. The goal is to maximize this product by choosing the best concatenations of digits.

For example, we are given the list: 2 3 2 (separated by spaces). We can form the following concatenations:

* `2 3 2` (product of these concatenations is `12`)
* `23 2` (product is `46`)
* `32 2` (product is `64`)
* `22 3` (product is `66`)

Since the largest product that we can form of concatenations is 66, we output that.

Rules:

* There must be at least one multiplication (i.e., you cannot just concatenate all of the digits and output that).
* You cannot use any other operators other than multiplication, or insert parentheses, etc.
* Assume that the list of integers given is separated by spaces, and all integers have values between 1 and 9.

Shortest code (in bytes) wins!

Test cases:

Input: `1 2 3`; Output: `63` (i.e., `21*3`)

Input: `2 5 9`; Output: `468` (`52*9`)

Input: `1 2 3 4`; Output: `1312` (`41*32`)

# Answer
# CJam, ~~32~~ ~~28~~ ~~23~~ 12 bytes

```
0le!f{~*}:e>

```

Try it online in the CJam interpreter.

*Thanks to @user23013 for helping me save 16 whole bytes!*

# Idea

Permuting the characters in the input string divides it into integers (groups of consecutive digits) separated by spaces. By pushing a zero and then evaluating the permuted input string, we push two or more integers. Multiplying the topmost two will result either in the product of the input divided into exactly two integers or some suboptimal value.

# Code

```
 le!         e# Push all possible character permutations of the input.
0   f{  }    e# For each permutation:
             e#   Push 0, then the permuted string.
      ~      e#   Evaluate the string. Pushes one or more integers.
       *     e#   Multiply the two topmost integers.
         :e> e# Retrieve the greatest integer in the array.

```
> 9 votes

# Answer
# CJam, ~~36~~ 35 bytes

```
q~]_,([SL]m*{s},\e!\m*{z[s~]:*}%$W=

```

Pretty straight forward. Iterates over all possible combinations and sorts them by product. Then outputs the largest. All this, keeping in mind that at least 1 multiplication should be present.

Will add explanation soon.

Try it online here
> 2 votes

# Answer
# JavaScript (ES6) 125

**Edit** I think @oberon got it right : "each new digit must be concatenated to the smallest number"

I'll not change this answer stealing his idea. Implementation in ES6 would be 70 bytes (sign changed in comparison to compare as number and not strings)

```
f=l=>l.split(' ').sort().reverse().map(d=>-a>-b?a+=d:b+=d,a=b='')||a*b

```

**My solution**

```
f=l=>(i=>{for(r=0;a=b='',k=--i;r<a*b?r=a*b:0)for(v of l)k&1?a+=v:b+=v,k/=2})(1<<~-(l=l.split(' ').sort().reverse()).length)|r

```

As I said in comments, for each pair of numbers a,b, the product a\*b is less than the simple concatenation ab (=a\*10^(digits of b)+b). So it's better to avoid products and prefer concatenation, but as at least 1 product is requested, we have to build 2 numbers and multiply them.

I try all possible grouping of digits, building a pair of numbers to multiply. Each number is obviosuly built taking digits in decreasing order.

For instance, with a list of 4 numbers, \[1 2 3 4\] - try:

* 4 * 321
* 43 * 21
* 42 * 31
* 41 * 32
* 432 * 1
* 431 * 2
* 421 * 3

The max of these value is the result we need.

The groupings can be enumerated looping on a bitmap of 4 bits, with min value 0001 and max value 0111 (that is 1\<\<(4 -1) - 1)

**Not so golfed**

```
f=l=>{
  l = l.split(' '); // string to array
  l.sort().reverse(); // decreasing order
  m = 1 << (l.length-1); starting value fro loop
  r = 0
  // loop from m-1 down to 1
  for(i=m; --i; )
  {
    a = b = '';
    k = i;
    for(v of l) // divide the digits base on bits of i
    {
      k & 1 ? a+=v : b+=v;
      k /= 2;
    }
    if (r < a*b) r = a*b; // remember max value in r
  }
  return r
}

```

Test using the snippet below in Firefox.

```
f=l=>(i=>{for(r=0;a=b='',k=--i;r<a*b?r=a*b:0)for(v of l)k&1?a+=v:b+=v,k/=2})(1<<~-(l=l.split(' ').sort().reverse()).length)|r

t=l=>(i=>{for(x=r='';a=b='',k=--i;r<a*b?(r=a*b,x=' = '+a+'x'+b):0)for(v of l)k&1?a+=v:b+=v,k/=2})
(1<<~-(l=l.split(' ').sort().reverse()).length)|| x

function go()
{
  R.value = f(I.value) // TEST AS IS
   + t(I.value) // Some more info
}

test=['1 2 3 4','1 2 3','2 5 9','8 9 8']

test.forEach(t => O.innerHTML = O.innerHTML + (t + ' -> ' + f(t)) + '\n')
```

```
Type your list: <input id=I><button onclick='go()'>-></button><input readonly id=R><br>
<pre id=O></pre>
```
> 1 votes

# Answer
# Python 3, 111 bytes

It's probably much more golfable. I like its running time, though (O(*n* log *n*), is it?).

```
l=sorted(map(int,input().split()),reverse=1);m=[0,0]
for x in l:i=m[0]>m[1];m[i]=m[i]*10+x
print(m[0]*m[1])

```

Ungolfed with explanation.

```
# edc65 has already explained that the optimal solution can be found applying a single
# multiplication. thus, given that
#     (10x + d)y > (10y + d)x
# where x, y are the two numbers and d is the next digit to insert, it follows that
#     y > x
# and thus each new digit must be concatenated to the smallest number. obviously, digits
# should be added in descending order.
l = sorted(map(int, input().split()), reverse=1)
m = [0,0]
for x in l:
    i = m[0] > m[1]
    m[i] = m[i]*10 + x
print(m[0] * m[1])

```
> 1 votes

# Answer
# R, 164

```
function(n){l=length(n);a=sort(n,T);i=1;while(a[i]==a[i+1]&&i<l-2)i=i+2;a[c(i,i+1)]=a[c(i+1,i)];eval(parse(t=paste0(c(a[1:l%%2==1],"*",a[1:l%%2==0]),collapse='')))}

```

As a method I'm unsure if this is robust. With the cases that I have tested it appears to work each time. I tried testing it against optimizers solution and it appears to be OK against that as well. I'm more than prepared to be proven wrong :) There's room for golfing, but I was hoping to get some feedback on the method first.

The general process is :

* Sort the list in descending order
* Swap the first odd/even pair that differ
* Concatenate the even and odd items of the list
* Evaluate the product of the two results

Expanded out with some comments

```
function(n){
    l=length(n);
    a=sort(n,T);    # sort descending order
    # Determine which pair to swap
    i=1;
    while(a[i]==a[i+1]&&i<l-2)i=i+2;
    a[c(i,i+1)]=a[c(i+1,i)];  # swap pair
    # concatenate the even and odd indices items around a * and evaluate
    eval(parse(t=paste0(c(a[1:l%%2==1],"*",a[1:l%%2==0]),collapse='')))
}

```

And some test runs (implemented as a function called g)

```
> g(c(1,2,3))
[1] 63
> g(c(2,5,9))
[1] 468
> g(c(1,2,3,4))
[1] 1312
> g(c(1,2,3,5,5,5))
[1] 293132
> g(c(1,5,7,7,9,9))
[1] 946725
> g(c(1,7,8,9,9,9))
[1] 978117
> g(c(7,8,9,9,9))  #Test case provided edc65 to randomra
[1] 97713

```
> 0 votes

# Answer
# Pyth, 25 bytes

```
eSsmm*ss<dkss>dkr1ld.pcz)

```

I loop over every permutation of the input. Then because every optimal combination consists of two integers I merely split it at every possible position, and multiply the concatenated splits. I then sort and get the last element.
> 0 votes

# Answer
# Jelly, 12 bytes

```
Œ!ŒṖ€Ṗ€ẎḌP€Ṁ

```

Try it online!

ಠ\_ಠ Tied with CJam. Takes input as a list of values, +2 bytes to input as space-separated

## How it works

```
Œ!ŒṖ€Ṗ€ẎḌP€Ṁ - Main link. Takes a list L on the left
Œ!           - Permutations of L
  ŒṖ€        - Partitions of each
     Ṗ€      - Remove the last one from each
       Ẏ     - Join into one list
        Ḍ    - Convert from digits to numbers
         P€  - Product of each
           Ṁ - Maximum

```
> 0 votes

# Answer
# Stax, 8 bytes

```
ä;ªÜé▐ßó

```

Run and debug it

Uncompressed is 9 bytes, still beating CJam(with the same method).

## Explanation

```
|T{Ze*m|M
|T        permutations of input
  {   m   mapped to:
   Z      tuck a zero under the string
    e     evaluate the string
     *    multiply the top two elements
       |M get the maximum of the mapped list

```
> 0 votes

---
Tags: code-golf, arithmetic, combinatorics, set-partitions
---


title: Test if given number is a Keith number

text:
# Question
Title: Test if given number is a Keith number
Since Fibonacci numbers and sequences seems like a popular subject for code golf I thought that it might be a fun challenge to code golf with Keith numbers.

So I propose a challenge that is to create a function that takes an integer and gives back a true or false depending on the number is a Keith number or not.

*More about Keith numbers*

> In recreational mathematics, a Keith number or repfigit number (short for repetitive Fibonacci-like digit) is a number in the following integer sequence: 14, 19, 28, 47, 61, 75, 197, 742, 1104, 1537, 2208, 2580, …

Numberphile has a video explaining how to calculate a Keith number. But basically you take the digits of a number. Add them together and then take the last digits of the original number and add them to the sum of the calculation, rinse and repeat. And example to make it clear.

> **14**
> 1 + 4 = 5
> 4 + 5 = 9
> 5 + 9 = **14**

## Input

An integer.

## Output

True if the number is a Keith number. False if it's not..

# Answer
## GolfScript (31 25 chars)

```
..[10base{.{+}*+(\}@*]?0>

```

Input as an integer on top of the stack. Output is 0 (false) or 1 (true). Online demo which lists the Keith numbers up to 100.
> 7 votes

# Answer
## Python (~~78~~ 75)

```
a=input()
n=map(int,`a`)
while a>n[0]:n=n[1:]+[sum(n)]
print(a==n[0])&(a>9)

```

`n=n[1:]+[sum(n)]` does all the magic. It takes every item but the first item of `n`, sticks on the sum of `n` (with the first item), then sets that to `n`.

I wish you could call `list` on an integer and have the digits seperated.

Returns `False` on all inputs below 10. Can be 8 characters shorter if it returned `True`.
> 7 votes

# Answer
### GolfScript, 32 29 characters

```
...[10base\{.{+}*+(\}*]&,\9>&

```

A GolfScript implementation which can be tested online. Input is given as top element on the stack and it returns 0 (i.e. false) or 1 respectively.
> 6 votes

# Answer
## APL, ~~36~~ ~~34~~ ~~39~~ ~~36~~ ~~33~~ ~~29~~ 27

```
*+/x={(∇⍣(⊃x>¯1↑⍵))⍵,+/⍵↑⍨-⍴⍕x}⍎¨⍕x←⎕

```

Output `1` if Keith, `0` otherwise

GolfScript strikes again!!

---

**Edit**

```
+/x={(∇⍣(x>⊢/⍵))⍵,+/⍵↑⍨-⍴⍕x}⍎¨⍕x←⎕

```

Using Right-reduction (`⊢/`) instead of Take minus 1 (`¯1↑`), directly saving 1 char and indirectly saves 1 from Disclose ()

**Explanation**

`⍎¨⍕x←⎕` takes evaluated input (treated as a number) and assign it to `x`. Converts it to a character array (aka "string" in other languages), and loop through each character (digit), converting it to a number. So this results in a numerical array of the digits.

`{(∇⍣(x>⊢/⍵))⍵,+/⍵↑⍨-⍴⍕x}` is the main "loop" function:
`+/⍵↑⍨-⍴⍕x` takes the last `⍴⍕x` (no. of digits in `x`) numbers from the array and sums them.
`⍵,` concatenates it to the end of the array.
`(x>⊢/⍵)` check if the last number on the array (which doesn't have `+/⍵↑⍨-⍴⍕x` concatenated yet) is smaller than `x` and returns `1` or `0`
`∇⍣` executes this function on the new array that many times. So if the last number is smaller than `x`, this function recurs. Otherwise just return the new array

After the executing the function, the array contains the sums up to the point where 2 of the numbers are greater than or equal to `x` (e.g. `14` will generate `1 4 5 9 14 23`, `13` will generate `1 3 4 7 11 18 29`)
Finally check if each number is equal to `x` and output the sum of the resulting binary array.

---

**Edit**

```
1=+/x={(∇⍣(x>⊢/⍵))⍵,+/⍵↑⍨-⍴⍕x}⍎¨⍕x←⎕

```

Added 2 chars :-( to make output `0` if the input is one-digit

---

**Yet another edit**

```
+/x=¯1↓{(∇⍣(x>⊢/⍵))1↓⍵,+/⍵}⍎¨⍕x←⎕

```

**Explanation**

The function now drops the first number (`1↓`) from the array instead of taking the last `⍴⍕x` (`↑⍨-⍴⍕x`).
However, this approach makes `1=` not adequate to handle single digit numbers. So it now drops the last number from the array before checking equality to `x`, adding 1 char

---

**You guessed it: EDIT**

```
+/x=1↓{1↓⍵,+/⍵}⍣{x≤+/⍵}⍎¨⍕x←⎕

```

Compares `x` to the newly-added item instead of the old last item, so dropping the first (instead of last) item before checking equality to `x` is suffice, saving a minus sign. Saves another 3 by using another form of the Power operator()

And a 25-char gs answer appears (Orz)

---

**Last edit**

```
x∊1↓{1↓⍵,+/⍵}⍣{x≤+/⍵}⍎¨⍕x←⎕

```

Can't believe I missed that.
Can't golf it anymore.
> 4 votes

# Answer
# Common Lisp, 134

CL can be quite unreadable at times.

```
(defun k(n)(do((a(map'list #'digit-char-p(prin1-to-string n))(cdr(nconc a(list(apply'+ a))))))((>=(car a)n)(and(> n 9)(=(car a)n)))))

```

Some formatting to avoid horizontal scrolling:

```
(defun k(n)
  (do
    ((a(map'list #'digit-char-p(prin1-to-string n))(cdr(nconc a(list(apply'+ a))))))
    ((>=(car a)n)(and(> n 9)(=(car a)n)))))

```

Test:

```
(loop for i from 10 to 1000
      if (k i)
      collect i)

=> (14 19 28 47 61 75 197 742)

```
> 2 votes

# Answer
## F# - 184 chars

I hope it's ok that I'll participate in my own challenge.

```
let K n=
let rec l x=if n<10 then false else match Seq.sum x with|v when v=n->true|v when v<n->l(Seq.append(Seq.skip 1 x)[Seq.sum x])|_->false
string n|>Seq.map(fun c->int c-48)|>l

```

*Edit* Fixed a bug regarding small numbers.
> 1 votes

# Answer
## PowerShell: 120 128 123 111 110 97

```
$j=($i=read-host)-split''|?{$_};While($x-lt$i){$x=0;$j|%{$x+=$_};$null,$j=$j+$x}$x-eq$i-and$x-gt9

```

`$i=read-host` takes input from the user, stores it in $i.

`$j=(`...`)-split''|?{$_}` breaks up the digits from $i into an array and stores it in $j.

> Thanks to Rynant for pointing out that `-ne''` is unnecessary.

`While($x-lt$i)` sets the following Fibonnaci-like loop to run until the sum variable, $x, reaches or exceeds $i.

`$x=0` zeroes out $x, so it's ready to be used for summing (necessary for when the loop comes back around).

`$j|%{$x+=$_}` uses a ForEach-Object loop to add up the values from $j into $x.

`$null,$j=$j+$x` shifts the values in $j left, discarding the first, while appending $x.

> Yay! I finally figured out a shorter way to do shift-and-append, and got this script under 100!

`$x-eq$i` after the while loop completes, tests if the sum value, $x, equals the initial value, $i - generally indicative of a Keith Number.

`-and$x-gt9` invalidates single-digit numbers, zero, and negative numbers, which cannot be Keith Numbers.

This script is a bit "messy". It can gracefully handle $i and $j being leftover, but you'll need to clear $x between runs.

> Thanks to Keith Hill and mjolinor for some methods of breaking numbers into digits which were used in earlier versions of this script. While they are not in the final version, they did provide for a great learning experience.
> 1 votes

# Answer
# K, 55

```
{(x>9)&x=*|a:{(1_x),+/x}/[{~(x~*|y)|(+/y)>x}x;"I"$'$x]}

```

.

```
k)&{(x>9)&x=*|a:{(1_x),+/x}/[{~(x~*|y)|(+/y)>x}x;"I"$'$x]}'!100000
14 19 28 47 61 75 197 742 1104 1537 2208 2580 3684 4788 7385 7647 7909 31331 34285 34348 55604 62662 86935 93993

```
> 1 votes

# Answer
# Husk, 11 bytes

```
S£o¡oΣ↑_L¹d

```

Try it online!

Returns the iteration at which the Keith number is present, otherwise 0.

This challenge is perfect for Husk.

## Explanation

```
S£o¡oΣ↑_L¹d
   ¡o       create an infinite list, starting with
          d the digits of the input
      ↑_L¹  take length(input) numbers from the end
     Σ      and sum to compute the next number
S£o         is the input present in the list?

```
> 1 votes

# Answer
## **Ruby, 82**

```
def keith?(x)
  l="#{x}".chars.map &:to_i
  0while(l<<(s=l.inject :+)).shift&&s<x
  (s==x)&l[1]
end

```

Suspect Python's a better tool for this one.
> 0 votes

# Answer
## C, 123

```
k(v){
    int g[9],i,n,s,t=v;
    for(n=s=0;t;t/=10)s+=g[n++]=t%10;
    for(i=n;s<v;){
        i=(i+n-1)%n;
        t=g[i];g[i]=s;s=s*2-t;
    }
    return n>1&&s==v;
}

```

test via harness:

```
main(i){
    for(i=0;i<20000;i++)
        if(k(i)) printf("%d ",i);
}

```

gives:

```
14 19 28 47 61 75 197 742 1104 1537 2208 2580 3684 4788 7385 7647 7909

```
> 0 votes

# Answer
## R, 116

Python rip-off:

```
a=scan();n=as.numeric(strsplit(as.character(a),"")[[1]]);while(a>n[1])n=c(n[-1],sum(n));if((n[1]==a)&&(a>9))T else F

```
> 0 votes

# Answer
## Perl, 90

```
sub k{$-=shift;$==@$=split//,$-;push@$,eval join'+',@$[-$=..-1]while@$[-1]<$-;grep/$-/,@$}

```

A fun exercise! I know it's an old post but I noticed perl was missing!

I'm sure I can improve the way I build this from digesting the other responses more thoroughly, so I'll likely revisit this!
> 0 votes

# Answer
# Smalltalk - 136 char

```
 [:n|s:=n asString collect:[:c|c digitValue]as:OrderedCollection.w:=s size.[n>s last]whileTrue:[s add:(s last:w)sum].^(s last=n and:n>9)]

```

Send this block `value:`
> 0 votes

# Answer
# Python3 104

```
#BEGIN_CODE
def k(z):
 c=str(z);a=list(map(int,c));b=sum(a)
 while b<z:a=a[1:]+[b];b=sum(a)
 return(b==z)&(len(c)>1)
#END_CODE score: 104

print([i for i in filter(k, range(1,101))])  #[14, 19, 28, 47, 61, 75]

```

And it is a function ;)
> 0 votes

# Answer
# Python - 116 chars

Not really an expert at codegolf, so there you have it- my first try.

```
x=input();n=`x`;d=[int(i)for i in n];f=d[-1]
while f<x:d+=[sum(d[-len(n):])];f=d[-1]
if f==x>13:print 1
else:print 0

```

Make 2 changes for a function:

* Change `print` to `return`
* Assign `x` to be the parameter

P.S. I second @beary605- add a built-in to separate the digits/characters/whatever.
> 0 votes

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


title: McCarthy's LISP

text:
# Question
Title: McCarthy's LISP
# McCarthy's 1959 LISP

In early 1959, John McCarthy wrote a groundbreaking paper defining just nine primitive functions that when put together still form the basis for all LISP-like languages today. The paper is available digitized here:

**http://www-formal.stanford.edu/jmc/recursive.pdf**

Your job is to fully implement a parser and interpreter for McCarthy's LISP exactly as described in the 1960 paper: That is, the functions `QUOTE`, `ATOM`, `EQ`, `CAR`, `CDR`, `CONS`, `COND`, `LAMBDA`, and `LABEL` should all be functional. The paper will take precedence over this challenge text when considering the correctness of answers, but I've tried to summarize the nine functions below. Note that the language will be in ALL CAPS and no error checking is necessary, all input should be presumed to be valid.

**Types**

* There are only two types in McCarthy's LISP: An atom, and a linked list, which is recursively defined as a head, which may be a list or an atom, and a list that the head is attached to (tail). `NIL` has the special property of being both an atom and a list.
* As per the paper, atom names will only consist of capital letters, numbers, and the space character, though strings of consecutive spaces should be considered as just one space and all leading and trailing space characters should be removed. Example equivalent atom names (replace underscore with space character): `___ATOM__1__ = ATOM_1`. Example not equivalent atom names: `A_TOM_1 != ATOM_1`
* Lists are denoted by parentheses, and an implied `NIL` is at the end of every list. Elements in a list are separated by commas and *not* whitespace like in most modern Lisps. So the list `(ATOM 1, (ATOM 2))` would be `{[ATOM 1] -> {[ATOM 2] -> NIL} -> NIL}`.

**`QUOTE`:**

* Takes one argument which may be either an atom (single element) or a linked list. Returns the argument exactly.
* **Test cases:**
* `(QUOTE, ATOM 1) -> ATOM 1`
* `(QUOTE, (ATOM 1, ATOM 2)) -> (ATOM 1, ATOM 2)`

**`ATOM`:**

* Takes one argument which may be either an atom (single element) or a linked list. Returns `T` (true) if the argument is an atom, or `NIL` (false) if the argument is not an atom.
* **Test cases:**
* `(ATOM, (QUOTE, ATOM 1)) -> T`
* `(ATOM, (QUOTE, (ATOM 1, ATOM 2))) -> NIL`

**`EQ`:**

* Takes two arguments which must be atoms (behavior is undefined if either of the arguments are not atoms). Returns `T` (true) if the two atoms are equivalent, or `NIL` (false) if they are not.
* **Test cases:**
* `(EQ, (QUOTE, ATOM 1), (QUOTE, ATOM 1)) -> T`
* `(EQ, (QUOTE, ATOM 1), (QUOTE, ATOM 2)) -> NIL`

**`CAR`:**

* Takes one argument which must be a list (behavior is undefined if it is not a list). Returns the first atom (head) of that list.
* **Test cases:**
* `(CAR, (QUOTE, (ATOM 1, ATOM 2))) -> ATOM 1`

**`CDR`:**

* Takes one argument which must be a list (behavior is undefined if it is not a list). Returns every atom but the first atom of the list, i.e. the tail. Note that every list ends in an implied `NIL`, so running `CDR` on a list that appears to just have one element will return `NIL`.
* **Test cases:**
* `(CDR, (QUOTE, (ATOM 1, ATOM 2))) -> (ATOM 2)`
* `(CDR, (QUOTE, (ATOM 1))) -> NIL`

**`CONS`:**

* Takes two arguments. The first may be an atom or a list but the second must be a list or `NIL`. Prepends the first argument to the second argument and returns the newly-created list.
* **Test cases:**
* `(CONS, (QUOTE, ATOM 1), (QUOTE, NIL)) -> (ATOM 1)`
* `(CONS, (QUOTE, ATOM 1), (CONS, (QUOTE, ATOM 2), (QUOTE, NIL))) -> (ATOM 1, ATOM 2)`

**`COND`:**

* This is LISP's "if-else" statement of sorts. Takes a variable-length amount of arguments, each of which must be a list of length exactly 2. For each argument list in order, evaluate the first term and if it is true (T), return the associated second term and exit the function. If the first term is not true, move on to the next argument and test its condition, and so on until the first true condition is reached. At least one of the argument conditions can be assumed to be true -- if they are all false, this is undefined behavior. See page 4 for a good example of the behavior of this function.
* **Test cases:**
* `(COND, ((ATOM, (QUOTE, ATOM 1)), (QUOTE, 1)), ((ATOM, (QUOTE, (ATOM 1, ATOM 2))), (QUOTE, 2))) -> 1`
* `(COND, ((ATOM, (QUOTE, (ATOM 1, ATOM 2))), (QUOTE, 2)), ((ATOM, (QUOTE, ATOM 1)), (QUOTE, 1))) -> 1`

**`LAMBDA`:**

* Defines an anonymous function. Takes two arguments, the first being a list of atoms which represent the arguments to the function and the second being any S-expression (the function body), which would typically use the arguments.
* **Test cases:**
* Defining and using an anonymous "isNull" function:
* `((LAMBDA, (ATOM 1), (EQ, ATOM 1, (QUOTE, NIL))), (QUOTE, NIL)) -> T`
* `((LAMBDA, (ATOM 1), (EQ, ATOM 1, (QUOTE, NIL))), (QUOTE, ATOM 1)) -> NIL`

**`LABEL`:**

* Gives a name to an anonymous `LAMBDA` function, which also allows that function to be called recursively in the body of the `LAMBDA`. Takes two arguments, the first being a label and the second being the `LAMBDA` function to which the label should be bound. Returns the name supplied. The scope of all `LABEL` names is global, and redefining a `LABEL` is undefined behavior.
* Fun fact, `LABEL` is not actually necessary to create recursive functions as we now know `LAMBDA` can be used with a 'Y-Combinator' to accomplish this task, but McCarthy wasn't aware of this method when writing the original paper. It makes programs much easier to write anyways.
* **Test cases:**
* `(LABEL, SUBST, (LAMBDA, (X, Y, Z), (COND, ((ATOM, Z), (COND, ((EQ, Y, Z), X), ((QUOTE, T), Z))), ((QUOTE, T), (CONS, (SUBST, X, Y, (CAR, Z)), (SUBST, X, Y, (CDR, Z))))))) -> SUBST`
* *(after running the above)* `(SUBST, (QUOTE, A), (QUOTE, B), (QUOTE, (A, B, C))) -> (A, A, C)`

To help visualize the `SUBST` function above, it could be represented as this Python-like pseudocode:

```
def substitute(x, y, z): # substitute all instances of y (an atom) with x (any sexp) in z
    if isAtom(z):
        if y == z:
            return x
        elif True:
            return z
    elif True:
        return substitute(x,y,z[0]) + substitute(x,y,z[1:])

```

**FINAL TEST CASE:**

If I have transcribed it correctly, your interpreter should be able to interpret `EVAL` with this code:

```
(LABEL, CAAR, (LAMBDA, (X), (CAR, (CAR, X))))
(LABEL, CDDR, (LAMBDA, (X), (CDR, (CDR, X))))
(LABEL, CADR, (LAMBDA, (X), (CAR, (CDR, X))))
(LABEL, CDAR, (LAMBDA, (X), (CDR, (CAR, X))))
(LABEL, CADAR, (LAMBDA, (X), (CAR, (CDR, (CAR, X)))))
(LABEL, CADDR, (LAMBDA, (X), (CAR, (CDR, (CDR, X)))))
(LABEL, CADDAR, (LAMBDA, (X), (CAR, (CDR, (CDR, (CAR, X))))))

(LABEL, ASSOC, (LAMBDA, (X, Y), (COND, ((EQ, (CAAR, Y), X), (CADAR, Y)), ((QUOTE, T), (ASSOC, X, (CDR, Y))))))

(LABEL, AND, (LAMBDA, (X, Y), (COND, (X, (COND, (Y, (QUOTE, T)), ((QUOTE, T), (QUOTE, NIL)))), ((QUOTE, T), (QUOTE, NIL)))))
(LABEL, NOT, (LAMBDA, (X), (COND, (X, (QUOTE, NIL)), ((QUOTE, T), (QUOTE, T)))))

(LABEL, NULL, (LAMBDA, (X), (AND, (ATOM, X), (EQ, X, (QUOTE, NIL)))))

(LABEL, APPEND, (LAMBDA, (X, Y), (COND, ((NULL, X), Y), ((QUOTE, T), (CONS, (CAR, X), (APPEND, (CDR, X), Y))))))

(LABEL, LIST, (LAMBDA, (X, Y), (CONS, X, (CONS, Y, (QUOTE, NIL)))))

(LABEL, PAIR, (LAMBDA, (X, Y), (COND, ((AND, (NULL, X), (NULL, Y)), (QUOTE, NIL)), ((AND, (NOT, (ATOM, X)), (NOT, (ATOM, Y))), (CONS, (LIST, (CAR, X), (CAR, Y)), (PAIR, (CDR, X), (CDR, Y)))))))

(LABEL, EVAL, (LAMBDA, (E, A), (COND, ((ATOM, E), (ASSOC, E, A)), ((ATOM, (CAR, E)), (COND, ((EQ, (CAR, E), (QUOTE, QUOTE)), (CADR, E)), ((EQ, (CAR, E), (QUOTE, ATOM)), (ATOM, (EVAL, ((CADR, E), A)))), ((EQ, (CAR, E), (QUOTE, EQ)), (EQ, (EVAL, (CADR, E, A)), (EVAL, (CADDR, E, A)))), ((EQ, (CAR, E), (QUOTE, COND)), (EVCON, (CDR, E), A)), ((EQ, (CAR, E), (QUOTE, CAR)), (CAR, (EVAL, (CADR, E), A))), ((EQ, (CAR, E), (QUOTE, CDR)), (CDR, (EVAL, (CADR, E), A))), ((EQ, (CAR, E), (QUOTE, CONS)), (CONS, (EVAL, (CADR, E), A), (EVAL, (CADDR, E), A))), ((QUOTE, T), (EVAL, (CONS, (ASSOC, (CAR, E), A), (EVLIS, (CDR, E), A)), A)))), ((EQ, (CAAR, E), (QUOTE, LABEL)), (EVAL, (CONS, (CADDAR, E), (CDR, E)), (CONS, (CONS, (CADAR, E), (CONS, (CAR, E), (CONS, A, (QUOTE, NIL))))))), ((EQ, (CAAR, E), (QUOTE, LAMBDA)), (EVAL, (CADDAR, E), (APPEND, (PAIR, (CADAR, E), (EVLIS, (CDR, E), A)), A))))))

(LABEL, EVCON, (LAMBDA, (C, A), (COND, ((EVAL, (CAAR, C), A), (EVAL, (CADAR, C), A)), ((QUOTE, T), (EVCON, (CDR, C), A)))))

(LABEL, EVLIS, (LAMBDA, (M, A), (COND, ((NULL, M), (QUOTE, NIL)), ((QUOTE, T), (CONS, (EVAL, (CAR, M), A), (EVLIS, (CDR, M), A))))))

```

After running that behemoth, this line should return `(A, B, C)`:

```
(EVAL, (QUOTE, (CONS, X, (QUOTE, (B, C)))), (QUOTE, ((X, A), (Y, B))))

```

However, to quote John McCarthy himself on page 16, it seems like he was running out of characters on his computer:

> If more characters were available on the computer, it could be improved considerably ...

Therefore, this challenge is tagged and the shortest answer in characters will be the winner. Standard loopholes apply. Good luck!

**Note on String Evals**: I understand that some think it may be possible to win this challenge by using a Lisp and modifying the syntax to fit the host language and then using a string `(eval)`. I'm not particularly convinced that this approach will necessarily win especially with the identifier naming rules, and even if it did I think banning string `eval`s in all languages would be a subjective and slippery slope. But I don't want to punish people for doing this challenge the 'right' way, so I may allow two winners for this challenge, one in a Lisp-like language and one in a non-Lispy language, if this becomes a problem.

# Answer
# APL (Dyalog Unicode), <sup>~~523...451~~</sup> 447 bytes

Saved 12 bytes thanks to @Bubbler!

Saved 1 byte thanks to @Adám (and 7 more thanks to this comment on another answer)

```
s←⎕SE.Dyalog.Utils.repObj
z←'NIL'
p←{')'=⊃⍵:(⊂z)(1↓⍵)⋄v r←{'('=⊃⍵:p⍵⋄⍵(↑,Ö⊂↓)⍨⊃⍸⍵∊',)'}1↓⍵⋄n r←∇r⋄(n,⍨⊂v)r}
e←{1=≡⍵:((⊃⍺)⍳⊂⍵)⊃(1⊃⍺),⊂⍵⋄⍺(⍎⍺e⊃⍵)1↓⍵}
b←⊃∘z'T'
CAR←⊃x←e∘⊃
CDR←1↓x
QUOTE←⊃⊢
CONS←{(⊂⍺x⍵),⊆⍺e 1⊃⍵}
EQ←{b≡/⍺∘e¨¯1↓⍵}
ATOM←b 1=∘≡x
COND←{z≢⍺x⊃⍵:⍺e 1⊃⊃⍵⋄⍺∇1↓⍵}
LAMBDA←{⍕'{((('(s⊃⍵)'),⊃⍺)((⍺∘e¨⍵),1⊃⍺))e'(s 1⊃⍵)'}'}
LABEL←{u←⍎⍕'#.'(⊃⍵)'←',⍺e 1⊃⍵⋄⊃⍵}

```

To execute a line of LISP:

```
{{1=≢⍵:⍵⋄1=≡⍵:'_'⎕R' '⊢⍵⋄⍕1⌽')(',∇¨¯1↓⍵}⍬⍬e⊃p'(?<=\(|,) *(?=\d)| +' ' *([(),]) *'⎕R'_' '\1'⊢⍵}

```

Try it online!

~~Unfortunately, this doesn't work in TIO~~ dzaima (and Adám) got `⎕SE.Dyalog.Utils.repObj` working! Requires `⎕IO←0` now.

## Formatting the input

First `⎕R` is used to format the input. It accepts a bunch of regex on the left and the strings to replace them with on the right. In this case, we're replacing areas before atom names starting with digits (`(?<=\(|,) *(?=\d)`) or multiple spaces ( `+`) with a single underscore because in APL, identifiers cannot contain spaces or start with digits.

At the same time,  `*([(),]) *` captures parentheses or commas along with spaces around them, but only keeps the parentheses and commas, dropping leading or trailing spaces by doing so. Thus, `( QUOTE, (1, ATOM 2))` would become `(QUOTE,(_1,ATOM_2))`.

## Creating an AST

`p` creates an AST from this formatted string. Every atom is represented by a string, and every s-expression is simply an array of atoms or other s-expressions, with the string `NIL` at the end. Thus, `(QUOTE,(ATOM_1,ATOM_2))` would become `('QUOTE' ('ATOM_1' 'ATOM_2' 'NIL') 'NIL')`.

## Executing the AST

`e` takes such an AST as its right argument and evaluates it. The left argument is a context that gives the variables in scope. It's an array whose first elements is a list of strings denoting the names of atoms, while the second element is a list of the same length with those variables' values. For example, given a lisp expression `((LAMBDA, (X, Y), (CONS, Y, X)), (QUOTE, (ATOM 1)), (QUOTE, ATOM 2))`, the context would look like this (the `NIL`s are an unfortunate side effect of how the ASTs are structured, but they're harmless):

```
       'X'     |    'Y'   | 'NIL'
'ATOM_1' 'NIL' | 'ATOM_2' | 'NIL'

```

If the right argument to `e` is a single string (an atom), it looks up the atom in the context and gets back the corresponding value. If the atom is not found in the context, it just gives back the same string. So in the example above, if  (the right argument) were `X`, we would get back `ATOM_1`, but if it were `CAR`, we would get back `CAR` again.

Otherwise, it's a function call, so it calls `e` on the first element of that tree with the same context on the left. The first element of the AST is either a label name or one of the nine "builtin" functions, or a lambda expression. If it's the former, we'll just get back the name of the function again. In that case, we can execute the string with  (APL's equivalent of `eval`) to get another dyadic function. We give it the same context on the left and apply it to the rest of , the right argument.

Otherwise, if it's a lambda expression, applying the function `LAMBDA` (the one I've defined) returns a string containing a function, so again, we can execute it and apply it to the rest of .

The initial left argument is `⍬⍬` ( is an empty array), because we don't have any variables defined yet.

## Printing the result

`{1=≢⍵:⍵⋄1=≡⍵:'_'⎕R' '⊢⍵⋄⍕'('(∇¨¯1↓⍵)')'}` is a recursive function that turns arrays into strings. `1=≢⍵` checks if the argument is a string (with depth 1). If so, it turns underscores back into spaces with `'_'⎕R' '`. Otherwise, it drops the last element (always `NIL`) using `¯1↓⍵`, then calls itself on each element using `∇¨`. That is put into an array with parentheses, and  is used to turn that array into a string (with extra spaces).

### `LAMBDA`

This function returns a string representing another function. For example, `(LAMBDA, (X, Y), (CONS, X, Y))` becomes

```
{((('X' 'Y' 'NIL'),⊃⍺)((⍺∘e¨⍵),1⊃⍺))e'CONS' 'X' 'Y' 'NIL'}

```

While the definition of `LAMBDA` itself may look messy, there is nothing complicated about it. On the right is simply the body given to the lambda; only the context has changed. Like the Python answer, I used dynamic scoping, so the new context adds to the context given at the call site, not where the lambda is defined. The first element is just the names lambda's parameters prepended to the the old context's names. The second is the result of evaluating all the arguments (with the same context), prepended to the old context's values. `repObj` (assigned to `s` because it is used multiple times) finds the string representation of the parameters and lambda body.

### `LABEL`

This is why we had to add underscores before. `LABEL` constructs a string that looks like `#.name ← lambda`, given the arguments `name lambda 'NIL'`, executes it, adding a function called `name` to the root namespace `#`, so it is global. Like `LAMBDA`, it ignores the context given to it, because of dynamic scoping.
> 7 votes

# Answer
# Python 3, 770 bytes

This is a REPL on stdin/stdout. Expects every line to be a full statement or empty. `eval` is used to shorten the implementation, but is otherwise not necessary for logic.

```
import re,sys;S=re.sub
P=lambda l:eval(S("([A-Z0-9][A-Z0-9 ]*)",r"' '.join('\1'.strip().split())",S("NIL","()",S("\)",",)",l))))
d={"QUOTE":'(v,L[1])[1]',"EQ":'[(),"T"][E(L[1],v)==E(L[2],v)]',
"CDR":'E(L[1],v)[1:]',"CONS":'(E(L[1],v),)+E(L[2],v)',"CAR":'E(L[1],v)[0]',
"LAMBDA":'("#",)+L[1:]',"LABEL":'[v.update({L[1]:E(L[2],v)}),L[1]][1]'}
def E(L,v):
 if L*0=="":return v[L]
 elif L[0]in d:return eval(d[L[0]])
 elif L[0]=="COND":return next(E(l[1],v)for l in L[1:]if E(l[0],v)=="T")
 elif L[0]=="ATOM":o=E(L[1],v);return[(),"T"][o*0in["",o]]
 else:l=E(L[0],v);n=v.copy();n.update({a:E(p,v)for a,p in zip(l[1],L[1:])});return E(l[2],n)
R=lambda o:o==()and"NIL"or 0*o==()and"(%s)"%", ".join(R(e)for e in o)or o
g={}
for l in sys.stdin:
 if l.strip():print(R(E(P(l),g)))

```
> 19 votes

---
Tags: code-golf, interpreter, lisp
---


title: Twist on words to numbers

text:
# Question
Title: Twist on words to numbers
## The Goal

The goal of this question is to put a twist on **this question**. Your answer should be able to convert an array of words associated with integers into those integers. As an extra challenge, allow support for , `+`, `-`, and `_` in between numbers such as `sixty seven`, `sixty+seven`, `sixty-seven`, or `sixty_seven`.

## Examples

General Example: `one, twenty-two, eleven, thirty+five, forty eight` =\> `1, 22, 11, 35, 48`.
General Example: `ninety_two, eighty one, zero, seventy+seven, nine` =\> `92, 81, 0, 77, 9`.
Javascript/Node.JS Example: `['five', 'twenty+eight', 'fifty_two', 'thirty', 'zero']` =\> `[5, 28, 52, 30, 0]`

## Assumptions

* There are no negative numbers
* The applicable numbers only need to be `0-99`
* The array will not be empty

## Scoring

As this is code-golf, let the answer with the fewest amount of bytes win. Good luck.

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

```
a=>a.map(s=>s.replace(/[a-z]+/g,s=>t+=Buffer(`3!S~0?.']5~g)~~~#I*~{2"&+,/-~4~$%q~(1`)[parseInt(s,36)%620%546%115%37]-33,t=0)|t)

```

Try it online!

Below is a summary of the hash function, which gives a result in \\$\[0..36\]\\$ with a few unused slots.

```
 string      | base 36 -> dec. | mod 620 | mod 546 | mod 115 | mod 37
-------------+-----------------+---------+---------+---------+--------
 'zero'      |  1652100        |   420   |   420   |   75    |  1
 'one'       |  31946          |   326   |   326   |   96    |  22
 'two'       |  38760          |   320   |   320   |   90    |  16
 'three'     |  49537526       |   146   |   146   |   31    |  31
 'four'      |  732051         |   451   |   451   |   106   |  32
 'five'      |  724298         |   138   |   138   |   23    |  23
 'six'       |  36969          |   389   |   389   |   44    |  7
 'seven'     |  47723135       |   495   |   495   |   35    |  35
 'eight'     |  24375809       |   509   |   509   |   49    |  12
 'nine'      |  1097258        |   478   |   478   |   18    |  18
 'ten'       |  38111          |   291   |   291   |   61    |  24
 'eleven'    |  882492287      |   407   |   407   |   62    |  25
 'twelve'    |  1807948346     |   446   |   446   |   101   |  27
 'thirteen'  |  2310701170991  |   351   |   351   |   6     |  6
 'fourteen'  |  1229565944111  |   371   |   371   |   26    |  26
 'fifteen'   |  33766692143    |   423   |   423   |   78    |  4
 'sixteen'   |  62095095599    |   619   |   73    |   73    |  36
 'seventeen' |  80156542487855 |   95    |   95    |   95    |  21
 'eighteen'  |  1137277763375  |   115   |   115   |   0     |  0
 'nineteen'  |  1842973464623  |   103   |   103   |   103   |  29
 'twenty'    |  1807950886     |   506   |   506   |   46    |  9
 'thirty'    |  1782948454     |   194   |   194   |   79    |  5
 'forty'     |  26350054       |   54    |   54    |   54    |  17
 'fifty'     |  26054566       |   306   |   306   |   76    |  2
 'sixty'     |  47912902       |   542   |   542   |   82    |  8
 'seventy'   |  61849184038    |   278   |   278   |   48    |  11
 'eighty'    |  877529158      |   378   |   378   |   33    |  33
 'ninety'    |  1422047446     |   566   |   20    |   20    |  20

```

---
Tags: code-golf, array, integer, conversion
---


# Question
Title: Convert numbers to binary... but you're allowed to use twos as well
Based on the "binary, but with twos" notation mentioned in this numberphile video, write a function that takes a single number as input and outputs *all* variations of that number in a "binary" system where twos are allowed.

### Rules

* Code must only be a function/method, not a full program
* Input is an integer passed as the sole parameter to the function
* Output is *all* valid variations of the input number converted to "binary, but with twos" notation
* Output is the return value of the function, but can be in whatever format is convenient as long as it's obvious (eg, 3 ints, 3 strings, comma/space delimited string, array of ints, etc), order is unimportant
* In the unlikely event that a language happens to contain a built-in function to achieve the result, it's disallowed
* Shortest code in bytes is the winner

### Explanation of the output

By example, if you're passed the number `9`, you can convert it to binary as `1001`, but if you allowed `2`s in each position, you could also write it as `201` (i.e. `2*4 + 0*2 + 1*1`), or `121` (i.e. `1*4 + 2*2 + 1*1`), as shown in this table:

```
+----+----+----+----+
| 8s | 4s | 2s | 1s |
+----+----+----+----+
|  1 |  0 |  0 |  1 |
|  0 |  2 |  0 |  1 |
|  0 |  1 |  2 |  1 |
+----+----+----+----+

```

So, if passed `9`, your function would need to return the three numbers, `1001`, `201` and `121`.

Format and order are irrelevant, so long as it's obvious (i.e. `[121,201,1001]`, `"0201 0121 1001"`, `("1001","121","201")` are valid results when given an input of `9`).

### Examples

* `2` =\> `10, 2`
* `9` =\> `1001, 201, 121`
* `10` =\> `1010, 210, 202, 1002, 122`
* `23` =\> `2111, 10111`
* `37` =\> `100101, 20101, 100021, 20021, 12101, 12021, 11221`

# Answer
> 10 votes
## GolfScript (25 bytes) / CJam (19 17 bytes)

GolfScript:

```
{:^.*,{3base}%{2base^=},}

```

This creates an anonymous function (see meta discussion about permissibility of anonymous functions).

Online demo

A straight translation into CJam is (with thanks to Martin Büttner for shaving a couple of characters)

```
{:X_*,3fb{2bX=},}

```

### Dissection

```
{             # Function boilerplate
  :^          # Store parameter as variable ^
  .*          # Square parameter - see detailed explanation below
  ,{3base}%   # Produce an array of 0 to ^*^-1 in ternary
  {2base^=},  # Filter to those which evaluate to ^ in binary
}

```

The reason for the squaring operation is that we need to iterate up to the largest possible value whose ternary representation, interpreted in binary, is equal to `^`. Since `2 = 10`, the "normal" binary representation of `^` is the one which matters. If we convert that to ternary, we find that the "worst" cases are powers of 2. An optimal approach would be to take the argument to the power of `ln 3/ln 2 ~= 1.585`, but squaring is much shorter.

# Answer
> 8 votes
# Python 2 (59 bytes)

```
S=lambda n,B="":[B][n:]or~n%2*S(n/2-1,"2"+B)+S(n/2,`n&1`+B)

```

*(Much thanks to @grc, @xnor and @PeterTaylor for helping out in chat)*

Simple recursion, call with `S(23)` or similar.

## Explanation

The general idea is that if `n`'s binary expansion ends in a `1`, then any pseudo-binary ("binary, but with twos") expansion must also end with a `1`. Otherwise it could end with `0` or `2`.

Hence we look at the last bit of `n`, divide out and branch accordingly.

## Dissection

```
S=lambda n,B="":           # Lambda expression
[B][n:]or                  # Short circuit, return [B] if n==0 else what follows
~n%2*                      # Keep next list result if n is even else turn into []
S(n/2-1,"2"+B)             # Add a "2" to B, recurse
+
S(n/2,`n&1`+B)             # Add "0" or "1" to B depending on n's last bit, recurse

```

Variables:

* `n`: The number we want to find pseudo-binary expansions of
* `B`: A pseudo-binary string being built right-to-left

# Answer
> 5 votes
# Bash+coreutils, 77

```
f()(seq `dc -e2o$1p`|sed '/[3-9]/d;s/.*/&n9P2i&pAi/'|dc|grep -Po ".*(?= $1)")

```

(That is a `TAB` character in the grep expression.)

This is bending this rule a bit:

*"In the unlikely event that a language happens to contain a built-in function to achieve the result, it's disallowed"*

It turns out that `dc` has **the reverse** of what we need built in. For instance if we set the input base to 2 and input a binary number with twos, it will correctly parse it. (Similarly if the input mode is base 10, then A-F are parsed as decimal "digits" 10-15).

`seq` creates a list of all decimal numbers up to the standard binary representation of n, parsed as a decimal. Then all numbers that contain anything other than {0,1,2} are filtered out. Then `dc` parses the remaining numbers as binary to see which evaluate back to n.

Bash functions can only "return" scalar integers 0-255. So I'm taking the liberty of printing the list to STDOUT as my way of "returning". This is idiomatic for shell scripts.

### Output:

```
$ f 2
2
10
$ f 9
121
201
1001
$

```

# Answer
> 4 votes
# Haskell, 82

```
t n=[dropWhile(==0)s|s<-mapM(\_->[0..2])[0..n],n==sum[2^(n-i)*v|(i,v)<-zip[0..]s]]

```

this is just a brute-force solution. it is very inefficient, because it is expected to crunch through 3^n possibilities.

# Answer
> 4 votes
# Jelly, 10 bytes, language postdates challenge

```
ṗ@3Ḷ¤Ḅ=¥Ðf

```

Try it online!

A bruteforce solution up to a number of hyperbits equal to the input (this format is known as "hyperbinary"). As such, it's incredibly inefficient, running in O(3n).

## Explanation

```
ṗ@3Ḷ¤Ḅ=¥Ðf
ṗ@            Construct all lists with the given length, and elements taken from
  3Ḷ¤         the list [0,1,2]
        Ðf    then take only those elements which
     Ḅ=¥      when interpreted as binary, equal {the original number}

```

# Answer
> 2 votes
# PHP, 138 Bytes

```
function p($v,$i=0,$r=""){global$a;if($v==0)$a[]=$r?:0;elseif($v>0)for(;$l<3;)p($v-2**$i*$l,$i+1,+$l++.$r);}p($argv[1]);echo join(",",$a);

```

## Breakdown

```
function p($v,$i=0,$r=""){
    global$a;
    if($v==0)$a[]=$r?:0;  # fill result array
    elseif($v>0) # make permutations
        for(;$l<3;)
            p($v-2**$i*$l,$i+1,+$l++.$r); #recursive
}
p($argv[1]);
echo join(",",$a); # Output

```

# Answer
> 1 votes
C++, 159 bytes

```
void c(int x,string r){int i,t=0,s=r.size();if(s<8){if(r[0]>48){for(i=0;i<s;i++)t+=(r[s-i-1]-48)*1<<i;if(t==x)cout<<r<<" ";}for(char n=48;n<51;n++)c(x,r+n);}}

```

Test it here

# Answer
> 1 votes
# k, 21 bytes

Uses the same method as Peter Taylor's Golfscript answer

```
{X@&x=2/:'X:3\:'!x*x}

```

Examples:

```
k) {X@&x=2/:'X:3\:'!x*x}9
(1 2 1;2 0 1;1 0 0 1)
k) {X@&x=2/:'X:3\:'!x*x}10
(1 2 2;2 0 2;2 1 0;1 0 0 2;1 0 1 0)

```

# Answer
> 1 votes
# Haskell, 80 bytes

```
f 0=[[]]
f n=((++[n-2*d])<$>f d)++[x|n==2*d,x<-(++[2])<$>(f$d-1)]where d=n`div`2

```

Try it online!

Recursive solution, and my first Haskell golf.

```
-- recursive definition
-- base case: a sum of 0 is possible as simply a 0-length "binary-with-two" string
f 0=[[]]
-- f n=all possibilities to form n
f n =
-- like normal binary, can have a last digit of 0 or 1 if even or odd, respectively
-- consider n`mod'`2 = n-2*d
  (
    (++[n-2*d])<$> -- add that last digit to each
    f d -- possibility from n/2
  )
-- additional possibility of last digit 2, only if n is even
     n==2*d -- if n is even:
  [x|      ,x<-(++[2])<$>(f$d-1)] -- add that last digit 2 to each possibility from (n-2)/2
  where d=n`div`2

```

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


title: Generalised Taxicab Numbers

text:
# Question
Title: Generalised Taxicab Numbers
\\$\newcommand{T}\[1\]{\text{Ta}(#1)} \newcommand{Ta}\[3\]{\text{Ta}\_{#2}^{#3}(#1)} \T n\\$ is a function which returns the smallest positive integer which can be expressed as the sum of 2 positive integer cubes in \\$n\\$ different ways. For example, \\$\T 1 = 2 = 1^3 + 1^3\\$ and \\$\T 2 = 1729 = 1^3 + 12^3 = 9^3 + 10^3\\$ (the Hardy-Ramanujan number).

Let's generalise this by defining a related function: \\$\Ta n x i\\$ which returns the smallest positive integer which can be expressed as the sum of \\$x\\$ \\$i\\$th powers of positive integers in \\$n\\$ different ways. In this case, \\$\T n = \Ta n 2 3\\$ (note: this is the same function here, \\$\Ta n x i = \text{Taxicab}(i, x, n)\\$)

Your task is to take 3 positive integers \\$n, x\\$ and \\$i\\$ and return \\$\Ta n x i\\$. This is so the shortest code in bytes wins.

In case \\$x = 1 \\$ and \\$ n \> 1\\$, your program can do anything short of summoning Cthulhu, and for other cases where \\$\Ta n x i\\$ is not known to exist (e.g. \\$\Ta n 2 5\\$), the same applies.

## Test cases

```
n, x, i -> out
1, 1, 2 -> 1
1, 2, 3 -> 2
2, 2, 2 -> 50
2, 2, 3 -> 1729
3, 3, 2 -> 54
3, 3, 3 -> 5104
2, 6, 6 -> 570947
2, 4, 4 -> 259
6, 4, 4 -> 3847554
2, 5, 2 -> 20
2, 7, 3 -> 131
2, 5, 7 -> 1229250016
5, 8, 4 -> 4228

```

---

### Properties of \\$\Ta n x i\\$

* \\$\forall i : \Ta 1 x i = x\\$ as \\$x = \underbrace{1^i + \cdots + 1^i}\_{x \text{ times}}\\$
* \\$\Ta n 1 i\\$ does not exist for all \\$n \> 1\\$
* \\$\Ta n 2 5\\$ is not known to exist for any \\$n \ge 2\\$

This is a table of results \\$\\{\Ta n x i \\:|\\: 1 \le n,x,i \le 3 \\}\\$, ignoring \\$\Ta 2 1 i\\$ and \\$\Ta 3 1 i\\$:

$$\begin{array}{ccc|c} n & x & i & \Ta n x i \\ \hline 1 & 1 & 1 & 1 \\ 1 & 1 & 2 & 1 \\ 1 & 1 & 3 & 1 \\ 1 & 2 & 1 & 2 \\ 1 & 2 & 2 & 2 \\ 1 & 2 & 3 & 2 \\ 1 & 3 & 1 & 3 \\ 1 & 3 & 2 & 3 \\ 1 & 3 & 3 & 3 \\ 2 & 2 & 1 & 4 \\ 2 & 2 & 2 & 50 \\ 2 & 2 & 3 & 1729 \\ 2 & 3 & 1 & 5 \\ 2 & 3 & 2 & 27 \\ 2 & 3 & 3 & 251 \\ 3 & 2 & 1 & 6 \\ 3 & 2 & 2 & 325 \\ 3 & 2 & 3 & 87539319 \\ 3 & 3 & 1 & 6 \\ 3 & 3 & 2 & 54 \\ 3 & 3 & 3 & 5104 \\ \end{array}$$

# Answer
> 5 votes
# 05AB1E, 15 bytes

```
∞.ΔL¹m²ã€{ÙOy¢Q

```

Try it online!

This is really slow, inserting `¹zmï` after  limits the search space significantly: Try it online!

**Commented:**

```
                # Inputs ¹=i, ²=x, ³=n
∞.Δ             # find the first natural number k that satisfies:
   L            #   each of the range [1..k]
    ¹m          #   raised to the i-th power
      ²ã        #   take the list to the x-th cartesian power
        €{      #   sort each x-tuple
          Ù     #   deduplicate the tuples
           O    #   sum each x-tuple
            y¢  #   count the number of k's
              Q #   is this equal to the last input?

```

`ã€{Ù` does the same as Python's `itertools.combinations_with_replacement`, but there doesn't seem to be a builtin for this in *05AB1E*.

# Answer
> 4 votes
# \+ gtools, 84 bytes

```
function(n,x,i){while(sum(rowSums(gtools::combinations(+T,x,re=1)^i)==T)<n)T=T+1;+T}

```

Try it online!

Counts `T` up from 1, calculating the number of combinations of `x` numbers ≤`T` whose `i`th powers sum to `T`. Stops at the first number that gives (at least) `n` combinations.

```
function(n,x,i){
                    # variable T (TRUE) initialized by default to 1
 while( ... )T=T+1  # while the condition (see below) is met, keep incrementing T
                    #
 a=gtools::combinations(+T,x,re=1)  # all combinations of x numbers from 1..T (as rows of matrix)
 b=a^i              # raised to the i-th power
 c=rowSums(b)       # the row sums are the sums of each combination
 d=sum(c==T)        # when the row sums equal T, we have a combination of x i-th powers that equals T
 d<n                # the condition: we didn't get n combinations yet
                    #
 +T                 # finally, the condition fails, so we've got n combinations: return this value of T
}

```

---

For a base- solution (without the gtools library), swap `gtools::combinations(+T,x,re=1)` for `unique(t(apply(expand.grid(rep(list(1:T),x)),1,sort)))` (+23 bytes).

# Answer
> 3 votes
# Wolfram Language (Mathematica), 79 bytes

```
(n=1;While[Length@Select[PowersRepresentations[n++,#2,#3],#~FreeQ~0&]!=#];n-1)&

```

Try it online!

# Answer
> 3 votes
# Jelly, 12 bytes

```
œċ³*⁴§ċ⁼⁵µ1#

```

A full program which (given enough time!) prints the result if it exists. Inputs are \\$x\\$, \\$i\\$, \\$n\\$.

**Try it online!** (Too slow for most of the test cases.)

### How?

Brute-force (and an inefficient one at that):

```
œċ³*⁴§ċ⁼⁵µ1# - Main Link: x
         µ1# - Count up starting with k=x until 1 truthy result, then yield k, using:
  ³          -   1st program argument, x
œċ           -   all combinations (of x elements from [1..k]), allowing repeats
    ⁴        -   2nd program argument, i
   *         -   exponentiate (vectorises)
     §       -   sums
      ċ      -   count occurrences (of k)
        ⁵    -   3rd program argument, n
       ⁼     -   equal?

```

Note `œċ` does not give unordered repeats, for example `2œċ3` yields:
`[[1, 1, 1], [1, 1, 2], [1, 2, 2], [2, 2, 2]]`

# Answer
> 2 votes
# JavaScript (ES7), 89 bytes

```
(n,x,i)=>(F=q=>(g=(k,p,j)=>j?p**i>k?0:g(k-p**i,p,j-1)+g(k,p+1,j):!k)(++q,1,x)-n?F(q):q)``

```

Try it online!

### Commented

We recursively look for the smallest \\$q\\$ such that there exists exactly \\$n\\$ sums of the form:

$${p\_1}^i+{p\_2}^i+\ldots+{p\_x}^i=q,\\:p\_{k+1}\ge p\_k \ge 1$$

```
(n, x, i) => (        // input variables, as described in the challenge
  F = q =>            // F is a recursive function taking a candidate solution q
  ( g = (             //   g is a recursive function taking:
      k,              //     k = current sum
      p,              //     p = number to be raised to the power of i
      j               //     j = remaining number of terms in the sum
    ) =>              //
    j ?               //     if there's at least one more term to compute:
      p ** i > k ?    //       if p ** i is greater than k:
        0             //         abort
      :               //       else:
        g(            //         do a 1st recursive call with:
          k - p ** i, //           k = k - p ** i
          p,          //           p unchanged
          j - 1       //           one less term to compute
        ) +           //
        g(            //         do a 2nd recursive call with:
          k,          //           k unchanged
          p + 1,      //           p incremented
          j           //           j unchanged
        )             //
    :                 //     else:
      !k              //       increment the final result if k = 0
  )(++q, 1, x)        //   initial call to g with k = ++q, p = 1 and j = x
  - n ?               //   if the result is not equal to n:
    F(q)              //     try again
  :                   //   else:
    q                 //     success: return q
)``                   // initial call to F with q zero'ish

```

# Answer
> 2 votes
# Wolfram Language, ~~110~~ 108 bytes

Try it online!

```
(i=0;While[Length@FindInstance[i++==Tr[(v=Unique[]~Table~#2)^#3]&&LessEqual@@v,v,PositiveIntegers,#]!=#];i)&

```

# Answer
> 1 votes
# Scala, 125 bytes

```
(n,x,i)=>1 to 1<<30 find(c=>Seq.fill(x)(1 to c map(Math.pow(_,i))takeWhile(_<=c)).flatten.combinations(x).count(_.sum==c)==n)

```

Try it online!

**Approach**: for each candidate integer `c`, generate a list of `x` copies of `i`-powered integers lower than `c`, and count whether `n` (distinct!) combinations of length `x` sum up to `c`.

**Performance**: the trade-off between performance and code length is made such that most test cases finish within some seconds. The following variant would save 14 bytes, but would be much less performant:

```
(n,x,i)=>0 to 1<<30 find(c=>Seq.fill(x)(1 to c).flatten.combinations(x).count(_.map(Math.pow(_, i)).sum==c)==n)

```

---
Tags: code-golf, math, number-theory, integer
---


title: Generate a Graeco-Latin square

text:
# Question
Title: Generate a Graeco-Latin square
<sup> disclaimer: I'm not aware of any non-bruteforce solutions </sup>

A Graeco-Latin square is, for two sets of same length \\$n\\$, a \\$n \times n\\$ arrangement of cells, each containing a unique (across the entire square) pair of a element of the first set and a element of the second set, such that all first elements and all second elements of the pairs are unique in their row and column. The most common sets used are, as one could guess, the first \\$n\\$ letters of the Greek and the Latin alphabets.

Here is a picture of a 4x4 Graeco-Latin square:

Graeco-Latin squares are as useful as they sound (the Wikipedia article mentions "design of experiments, tournament scheduling and constructing magic squares"). Your task is, given a positive integer \\$n\\$, to generate a \\$n\times n\\$ Graeco-Latin square.

## Input

A positive integer \\$n \> 2\\$; it is guaranteed that a \\$n\times n\\$ Graeco-Latin square exists (that is, \\$n \ne 6\\$).

## Output

A Graeco-Latin square with side length n as a two-dimensional array, a array of arrays, a flattened array or outputted directly.

## Notes

* You do not have to use the Greek and Latin alphabets specifically; for example, outputting pairs of positive integers is allowed as well.
* If you choose to use a alphabet that can't be extended arbitrarily, you have to (theoretically; your code doesn't have to finish before the heat death of the universe) support a maximal side length of at least 20.

This is , so the shortest code wins!

# Answer
# Jelly,  ~~21~~  20 bytes

-1 thanks to Nick Kennedy (flat output option allows a byte save of `ż"þ`ẎẎQƑ$Ƈ` \\$\rightarrow\\$ `F€p`Z€QƑƇ`)

```
Œ!ṗ⁸Z€Q€ƑƇF€p`Z€QƑƇḢ

```

**Try it online!** (Too slow for `4` in 60s on TIO, but if we replace the Cartesian power, , with Combinations, `œc`, it will complete \- although 5 certainly will not!)

### How?

```
Œ!ṗ⁸Z€Q€ƑƇF€p`Z€QƑƇḢ - Link: integer, n
Œ!                   - all permutations of [1..n]
   ⁸                 - chain's left argument, n
  ṗ                  - Cartesian power (that is, all ways to pick n of those permutations, with replacement, not ignoring order)
    Z€               - transpose each
         Ƈ           - filter, keeping those for which:
        Ƒ            -   invariant under:
      Q€             -     de-duplicate each
          F€         - flatten each
             `       - use this as both arguments of:
            p        -   Cartesian product
              Z€     - transpose each
                  Ƈ  - filter, keeping those for which:
                 Ƒ   -   invariant under:
                Q    -     de-duplicate (i.e. contains all the possible pairs)
                   Ḣ - head (just one of the Latin-Greaco squares we've found)

```
> 2 votes

# Answer
# 05AB1E, ~~26~~ ~~23~~ 22 bytes

*-3 bytes thanks to Emigna*

*-1 byte thanks to Kevin Cruijssen*

```
Lãœ.ΔIôDζ«D€í«ε€нÙgQ}P

```

Try it online!
> 3 votes

# Answer
# , ~~164~~ 148 bytes

-many bytes thanks to Giuseppe.

```
n=scan()
`!`=function(x)sd(colSums(2^x))
m=function()matrix(sample(n,n^2,1),n)
while(T)T=!(l=m())|!(g=m())|!t(l)|!t(g)|1-all(1:n^2%in%(n*l+g-n))
l
g

```

Try it online!

Dramatically inefficient - I think it's even worse than other brute force approaches. Even for `n=3`, it will probably time out on TIO. Here is an alternate version (155 bytes) which works for `n=3` in about 1 second.

Works by rejection. The function `m` draws a random matrix of integers between \\$1\\$ and \\$n\\$ (without forcing each integer to appear exactly \\$n\\$ times, or in different columns - this explains the slowness of the code, and is the only thing changed in the faster version). Call this function twice, to get the "latin" and "greek" squares `l` and `g`. Then we check:

1. `all(1:n^2%in%(n*l+g-n))`: are there \\$n^2\\$ different pairs of values in `l` \\$\times\\$ `g`?
2. are `l` and `g` latin squares?

To check that a matrix is a latin square, use the function `!`. Since point 1. above has been validated, we know that each integer appears \\$n\\$ times in each of `l` and `g`. Compute the column-wise sums of `2^l`: these sums are all equal if and only if each integer appears once in each column (and the value of the sum is then \\$2^{n+1}-2\\$). If this is true for both `l` and its transpose `t(l)`, then `l` is a latin square; same for `g`. The function `sd`, which computes the standard deviation, is an easy way to check whether all values of a vector are equal. Note that it doesn't work for the trivial cases \\$n=0\\$ and \\$n=1\\$ , which is OK according to the OP.

A final note: as often in R code golf, I used the variable `T`, which is initialized as `TRUE`, to gain a few bytes. But this means that when I needed the actual value `TRUE` in the definition of `m` (parameter `replace` in `sample`), I had to use `1` instead of `T`. Similarly, since I am redefining `!` as a function different from negation, I had to use `1-all(...)` instead of `!all(...)`.
> 3 votes

# Answer
# JavaScript (ES6),  ~~159 147~~  140 bytes

Returns a flat array of \\$n\times n\\$ pairs of non-negative integers.

This is a simple brute force search, and therefore very slow.

```
n=>(g=(m,j=0,X=n*n)=>j<n*n?!X--||m.some(([x,y],i)=>(X==x)+(Y==y)>(j/n^i/n&&j%n!=i%n),g(m,j,X),Y=X/n|0,X%=n)?o:g([...m,[X,Y]],j+1):o=m)(o=[])

```

Try it online! (with prettified output)

### Commented

```
n => (                      // n = input
  g = (                     // g is the recursive search function taking:
    m,                      //   m[] = flattened matrix
    j = 0,                  //   j   = current position in m[]
    X = n * n               //   X   = counter used to compute the current pair
  ) =>                      //
    j < n * n ?             // if j is less than n²:
      !X-- ||               //   abort right away if X is equal to 0; decrement X
      m.some(([x, y], i) => //   for each pair [x, y] at position i in m[]:
        (X == x) +          //     yield 1 if X is equal to x OR Y is equal to y
        (Y == y)            //     yield 2 if both values are equal
                            //     or yield 0 otherwise
        >                   //     test whether the above result is greater than:
        ( j / n ^ i / n &&  //       - 1 if i and j are neither on the same row
          j % n != i % n    //         nor the same column
        ),                  //       - 0 otherwise
                            //     initialization of some():
        g(m, j, X),         //       do a recursive call with all parameters unchanged
        Y = X / n | 0,      //       start with Y = floor(X / n)
        X %= n              //       and X = X % n
      ) ?                   //   end of some(); if it's falsy (or X was equal to 0):
        o                   //     just return o[]
      :                     //   else:
        g(                  //     do a recursive call:
          [...m, [X, Y]],   //       append [X, Y] to m[]
          j + 1             //       increment j
        )                   //     end of recursive call
    :                       // else:
      o = m                 //   success: update o[] to m[]
)(o = [])                   // initial call to g with m = o = []

```
> 2 votes

# Answer
# Haskell, ~~207 143~~ 233 bytes

```
(p,q)!(a,b)=p/=a&&q/=b
e=filter
f n|l<-[1..n]=head$0#[(c,k)|c<-l,k<-l]$[]where
	((i,j)%p)m|j==n=[[]]|1>0=[q:r|q<-p,all(q!)[m!!a!!j|a<-[0..i-1]],r<-(i,j+1)%e(q!)p$m]
	(i#p)m|i==n=[[]]|1>0=[r:o|r<-(i,0)%p$m,o<-(i+1)#e(`notElem`r)p$r:m]

```

Try it online!

OK, I think I finally got it this time. It works fine for n=5, n=6 times out on TIO but I think that might just be because this new algorithm is INCREDIBLY inefficient and basically checks all possibilities until it finds one that works. I'm running n=6 on my laptop now to see if it terminates with some more time.

Thanks again to @someone for pointing out the bugs in my previous versions
> 2 votes

# Answer
# Haskell, 187 bytes

```
import Data.List
import Data.List.Split
t=transpose
c a e h=[s|p<-a,s<-c(a\\[p])(e++[p])h,and[r==nub r|d<-h<$>t s,m<-[d,t d],r<-m]]++[e]
f n=head$c[[a,b]|a<-[1..n],b<-[1..n]][]$chunksOf n

```

Try it online!

This is equivalent to a DFS Brute-Force Approach. Times out for `n>3` on TIO, so only `n=1` and `n=3` work correctly.

## Explanation

```
import Data.List -- used for nub, transpose, and difference (\\)
import Data.List.Split -- used for chunksOf, shorter than a custom definition using splitAt or take/drop
-- we store each pair as [a,b]::[Int] instead of (a,b)::(Int,Int) to save bytes
t=transpose
-- c :: [[Int]] -> [[Int]] -> Int -> [[[Int]]]
-- recursive algorithm that yields a (lazy) list of all possible GL squares using
--  a = available pairs left (avoids duplicates)
--  e = existing square state, flattened (first `length e` pairs of the square in LTR reading order)
--  h = chunksOf n
c a e h=[
  s| -- where each possible square comes from
  p<-a, -- some available pair to add
  s<-c -- each square comes from recursion with
    (a\\[p]) -- that pair taken from the list of available pairs
    (e++[p]) -- that pair added to the existing square state
    h,
  and[r==nub r|  -- such that every "row" contains no duplicates
    d<-h<$>t s, -- d<-(list of [the rows of the first element of each pair, the rows of the second element of each pair])
    m<-[d,t d], -- m<-(rows of the square, columns of the square)
    r<-m -- row r<-m
    ]
  ]
  ++[e] -- base case: only reached if a==[] or if no valid possibilities exist (n==2 || n==6, not required to be handled)
f :: Int -> [[Int]]
f n=head$c -- the first valid GL square found from the initial conditions:
  [[a,b]|a<-[1..n],b<-[1..n]] -- all possible pairs
  [] -- empty existing GL square
  $chunksOf n -- given chunksOf function

```
> 2 votes

# Answer
## C#, 520 506 494 484 bytes

```
class P{static void Main(string[]a){int n=int.Parse(a[0]);int[,,]m=new int[n,n,2];int i=n,j,k,p,I,J;R:for(;i-->0;)for(j=n;j-->0;)for(k=2;k-->0;)if((m[i,j,k]=(m[i,j,k]+ 1) % n)!=0)goto Q;Q:for(i=n;i-->0;)for(j=n;j-->0;){for(k=2;k-->0;)for(p=n;p-->0;)if(p!=i&&m[i,j,k]==m[p,j,k]||p!=j&&m[i,j,k]==m[i,p,k])goto R;for(I=i;I<n;I++)for(J=0;J<n;J++)if(I!=i&&J!=j&&m[i,j,0]==m[I,J,0]&&m[i,j,1]==m[I,J,1])goto R;}for(i=n;i-->0;)for(j=n;j-->0;)System.Console.Write(m[i,j,0]+"-"+m[i,j,1]+" ");}}

```

The algorithm of findinf a square is very simple. It is... bruteforce. Yeah, it's stupid, but code golf is not about speed of a program, right?

The code before making it shorter:

```
using System;

public class Program
{
    static int[,,] Next(int[,,] m, int n){
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
            {
                for (int k = 0; k < 2; k++)
                {
                    if ((m[i, j, k] = (m[i, j, k] + 1) % n) != 0)
                    {
                        return m;
                    }
                }
            }
        }
        return m;
    }
    static bool Check(int[,,] m, int n)
    {
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
            {
                for (int k = 0; k < 2; k++)
                {
                    for (int p = 0; p < n; p++)
                    {
                        if (p != i)
                            if (m[i, j, k] == m[p, j, k])
                                return false;
                    }
                    for (int p = 0; p < n; p++)
                    {
                        if (p != j)
                            if (m[i, j, k] == m[i, p, k])
                                return false;
                    }
                }
            }
        }

        for (int i_1 = 0; i_1 < n; i_1++)
        {
            for (int j_1 = 0; j_1 < n; j_1++)
            {
                int i_2 = i_1;
                for (int j_2 = j_1 + 1; j_2 < n; j_2++)
                {
                    if (m[i_1, j_1, 0] == m[i_2, j_2, 0] && m[i_1, j_1, 1] == m[i_2, j_2, 1])
                        return false;
                }
                for (i_2 = i_1 + 1; i_2 < n; i_2++)
                {
                    for (int j_2 = 0; j_2 < n; j_2++)
                    {
                        if (m[i_1, j_1, 0] == m[i_2, j_2, 0] && m[i_1, j_1, 1] == m[i_2, j_2, 1])
                            return false;
                    }
                }
            }
        }
        return true;
    }
    public static void Main()
    {
        int n = 3;
        Console.WriteLine(n);
        int maxi = (int)System.Math.Pow((double)n, (double)n*n*2);
        int[,,] m = new int[n, n, 2];
        Debug(m, n);
        do
        {
            m = Next(m, n);
            if (m == null)
            {
                Console.WriteLine("!");
                return;
            }
            Console.WriteLine(maxi--);
        } while (!Check(m, n));

        Debug(m, n);
    }

    static void Debug(int[,,] m, int n)
    {
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
            {
                Console.Write(m[i, j, 0] + "-" + m[i, j, 1] + " ");
            }
            Console.WriteLine();
        }
        Console.WriteLine();
    }
}

```

Now, if you want to test it with n=3 you wil have to wait like an hour, so here is another version:

```
public static void Main()
{
    int n = 3;
    Console.WriteLine(n);
    int maxi = (int)System.Math.Pow((double)n, (double)n*n*2);
    int[,,] result = new int[n, n, 2];
    Parallel.For(0, n, (I) =>
    {
        int[,,] m = new int[n, n, 2];
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
            {
                m[i, j, 0] = I;
                m[i, j, 1] = I;
            }
        while (true)
        {
            m = Next(m, n);
            if (Equals(m, n, I + 1))
            {
                break;
            }
            if (Check(m, n))
            {
                Debug(m, n);
            }
        }
    });
}

```

Update: forgot to remove "public".

Update: used "System." instead of "using System;"; Also, thanks to Kevin Cruijssen, used "a" instead of "args".

Update: thanks to gastropner and someone.
> 1 votes

# Answer
# Octave, 182 bytes

Brute force method, TIO keeps timing out and I had to run it a bunch of times to get output for n=3, but theoretically this should be fine. Instead of pairs like (1,2) it outputs a matrix of complex conjugates like 1+2i. This might be stretching the rule a bit, but in my opinion it stll fits the output requirements. There must be a better way to do the two lines under the functino declaration though, but I'm not sure at the moment.

```
function[c]=f(n)
c=[0,0]
while(numel(c)>length(unique(c))||range([imag(sum(c)),imag(sum(c.')),real(sum(c)),real(sum(c.'))])>0)
a=fix(rand(n,n)*n);b=fix(rand(n,n)*n);c=a+1i*b;
end
end

```

Try it online!
> 1 votes

# Answer
# Wolfram Language (Mathematica), 123 bytes

```
P=Permutations
T=Transpose
g:=#&@@Select[T[Intersection[x=P[P@Range@#,{#}],T/@x]~Tuples~2,2<->4],DuplicateFreeQ[Join@@#]&]&

```

Try it online!

I use `TwoWayRule` notation `Transpose[...,2<->4]` to swap the 2nd and 4th dimensions of an array; otherwise this is fairly straightforward.

Ungolfed:

```
(* get all n-tuples of permutations *)
semiLSqs[n_] := Permutations@Range@n // Permutations[#, {n}] &;

(* Keep only the Latin squares *)
LSqs[n_] := semiLSqs[n] // Intersection[#, Transpose /@ #] &;

isGLSq[a_] := Join @@ a // DeleteDuplicates@# == # &;

(* Generate Graeco-Latin Squares from all pairs of Latin squares *)
GLSqs[n_] :=
  Tuples[LSqs[n], 2] // Transpose[#, 2 <-> 4] & // Select[isGLSq];

```
> 0 votes

# Answer
# Python 3, ~~271~~ ~~267~~ 241 bytes

Brute-force approach: Generate all permutations of the pairs until a Graeco-Latin square is found. Too slow to generate anything larger than `n=3` on TIO.

Thanks to alexz02 for golfing 26 bytes and to ceilingcat for golfing 4 bytes.

Try it online!

```
from itertools import*
def f(n):
 s=range(n);l=len
 for r in permutations(product(s,s)):
  if all([l({x[0]for x in r[i*n:-~i*n]})*l({x[1]for x in r[i*n:-~i*n]})*l({r[j*n+i][0]for j in s})*l({r[j*n+i][1]for j in s})==n**4for i in s]):return r

```

Explanation:

```
from itertools import *  # We will be using itertools.permutations and itertools.product
def f(n):  # Function taking the side length as a parameter
 s = range(n)  # Generate all the numbers from 0 to n-1
 l = len  # Shortcut to compute size of sets
 for r in permutations(product(s, s)):  # Generate all permutations of all pairs (Cartesian product) of those numbers, for each permutation:
  if all([l({x[0] for x in r[i * n : (- ~ i) * n]})  # If the first number is unique in row i ...
        * l({x[1] for x in r[i * n:(- ~ i) * n]})  # ... and the second number is unique in row i ...
        * l({r[j * n + i][0] for j in s})  # ... and the first number is unique in column i ...
        * l({r[j * n + i][1] for j in s})  # ... and the second number is unique in column i ...
        == n ** 4 for i in s]):  # ... in all columns i:
   return r  # Return the square

```
> 0 votes

---
Tags: code-golf
---


# Question
Title: Split a number in every way possible way within a threshold
# Task

Given a positive integer number and a threshold, split into every possible way without generating any numbers above the threshold.

# Examples

> Input: **15008**
> Threshold: **400**

Valid Output:
`[[1, 5, 0, 0, 8], [15, 0, 0, 8] [1, 50, 0, 8], [150, 0, 8]]`

Invalid outputs:

* `[[1, 5, 0, 0, 8], [15, 0, 0, 8], [150, 0, 8], [1, **500**, 8] ...` (500 is above threshold)
* `[[1, 5, 0, 0, 8], [15, 0, 0, 8], [150, 0, 8], [1, **5008**] ...`  (5008 is above threshold)
* `[[1, 5, 0, 0, 8], [15, 0, 0, 8], [150, 0, 8], [1, 5, **00**, 8] ...`  (double zeroes not allowed)
* `[[1, 5, 0, 0, 8], [15, 0, 0, 8], [150, 0, 8], [1, 5, 0, **08**] ...`  (leading zero not allowed)
* `[[1, 5, 0, 0, 8], [15, 0, 0, 8], [150, 0, 8], [1, 5, **008**] ...`  (leading zeroes not allowed)

> Input: **15008**
> Threshold: **17**

Valid Output:
`[[1, 5, 0, 0, 8], [15, 0, 0, 8]]`

Invalid output:
`[[1, 5, 0, 0, 8], [15, 0, 0, 8], [**150**,0,0,8]...` (150 is above threshold)

# Rules

* Valid threshold values are between 10 and 999.
* Double zeroes are not allowed on output.
* Leading zeroes are not allowed on output.
* Duplicates must be removed.
* Output order is not relevant

# Scoring

* Shortest answer in bytes wins

# Answer
# 05AB1E, 9 bytes

Generates all valid partitions and keeps those that join to the input number. This is *really slow* because it generates partitions of up to as many integers as the input number.

```
Ýsã0δÛʒJQ

```

Try it online! Don't try the cases from the challenge, even for the one with threshold 17 this tries to generate roughly \\$1.35 \cdot 10^{18839}\\$ partitions.

**Commented:**

```
           # first input: threshold, second input: number
Ý          # inclusive range [0 .. threshold]
 s         # swap to the input number
  ã        # take the range to this cartesian power
           # this generates all input-tuples of integers in [0 .. threshold]
   0δÛ     # for each tuple remove leading 0's
      ʒ    # only keep the partitions
       JQ  # which are equal to the input if joined into a single string

```

---

# 05AB1E, 10 bytes

This is more efficient, starting with actual partitions of the number and keeping the valid ones.

```
.œʒà@y*J¹Q

```

Try it online!

**Commented**:

```
            # first input: number, second input: threshold
.œ          # all string partitions of the first input
  ʒ         # keep all partitions where
   à        #   the maximum string
    @       #   is less or equal compared to the second input
     y*     #   multiply this (0 or 1) with each number in the partition
            #   all strings are converted to integers here, which removes any leading 0's
       J    #   join into single string
        ¹Q  #   is this equal to the first input?

```
> 5 votes

# Answer
# Jelly, 11 bytes

```
ŒṖḌfV⁼³ʋƇḶ}

```

Try it online!

-1 byte thanks to Jonathan Allan

-1 more byte thanks to Jonathan Allan

## How it works

```
ŒṖḌfV⁼³ʋƇḶ} - Main link. Takes n on the left and t on the right
ŒṖ          - All partitions of the digits of n
  Ḍ         - Convert the lists of digits to a list of numbers
          } - To t:
         Ḷ  -   Yield [0, 1, 2, ..., t-1]
        Ƈ   - Filter the partitions p, keeping those for which the following is true...
       ʋ      ...with each partition p on the left and the lowered range on the right:
   f        -   Keep the numbers in the lowered range (i.e. less than t)
    V       -   Concatenate the numbers into a single number
     ⁼³     -   Is that equal to n?

```
> 7 votes

# Answer
# Perl 5, 131 bytes

```
sub{($n,$t)=@_;grep{!grep$_>$t,/\d+/g}grep$n==s/,//gr,map$n=~s|.|$_/=2;$_*2%2?"$&,":$&|egr=~s/\b0+\B|00+//gr,0..2**($n=~y///c-1)-1}

```

Try it online!
> 3 votes

# Answer
# JavaScript (V8),  ~~97 90~~  89 bytes

Expects `(threshold)("integer")`.

```
t=>g=([v,...a],p=[],c='',u=[...p,c])=>c&&[+c]!=c|c>t?0:v?g(a,p,c+v)||c&&g(a,u,v):print(u)

```

Try it online!
> 3 votes

# Answer
# Wolfram Language (Mathematica), 128 bytes

```
Union@(w=Select)[d=#2;(f=Flatten)[Permutations/@Subsets@w[FromDigits/@Subsequences[s=(i=IntegerDigits)@#],#<d&],1],f[i/@#]==s&]&

```

Try it online!
> 2 votes

# Answer
# Japt, ~~31~~ 40 bytes

```
Êo1 Ôà ËF=UD£F=iSXÃFÃm¸®mnÃf_e<VÃâ f@¥Xq

```

Try it

* Input : number as string.
* Output : arrays of numbers.

```
    0oUÊÉJ  - enclosed indexes in descending order
    à       - combinations

    Now we have all the arrays of indexes to split.

    ËF=U    - map each group of indexes using a copy of number(F)
    D£F=iSXÃ  : inserting a space at every index(in reverse)
    FÃ        - return the spaced number
    m¸      - split each
    f_e<V   - filter out the result

```
* Edit : fixed deduplicate requirements and $00..$
> 2 votes

# Answer
# Scala, ~~164~~ ~~155~~ ~~132~~ 131 bytes

```
s=>t=>1 to 1<<s.size-1 map(i=>s.indices.map(j=>s(j)+","*(i>>j&1)).mkString.split(','))filter(_.forall(i=>i.toInt<=t&i==i.toInt+""))

```

Try it online!

Generating all partitions is still the most byte-consuming part, since there is no built-in for that.

The original version took a different approach (164 bytes), which was optimized by @user via three nice tricks (155 bytes), see comments for details and code. Now, I changed the strategy itself, which gives the current solution (132 bytes), and another byte removed thanks to another hint by @user (now: 131 bytes).

The current version uses the 1-bit-index-positions of a counter variable as split-positions.

The original version generated the indices of split-positions directly via combinations of all valid lengths and ranges.

**Some details on the "bit-hacking"**:

The outer loop generates all numbers from `1` up to `2^(numDigits-1)`, where the upper bound is represented via bit-shifting as `1<<s.size-1` (side note: as a consequence, this solution, based on signed Integer shifts, does only work for input numbers of at most 31 digits, which should be fair enough, but could easily be extended via BigInt to arbitrary input lengths). In binary representation, the outer loop variable `i` goes, for example, from `00001`, `00010`, `00011`, ... up to `10000` for a 5-digit input such as `15008`. The `j`'th bit position (counted from the right, starting at 0) indicates whether we should inject a "comma character" after the `j`'th index position of the input string. This is executed by the inner loop: The inner loop traverses the input string `s` char by char at index `j` and evaluates the expression `i>>j&1`. This expression "probes" whether the `j`'th bit of `i` is set by shifting `i` by `j` bit-positions to the right and then bit-AND-ing it with 1, which evaluates to 0 or 1, depending on whether the `j`'th bit is 1 or 0. As a consequence, the current char `s(j)` is preceeded by either the empty string `","*0` or by a comma `","*1`, depending on the `j`'th bit of `i`. (side note: bit representation `10000` represents the case of not including any comma, since it is injected after the last position. This case could also be achieved via `00000` instead, but then one would have to use the longer loop expression `0 until 1<<s.size-1` instead).
> 2 votes

# Answer
# Perl 5 (`-p`), 93 bytes

```
s/(.*\d)(\d.*)/$1,$2
$1.$2/?redo:y/.//d;$t=<>;$_=join$/,grep!(/\b0\d/|grep$_>$t,/\d+/g),/.+/g

```

Try it online!
> 2 votes

# Answer
# Python 3.8, 106 bytes

Recursive function taking the number as a string and the threshold as an integer.

```
f=lambda s,t:[[]][s>'':]or[[d]+p for i in range(s<'1'or len(s))if t>=int(d:=s[:i+1])for p in f(s[i+1:],t)]

```

Try it online!

**Commented**:

```
f=lambda s,t:                    # recursive function taking arguments:
                                 # s: str - the number to split
                                 # t: int - the threshold
[[]][s>'':]                      # if s is the empty string, return [[]]
or                               # otherwise:
[[d]+p                           #  a prefix of s prepended to a valid partition of the corresponding postfix
 for i in range(              )  #  iterate over every possible (decremented) postfix lengths i
                s<'1'or len(s)   #  if s starts with a 0, this can only be i=0, otherwise i=0, 1, ..., len(s)-1
 if t>=int(d:=s[:i+1])           #  the prefix is valid if it is not larger than the threshold as an integer
 for p in f(s[i+1:],t)]          #  iterate overall partitions of the postfix

```
> 2 votes

# Answer
# , <sup>~~73~~</sup> 70 bytes

```
(]#~0=1#.<:&>)<@](-:"1&(,&":/@>)#])[:<@;"1]<@#.~&10;.1~1,.2#:@i.@^<:@#

```

Try it online!

Turned out to be harder than I thought, and could likely be golfed more, but this will do for now.

Takes the threshold as an int, and the number to partition as a list of digits.
> 2 votes

# Answer
# Charcoal, 54 bytes

```
⊞υ⟦Ｓ⟧Ｆυ«≔§ι⁰ηＦＬη¿∧κ∨⁼⊖ＬηκＩ§ηκ⊞υ⁺⟦…ηκ✂ηκ⟧✂ι¹»ＮηΦυ¬‹η⌈Ｉι

```

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

```
⊞υ⟦Ｓ⟧

```

Start a breadth-first search for all partitions of the integer (as a string).

```
Ｆυ«

```

Loop over each partition.

```
≔§ι⁰η

```

Get the first string in the partition.

```
ＦＬη

```

Loop over each character index.

```
¿∧κ

```

If this is not the start of the string, and...

```
∨⁼⊖Ｌηκ

```

... either this is the last character of the string, or...

```
Ｉ§ηκ

```

... the current digit is not zero, then...

```
⊞υ⁺⟦…ηκ✂ηκ⟧✂ι¹

```

... create a new partition with the first string split at the current index.

```
»Ｎη

```

Input the threshold.

```
Φυ¬‹η⌈Ｉι

```

Print all partitions whose maximum value is not greater than the threshold.
> 1 votes

# Answer
# Stax, 18 bytes

```
âë┴fτ♪C┼Hnm♥ì╩≈╘9ù

```

Run and debug it

first input is the threshold and second input is the number as a string.
> 1 votes

# Answer
# Python 3.8, 210 bytes

```
def f(n,t):
 l=len(n);r=[]
 for i in range(2**l):c=[0]+[i for i,d in enumerate(f'{i:0{l}b}')if'1'==d]+[l];e=[n[g:h]for g,h in zip(c,c[1:])];r+=[e]*all(j and(k:=int(j))<t and(k>9or len(j)<2)for j in e)
 return r

```

Try it online!

Inputs a number as a string and the threshold as an integer.
Returns all splits as a list of lists of strings.
> 1 votes

# Answer
# Haskell, 89 bytes

A port of my Python answer.

```
""!t=[[]]
s!t=[d:p|i<-[1..last$length s:[1|s<"1"]],p<-drop i s!t,d<-[read$take i s],d<=t]

```

Try it online!
> 1 votes

---
Tags: code-golf, number, set-partitions
---