たかしくんにお遍路を土日だけで巡回させる

## たかしくんとは？

算数の文章問題でよく出てくるたかしくんを使って、自分で問題を出して解こうと思います！

https://qiita.com/canonno/items/29eb369d32c030fea367

こちらの記事を見て自分もたかしくんに色々させてみたいと思いました。（`たかしくん`タグ流行れ）

### たかしくんのスペック

* **たかしくんは強い**ので海を渡れます。
* **たかしくんは強い**ので山があろうが谷があろうが一定の速度で走れます。
* **たかしくんは強い**ので24時間走れます。

ここテンプレートでいいのかも…
mdも残しておきます

```
* **たかしくんは強い**ので海を渡れます。
* **たかしくんは強い**ので山があろうが谷があろうが一定の速度で走れます。
* **たかしくんは強い**ので24時間走れます。
```

### お遍路とは

[お遍路の基本｜愛媛のお遍路はこう回る！｜愛媛 旅の特集｜愛媛県の公式観光サイト【いよ観ネット】](https://www.iyokannet.jp/feature/henro/kihon#:~:text=%E3%80%8C%E3%81%8A%E9%81%8D%E8%B7%AF%E3%80%8D%E3%81%A8%E3%81%AF%E3%80%81,%E5%8F%82%E6%8B%9D%E3%83%AB%E3%83%BC%E3%83%88%E3%81%8C%E7%89%B9%E5%BE%B4%E3%81%A7%E3%81%99%E3%80%82)

以下抜粋です

- 約1200年前に弘法大師（空海）が修行した88の霊場をたどる巡礼のこと
- 参拝する88ヶ寺のことを「札所」と呼ぶ
- すべての札所を巡拝することで、弘法大師の功徳を得られる
- 道のりは約1400kmにも及ぶ
- 参拝は、心を込めて参拝することが何より大切です
- 4つの必需品がある

正装はこんな感じ

[![Image from Gyazo](https://i.gyazo.com/19be3e386b3d23bec2697facbf1d35c9.jpg)](https://gyazo.com/19be3e386b3d23bec2697facbf1d35c9)

(https://www.ippoippodo.com/?mode=f10)

### たかしくんもお遍路を巡回したいそうです

* たかしくんはなんか仕事で大きな失敗をしてしまったのか、とりあえずお遍路巡回して徳を得ようと考えたようです。
* たかしくんは平日はフルタイム勤務なので土日の48時間で周りたいようです。
    * リモートワークなので出発(ゴール)するお寺からの移動は考えなくていいようです。
* たかしくんはせっかちなので移動は全て直線で行うものとします。
    * 山があったら潜っていくし、谷や海があったら飛んで移動します。
* たかしくんはお遍路88箇所を寝ずに食べずに走って周ります。
    * 札所の滞在時間は0秒です。
    * 24時間食べずに走れるので手ぶらでいきます。
    * 走りやすいようにジャージでいきます。

## やってみる

### 他の人が共有しているマップから緯度経度を取得する

https://www.google.com/maps/d/u/0/viewer?ie=UTF&msa=0&mid=1nxXvA3fGWgDasOjUScvlyRydBkQ&ll=33.54690165757816%2C133.562764&z=8

こちらで公開してくれているマップから緯度経度を取得してみます

GoogleMapのAPIを使おうと思いましたが、もっと簡単な方法がありました

#### KMLファイルのダウンロード

[![Image from Gyazo](https://i.gyazo.com/b86a106a3265693406e31043cff50a7d.png)](https://gyazo.com/b86a106a3265693406e31043cff50a7d)

直接CSVとかJSONとかダウンロードできれば一番いいですが、いったんKMLというファイル形式でマップの情報をダウンロードします。

#### KMLからJSONに変換

http://ogre.adc4gis.com/

こちらのサイトでKMLからJSONに変換します。

すると中身が

```json
{"type":"FeatureCollection","crs":{"type":"name","properties":{"name":"urn:ogc:def:crs:OGC:1.3:CRS84"}},"features":[{"type":"Feature","properties":{"Name":"第1番札所 霊山寺 りょうぜんじ","description":"第一番札所　竺和山　霊山寺（じくわざん　りょうぜんじ）<br>高野山真言宗 <br>ご本尊　　釈迦如来<br>開基　　　 行基菩薩<br>御詠歌　　霊山の釈迦のみ前にめぐりきてよろずの罪も消え失せにけり<br>住所　　　 徳島県鳴門市大麻町板東霊山寺１２６<br>電話　　　 ０８６－６８９－１１１１<br>北緯34度09分34.0秒東経134度30分10.8秒<br>+34° 9' 34.00\", +134° 30' 10.80\"<br>34.159444, 134.503000","timestamp":null,"begin":null,"end":null,"altitudeMode":null,"tessellate":-1,"extrude":0,"visibility":-1,"drawOrder":null,"icon":null},"geometry":{"type":"Point","coordinates":[134.503,34.159444,0]}},{"type":"Feature","properties":{"Name":"第2番札所 極楽寺 ごくらくじ","description":"第二番札所　日照院　極楽寺（にっしょうざん　ごくらくじ）<br>高野山真言宗<br>ご本尊　阿弥陀如来<br>開基　　 行基菩薩<br>ご詠歌　極楽の弥陀の浄土へ行きたくば　南無阿弥陀仏口ぐせにせよ<br>住所　　 徳島県鳴門市大麻町檜字段の上１２<br>電話　　 ０８８－６８９－１１１２<br>北緯34度09分21.7秒東経134度29分24.9秒<br>+34° 9' 21.70\", +134° 29' 24.90\"<br>34.156028, 134.490250","timestamp":null,"begin":null,"end":null,"altitudeMode":null,"tessellate":-1,"extrude":0,"visibility":-1,"drawOrder":null,"icon":null},"geometry":{"type":"Point","coordinates":[134.490509,34.155566,0]}},
```

こんな感じでみることができます（データ全部を載せていないです。省略しています）

### Node.jsで計算していく

#### まずはjsonを読み込んで、緯度経度取得

```js
'use strict';

const fs = require('fs');

const ohenroJson = JSON.parse(fs.readFileSync('./convert.json', 'utf8'));
const ohenroArr = ohenroJson.features;

ohenroArr.forEach(e => {
  console.log(e.properties.Name);
  console.log('lat:' + e.geometry.coordinates[0] + ', lon:' + e.geometry.coordinates[1]);
});
```

結果は以下のような感じ

[![Image from Gyazo](https://i.gyazo.com/2e38cbc3e0daff570e313f882225cc43.png)](https://gyazo.com/2e38cbc3e0daff570e313f882225cc43)

#### 距離計算

https://qiita.com/kawanet/items/a2e111b17b8eb5ac859a

こちらの記事を参考にまずはデータ的に1番の札所から順番に周ったときの距離を計算してみます

```js
'use strict';

const fs = require('fs');

const ohenroJson = JSON.parse(fs.readFileSync('./convert.json', 'utf8'));
const ohenroArr = ohenroJson.features;

let sum = 0;
for (let i = 0; i < ohenroArr.length - 1; i++) {
  const cLat = ohenroArr[i].geometry.coordinates[0];
  const cLon = ohenroArr[i].geometry.coordinates[1];
  const nLat = ohenroArr[i + 1].geometry.coordinates[0];
  const nLon = ohenroArr[i + 1].geometry.coordinates[1];
  const dist = distance(cLat, cLon, nLat, nLon);
  sum += dist;
}

// 直線での距離
console.log('直線でのお遍路巡礼の距離は' + sum + 'km');

// kmを返す
function distance(lat1, lng1, lat2, lng2) {
  lat1 *= Math.PI / 180;
  lng1 *= Math.PI / 180;
  lat2 *= Math.PI / 180;
  lng2 *= Math.PI / 180;
  return 6371 * Math.acos(Math.cos(lat1) * Math.cos(lat2) * Math.cos(lng2 - lng1) + Math.sin(lat1) * Math.sin(lat2));
}
```

すると結果は

```
直線でのお遍路巡礼の距離は794.2115810769094km
```

お遍路の参考サイトでは1200kmもの道のりとありましたが、すでに400kmくらい短縮できました
さすがたかしくん

## 土日の48時間でお遍路を直線的に巡回する際、時速何キロで走ればいい？

```js
console.log('時速' + (sum / 48) + 'kmで走れば48時間で巡れる');
```

こちらのコードを追加

答えは、

```
時速16.546074605768947kmで走れば48時間で巡れる
```

です！

## 最後に

これでたかしくんは時速16.546074605768947kmで48時間ジャージで走り続け、参拝を0秒で行い、土日だけで徳を積むことができたそうです。

めでたしめでたし

## 最短の組み合わせもやりたかった

全部の組み合わせを出してやろうと思ったけど、処理が1日経っても終わらなかった…

ちなみに全部のパターンを配列にしてくれる処理はたぶんメモリリークでだめだった…

88箇所でどこからスタートしてもいいし、ゴールに設定しても良い状況での組み合わせは相当多かった

計算方式として例えばA,B,C,Dの4箇所だとしても

- ABCD
- ABDC
- ACBD
- ACDB
- ADBC
- ADCB

Aから始まっているのが6パターンあるのでそれがもう3個あると考えると`24パターン`あることになるはず。

その計算方法が、`4*3*2*1`らしい。

なので、組み合わせ数を計算する関数を作ってみた

```js
console.log(BigInt(combinationNum(88)));

function combinationNum(len) {
  let r = 1;
  for (let i = len; i > 1; i--) {
    r *= i;
  }
  return r;
}
```

めちゃくちゃでかい数字なので`BigInt`で囲ってます

結果

`185482642257398395706669786749287093090739583271062212249681965111775306403630728065563094740586576320295195562781717041354470915571712`パターンあるっぽいです

https://www.nap.st/large_numbers_to_kanji/?lang=ja

ここのサイトで漢字の単位を入れると

`1854無量大数8264不可思議2257那由他3983阿僧祇9570恒河沙6669極7867載4928正7093澗907溝3958穰3271𥝱622垓1224京9681兆9651億1177万5306`

無量大数を普通に単位として使うの初めてだこれ…

とにかく無理なので最適化のアルゴリズム、これから勉強してやっていきたいです！

JavaScriptでもいいけど、Pythonでもいいかも…