概要

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

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

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

実行環境

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=9)]

A Pythagorean triplet is a set of three natural numbers, $a < b < c$, for which,
a^2 + b^2 = c^2
For example, $3^2 + 4^2 = 9 + 16 = 25 = 5^2$.
There exists exactly one Pythagorean triplet for which $a + b + c = 1000$.
Find the product $abc$.

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

ピタゴラス数(ピタゴラスの定理を満たす自然数)とは $a < b < c$ で以下の式を満たす数の組である.
a^2 + b^2 = c^2
例えば, $3^2 + 4^2 = 9 + 16 = 25 = 5^2$ である.
$a + b + c = 1000$ となるピタゴラスの三つ組が一つだけ存在する.
これらの積 $abc$ を計算しなさい.

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

解法

1   #!/bin/sh
2   
3   seq 1 332 \
4   | # a列の生成
5   awk '{for(b=1; b<500; b++) {print $1, b}}' \
6   | # b列の生成
7   awk '$1 < $2 && 500 < ($1+$2) {print $1, $2, sqrt(($1)^2 + ($2)^2)}' \
8   | # c列候補の生成
9   awk 'length($3) == 3' \
10  | # c列の抽出
11  awk '$1+$2+$3 == 1000' \
12  | # a+b+c = 1000 となる1組の抽出
13  tr ' ' '*' \
14  | # 計算式の生成
15  bc
16    # 計算結果の出力

解説

$a, b, c$ の候補を列挙し、その中から $a + b + c = 1000$ を満たすものを抽出すれば良い。

$a, b, c$ の候補を絞り込むために、問題文から $a, b, c$ の性質を考える。
まず、 $a \lt b \lt c$ かつ $a + b + c = 1000$ より、 $a \le 332$ である。
次に、 $a + b + c = 1000$ かつ $b \lt c$ より、 $b \lt 500$ である。
よって、 $a + b + c = 1000$ 、 $a \lt b \lt c$ 、 $a \le 332$ 、 $b \lt 500$ を4つの条件全てを満たす $a, b, c$ の全候補を、列挙すれば良い。

初めに、 $a, b, c$ の候補を列挙する。
これは、3~9行目のsedとawkによっておこなう。
列挙する候補を減らすために、上記の性質を利用して、 $a$ の上限は332まで、 $b$ の上限は499までとする。

次に、 $a + b + c = 1000$ を満たす1組を抽出する。
これは、11行目のawkによっておこなう。

最後に、積 $abc$ を算出する。
積の算出は、13~15行目のtrとbcによっておこなっている。

以上が、 $a \lt b \lt c$ かつ $a + b + c = 1000$ を満たすピタゴラス数の積、 $abc$ を算出する方法である。

雑記

「こんな別解があるよ」や、「こうすればもっと効率化できるぜ」、「こう書けばエレガントですわよ」等の意見がありましたら、気軽に教えていただけますと幸いです🐺
現在の進捗状況 -> https://github.com/gin135/Project_Euler/tree/master/sh
何だか、今回の解法は泥臭いというか、いつもに増して洗練されていない気がする...
- 特に、3~9行目。もうちょっと良い方法があるような......
- 実質、3重ループを回しているようなものだし、速度的にも少し不安。
- この性質を利用すれば、もっとスマートな解法で解けるのかも。 >> "ピタゴラス数のある性質" http://www004.upp.so-net.ne.jp/s_honma/pythagoras/pythagoras2.htm

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

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

概要

実行環境

問題文

解法

解説

雑記