¡No he visto ese número antes!

31

Escribir un programa que pasa a través de una cadena de caracteres no está en blanco (se puede suponer que son los dígitos 0a 9, pero nada en la forma en que se van a procesar depende de esto) y añade los espacios de acuerdo a las siguientes reglas.

  1. Deje que el token actual sea la cadena vacía, y los tokens emitidos previamente sean un conjunto vacío.
  2. Iterar a través de los caracteres de la cadena. Para cada personaje, primero agregue el personaje al token actual. Luego, si el token actual aún no está en el conjunto de tokens emitidos previamente, agregue el token actual a ese conjunto y deje que el nuevo token actual sea la cadena vacía.
  3. Si cuando llega al final de la cadena, el token actual está vacío, muestre los tokens emitidos previamente en orden de emisión, separados por un carácter de espacio. De lo contrario, envíe la cadena original literalmente.

Entrada

La entrada al STDIN debe ser una secuencia de dígitos.

Salida

El programa debe imprimir el resultado como se especifica en el paso 3.

Muestras

Entradas de muestra

2015
10101010
4815162342
101010101010
3455121372425
123456789101112131415
314159265358979323846264338327950288419716939937

Resultados de muestra

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

Este es el código de golf, por lo que se aplican las reglas estándar de CG. El programa más corto en bytes gana.

(Solicite cualquier aclaración en los comentarios. Todavía soy nuevo en esto. ¡Gracias!)

Arcturus
fuente
10
4815162342Veo lo que hiciste allí, Brotha .
Fatalize
16
Entrada propuesta de OEIS: números que se dividen en al menos dos segmentos por este proceso
Martin Ender
3
@IsmaelMiguel El paso 5 (como cualquier otro paso) solo puede avanzar un dígito a la vez. Una vez que tenga 1 0 10 , la siguiente iteración encontrará 1(ya utilizada), luego avanzará una para encontrar 10(ya utilizada), luego avanzará una para buscar 101, que es nueva y se 'agregará'. Luego agregaría un espacio y llegaría a uno nuevo 0, que ya se ha utilizado, pero está aquí al final de la cadena. Por lo tanto, la salida sería 1 0 10 101 0, que no es válida ( 0se repite), y el script solo debe generar la cadena de entrada. Solo podría hacer 1010si 101ya se hubiera utilizado.
Janus Bahs Jacquet
3
@kasperd No If a unique number cannot be formed at the end of the string, then the input should be printed verbatim10101010 no se puede dividir, por lo que se imprime tal cual.
edc65
1
Pero cuando ingresas al paso 5, el espacio estará después del 1, lo que sería una repetición. Entonces, en cambio, te mueves hacia la derecha en el espacio 5, y luego te mueves hacia la derecha nuevamente en el paso 4, ingresas el paso 5 nuevamente y creas 101.
Peter Taylor

Respuestas:

9

Pyth, 22 bytes

 faW!}=+kTYY~kdz?tkzsY

Liderar el espacio es importante.

orlp
fuente
13

Retina , 68 61 bytes

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

<empty>Es una línea vacía. Tenga en cuenta el espacio final en la línea 3. Puede ejecutar el código anterior desde un solo archivo con la -sbandera.

Explicación

+`\b(\w+?)(?<!\b\1 .*)(\w+)$
$1 $2

Este primer paso implementa las reglas 1 a 6. Es una sustitución de expresiones regulares que se aplica repetidamente hasta que la cadena deja de cambiar (para eso +está). En cada paso agregamos un solo espacio en la cadena de izquierda a derecha (siguiendo las reglas del desafío). La expresión regular coincide con la cadena de dígitos más corta que no ha aparecido en la parte ya procesada de la cadena. Nos aseguramos de que estamos viendo un prefijo de la cadena restante con el límite de la palabra \by comprobando que podemos llegar al final de la cadena sin pasar espacios con (\w+)$. Este último también garantiza que solo realicemos un reemplazo por paso.

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

Esto coincide con cualquier espacio (que se encuentra al final de la expresión regular), siempre que el último segmento de la cadena sea el mismo que cualquier otro segmento de la cadena y los reemplace con la cadena vacía. Es decir, deshacemos el primer paso si resultó en un segmento final no válido, implementando la regla 7.

Martin Ender
fuente
11

Pyth 24 23 bytes

VzI!}=+kNYaY~k"";?kzjdY

Pruébalo aquí .

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

Gracias a @FryAmTheEggman por guardar un byte: o)

Sok
fuente
@FryAmTheEggman Una buena decisión, me quedé bastante atrapado tratando de preservar el valor original de k
Sok
8

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

Básicamente, una versión muy desarrollada de la solución de @ Willem.

orlp
fuente
[" ".join(o),i][n>""]
FryAmTheEggman
@FryAmTheEggman Ah genial, lo había intentado bool(n)pero no pensé en eso n>"".
orlp
6

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))
Willem
fuente
2
Arreglé tu cuenta de bytes. Además, debe eliminar el espacio de else ".
mbomb007
1
Algunos campos de golf comunes Además, creo que su puntaje original era de 100 bytes.
FryAmTheEggman
¡Genial, gracias! No sabía que el espacio después de "else" podría eliminarse. Otro día vivido, otro día aprendido :)
Willem
5

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&)}

Esto me hizo darme cuenta de que hay muchas cosas sobre la sintaxis que necesito cambiar ...

Explicación

:_:_              § 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
)
Fatalizar
fuente
4

CJam, 26 bytes

LLq{+_a2$&{a+L}|}/:X+X!S**

Pruébalo aquí.

Explicación

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.
Martin Ender
fuente
3

JavaScript (ES6), 109

Mi formato de salida no es exactamente el mismo de las muestras de salida en la consulta (hay un espacio inicial). No lo veo como un defecto, ya que el formato de salida no está especificado (solo el programa debería imprimir el número después del número ... )

Pruebe a ejecutar el fragmento a continuación en un navegador compatible con EcmaScript 6. Desarrollado con Firefox, probado y ejecutándose en el último 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>

edc65
fuente
2

GNU sed, 83 77 73 71 bytes

(Anote un extra porque requerimos -rbandera)

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

El bucle interno prueba una secuencia repetida y agrega caracteres según sea necesario hasta que aparezca un número único después del separador _. El bucle externo se mueve a lo _largo.

Versión ampliada y anotada:

#!/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/_//
Toby Speight
fuente
Podrías combinar ambos ten uno.
Usuario112638726
También /((\b[^ ]+).*\b\2)_/{se puede reescribir como /(\b[^ ]+).*\b\1_/{, no hay razón para 2 grupos de captura.
Usuario112638726
No hay problema :), ¡debes cambiar la referencia a \1!
Usuario112638726
1

Ruby, 57 + 1 = 58 bytes

s=''
l={}
$_.chars{|c|l[s<<c]||=s=''}
l[s]||$_=l.keys*' '

Utiliza el indicador de línea de comando -p(o plsi su entrada tiene una nueva línea final). Explota varios rasgos de los diccionarios Ruby Hash: puede mutar de forma segura la cadena que utilizó para definir una clave sin que cambie la clave (que no funciona para otros tipos mutables), .keysdevuelve las claves en el orden en que se insertaron y el []||=operador proporciona una forma concisa de ramificar si una clave dada ya está allí.

histocrat
fuente
1

Haskell, 105 bytes

f lo hace.

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""[]
Leif Willerts
fuente
1

PHP - 148 bytes

¡Genial desafío, mucha diversión!

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

fuente