Recherche de programmes dans un immense tableau Boggle

25

Chaque caractère de ce bloc de texte 64 x 64 a été choisi de manière aléatoire et uniforme parmi les 95 caractères ASCII imprimables .

/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+;

Votre tâche dans ce défi n'est pas d'écrire votre propre code, mais plutôt d'extraire le code de ce bloc de texte comme s'il s'agissait d'une énorme grille Boggle et que vous recherchez un programme exécutable au lieu d'un mot.

La soumission avec le programme qui produit la sortie finie la plus longue l'emporte.

Détails

Traitez la grille de texte 64 x 64 exactement comme une grille Boggle 64 x 64 avec des caractères supplémentaires. Construisez une chaîne qui est un programme exécutable dans une langue en choisissant un emplacement de départ dans la grille et en déplaçant à plusieurs reprises une étape verticalement, horizontalement ou en diagonale (8 directions au total) autant de fois que vous le souhaitez. Vous ne pouvez PAS utiliser le même espace de grille plus d'une fois!

Par exemple, ces 4 lignes ont été prises à partir du milieu du bloc de texte:

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

En commençant par l' pextrémité droite de la troisième ligne, je peux passer à la diagonale en descendant et à droite, puis "en allant à droite, puis en remontant 3 fois  zKet à gauche 4 fois #3x". Cela trace la chaîne p " zK#3x"qui, lorsqu'elle est exécutée en tant que programme Ruby , sort " zK#3x".

Le but est de trouver un programme qui produit la sortie finie la plus longue . Seuls les caractères ASCII imprimables sont pris en compte lors du comptage de la longueur de la sortie (cela signifie que les tabulations et les sauts de ligne ne sont pas comptés), bien que d'autres caractères puissent être présents. L'exemple Ruby ne produit que 8 caractères.

Également...

  • Le programme peut comporter de 1 à 4096 caractères.
  • Le programme peut ne pas contenir d'onglets, de nouvelles lignes ou d'ASCII non imprimables (car ils ne sont pas dans la grille).
  • Le programme doit s'exécuter et se terminer sans erreur.
  • Il n'y a pas de contraintes de temps ou de complexité tant que le programme se terminera finalement avec une sortie finie.
  • La grille ne boucle pas de gauche à droite ou de haut en bas.

Veuillez indiquer où votre programme apparaît dans la grille afin que nous puissions rapidement vérifier qu'il est vraiment là.

code-challenge boggle Loisirs de Calvin
la source
8
Pourquoi le caractère 4096 reste ... oh.
John Dvorak
2
Cela aurait peut-être été plus intéressant si le programme devait résoudre un problème de golf de code réel, mais être extrait de la grille.
feersum
2
@DavidCarraher - Ou pour toute langue non golfique en fait. J'ai trouvé une instance de yes, par exemple.
1
TECO n'est pas une langue de golf ... c'est un éditeur de bande / texte datant des années 1960.
feersum
1
On dirait un programme Perl parfaitement viable à première vue ...
DGM

Réponses:

15

CJam, sur (81182737 ^ 2813292) ↑↑ (10604499373-1) car

D'accord, je pense que j'ai finalement tout réglé. C'était amusant - trouver le code était comme naviguer dans un champ de mines.

Avant de plonger, commençons par un exemple plus simple ( essayez-le en ligne ):

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

hest une boucle do-while qui laisse la condition sur la pile, et {}sont des blocs de code. Le bloc intérieur est:

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

Supposons que le haut de la pile soit [1 10]et nous effectuons le do-while {(\5*\}h;. Voici ce qui se passe:

[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]
       ...

Cela se produit jusqu'à ce que le 10 décrémente jusqu'à 0 et que la boucle se termine, point auquel nous nous retrouvons en [5^10 0]haut de la pile. On peut alors utiliser ;pour faire éclater le zéro, en partant [5^10].

En d'autres termes, nous venons d'effectuer une exponentiation, avec pour [1 x]{(\5*\}h;résultat [5^x].

Le bloc extérieur {(\1\{(\5*\}h;\}h;est similaire, mais au lieu de celui 5*du milieu, nous avons notre boucle "exponentiate base 5". Donc, pour notre exemple simple, en commençant par [1 3]nous obtenons:

[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]

Le sommet est nul, donc nous arrêtons la boucle et sautons, en partant [5^5^5]. En d'autres termes, nous venons de créer 5^5^5, ou 5↑↑3dans la notation de flèche vers le haut de Knuth . Vous pouvez basculer entre 5 et 3 pour d'autres nombres, mais l'hyperexponentiation devient très rapide , donc je ne recommanderais pas de choisir quelque chose de trop grand.

Maintenant pour la vraie chose:

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

(Trace de chemin)

Anoté (tout ce qui est sans notes est une charge):

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

C'est fondamentalement le même que l'exemple simple, juste avec beaucoup de remplissage lors de la navigation d'une instruction à l'autre dans la grille.

Au lieu de 5 et 3, nous avons 81182737^2813292et 10604499373, ce qui signifie que cela (81182737^2813292)↑↑10604499373est sorti à la fin (avec suffisamment de temps et de mémoire, bien sûr!). Notez qu'il s'agit simplement d'une limite inférieure - il y a beaucoup d'autres impressions qui ont lieu, par exemple avec 6 et 3, la sortie dépasse 2 millions de caractères même si elle 6^6^6n'a que 36k chiffres.

Si vous voulez essayer cette version complète par vous-même, testez avec:

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

en remplaçant les 5 et 3 des deuxième et quatrième lignes par des chiffres de votre choix. Notez que la sortie aura quelques chiffres supplémentaires autour de l'important nombre hyperexponentiated (à savoir un précédent 010et un suivant 0).

Quelques notes sur CJam

Vous vous demandez peut-être: pourquoi ne pas utiliser l'exponentiation ( #) intégrée de CJam au lieu de la boucle do-while intérieure? Malheureusement, après avoir fouillé la source de CJam, j'ai appris que pour l'exponentiation, la base peut être un BigInt (précision arbitraire) mais l'exposant est converti en un int normal de 32 bits . Cela a des effets secondaires amusants mais ennuyeux:

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

Cela signifiait que je ne pouvais pas utiliser l'exponentation intégrée de CJam lorsque l'exposant était trop grand, pour des raisons de débordement. Cependant, la multiplication est différente car multiplier deux BigInts donne un nouveau BigInt, j'ai donc décidé d'exploiter cela à la place.

Sp3000
la source
4
La règle des minutes a été supprimée. Devenir fou!
Calvin's Hobbies
7

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

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

entrez la description de l'image ici

Edit: J'ai changé quelques personnages parce que j'en ai réutilisé un accidentellement, mais cette partie était dans un commentaire donc ça ne fait pas beaucoup de différence.

L' ?activation de l'écho de la commande, que j'utilise pour créer la plupart de la sortie. Ensuite, les caractères \RZK%B"s'1UC>sont imprimés en boucle. %B"sajoute un à B, puis teste s'il est inférieur à zéro. Ainsi, ce conditionnel doit être entré après 2 ^ 31 cycles lorsqu'il déborde sur un nombre négatif. A l'intérieur du conditionnel, il y a une EXcommande qui quitte le programme.

Actuellement, j'essaie de l'exécuter jusqu'à la fin avec la sortie dirigée vers un fichier.

feersum
la source
"Actuellement, j'essaie de l'exécuter jusqu'à la fin avec la sortie dirigée vers un fichier." J'espère que vous avez 27,9 Go (26 Gio) d'espace libre, alors ...
John Dvorak
1
@JanDvorak J'ai plus de 600 Go d'espace libre ... mais il progresse si lentement qu'il semble peu probable de le faire jusqu'au bout.
feersum
-4

HQ9 + (17195 caractères)

La source:

9Q9

(commence à 5: 4 puis descend)

Sortie:

Le texte de la chanson "99 bouteilles de bière" (8596 caractères), la chaîne 9Q9(3 caractères) et une autre copie de "99 bouteilles de bière" (8596 caractères).

C'est une réponse très boiteuse et vous ne devriez pas la voter, mais quelqu'un a dû la poster.

Philipp
la source