Partitioning Digits into Distinct Integers

Question

Given a sequence of base-10 digits, output the longest list of integers that contains all the digits exactly once, in the order in which they appeared in the input, without repeating any integers.

Examples

Input: 12345
Output: [1, 2, 3, 4, 5]

Input: 12123
Output: [1, 2, 12, 3]

Input: 10010
Output: [100, 1, 0]

Input: 35353
Output: [35, 3, 53] or [3, 5, 353]

Input: 988382
Output: [9, 88, 3, 8, 2]

Rules

• Use any convenient formats for input and output
• You must support input sequences of up to 10,000 digits long.
• You must support integers of 18 decimal digits or more (This will fit in 64-bit integers, though you may want work with strings anyway)
• You may assume that the input given can be made into a sequences where the 18-digit number requirement is possible.
• If there is more than one possible longest sequence, you may output any one of them.
• Numbers in the output sequence may not be zero-padded.
• Zero is a valid element, but it can, of course, only be used once in the output.
• There is no time or complexity requirement.
• Shortest code wins.

Answer 1

Jelly, 14 bytes

ŒṖḌD$ƑƇḌQƑƇLÞṪ

Try it online!

A monadic link taking a list of base-10 digits and returning a list of integers.

Added a byte (and switched to numbers) because of the zero padding issue.

Added 5 bytes to fix a further issue with zeros pointed out by @KevinCruijssen - thanks!

Explanation

ŒṖ             | Partitions of list
  ḌD$ƑƇ        | Keep only those invariant when converted to integers and back to lists of digits
       Ḍ       | Convert from lists of lists of lists of decimal digits to lists of lists of integers
        QƑƇ    | Keep only those invariant when uniquified
           LÞ  | Sort by ascending length
             Ṫ | Tail

Answer 2

Perl 6, 49 bytes

{m:ex/(0|<![0]>.+)+<!{$0>set ~<<$0}>/.max(+*[0])}

Try it online!

Outputs a regex match with a list of submatches as the integers.

Explanation:

{                                               }  # Anonymous code block
 m:ex/                              /    # Match all
      (          )+                        # Series of
       0|                                  # Zero or
         <![0]>.+                          # Numbers not starting with zero
                   <!{$0          }>     # Where the series is not
                        >set ~<<$0       # Larger than the set of itself
                                     .max(+*[0])   # Return the maximum by length of series

Answer 3

05AB1E, 10 bytes

.œʒÙïJQ}éθ

Try it online!

Answer 4

JavaScript (ES6), 100 bytes

Takes input as a string.

f=([v,...a],p=o=[],c='')=>(v&&f(a,p,c+v),c?p.includes(c)|[+c]!=c||f(a,[...p,c],v):p[o.length]?o=p:o)

Try it online!

Commented

f = (                    // f is a recursive function taking:
  [v,                    //   v   = next digit
     ...a],              //   a[] = array of remaining digits
  p = o = [],            //   p[] = current list, o[] = best list
  c = ''                 //   c   = current pattern
) => (                   //
  v &&                   // if v is defined:
    f(a, p, c + v),      //   do a recursive call with c + v
  c ?                    // if c is not empty:
    p.includes(c) |      //   unless p[] already includes c
    [+c] != c ||         //   or c has leading zeros:
      f(a, [...p, c], v) //     do a recursive call with c appended to p[]
  :                      // else:
    p[o.length] ? o = p  //   update o[] to p[] if p[] is longer than o[]
                : o      //   or just return o[] unchanged otherwise
)                        //

Answer 5

Perl 5, 119 bytes

sub f{($s=$_=shift)=~/\b(\d+)\b.*\b\1\b/?push@_,grep!/\b0\d/,map$s=~s/^((.*?,){$_}.*?),/$1/r,0..y/,//:return$s while@_}

Try it online!

sub f {
  ($s=$_=shift)                               #get next trial
    =~ /\b(\d+)\b.*\b\1\b/                    #duplicate exist in trial?
    ? push @_,                                #if so, add trials
           grep !/\b0\d/,                     #without zero-leading
           map $s=~s/^((.*?,){$_}.*?),/$1/r,  #remove nth comma
           0 .. y/,//                         #that many trials (-1)
    : return $s                               #answer = 1st w.o. duplicate
        while @_                              #while trials left
}

Passes:

12345     → 1,2,3,4,5
12123     → 12,1,2,3
10010     → 100,1,0
35353     → 353,5,3
988382    → 9,88,3,8,2
1001000   → 10,0,1000
100100010 → 100,1000,1,0

Answer 6

Burlesque, 24 bytes

PppPsu5cb{++pP==}f[:U_[~

Try it online!

Not necessarily the best method, think I could probably save on some loading.

Pp    #Save number (as str) for later use
pP    #Load number
su    #Find all substrings of number
5cb   #Find all combinations of substrings of length 5 (as list of list of str)
{
 ++   #Concatenate all strings
 pP   #Load number
 ==   #Is equal
}f[   #Filter for all substring combinations where 
       the concatenation is the same as original number
:U_   #Filter for all elements unique
[~    #Take the last one

Answer 7

Ruby, 115 112 114 bytes

Takes input as a string. A recursive function that takes a string and a list of previously-used numbers; it gets all substrings that start with the first character, and for each gets the result of the recursive call on the rest of the string. It then decides what the longest string that still matches is.

f=->s,*e{(1..l=s.size).map{|i|*q=x=s[0,i];q-e==[]||x=~/^0./?[]:q+f[s[i,l],*q+e]}.max_by{|i|s==i*''?i.size: 0}||[]}

Try it online!

Answer 8

Charcoal, 55 bytes

⊞υ⟦ωＳ⟧Ｆυ«≔⊟ιθＦＬθＦ∧Ｉ§θκ¬№ι…θκ⊞υ⁺ι⟦…θκ✂θκ⟧⊞ιθ»⊟Φυ⁼Ｌι⌈ＥυＬλ

Try it online! Link is to verbose version of code. Outputs each integer preceded by a newline. Explanation:

⊞υ⟦ωＳ⟧Ｆυ«

Perform a breadth-first search starting from the input and having only seen the empty string before.

≔⊟ιθ

Temporarily separate the current suffix from the list of previously seen integers.

ＦＬθ

Loop over the potential new suffixes. (The next integer is then the current suffix with the new suffix removed.)

Ｆ∧Ｉ§θκ¬№ι…θκ

Check that the new suffix does not begin with zero and the next integer has not already been seen.

⊞υ⁺ι⟦…θκ✂θκ⟧

If so then create a new entry including the next integer and the new suffix.

⊞ιθ»

Restore the suffix for the entry in case no suffixes were valid.

⊟Φυ⁼Ｌι⌈ＥυＬλ

Print the last entry of those with the longest length.

Answer 9

PHP, 380 338 287 279 bytes

<?php $s=array_fill(0,$n=strlen($u=$argv[1]),0);$m=[];g:if(array_sum($s)==$n){$b=[];$p=0;$k=1;foreach($s as$c){$c&&($b[]=substr($u,$p,$c))[0]==0&&$c>1&&$k=0;$p+=$c;}if($k&&array_unique($b)==$b&&$b>$m)$m=$b;}for($i=0;;){if(++$s[$i]<=$n)goto g;$s[$i++]=0;$i==$n&&die(print_r($m));}

Try it online!

Ungolfed

<?php
$input= $argv[1];

$len=strlen($input);
$counts=array_fill(0,$len,0); // enumerator - basically a counter to base input-length, where each digit represents substring length
$max=0;
$max_sub=[];
do {
    // add up size of all substring lengths
    $size=0;
    for($i=0;$i<$len;$i++) {
        $size+=$counts[$i];
    }

    // size matches string length
    if ($size==$len){
        $subs=[];
        $pos=0;

        // get the substrings and ensure constraints
        $ok=true;
        for ($i=0;$i<$len;$i++) {
            //exclude zero length substrings
            if ($counts[$i]>0) {
                $sub = $subs[] = substr($input, $pos, $counts[$i]);
                if ($sub[0]=='0' && $counts[$i]>1) {
                    $ok=false;
                    break;
                }
                $pos+=$counts[$i];
            }
        }

        // makes sure no repeated substrings
        for($i=0;$i<count($subs);$i++){
            for($j=0;$j<$i;$j++){
                if($subs[$i]==$subs[$j]) {
                    $ok=false;
                    break(2);
                }
            }
        }

        // if all ok, then check this has maximal number of substrings
        if ($ok) {
            if (count($subs)>$max) {
                $max=count($subs);
                $max_sub=$subs;
            }
        }
    }

    // increment counter
    for($i=0;$i<$len;$i++) {
        $counts[$i]++;
        if ($counts[$i]<=$len) {
            break;
        }
        $counts[$i]=0;
    }

// counter hasn't reached the end
} while ($i<$len);

echo json_encode($max_sub);