PyScriptを使って、時刻を動的に表示してみます。
動的な表示をするためにはまずimport asyncioと宣言しasyncioライブラリをインポートしておきます。
次に動的に動かしたい関数（今回はfoo関数）にasyncという修飾子をつけます。
foo関数内では、繰り返したい処理をwhile True配下に記載します。
今回は、時刻を取得しそれをoutputDiv2とoutputDiv3に反映しています。
またawait asyncio.sleep(1)を使って、１秒待ってから実行するようにしています。
[ソースコード]
1 | <html> |
[ブラウザ表示]
ブラウザ上に時刻が１秒ごとに更新される（動的に表示される）ことを確認できました。
PyScriptではイベント処理を行うことができます。
今回は、赤・白・黄を選択するラジオボタンを表示し、どのボタンが選択されているかを確認してみます。
イベント処理を行うためには、まずfrom pyodide.ffi import create_proxyを宣言します。
次にイベントが発生した際に呼び出される関数(select_color関数)を定義します。
この関数内では、Html上のコンポーネントから情報を読み取り、その情報を表示しています。
Html上のコンポーネントはjs.document.getElementsByName関数を使って取得し、取得した各コンポーネントに対してaddEventListener関数を使ってイベントリスナーを設定します。
このaddEventListener関数の第１引数にはイベントの種類を設定し、第２引数にはcreate_proxy関数で作成したプロキシを設定します。
なおcreate_proxy関数の第１引数には最初に定義したselect_color関数を指定しています。
[ソースコード]
1 | <html> |
[ブラウザ表示]
選択肢の色をクリックするたびにイベントが発生し、選択された色についてはele.checkedがTrueとなっていることが確認できました。
PyScriptでライブラリを使用するときには、py-config タグを使います。
例えば matplotlib と pandas を使用するためには、下記のように記述します。
1 | <py-config> |
使用するライブラリをpy-configタグで宣言することにより、py-scriptタグ内でそのライブラリをインポートすることができるようになります。
下記のサンプルコードでは、CSVファイルをダウンロードし、pandasライブラリを使ってそのCSVファイルを読み込み、matplotlibライブラリを使って棒グラフを描画しています。
[ソースコード]
1 | <html> |
[ブラウザ表示]
上記のようにブラウザ上に、棒グラフを描画することができました。
PyScriptを使うと、Htmlの中でPythonのコードを実行することができます。
インストール等は必要ありませんが、HTML読み込み時にランライムのロードやコンポーネントの初期化処理があるため数秒待つ必要があります。
「Hello, World!」を表示するサンプルを作成します。
PyScriptを実行するためには、HTMLのヘッダー部に次の２行を追加します。
1 | <link rel="stylesheet" href="https://pyscript.net/latest/pyscript.css" /> |
Pythonコードは、py-scriptタグの間に記載します。（7～9行目）
[ソースコード]
1 | <html> |
[ブラウザ表示]
ブラウザ上に、Pythonコードのprintで表示した文字列‘Hello, World!’を表示することができました。
$ n $ 種類の品物があり、 $ i $ 番目の品物は $ a_i $ 個あります。
異なる種類の品物同士は区別できますが、同じ種類の品物同士は区別できません。
これらの品物の中から $ m $ 個選ぶ組み合わせの総数を求めて下さい。
[制約]
🔹$ 1 \leqq n \leqq 1000 $
🔹$ 1 \leqq m \leqq 1000 $
🔹$ 1 \leqq a_i \leqq 1000 $
重複なく数え上げるために、同じ種類の品物を一度に処理します。
漸化式を次のように定義します。
$$ dp[i+1][j] := i 番目までの品物からj個選ぶ組み合わせの総数 $$
$ i $ 番目までの品物から $ j $ 個選ぶためには、$ i - 1 $ 番目までの品物から $ j - k $ 個選んで、$ i $ 番目の品物を $ k $ 加えればよいので
$$ dp[i+1][j] = \sum_{k=0}^{min(j,a[i])}dp[i][j-k] $$
という漸化式が成り立ちます。
この漸化式は計算量が $ O(nm^2) $ となりますが、
$$ \sum_{k=0}^{min(j,a[i])}dp[i][j-k] = \sum_{k=0}^{min(j-1,a[i])}dp[i][j-1-k]+dp[i][j]-dp[i][j-1-a_i] $$
であるので、
$$ dp[i+1][j]=dp[i+1][j-1] + dp[i][j]-dp[i][j-1-a_i] $$
と変形することができ、計算量は$ O(nm) $ となります。
[Google Colaboratory]
1 | #--------- 入力例 ---------- |
[実行結果]
解： 6
[1 2 0]、[1 1 1]、[1 0 2]、[0 2 1]、[0 1 2]、[0 0 3]の６パターンあるので、解は6となります。
$ n $ 個の品物を、$ m $ 個以下に分割する方法の総数を求めて下さい。
n の m 分割 $ a_i ( \sum_{i=1}^{m}a_i=n ) $ を考えてみます。
全ての $ i $ で $ a_i > 0 $ ならば、$ {a_i - 1} $ は $ n - m $ の $ m $ 分割となります。
また、$ a_i = 0 $ となる $ i $ が存在したら、これは $ n $ の $ m - 1 $ 分割となります。
したがって、次のような漸化式を立てることができます。
$$ dp[i][j] = dp[i][j - i] + dp[i - 1][j] $$
この漸化式ならば重複なく分割数を数え上げることができ、計算量は $ 0(mn) $ となります。
[Google Colaboratory]
1 | #--------- 入力例 ----------- |
[実行結果]
解： 4
4個の品物を3分割以下にする方法は、[1 1 2]、[1 3]、[2 2]、[4]の４パターンあるので、解は4となります。
数学的な演算を簡単にするのに逆ポーランド記法があります。
逆ポーランド記法では、「1 + 2」という書き方を「1 2 +」というように演算子を数字の後ろに記述します。
逆ポーランド記法で表現されたものはスタックで処理しやすいという特徴があります。
先頭から順に読み込んで、数であればスタックに積み、演算子であればスタックから値を２つ取り出して計算した結果をまたスタックに積む、という操作を繰り返すだけで計算ができます。
「4 * (8 + 2) - (3 -1) * 4」という数式を逆ポーランド記法で表現すると「4 8 2 + * 3 1 - 4 * -」となります。
これを計算するソースコードは次のようになります。
[Google Colaboratory]
1 | def calc(s): |
[実行結果]
[] [4] [4, 8] [4, 8, 2] [4, 10] [40] [40, 3] [40, 3, 1] [40, 2] [40, 2, 4] [40, 8] 解： 32
解は 32 となり「4 * (8 + 2) - (3 -1) * 4」の計算結果として正しいことが確認できます。
A*（エースター）アルゴリズムは、ダイクストラ法を発展させたアルゴリズムで、ゴールから遠ざかるような無駄な経路は探索しないように工夫することで処理を高速化します。
ゴールから遠ざかっていることを判断するため、現在値からゴールへのコストの推定値を考えます。
今回はコストの推定値として、マンハッタン距離が与えられているものとします。（21行目）
マンハッタン距離は、各座標の差の絶対値を使うためどの経路でも同じ距離が得られます。
[Google Colaboratory]
1 | import heapq |
[実行結果]
解： [0, 5, 6, 10, 13, 7]
A*（エースター）アルゴリズムを使って最短経路を求めることができました。
前回は３目並べをランダムでプレイするコードを実装しました。
今回はミニマックス法を使って３目並べをプレイしてみます。
ミニマックス法は相手が自分にとって最も不利になる手を指すと仮定して、最善の手を探す方法です。
相手が手番の場合は選択できる手の中から最も評価値の高い手を選び、自分が手番の場合は選択できる手の中から最も評価値の低い手を選びます。
ゲームの評価値としては、勝てば $ 1 $ ポイント、負ければ $ -1 $ ポイント、引き分けであれば $ 0 $ ポイントとします。（minmax関数）
[Google Colaboratory]
1 | goal = [0b111000000, 0b000111000, 0b000000111, # 横に３つ並んだケース |
[実行結果]
選択可能なマス目 [0, 1, 2, 3, 4, 5, 6, 7, 8] マス目の評価値 [0, 0, 0, 0, 0, 0, 0, 0, 0] 選択するマス目 0 ---------------------------- 選択可能なマス目 [1, 2, 3, 4, 5, 6, 7, 8] マス目の評価値 [-1, -1, -1, 0, -1, -1, -1, -1] 選択するマス目 4 ---------------------------- 選択可能なマス目 [1, 2, 3, 5, 6, 7, 8] マス目の評価値 [0, 0, 0, 0, 0, 0, 0] 選択するマス目 1 ---------------------------- 選択可能なマス目 [2, 3, 5, 6, 7, 8] マス目の評価値 [0, -1, -1, -1, -1, -1] 選択するマス目 2 ---------------------------- 選択可能なマス目 [3, 5, 6, 7, 8] マス目の評価値 [-1, -1, 0, -1, -1] 選択するマス目 6 ---------------------------- 選択可能なマス目 [3, 5, 7, 8] マス目の評価値 [0, -1, -1, -1] 選択するマス目 3 ---------------------------- 選択可能なマス目 [5, 7, 8] マス目の評価値 [0, -1, -1] 選択するマス目 5 ---------------------------- 選択可能なマス目 [7, 8] マス目の評価値 [0, 0] 選択するマス目 7 ---------------------------- 選択可能なマス目 [8] マス目の評価値 [0] 選択するマス目 8 ---------------------------- 引き分け ['0b10011100', '0b101100011']
結果は引き分けとなりました。
３目並べでは両者が最善の手を選べば、確実に引き分けになります。
３目並べは、３×３のマス目に〇と×を交互に書いて、縦・横・斜めのいずれかに３つを並べたほうが勝ちとなるゲームです。
ビット演算を使って３目並べを実装してみます。
先手と後手を別々の変数で保持します。
また、２進数の各桁を９か所のマスに割り当てます。
縦３マス、横３マスを２進数の１次元配列に対応づけると、空いているマスは先手と後手の変数に対してOR演算を行うと簡単にチェックできます。
（すべてのマスが埋まっていると、OR演算の結果として全てのビットが1になります。）
勝負の判定は、同じ記号が３つ並んだ場合で行うため、３つ並んだパターンを事前に用意しておきます。（goal変数）
このパターンとAND演算を行った結果が、パターンと同じであれば３つ並んだと判定できます。（check関数）
プレイ方法として、コンピュータ同士の対戦で、マス目の空いているところにランダムに置いていくことにします。
（実行するたびに結果が変わります。）
空いている場所（マス目）は、現在の盤面（双方のOR演算した結果）に対して１桁ずつAND演算を行い、0となったものを探します。（28行目）
[Google Colaboratory]
1 | import random |
[実行結果（勝負がつく場合）]
勝負あり ['0b10101000', '0b1000111']
下段が３つ並んでいるので勝負がついています。
[実行結果（引き分けの場合）]
引き分け ['0b10100101', '0b101011010']
全てのマスが埋まっていて、３つ並んでいる箇所がないため引き分けとなります。