Auf der Suche nach Programmen in einem riesigen Boggle-Board

25

Jedes Zeichen in diesem 64 x 64-Textblock wurde zufällig und einheitlich aus den 95 druckbaren ASCII- Zeichen ausgewählt.

/rq$:Zy5*g'$DeGXX2o8y "{@Cg:FR9qih}xh >5$DsF1Fs5Ao~smFp;.RJbV )U
c4\(|Sx*V$10G9xO:NjHKasem%,\9[pPm@&kTaN~HC[;9`lgqlAH(7dt0a-5}LJ[
&sifw9V-.PLRoD~F'dJYA^Q)L#h>$9h!B4b&ceKp8~HndzDm#1/ySydrf5T8[Y%4
U9>HLQ74Qf[^V9tpWrKFcFxZJ::4?z/o]3u,V[B&hB9lFYA0:rW#yql5z9.d*D}U
:M2*O9'7_HMGw_=%@hR>O+(@Dr6MIt(=/{-{4lia0Vmws32wr(fnTmT%HSo&7!uz
\KZWG&KnXh+6E+Q>%pV(<Bnm-d+p~y~]Ta"aw9)]0A_AHz\tP3&}1R^/yPPSgN?8
".7|Uj)S7-k[`yeLO~P2a?z3wiS(R-\k'?z(pVm;;D^k/q84?&7:,E*9$UQ"UbBJ
ME]&*R ,*7PDF4Tw*-;De{YeP_al.CJcJX`@V_y+>^<h{L[^Y"!RxjN^lyA_/Y=(
#C>Zo#Sl;UUD5ChIj'L@rkELk%S*]a$87j\\n;}796m/\NPL>8d-T-hR!7ftw ?A
tV5"E309bAv$jhE6\'8f?VGlBb?z#V;F((3'|}$tfpiNB>"*mxc,X1s:/%x*JQAL
rxYXUJsd?X}^yc|'16539vd=psU'>|y/!$-TRamKcJk^2-aD35h7CcaRNue"8#{;
@yUq?*(72I8@I)So+]RwtKy:mLhjG/f#:U<TXml<PtX*+,ngfZt75-q*gSsyI2tS
|*M*;yz6u2(LZ>W`bth-7G~>|dh'pm}]@"#Oq9%o\W)b,gh%b1O]4F:EGb7ERI=@
ehMo69slKw=S@<j*Q4sfd\1')#)V&yaPF%%ZG6VK\_-$Cab,nrlW"O(<tu&xU=I&
|[g4k2L;FD)=yX0SsE-|vI(mDOccuU(+m\wxgrJxi8ZP[uD)L.!K@]%@q`!pk8Yx
?PZaS3;x,7nK~IHlrCGy~xq:@K/CJ1J^oeac&Tv?6[H>>0lu?(/bh@6J^@S?IY-|
@tdN$K=Ci2;_0Du;L2OO'en|]<_`nX5p3Bes9`8{}fRCV$X&aoQGYS'$j%r<2709
UwETsAo^d!aUZ0vN5,Yq\n%JAIm}%O88FAJK^Jt&=jM\Q1^+^|X8\._"l%hlF+yH
+c^FBFxTGz|f|#kElQs)mS64-3Z\An]|[rQo"OQ+ IP"ARdJ}/OYFQF_/{B 73mU
UPvxNByN[2TT,XgRZ_LwolUVWuR)DjYI7j#mmA8m?&Y}}[_h8@Y-R*,#=1\D*&@*
ePW.w{@z3moe3Vztd,>?*~ZQUvn8$+xw$$f92D*kPZ":;lcTr3m&{*?j$FgZK|cU
IAd'0C{<4b}NuhX1B#gmk'oF4+(@fzP^T?hF/#]g^y rb5][)X-d4Q't~1]HE"tZ
p2Z,%H0$EWF/%|UQm?&]E~=v;9YwxrSs%}df`[ `SfXMJWt86UY1duGAAKkFSrH!
oUyB[soS!N%XYwX]%n K^}CcTE?~.,8`C&l)Jjjp5|z))!o/ "G)sj,{OETsi:KE
4E,':a=,T~YlxdF^<\$fE|f:_-RG}7=m%g\-9a*X]`n<P$D+q7O`+$P&!\"NUs7n
hL@0s 7i^Xp\._4$lZIB9Ql AXX_00K=<hp%55KSO6yWH~cGe%|(p_WzlhPUbH{?
o5b4pi(,]&&jB\hGa:\DQbrYc,n|,b)_E{n~i~+JSxn?%/qJVm|B 8"Jf||L.|M-
 KRxH;T^Z7%ZufyO=nI;[v1\8ZTg\_)ect4DvMTvqtoo(;b~J&'~E2TTD!w1BvGv
Q+1sv>q%1$BaCm%(\%uGH*]emoFwejkhb$gKm=DVG#&:p'";s)&MY30q_cG=.CKJ
q,aWTi|^w2wg3<G_y<n+^Xq2ymHFs#7z[x0l'Lz6N>Mpo?=hAd&58HVMhsh(kQH5
&kSivkn`,KON9xb:$M[L15!D6W?\ASWc#}V#2U;qxKhtil73,!iuG~(lr[tPJQ6w
IZ)0Vp{kEUID:vgwmTMQ#Y]NdX6{'/3bI2x9k 4[>j)&Q0U,t,iA#A%4929o6+n_
SQe/!KubbuXthMe&2\%:'Z`,aaA)V&(v+]0^v-_@*Qg!^K!pCo"@e/|3}.3q^R||
6hF>/jd>(=il~2$KY.^x~K_H)J8Fi)'LOcUr4xJir^v0,c fIsoT<|7K}Bls|36z
MQ|-w=bp)_EY>YtGcW)!@/|Lc:I_<]x.~[|QSgJY1ZX9^e`ojAR6U#zt9!,44}>#
EJzH \gwosC>Z*)H!]1BPaIEYGyk{c0zv{d\#px2@#'-T{{.Qxknxv}"x3#K]w>;
<X(\bNnY_6*7Yu7_3a+wInwt vh=1eBgz>7Bnhs!<t.T#&V{+?p+{.RTN:xz>|,E
$upN*[F4A`~ZDMDt{.&2z+LZ7bcfeJfF9Uy3xX]ZzQ1FvB.U4S!hm$LYCp: wF7h
 47-+lY$"}AExXQ@?!/6}biptH=6N-6&8-T\C8{`i56e'%cimv,0QKYTx) "nkFJ
C:Enw=Q%6J;t6wS+2O,b0v'"OK6GMbr);y#-H86>pCE6wjdk*rR*=reWo57^2TFH
::Nq,t9_S">\o^NZzh|U\^qyh-yt0nvMs%'6\;$%(91gTC=&1q]q-*u*so KrXsE
-Sz>q]l86[OO@\5W<'\XDc,%/=0sV0&1'Etty%f ~,c45IIqy=no.DY{8\?fa<9{
6%3TP:i^q.JzU217CADu}iAzWT""E\{IEMbGDKZB6s*LmlM0|<WA8CP7sR}f?WSL
S`T} 7Tn9!h8P\W 8J\#Mg\o;Qwt&4\UYKf{)O3G&B]sK.bw1!?7=:h$IIOIakD<
H/O5v`ld*35MSsydSQoiAnJ*\!^?'_=6E?c> PtM!rw5y{ZT2xSco){3_?j|wtJp
CT1!e~k8aNgw)LE:}oX4R*<u]TB%\IN8YoMK'bV%L2H{L3'c/|xoTY^&&WPKSyo<
cXma$Rfjj^':^a\?$UOo48]791Wywj7aH1\iP|\l=sjjbjqZB2)-apvjV@q47Spw
OP[kT<l@cKB="n;VC#6a*InmS~$TN{= j)r>S] uH9:E-}y>.Ygc'll$5Y$j]AYt
jB="iGo7[qY~A*nv.\51[<]):^[iZs4s-D_bC'OfM%lHlz;MoxY$Ku]NCt72PYMB
_(myN5'%] C!7FPoGX7+*,Yptuaz;Q6W,;R|U1XEhgq21R7<ncnDB<D_);j.:r0r
Q6!k|Dq`!Jz7l="*n?w@f|h=PA_A)n._ii:s~'n~XsD}?JRIkC9AW^piUfBTU,ui
nf+yZ`7P-(@{>s:{Vz'N 7qB&+UZbm4'0]D~HZNJq.w</3 \cL)WRDP(y]w~L4N/
!!lA+NK[+9#-iwx`PE53D.K2]]#M.Rm$^Cc'|!@cX6{yCg8K0|>E_jyup|+'=#c%
Ao5$B);DoQ#jg[7GbdE+o:R,T#@`;UnX}.?2z\RJ98Se*_.*e8mCUF}Vw1u13cy1
2s}1@?{0);Jo6(J@l>[M 0CkeO6{ExN7,%Kv1#[!** czaX)=;Q~D;z',fkq!1W<
% f(i#i`PQY!m7v#D:j5pyU]8:at2,k("BWZRI<WR??GQ$^1d[m,F(<e5CLv-m*B
CD)zVpa95WpJ K@&}yN\Q8I<%z/*_/bPsR5=0\Z=#mWZDAfA5[k|$Yks@Q;@h,s/
Np.$gTvz>T+"0|$Nw::%m$GFYxG{2akv$Eh8\4|eW'oJEffNzJ>UxU4>oITZMe/'
EMg$>kD|\ ^.W)Stzv/7z\^bdi]E@] U&-r8(B^?}$P56[?e~jE#_j)5=#~.yNP$
'mgF3EAhXB 55)\WXp*e+fD#^&SHGx++7VO[R7*b(Q+:jESt'K%m~d$Bv^/{7=zr
5oCZDp& ;*Y*G`L$C]Nm`|^:y2NKaO!)u/{hwm(VjS`<qKgNw7[+~0 <be'sWjTo
[email protected]*ml)pLeEVJ~8A$mgz*d>ajbg1FIYrg6J`D0xJMXi`ghA1V$ju
*rJg/ o;6M7`(qTF.nO'4da,{ieM&NC9rg;nX*))*DK"DycYD66&6z/I@}y4@$<f
3S]~9g An{=Rj|y&A2Vh^F\3lb#N~8w0EMx<K$]z(eZS~zbmgeeV\i7,MY~zrc+;

Ihre Aufgabe bei dieser Herausforderung ist es nicht, Ihren eigenen Code zu schreiben, sondern Code aus diesem Textblock zu extrahieren, als wäre es ein riesiges Boggle- Gitter, und Sie suchen nach einem ausführbaren Programm anstelle eines Wortes.

Die Einreichung mit dem Programm, das die längste endliche Ausgabe erzeugt, gewinnt.

Einzelheiten

Behandeln Sie das 64 x 64-Raster genau wie ein 64 x 64-Raster mit zusätzlichen Zeichen. Erstellen Sie eine Zeichenfolge, die in einer bestimmten Sprache als ausführbares Programm ausgeführt werden kann, indem Sie eine Startposition im Raster auswählen und so oft Sie möchten einen Schritt vertikal, horizontal oder diagonal (insgesamt 8 Richtungen) verschieben. Sie dürfen den gleichen Rasterplatz NICHT mehrmals benutzen!

Diese 4 Zeilen wurden beispielsweise aus der Mitte des Textblocks entnommen:

EJzH \gwosC>Z*)H!]1BPaIEYGyk{c0zv{d\#px2@#'-T{{.Qxknxv}"x3#K]w>;
<X(\bNnY_6*7Yu7_3a+wInwt vh=1eBgz>7Bnhs!<t.T#&V{+?p+{.RTN:xz>|,E
$upN*[F4A`~ZDMDt{.&2z+LZ7bcfeJfF9Uy3xX]ZzQ1FvB.U4S!hm$LYCp: wF7h
 47-+lY$"}AExXQ@?!/6}biptH=6N-6&8-T\C8{`i56e'%cimv,0QKYTx) "nkFJ

Beginnend mit dem pungefähr rechten Ende der dritten Zeile kann ich mich bewegen, indem ich diagonal nach unten und rechts "gehe, dann nach rechts gehe, dann dreimal nach oben  zKund viermal nach links #3x". Dadurch wird die Zeichenfolge nachverfolgt, p " zK#3x"die bei Ausführung als Ruby- Programm ausgegeben wird " zK#3x".

Ziel ist es, ein Programm zu finden, das die längste endliche Ausgabe liefert . Beim Zählen der Länge der Ausgabe werden nur druckbare ASCII-Zeichen berücksichtigt (dies bedeutet, dass Tabulatoren und Zeilenumbrüche nicht gezählt werden), obwohl möglicherweise andere Zeichen vorhanden sind. Das Ruby-Beispiel erzeugt nur 8 Zeichen.

Ebenfalls...

  • Das Programm kann 1 bis 4096 Zeichen lang sein.
  • Das Programm enthält möglicherweise keine Tabulatoren, Zeilenumbrüche oder nicht druckbaren ASCII-Zeichen (da sie nicht im Raster enthalten sind).
  • Das Programm sollte ohne Fehler ausgeführt und beendet werden.
  • Es gibt keine Zeit- oder Komplexitätsbeschränkungen, solange das Programm irgendwann mit einer endlichen Ausgabe enden würde .
  • Das Raster verläuft nicht von links nach rechts oder von oben nach unten.

Bitte geben Sie an, wo Ihr Programm im Raster angezeigt wird, damit wir schnell überprüfen können, ob es wirklich vorhanden ist.

Calvins Hobbys
quelle
8
Warum ruhen die 4096 Zeichen ... oh.
John Dvorak
2
Vielleicht wäre es interessanter gewesen, wenn das Programm ein aktuelles Code-Golf-Problem lösen müsste, aber aus dem Raster genommen werden müsste.
Feersum
2
@DavidCarraher - Oder eigentlich für jede andere Sprache als Golf. Ich habe yeszum Beispiel eine Instanz von gefunden .
1
TECO ist keine Golfsprache ... es ist ein Band- / Texteditor aus den 1960er Jahren.
Feersum
1
Sieht auf den ersten Blick wie ein perfekt funktionierendes Perl-Programm aus ...
DGM

Antworten:

15

CJam, über (81182737 ^ 2813292) ↑↑ (10604499373-1) Zeichen

Okay, ich glaube, ich habe endlich alles geklärt. Das hat Spaß gemacht - es war, als würde man durch ein Minenfeld navigieren.


Bevor wir eintauchen, lassen Sie uns mit einem einfacheren Beispiel beginnen ( versuchen Sie es online ):

1 3{(\1\{(\5*\}h;\}h;

hist eine do-while-Schleife, die die Bedingung auf dem Stapel belässt und {}Codeblöcke sind. Der innere Block ist:

(        Decrement
\        Swap top two of stack
5*       Push 5 and multiply
\        Swap back

Angenommen, der oberste Teil des Stapels ist [1 10]und wir führen das Do-while durch {(\5*\}h;. Das ist, was passiert:

[1 10] --decrement--> [1 9]    --swap--> [9 1]    --multiply--> [9 5^1]  --swap--> [5^1 9]
       --decrement--> [5^1 8]  --swap--> [8 5^1]  --multiply--> [8 5^2]  --swap--> [5^2 8]
       --decrement--> [5^2 7]  --swap--> [7 5^2]  --multiply--> [7 5^3]  --swap--> [5^3 7]
       ...

Dies geschieht, bis die 10 bis auf 0 dekrementiert und die Schleife endet. An diesem Punkt landen wir [5^10 0]oben auf dem Stapel. Wir können dann verwenden, ;um die Null zu platzen und zu verlassen [5^10].

Mit anderen Worten haben wir nur Potenzierung durchgeführt, mit [1 x]{(\5*\}h;was [5^x].

Der äußere Block {(\1\{(\5*\}h;\}h;ist ähnlich, aber anstelle 5*der mittleren haben wir unsere "Exponentiate Base 5" -Schleife. Für unser einfaches Beispiel erhalten [1 3]wir beginnend mit :

[1 3] -dec/swap-> [2 1]   -push 1-> [2 1 1]   -swap-> [2 1 1]   -5^-> [2 5]     -swap-> [5 2]
      -dec/swap-> [1 5]   -push 1-> [1 5 1]   -swap-> [1 1 5]   -5^-> [1 5^5]   -swap-> [5^5 1]
      -dec/swap-> [0 5^5] -push 1-> [0 5^5 1] -swap-> [0 1 5^5] -5^-> [0 5^5^5] -swap-> [5^5^5 0]

Die Oberseite ist Null, also stoppen wir die Schleife und knallen und gehen [5^5^5]. Mit anderen Worten, wir haben gerade 5^5^5oder 5↑↑3in Knuths Pfeil-nach-oben-Notation erstellt . Sie können für andere Zahlen zwischen 5 und 3 wechseln, aber die Überkompensation wird schnell groß , sodass ich nicht empfehlen würde, etwas zu groß auszuwählen.


Nun zur Sache:

1B);0D+9#{z(J Y=A*;\VC#UooJ87<W5^o\OO>;J6%_9=+NpXzH|>!p{Kdp(_E=XIK21^%^Z&&p\Y~!E<432|T|Z#00I0*boW)I^8227(*JEo*#09;*7XH+G^o9=pWdK>(2P-*I\6539K~>)#D@</CJ1(+^po\F"U$(jX?a"apV\|;}_V);;D00&phVA^^6pJP\<%o\8H>V1^+aoXY-Y&41-X)8/o!Jb;}"}:rM)<W?o:p'";h

(Pfadverfolgung)

Anotiert (alles ohne Noten ist Füller):

1                                           Push 1
B);
0D+9#                                       Push 13^9 = 10604499373
{                                           Start outer block
z
(                                           Decrement
J Y=A*;
\                                           Swap
VC#Uoo
J87<                                        Push 1
W5^o
\                                           Swap back
OO>;
J6%_9=+NpXzH|>!p
{                                           Start inner block
Kdp
(                                           Decrement
_E=XIK21^%^Z&&p
\                                           Swap
Y~!E<432|T|Z#00I0*boW)I^8227(*JEo*#         Push 81182737^2813292, <output 3 chars>
09;
*                                           Multiply by previous large number
7XH+G^o9=pWdK>(2P-*I\6539K~>)#D@</CJ1(+^po
\                                           Swap back
F"U$(jX?a"apV\|;
}                                           End inner block
_V);;
D00&p
h                                           Perform inner do-while loop
VA^^6pJP\<%o                                Pop top of stack by outputting
\                                           Swap back
8H>V1^+aoXY-Y&41-X)8/o!Jb;
}                                           End outer block
"}:rM)<W?o:p'";
h                                           Perform outer do-while loop

Es ist im Grunde dasselbe wie im einfachen Beispiel, nur mit viel Füllmaterial, während Sie von einer Anweisung zur nächsten im Raster navigieren.

Statt 5 und 3 haben wir 81182737^2813292und 10604499373, was bedeutet, dass es (81182737^2813292)↑↑10604499373am Ende ausgegeben wird (natürlich mit genügend Zeit und Speicher!). Beachten Sie, dass dies nur eine Untergrenze ist - es findet eine Menge anderer Druckvorgänge statt, z. B. bei 6 und 3 ist die Ausgabe über 2 Millionen Zeichen lang, obwohl 6^6^6sie nur 36.000 Stellen hat.

Wenn Sie diese Vollversion selbst ausprobieren möchten, testen Sie mit:

1B);
3
{z(J Y=A*;\VC#UooJ87<W5^o\OO>;J6%_9=+NpXzH|>!p{Kdp(_E=XIK21^%^Z&&p\
5
09;*7XH+G^o9=pWdK>(2P-*I\6539K~>)#D@</CJ1(+^po\F"U$(jX?a"apV\|;}_V);;D00&phVA^^6pJP\<%o\8H>V1^+aoXY-Y&41-X)8/o!Jb;}"}:rM)<W?o:p'";h

Ersetzen Sie die 5 und 3 in der zweiten und vierten Zeile durch Zahlen Ihrer Wahl. Beachten Sie, dass die Ausgabe einige zusätzliche Stellen um die wichtige überkompensierte Zahl enthält (nämlich eine vorangestellte 010und eine nachgestellte 0).


Ein paar Anmerkungen zu CJam

Vielleicht fragen wir uns: Warum nicht CJams eingebaute Potenzierung ( #) anstelle der inneren Do-While-Schleife verwenden? Leider habe ich nach dem Durchsuchen von CJams Quelle erfahren, dass die Basis für die Exponentiation ein BigInt (willkürliche Genauigkeit) sein kann, aber der Exponent wird in ein normales 32-Bit-Int konvertiert . Dies hat einige amüsante, aber ärgerliche Nebenwirkungen:

2 2 31# #     -->    java.lang.ArithmeticException: Negative exponent  (should be 2^2^31)
2 2 32# #     -->    1                                                 (should be 2^2^32)

Dies bedeutete, dass ich CJams eingebaute Exponentierung aus Überlaufgründen nicht verwenden konnte, wenn der Exponent zu groß ist. Die Multiplikation ist jedoch anders, da die Multiplikation von zwei BigInts zu einem neuen BigInt führt. Deshalb habe ich mich entschlossen, dies stattdessen auszunutzen.

Sp3000
quelle
4
Minutenregel entfernt. Verrückt werden!
Calvins Hobbys
7

TECO, ~ 2 ^ 31 * 13 ~ = 27,9 * 10 ^ 9

?^e=<\RZK%B"svbk7,.c2z\R!Z~|bS|VM!2=9%MEX'1UC>

Bildbeschreibung hier eingeben

Bearbeiten: Einige Zeichen wurden geändert, weil ich versehentlich eines wiederverwendet habe, aber dieser Teil befand sich in einem Kommentar, sodass es keinen großen Unterschied macht.

Das ?Befehlsecho wird aktiviert, mit dem ich den größten Teil der Ausgabe erstelle. Dann werden die Zeichen \RZK%B"s'1UC>in einer Schleife gedruckt. %B"saddiert eins zu B und prüft dann, ob es kleiner als null ist. Daher sollte diese Bedingung nach 2 ^ 31 Zyklen eingegeben werden, wenn sie auf eine negative Zahl überläuft. Innerhalb der Bedingung gibt es einen EXBefehl, der das Programm beendet.

Derzeit versuche ich, es vollständig mit der Ausgabe auszuführen, die an eine Datei gerichtet ist.

Feersum
quelle
"Derzeit versuche ich, es vollständig mit der Ausgabe auszuführen, die an eine Datei gerichtet ist." Ich hoffe, Sie haben 27,9 GB (26 GiB) freien Speicherplatz, dann ...
John Dvorak
1
@JanDvorak Ich habe über 600 GB freien Speicherplatz ... aber es geht so langsam voran, dass es irgendwie unwahrscheinlich ist, dass es den ganzen Weg geht.
Feersum
-4

HQ9 + (17195 Zeichen)

Quelle:

9Q9

(beginnt um 5: 4 und dann runter)

Ausgabe:

Der Text zum Lied "99 Flaschen Bier" (8596 Zeichen), die Zeichenfolge 9Q9(3 Zeichen) und eine weitere Kopie von "99 Flaschen Bier" (8596 Zeichen).

Dies ist eine sehr lahme Antwort, und Sie sollten sie nicht unterstützen, aber jemand musste sie posten.

Philipp
quelle