<commit_before>最短経路
　http://d.hatena.ne.jp/zariganitosh/20100419/maze

一筆書き経路
　全探索して、閉路ができてしまうルートは刈る。

例：

　1 2 3 4
1 Ｓ□□□
2 □□■□
3 □□Ｇ□

Ｓ[1,1], Ｇ[3,3]

1歩目
　[1,1],[1,2]
　[1,1],[2,1]

各ルートの行き止まりチェックとゴールチェック
※ 行き止まりチェック == 最終到達マスの周囲4マス全てが空白マスでもＧでもない、かつ、Ｇを除く未到達マスの中で3方向が囲まれている、かつ、その3方向の中に最終到達マスが無い。
いずれのルートも行き止まり無し


2歩目
　[1,1],[1,2],[1,3]
　[1,1],[1,2],[2,2]　×
　[1,1],[2,1],[2,2]
　[1,1],[2,1],[3,1]

各ルートの行き止まりチェック
×のルートは行き止まりができるので探索から外す([1,3]が行き止まり)

3歩目
　[1,1],[1,2],[1,3],[1,4]
　[1,1],[2,1],[2,2],[1,2]
　[1,1],[2,1],[2,2],[3,2]　× ([1,2]が行き止まり)
　[1,1],[2,1],[3,1],[3,2]

4歩目
　[1,1],[1,2],[1,3],[1,4],[2,4]
　[1,1],[2,1],[2,2],[1,2],[1,3]
　[1,1],[2,1],[3,1],[3,2],[2,2]
　[1,1],[2,1],[3,1],[3,2],[3,3]　×(ゴールしたけど全部通っていない)

※ゴールチェック == 最終到達マスがゴールかつ、全部通ったか。全部通っていればそのルートが最長ルート。
　ちなみに、一番最初に最終到達マスがゴールになったルートが最短ルート。

再掲
　1 2 3 4
1 Ｓ□□□
2 □□■□
3 □□Ｇ□

5歩目
　[1,1],[1,2],[1,3],[1,4],[2,4],[3,4]
　[1,1],[2,1],[2,2],[1,2],[1,3],[1,4]
　[1,1],[2,1],[3,1],[3,2],[2,2],[1,2]

6歩目
　[1,1],[1,2],[1,3],[1,4],[2,4],[3,4],[3,3]　×(ゴールしたけど全部通っていない)
　[1,1],[2,1],[2,2],[1,2],[1,3],[1,4],[2,4]
　[1,1],[2,1],[3,1],[3,2],[2,2],[1,2],[1,3]

7歩目
　[1,1],[2,1],[2,2],[1,2],[1,3],[1,4],[2,4],[3,4]
　[1,1],[2,1],[3,1],[3,2],[2,2],[1,2],[1,3],[1,4]

8歩目
　[1,1],[2,1],[2,2],[1,2],[1,3],[1,4],[2,4],[3,4],[3,3]　×(ゴールしたけど全部通っていない)
　[1,1],[2,1],[3,1],[3,2],[2,2],[1,2],[1,3],[1,4],[2,4]

9歩目
　[1,1],[2,1],[3,1],[3,2],[2,2],[1,2],[1,3],[1,4],[2,4],[3,4]

10歩目
　[1,1],[2,1],[3,1],[3,2],[2,2],[1,2],[1,3],[1,4],[2,4],[3,4],[3,3]　○(ゴールしてかつ全部通っている)


課題：
　最短経路みたいな方法でもっと効率いい方法あるかもしれないが思い浮かばない。
　枝刈り処理ももっと何とかなりそう。
　例えば
　
　1 2 3 4
1 ↓□□□
2 →→→↓
3 □□□□
4 □□□□
5 □□□□
6 Ｇ□□□

の時点で、[1,2～4]の地点を通ることはできなくなるので、このルートを刈りたい。

いける方向が2つしかない時、その2つがセパレートされているかどうか判定？

行き止まり判定も移動候補マスだけやればよい？
[3,3]から3方向行けるが[2,3]に進むと[3,2]が行き止まり。
[3,3]から進むときに行き止まりができる可能性のあるマスは[3,3]に隣接しているマスだけで、
他のマスで行き止まりになる場合は無い、かも。

　1 2 3 4 5 6 7
1 ↓□□□□□□
2 ↓□↑□□□□
3 ↓□↑□□□□
4 →→↑□□□□
5 □□□□□□Ｇ<commit_msg>迷路メモ追記<commit_after>最短経路
　http://d.hatena.ne.jp/zariganitosh/20100419/maze

一筆書き経路
　全探索して、閉路ができてしまうルートは刈る。

例：

　1 2 3 4
1 Ｓ□□□
2 □□■□
3 □□Ｇ□

Ｓ[1,1], Ｇ[3,3]

1歩目
　[1,1],[1,2]
　[1,1],[2,1]

各ルートの行き止まりチェックとゴールチェック
※ 行き止まりチェック == 最終到達マスの周囲4マス全てが空白マスでもＧでもない、かつ、Ｇを除く未到達マスの中で3方向が囲まれている、かつ、その3方向の中に最終到達マスが無い。
いずれのルートも行き止まり無し


2歩目
　[1,1],[1,2],[1,3]
　[1,1],[1,2],[2,2]　×
　[1,1],[2,1],[2,2]
　[1,1],[2,1],[3,1]

各ルートの行き止まりチェック
×のルートは行き止まりができるので探索から外す([1,3]が行き止まり)

3歩目
　[1,1],[1,2],[1,3],[1,4]
　[1,1],[2,1],[2,2],[1,2]
　[1,1],[2,1],[2,2],[3,2]　× ([1,2]が行き止まり)
　[1,1],[2,1],[3,1],[3,2]

4歩目
　[1,1],[1,2],[1,3],[1,4],[2,4]
　[1,1],[2,1],[2,2],[1,2],[1,3]
　[1,1],[2,1],[3,1],[3,2],[2,2]
　[1,1],[2,1],[3,1],[3,2],[3,3]　×(ゴールしたけど全部通っていない)

※ゴールチェック == 最終到達マスがゴールかつ、全部通ったか。全部通っていればそのルートが最長ルート。
　ちなみに、一番最初に最終到達マスがゴールになったルートが最短ルート。

再掲
　1 2 3 4
1 Ｓ□□□
2 □□■□
3 □□Ｇ□

5歩目
　[1,1],[1,2],[1,3],[1,4],[2,4],[3,4]
　[1,1],[2,1],[2,2],[1,2],[1,3],[1,4]
　[1,1],[2,1],[3,1],[3,2],[2,2],[1,2]

6歩目
　[1,1],[1,2],[1,3],[1,4],[2,4],[3,4],[3,3]　×(ゴールしたけど全部通っていない)
　[1,1],[2,1],[2,2],[1,2],[1,3],[1,4],[2,4]
　[1,1],[2,1],[3,1],[3,2],[2,2],[1,2],[1,3]

7歩目
　[1,1],[2,1],[2,2],[1,2],[1,3],[1,4],[2,4],[3,4]
　[1,1],[2,1],[3,1],[3,2],[2,2],[1,2],[1,3],[1,4]

8歩目
　[1,1],[2,1],[2,2],[1,2],[1,3],[1,4],[2,4],[3,4],[3,3]　×(ゴールしたけど全部通っていない)
　[1,1],[2,1],[3,1],[3,2],[2,2],[1,2],[1,3],[1,4],[2,4]

9歩目
　[1,1],[2,1],[3,1],[3,2],[2,2],[1,2],[1,3],[1,4],[2,4],[3,4]

10歩目
　[1,1],[2,1],[3,1],[3,2],[2,2],[1,2],[1,3],[1,4],[2,4],[3,4],[3,3]　○(ゴールしてかつ全部通っている)


課題：
・最短経路みたいな方法でもっと効率いい方法あるかもしれないが思い浮かばない。
・枝刈り処理ももっと何とかなりそう。
　例えば
　
　1 2 3 4
1 ↓□□□
2 →→→↓
3 □□□□
4 □□□□
5 □□□□
6 Ｇ□□□

の時点で、[1,2～4]の地点を通ることはできなくなるので、このルートを刈りたい。

いける方向が2つしかない時、その2つがセパレートされているかどうか判定？

行き止まり判定も移動候補マスだけやればよい？
[3,3]から3方向行けるが[2,3]に進むと[3,2]が行き止まり。
[3,3]から進むときに行き止まりができる可能性のあるマスは[3,3]に隣接しているマスだけで、
他のマスで行き止まりになる場合は無い、かも。

　1 2 3 4 5 6 7
1 ↓□□□□□□
2 ↓□↑□□□□
3 ↓□↑□□□□
4 →→↑□□□□
5 □□□□□□Ｇ

・確定ルートの利用
黒マスの配置によっては部分的に確定するルートがある(図の○)。
黒マスに挟まれているマスは確定ルート。確定ルートに挟まれている箇所は確定ルート。ただし順序は確定しない。
予め導出した確定ルートに隣接するマス(図の△)に入った時点で○を通って次の△までいくことが確定する。

　1 2 3 4 5 6 7
1 Ｓ□□△○△□
2 ■□□□■△□
3 ○△□□■○■
4 ○■□□□△■
5 ○○△□□□Ｇ

・確定ルートの拡張
△マス2つによって閉路ができているかつ閉路内にＳもＧもない場合は、その2つの△を結ぶ最長経路も確定ルートになる。
(上の図の[1,6],[1,7],[2,7],[2,6])


{'fraction_non_alphanumeric': 0.36944980694980695, 'fraction_numerical': 0.1858108108108108, 'mean_word_length': 8.84560570071259, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 3, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '3188843', 'n_tokens_mistral': 4007, 'n_tokens_neox': 3690, 'n_words': 271}