14
\$\begingroup\$

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.
\$\endgroup\$
  • \$\begingroup\$ I made a small edit to clarify the challenge a little bit, roll back if you don't agree! \$\endgroup\$ – flawr Jan 3 at 23:38
  • 8
    \$\begingroup\$ Another interesting example would be 10010. \$\endgroup\$ – flawr Jan 3 at 23:44
  • 2
    \$\begingroup\$ Suggested test case: 988382 -> [ 9, 88, 3, 8, 2 ]. \$\endgroup\$ – Arnauld Jan 4 at 10:54
  • 1
    \$\begingroup\$ @Jonah The purpose of the ten thousand digit requirement is just to emphasize the need for a complete algorithm rather than a fast one - similar to the "must work for arbitrarily long inputs" without actually requiring arbitrarily long inputs. Putting bounds on the problem opens the door to certain kinds of amusing solutions, such as circuits. \$\endgroup\$ – Beefster Jan 5 at 1:27
  • 1
    \$\begingroup\$ @Jonah - no complexity or time requirements since I suspect this problem might not be in P \$\endgroup\$ – Beefster Jan 5 at 1:31
4
\$\begingroup\$

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
\$\endgroup\$
  • 1
    \$\begingroup\$ Just like my now deleted 05AB1E answer it fails for 10010010. It uses partition [100,10,01,0] and the 01 becomes 1. \$\endgroup\$ – Kevin Cruijssen Jan 6 at 16:39
  • 1
    \$\begingroup\$ @KevinCruijssen fixed I think \$\endgroup\$ – Nick Kennedy Jan 6 at 17:37
  • 1
    \$\begingroup\$ Ah, smart! I could do something similar to fix my 05AB1E answer. :D EDIT: I'll leave my answer deleted, since Grimmy already posted the fixed answer (as I said he could when I deleted my answer). \$\endgroup\$ – Kevin Cruijssen Jan 6 at 18:04
2
\$\begingroup\$

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
\$\endgroup\$
2
\$\begingroup\$

05AB1E, 10 bytes

.œʒÙïJQ}éθ

Try it online!

\$\endgroup\$
  • \$\begingroup\$ Ah, I see you've already posted. In that case I'll leave my answer deleted. Was about to add the ï to it to fix both my programs after the tip of NickKennedy. \$\endgroup\$ – Kevin Cruijssen Jan 6 at 18:07
1
\$\begingroup\$

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
)                        //
\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

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!

\$\endgroup\$
  • \$\begingroup\$ Shouldn't 1001000 return 10,0,1000? Your return 100,1000. \$\endgroup\$ – Kjetil S. Jan 9 at 15:24
  • \$\begingroup\$ @KjetilS. you are right. Fixing \$\endgroup\$ – Value Ink Jan 10 at 17:16
0
\$\begingroup\$

Charcoal, 55 bytes

⊞υ⟦ωS⟧Fυ«≔⊟ιθFLθF∧I§θκ¬№ι…θκ⊞υ⁺ι⟦…θκ✂θκ⟧⊞ιθ»⊟Φυ⁼Lι⌈EυLλ

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

⊞υ⟦ωS⟧Fυ«

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.

FLθ

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

F∧I§θκ¬№ι…θκ

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.

⊟Φυ⁼Lι⌈EυLλ

Print the last entry of those with the longest length.

\$\endgroup\$
  • \$\begingroup\$ @Jonah Optimising for code golf tends to result in inefficient algorithms. I'm sure it could do long streams given sufficient resources. As for your sidenode, I try to code in verbose mode, but that's not always possible e.g. a cat program whose reverse is a reversal program. \$\endgroup\$ – Neil Jan 4 at 21:41
0
\$\begingroup\$

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
\$\endgroup\$
0
\$\begingroup\$

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);
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.