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

概要

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

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

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

実行環境

• Arch Linux (x86_64, 4.3.3-2-ARCH)
• bash (4.3.42, POSIX互換モード)
• GNU coreutils (8.24)

問題文

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

$2^{15} = 32768$ and the sum of its digits is $3 + 2 + 7 + 6 + 8 = 26$.
What is the sum of the digits of the number $2^{1000}$ ?

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

$2^{15} = 32768$ であり, これの数字和 ( 各桁の和 ) は $3 + 2 + 7 + 6 + 8 = 26$ となる.
同様にして, $2^{1000}$ の数字和を求めよ.

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

解法

prob_016.sh

1	#!/bin/sh
2	
3	echo '2^1000' \
4	| # 2^1000の算出式の生成
5	bc \
6	| # 2^1000の出力
7	tr -d '\\\n' \
8	| # bcの出力の整形
9	grep -o . \
10	| # 列->行変換
11	xargs \
12	| # 行->列変換
13	tr ' ' '+' \
14	| # 総和算出式の生成
15	bc
16	  # 総和の出力

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

echo '2^1000' | bc | tr -d '\\\n' | grep -o . | xargs | tr ' ' '+' | bc

解説

単純に $2^{1000}$ を算出し、その数字和を求めれば良い。

まず、 $2^{1000}$ を算出する。
この処理は、3~7行目のecho, bc, trを用いておこなう。
bcは、デフォルトでは出力を70字毎に改行するため、7行目のtrによって出力を整形する。

そして、数字和(総和)を求める。
この処理は、9~15行目のgrep, xargs, tr, bcを用いておこなう。
3~7行目で算出した $2^{1000}$ の値を、grepとxargsを用いて1字毎に分離する。
その後、trによって総和の算出式を生成し、bcによって総和を求めている。

以上が、 $2^{1000}$ の数字和を求める方法である。

雑記

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

• 今回の問題は、これ以上無いくらいシンプル。
• 問題とは全然関係無いけれど、grep -oとxargsを用いた行列変換が好き。
  • grep -oで一度列->行変換してから、xargsで再度行->列に戻すと、ちょうどtrに渡しやすい書式になっている点が面白い。
  • こう、向きを縦方向にしたり横方向に戻したり、データをこねくり回すのが、何だか楽しい。

---

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

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

3. 1366 ↩