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

概要

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

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

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

実行環境

• Arch Linux (x86_64, 4.5.4-1-ARCH)
• bash (4.3.42, POSIX互換モード)
• GNU coreutils (8.25)

• gawk (4.1.3)
  
  

• usp Personal Tukubai(20160402、別解のみ使用)

問題文

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

Distinct powers

Consider all integer combinations of $a^b$ for $2 \le a \le 5$ and $2 \le b \le 5$:

2^2=4,\hspace{0.5em}2^3=8,\hspace{0.5em}2^4=16,\hspace{0.5em}2^5=32 \\
3^2=9,\hspace{0.5em}3^3=27,\hspace{0.5em}3^4=81,\hspace{0.5em}3^5=243 \\
4^2=16,\hspace{0.5em}4^3=64,\hspace{0.5em}4^4=256,\hspace{0.5em}4^5=1024 \\
5^2=25,\hspace{0.5em}5^3=125,\hspace{0.5em}5^4=625,\hspace{0.5em}5^5=3125

If they are then placed in numerical order, with any repeats removed, we get the following sequence of 15 distinct terms:

4, 8, 9, 16, 25, 27, 32, 64, 81, 125, 243, 256, 625, 1024, 3125

How many distinct terms are in the sequence generated by $a^b$ for $2 \le a \le 100$ and $2 \le b \le 100$?

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

個別のべき乗

$2 \le a \le 5$ と $2 \le b \le 5$について, $a^b$ を全て考えてみよう:

2^2=4,\hspace{0.5em}2^3=8,\hspace{0.5em}2^4=16,\hspace{0.5em}2^5=32 \\
3^2=9,\hspace{0.5em}3^3=27,\hspace{0.5em}3^4=81,\hspace{0.5em}3^5=243 \\
4^2=16,\hspace{0.5em}4^3=64,\hspace{0.5em}4^4=256,\hspace{0.5em}4^5=1024 \\
5^2=25,\hspace{0.5em}5^3=125,\hspace{0.5em}5^4=625,\hspace{0.5em}5^5=3125

これらを小さい順に並べ, 同じ数を除いたとすると, 15個の項を得る:

4, 8, 9, 16, 25, 27, 32, 64, 81, 125, 243, 256, 625, 1024, 3125

$2 \le a \le 100$, $2 \le b \le 100$ で同じことをしたときいくつの異なる項が存在するか?

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

解法

1   #!/bin/sh
2   
3   seq 2 100 \
4   | # aの候補列の生成
5   awk '{for(i=2; i<=100; i++){print $0,i}}' \
6   | # a候補列に対して、bの候補列を生成
7   tr ' ' '^' \
8   | # 各組み合わせに関して計算式$a^b$を生成
9   BC_LINE_LENGTH=0 bc \
10  | # 式の計算
11  sort -n \
12  | # 出力を数値順・昇順にソート
13  uniq \
14  | # 重複の除去
15  grep -c ''
16    # 項数の出力

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

seq 2 100 | awk '{for(i=2; i<=100; i++){print $0,i}}' | tr ' ' '^' | BC_LINE_LENGTH=0 bc | sort -n | uniq | grep -c ''

解説

まず、解答方針を述べる。

今回の設問では、$a$と$b$の全組み合わせに関して$a^b$を列挙し、重複した値を取り除いた後、項数を求めれば良い。

---

次に、ソースコードの解説を述べる。

まず、$a$の候補を生成する。
この処理は、3行目のseqを用いておこなう。

次に、生成した$a$の候補に対して、$b$の候補を生成する
この処理は、5行目のawkを用いておこなう。

そして、生成した$a$、$b$の組み合わせに対して、$a^b$を算出する。
この処理は、7行目のtrと9行目のbcを用いておこなう。
まず、各レコードに対して、trで累乗記号を付加する。
その後、bcによって$a^b$を算出する。

最後に、一意な項数を求める。
この処理は、11行目のsort、13行目のuniq、15行目のgrepを用いておこなう。
まず、重複したレコードを除去するための下準備として、sortによって入力を数値順に整列する。
次に、uniqによって重複したレコードを除去する。
そして、grepによってレコード数を出力する。

以上が、$2 \le a \le 1000$、$2 \le b \le 1000$の範囲において、重複しない$a^b$の項数を求める方法である。

参考にしたもの

(特に無し)

雑記

• 「こんな別解があるよ」や、「こうすればもっと効率化できるぜ」、「こう書けばエレガントですわよ」等の意見がありましたら、気軽に教えていただけますと幸いです🐺

• 現在の進捗状況 -> https://github.com/gin135/Project_Euler/tree/master/sh
  
  

• @eban さんが、ご自身の日記にて別解を投稿していらっしゃいます。

  • "Project Euler Problem 29 #シェル芸 - jarp," http://jarp.does.notwork.org/diary/201602b.html#201602121
  • シェルのブレース展開を活用して、非常にシンプルな解答をしていらっしゃいます。
  • また、rubyによるワンライナー解答も投稿していらっしゃいます。
    
    

• 今回の問題は、シェルスクリプト(シェル芸)だと簡単！

  • 大量のデータを列挙・整列・重複除去するのは、シェルが得意とする処理だと思う。

• 別解として、usp Tukubaiコマンドを使うと、ちょっとだけシンプルになる...かも？

#!/bin/bash

loopx <(seq 2 100) <(seq 2 100) \
| # a,bの全組み合わせの列挙
gawk -M '$0=$1^$2' \
| # 各組み合わせに対してa^bを出力(桁数が大きくなるので、MPFRを有効にする)
sort -n \
| # 数値順にソート
uniq \
| # 重複の除去
gyo
  # 項数の出力

---

---

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

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

3. 9183 ↩