Finden Sie den kleinsten Zeitraum aus einer> 1000-stelligen Zahl

10

Ihre Aufgabe ist es, diese Nummer als Eingabe zu verwenden (obwohl sie auch mit jeder anderen Nummer funktionieren sollte):

18349570345710975183495703457109751834957034571097518349570345710975183495703457109761834957034571097518349570345710975183495703457109751834957034571097518349570345710976183495703457109751834957034571097518349570345710975183495703457109751834957034571097618349570345710975183495703457109751834957034571097518349570345710975183495703457109761834957034571097518349570345710975183495703457109751834957034571097518349570345710976183495703457109751834957034571097518349570345710975183495703457109751834957034571097618349570345710975183495703457109751834957034571097518349570345710975183495703457109761834957034571097518349570345710975183495703457109751834957034571097518349570345710976183495703457109751834957034571097518349570345710975183495703457109751834957034571097618349570345710975183495703457109751834957034571097518349570345710975183495703457109761834957034571097518349570345710975183495703457109751834957034571097518349570345710976183495703457109751834957034571097518349570345710975183495703457109751834957034571097618349570345710975183495703457109751834957

und finde die kleinste Periode, die in diesem Fall ist:

1834957034571097518349570345710975183495703457109751834957034571097518349570345710976

Viel Glück und hab Spaß!


Erläuterungen :

  • Die eingegebene Nummer hat mindestens eine Periode und eine Teilperiode
  • Die Periode beginnt immer am Anfang der eingegebenen Nummer
  • Punkt bedeutet in diesem Fall eine Folge von Zahlen, die sich wiederholt.
Michael Bolli
quelle
Was ist die maximale Größe der eingegebenen Nummer? Wenn Sie 1000 als maximale Größe gemeint haben, ist Ihre >Richtung falsch.
Level River St
@steveverrill: Nein, es gibt keine maximale Größe der eingegebenen Nummer an sich, aber beschränken wir uns auf 2 ^ 16 Stellen (weil Sie gefragt haben).
Michael Bolli
3
Was ist eine Periode?
FUZxxl
@FUZxxl in diesem Fall: eine Folge von Zahlen, die sich wiederholt.
Michael Bolli
3
Was Sie verlangen, ist klar, aber Sie sollten es wirklich nicht als Punkt bezeichnen: In der Mathematik bezieht sich ein Punkt nur auf Ziffern nach dem Dezimalpunkt, die unendlich oft wiederholt werden . Im Gegensatz dazu ist Ihre Testeingabe eine Ganzzahl und hat eine endliche Anzahl von Ziffern.
GOTO 0

Antworten:

4

CJam, 20 16 Bytes

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

Liest von STDIN. Probieren Sie es online aus.

Der obige Code benötigt einen O (n 2 ) -Speicher, wobei n die Länge der Eingabe ist. Es wird mit 2 arbeiten 16 Ziffern, solange Sie genügend Speicher haben.

Hiermit können die Kosten für fünf zusätzliche Bytes behoben werden:

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

Beispiellauf

$ 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

Wie es funktioniert

Für die Eingabe Q besteht die Idee darin, das erste Zeichen len (Q) Mal zu wiederholen und zu überprüfen, ob der Index von Q im Ergebnis 0 ist. Wenn dies nicht der Fall ist, wiederholen Sie die ersten beiden Zeichen len (Q) Mal usw.

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
quelle
8

Regex (.NET-Geschmack), 23 22 Byte

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

Dies entspricht dem erforderlichen Zeitraum als Teilzeichenfolge.

Testen Sie es hier.

Wie funktioniert es?

# 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
quelle
1
Dies funktioniert jedoch nur, wenn der Punkt am Anfang der Zeichenfolge beginnt. Das ist hier zufällig der Fall, aber ich sehe dies nicht in den Spezifikationen. Recht?
Tim Pietzcker
1
@TimPietzcker Siehe OPs Kommentar / Bearbeitung zur Frage: Der Punkt beginnt immer am Anfang der Zeichenfolge.
Martin Ender
Regex Storm .Net scheint auch .NET zu verarbeiten und erfordert kein Silverlight (auf den meisten Plattformen nicht verfügbar).
Dennis
@ Tennis Danke, das wusste ich nicht!
Martin Ender
1
@tolos Das liegt daran, dass Sie nicht sicherstellen, dass Sie das Ende der Zeichenfolge so erreichen können. Daher wird nur das erste verwendet, was sich überhaupt wiederholt. ZB aabaabaabwird wahrscheinlich übereinstimmen, aweil es sich wiederholt. Ich habe noch keinen Weg gefunden, es in PCRE zu lösen. Dennis versuchte es in einer jetzt gelöschten Antwort, aber diese funktionierte auch nicht vollständig. Übrigens brauchst du nicht g.
Martin Ender
3

Python 60

s ist die Ziffernfolge

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

z.B:

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

Pyth , 14 Zeichen

hf}z*lzTm<zdUz

Erläuterung:

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

Im Wesentlichen werden alle Anfangssequenzen der Eingabe generiert, jedes len(z)Mal wiederholt und es wird geprüft, ob zdie Eingabe innerhalb der resultierenden Zeichenfolge liegt.


Dies ist keine gültige Antwort, aber Pyth wurde kürzlich eine Funktion hinzugefügt, nachdem eine Frage gestellt wurde, die eine Lösung mit 12 Zeichen ermöglicht:

<zf}z*lz<zT1

Dies verwendet die Filter-on-Integer-Funktion.

isaacg
quelle
0

Japt , 8 Bytes

å+ æ@¶îX

Versuch es

-2 Bytes dank Shaggy!

Transpiled JS Erklärt:

// 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
quelle
1
8 Bytes:å+ æ@¶îX
Shaggy
Ausgezeichnet :) Ich habe schon einmal gesehen, wie ein Operator in die Reduzierungsfunktion geworfen wurde, habe es aber vergessen.
Dana
0

Java 8, 125 Bytes

Nimmt die Eingabe als Zeichenfolge auf, da es in Java keine vernünftige Möglichkeit gibt, eine mehr als 1000-stellige Zahl als eine Zeichenfolge darzustellen (bitte keine BigInteger).

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

Probieren Sie es online aus!

Benjamin Urquhart
quelle
Sie können durch Stringvar ersetzen . -3 Bytes
Adam
@ Adam Java 8 obwohl
Benjamin Urquhart
Oh, habe das nicht gesehen.
Adam