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

概要

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

---

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

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

3. 31875000 ↩