31
\$\begingroup\$

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

\$\endgroup\$
17
  • 10
    \$\begingroup\$ 4815162342 I see what you did there, brotha. \$\endgroup\$
    – Fatalize
    Sep 15, 2015 at 12:36
  • 16
    \$\begingroup\$ Proposed OEIS entry: numbers which are split into at least two segments by this process. \$\endgroup\$ Sep 15, 2015 at 14:05
  • 3
    \$\begingroup\$ @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. \$\endgroup\$ Sep 15, 2015 at 15:32
  • 3
    \$\begingroup\$ @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. \$\endgroup\$
    – edc65
    Sep 15, 2015 at 17:05
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ Sep 15, 2015 at 20:43

12 Answers 12

13
\$\begingroup\$

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.

\$\endgroup\$
11
\$\begingroup\$

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)

\$\endgroup\$
1
  • \$\begingroup\$ @FryAmTheEggman A good call, I got pretty caught up in trying to preserve k's original value \$\endgroup\$
    – Sok
    Sep 15, 2015 at 14:59
9
\$\begingroup\$

Pyth, 22 bytes

 faW!}=+kTYY~kdz?tkzsY

Leading space is important.

\$\endgroup\$
7
\$\begingroup\$

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.

\$\endgroup\$
2
  • \$\begingroup\$ [" ".join(o),i][n>""] \$\endgroup\$ Sep 15, 2015 at 14:55
  • \$\begingroup\$ @FryAmTheEggman Ah cool, I had tried that with bool(n) but I didn't think of n>"". \$\endgroup\$
    – orlp
    Sep 15, 2015 at 14:56
6
\$\begingroup\$

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))
\$\endgroup\$
3
  • 2
    \$\begingroup\$ I fixed your byte count. Also, you should remove the space from else ". \$\endgroup\$
    – mbomb007
    Sep 15, 2015 at 14:37
  • 1
    \$\begingroup\$ Some common golfs Also, your original score was 100 bytes, I think. \$\endgroup\$ Sep 15, 2015 at 14:37
  • \$\begingroup\$ Cool thanks! I didn't know that the space after "else" could be removed. Another day lived, another day learned :) \$\endgroup\$
    – user42748
    Sep 15, 2015 at 14:49
5
\$\begingroup\$

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

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.
  _a2$&  e#   Duplicate and check if it's already in the segment list.
  {      e#   If not...
    a+L  e#     Add it to the list and push a new empty array for the next segment.
  }|
}/
:X+      e# Store the trailing segment in X and add it's *characters* to the list.
         e# For valid splittings, this trailing segment will be empty, so that the
         e# list remains unchanged.
X!       e# Push X again and take the logical NOT.
S*       e# Get that many spaces, i.e. 1 for valid segments and 0 otherwise.
*        e# Join the list with this string between elements.
\$\endgroup\$
3
\$\begingroup\$

JavaScript (ES6), 109

My output format is not exactly the same of the output samples in the questioin (there is a leading space). I don't see that as a flaw, as the output format is not specified (just The program should print the number after the number...)

Test running the snippet below in a EcmaScript 6 compliant browser. Developed with Firefox, tested and running on the latest Chrome.

/* Test: redirect console.log */ console.log=x=>O.innerHTML+=x+'\n';

F=s=>{for(z=s,b=l=o=' ';s[+l];)~o.search(b+(n=s.slice(0,++l)+b))||(s=s.slice(l),o+=n,l=0);console.log(s?z:o)}

/* Test cases */
test = [
  '2015',
,'10101010'
,'4815162342'
,'101010101010'
,'3455121372425'
,'123456789101112131415'
,'11312123133'
,'314159265358979323846264338327950288419716939937']

test.forEach(t=>{console.log('\n'+t);F(t)})
<pre id=O></pre>

\$\endgroup\$
2
\$\begingroup\$

GNU sed, 83 77 73 71 bytes

(Score one extra because we require -r flag)

h
s/./&_/
:
/(\b[^ ]+).*\b\1_/{
s/_(.)/\1_/
t
g
}
s/_(.)/ \1_/
t
s/_//

The inner loop tests for a repeated sequence and appends characters as needed until a unique number appears after the separator _. The outer loop moves _ along.

Expanded, annotated version:

#!/bin/sed -rf

# Stash original in hold space
h

# Add separator
s/./&_/

:
# If current candidate is a duplicate, ...
/(\b[^ ]+).*\b\1_/{
#  ...then attempt to lengthen it ...
s/_(.)/\1_/
# ... and repeat if we succeeded, ...
t
# ... otherwise, restore original string
g
}
# Insert a space, and move our separator along
s/_(.)/ \1_/
t

# Remove the separator if we still have it
s/_//
\$\endgroup\$
3
  • \$\begingroup\$ You could combine both the t's into one. \$\endgroup\$ Sep 16, 2015 at 14:51
  • \$\begingroup\$ Also /((\b[^ ]+).*\b\2)_/{ can be rewritten as /(\b[^ ]+).*\b\1_/{, no reason for 2 capture groups. \$\endgroup\$ Sep 16, 2015 at 15:31
  • \$\begingroup\$ No problem :), you need to change the reference to \1 though! \$\endgroup\$ Sep 16, 2015 at 15:51
1
\$\begingroup\$

Ruby, 57 + 1 = 58 bytes

s=''
l={}
$_.chars{|c|l[s<<c]||=s=''}
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.

\$\endgroup\$
1
\$\begingroup\$

Haskell, 105 bytes

f does it.

e""s""=unwords s
e t s""=concat s++t
e t s(c:r)|t&c`elem`s=e(t&c)s r|0<1=e""(s&(t&c))r
a&b=a++[b]
f=e""[]
\$\endgroup\$
1
\$\begingroup\$

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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