Encuentra el período más pequeño de un número> 1000 dígitos

10

Su trabajo es tomar este número como entrada (aunque también debería funcionar con cualquier otro número):

18349570345710975183495703457109751834957034571097518349570345710975183495703457109761834957034571097518349570345710975183495703457109751834957034571097518349570345710976183495703457109751834957034571097518349570345710975183495703457109751834957034571097618349570345710975183495703457109751834957034571097518349570345710975183495703457109761834957034571097518349570345710975183495703457109751834957034571097518349570345710976183495703457109751834957034571097518349570345710975183495703457109751834957034571097618349570345710975183495703457109751834957034571097518349570345710975183495703457109761834957034571097518349570345710975183495703457109751834957034571097518349570345710976183495703457109751834957034571097518349570345710975183495703457109751834957034571097618349570345710975183495703457109751834957034571097518349570345710975183495703457109761834957034571097518349570345710975183495703457109751834957034571097518349570345710976183495703457109751834957034571097518349570345710975183495703457109751834957034571097618349570345710975183495703457109751834957

y encuentre el período más pequeño, que es en este caso:

1834957034571097518349570345710975183495703457109751834957034571097518349570345710976

¡Buena suerte y diviertete!


Aclaraciones :

  • El número de entrada tiene como mínimo un período y un período parcial
  • El período siempre comienza al principio del número de entrada.
  • Período significa en este caso una secuencia de números que se repite.
Michael Bolli
fuente
¿Cuál es el tamaño máximo del número de entrada? Si quisiste decir que 1000 es el tamaño máximo, estás >mirando hacia el lado equivocado.
Level River St
@steveverrill: No, no hay un tamaño máximo del número de entrada per se, pero limitemos a 2 ^ 16 dígitos (porque usted lo solicitó).
Michael Bolli
3
¿Qué es un período?
FUZxxl
@FUZxxl en este caso: una secuencia de números que se repite.
Michael Bolli
3
Lo que está pidiendo es claro, pero realmente no debería llamarlo punto: en matemáticas, un punto solo se refiere a dígitos después del punto decimal repetido infinitamente muchas veces . Como opuesto, su entrada de prueba es un número entero y tiene un número finito de dígitos.
GOTO 0

Respuestas:

4

CJam, 20 16 bytes

Ll:Q{+_Q,*Q#!}=;

Lecturas de STDIN. Pruébalo en línea.

El código anterior requerirá memoria O (n 2 ) , donde n es la longitud de la entrada. Se va a trabajar con 2 de 16 dígitos, siempre y cuando usted tiene suficiente memoria.

Esto se puede arreglar el costo de cinco bytes adicionales:

Ll:Q{+_Q,1$,/)*Q#!}=;

Ejecución de ejemplo

$ cjam <(echo 'Ll:Q{+_Q,*Q#!}=;') <<< 18349570345710975183495703457109751834957034571097518349570345710975183495703457109761834957034571097518349570345710975183495703457109751834957034571097518349570345710976183495703457109751834957034571097518349570345710975183495703457109751834957034571097618349570345710975183495703457109751834957034571097518349570345710975183495703457109761834957034571097518349570345710975183495703457109751834957034571097518349570345710976183495703457109751834957034571097518349570345710975183495703457109751834957034571097618349570345710975183495703457109751834957034571097518349570345710975183495703457109761834957034571097518349570345710975183495703457109751834957034571097518349570345710976183495703457109751834957034571097518349570345710975183495703457109751834957034571097618349570345710975183495703457109751834957034571097518349570345710975183495703457109761834957034571097518349570345710975183495703457109751834957034571097518349570345710976183495703457109751834957034571097518349570345710975183495703457109751834957034571097618349570345710975183495703457109751834957; echo
1834957034571097518349570345710975183495703457109751834957034571097518349570345710976
$ cjam <(echo 'Ll:Q{+_Q,*Q#!}=;') <<< 12345123451; echo
12345
$ cjam <(echo 'Ll:Q{+_Q,*Q#!}=;') <<< 1234512345; echo
12345
$ cjam <(echo 'Ll:Q{+_Q,*Q#!}=;') <<< 123451; echo
12345

Cómo funciona

Para la entrada Q, la idea es repetir el primer carácter len (Q) veces y verificar si el índice de Q en el resultado es 0. Si no es así, repita los dos primeros caracteres len (Q) veces, etc.

L                   " Push L := [].                                                       ";
 l:Q                " Read one line from STDIN and save the result in Q.                  ";
    {        }=     " Find the first element q ∊ Q that yields a truthy value:            ";
     +              "   Execute L += [q].                                                 ";
      _Q,*Q#        "   Push (L * len(Q)).index(Q).                                       ";
            !       "   Compute the logical NOT of the index.                             ";
               ;    " Discard the last q. This leaves L on the stack.                     ";
Dennis
fuente
8

Regex (sabor .NET), 23 22 bytes

.+?(?=(.*$)(?<=^\1.*))

Esto coincidirá con el período requerido como una subcadena.

Pruébalo aquí.

¿Como funciona?

# The regex will always find a match, so there's no need to anchor it to
# the beginning of the string - the match will start there anyway.
.+?        # Try matching periods from shortest to longest
(?=        # Lookahead to ensure that what we've matched is actually
           # a period. By using a lookahead, we ensure that this is
           # not part of the match.
  (.*$)    # Match and capture the remainder of the input in group 1.
  (?<=     # Use a lookahead to ensure that this remainder is the same
           # as the beginning of the input. .NET lookaheads are best
           # read from right to left (because that's how they are matched)
           # so you might want to read the next three lines from the 
           # bottom up.
    ^      # Make sure we can reach the beginning of the string.
    \1     # Match group 1.
    .*     # Skip some characters, because the capture won't cover the
           # entire string.
  )
)
Martin Ender
fuente
1
Sin embargo, esto solo funciona si el período comienza al comienzo de la cadena. Ese es el caso aquí, pero no veo esto en las especificaciones. ¿Derecho?
Tim Pietzcker
1
@TimPietzcker Vea el comentario / edición de OP sobre la pregunta: el punto siempre comienza al comienzo de la cadena.
Martin Ender
Regex Storm .Net parece manejar también .NET, y no requiere Silverlight (no disponible en la mayoría de las plataformas).
Dennis
@ Dennis Gracias, ¡no lo sabía!
Martin Ender
1
@tolos Eso es porque no te aseguras de poder llegar al final de la cadena de esta manera. Por lo tanto, solo usará lo primero que se repita en absoluto. Por ejemplo aabaabaab, probablemente coincidirá aporque se repite. Todavía no he encontrado una manera de resolverlo en PCRE. Dennis intentó en una respuesta ahora eliminada, pero esa tampoco funcionó completamente. Por cierto, no necesitas g.
Martin Ender
3

Python 60

s es la cadena de dígitos

[s[:i]for i in range(len(s))if(s[:i]*len(s))[:len(s)]==s][0]

p.ej:

>>> s = '18349570345710975183495703457109751834957034571097518349570345710975183495703457109761834957034571097518349570345710975183495703457109751834957034571097518349570345710976183495703457109751834957034571097518349570345710975183495703457109751834957034571097618349570345710975183495703457109751834957034571097518349570345710975183495703457109761834957034571097518349570345710975183495703457109751834957034571097518349570345710976183495703457109751834957034571097518349570345710975183495703457109751834957034571097618349570345710975183495703457109751834957034571097518349570345710975183495703457109761834957034571097518349570345710975183495703457109751834957034571097518349570345710976183495703457109751834957034571097518349570345710975183495703457109751834957034571097618349570345710975183495703457109751834957034571097518349570345710975183495703457109761834957034571097518349570345710975183495703457109751834957034571097518349570345710976183495703457109751834957034571097518349570345710975183495703457109751834957034571097618349570345710975183495703457109751834957'
>>> [s[:i]for i in range(len(s))if(s[:i]*len(s))[:len(s)]==s][0]
'1834957034571097518349570345710975183495703457109751834957034571097518349570345710976'
gnibbler
fuente
1

Pyth , 14 caracteres

hf}z*lzTm<zdUz

Explicación:

implicit:      z = input()
h              head(
 f                  filter(lambda T:
  }z                                z in
    *lz                                  len(z) * 
       T                                          T,
  m                        map(lambda d:
   <zd                                  z[:d],
   Uz                                   range(len(d)))))

Esencialmente, genera todas las secuencias iniciales de la entrada, se repite cada una len(z)y ve si zla entrada se encuentra dentro de la cadena resultante.


Esta no es una respuesta válida, pero recientemente se agregó una característica a Pyth, después de que se hizo la pregunta, que permite una solución de 12 caracteres:

<zf}z*lz<zT1

Esto utiliza el filtro en la función de entero.

isaacg
fuente
0

Japt , 8 bytes

å+ æ@¶îX

Intentalo

-2 bytes gracias a Shaggy!

Transpiled JS explicado:

// U is the input string representation of the number
U
 // cumulative reduce using the '+' operator
 // the result is an array of strings length 1, 2, ..., N
 // all substrings start with the first character from input
 .å("+")
 // find the first match
 .æ(function(X, Y, Z) {
  // repeat the substring until it is as long as the input
  // and compare it to the input
  return U === U.î(X)
 })
dana
fuente
1
8 bytes:å+ æ@¶îX
Shaggy
Excelente :) He visto lanzar un operador a la función de reducción antes, pero lo olvidé.
dana
0

Java 8, 125 bytes

Toma la entrada como una cadena ya que no hay una forma razonable de representar un número de más de 1000 dígitos en Java que no sea una cadena (No BigInteger, por favor).

s->{String o="";for(int i=0;java.util.Arrays.stream(s.split(o+=s.charAt(i++))).filter(b->!b.isEmpty()).count()>1;);return o;}

Pruébalo en línea!

Benjamin Urquhart
fuente
Se puede reemplazar Stringcon var. -3 bytes
Adam
@Adam Java 8, aunque
Benjamin Urquhart
Oh, no vi eso.
Adam