あいどる💖たいむ

あいどるやってます。

Scilab/Scicosはじめた

使い方が難しい(*>△<)

はたして、シュミレーションできるようになるのか?

ステップ関数の加算に成功した!

f:id:shiccocsan:20170511233309j:plain

グリッドの表示に成功した!

f:id:shiccocsan:20170511233316j:plain

abc025_c

C: 双子と○×ゲーム - AtCoder Beginner Contest 025 | AtCoder

はじめてミニマックス法の問題を解いた。 ミニマックス法 - Wikipedia

解法メモ

スコアの"最大値を目指す"と、"最小値を目指す"を交互に繰り返し、スコアの最大値を求めるってイメージ。
コード的には全探索と同じようなコードになる。
ただ、途中で同じ盤面の状態になることがあるから、一度発生した盤面でのスコア最大値はメモしておく。

コード

A = [[0] * 3 for i in range(3)]  # 盤面(0:null, 1:dai, -1,ko)
B = [list(map(int, input().split())) for _ in range(2)]
C = [list(map(int, input().split())) for _ in range(3)]


def get_key():
    return tuple(tuple(A[_]) for _ in range(3))


memo = dict()

SUM_SCORE = 0
for i in range(3):
    for j in range(2):
        SUM_SCORE += B[j][i] + C[i][j]


def score():
    res = 0
    for i in range(3):
        for j in range(2):
            if A[j][i] != A[j + 1][i]:
                res += B[j][i]
            if A[i][j] != A[i][j + 1]:
                res += C[i][j]
    return SUM_SCORE - res


def min_max(position):
    if position == 9:
        return score()

    stat = get_key()
    if stat in memo.keys():
        return memo[stat]

    res = -1e10
    sign = -1 if position % 2 else 1

    for i in range(3):
        for j in range(3):
            if not A[i][j]:
                A[i][j] = sign
                res = max(res, sign * min_max(position + 1))
                A[i][j] = 0

    memo[get_key()] = sign * res
    return sign * res


spam = min_max(0)
print(spam)
print(SUM_SCORE - spam)

リスト内包表記でタプルを作るときは、
tuple(i for i in range(3)) のように書く。
(i for i in range(3)) だとgenerator objectが返るから注意。

numpyの配列から上位n個を取得する

概要

numpy.darrayから値を比較し、上位n個を取得したい。
argsortを使えば実現できた。

環境

$ python --version
Python 3.5.1

argsortを使ってみる

argsortでソート後のindexのリストを取得できる
numpy.argsort — NumPy v1.12 Manual

In [1]: import numpy as np

In [3]: x = np.array([[0, 3, 1, 2],
   ...:        [1, 0, 2, 2],
   ...:        [4, 4, 4, 4]])
   ...:

In [4]: x
Out[4]:
array([[0, 3, 1, 2],
       [1, 0, 2, 2],
       [4, 4, 4, 4]])

# axis=0の場合(列ごとに比較するイメージ)
In [5]: np.argsort(x, axis=0)
Out[5]:
array([[0, 1, 0, 0],
       [1, 0, 1, 1],
       [2, 2, 2, 2]])

# axis=0の場合(行ごとに比較するイメージ)
In [6]: np.argsort(x, axis=1)
Out[6]:
array([[0, 2, 3, 1],
       [1, 0, 2, 3],
       [0, 1, 2, 3]])

# axisのデフォルトは-1(最後の次元)
In [7]: np.argsort(x)
Out[7]:
array([[0, 2, 3, 1],
       [1, 0, 2, 3],
       [0, 1, 2, 3]])

argsortを使って、上位2個を取得する

In [3]: np.argsort(x)[0][::-1][:2]
Out[3]: array([1, 3])

# 1つのスライスで処理するなら・・・
In [4]: np.argsort(x)[0][:-3:-1]
Out[4]: array([1, 3])

こんな感じでしょうか