LoginSignup
3
3

More than 5 years have passed since last update.

@gin_135

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

Posted at

概要

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

しかし、シェル芸2による解答は、私が探した限りでは、@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$乗した数の和が元の数と一致するような数の総和を求めよ.

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

解法

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 さんが、ご自身の日記にて別解を投稿していらっしゃいます。

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

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

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

    • @mutz0623 さんの資料↓によれば、xargsは特に指定されない限り、内部で/bin/echoを呼び出しているとのこと。
    • きちんと調べてはいないけれど... xargsって、変数replace-strに引数を格納して、単にechoしているだけとか？

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

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

  3. 443839 ↩

3
3
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
3
3