RubyistはAtCoderをGolangで解いてみよう - マシンの理解

AtCoderの過去問精選をGolangで解く。

AtCoderとは？ なぜやるのか？

この記事をお読みください。

仕事でRubyばっかり入り浸っていると、つい「マシンがどう動いているのか」を忘れてしまう（習ったことがない）。Golangは、Rubyistにとって最も入門しやすい言語で、低レイヤーへの入門として最適だと思う。

解いてみた

最適解かどうかは分からないが、このレベルでの問題ではそこまでコード実装に差異はないと思う。

ABC049C - Daydream

https://atcoder.jp/contests/abs/tasks/arc065_a

与えられた文字列が、決められた単語の組み合わせだけで構成できるかという問題。

考え方

// Pseudocode
solve("erasedream", dictionary)

// 与えられた文字列を頭から順に見ていく。
when "e"
  // check against the dictionary
  // for each hit (dictionary word)
    "e" - "erase"
    "e" - "eraser"
      // check if it can cleanly match the dictionary word
        match("erasedream", "erase")
	match("erasedream", "eraser")
        // if matched, we can recursively solve for the substring
	  solve("dream", dict)

// end condition - if any of the solve encounteres empty string
// else false

Go code

Github codeを参照ください。

サンプル解法と比較したら、自分のはゴリ押しでした。

個人的に忘れがちなこと

• map や slice の初期化: map[string][]string とか。
• runeを使わないと、文字列のsubstringはUnicodeでバグる。