Reihe von natürlichen Zahlen

22

Definition

Es gibt eine unendliche Reihe verketteter natürlicher Zahlen (positive ganze Zahlen, beginnend mit 1):

1234567891011121314151617181920212223...

Herausforderung

  • Schreiben Sie ein Programm in einer beliebigen Sprache, das die Positionsnummer als Eingabe akzeptiert und eine Ziffer von dieser Position in der oben definierten Zeile ausgibt.
  • Die Positionsnummer ist eine positive Ganzzahl beliebiger Größe. Das heißt, die erste Position ist 1 und ergibt die Ausgangsziffer '1'.
  • Die Eingabe erfolgt entweder dezimal (z. B. 13498573249827349823740000191) oder in elektronischer Form (z. B. 1.2e789) entsprechend einer positiven Ganzzahl.
  • Das Programm muss in angemessener Zeit (10 Sekunden auf einem modernen PC / Mac) beendet werden, wenn ein sehr großer Index als Eingabe verwendet wird (z. B. 1e123456 - das ist 1 mit 123456 Nullen). Eine einfache Iterationsschleife ist daher nicht akzeptabel.
  • Bei ungültiger Eingabe muss das Programm nach 1 s mit einem Fehler abgebrochen werden. Z.B. 1,23e (ungültig) oder 1,23e1 (entspricht 12,3 - keine ganze Zahl)
  • Es ist in Ordnung, die öffentliche BigNum-Bibliothek zu verwenden, um Zahlen zu analysieren / zu speichern und einfache mathematische Operationen mit ihnen durchzuführen (+ - * / exp). Es wird keine Byte-Strafe angewendet.
  • Kürzester Code gewinnt.

TL; DR

  • Eingabe: Bignum Integer
  • Ausgabe: Ziffer an dieser Stelle in unendlicher Reihe 123456789101112131415...

Einige Abnahmetestfälle

in der Notation "Input: Output". Alle von ihnen sollten bestehen.

  • 1: 1
  • 999: 9
  • 10000000: 7
  • 1e7: 7 (wie oben)
  • 13498573249827349823740000191: 6
  • 1.1e10001: 5
  • 1e23456: 5
  • 1,23456e123456: 4
  • 1e1000000: 0
  • 1.23e: Fehler (ungültige Syntax)
  • 0: Fehler (außerhalb der Grenzen)
  • 1.23e1: Fehler (keine ganze Zahl)

Bonus!

Geben Sie die Ziffernpositionsnummer innerhalb der Nummer und die Ausgangsnummer selbst aus. Beispielsweise:

  • 13498573249827349823740000191: 6 24 504062383738461516105596714
    • Das ist die Ziffer '6' an Position 24 der Nummer '50406238373846151610559 6 714'
  • 1e1000000: 0 61111 1000006111141666819445...933335777790000
    • Stelle '0' an Position 61111 der 999995-stelligen langen Nummer, die ich hier nicht einschließen werde.

Wenn Sie die Bonusaufgabe erfüllen, multiplizieren Sie die Größe Ihres Codes mit 0,75

Kredit

Diese Aufgabe wurde bei einem Treffen von devclub.eu im Jahr 2012 ohne große Anzahl von Anforderungen gestellt. Daher waren die meisten Antworten Trivialschleifen.

Habe Spaß!

metalim
quelle
Ich verstehe die Herausforderung wirklich nicht. Sollen wir die Eingabe übernehmen und die Nummer an dieser Position ausgeben?
The_Basset_Hound
1
Dies ist die OEIS-Sequenz 33307 .
Tyilo,
2
@vihan Die Verwendung einer öffentlichen Bignum-Bibliothek ist akzeptabel. Keine Strafe. Natürlich ist es in Betracht zu ziehen, die Lösung in die Bibliothek aufzunehmen und die Bibliothek als Einzeiler zu verwenden. Hier gilt der gesunde Menschenverstand.
Metalim
1
Ich wollte nur eine überraschend präzise F # -Lösung präsentieren , die mit 44 Bytes einrastet. Zugegeben, es kann nur Indizes bis zu 2 ^ 31-1 verarbeiten (und es wird immer noch versucht, diesen Wert zu berechnen, während ich dies schreibe). Ich poste das aber nicht, weil es in der Tat gegen die Regeln verstößt, aber ich würde sagen, es ist ziemlich gut für F #!
Jwosty
7
Die Anforderung, Eingaben wie 1.23456e123456willkürlich zu behandeln, bestraft Sprachen, die solche Werte nicht nativ verarbeiten können, und erfordert, dass sie eine String-Verarbeitung durchführen, die tangential zur Herausforderung ist.
Xnor

Antworten:

12

CJam , 78 Bytes

r_A,s-" e . .e"S/\a#[SSS"'./~'e/~i1$,-'e\]s"0]=~~_i:Q\Q=Qg&/
s,:L{;QAL(:L#9L*(*)9/-_1<}g(L)md_)p\AL#+_ps=

Das Programm ist 104 Bytes lang und qualifiziert sich für den Bonus.

Die Newline ist rein kosmetisch. Die erste Zeile analysiert die Eingabe, die zweite Zeile generiert die Ausgabe.

Probieren Sie es online!

Idee

Für jede positive ganze Zahl k gibt es 9 × 10 k-1 positive ganze Zahlen mit genau k Stellen (ohne führende Nullen). Wenn wir also alle verketten, erhalten wir eine ganze Zahl von 9 × n × 10 k-1 .

Wenn Sie nun alle ganzen Zahlen mit n oder weniger Ziffern verketten, erhalten Sie eine ganze Zahl von

Formel

Ziffern.

Für eine gegebene Eingabe q versuchen wir, das höchste n so zu bestimmen, dass der obige Ausdruck kleiner als q ist . Wir setzen n: = ⌈log 10 q⌉-1 , dann n: = ⌈log 10 q⌉-2 usw., bis der gewünschte Ausdruck kleiner als q wird , subtrahieren den resultierenden Ausdruck von q (ergibt r ) und speichern den letzten Wert von n in l .

r gibt nun den Index in der Verkettung aller positiven ganzen Zahlen von l + 1 an , was bedeutet, dass die gewünschte Ausgabe die r% (l + 1) -te Stelle der r / (l + 1) -ten ganzen Zahl von l + 1 ist Ziffern.

Code (Eingabe-Parsing)

r_          e# Read from STDIN and duplicate.
A,s-        e# Remove all digits.
" e . .e"S/ e# Push ["" "e" "." ".e"].
\a#         e# Compute the index of the non-digit part in this array.

[SSS"'./~'e/~i1$,-'e\]s"0]

            e# Each element corresponds to a form of input parsing:
            e#   0 (only digits): noop
            e#   1 (digits and one 'e'): noop
            e#   2 (digits and one '.'): noop
            e#   3 (digits, one '.' then one 'e'):
            e#     './~    Split at dots and dump the chunks on the stack.
            e#     'e/~    Split the and chunks at e's and dump.
            e#     i       Cast the last chunk (exponent) to integer.
            e#     1$      Copy the chunk between '.' and 'e' (fractional part).
            e#     ,-      Subtract its length from the exponent.
            e#     'e\     Place an 'e' between fractional part and exponent.
            e#     ]s      Collect everything in a string.
            e#   -1 (none of the above): push 0

~           e# For s string, this evaluates. For 0, it pushes -1.
~           e# For s string, this evaluates. For -1, it pushes 0.
            e# Causes a runtime exception for some sorts of invalid input.
_i:Q        e# Push a copy, cast to Long and save in Q.
\Q=         e# Check if Q is numerically equal to the original.
Qg          e# Compute the sign of Q.
&           e# Logical AND. Pushes 1 for valid input, 0 otherwise.
/           e# Divide by Q the resulting Boolean.
            e# Causes an arithmetic exception for invalid input.

Code (Ausgabegenerierung)

s,:L     e# Compute the number of digits of Q and save in L.
{        e# Do:
  ;      e#   Discard the integer on the stack.
  Q      e#   Push Q.
  AL(:L# e#   Push 10^(L=-1).
  9L*(   e#   Push 9L-1.
  *)     e#   Multiply and increment.
  9/     e#   Divide by 9.
  -      e#   Subtract from Q.
  _1<    e#   Check if the difference is non-positive.
}g       e# If so, repeat the loop.
(        e# Subtract 1 to account for 1-based indexing.
L)md     e# Push quotient and residue of the division by L+1.
_)p      e# Copy, increment (for 1-based indexing) and print.
\AL#+    e# Add 10^L to the quotient.
_p       e# Print a copy.
s        e# Convert to string.
2$=      e# Retrieve the character that corresponds to the residue.
Dennis
quelle
5

C Jam, 75 × 0,75 = 56,25

Dies ist ziemlich schnell, eine Iteration pro Ziffer der Zahl, die die gewünschte Position enthält. Ich bin sicher, es kann viel mehr golfen werden, es ist ziemlich grob, wie es ist.

q~_i_@<{0/}&:V9{VT>}{T:U;_X*T+:T;A*X):X;}w;U-(_X(:X/\X%10X(#@+s_2$\=S+@)S+@

Geben Sie die Position als Eingabe an, die Ausgabe ist:

<digit> <position> <full number>

Probieren Sie es online aus .

Andrea Biondo
quelle
@ Tennis Arbeiten mit allen Eingaben jetzt :)
Andrea Biondo
Dies löst immer noch keinen Fehler aus (wie es sollte) für 1.23e1. Es ist jedoch fehlerhaft, 1.23456e123456da die Eingabe nicht durch ein Double dargestellt werden kann. Auch die letzten Testfälle dauern 3 Minuten.
Dennis
2
@ Tennis Now wirft den Fehler auf. Was den großen Testfall betrifft ... Verdammt. Möglicherweise muss ich das Ganze neu schreiben.
Andrea Biondo