概要

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に渡しやすい書式になっている点が面白い。
- こう、向きを縦方向にしたり横方向に戻したり、データをこねくり回すのが、何だか楽しい。

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

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

概要

実行環境

問題文

解法

解説

雑記