Große, große Zahlen

25

Bei dem Versuch, mehrere meiner Antworten auf den Prüfstand zu stellen, musste ich große Ganzzahlen mit möglichst wenigen Zeichen schreiben.

Jetzt weiß ich den besten Weg, das zu tun: Ich werde Sie dazu bringen, dieses Programm zu schreiben.

Die Herausforderung

  • Schreiben Sie ein Programm, das bei Angabe einer positiven Ganzzahl ein Programm ausgibt, das es als stdout oder gleichwertig ausgibt.
  • Die Ausgabeprogramme müssen nicht in der Sprache des Erstellers sein.
  • Die Ausgabe darf maximal 128 Byte betragen.
  • Sie können Eingaben von stdin oder einer gleichwertigen Quelle akzeptieren (keine Funktionseingabe).
  • Sie können das resultierende Programm als stdout oder gleichwertig ausgeben.
  • Die Zahlenausgabe muss dezimal sein (Basis 10)

Wertung

Ihre Punktzahl entspricht der kleinsten positiven Ganzzahl, die Ihr Programm nicht codieren kann.

Der Eintrag mit der höchsten Punktzahl gewinnt.

Blau
quelle
Ich habe das Tag Metagolf hinzugefügt, da wir das Ausgabeprogramm golfen.
Orlp
1
@orlp Ich habe es absichtlich weggelassen, weil Metagolf ein Bewertungskriterium ist, das besagt, dass "die Punktzahl die Länge Ihrer Ausgabe ist". Ich denke darüber nach, einen Meta-Post hinzuzufügen, um auch ein inverses Scoring zu ermöglichen (was zum Beispiel für den schnellsten Code der Fall ist).
Martin Ender
1
@ MartinBüttner Ich denke, wir brauchen Meta-Restricted-Source :)
Orlp
2
Inwiefern unterscheidet sich die Herausforderung von "Welche Sprache hat den größten ganzzahligen Bereich" ?
NWP
5
@nwp Ich denke du verstehst die Frage falsch. Die Frage ist über die Komprimierung. Es wäre nützlich, aber nicht notwendig, eine Sprache mit einem großen ganzzahligen Bereich zu verwenden.
Kartoffel

Antworten:

2

Python 3 → CJam, (163 122 - 1) · 255/162 + 1 · 1,213 · 10 270

import sys
n = int(input())
for b in range(163, 1, -1):
    s = []
    m = n
    while m:
        m, r = divmod(m - 93, b)
        if m < 0:
            break
        s.append(r + 93)
    else:
        sys.stdout.buffer.write(b'"%s"%db' % (bytes(s[::-1]), b))
        break
else:
    sys.stdout.buffer.write(b'%d' % n)

Es stellt sich heraus, dass jede ganze Zahl von 1023 bis (163 122 - 1) · 255/162 in mindestens einer Weise durch eine Konvertierung der Basis b ≤ 163 aus einer Zeichenfolge von höchstens 122 Zeichen mit den Codes 93 bis b + 92 dargestellt werden kann. anstatt die üblichen 0 bis b - 1. Dies vermeidet die lästige Zeichen 34 (doppelten Anführungszeichen) und 92 (Backslash) ohne zusätzlichen Ausgabecode.

Anders Kaseorg
quelle
12

Pyth, 252 111 ≤ 3,593 × 10 266

Js[
"ixL-rC1`H``N"
N
s@L-rC1`H``NjQ252
N
"252")$import sys$$sys.stdout.buffer.write(J.encode('iso-8859-1'))$

Musste ein bisschen Python-Syntax verwenden, da Pyths printnicht drucken können iso-8859-1.

Die Zahl wird in Basis 252 codiert und repräsentiert jede Ziffer in dieser Basis als ISO-8859-1-Zeichen. Die Zeichen \und "müssten entkommen und werden daher nicht verwendet. Das Zeichen `wird nicht benutzt, weil Golf gespielt wird ... Und zusätzlich wird das Null-Byte auch nicht benutzt, der Pyth-Compiler verbietet es.

Die Ausgabe ist ein Programm mit einem Overhead von 17 Bytes:

ixL-rC1`H``N""252

Hier ist ein Anwendungsbeispiel mit der größtmöglichen Anzahl:

Verwendung

Erläuterung

des Ausgabeprogramms.

ixL-rC1`H``N""252
    rC1`H          create the range of chars: ['\x01', '\x02', ..., '{}']
         ``N       creates a string containing the 3 chars " ' \
   -               remove strings which consists of these 3 chars
 xL         ""     determine the index of each char in "" (encoded number)
i             252  convert from base 253 to base 10
Jakube
quelle
1
Dieses Programm kann nicht codieren 12, da Pyth CR leider als LF liest .
Anders Kaseorg
10

CJam, 254 109 ≈ 1,34 x 10 262

q~254b{_33>+_91>+c}%`"{_'[>-_'!>-}%254b"

Ich codiere die Zahl in Basis 254 und stelle jede Ziffer in dieser Basis als ISO 8859-1-Zeichen dar, überspringe "und \. Die Ausgabe hat einen Overhead von 19 Bytes, ""{_'[>-_'!>-}%254bsodass ich alles weniger als 254 128-19 oder explizit darstellen kann

13392914970384089616967895168962602841770234460440231501234736723328784159136966979592516521814270581662903357791625539571324435618053333498444654631269141250284088221909534717492397543057152353603090337012149759082408143603558512232742912453092885969482645766144

Als Beispiel 6153501wäre codiert als

"abc"{_'[>-_'!>-}%254b

Hier ist ein Testprogramm, das die codierte Ganzzahl ausgibt, ihre Länge ausgibt und sie dann sofort ausführt, um ihre Gültigkeit zu überprüfen (dies vermeidet die Mühe, die nicht druckbaren Zeichen in ein neues Programm zu kopieren, was nicht immer funktioniert mit dem Online-Dolmetscher).

Martin Ender
quelle
8

Perl, 10-216

print"print unpack'h*',q{",(pack'h*',<>),"}"

Auch Base-100-Codierung, etwas eleganter. Ausgabe für 12345678wäre:

print unpack'h*',q{!Ce‡}

Die Trennzeichen {und }entsprechen den Hex - Werte b7und d7jeweils, die nicht in der Eingabe erscheinen können, und müssen daher nicht entgangen sein.

Der Overhead beträgt 20 Byte, sodass 108 Byte für die Codierung verbleiben und ein Maximalwert von 10 216 -1 erreicht wird.


Perl, 10, 206

print"ord=~print\$' for'",(map chr"1$_",<>=~/.{1,2}/g),"'=~/.|/g"

Einfache Base-100-Codierung. Die Ausgabe für 12345678würde folgendermaßen aussehen:

ord=~print$' for'p†œ²'=~/.|/g

Der Overhead beträgt 25 Byte, so dass 103 Byte für die Codierung verbleiben und ein Maximalwert von 10 206 -1 erreicht wird.

primo
quelle
6

Common Lisp, 36 114 - 1 ~ 2,62 × 10 117

(lambda(x)(format t"(lambda()#36r~36r)"x))

Die größte Zahl ist:

2621109035105672045109358354048170185329363187071886946329003212335230440027818091139599929524823562064749950789402494298276879873503833622348138409040138018421944

Verwenden Sie einfach die Basis 36. Für die größte Eingabe ist die 128 Byte lange Ausgabe:

(lambda()#36rzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz)
Core-Dump
quelle
1

CJam, 233 114 7,561 10 269

ri233b{Kms/m]_34=+c}%s`"{iKms*}%233b"

Das Ausgabeprogramm "…"{iKms*}%233bdecodiert die 8-Bit-Zeichen eines Strings auf Basis von 233 Ziffern mit n ↦ ⌊ n ⋅ sin 20⌊ = ⌊ n ⌋ 0,913⌋. Diese Transformation ist zufällig surjektiv, ohne dass die kritischen Codepunkte 34 (doppeltes Anführungszeichen) und 92 (umgekehrter Schrägstrich) als Eingabe erforderlich sind.

Anders Kaseorg
quelle