🔙 Back to Top

Tue Dec 15 19:04:11 JST 2015

Advent of Code (Day 1-7)

12月はこういう、advent calendar とかいうイベントが各方面であるらしい. 薄々は知ってる. その分野の記事を毎日誰かが担当して書くらしい. Advent of Code は、プロコンの問題を毎日一題ずつ出題される (他にも; http://www.adventar.org/calendars/912).

まだ Day 7 までしか解いてないからかもしれないけど易しい部類のものばかりが並ぶ. 問題と大きい入力が与えられるので、手元で実行して出力結果を送信する系.

以下、私の解法

Day 1

順序を気にせず開き括弧と閉じ括弧を数えるだけ

cat input | grep -o '(' | wc -l
cat input | grep -o ')' | wc -l
# 引き算!

Day 2

算数

Day 3

シミュレーション

Day 4

md5sum コマンドを使って全探索. 時間は掛かった. 雑に言えば、\(16^5\) 個に 1個は、目的のものが得られるはず.

Day 5

example まで含めて英文を気をつけて読めばOK.

Day 6

シミュレーション. 時間はかかるけど入力は300程度しかない.

Day 7

真面目にシミュレーションすることをせず、 ソースコードに変換して、コンパイラに投げることにした. 変数の依存関係が怪しいので、 自由な順序で宣言しても上手いことしてくれるHaskellにした. (a までに) ループはどうせ無いだろうと踏んだ. あったら困ったけど無かった.

# コードのヘッダ
cat << EOM > test.hs
import Data.Word
import Data.Bits
main :: IO ()
main = print a
  where
EOM

# 入力をHaskell語に変換
sed '
s/AND/.\&./g
s/OR/.|./g
s/NOT/complement/g
s/LSHIFT/`shiftL`/g
s/RSHIFT/`shiftR`/g
s/^\(.*\) -> \(.*\)$/    \2 = \1 :: Word16/g'
input >> test.hs

# 処理系に丸投げ
runghc test.hs

変数名に do if などのキーワードがあったので、手作業で doo iff みたいに変換する手間があった.

Word という型が、符号なし整数らしい. 学んだ. Haskellのビット演算は、演算子が気持ち悪い. ライブラリ実装な時点であれだ.