Help us understand the problem. What is going on with this article?

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

More than 3 years have passed since last update.

概要

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

しかし、シェル芸2による解答は、私が探した限りでは、殆ど見つからなかった。
そこで、私自身の勉強も兼ねて、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$ を計算しなさい.

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

解法

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 

gin_135
Unixが好きです。シェルが好きです。面倒臭いのは好きじゃないです。
http://harpyja.daemon.asia
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away