# I haven't seen that number before!

Write a program that goes through a string of non-whitespace characters (you may assume that they are digits 0 to 9, but nothing in the way they are to be processed depends on this) and adds spaces according to the following rules.

1. Let the current token be the empty string, and the previously emitted tokens be an empty set.
2. Iterate through the characters of the string. For each character, first append the character to the current token. Then if the current token is not already in the set of previously emitted tokens, add the current token to that set and let the new current token be the empty string.
3. If when you reach the end of the string the current token is empty, output the previously emitted tokens in order of emission, separated by a space character. Otherwise output the original string verbatim.

Input

The input to the STDIN should be a sequence of digits.

Output

The program should print the result as specified in step 3.

Samples

Sample inputs

2015
10101010
4815162342
101010101010
3455121372425
123456789101112131415
314159265358979323846264338327950288419716939937


Sample outputs

2 0 1 5
10101010
4 8 1 5 16 2 3 42
1 0 10 101 01 010
3 4 5 51 2 1 37 24 25
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
3 1 4 15 9 2 6 5 35 8 97 93 23 84 62 64 33 83 27 95 0 28 841 971 69 39 937


This is code golf, so standard CG rules apply. Shortest program in bytes wins.

(Please request any clarifications in the comments. I'm still new to this. Thanks!)

• 4815162342 I see what you did there, brotha. – Fatalize Sep 15 '15 at 12:36
• Proposed OEIS entry: numbers which are split into at least two segments by this process. – Martin Ender Sep 15 '15 at 14:05
• @IsmaelMiguel Step 5 (as any other step) can only advance one digit at a time. Once you’ve got 1 0 10 , the next iteration will find 1 (already used), then advance one to find 10 (already used), then advance one to find 101, which is new and would be ‘added’. It would then add a space and you'd get to a new 0, which has already been used, but is here at the end of the string. Therefore, the output would be 1 0 10 101 0, which is invalid (0 is repeated), and the script must then just output the input string. It could only make 1010 if 101 had already been used. – Janus Bahs Jacquet Sep 15 '15 at 15:32
• @kasperd No If a unique number cannot be formed at the end of the string, then the input should be printed verbatim 10101010 cannot be split so it is printed as is. – edc65 Sep 15 '15 at 17:05
• But when you enter step 5, the space would be after the 1, which would be a repeat. So instead you move right one in space 5, and then you move right one again in step 4, and you enter step 5 again and create 101. – Peter Taylor Sep 15 '15 at 20:43

# Pyth, 22 bytes

 faW!}=+kTYY~kdz?tkzsY


# Retina, 68 61 bytes

+\b(\w+?)(?<!\b\1 .*)(\w+)1 $2 (?=.* (.+)$(?<=\b\1 .+))
<empty>


<empty> is an empty line. Note the trailing space on line 3. You can run the above code from a single file with the -s flag.

## Explanation

+\b(\w+?)(?<!\b\1 .*)(\w+)1 $2  This first step implements rules 1 to 6. It is a regex substitution which is applied repeatedly until the string stops changing (that's what the + is for). In each step we add a single space into the string from left to right (following the rules of the challenge). The regex matches the shortest string of digits which hasn't appeared in the already processed part of the string. We ensure that we're looking at a prefix of the remaining string with the word boundary \b and checking that we can reach the end of the string without passing spaces with (\w+)$. The latter also ensures that we only perform one replacement per step.

(?=.* (.+)$(?<=\b\1 .+)) <empty>  This matches any space (which is at the end of the regex), provided that the last segment of the string is the same as any other segment in the string, and replaces them with the empty string. That is, we undo the first step if it resulted in an invalid final segment, implementing rule 7. ## Pyth, 24 23 bytes VzI!}=+kNYaY~k"";?kzjdY  Try it out here. VzI!}=+kNYaY~k"";?kzjdY Implicit: z=input(), k='', Y=[], d=' ' Vz ; For N in z: =+kN Append N to k I!} Y Is the above not in Y? aY k Append k to Y ~k"" After append, reset k to '' ?k Is k truthy (i.e. not '') z Print original input jdY Otherwise print Y joined on spaces  Thanks to @FryAmTheEggman for saving a byte :o) • @FryAmTheEggman A good call, I got pretty caught up in trying to preserve k's original value – Sok Sep 15 '15 at 14:59 # Python 3, 92 bytes i,n,*o=input(),"" for c in i:n+=c;o,n=[o+[n],o,"",n][n in o::2] print([" ".join(o),i][n>""])  Basically a heavily golfed version of @Willem's solution. • [" ".join(o),i][n>""] – FryAmTheEggman Sep 15 '15 at 14:55 • @FryAmTheEggman Ah cool, I had tried that with bool(n) but I didn't think of n>"". – orlp Sep 15 '15 at 14:56 ## Python 3, 100 99 bytes o=[];n="";i=input() for c in i: n+=c if not n in o:o.append(n);n="" print(i if n else" ".join(o))  • I fixed your byte count. Also, you should remove the space from else ". – mbomb007 Sep 15 '15 at 14:37 • Some common golfs Also, your original score was 100 bytes, I think. – FryAmTheEggman Sep 15 '15 at 14:37 • Cool thanks! I didn't know that the space after "else" could be removed. Another day lived, another day learned :) – Willem Sep 15 '15 at 14:49 # Brachylog, 91 bytes :_:_{h:0<|bhN,?hh:NrcH,?hB(l1,-1=A;BbA),?rhL:I(mH:Ar:[L]c:1&;:[H]:\"~w \"w,L:[H]c:_:Ar:1&)}  This made me realize that there's a lot of things about the syntax I need to change... ### Explanation :_:_ § Creates a list [Input,[],[]] {...} § Define a new predicate between the brackets and call it with the previous list as input h:0< § If the head of the input is negative, stop | § Else bhN, § Second element of Input is called N ?hh:NrcH, § N concatenated with the first element of Input is H ?hB(l1,-1=A;BbA), § Remaining digits A are either -1 if there's only one digit left or all the digits but the head otherwise ?rhL:I § List of used integers is called L ( mH:Ar:[L]c:1& § If H is already in L, call the predicate with input [A,H,L] ; § Else :[H]:\"~w \"w, § Print H followed by a space L:[H]c:_:Ar:1& § Call the predicate with input [A,[],M] where M is L with H appended to it )  # CJam, 26 bytes LLq{+_a2$&{a+L}|}/:X+X!S**


Test it here.

## Explanation

L        e# Push an empty array to keep track if the previous segments.
L        e# Push an empty array to build the current segment.
q{       e# For each character in the input...
+      e#   Add it to the current segment.
l[s]||$_=l.keys*' '  Uses the command line flag -p (or pl if your input has a trailing newline). Exploits several traits of Ruby Hash dictionaries: you can safely mutate the string you used to define a key without it changing the key (which doesn't work for other mutable types), .keys returns the keys in the order they were inserted, and the []||= operator provides a terse way of branching on whether a given key is already there. # Haskell, 105 bytes f does it. e""s""=unwords s e t s""=concat s++t e t s(c:r)|t&celems=e(t&c)s r|0<1=e""(s&(t&c))r a&b=a++[b] f=e""[]  # PHP - 148 bytes Cool challenge, lots of fun! $x=fgets(STDIN);$w=array();$k='';$l='';for($i=0;$i<strlen($x);$i++){$k.=$x[$i];if(!isset($w[$k])){$l.=$k.' ';$w[$k]=1;$k='';}}echo strlen($k)?$x:$l;