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

概要

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

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

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

実行環境

• 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=8)]

The four adjacent digits in the 1000-digit number that have the greatest product are $9 × 9 × 8 × 9 = 5832$.

73167176531330624919225119674426574742355349194934 \\
96983520312774506326239578318016984801869478851843 \\
85861560789112949495459501737958331952853208805511 \\
12540698747158523863050715693290963295227443043557 \\
66896648950445244523161731856403098711121722383113 \\
62229893423380308135336276614282806444486645238749 \\
30358907296290491560440772390713810515859307960866 \\
70172427121883998797908792274921901699720888093776 \\
65727333001053367881220235421809751254540594752243 \\
52584907711670556013604839586446706324415722155397 \\
53697817977846174064955149290862569321978468622482 \\
83972241375657056057490261407972968652414535100474 \\
82166370484403199890008895243450658541227588666881 \\
16427171479924442928230863465674813919123162824586 \\
17866458359124566529476545682848912883142607690042 \\
24219022671055626321111109370544217506941658960408 \\
07198403850962455444362981230987879927244284909188 \\
84580156166097919133875499200524063689912560717606 \\
05886116467109405077541002256983155200055935729725 \\
71636269561882670428252483600823257530420752963450

Find the thirteen adjacent digits in the 1000-digit number that have the greatest product. What is the value of this product?

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

次の1000桁の数字のうち, 隣接する4つの数字の総乗の中で, 最大となる値は, 9 × 9 × 8 × 9 = 5832である.

73167176531330624919225119674426574742355349194934 \\
96983520312774506326239578318016984801869478851843 \\
85861560789112949495459501737958331952853208805511 \\
12540698747158523863050715693290963295227443043557 \\
66896648950445244523161731856403098711121722383113 \\
62229893423380308135336276614282806444486645238749 \\
30358907296290491560440772390713810515859307960866 \\
70172427121883998797908792274921901699720888093776 \\
65727333001053367881220235421809751254540594752243 \\
52584907711670556013604839586446706324415722155397 \\
53697817977846174064955149290862569321978468622482 \\
83972241375657056057490261407972968652414535100474 \\
82166370484403199890008895243450658541227588666881 \\
16427171479924442928230863465674813919123162824586 \\
17866458359124566529476545682848912883142607690042 \\
24219022671055626321111109370544217506941658960408 \\
07198403850962455444362981230987879927244284909188 \\
84580156166097919133875499200524063689912560717606 \\
05886116467109405077541002256983155200055935729725 \\
71636269561882670428252483600823257530420752963450

この1000桁の数字から13個の連続する数字を取り出して, それらの総乗を計算する. では、それら総乗のうち、最大となる値はいくらか.
EX 6桁の数123789から5個の連続する数字を取り出す場合, $12378$と$23789$の二通りとなり, 後者の$23789=3024$が最大の積となる.

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

解法

prob_008.sh

1	#!/bin/sh
2	
3	(cat << EOS
4	73167176531330624919225119674426574742355349194934
5	96983520312774506326239578318016984801869478851843
6	85861560789112949495459501737958331952853208805511
7	12540698747158523863050715693290963295227443043557
8	66896648950445244523161731856403098711121722383113
9	62229893423380308135336276614282806444486645238749
10	30358907296290491560440772390713810515859307960866
11	70172427121883998797908792274921901699720888093776
12	65727333001053367881220235421809751254540594752243
13	52584907711670556013604839586446706324415722155397
14	53697817977846174064955149290862569321978468622482
15	83972241375657056057490261407972968652414535100474
16	82166370484403199890008895243450658541227588666881
17	16427171479924442928230863465674813919123162824586
18	17866458359124566529476545682848912883142607690042
19	24219022671055626321111109370544217506941658960408
20	07198403850962455444362981230987879927244284909188
21	84580156166097919133875499200524063689912560717606
22	05886116467109405077541002256983155200055935729725
23	71636269561882670428252483600823257530420752963450
24	EOS
25	) \
26	| # 設問で与えられた文字列の出力
27	tr -d '\n' \
28	| # 文字列を1行の数値に変換
29	awk 'BEGIN{FS=""} {ORS=""; for(i=1; i<=NF-12; i++){for(j=0; j<=12; j++){print $(i+j) " "}; print "\n"}}' \
30	| # 13個の連続する数字の全組合せを出力
31	grep -v '0' \
32	| # '0'が含まれる組合せの除去(n*0=0であるため)
33	tr ' ' '*' \
34	| # 積の算出式の生成
35	sed -e 's/\*$//' \
36	| # 各行それぞれについて、末尾の余分な演算子'*'の除去
37	bc \
38	| # 各行それぞれについて、積を出力
39	sort -n \
40	| # 積のソート
41	tail -1
42	  # 積の最大値の抽出

解法の解説

与えられた1000桁の数値を、先頭から13字毎に走査していき、総乗の全組合せを列挙する。
その組合せの中から、最大値になるものを取り出せば良い。

まず、3行目のcatによって、与えられた文字列を出力する。
ここで、与えられた文字列は固定長で改行されているため、1行の文字列(数値)に変換する必要がある。
具体的には、27行目のtrによって改行コードを除去し、1行の数値に変換している。

次に、1000桁の数値を、先頭から13字毎に走査していき、総乗を算出する全組合せを列挙する。
この処理は、29行目のawkで多重ループを用いることでおこなう。
列挙した組合せのうち、'0'が含まれているものは、総乗が0になることが自明である。
そのため、31行目のgrepを用いて、'0'が含まれている組合せを除去する。

そして、組合せを列挙した後に、それぞれについて総乗を算出する。
具体的には、33~35のtrとsedで式を生成し、39行目のbcによって算出する。

最後に、総乗の全組合せの中から、最大値になるものを取り出す。
これは、39~41行目のsortとtailを用いておこなう。
sortで総乗を数値順に昇順で並び替えた後、tailで一番最後の値(最大値)を出力すれば良い。

以上が、1000桁の数値から連続する13桁の数値を取り出した際、最大となる総乗値を算出する方法である。

参考にしたもの

• ヒアドキュメントとパイプ - odz buffer 〈http://d.hatena.ne.jp/odz/20070215/1171560784〉

  • 解法とは直接は関係無いけれど、あるコマンドに入力をヒアドキュメントで与えた際、パイプをヒアドキュメントの後に置くやり方の参考になった。
  • コマンドとヒアドキュメント自体を'()'で括り、サブシェル扱いで動作させれば可能だった。多謝。
  • ↓こんな感じ。

  $ cmd1 << EOS | cmd2 | cmd3 | ...      # 一般的なパイプの繋げ方
  hogehoge
  EOS
  $ (cmd1 << EOS                         # サブシェルを用いたパイプの繋げ方
  hogehoge
  EOS
  ) | cmd2 | cmd3 | ...
  

雑記

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

• 何でヒアドキュメントとパイプの記法に拘るかについて。

  • 個人的な考えだけれど、シェル芸の書き方は、データが上から下へ一方的に流れるような記法にしたいんだよね...
  • なので、パイプはヒアドキュメントの開始直後ではなく、終了直後に書きたい。
  • ↓一般的なパイプの繋げ方だと、見た目が美しくない。

  # 一般的なパイプの繋げ方を用いた場合のシェル芸記法(勝手に命名)
  cmd1 << EOS |
  hogehoge
  EOS                 # このcmd1とcmd2の繋ぎだけが特殊な書き方で、統一感が無い。cmd1の出力は横方向に流れているみたい...
  cmd2 \
  |
  cmd3 \
  |
  ...
  
  # サブシェルを用いた場合のシェル芸記法
  (cmd1 << EOS
  hogehoge
  EOS
  ) \
  |                   # やっぱり、データは下に流れていかないと。
  cmd2 \
  |
  cmd3 \
  |
  ...
  

• (Problem 1から毎日投稿してきましたが、休日・祝日はお休みいたします。)

---

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

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

3. 23514624000 ↩