Split a number in every way possible way within a threshold

Question

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 1

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?

Answer 2

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?

Answer 3

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!

Answer 4

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!

Answer 5

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!

Answer 6

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..$

Answer 7

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!

Answer 8

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

Answer 9

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).

Answer 10

J, ⁷³ 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.

Answer 11

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.

Answer 12

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.

Answer 13

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.

Answer 14

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!