ひよこになりたい

Programming Server Network Security and so on

3Dマルバツゲームの残骸

DEFCON 22 CTF Qualifications で出題された3dtttを解いてたのですが、惜しくもなく解けなかったので、途中まで組んで出来上がった残骸を放り投げておきます。

3dtttは3D Tic Tac Toe(3Dマルバツゲーム)を指定された条件で解いていく問題でした。WriteUpは __math氏のWriteUpが参考になります。

3dttt(@__math氏) - https://gist.github.com/math314/34ff1da0b4e169b1ed33

プログラム(Python3)

3Dの盤面をランダムに生成して指定した個数だけ○と×が揃っている盤面を抽出する。何かに使えるかもしれない(?)

# -*- coding: utf-8 -*-
import random

ox = ('o', 'x')

# generate 3d tic tac
def makeline():
  return [random.choice(ox), random.choice(ox), random.choice(ox)]
def makeaspect():
  return [makeline(), makeline(), makeline()]
def maketic():
  return [makeaspect(), makeaspect(), makeaspect()]

# print 3d tic tac
def printtic(tic):
  for aspect in tic:
    for line in aspect:
      print(line)
    print('')

# print aspect
#def printasp(tic):
# for aspect in tic:
#   print(aspect)

# 横チェック
def check_c(aspect):
  win = [0, 0]
  for i, c in enumerate(ox):
    win[i] += sum([1 if line.count(c) == 3 else 0 for line in aspect])
    
  return tuple(win)

# 縦チェック
def check_r(aspect):
  win = [0, 0]
  for i, c in enumerate(ox):
    win[i] += sum([1 if line.count(c) == 3 else 0 for line in list(map(list, zip(*aspect)))])
  return tuple(win)

# 斜めチェック
def check_d(aspect):
  win = [0, 0]
  for i, c in enumerate(ox):
    win[i] += 1 if [aspect[j][j]     for j in range(3)].count(c) == 3 else 0
    win[i] += 1 if [aspect[j][2 - j] for j in range(3)].count(c) == 3 else 0
  return tuple(win)

# 3Dの盤面の斜めチェック
def check_tic_d(tic):
  win = [0, 0]
  for i, c in enumerate(ox):
    if tic[0][0][0] == tic[1][1][1] == tic[2][2][2] == c:
      win[i] += 1
    if tic[2][0][0] == tic[1][1][1] == tic[0][2][2] == c:
      win[i] += 1
    if tic[0][2][0] == tic[1][1][1] == tic[2][0][2] == c:
      win[i] += 1
    if tic[2][2][0] == tic[1][1][1] == tic[0][0][2] == c:
      win[i] += 1
  return tuple(win)

if __name__ == '__main__':
  o = 4
  x = 2

  count = 0
  while True:
    if count % 10000 == 0:
      print(count)
    count += 1

    # 3D空間にランダムプロット
    tic = maketic()

    # ticのスライス1(面を変える)
    tictrans1 = []
    asptrans = []
    for i in range(3):
      for aspect in tic:
        asptrans.append(aspect[i])
      tictrans1.append(asptrans)
      asptrans = []

    # ticのスライス2(面を変える)
    tictrans2 = []
    asptrans = []
    for i in range(3):
      for aspect in tic:
        aspect = list(map(list, zip(*aspect)))
        asptrans.append(aspect[i])
      tictrans2.append(asptrans)
      asptrans = []

    # 縦横チェック (通常状態 8x3=24通り)
    chk = []
    for aspect in tic:
      chk.append(check_r(aspect))
      chk.append(check_c(aspect))
      chk.append(check_d(aspect))

    # 別の面からの判定1(縦方向への向き3x3=9通り + 斜め2x3=6通り)
    for aspect in tictrans1:
      chk.append(check_r(aspect))
      chk.append(check_d(aspect))

    # 別の面からの判定2(斜め2x3=6通り)
    for aspect in tictrans2:
      chk.append(check_d(aspect))

    # 斜め(3Dの対角線 4通り)
    chk.append(check_tic_d(tic))

    # 個数
    sumO = sum([X for X, Y in chk])
    sumX = sum([Y for X, Y in chk])

    if sumO == o and sumX == x:
      print("Found!: ({0}, {1})".format(o, x))
      printtic(tic)

出力

$ python 3dtictac.py
0
Found!: (4, 2)
['x', 'o', 'x']
['o', 'o', 'x']
['o', 'o', 'o']

['o', 'o', 'x']
['x', 'o', 'o']
['o', 'x', 'x']

['x', 'x', 'x']
['o', 'o', 'x']
['o', 'x', 'o']
.....(略)

多分あってると思う(たぶん)

競技プログラミング勢は簡単に解いていたみたい。つよい。