TSPは巡回セールスマン問題から着想を得た難解プログラミング言語である。
セールスマンがxy平面の格子点上を動く経路によってグラフが構築され、グラフの頂点に対応する命令が実行される。
- セールスマンは最初、xy平面の原点
(0, 0)にいる。 A,S,D,Wをコードに記述するとそれぞれ左、下、右、上にセールスマンが長さ1だけ移動する。$を記述するとセールスマンは現在いる格子点を「訪れる」。- 同じ点は二度と訪れることは出来ないが、通過することは何度でもできる。
- セールスマンはコードの最後に原点を訪れる必要がある。
- セールスマンが訪れた格子点を頂点とし、訪れた順に頂点を結んでできるグラフを
Gとする。 Gの各頂点には命令が割り当てられる。どの命令が割り当てられるかはその頂点の座標による。- x軸の正の向きを東、y軸の正の向きを北として、原点から見たときの方位により命令が決定される
- コード上で命令を記述する際にASDWで移動した歩数を
Nとする。 - スタックの上から
n番目 （1-origin） を$nと表す。 - x軸、y軸、直線
y = x、直線y = -x上の格子点にはnopが割り当てられる。
| 方位 | 命令 | 説明 |
|---|---|---|
| 東北東 | push N |
N をスタックにpushする |
| 北北東 | dup |
$1 と同じ値をスタックにpushする |
| 北北西 | swap N |
スタックの $1 と $N の値を入れ替える |
| 西北西 | sub |
$1 と $2 をスタックからpopし、$2 - $1 をpushする |
| 西南西 | greater |
$1 と $2 をスタックからpopし、$2 > $1 なら1を、そうでなければ0をpushする |
| 南南西 | jump-zero N |
スタックの $1 を参照し、0ならジャンプする(*) |
| 南南東 | getchar |
標準入力から1文字読み込み、スタックにpushする |
| 東南東 | putchar |
スタックから $1 をpopし、標準出力に出力する |
- 命令の実行順は以下のように決定される。 セールスマンが訪れた順は実行順と必ずしも一致しない。
- 各頂点の原点からのチェビシェフ距離
CD = max(abs(x), abs(y))とマンハッタン距離MD = abs(x) + abs(y)を計算する。 CDが小さい順に実行される。CDが同じ頂点が複数存在する場合、MDが小さい順に実行される。CDとMDが完全に同一である頂点がGに2つ以上存在してはいけない。- (*)
jump-zero Nはジャンプ後、CDがN以上である頂点のうちCDが最小である頂点の中でMDが最小であるような頂点の命令を次に実行する。
- 各頂点の原点からのチェビシェフ距離
- 細則
ASDW$以外の文字はコメントとして扱われる。- セールスマンがある頂点から別の頂点に移動する間の経路は遠回りしたり同じ場所を行ったり来たりすることができる（例:
WWWADADS）。 - スタックの要素は32bit整数型である。
- 文字の入出力に際してはUTF-8を想定し、1 unicode code pointを1文字として扱う。
- Go言語におけるruneの扱いと同様である。 cf. Strings, bytes, runes and characters in Go
- 入力がEOFに達したときは0がpushされる。
- スタックの要素数が命令に必要な数未満であったり、範囲外を参照しようとするとnopとして扱われる。
- コマンド引数
-strictを指定すると異常終了する。
- コマンド引数
Requirements: Go 1.13 or later
$ go get -u github.com/nakario/tsp/cmd/tsp
$ tsp [-debug] [-strict] code.tsp