Project Eulerをシェル芸で解いてみる(Problem 15)

概要

Project Euler¹は、数学的な問題解決能力を要求する、プログラミング問題集・オンラインプログラミングジャッジである。
一般的なオンラインプログラミングジャッジとは異なり、解答するプログラミング言語は、特に限定されていない。
フォームに入力した値だけで正誤を判別するため、適切なアルゴリズムさえ考案できれば、あらゆるプログラミング言語で解答することが可能である。
そのため、Web上では様々な手法による解答が公開されている。

しかし、シェル芸²による解答は、私が探した限りでは、殆ど見つからなかった。
そこで、私自身の勉強も兼ねて、Project Eulerをシェル芸で解いてみることにした。

本記事では、Project EulerのProblem 15を、シェル芸で解いた際の過程を述べる。

実行環境

• Arch Linux (x86_64, 4.3.3-2-ARCH)
• bash (4.3.42, POSIX互換モード)
• GNU coreutils (8.24)
• gawk (4.1.3)

問題文

[原文 (https://projecteuler.net/problem=15)]

Starting in the top left corner of a $2 \times 2$ grid, and only being able to move to the right and down, there are exactly 6 routes to the bottom right corner.


> How many such routes are there through a $20 \times 20$ grid?

[日本語訳 (http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2015)]

$2 \times 2$ のマス目の左上からスタートした場合, 引き返しなしで右下にいくルートは 6 つある.

(画像は原文と同じ)

> では, $20 \times 20$ のマス目ではいくつのルートがあるか.

正答は、注釈³に記載する。

解法

prob_015.sh

1	#!/bin/sh
2	
3	echo 20 \
4	| # マス目nの設定
5	awk '{print $1*2, $1}' \
6	| # 2n, nの出力
7	awk '{for(i=0; i<=$2-1; i++){print $1-i}; print "#"; for(i=$2; i>0; i--){print i}}' \
8	| # 2nCnの算出式の生成1
9	xargs \
10	| # 行->列変換
11	sed -e 's$ # $/$; s$\(.*\)/\(.*\)$(\1)/(\2)$' \
12	| # 2nCnの算出式の生成2
13	tr ' ' '*' \
14	| # 2nCnの算出式の生成3
15	bc
16	  # 2nCnの出力

以下、コマンドライン上での実行用コードである。

echo 20 | awk '{print $1*2, $1}' | awk '{for(i=0; i<=$2-1; i++){print $1-i}; print "#"; for(i=$2; i>0; i--){print i}}' | xargs | sed -e 's$ # $/$; s$\(.*\)/\(.*\)$(\1)/(\2)$' | tr ' ' '*' | bc

解説

初めに、解答方針を述べる。
今回の設問では、格子経路をパスカルの三角形として考える。(参考1)

まず、格子経路を $45^\circ$ 回転させる。
ここで、 $45^\circ$ 回転させた $n \times n$ 格子経路は、 $2n$ 段のパスカルの三角形の一部分と一致する。
このとき、パスカルの三角形のある位置の値は、格子経路においてスタート地点から該当する位置へ引き返し無しで進む経路の数と一致する。
したがって、今回の問題では、 $2n$ 段のパスカルの三角形の値に着目すれば良い。

具体例として、 $2 \times 2$ 格子経路とパスカルの三角形の関係を挙げる。
まず、 $2 \times 2$ 格子経路を $45^\circ$ 回転させる。


次に、4段のパスカルの三角形において、 $2 \times 2$ 格子経路と一致する部分を示す。

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1

(青: スタート地点、緑: 経過地点、赤: ゴール地点、灰: 格子経路外)

ここで、パスカルの三角形におけるある位置の値は、スタート地点からその位置まで引き返し無しで進む経路の数と一致する性質を利用する。 $2 \times 2$ 格子経路の左上から右下までの経路数を求める場合は、左下に該当する1段目の'1'から、 $2 \times 2$ 段真下に進んだ位置の値を見れば良い。 そして、パスカルの三角形において、1段目から $n$ 段真下に進んだ位置の値は、 $\_{2n} C_n$ で表すことができる。([参考2](http://qiita.com/gin_135/items/b140ce6ab69a09eb93e6#%E5%8F%82%E8%80%83%E3%81%AB%E3%81%97%E3%81%9F%E3%82%82%E3%81%AE)) つまり、 $2 \times 2$ 格子経路の場合、 $\_4 C_2 = 6$ が求める全経路数である。

以上の内容より、今回の問題では $_{2n} C_n$ の算出を実装すれば良い。

---

ソースコードに関しては、コードに記載してあるコメントの通りである。
概略だけ述べると、 $_{2n} C_n$ の算出式を生成し、bcによって計算結果を出力している。

参考にしたもの

1. project euler problem 15 - 計算機と戯れる日々 〈http://d.hatena.ne.jp/n9d/20100928/p1〉
2. 『数学ガール 乱択アルゴリズム』、結城 浩、SoftBank Creative、pp.89

雑記

• 「こんな別解があるよ」や、「こうすればもっと効率化できるぜ」、「こう書けばエレガントですわよ」等の意見がありましたら、気軽に教えていただけますと幸いです🐺
• 現在の進捗状況 -> https://github.com/gin135/Project_Euler/tree/master/sh

• 格子経路とパスカルの三角形の関係にどうしても気付けなくて、解法を調べてしまったorz
• 解法さえ分かれば、後はシンプル...

---

1. About - Project Euler (https://projecteuler.net) ↩

2. シェル芸の定義 >> シェル芸 - 上田ブログ (https://blog.ueda.asia/?page_id=1434) ↩

3. 137846528820 ↩