酒と泪とRubyとRailsと

Ruby on Rails と Objective-C は酒の肴です!

アルゴリズムの勉強: 三目並べ ◯x問題の正誤判定[AOJ 0066][Ruby/Python/c++]

引き続きプログラミングの基礎体力づくりと、Python/c++の勉強を兼ねてアルゴリズムを勉強中です。今回は『三目並べ ◯x問題の正誤判定』について勉強しました。AIZU Online Judgeで対応している問題は、『Tic Tac Toe』です。 pubyやpythonならほんとうに簡単に解けてしまうんですが、c言語のポインタで死ぬほどハマって、最終的に諦めました。やっぱりポインタの概念をちゃんと理解しないと!


サンプル問題(AOJ)

Tic Tac Toe
Aizu Online Judge。メモされた文章を読み込んで、その中にある数字を合算した結果の「暗証番号」

Rubyのサンプルソース

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
def judge(a,b,c)
  if a == b && b == c && a != 's'
    return a
  else
    return nil
  end
end

while gets
  s = $_.chomp.chars
  res = nil
  0.upto(3) do |i|
    res = judge(s[i], s[i+3], s[i+6])
    break if res
    res = judge(s[3*i], s[3*i+1], s[3*i+2])
    break if res
  end
  if s[4] != 's' and (judge(s[0], s[4], s[8]) or judge(s[2], s[4], s[6]))
    puts s[4]
  elsif res.nil?
    puts 'd'
  else
    puts res
  end
end

Pythonのサンプルソース

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def judge(a, b, c):
  return a if a == b == c and a != 's' else 0

while True:
  try:
    s = raw_input()
    for i in range(3):
      result = judge(*s[i:9:3])
      if result: break
      result = judge(*s[3*i:3*i+3])
      if result: break
    else:
      result = s[4] if s[4] != 's' and (judge(*s[0:9:4]) or judge(*s[2:7:2])) else 'd'
  except:
    break
  print result

c++のサンプルソース

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <iostream>
using namespace std;

int abs(int x) {
  return x >= 0 ? x : (-1)*x;
}

int judge(char *s) {
  int map[3][3];
  for( int i=0; i<9; i++) {
      if(s[i]=='o') map[i%3][i/3] = 1;
      if(s[i]=='x') map[i%3][i/3] = -1;
      if(s[i]=='s') map[i%3][i/3] = 0;
  }

  int sum[8];
  for(int i = 0; i < 8; i++) { sum[i] = 0; }
  for(int i = 0; i < 3; i++) {
    sum[0] += map[i][i];
    sum[1] += map[i][2-i];
    sum[2] += map[0][i];
    sum[3] += map[1][i];
    sum[4] += map[2][i];
    sum[5] += map[i][0];
    sum[6] += map[i][1];
    sum[7] += map[i][2];
  }

  if(abs(sum[0])==3) return sum[0]/3;
  if(abs(sum[1])==3) return sum[1]/3;
  if(abs(sum[2])==3) return sum[2]/3;
  if(abs(sum[3])==3) return sum[3]/3;
  if(abs(sum[4])==3) return sum[4]/3;
  if(abs(sum[5])==3) return sum[5]/3;
  if(abs(sum[6])==3) return sum[6]/3;
  if(abs(sum[7])==3) return sum[7]/3;
  return 0;
}

int main() {
    int res;
    char str[10];
    while(cin >> str) {
        res = judge(str);
        cout << (res != 0 ? ( res > 0 ? "o" : "x" ) : "d") << endl;
    }
    return 0;
}

Aizu Online Judgeのサンプルソース

当面はAOJを解きながら、アルゴリズムの再勉強をしていくつもりです。Ruby/PythonでのAOJの回答は下のリポジトリに保存しておきます。もしツッコミとかあれば是非^^

morizyun/aoj-ruby-python - GitHub

最近解いたAOJの問題

AOJタグのついた最近解いた問題一覧

おすすめの書籍