![プログラミング]()
![Polygon]()
プログラミング
4200000000Hzでゴリ押す！！！(2)
今回はアルゴリズムとCPUのパワーでパズルを全力で解きます。
Exponential Idle（Android版 / iOS版）というクリッカー系放置ゲーム中のミニゲームである、矢印パズルを攻略します。
こちらのnoteの記事にめっちゃ影響を受けて書くことにしました。
と言っても、初級と中級は私でも頑張れば解けたのと、上級も先行研究があるので、エキスパートに絞って話を進めていきます（まあ上級も同じプログラムをちょちょっといじれば簡単に解けますが）。訂正とお詫び前回のサムネイルの一部に「♪ラデツキー行進曲（1.5倍速）」とありましたが、正しくは1.543倍速です。謹んでお詫び申し上げます。ルール説明（エキスパート）図1：矢印パズル（エキスパート）のルール六角格子状に並べられたタイルをタップすると、そのタイルを含む周囲（最大）7個のタイルがそれぞれ時計回りに60°回転します。
それを繰り返してすべてのタイルの向きを上向きに揃える、というルールです。目標盤面を入力として受け取り、各タイルのタップ回数を出力する。基本の考え方1回タップすることに60°回転するので、6回同じ場所をタップすれば盤面の状態は変わらず、加法巡回群をなすような6元集合、$\mathbb{Z}/6\mathbb{Z}$ を持ってくる。解法案1参考文献[3]と同様に、$\mathbb{Z}/6\mathbb{Z}$ 上の37次の線形方程式を解くことに帰着させる方法です。が。
聡明な読者の方ならお気づきでしょう。$\mathbb{Z}/6\mathbb{Z}$ は体でしょうか。2,3,4は乗法逆元を持たないので体ではないですね。
すると線形方程式を解くときに除法が使えないということになり、掃き出し法は使えないことになります（ピボットを1にできないだけで掃き出せないわけではないだろうが、一般的なアルゴリズムをそのまま持ってくるのは厳しそう）。2掃き出しで解けない（難しい）と言っても、元は有限個しかないので $6^{37}=6.2 \times 10^{28}$ 通りすべてを試してしまえという考え方。猿。
いや無理やけど。もし1パターンを1nsで検証できたとしても6.2e19 s掛かります。実際は1パターンの検証で約7x37回の足し算をすることになるのでもっとかかります。
imos法で最適化すればどうにかなるようなレベルの話ではないです。やるだけ無駄。3大本命。DFSです。DFS自体は木の全探索なのですが、探索の必要がない部分を枝刈りすればだいぶ計算量が減ります。どれぐらい絞れるかは後述。
今回はこれを採用。プログラムこれが解を探索するプログラムです。
入力の数字は、ディスプレイモードを数字にして表示された数字ということになっています（内部的には-1して持っているが）。#include <iostream>
#include <vector>
#include <tuple>
#include <algorithm>
using index_t = std::tuple<int, int>;
using board_t = std::vector<std::vector<int>>;
const int mod = 6;
const size_t board_row = 7, board_col = 7;
void dfs(board_t &board, board_t &hands, index_t index);
void flip_around(board_t &board, index_t index, int amount);
index_t next(index_t index);
bool is_in_board(index_t index);
void print_board(const board_t board);
const index_t end_index = next({ 6, 6 });
int main() {
board_t board(board_row, std::vector<int>(board_col));
board_t hands(board_row, std::vector<int>(board_col));
for (index_t i = { 0, 0 }; i != end_index; i = next(i)) {
const auto [r, c] = i;
std::cout << r << " " << c << ": " << std::flush;
std::cin >> board[r][c];
board[r][c]--;
}
dfs(board, hands, { 0, 0 });
return 0;
}
void dfs(board_t &board, board_t &hands, index_t index) {
if (index == end_index) {
print_board(hands);
exit(0);
return;
}
auto [r, c] = index;
// 右端辺での枝刈り
if (c == 6 && r > 3 && board[r - 1][c - 1] != board[r - 1][c]) {
return;
}
// 下端辺での枝刈り
if (r == 6 && c > 3 && board[r - 1][c - 1] != board[r][c - 1]) {
return;
}
// 上端、左端辺以外での枝刈り
if (r != 0 && c != 0) {
// 左上マスを0にするように動かす
const int hand = (mod - board[r - 1][c - 1]) % mod;
hands[r][c] = hand;
flip_around(board, index, hand);
dfs(board, hands, next(index));
flip_around(board, index, mod - hand);
} else {
for (int hand = 0; hand < mod; hand++) {
hands[r][c] = hand;
flip_around(board, index, hand);
dfs(board, hands, next(index));
flip_around(board, index, mod - hand);
}
}
}
void flip_around(board_t &board, index_t index, int amount) {
// 正体不明だがちゃんと最初だけ初期化処理が走る
static std::array<index_t, 7u> dpos{
dpos[0] = { -1, -1 },
dpos[1] = { -1, 0 },
dpos[2] = { 0, -1 },
dpos[3] = { 0, 0 },
dpos[4] = { 0, 1 },
dpos[5] = { 1, 0 },
dpos[6] = { 1, 1 }
};
const auto [r, c] = index;
for (const auto [dr, dc] : dpos) {
if (!is_in_board({ r + dr, c + dc })) continue;
board[r + dr][c + dc] += amount;
board[r + dr][c + dc] %= mod;
}
}
index_t next(index_t index) {
auto [r, c] = index;
if (c == 6 || c - r >= 3) {
r++;
c = std::max(r - 3, 0);
} else {
c++;
}
return { r, c };
}
bool is_in_board(index_t index) {
auto [r, c] = index;
return std::abs(r - 3) <= 3 && std::abs(c - 3) <= 3 && std::abs(c - r) <= 3;
}
void print_board(const board_t board) {
for (size_t i = 0; i < board_row; i++) {
for (size_t j = 0; j < board_col; j++) {
if (is_in_board({ i, j })) {
std::cout << board[i][j] << " ";
} else {
std::cout << " ";
}
}
std::cout << "\n";
}
std::cout << std::endl;
}
こんなに const とか & とか書くんだったら最初からRustでやればよかったなと若干の後悔。
ぼちぼち解説していきます。
まずここ。using index_t = std::tuple<int, int>;
using board_t = std::vector<std::vector<int>>;index_t というエイリアスに std::tuple<int, int> を当てています。
index_t index = {row, column}; となっているならば、index は、row 行 column 列のパネルの位置を表します。
board_t には std::vector<std::vector<int>> を当てていますが、
board_t board(R, std::vector<int>(C)); としたならば、board は、R 行 C 列のパネルの二次元配列を表します。（入力と）パネルの現状態と出力する手数に使います。
図2：indexの指し方
次はここ。index_t next(index_t index) {
auto [r, c] = index;
if (c == 6 || c - r >= 3) {
r++;
c = std::max(r - 3, 0);
} else {
c++;
}
return { r, c };
}next関数はその名の通り、次に探索する（タップ回数を決定する）点を決定する関数で、DFSでの探索順に直接関わってきます。
定義はまあ見りゃわかりますね（ifの条件に c - r >= 3 とか書いてあるが、これは条件をいっぱい書きたくなかったからうまいこと纏めてあるだけ）。
2行目の auto [r, c] = index; ってのは構造化束縛というC++17以降で追加された機能です。分割代入だと思って大体問題ありません。
一応探索順を図に示しておくとこうです。図3：DFSの探索順この順序にしているのは、単純に分かりやすいという以外にもう一点理由があって、枝刈りがしやすいという点。
枝刈りの方法はdfs関数を見ればわかります。
void dfs(board_t &board, board_t &hands, index_t index) {
if (index == end_index) {
print_board(hands);
exit(0);
return;
}
auto [r, c] = index;
// 右端辺での枝刈り
if (c == 6 && r > 3 && board[r - 1][c - 1] != board[r - 1][c]) {
return;
}
// 下端辺での枝刈り
if (r == 6 && c > 3 && board[r - 1][c - 1] != board[r][c - 1]) {
return;
}
// 上端、左端辺以外での枝刈り
if (r != 0 && c != 0) {
// 左上マスを0にするように動かす
const int hand = (mod - board[r - 1][c - 1]) % mod;
hands[r][c] = hand;
flip_around(board, index, hand);
dfs(board, hands, next(index));
flip_around(board, index, mod - hand);
} else {
for (int hand = 0; hand < mod; hand++) {
hands[r][c] = hand;
flip_around(board, index, hand);
dfs(board, hands, next(index));
flip_around(board, index, mod - hand);
}
}
}私もそこまでアホではないし、この関数は深い再帰を伴うので引数の大部分は参照で受けるようにしました。
部のC#erの皆さんが卒倒するかもしれませんが、vector<T>は値型です。というか、C/C++に値型・参照型という分け方はありません。
明示しない限り常にすべて値渡しになるので、ちゃんと参照渡しになるよう指定してやります。
さておき、枝刈りの話。これも図に示したほうが早いでしょう。図4：dfs関数の枝刈り図3に示した探索順から分かるように、27,32,36のノードでは、そのノードを操作した後は左上と真上の変化がないので、その2箇所の状態は必ず同じでなければならず、そうでなければ後退して探索し直すことになります。34,35,36でも左上と左下で同じことが起こります。
また図3から分かるように、ある時点で探索しているパネルの左上にパネルがあったとき、探索しているパネルを動かした後に再び左上のパネルが変わることはないので、左上は0にならなくてはなりません。よって左上のパネルを元にただ一通りに決まります。逆に言えば、0～5の中から自由に選べるのは左上にパネルが存在しない0,1,2,3,4,9,15のたった7個のパネルのタップ回数のみです。したがって、検証の必要なパターン数は $6^7 \approx 10^{5.45}$ 通りだけになります（ただし、関数呼び出し自体が重いことと、これらの点の不正性が分かるまでに再帰の深いところに潜ることがあるのでやはりある程度計算に時間はかかる）。
こんな感じで殆どの点で枝刈りが行えることがわかりますね。
if (index == end_index) {
print_board(hands);
exit(0);
return;
}で、最後36番が終わればここの分岐にたどり着いて終わりです（なんでこの人exitとreturn両方書いてるんだろう）。
でも図4を見てもらえばわかりますが、36番ノードだけチェックが入ってないんですよね。
これでいいのかと言われれば良くて、解が存在するならば、36番ノードだけが非0であることはありません。
流石に解が存在しない問題は生成されないだろうということでここは一つ。
flip_around(board, index, hand);
dfs(board, hands, next(index));
flip_around(board, index, mod - hand);ところでこの部分ですが、再帰DFSにおける常套手段です。
ある変換（ここではある1パネルをn回タップすること）が可逆であるならば、dfs呼び出しから帰ってきた後に逆変換（ここでは同じパネルを6-n回タップすること）を行えばうまいことDFSになります。是非覚えておいてください。
以上。閑話void flip_around(board_t &board, index_t index, int amount) {
// 正体不明だがちゃんと最初だけ初期化処理が走る
static std::array<index_t, 7u> dpos{
dpos[0] = { -1, -1 },
dpos[1] = { -1, 0 },
dpos[2] = { 0, -1 },
dpos[3] = { 0, 0 },
dpos[4] = { 0, 1 },
dpos[5] = { 1, 0 },
dpos[6] = { 1, 1 }
};
...
}この部分、何ですか。自分で書いたけどどういう理屈で初期化されているのかわかりません。C++プロの方、教えて下さい。
aggregateならメンバ名を指定して初期化する方法があるけど、その延長と考えていいんですかね。参考文献[1]Conic Games「Exponential Idle - Google Play のアプリ」<https://play.google.com/store/apps/details?id=com.conicgames.exponentialidle>
[2]Gilles-Philippe Paille「「Exponential Idle」をApp Storeで」<https://apps.apple.com/jp/app/exponential-idle/id1538487382>
[3]ちゃそ「Exponential Idle #2 矢印パズル攻略法（と二元体GF(2)上の線形方程式について）」<https://note.com/so_ra_64/n/n9c2eb6a5ef6f>
[4]ますたー。/繰り上げP「焼き甜花ちゃんシリーズの作り方＆素材」<https://www.nicovideo.jp/watch/sm37861810>
[5]いもす研「いもす法」<https://imoz.jp/algorithms/imos_method.html>
![>]()
内容を見る
![プログラミング]()
![Polygon]()
プログラミング
LaravelをCloud Runにデプロイして効率よくバックエンドを開発しよう！
何円ぐらいで済むの?
以下の手順で60.77時間、動かしてみました。リージョンは全て東京(asia-northeast1)です。
結果MySQL 実行: 97円MySQL ストレージ: 11円ストレージ(NA-APAC間の通信): 5円以上、113円でした。
一時間1.85円として計算すると、1ヶ月で1338円になります。
お詫びすいません、ケチれませんでした！！！！！
ただ、GitHubからデプロイすることで効率の良い開発スケール他GCPサービスとの円滑な連携が可能になる点は見逃せません。余裕のある方は試してみてください。
下準備GCPのセットアップgcloud CLIをインストールしておく。環境によって手順が異なるので省略。
プロジェクトを作り、支払いアカウントを紐づける。
gcloud auth loginまずはログインする。
PROJECT_NAME=(表示上のプロジェクトネーム)
PROJECT_ID=$(gcloud projects list --format 'value(projectId)' --filter name=$PROJECT_NAME)
export PROJECT_ID
gcloud config set project $PROJECT_ID
gcloud services enable \
containerregistry.googleapis.com \
cloudresourcemanager.googleapis.com \
iam.googleapis.com「表示上のプロジェクトネーム」はGCPの画面に出ているプロジェクト名。プロジェクトをセットし、APIを有効化する。
Terraformのインストールいつか使うんだろうなーと思っていた。入れてなかったのでここで入れておく。
brew install tfenv
tfenv install 0.12.6
tfenv use 0.12.6tfenvを使うのは、以下のテンプレートが0.12.6を想定していたから。随時変更しよう。
ステップ1. テンプレートを準備自分でやろうとしたがあまりにめんどくさかったので、以下のテンプレートを使う。
https://github.com/villers/laravel-cloud-run-sql
これをフォークしよう。
クローンしてビルドgit clone git@github.com:あなたのユーザー名/laravel-cloud-run-sql.git
cd laravel-cloud-run-sql
docker-compose build
euをasiaに東京で動かすので、レポジトリ内のeu.gcr.ioをasia.gcr.io に置換。
ローカルで試すdocker-compose up
起動の様子。なんでもDockerでやれば、なんかすごいことやってるみたいに見える。
docker-compose run --rm app php artisan migrate --seed
マイグレーションする。
http://localhost:8080/ で動作確認しよう。
ステップ2. GCPにコンテナをアップするサービスアカウントを用意するサービスアカウントを作り、Owner権限を与える。キーをダウンロードしてterraform-key.json として保存し、環境変数に設定、サービスアカウントとして認証する。それらが以下のコマンドでできる。ありがとうgcloud CLI!
gcloud iam service-accounts create deployer \
--display-name "Terraformのサービスアカウント"
gcloud projects add-iam-policy-binding ${PROJECT_ID} \
--member serviceAccount:deployer@${PROJECT_ID}.iam.gserviceaccount.com \
--role roles/owner
gcloud iam service-accounts keys create ~/terraform-key.json \
--iam-account deployer@${PROJECT_ID}.iam.gserviceaccount.com
export GOOGLE_APPLICATION_CREDENTIALS=~/terraform-key.json
gcloud auth activate-service-account --key-file=$GOOGLE_APPLICATION_CREDENTIALS
ビルド(M1注意)export SERVICE_NAME=laravel-app-service
docker build --platform linux/amd64 -f .cloud/docker/php/Dockerfile -t asia.gcr.io/${PROJECT_ID}/${SERVICE_NAME} .
上記コマンドでアジア用タグをつけたイメージをビルドする。間違ったタグをつけたりしたら、docker images からのdocker rmi [ID] で消せる。それか、Docker Desktopのイメージ画面を使う。
--platform linux/amd64 はM1用。ARMでビルドしてもデプロイで死ぬ。このせいで数時間が無駄になった。
レジストリにプッシュgcloud auth configure-docker
docker push asia.gcr.io/${PROJECT_ID}/${SERVICE_NAME}コンテナレジストリにログインして、さっきのをプッシュする。
ステップ3. 自動でCloud SQLとLaravelをデプロイTerraform初期化cd .cloud/terraform
terraform init
ついに初回デプロイexport REGION=asia-northeast1
export INSTANCE_NAME=laravel-app-service
terraform apply \
-var "region=${REGION}" \
-var "service=${SERVICE_NAME}" \
-var "project=${PROJECT_ID}" \
-var "instance_name=${INSTANCE_NAME}"
Do you want to perform these actions?
Terraform will perform the actions described above.
Only 'yes' will be accepted to approve.
Enter a value:
yesと打てば、Secret Managerでキーを作り`laravel`というサービスアカウントができCloud SQLにMySQLをセットアップCloud RunでLaravelをデプロイの4つが行われる。
Cloud SQLの部分でかなり時間がかかる。
Apply complete! Resources: 26 added, 0 changed, 0 destroyed.
Outputs:
result = The laravel-app-service is now running at https://<ここにURL>
If you haven't deployed this service before, you will need to perform the initial database migrations:
cd ../..
gcloud builds submit --project <ここにプロジェクトID> --config .cloudbuild/build-migrate-deploy.yaml \
--substitutions _APP_ENV=dev,_APP_DEBUG=true,_REGION=asia-northeast1,_INSTANCE_NAME=laravel-app-service,_SERVICE=laravel-app-service
The username and password are stored in these secrets:
gcloud secrets versions access latest --secret DATABASE_URL
✨
終わるとこんなんが出てくる。
Cloud Runの画面でもURLが確認できる。マイグレーションは後でやる。
GitHubと連動してビルド・デプロイさせる実はTerraformを使うのは初回だけでいい。あとはCloud Buildを活用しよう。
ルートにcloudbuild.yaml を作る。
cloudbuild.yamlsteps:
- id: 'build_and_push'
name: 'gcr.io/kaniko-project/executor:latest'
args:
[
# https://github.com/GoogleContainerTools/kaniko/issues/1427
"--dockerfile=.cloud/docker/php/Dockerfile",
"--cache=true",
"--cache-ttl=6h",
"--destination=asia.gcr.io/${PROJECT_ID}/${_SERVICE}",
]
- id: 'migrate'
name: 'gcr.io/google-appengine/exec-wrapper'
args: ['-i', 'asia.gcr.io/${PROJECT_ID}/${_SERVICE}',
'-s', '${PROJECT_ID}:${_REGION}:${_INSTANCE_NAME}',
'-e', 'PROJECT_ID=${PROJECT_ID}',
'-e', 'APP_ENV=${_APP_ENV}',
'-e', 'APP_DEBUG=${_APP_DEBUG}',
'--', 'php', 'artisan', 'migrate']
- id: 'deploy'
name: 'gcr.io/cloud-builders/gcloud'
args: ["run", "deploy", "${_SERVICE}",
"--platform", "managed",
"--region", "${_REGION}",
"--image", "asia.gcr.io/$PROJECT_ID/${_SERVICE}"]
options:
substitutionOption: ALLOW_LOOSE
substitutions:
_APP_ENV: prod
_APP_DEBUG: "false"
_SERVICE: laravel-app-service
_REGION: asia-northeast1
_INSTANCE_NAME: laravel-app-service
ビルドのトリガー設定を変更(重要)
次に、Cloud Runのページを開く。
このボタンでビルドのトリガーを作れる。
GitHubのレポジトリと接続すればいいが、Dockerfile は間違いなので修正が必要。
「EDIT CONTINUOUS DEPLOYMENT」から設定を開き、LocationをRepository に変える。 Cloud Build configuration file (yaml or json) を選択する。/cloudbuild.yaml になっているか確認。ブランチ名を変えた場合は、適宜トリガーの設定も変える。
プッシュすればビルド、プッシュ、マイグレーション、デプロイがされる。こちらのリンクからビルド履歴が見れる。
初回は時間がかかるが...
2回目以降はKanikoがキャッシュを活用してくれる。大体二分で終わる。
え? FTPで差分をアップした方が早い? 確かにそうかもしれない。だが、全部自動化バージョンを戻せる環境を簡単に再現という点で明らかに効率がいい。積極的に活用していこう。
![>]()
内容を見る
![プログラミング]()
![Polygon]()
プログラミング
VSCodeのVueでpropsの型チェックをする方法 (TypeScript)
注意書き
以下の内容はVSCode 1.16.2Vetur v0.35.0Nuxt v3.0.0-27252999.d2cc9e4 (Vue: 3.2.20)Next 11.1.2 (React: 17.0.2)時点の内容です。あと、当然ですが全てTypeScriptです。
Nuxt3はまだベータ版ですが、起動が早い + TypeScriptが使いやすいので皆さんも試してみてください。
Vueでpropsの型チェックをさせる方法ステップ1. Veturを入れるhttps://github.com/vuejs/vetur
これがないと話にならないです。
ステップ2. 設定を変えるなぜかデフォルトで型チェックできないので、settings.json に以下の設定を追記します。
{
(前略)
"vetur.validation.templateProps": true,
"vetur.experimental.templateInterpolationService": true,
(後略)
}
ステップ3. コンポーネントを作成する<template>
<div>
<h2>{{ name }}様</h2>
<div v-if="age">
<b>{{ age }}歳なので</b>
<span>わいの{{ age && age / 20 }}倍！</span>
</div>
</div>
</template>
<script lang="ts">
export default {
name: "TestComponent",
props: {
name: {
type: String,
required: true,
},
age: {
type: Number,
required: false,
},
},
}
</script>
name は文字列(必須)で、年齢は数値(任意)です。
「名前と年齢を受け取って、年齢があれば俺の年齢と比較する」という意味不明なコンポーネントです。
ステップ4. ページで使ってみる<template>
<div>
<TestComponent name="aaa" :age="100" />
</div>
</template>
<script lang="ts">
import TestComponent from "../components/TestComponent.vue"
export default {
components: { TestComponent },
}
</script>
こんな感じでページで使います。
できましたね。
ステップ5. エラーを起こしてみる<TestComponent name="aaa" age="100" />
試しにこう書いてみてください。
Type 'string' is not assignable to type 'number'.
Veturから怒られるはずです。なぜならage="100" が文字列の「100」を渡しているからです。
が、templateInterpolationService がまだ「experimantal」なので、エラーが出る場所がおかしいです。
ちょっと待って！Reactで書けばいいやんあのですね、なんで単なる自動補完に、拡張機能と設定がわざわざ必要なんですか?
Reactで同じことをやってみてください。何も設定がいらないです。
ステップ1. コンポーネントを書くinterface Props {
name: string;
age?: number;
}
const TestComponent: React.VFC<Props> = (props) => (
<div>
<h2>{props.name}様</h2>
{props.age && (
<div>
<b>{props.age}歳なので</b>
<span>わいの{props.age / 20}倍！</span>
</div>
)}
</div>
);
export default TestComponent;
めっちゃ短くなります。
型の定義も、ただTypeScriptのinterfaceを書けばいいのです。Vueのprops よりスッキリしていて見やすいでしょう？
Next.jsのページで使うimport TestComponent from '@/components/TestComponent';
import { NextPage } from 'next';
const TestPage: NextPage = () => (
<div>
<TestComponent name="aaa" age={100} />
</div>
);
export default TestPage;
もしage に数値以外を渡すと、その場でエラーが出ます。繰り返しますが、拡張機能や設定は必要ありません。
Vueはpropsだけで記述量が多すぎるそもそもですね、たかが「名前と年齢を出す」だけで記述量が多すぎるんですよ。
export default {
name: "TestComponent",
props: {
name: {
type: String,
required: true,
},
age: {
type: Number,
required: false,
},
},
}
これ、「nameとageを受け取る」ってだけですよ。長すぎるでしょ。
interface Props {
name: string;
age?: number;
}
const TestComponent: React.VFC<Props> = (props) => (
<div>
<h2>{props.name}様</h2>
{props.age && (
<div>
<b>{props.age}歳なので</b>
<span>わいの{props.age / 20}倍！</span>
</div>
)}
</div>
);
export default TestComponent;
さっきも書きましたけど、Reactはテンプレート自体を含めてこの長さですからね。絶対こっちの方が時間の節約になります。
以上、俺がReactを使う理由の記事でした。
---
あれ？なんの記事だったっけ？
思い出した！自動補完や！
以上、VSCodeのVueでpropsの型チェックをさせる方法でした。
![>]()
内容を見る
