Poszukuję programów w ogromnej tablicy Boggle

25

Każdy znak w tym 64 na 64 bloku tekstu został wybrany losowo i jednolicie spośród 95 drukowanych znaków ASCII .

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

Twoim zadaniem w tym wyzwaniu nie jest napisanie własnego kodu, ale wyodrębnienie kodu z tego bloku tekstu, tak jakby to była ogromna siatka Boggle, a zamiast słowa szukasz programu, który można uruchomić.

Zgłoszenie do programu, który generuje najdłuższy skończony wynik, wygrywa.

Detale

Traktuj siatkę tekstu 64 na 64 dokładnie tak, jak siatkę Boggle 64 na 64 z dodatkowymi znakami. Skonstruuj ciąg, który jest programem, który można uruchomić w jakimś języku, wybierając początkową lokalizację na siatce i wielokrotnie przesuwając jeden krok w pionie, w poziomie lub na ukosie (łącznie 8 kierunków) tyle razy, ile chcesz. NIE możesz używać tej samej przestrzeni siatki więcej niż raz!

Na przykład te 4 wiersze zostały pobrane ze środka bloku tekstu:

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

Zaczynając pod prawego końca trzeciej linii, mogę przejść do przechodząc po przekątnej w dół i w prawo, a następnie "przechodząc w prawo, następnie trzykrotnie w górę i czterokrotnie w  zKlewo #3x". To śledzi ciąg znaków, p " zK#3x"który jest uruchamiany jako program Ruby" zK#3x" .

Celem jest znalezienie programu, który generuje najdłuższy skończony wynik. Podczas liczenia długości danych wyjściowych brane są pod uwagę tylko drukowalne znaki ASCII (oznacza to, że tabulacje i znaki nowej linii nie są liczone), chociaż mogą występować inne znaki. Przykład Ruby produkuje tylko 8 znaków.

Również...

  • Program może mieć od 1 do 4096 znaków.
  • Program nie może zawierać tabulatorów, znaków nowej linii ani niedrukowalnych znaków ASCII (ponieważ nie ma ich w siatce).
  • Program powinien uruchomić się i wyjść bez błędów.
  • Nie ma ograniczeń czasowych ani złożoności, o ile program ostatecznie zakończyłby się skończonym wyjściem.
  • Siatka nie zapętla się od lewej do prawej lub od góry do dołu.

Podaj miejsce, w którym pojawia się Twój program, abyśmy mogli szybko sprawdzić, czy naprawdę tam jest.

Hobby Calvina
źródło
8
Dlaczego postać 4096 odpoczywa ... och.
John Dvorak,
2
Być może byłoby bardziej interesujące, gdyby program musiał rozwiązać rzeczywisty problem z kodem golfowym, ale wziąć go z sieci.
feersum
2
@DavidCarraher - Lub w rzeczywistości dla każdego języka nie golfowego. Znalazłem na przykład jedną instancję yes.
1
TECO nie jest językiem golfowym ... to edytor taśm / tekstów z lat 60. XX wieku.
feersum
1
Na pierwszy rzut oka wygląda na doskonale wykonalny program perla ...
DGM

Odpowiedzi:

15

CJam, over (81182737 ^ 2813292) ↑↑ (10604499373-1) znaki

Okej, myślę, że w końcu wszystko załatwiłem. To było zabawne - wymyślenie kodu było jak nawigacja po polu minowym.


Zanim zaczniemy, zacznijmy od prostszego przykładu ( wypróbuj online ):

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

hto pętla „do-while”, która pozostawia warunek na stosie i {}jest blokiem kodu. Blok wewnętrzny to:

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

Załóżmy, że górna część stosu to [1 10]i wykonujemy do-while {(\5*\}h;. Oto co się dzieje:

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

Dzieje się tak, dopóki 10 spadków aż do zera i pętla się nie skończy, w którym to momencie kończy się [5^10 0]na szczycie stosu. Następnie możemy użyć, ;aby zerować zero, pozostawiając [5^10].

Innymi słowy, właśnie wykonaliśmy potęgowanie, [1 x]{(\5*\}h;czego wynikiem jest [5^x].

Blok zewnętrzny {(\1\{(\5*\}h;\}h;jest podobny, ale zamiast 5*w środku mamy naszą pętlę „wykładniczej podstawy 5”. W naszym prostym przykładzie zaczynamy od [1 3]:

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

Góra ma zero, więc zatrzymujemy pętlę i pop, wychodzimy [5^5^5]. Innymi słowy, właśnie stworzyliśmy 5^5^5lub 5↑↑3w notacji Knutha w górę . Możesz przełączyć 5 i 3 na inne liczby, ale hiperprzekompensowanie robi się duże szybko , więc nie polecałbym wybierania zbyt dużych wartości.


Teraz na prawdę:

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

(Ślad ścieżki)

Anotowane (wszystko bez notatek jest wypełniaczem):

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

Jest to w zasadzie taki sam jak prosty przykład, z dużą ilością wypełniacza podczas nawigacji między instrukcjami w siatce.

Zamiast 5 i 3 mamy 81182737^2813292i 10604499373, co oznacza, że (81182737^2813292)↑↑10604499373jest wyprowadzane na końcu (oczywiście biorąc pod uwagę wystarczającą ilość czasu i pamięci!). Zauważ, że jest to tylko dolna granica - odbywa się wiele innych wydruków, np. Przy 6 i 3 wyjście ma ponad 2 miliony znaków, mimo że 6^6^6ma tylko 36k cyfr.

Jeśli chcesz wypróbować tę pełną wersję dla siebie, przetestuj za pomocą:

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

zastępując cyfry 5 i 3 w drugim i czwartym wierszu wybranymi liczbami. Zauważ, że wynik będzie zawierał kilka dodatkowych cyfr wokół ważnej liczby podzielonej na części (mianowicie poprzedzającej 010i końcowej 0).


Kilka uwag na temat CJam

Może zastanawiamy się: dlaczego nie użyć wbudowanego potęgowania CJam #zamiast wewnętrznej pętli do-while? Niestety, po przeszukaniu źródła CJam, dowiedziałem się, że do potęgowania podstawa może być BigInt (dowolna precyzja), ale wykładnik przekształca się w normalną 32-bitową liczbę całkowitą . Ma to zabawne, ale irytujące skutki uboczne:

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

Oznaczało to, że nie mogłem użyć wbudowanej funkcji wykładniczej CJam, gdy wykładnik jest zbyt duży, z powodu przepełnienia. Jednak zwielokrotnienie różni się od pomnożenia dwóch wyników BigInt w nowy BigInt, więc postanowiłem to wykorzystać.

Sp3000
źródło
4
Usunięto regułę minutową. Zwariować!
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>

wprowadź opis zdjęcia tutaj

Edycja: Zmieniłem kilka znaków, ponieważ przypadkowo użyłem ponownie jednego, ale ta część była w komentarzu, więc nie ma to większego znaczenia.

W ?zakręty na polecenia echo, którego używam do tworzenia najbardziej wyjścia. Następnie znaki \RZK%B"s'1UC>są drukowane w pętli. %B"sdodaje jeden do B, a następnie sprawdza, czy jest on mniejszy od zera. Zatem warunek ten należy wprowadzić po 2 ^ 31 cyklach, gdy przepełni się on liczbą ujemną. Wewnątrz warunkowego znajduje się EXpolecenie, które wychodzi z programu.

Obecnie próbuję uruchomić go do końca z wyjściem skierowanym do pliku.

feersum
źródło
„Obecnie próbuję uruchomić go do końca z wyjściem skierowanym do pliku.” Mam nadzieję, że masz 27,9 GB (26 GiB) wolnego miejsca, a następnie ...
John Dvorak
1
@JanDvorak Mam ponad 600 GB wolnego miejsca ... jednak postępuje tak wolno, że wydaje się, że jest mało prawdopodobne, aby udało się to zrobić.
feersum
-4

HQ9 + (17195 znaków)

Źródło:

9Q9

(zaczyna się od 5: 4, a następnie w dół)

Wydajność:

Tekst piosenki „99 butelek piwa” (8596 znaków), ciąg znaków 9Q9(3 znaki) i kolejna kopia „99 butelek piwa” (8596 znaków).

To bardzo kiepska odpowiedź i nie powinieneś głosować za nią, ale ktoś musiał ją opublikować.

Philipp
źródło