練習メモ: Cryptarithm Solver

Posted on One min read

虫食い算を解くツールを書いてみた。 制約プログラミングの練習をしたかったのでGoogle OR-Toolsを使った。 Dockerイメージを公開したので簡単に使えるはず。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

$ docker run masumi/cryptarithm-solver
NAME
    main.py

SYNOPSIS
    main.py COMMAND

COMMANDS
    COMMAND is one of the following:

     server
       start `cryptarithm solve` server with `/docs`

     solve
       solve cryptarithm problem

こんな感じで解いてくれる。

1
2
3
4
5

$ docker run -it masumi/cryptarithm-solver solve 'SEND + MORE = MONEY'

Problem: SEND + MORE = MONEY
O=0 Y=2 N=6 E=5 S=9 D=7 R=8 M=1
('OPTIMAL', [{'O': 0, 'Y': 2, 'N': 6, 'E': 5, 'S': 9, 'D': 7, 'R': 8, 'M': 1}])

制約プログラミングに慣れるのだけが目的だったけどなんだかんだ教育的でいい練習になった。

それぞれ必要になったときに読むべきリファレンスへのリンクは貼ってる。

ちょっとした感想

FastAPI, Python-Fireはそれぞれドキュメント付きOpenAPIサーバ、コマンドラインツールを簡単に作れる。 メンテナンスもされているし機能が小さい。特別な理由がなければPythonで実装するときはこれを使ってしまうのが早そう。

FastAPIはマイクロフレームワークを目指してる。 けれどTutorial User Guide, Advanced User Guideを眺めるとCORS,OAuth2,WebSockets,GraphQLと必要なことはだいたいできる。 Flaskのように肥大化しないで維持して欲しい。

FastAPIを使ってKafkaに繋いでるひともいた。(ほかにも)

問題文を解析するために ast,token,parser などのモジュールを作ったところPython-Fireがクラッシュした。 どうやら fire が渡したクラスを解析していてその際に使っているモジュールと衝突していそうだった。 そんなバカなって思ったけどログはそんな感じでモジュール名を変えたら避けられた。 小さい再現コードを作ってIssueを切りたい。その前に既知のバグなのか仕様なのかの確認をしないとだ。

mypyはDialyzerより気軽に使える。 PEPを久しぶりに読んだ。特に大事なのは下の3つ。

そもそもパッケージ化してないので、パッケージ化する際にはPEP 561対応したい。

Courseraに離散最適化のコースがあったのでとりあえず入ってみた。 いま英語と競プロと使えるライブラリ増やす月間とk8sとCoursera機械学習と子育てで死んでるのでどうなるんだろ。。 ざっと下を眺めつつ競プロと離散最適化コースは同じトレーニングとして頑張ろう。(同じ扱いにしてもやってみたいことの量は減らない)

comments powered by Disqus