オフラインリアルタイムどう書くE03 を解いた

オフラインリアルタイムどう書くE03に参加してきました。

- [凸頂点の数 横へな2016.4.2 問題](http://nabetani.sakura.ne.jp/hena/orde03nofconv/)
- [オフラインリアルタイムどう書くE03 の問題 (Qiita)](http://qiita.com/Nabetani/items/b8bf742d278c6cf501aa)

## 戦略

まず、凸頂点がどのような条件で現れるのかを考えました。
結論として、今回の問題では`00`の図形を除くと共有される頂点（下図の赤で示した箇所）は必ず凹頂点になるため、逆に言うと共有されない頂点（下図の青で示した箇所）が凸頂点となるため、すべての図形の頂点を取得し、一度しか現れない頂点の個数を数えることで凸頂点の個数を求めることができます。

<img src="https://qiita-image-store.s3.amazonaws.com/0/7256/1db1760a-dc40-5c41-ab63-fed2ec885061.jpeg" width="240"/>

ただし、`00`の図形は凹頂点を含んでいるため、頂点を共有しないにもかかわらず凹頂点になる場合があるので、その部分を取り除いてから数える必要があります。

<img src="https://qiita-image-store.s3.amazonaws.com/0/7256/bbc81fa7-4718-d954-ff25-eecf40f1942e.jpeg" width="240" />


頂点は、半径方向の数字を <i>r</i> 、回転角方の文字 a 〜 t を数値の 0 〜 19 に置き換えたものを <i>t</i>として、次のように定義しました。

```math
\begin{eqnarray*}
vertex_{hex} & = & (r - d_r, 2t + r - 1 + d_t \pmod{40}) \\
ここで \\
d_r & = & \lbrace 0, 1 \rbrace \\
d_t & = & \lbrace 0, 1, 2 \rbrace
\end{eqnarray*}
```

頂点の座標の取り方は、図に表すと次のようになります。

![凸頂点の数3.jpg](https://qiita-image-store.s3.amazonaws.com/0/7256/6dd9cdee-f9ff-0877-c308-5cc3b189aea0.jpeg)

## Ruby（時間内に解いたもの）

今回は Ruby で挑戦し、おそらく初めて時間内に全テストが通るコードを書くことができました。
共有されない頂点の個数を数えればよいということに気がつくまでおよそ20分、そこからコードを書き始めておよそ30分、計50分あまりでの書き上げました。

`00`の凹頂点は、全頂点を取得後に図形に`00`が含まれる場合は凹頂点になる点をすべて取り除くという方法で対処しています。

- https://gist.github.com/mattsan/bfd32c0045930354db7ac6ebd1324290

見返してみると冗長なコードが散見されます。

## Ruby

後になって、`00`の凹頂点を数えないようにするには、後から点を取り除くのではなく凹頂点を最初から複数回登録すれば頂点が共有されているとみなされて数え上げの対象から外すことができることに気がつきました。

それを踏まえて書き直したのがこちら。さらに短くなりました。

```ruby
def solve(input)
  input
    .chars
    .each_slice(2)
    .each_with_object([]) {|(r, t), a|
      r, t = [r, t] == ['0', '0'] ? [0, 0] : [r.to_i, t.ord - 'a'.ord]
      if [r, t] == [0, 0]
        40.times {|i| a.push [0, i] }
        20.times {|i| a.push [0, i * 2 + 1] }
      else
        [0, 1].product([0, 1, 2]).each {|dr, dt| a.push [r - dr, (t * 2 + r - 1 + dt) % 40] }
      end
    }
    .group_by {|r, t| [r, t] }
    .map {|k, v| [k, v.size] }
    .select {|k, size| size == 1}
    .size
    .to_s
end

# 以下テスト実施用コード

def test(input, expected)
  actual = solve(input)
  if actual == expected
    print '.'
  else
    puts <<-EOS

input:    #{input}
expected: #{expected}
actual:   #{actual}
EOS
  end
end

DATA.each do |line|
  test *line.split
end
puts

__END__
1a2t3s2s 11
1a1c1d00 22
```

## Haskell

メソッドチェインで書くことができたので、Haskell　で書くと綺麗に書けそうだと思い翻訳してみたのがこちら。
頂点を取得する関数がまた分離しましたが、`solve` 関数をポイントフリースタイルで書けたので満足です。

```hs
import Data.Char
import Data.List

vertices [] = []
vertices ('0':'0':cs) =
  [(0, t) | t <- [0..39]] ++ [(0, t * 2 + 1) | t <- [0..19]] ++ vertices cs
vertices (c1:c2:cs) =
  [(r - dr, mod (t * 2 + r - 1 + dt) 40) | dr <- [0, 1], dt <- [0..2]] ++ vertices cs
  where
    r = ord c1 - ord '0'
    t = ord c2 - ord 'a'

solve = show.length.filter (==1).map length.group.sort.vertices

-- 以下テスト実施用コード

test input expected =
  if actual == expected
    then
      putStr "."
    else
      putStrLn $ concat
        [ "\ninput:    ", input
        , "\nexpected: ", expected
        , "\nactual:   ", actual
        ]
  where
    actual = solve input

main = do
  test "1a2t3s2s" "11"
  test "1a1c1d00" "22"
  -- 以下略
```

## Prolog

Haskell で書けたのだから Prolog でも書けそうだ、と翻訳したのがこちら。
「複数回出現しない要素の数を数える」よい方法が思いつかなかったため、まず各々の要素を要素の出現回数に置き換えたリストを作成し、そのリストの中から値が1の要素の数を数える、という方法を取っています。

具体的には、`[a, b, a, c]` というリストがあった場合、それぞれの出現回数（`a` は 2 回、`b` と `c` は 1 回）に置き換えた `[2, 1, 2, 1]` というリストをまず作成し、そこから値が 1 の個数を数える、ということをしています。

```prolog
:- initialization(main).

hex_vertex(R, T, DR, DT, [R1 ,T1]) :-
  R1 is R - DR,
  T1 is (T * 2 + R - 1 + DT) mod 40.

vertices([], []).
vertices([0'0, 0'0|CS], VS) :-
  findall(V, (between(0, 39, T), append([0], [T], V)), VS1),
  findall(V, (between(0, 39, T), T mod 2 =:= 1, append([0], [T], V)), VS2),
  append(VS1, VS2, VS3),
  vertices(CS, VS4),
  append(VS3, VS4, VS).
vertices([C1, C2|CS], VS) :-
  R is C1 - 0'0,
  T is C2 - 0'a,
  findall(V, (between(0, 1, DR), between(0, 2, DT), hex_vertex(R, T, DR, DT, V)), VS1),
  vertices(CS, VS2),
  append(VS1, VS2, VS).

elems_counts([], _, []).
elems_counts([E|ES], List, [C|CS]) :-
  findall(E0, (member(E0, List), E0 == E), ES0),
  length(ES0, C),
  elems_counts(ES, List, CS).
elems_counts(ES, CS) :-
  elems_counts(ES, ES, CS).

solve(Input, Output) :-
  vertices(Input, VS),                       % 全頂点を取得する
  elems_counts(VS, CS),                      % 要素を要素の出現数に変換する
  findall(C, (member(C, CS), C =:= 1), CS1), % 出現数が 1 の要素のみ抽出する
  length(CS1, Count),                        % 出現数が 1 の要素の個数を数える
  number_codes(Count, Output).               % 個数を文字列にする

% 以下テスト実施用コード

judge(_, Expected, Expected) :-
  format(".", []).
judge(Input, Expected, Actual) :-
  format("~ninput:    ~s~nexpected: ~s~nactual:   ~s~n", [Input, Expected, Actual]).

test(Input, Expected) :-
  solve(Input, Actual),
  judge(Input, Expected, Actual).

main :-
  test("1a2t3s2s", "11"),
  test("1a1c1d00", "22"),
  test("00", "20"),
  % 中略
  format("~n", []),
  halt.
```

## C++

全頂点を集めてから出現回数を数えるのは C++ では面倒な感じだったので、代わりに頂点を求めるたびに個数を数えていくという方法を取っています。

```cpp
#include <iostream>
#include <string>
#include <map>
#include <numeric>

typedef std::map<int, int> Vertices;

const int ds[][2] = { {0, 0}, {0, 1}, {0, 2}, {1, 0}, {1, 1}, {1, 2} };

void vertices(const std::string& input, Vertices& vs)
{
    auto ci = input.begin();
    while(ci != input.end())
    {
        if((*ci == '0') && (*(ci + 1) == '0'))
        {
            for(int i = 0; i < 40; ++i)
            {
                vs[i] += (1 + i % 2);
            }
        }
        else
        {
            int r = *ci - '0';
            int t = *(ci + 1) - 'a';
            for(auto di = std::begin(ds); di != std::end(ds); ++di)
            {
                ++vs[(r - (*di)[0]) * 40 + (t * 2 + r - 1 + (*di)[1]) % 40];
            }
        }
        advance(ci, 2);
    }
}

std::string solve(const std::string& input)
{
    Vertices vs;
    vertices(input, vs);
    int count = std::accumulate(vs.begin(), vs.end(), 0, [](int a, const std::pair<int, int>& v) { return (v.second == 1) ? (a + 1) : a; });
    return std::to_string(count);
}

// 以下テスト実施用コード

void test(const std::string& input, const std::string& expected)
{
    std::string actual = solve(input);
    if(actual == expected)
    {
        std::cout << ".";
    }
    else
    {
        std::cout
          << "\ninput:    " << input
          << "\nexpected: " << expected
          << "\nactual:   " << actual
          << "\n";
    }
}

int main(int, char* [])
{
    test("1a2t3s2s", "11");
    test("1a1c1d00", "22");
    // 中略

    std::cout << std::endl;

    return 0;
}
```

## Ruby 三度び

C++ の `std::map` で頂点を求めるたびに個数を数えるという方法は、Ruby でも `Hash` を使えば同じことができるので、もう一度 Ruby に翻訳してみました。`test` 以下は同じなので、`solve` のみです。

```rb
def solve(input)
  input
    .chars
    .each_slice(2)
    .each_with_object(Hash.new(0)) {|(r, t), a|
      r, t = [r, t] == ['0', '0'] ? [0, 0] : [r.to_i, t.ord - 'a'.ord]
      if [r, t] == [0, 0]
        40.times {|i| a[[0, i]] += (1 + i % 2) }
      else
        [0, 1].product([0, 1, 2]).each {|dr, dt| a[[r - dr, (t * 2 + r - 1 + dt) % 40]] += 1 }
      end
    }
    .select {|k, size| size == 1}
    .size
    .to_s
end
```