Split a number in every way possible way within a threshold

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
• Welcome to the site, and nice first question! I'd recommend removing the last bullet point as it contradicts our I/O defaults. I'd also recommend posting future challenge proposals in the Sandbox to get feedback before posting to main Dec 29, 2020 at 17:16
• For the 15008, 7 example, is that output example supposed to be exhaustive? If so, why aren't [1,5,0], [0,0], [1,0] etc. in the output? In fact, it seems as though your two examples are contradictory. Are we supposed to only keep partitions where each element is below the threshold (i.e the first example), or do we remove elements from each partition above the threshold (second example) Dec 29, 2020 at 17:33
• What does "Duplicates must be removed" mean? The only duplicates I can think of would be those considering reordering (e.g. $12223$ giving both [1,22,2,3] and [1,2,22,3]) - is that what it means? Dec 29, 2020 at 19:18
• in every way possible way : that's too many ways ... by the way. Dec 30, 2020 at 11:06
• You say duplicates must be removed, but your example includes the number 0 twice in its valid results. Also, are double-zeroes allowed if they aren't leading zeroes, e.g. if you took your example of 15008, but with a threshold of 600, would [1, 500, 8] be a valid partitioning? Dec 30, 2020 at 20:34

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?

• I think Q is unnecessary here as the code before does not produce duplicates. Dec 29, 2020 at 19:26
• @JonathanAllan Oh yeah, because duplicates only arise from deleting a digit, and those partitions are filtered with V=¥Ƈ⁸. Nice find! Dec 29, 2020 at 19:28
• 11 bytes (full program): ŒṖḌfV⁼³ʋƇḶ} TIO. Can it be golfed? Dec 29, 2020 at 19:48
• @JonathanAllan Wow, that's a really clever use of f and Ḷ! I can't see anything obvious, but I'll tinker around with it Dec 29, 2020 at 19:51

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?


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! • Try it online! could save some bytes except if I missed something Dec 29, 2020 at 20:50 • Try it online! different solution 95 bytes Dec 29, 2020 at 22:14 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! 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! 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..$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!

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


Scala, 164155132 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).

• 155 bytes by currying, merging two maps together, and taking advantage of operator precedence. A for-yield might be even shorter, though I haven't tried yet
– user
Dec 30, 2020 at 17:11
• Thanks! Currying and removing short-circuit operators will generalize well to other problems as well! However, I found another approach for generating the partitions, which saves another 23 bytes, see above :) Dec 30, 2020 at 22:02
• Nice! No idea how the bit hacking works, but it looks really cool. Could you add an explanation too?
– user
Dec 30, 2020 at 22:08
• By the way, you can directly use 1<<s.size-1. No parentheses needed because of op precedence
– user
Dec 30, 2020 at 23:18
• Thanks! I really need to train my intuition on operator precedence for golfing. As a positive consequence, now the solution works for numbers up to 31 digits, not only 30 :) Dec 30, 2020 at 23:33

J, 73 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.

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.

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.

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.

""!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]