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

概要

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

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

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

実行環境

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

問題文

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

Digit fifth powers

Surprisingly there are only three numbers that can be written as the sum of fourth powers of their digits:

$1634 = 1^4 + 6^4 + 3^4 + 4^4$
$8208 = 8^4 + 2^4 + 0^4 + 8^4$
$9474 = 9^4 + 4^4 + 7^4 + 4^4$

As $1 = 1^4$ is not a sum it is not included.
The sum of these numbers is $1634 + 8208 + 9474 = 19316$.
Find the sum of all the numbers that can be written as the sum of fifth powers of their digits.

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

各桁の5乗

驚くべきことに, 各桁を4乗した数の和が元の数と一致する数は3つしかない.

$1634 = 1^4 + 6^4 + 3^4 + 4^4$
$8208 = 8^4 + 2^4 + 0^4 + 8^4$
$9474 = 9^4 + 4^4 + 7^4 + 4^4$

ただし, $1=1^4$は含まないものとする. この数たちの和は $1634 + 8208 + 9474 = 19316$ である.
各桁を$5$乗した数の和が元の数と一致するような数の総和を求めよ.

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

解法

1	#!/bin/sh
2	
3	yes 高須クリニック \
4	| # お約束のやつ
5	awk '{s+=9^5; if(s<10^NR){exit}} END{print NR}' \
6	| # 各桁^5の総和の最大桁数の出力
7	awk '{for(i=1;i<=$0;i++){printf("9")}; print ""}' \
8	| # 探索範囲の終端の出力
9	xargs -Iend seq 0 end \
10	| # 0から999999までの整数の出力
11	grep -v '^1\{1,\}$' \
12	| # 例外(1のみで構成された値)の除去
13	awk -v FS='' '{s=0; for(i=1;i<=NF;i++){s+=$i^5}; print $0,s}' \
14	| # 整数および各桁^5の総和の出力
15	awk '$1==$2' \
16	| # 元の整数と累乗の総和が一致するレコードの抽出
17	awk '{s+=$1} END{print s}'
18	  # 抽出した整数の総和の出力

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

yes 高須クリニック | awk '{s+=9^5; if(s<10^NR){exit}} END{print NR}' | awk '{for(i=1;i<=$0;i++){printf("9")}; print ""}' | xargs -Iend seq 0 end | grep -v '^1\{1,\}$' | awk -v FS='' '{s=0; for(i=1;i<=NF;i++){s+=$i^5}; print $0,s}' | awk '$1==$2' | awk '{s+=$1} END{print s}'

解説

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

今回の設問では、考えられる組み合わせを全て列挙し、その中から各桁を5乗した値の和が元の値と一致するものを抽出し、和を求めれば良い。
ただし、設問で記載されている情報だけでは、探索する範囲を定めることができない。
そのため、前準備として、各桁を5乗した値の和が、元の値を超えないための、最大桁数を調べる。

---

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

始めに、解答方針で述べたとおり、探索範囲を決定する。
この処理は、3行目のyes、5行目と7行目のawkを用いておこなう。
まず、yesによって、適当な入力を生成する。
次に、生成した入力を利用し、awkによって探索範囲を決定する。
具体的には、5行目のawkで、各桁を5乗した値の和が元の値を超えないための最大桁数を、7行目のawkで、探索範囲の終端を出力する。

そして、解答方針で始めに述べたとおりに処理を進める。

まず、考えられる組み合わせを、全て列挙する。
この処理は、9行目のxargsおよびseqを用いておこなう。
7行目のawkによって得られた探索範囲の終端を、xargsによってseqへ引数として渡し、全組み合わせを列挙する。

次に、設問で言及されている例外(1のみで構成された値)を除去する。
この処理は、11行目のgrepを用いておこなう。

そして、各桁を5乗した値の和と、元の値が一致する組み合わせを抽出する。
この処理は、13行目と15行目のawkを用いておこなう。
13行目のawkで各桁を5乗した値の和を2フィールド目に出力した後、15行目のawkによって元の値と一致する組み合わせを抽出する。

最後に、抽出した組み合わせの総和を求める。
この処理は、17行目のawkを用いておこなう。

以上が、各桁を5乗した値の和が元の値と一致するものの総和を求める方法である。

参考にしたもの

(特に無し)

雑記

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

• @eban さんが、ご自身の日記にて別解を投稿していらっしゃいます。
  • "Project Euler Problem 30 #シェル芸 - jarp," http://jarp.does.notwork.org/diary/201602b.html#201602151
  • 該当する値が最大で6桁になることを利用し、awkでよりシンプルな解答をしていらっしゃいます。

• 今回の問題も、 @eban さんの解答と大部分が同じになってしまったorz

  • なので、完全なワンライナーにして、ちょっとだけオリジナリティを出してみた...つもり。
  • てか、awkに頼りすぎかも＞＜

• 今回問題を解くにあたり、xargsの-Iオプションのreplace-strに文字列が使用可能であることを、初めて知った。

  • @mutz0623 さんの資料↓によれば、xargsは特に指定されない限り、内部で/bin/echoを呼び出しているとのこと。

  • xargsコマンドの話.pdf https://t.co/36Gd6R5DEZ #シェル芸

    — むっつー (@mutz0623) 2014年12月13日

- きちんと調べてはいないけれど... `xargs`って、変数`replace-str`に引数を格納して、単に`echo`しているだけとか？

---

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

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

3. 443839 ↩