Hatena::ブログ(Diary)

菊やんの雑記帳

2008-08-10 Google Code Jam 2008

[] GCJ Round 3 12:45  GCJ Round 3 - 菊やんの雑記帳 を含むブックマーク

Google Code Jam 2008 Round 3 でした。

結果 377位

今までの教訓から、最初に問題を一通り眺めてから手をつけることにした。

C-small

問題を読んだら行ごとにDPすれば解けそうだったので、最初に解く。42分42秒

A-small

値の範囲が狭かったので、全部絵に描けばできるじゃん。

とりあえず、400x400あれば十分だから、それを完全に塗りたくる。

もう少し工夫して書いてれば、largeにも使えたのにな…。1時間18分54秒

D-small

問題が画面の右にはみ出してたので、よく読んでなかったのだが、これ一番簡単じゃん。1時間33分14

D-large

二項係数を計算して適当に足し引きすればいいんだよなと思い、のめりこんでしまった。時間切れ。

これより B-small を解くべきだった。

A-large

もうちょっと時間があれば解ける問題だと思う。

B-small

これを解くべきだった。

B-large

B-smallと同様にすれば解けるはず。

C-large

こんなの分かるかよ。二部グラフのなんちゃららしい

D-large

落ち着いて一日考えればできると思う。

2007-07-23 ICFP

なぜかドイツ色に

[] ICFPに参加 20:46  ICFPに参加 - 菊やんの雑記帳 を含むブックマーク

20日

dna2rnaをRubyで書く。遅くてバギーで話にならん。

21日

日が変わったころにドキュメントの最後にプレフィックス例が載ってたのに気づく。実行してみるが真っ黒。

朝になって、直線の描画にバグがあることに気づく。やっと、テスト画面が表示される。

dna2rnaのすべてのバグが取れる。

C++でdna2rnaを書いてたのが一応できる。やはり速度が物足りない。

通常の実行で半日ぐらいかけないと source.png ができない。

夜になってやっと、repairing guideが見えるようになる。

22日

未明ごろになってやっと、repairing catalog の分かってるページがすべて描画される。

新しいdna2rnaを再び1からC++で書いてみるが、全然速くならない。

ていうか、gprofがさっぱり実用にならない。まじめにメンテされてんのかこれ?

10時ごろになって、やっと明るくなった画像が描画される。

13時ごろになって、またdna2rnaを新しく実装したら10倍速くなった。

残していた高速化を適用したら、さらに10倍ぐらい速くなった。

でも、残り一日と少ししか残り時間がない…

23日

寝ておきたら風呂入ってたら朝の6時。もう半日しか残ってない。

朝7時。やっとGene Tableのほかのページへのアクセス方法が分かる。

mainとかそういったシンボルが分かったので、その辺を中心に解析を始める。

解析には逆アセンブラを作るのがよいという結論になったので、作り始める。

14時になってやっと逆アセンブラが9割がたの命令をサポートするようになる。あと三時間…

とりあえず、ぱっとみ簡単そうな花を移動させるプリフィックスを考えることにする。

17時半。やっと花が完璧に動く。

カーゴの色が変わる。

18時。親子のアヒルが表示される。

リンゴが梨になる。

18時半。UFOが消える。

アヒルを描くと全体が1ドットずれて表示されて、えらい点数が下がる。

アヒルの表示はあきらめることにする。

λx.xが消える。

クジラを移動させようとするも時間切れ。

アセンブラ

アセンブラが完成したおかげで、残り3時間で無茶苦茶進んだ。

アセンブラを使うとDNAがこんな感じに見える。

scenario関数の逆アセンブルの結果

00A5F8	RNA CCIIPIC
00A5F8	ALLOC STCK 48
00A5AF	MOVE 00000000 (0) TO B[24:24]
00A563	MOVE 00000000 (0) TO B[0:24]
00A517	CALL @571A21:000AF7	# setOrigin
00A45E	CALL @58B96F:001325	# sky
00A3A5	CALL @52DF43:000834	# resetOrigin
00A2EC	RNA PCCPFFP
00A2EC	JUMP @00A279 IF G[03346A:1] IS TRUE
00A29A	JUMP @009F77
00A279	ALLOC STCK 48
00A23A	MOVE 00000000 (0) TO B[24:24]
00A1EE	MOVE 00000000 (0) TO B[0:24]
00A1A2	CALL @571A21:000AF7	# setOrigin
00A0E9	CALL @6D3FB5:00293F	# surfaceTransform
00A030	CALL @52DF43:000834	# resetOrigin
009F77	RNA PFFPCCP
009F77	RNA PCCPFFP
009F77	ALLOC STCK 48
009F24	MOVE 00000000 (0) TO B[24:24]
009ED8	MOVE 000000EF (239) TO B[0:24]
009E8C	CALL @571A21:000AF7	# setOrigin
009DD3	CALL @25DA00:0009E9	# grass
009D1A	CALL @52DF43:000834	# resetOrigin
009C61	RNA PFFPCCP
009C61	RNA PCCPFFP
009C61	RNA PIIPICP
009C61	ALLOC STCK 1176
009BFF	MOVE 00000046 (70) TO B[1152:24]
009BB3	???
00990A	CALL @282970:00223B	# drawGrassPatch
009851	RNA PFFPCCP
009851	RNA PCCPFFP
009851	JUMP @0097D4 IF G[0C97B1:1] IS TRUE
0097F5	JUMP @0085A3
0097D4	ALLOC STCK 48
009795	MOVE 000001F4 (500) TO B[24:24]
009749	MOVE 00000223 (547) TO B[0:24]
0096FD	CALL @571A21:000AF7	# setOrigin
009644	ALLOC STCK 144
009603	MOVE 0023ADF8 (2338296), 00000172 (370) TO B[96:48]
00959D	MOVE 003CBE51 (3980881), 00000172 (370) TO B[48:48]
009537	MOVE 0065E3C5 (6677445), 00000244 (580) TO B[0:48]
0094D1	CALL @224FB1:0014C9	# flower
009418	CALL @52DF43:000834	# resetOrigin
00935F	RNA PCCPFFP
00935F	ALLOC STCK 48
009316	MOVE 00000216 (534) TO B[24:24]
0092CA	MOVE 00000223 (547) TO B[0:24]
00927E	CALL @571A21:000AF7	# setOrigin
0091C5	ALLOC STCK 144
009184	MOVE 0023ADF8 (2338296), 00000172 (370) TO B[96:48]
00911E	MOVE 0065E3C5 (6677445), 00000244 (580) TO B[48:48]
0090B8	MOVE 003CBE51 (3980881), 00000172 (370) TO B[0:48]
009052	CALL @224FB1:0014C9	# flower
008F99	CALL @52DF43:000834	# resetOrigin
008EE0	RNA PFFPCCP
008EE0	RNA PCCPFFP
008EE0	ALLOC STCK 48
008E8D	MOVE 00000205 (517) TO B[24:24]
008E41	MOVE 0000023B (571) TO B[0:24]
008DF5	CALL @571A21:000AF7	# setOrigin
008D3C	ALLOC STCK 144
008CFB	MOVE 0023ADF8 (2338296), 00000172 (370) TO B[96:48]
008C95	MOVE 0065E3C5 (6677445), 00000244 (580) TO B[48:48]
008C2F	MOVE 003CBE51 (3980881), 00000172 (370) TO B[0:48]
008BC9	CALL @224FB1:0014C9	# flower
008B10	CALL @52DF43:000834	# resetOrigin
008A57	RNA PFFPCCP
008A57	RNA PCCPFFP
008A57	ALLOC STCK 48
008A04	MOVE 0000022E (558) TO B[24:24]
0089B8	MOVE 0000022F (559) TO B[0:24]
00896C	CALL @571A21:000AF7	# setOrigin
0088B3	ALLOC STCK 144
008872	MOVE 0023ADF8 (2338296), 00000172 (370) TO B[96:48]
00880C	MOVE 003CBE51 (3980881), 00000172 (370) TO B[48:48]
0087A6	MOVE 0065E3C5 (6677445), 00000244 (580) TO B[0:48]
008740	CALL @224FB1:0014C9	# flower
008687	CALL @52DF43:000834	# resetOrigin
0085CE	RNA PFFPCCP
0085CE	JUMP @0082A1
0085A3	ALLOC STCK 48
008564	MOVE 000001F4 (500) TO B[24:24]
008518	MOVE 00000223 (547) TO B[0:24]
0084CC	CALL @571A21:000AF7	# setOrigin
008413	CALL @45ACB4:001305	# flowerbed
00835A	CALL @52DF43:000834	# resetOrigin
0082A1	RNA PFFPCCP
0082A1	RNA PCCPFFP
0082A1	ALLOC STCK 48
00824E	MOVE 000001D1 (465) TO B[24:24]
008202	MOVE 0000015E (350) TO B[0:24]
0081B6	CALL @571A21:000AF7	# setOrigin
0080FD	CALL @21EDD5:006022	# cargobox
008044	CALL @52DF43:000834	# resetOrigin
007F8B	RNA PFFPCCP
007F8B	RNA PCCPFFP
007F8B	???
007F46	JUMP @007EDD IF G[0C45E9:1] IS TRUE
007EFE	JUMP @007EBC
007EDD	JUMP @007B89
007EBC	???
007E8B	ALLOC STCK 48
007E4C	MOVE 0000000B (11) TO B[24:24]
007E00	MOVE 00000123 (291) TO B[0:24]
007DB4	CALL @571A21:000AF7	# setOrigin
007CFB	CALL @25CCA1:000D47	# motherDuckWithChicks
007C42	CALL @52DF43:000834	# resetOrigin
007B89	RNA PFFPCCP
007B89	RNA PCCPFFP
007B89	ALLOC STCK 48
007B36	MOVE 000001F4 (500) TO B[24:24]
007AEA	MOVE 000000AA (170) TO B[0:24]
007A9E	CALL @571A21:000AF7	# setOrigin
0079E5	CALL @3C870E:00372B	# appletree
00792C	CALL @52DF43:000834	# resetOrigin
007873	RNA PFFPCCP
007873	RNA PCCPFFP
007873	ALLOC STCK 48
007820	MOVE 0000021C (540) TO B[24:24]
0077D4	MOVE 000000AF (175) TO B[0:24]
007788	CALL @571A21:000AF7	# setOrigin
0076CF	CALL @3C870E:00372B	# appletree
007616	CALL @52DF43:000834	# resetOrigin
00755D	RNA PFFPCCP
00755D	RNA PCCPFFP
00755D	JUMP @0074E0 IF G[033964:1] IS TRUE
007501	JUMP @0070D2
0074E0	ALLOC STCK 48
0074A1	MOVE 0000020D (525) TO B[24:24]
007455	MOVE 00000104 (260) TO B[0:24]
007409	CALL @571A21:000AF7	# setOrigin
007350	ALLOC STCK 96
007310	MOVE 006D730D (7172877), 00000208 (520) TO B[48:48]
0072AA	MOVE 003C674C (3958604), 000001F4 (500) TO B[0:48]
007244	CALL @541D0E:003049	# chick
00718B	CALL @52DF43:000834	# resetOrigin
0070D2	RNA PFFPCCP
0070D2	RNA PCCPFFP
0070D2	ALLOC STCK 48
00707F	MOVE 00000208 (520) TO B[24:24]
007033	MOVE 000000BE (190) TO B[0:24]
006FE7	CALL @571A21:000AF7	# setOrigin
006F2E	CALL @3C870E:00372B	# appletree
006E75	CALL @52DF43:000834	# resetOrigin
006DBC	RNA PFFPCCP
006DBC	RNA PCCPFFP
006DBC	ALLOC STCK 48
006D69	MOVE 00000014 (20) TO B[24:24]
006D1D	MOVE 000000FA (250) TO B[0:24]
006CD1	CALL @571A21:000AF7	# setOrigin
006C18	CALL @64D550:00510B	# weeds
006B5F	CALL @52DF43:000834	# resetOrigin
006AA6	RNA PFFPCCP
006AA6	RNA PCCPFFP
006AA6	ALLOC STCK 48
006A53	MOVE 00000186 (390) TO B[24:24]
006A07	MOVE 000000E6 (230) TO B[0:24]
0069BB	CALL @571A21:000AF7	# setOrigin
006902	CALL @23BCFC:000CFA	# vmu
006849	CALL @52DF43:000834	# resetOrigin
006790	RNA PFFPCCP
006790	RNA PCCPFFP
006790	ALLOC STCK 48
00673D	MOVE 00000023 (35) TO B[24:24]
0066F1	MOVE 00000019 (25) TO B[0:24]
0066A5	CALL @571A21:000AF7	# setOrigin
0065EC	CALL @51A9FF:01294A	# windmill
006533	CALL @52DF43:000834	# resetOrigin
00647A	RNA PFFPCCP
00647A	RNA PCCPFFP
00647A	ALLOC STCK 48
006427	MOVE 0000002D (45) TO B[24:24]
0063DB	MOVE 00000113 (275) TO B[0:24]
00638F	CALL @571A21:000AF7	# setOrigin
0062D6	CALL @4D730E:002640	# lambda-id
00621D	CALL @52DF43:000834	# resetOrigin
006164	RNA PFFPCCP
006164	RNA PCCPFFP
006164	RNA PFFPCCP
006164	RNA PCCPFFP
006164	RNA PIIPICP
006164	RNA PIPIIFF
006164	RNA PIPIIFF
006164	RNA PIPIIFF
006164	RNA PIPIIFF
006164	RNA PIPIIFF
006164	RNA PIPIIFF
006164	RNA PIPIIFF
006164	RNA PIPIIFF
006164	RNA PIPIIIC
006164	RNA PIPIIIC
006164	RNA PIPIIIC
006164	RNA PIPIIIC
006164	RNA PIPIIIC
006164	RNA PIPIIIC
006164	RNA PIPIIIC
006164	RNA PIPIIIC
006164	RNA PIPIIIC
006164	RNA PIPIIIC
006164	RNA PIPIIIC
006164	RNA PIPIIIC
006164	RNA PIPIIIC
006164	RNA PIPIIIC
006164	RNA PIPIIIC
006164	ALLOC STCK 24529
006004	???
005FD3	???
005EEA	CALL @5A5F7E:001B95	# drawPolyline
005E31	ALLOC STCK 48
005DF2	MOVE 00000015 (21) TO B[24:24]
005DA6	MOVE 0000017A (378) TO B[0:24]
005D5A	CALL @5412AB:000A4B	# moveTo
005CA1	RNA PIIPIIP
005CA1	RNA PFFPCCP
005CA1	RNA PCCPFFP
005CA1	ALLOC STCK 48
005C44	MOVE 00000014 (20) TO B[24:24]
005BF8	MOVE 0000019B (411) TO B[0:24]
005BAC	CALL @571A21:000AF7	# setOrigin
005AF3	CALL @450195:000F99	# river
005A3A	CALL @52DF43:000834	# resetOrigin
005981	RNA PFFPCCP
005981	RNA PCCPFFP
005981	ALLOC STCK 48
00592E	MOVE 00000000 (0) TO B[24:24]
0058E2	MOVE 00000157 (343) TO B[0:24]
005896	CALL @571A21:000AF7	# setOrigin
0057DD	CALL @6F0E03:000B28	# bridge
005724	CALL @52DF43:000834	# resetOrigin
00566B	RNA PFFPCCP
00566B	RNA PCCPFFP
00566B	ALLOC STCK 48
005618	MOVE 00000008 (8) TO B[24:24]
0055CC	MOVE 000001AE (430) TO B[0:24]
005580	CALL @571A21:000AF7	# setOrigin
0054C7	CALL @3D3B81:002C15	# tuiips
00540E	CALL @52DF43:000834	# resetOrigin
005355	RNA PFFPCCP
005355	RNA PCCPFFP
005355	ALLOC STCK 48
005302	MOVE 0000005D (93) TO B[24:24]
0052B6	MOVE 000001B3 (435) TO B[0:24]
00526A	CALL @571A21:000AF7	# setOrigin
0051B1	CALL @532F8C:000C72	# grass1
0050F8	CALL @52DF43:000834	# resetOrigin
00503F	ALLOC STCK 48
005000	MOVE 0000007B (123) TO B[24:24]
004FB4	MOVE 000001CF (463) TO B[0:24]
004F68	CALL @571A21:000AF7	# setOrigin
004EAF	CALL @4A8B3F:000C41	# grass2
004DF6	CALL @52DF43:000834	# resetOrigin
004D3D	ALLOC STCK 48
004CFE	MOVE 0000008E (142) TO B[24:24]
004CB2	MOVE 000001EA (490) TO B[0:24]
004C66	CALL @571A21:000AF7	# setOrigin
004BAD	CALL @23AF82:000D62	# grass3
004AF4	CALL @52DF43:000834	# resetOrigin
004A3B	ALLOC STCK 48
0049FC	MOVE 0000009A (154) TO B[24:24]
0049B0	MOVE 000001EF (495) TO B[0:24]
004964	CALL @571A21:000AF7	# setOrigin
0048AB	CALL @3FD02F:000D43	# grass4
0047F2	CALL @52DF43:000834	# resetOrigin
004739	ALLOC STCK 48
0046FA	MOVE 000000AC (172) TO B[24:24]
0046AE	MOVE 00000206 (518) TO B[0:24]
004662	CALL @571A21:000AF7	# setOrigin
0045A9	CALL @532F8C:000C72	# grass1
0044F0	CALL @52DF43:000834	# resetOrigin
004437	ALLOC STCK 48
0043F8	MOVE 000000C1 (193) TO B[24:24]
0043AC	MOVE 00000215 (533) TO B[0:24]
004360	CALL @571A21:000AF7	# setOrigin
0042A7	CALL @4A8B3F:000C41	# grass2
0041EE	CALL @52DF43:000834	# resetOrigin
004135	ALLOC STCK 48
0040F6	MOVE 000000D1 (209) TO B[24:24]
0040AA	MOVE 00000226 (550) TO B[0:24]
00405E	CALL @571A21:000AF7	# setOrigin
003FA5	CALL @23AF82:000D62	# grass3
003EEC	CALL @52DF43:000834	# resetOrigin
003E33	ALLOC STCK 48
003DF4	MOVE 000000DA (218) TO B[24:24]
003DA8	MOVE 0000022B (555) TO B[0:24]
003D5C	CALL @571A21:000AF7	# setOrigin
003CA3	CALL @3FD02F:000D43	# grass4
003BEA	CALL @52DF43:000834	# resetOrigin
003B31	ALLOC STCK 48
003AF2	MOVE 000000E1 (225) TO B[24:24]
003AA6	MOVE 00000237 (567) TO B[0:24]
003A5A	CALL @571A21:000AF7	# setOrigin
0039A1	CALL @532F8C:000C72	# grass1
0038E8	CALL @52DF43:000834	# resetOrigin
00382F	ALLOC STCK 48
0037F0	MOVE 00000068 (104) TO B[24:24]
0037A4	MOVE 000001BD (445) TO B[0:24]
003758	CALL @571A21:000AF7	# setOrigin
00369F	CALL @4A8B3F:000C41	# grass2
0035E6	CALL @52DF43:000834	# resetOrigin
00352D	ALLOC STCK 48
0034EE	MOVE 0000006F (111) TO B[24:24]
0034A2	MOVE 000001C9 (457) TO B[0:24]
003456	CALL @571A21:000AF7	# setOrigin
00339D	CALL @23AF82:000D62	# grass3
0032E4	CALL @52DF43:000834	# resetOrigin
00322B	ALLOC STCK 48
0031EC	MOVE 00000087 (135) TO B[24:24]
0031A0	MOVE 000001DE (478) TO B[0:24]
003154	CALL @571A21:000AF7	# setOrigin
00309B	CALL @3FD02F:000D43	# grass4
002FE2	CALL @52DF43:000834	# resetOrigin
002F29	ALLOC STCK 48
002EEA	MOVE 000000A5 (165) TO B[24:24]
002E9E	MOVE 000001FB (507) TO B[0:24]
002E52	CALL @571A21:000AF7	# setOrigin
002D99	CALL @532F8C:000C72	# grass1
002CE0	CALL @52DF43:000834	# resetOrigin
002C27	ALLOC STCK 48
002BE8	MOVE 000000B7 (183) TO B[24:24]
002B9C	MOVE 0000020F (527) TO B[0:24]
002B50	CALL @571A21:000AF7	# setOrigin
002A97	CALL @4A8B3F:000C41	# grass2
0029DE	CALL @52DF43:000834	# resetOrigin
002925	ALLOC STCK 48
0028E6	MOVE 000000C6 (198) TO B[24:24]
00289A	MOVE 0000021C (540) TO B[0:24]
00284E	CALL @571A21:000AF7	# setOrigin
002795	CALL @23AF82:000D62	# grass3
0026DC	CALL @52DF43:000834	# resetOrigin
002623	ALLOC STCK 48
0025E4	MOVE 000000CD (205) TO B[24:24]
002598	MOVE 00000220 (544) TO B[0:24]
00254C	CALL @571A21:000AF7	# setOrigin
002493	CALL @3FD02F:000D43	# grass4
0023DA	CALL @52DF43:000834	# resetOrigin
002321	ALLOC STCK 48
0022E2	MOVE 000000E7 (231) TO B[24:24]
002296	MOVE 0000023F (575) TO B[0:24]
00224A	CALL @571A21:000AF7	# setOrigin
002191	CALL @532F8C:000C72	# grass1
0020D8	CALL @52DF43:000834	# resetOrigin
00201F	RNA PFFPCCP
00201F	RNA PCCPFFP
00201F	ALLOC STCK 48
001FCC	MOVE 00000187 (391) TO B[24:24]
001F80	MOVE 000000B0 (176) TO B[0:24]
001F34	CALL @571A21:000AF7	# setOrigin
001E7B	ALLOC STCK 2
001E40	???
001E0F	???
001DDE	CALL @26589C:001F2A	# whale
001D25	CALL @52DF43:000834	# resetOrigin
001C6C	RNA PFFPCCP
001C6C	RNA PCCPFFP
001C6C	ALLOC STCK 48
001C19	MOVE 00000188 (392) TO B[24:24]
001BCD	MOVE 000000E6 (230) TO B[0:24]
001B81	CALL @571A21:000AF7	# setOrigin
001AC8	CALL @592C81:001C97	# crater
001A0F	CALL @52DF43:000834	# resetOrigin
001956	RNA PFFPCCP
001956	RNA PCCPFFP
001956	ALLOC STCK 48
001903	MOVE 00000000 (0) TO B[24:24]
0018B7	MOVE 00000000 (0) TO B[0:24]
00186B	CALL @571A21:000AF7	# setOrigin
0017B2	CALL @0DAEDB:005806	# bmu
0016F9	CALL @52DF43:000834	# resetOrigin
001640	RNA PFFPCCP
001640	RNA PCCPFFP
001640	ALLOC STCK 48
0015ED	MOVE 000000FF (255) TO B[24:24]
0015A1	MOVE 00000131 (305) TO B[0:24]
001555	CALL @571A21:000AF7	# setOrigin
00149C	CALL @6F31B6:001A83	# balloon
0013E3	CALL @52DF43:000834	# resetOrigin
00132A	RNA PFFPCCP
00132A	RNA PCCPFFP
00132A	JUMP @0012AD IF G[0C97B1:1] IS TRUE
0012CE	JUMP @000E91
0012AD	???
001261	???
0011FB	ALLOC STCK 10416
0011B4	???
001108	MOVE 0000011D (285) TO B[1176:24]
0010BC	MOVE 0000023A (570) TO B[1152:24]
001070	???
000F6B	CALL @239A6D:00056F	# drawString
000EB2	JUMP @0009E2
000E91	???
000D56	???
000CF0	ALLOC STCK 10416
000CA9	???
000BFD	MOVE 0000011D (285) TO B[1176:24]
000BB1	MOVE 0000023A (570) TO B[1152:24]
000B65	???
000A9B	CALL @239A6D:00056F	# drawString
0009E2	RNA PFFPCCP
0009E2	RNA PCCPFFP
0009E2	???
0009A2	JUMP @000939 IF G[00050F:1] IS TRUE
00095A	JUMP @000908
000939	???
000908	???
0008C0	JUMP @00057C
00089F	ALLOC STCK 48
000860	MOVE 00000000 (0) TO B[24:24]
000814	MOVE 00000000 (0) TO B[0:24]
0007C8	CALL @571A21:000AF7	# setOrigin
00070F	CALL @652673:0006BF	# cloak-night
000656	CALL @52DF43:000834	# resetOrigin
00059D	JUMP @00057C
00057C	???
00054D	RNA PFFPCCP
00054D	RNA PCCPFFP
00054D	???
0004DA	JUMP @000498
0004B9	JUMP @000418
000498	???
000439	JUMP @0000F5
000418	ALLOC STCK 48
0003D9	MOVE 00000000 (0) TO B[24:24]
00038D	MOVE 00000000 (0) TO B[0:24]
000341	CALL @571A21:000AF7	# setOrigin
000288	CALL @309590:03484D	# cloak-rain
0001CF	CALL @52DF43:000834	# resetOrigin
000116	JUMP @0000F5
0000F5	RNA PFFPCCP
0000F5	RNA CFPICFP
0000F5	???
00004B	???
00003E	???
000038	???
000032	???
00002C	???
000026	???
00001D	???

これがあと半日早くできてれば、もう少し点数稼げてたんだけどな。役にたたんヒントに釣られすぎた。

適当にフラグをいじってたら

なんかドイツ色になった。「Endo hat gemorpht」とかになってるし…

f:id:kikx:20070723211059p:image

2007-07-18 BrainstuckでBF

[] 03:32 BrainstuckでBF - 菊やんの雑記帳 を含むブックマーク

shinhさんのBrainstuck(id:shinichiro_h:20070714#1184371977)でBrainf*ckを実装する方法を思いついたのだが、書く時間がない。

以下アイデア

必要なBFのセルは1ステップ実行するごとに最大で一個しか増えないので、1ステップ実行するごとにスタック上のBFのセルを全部積みなおして、最後に一個だけ新しいセルを追加する。

すなわち、nステップ後のスタックは(スタックは右に伸びるとする)

BF junk C0 C1 ... Cn

ここで、BFは実行するBFのコード、junkはもう使わないごみ領域、C0が0番目のセル、…、Cnがn番目のセル。

各々のセルはスタックの5エントリを消費して、内容は

C=(clock, value, cursor, pc, end)

ここで、左にある要素ほどスタックの深いところにある。

nステップ後のスタックにおいては、

value はこのセルの現在値。cursor はカーソルがこのセルの位置にあれば1、なければ0。end は常に0。

pc と clock は Cn 以外はゴミで、Cn.pc は次に実行するコードの深さを指す。Cn.clock は n*5。

で、うまくコードを書いてやればn+1ステップ後のスタック

BF junk C0 C1 ... Cn C'0 C'1 ... C'n C'n+1

の形にできてインタープリタが完成する。このコピーの途中で「+-<>」の4命令は実行できる(最初に命令で分岐して、個別に更新しながらコピーを実行)。新しい C'n+1.pc は Cn.pc + n*5 + 5 - 1 にしないといけないのだが、これの計算に C'i.pc の領域をうまく使おう。

残った繰り返し命令がめんどくさいのだが、「通常実行モード」「]を探してる途中」「[を探してる途中」で分けるしかないはず。

実装できるはずなのだが、こいつはめんどうだ。