ペントミノ・ソルバーをいろんな言語で書いてみる

# 概要
プログラム言語の文法はいろいろなので *Hello World* だけではその言語の特徴は把握できないですよね。
そこで、基本的な文法の理解＆比較＆備忘録として、[**ペントミノ**](https://ja.wikipedia.org/wiki/%E3%83%9A%E3%83%B3%E3%83%88%E3%83%9F%E3%83%8E)のソルバーを**20種類のプログラミング言語**で書いてみました。

どの言語も200～300行程度のコードなので全体を把握するのは難しくないと思います。

|  |  |
|:-:|:-:|
|![output.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3761186/754143bb-d744-6a9c-66a6-592c816ede53.png)| Ruby Python Lua Squirrel Julia JavaScript TypeScript Groovy Perl AWK PHP C C++ C# Java Kotlin Go Rust Swift LISP Crystal Elixir F# D Dart|

（2024/12/9： Crystal、Elixir を追加、実行速度グラフの修正）
（2025/2/10： D、Dartを追加、実行速度グラフの修正）
  

### 比較のポイント
* 関数の宣言方法：引数、返り値
* 変数の宣言方法：型指定、ローカル、グローバル、mutable/immutable
* 配列：作り方、操作メソッド、多次元
* 文字列：操作メソッド、変数埋込、複数行文字列
* 連想配列
* NULL値: null, nil, nothing, ....
* print文： 書式指定方法
* コメント文
* ブロックの書式： {} 、～ end
* for, foreach, if の構文
* 三項演算子
* lambda、closure、アロー関数
* クラス：メンバ変数、メソッド、コンストラクタ
* コマンドライン引数
* 実行時間

# プログラム

### ソースコード

[https://github.com/sense-n-react/PentominoSolvers](https://github.com/sense-n-react/PentominoSolvers) 

プログラムの特徴としては、ひたすら配列アクセスや関数呼び出しを行うものです。これだけで言語の良し悪しを評価することはできませんが、素（す）の言語の使い勝手を感じることはできると思います。

プログラム全体の処理の流れ、構成（見た目）、クラス名、関数名、変数名はできるだけ同じにしています。オブジェクト指向的な作りを心掛けましたが、*AWK、Perl、LISP* はベタな書き方で妥協しています。


### 実行方法
ソルバープログラムは個別に実行できます。表示はキャラクターベースです。
```shell-session:普通に実行
$ ruby solver.rb
+---+---------------+---+
|   |               |   |
|   +-------+   +---+   |
|           |   |       |
+-------+   +---+   +---+
|       |   |       |   |
|       +---+-------+   |
|       |           |   |
+---+   +-------+   |   |
|   |   |       |   |   |
|   +---+---+   |   |   |
|           |   |   |   |
|   +---+---+   +---+   |
|   |   |       |   |   |
+---+   +---+---+   +---+
|           |   |       |
+---+   +---+   +---+   |
|   |   |           |   |
|   +---+-------+   |   |
|               |   |   |
+---------------+---+---+ 
                            2339
```
#### 盤面のサイズ指定
デフォルトでは *`6x10`* の盤面で解を求めます。コマンドラインに *`8x8`* のように盤面のサイズを指定できます。指定可能なサイズは *`3x20`* *`4x15`* *`5x12`* *`6x10`* *`10x6`* *`12x5`* *`14x5`* *`20x3`* *`8x8`* *`4x16`* *`16x4`* のいずれかです。これ以外だと *`6x10`* として実行します。
*`8x8`* や *`4x16`* では中央に *`4x4`* のスペースを配置して解を求めます。
```shell-session:8x8を指定して実行
$ ruby solver.rb 8x8
+---+-----------+---------------+
|   |           |               |
|   +-------+   |   +-----------+
|           |   |   |           |
+-------+   |   +---+   +-------+
|       |   |   |       |       |
+---+   +---+---+---+---+   +---+
|   |       |       |       |   |
|   +---+   |       +---+   |   |
|       |   |       |   |   |   |
|   +---+---+---+---+   +---+   |
|   |   |       |           |   |
|   |   |       +---+   +---+   |
|   |   |       |   |   |   |   |
+---+   +---+   |   +---+   |   |
|           |   |           |   |
+-----------+---+-----------+---+
                                    65
```
#### *run-solver*
言語が20種類もあると言語のコマンドをいちいち覚えてられない（特にコンパイル系）ので、***run-solver*** という*Ruby*スクリプトを作りました。
ファイルの拡張子を指定すれば対応する言語のプログラムを実行します。
コンパイル系言語ではコンパイルしてから実行します。
```shell-session:拡張子（言語）を指定して実行
$ ./run-solver rb                # ruby solver.rb を実行
$ ./run-solver rb js cpp         # 複数指定可
$ ./run-solver ruby              # 言語名でもOK
$ ./run-solver --all             # 全ての言語で実行
$ ./run-solver py --size 5x12    # 5x12 を python で実行
```


# 感想

以下は、各言語に対する私の感想です。理解不足や偏見がありますのでご注意ください。

0. ***Ruby***
シンプルで一番好きです。慣れてることもあり「考えていることをそのまま書く」ことができます。特に、メソッドチェーンを使ってシンプルに書けるところが良いです。

0. ***Python***
Rubyと同程度にシンプルに書けます。が、メソッドチェーンで不自由を感じました。実行速度は意外に遅いです。内包表記や３項演算子などが他の言語と比べて独特で取っ付きにくいです。インデントも賛否両論・・・。ユーザの多さや豊富なライブラリはメリットと言えますが、言語として好みではありません。

 0. ***JavaScript***
実行速度が非常に速いので驚きました。JITの効果を体感できます。言語仕様もいい感じで癖がないと思います。let と var  の使い分けは少し億劫です。solver.js では使っていませんが、JavaScript の非同期処理の書き方は直感的でなくて好きではありません。

 0. ***TypeScript***
型チェック、、、頑張ってるなぁと思います。もちろんパフォーマンスは JavaScript と同じです。tsc 自体が JavaScript で書かれていることにも驚きです。
オプション指定は *`tsconfig.json`* を使うのが作法のようですが、ファイル１個を動かすだけだしコマンドラインオプションで対応しました。結構試行錯誤しました。

0. ***Julia***
着実に進歩してますね。数値計算に向いてるらしいのでオブジェクト指向でガンガン...というのではないようです。配列が [1] から始まるのが...

0. ***Lua***
コンパクトなのにパフォーマンスが良くて、面白い言語です。 メンバ変数は '.' なのに メソッドは ':' とか、配列が [1] から始まるのが残念です。玄人向けだと思います。

0. ***Squirrel***
Lua と同じくコンパクトで、C++ を知ってれば使えるという感じです。拡張子が nut なのがおしゃれです。
グローバル変数の扱いに戸惑いました。ローカル変数につけないといけない local が目につきます。エラーメッセージが判りにくいのと REPLが使いにくいのが残念です。

0. ***Groovy***
ググったら JAVA VM で動く動的言語が見つかったので味見してみました。型があるけど Ruby に似てる感じがあって抵抗なく使えました。
ファイル名と同じ変数名が使えなくて Java のニオイがしました。*`solver_ = new Solver( 6, 10 )`* と _ を付けているのはエラー回避のためです。

0. ***Perl***
ローカル変数が *`my`* って・・・・イケてないと思います。配列変数が *`@`* や *`$`* だったり、参照渡しの場合は *`\`* や *`[]`* が必要だったり、、、戸惑うし理解が難しいです。*`$Pieces{"F"} = [@{$Pieces{"F"}}[0..1]]`* なんて変態です。
間違っていても中途半端に動いてしまうことがあり、初学者には難しいだけでなく危険だと思います。

0. ***AWK***
ペントミノは AWK にとって可哀そうだけど頑張りましたって感じです。 AWK の連想配列はすばらしいです。配列が [1]から始まるのは AWK だから許します。
mawk, nawk, gawk などの派生がまだ使われていて AWK の歴史を感じるけれど、プログラミング言語としては過去の言語だと思います。

0. ***PHP***
WEB開発用の言語でしょ？ということぐらいしか知らず、ペントミノをPHPでやるもんじゃないと思いながらもやってみたらできました。言語としてはシンプルで理解しやすいし、パフォーマンスも悪くないです。
やたらと *`$`* と *`->`* が目に付くのでそこは好きになれないです。行末の *`;`* を忘れて怒られることが多いです。

0. ***C***
C言語を使うことはホントに少なくなりました。メモリを意識しないといけないし、文字列の扱いが不自由だし、、、不便な言語です。実行速度はもちろん速いです。使い勝手としてはセンブリ言語みたいな感じがします。

0. ***C++***
STL を使えば使い勝手はスクリプト言語に（少し）近づきます。STLの多用は実行速度に影響するので、書きやすさとパフォーマンスはトレードオフです。template は変態的で理解が追いつかないです。

0. ***C#***
あまり親しみがないのでこんなものなのかな・・・という感じです。Java や C++ を知っていれば使えるのでしょう。Linuxでも動くのでもう少し使ってみようかな・・・

0. ***Java***
面倒くさい印象があり、昔から使い易い（書き易い）とは思っていません。食わず嫌いです。ファイル名を小文字の solver.java にできなかったのが悔しいです。
ubuntu の java はバージョンが古くて Text Block に対応してないので、それに合わせて *`PIECE_DEF_DOC`* はベタな書き方にしています（残念）。

0. ***Kotlin***
Java よりも格段に良いです。Java の面倒くささを隠蔽してくれて、メソッドチェーンも良い感じに書けて使いやすいです。これで Java を使わずに VM のアプリが作れます。実際に私は Android アプリを Kotlin で作りました。

0. ***Rust***
私には無茶苦茶とっつき難いです。コンパイルエラーを消すのに試行錯誤・・・どうしても unsafe を取ることもできず・・・。腰を落ち着けて勉強しないとだめですね。ポインタをガチャガチャいじるようなアプリには向いてないのかもしれません。
エラーメッセジーはとても親切です。

0. ***Go***
文法に独特感があって、触ってないと忘れてしまいます。このソルバープログラムを備忘録にします。

0. ***Swift***
Objective-C を試そうと思ったけれど Mac以外で環境を作るのが面倒そうだったので諦めて、代わりに Swift を選びました。
引数の型宣言が面倒でしたがあまり癖は感じなかったです。Mac以外で使うことあるのかなぁ・・・

0. ***LISP***
今まで避けていましたが、興味があったので使ってみました。なんとなく***LISPの心***が解った気がします。でも、独特過ぎて書き易いとも見易いとも思いません。emacs の 設定が読めるようになった（たぶん）のでトライして良かったです。

0. ***Crystal***
存在を知りませんでした。 ほぼ Rubyのように書けます。頑張ってると思います。C や C++ と同じとは行きませんが実行速度は速いです。頑張ってると思います。

0. ***Elixir***
関数型言語の特徴を体験できます。表記方法に Ruby のニオイがします。すべてのデータが imutable なので、List、Map の要素を書き換えるという基本的な操作に手間取ったり、グローバル変数という概念がないので面食らいます。従来のプログラムではいかに副作用に依存していたかということを痛感します。パイプ演算子（|>）は面白いです。

0. ***F#***
Elixir 以外の関数型言語もと思い試してみました。実行速度は速いです。表記方法は Python のニオイがするし、他にもクセの強さを感じました。また、match ～ with が難しい、エラーメッセージが解りにくい、など難しさも感じました。

0. ***D***
コンパイル型言語なのにスクリプティング言語みたいな書き易さがあり、C++のような変態性がなく、センスのいい言語だと思います。もっとメジャーになって欲しいです。Uniform Function Call Syntax (UFCS) と Range が素晴らしい！
そんなD言語の設計者 Walter Bright氏⋯⋯と言えば Zortech C++コンパイラ！ あれはコンパクトで使いやすかったです。

0. ***Dart***
JavaScript がベースらしいので、ChatGPTに手伝ってもらいながら solver.js を書き直してとりあえず動くものはすぐにできました。ペントミノソルバー程度のプログラムを書く分には特に JavaScript 以上のメリットは感じないです。

# 動作環境

Linux ubuntu:22.04、Mac Sonoma:14.4、Cygwin(Windows)で動作確認しました。

:::note info
*tsc (TypeScript Compiler)* では、*`npm i --save-dev @types/node`* を一度だけ実行しておく必要があります。 実行していないとエラーがでます。
```shell-session:TypeScript の初回実行
$ tsc -t es2019 -m commonjs --strict solver-ts.ts
solver-ts.ts(202,18): error TS2580: Cannot find name 'process'. Do you need to install type definitions for node? Try `npm i --save-dev @types/node`.

$ npm i --save-dev @types/node  # 指示通りに npm i ...を実行
$ ls node_modules          　   # node_modules ディレクトリが作られる
@types/   undici-types/
$ tsc -t es2019 -m commonjs --strict solver-ts.ts   # エラーにならずに実行できる
```
:::

### ubuntu 22.04

Mac と Windows(WSL2) 上のコンテナで~~全ての言語をインストールして~~動作確認しました。[Dockerfile](https://github.com/sense-n-react/PentominoSolvers/blob/main/Dockerfile) で x86_64 でなければ arm64 の Julia と Swift をダウンロードするように設定しています。


|  |  |  |  |  |
|:-:|:-:|:-:|:-:|:-:|
| ***Ruby***<br> 3.0.2  | ***Python***<br> 3.10.12  | ***Lua***<br>5.1.5 | ***Squirrel***<br>3.2| ***Julia*** <br> 1.10.2|
| ***JavaScript***<br> node 12.22.9   | ***TypeScript***<br>tsc 4.9.5 | ***Groovy***<br>2.4.21 | ***Perl*** <br> 5.34.0 | ***AWK***<br> mawk 1.3.4 |
| ***PHP***<br> 8.1.2 | ***C*** <br>gcc 11.4.0<br>clang 15.0| ***C++***<br> g++ 11.4.0<br>clang++ 15.0| ***C#***<br>mcs 6.8.0.105 | ***Java***<br> javac 11.0.22 |
| ***Kotlin***<br>  kotlinc-jvm 1.3 | ***Go***<br>1.18.1 | ***Rust***<br> rustc 1.75.0  | ***Swift***<br>5.10| ***LISP***<br>sbcl 2.1.11 <br> clisp 2.49.93| 
| ***Crystal***<br> 1.14.0 <br> LLVM: 18.1.6 |  ***Elixir***<br>  1.12.2| ***F# 6.0***<br> fsi 12.0.0.0<br>dotnet 6.0.135  | ***D***<br> LDC 1.28.0|***Dart***<br>2.15.1<br>and<br>3.6.2 |

apt-get でインストールしましたが、Julia, Swift, Squirrel はパッケージが見つかりませんでした。Julia と Swift はバイナリイメージがあったのでそれをダウンロードし、Squirrel　はソースからビルドしています。
Crystal は Dcokerfile に反映していないですが、x86_64版 tarball で動作確認しました。Dart は Dockerイメージで動作確認しました。

### Mac Sonoma

brew install でインストールしました。
（追記）F# は [Microsoftの.NETのダウンロードサイト](https://dotnet.microsoft.com/ja-jp/download)からダウンロードしました。

(2024/12 時点）
|  |  |  |  |  |
|:-:|:-:|:-:|:-:|:-:|
| ***Ruby***<br> 3.2.0  | ***Python***<br> 3.13.0  | ***Lua***<br>5.4.7 | ***Squirrel***<br>3.2| ***Julia*** <br> 1.11.1|
| ***JavaScript***<br> node 23.1   | ***TypeScript***<br>tsc 4.9.5 | ***Groovy***<br> 4.0.24 | ***Perl*** <br> 5.34.1 | ***AWK***<br> gawk 5.3.1<br>nawk 20200816 |
| ***PHP***<br> 8.3.13 | ***C*** <br>clang 15.0.0| ***C++***<br> clang++ 15.0.0| ***C#***<br>mcs 6.12.0.182<br>csc 3.9.0 | ***Java***<br> javac 23.0.1 |
| ***Kotlin***<br> kotlinc-jvm 2.0.21 | ***Go***<br> 1.23.2 | ***Rust***<br> rustc 1.76.0  | ***Swiftc***<br>1.90.1| ***LISP***<br>sbcl 2.4.10 <br> clisp 2.49.92| 
| ***Crystal***<br> 1.14.0 |  ***Elixir***<br>  1.17.3 | * ***F# 9.0***<br> fsi 12.9.100.0<br>dotnet 9.0.101 |  ***D***<br> LDC 1.40.0| ***Dart***<br>3.6.2 |

### Cygwin(Windows)
Cygwin Ports にないものは Windows版をインストールし（＊印）、 Windows版もないものはソースからビルド（＊＊印）しました。

|  |  |  |  |  |
|:-:|:-:|:-:|:-:|:-:|
| ***Ruby***<br> 3.2.2  | ***Python***<br> 3.9.16  | ***Lua***<br>5.3.6 | ** ***Squirrel***<br>3.2| * ***Julia*** <br> 1.8.2|
| * ***JavaScript***<br> node 20.12.2   | * ***TypeScript***<br>tsc 4.9.5 | * ***Groovy***<br> 2.5.23 | ***perl*** <br> 5.36 | ***AWK***<br> gawk 5.3.0 |
| ***PHP***<br> 7.3.7 | ***C*** <br>gcc 11.4.0<br>clang 8.0.1| ***C++***<br> g++ 11.4.0<br>clang++ 8.0.1| ***C#***<br>csc 4.8.4084.0  | ****Java***<br> javac 21.0.2 |
| * ***Kotlin***<br> kotlinc-jvm 1.7.20 | * ***Go***<br> 1.19.4 | * ***Rust***<br> rustc 1.70.0  | * ***Swift***<br>5.10| ***LISP***<br> *sbcl 2.3.2 <br> clisp 2.49|
| * ***Crystal***<br>  1.13.3 <br> LLVM: 18.1.1 |  * ***Elixir***<br>  1.17.3 | * ***F# 9.0***<br> fsi 12.9.100.0 | * ***D***<br> DMD32 v2.109.1 | ***Dart***<br> N/A |

# 実行時間

やはり気になる実行時間をグラフにしてみました。MacBook M2 Sonoma の環境で、6x10 の全解（2,339通り）を求めるのにかかった時間をプロットしました。
スクリプト系とコンパイル系とでは桁が違ってくるので対数表示にしています。

![dart.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3761186/a195b2b1-5942-6d6a-a935-af2e07aa525f.png)



なお、アルゴリズムを改良すれば全ての言語において10倍以上の高速化が可能ですが、ここでは言語間の比較が目的なので最適化には触れません。


# 参考記事

https://qiita.com/gushwell/items/9742c5091b2d95725651

https://qiita.com/maskot1977/items/685c336b104a3ec12c2c

https://ja.wikipedia.org/wiki/%E3%83%9A%E3%83%B3%E3%83%88%E3%83%9F%E3%83%8E

https://en.wikipedia.org/wiki/Pentomino

https://www.codeproject.com/Articles/271634/Puzzle-Solver

https://en.wikipedia.org/wiki/Knuth%27s_Algorithm_X


* [pentomino-solver](https://github.com/mlepage/pentomino-solver)
* [明治ミルクチョコーレートパズルの解をすべて探す - ザリガニが見ていた...。](https://zariganitosh.hatenablog.jp/entry/20150112/pentomino_programming)
* [PENTOMINO](https://www.kobe-kosen.ac.jp/~maeda/)
* [ペントミノを解く](https://www.asahi-net.or.jp/~rn8t-nkmr/pentomino/)
* [脳ブロック](https://bb.tenyo.co.jp/products/index.html)