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

概要

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

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

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

実行環境

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

問題文

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

$n!$ means $n \times (n − 1) \times \dots \times 3 \times 2 \times 1$

For example, $10! = 10 \times 9 \times \dots \times 3 \times 2 \times 1 = 3628800$,
and the sum of the digits in the number $10!$ is $3 + 6 + 2 + 8 + 8 + 0 + 0 = 27$.

Find the sum of the digits in the number $100!$

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

$n \times (n - 1) \times \dots \times 3 \times 2 \times 1$ を $n!$ と表す.

例えば, $10! = 10 \times 9 \times \dots \times 3 \times 2 \times 1 = 3628800$ となる.
この数の各桁の合計は $3 + 6 + 2 + 8 + 8 + 0 + 0 = 27$ である.

では, $100!$ の各桁の数字の和を求めよ.

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

解法

prob_020.sh

1	#!/bin/sh
2	
3	seq 1 100 \
4	| # 1~100の整数の生成
5	xargs \
6	| # 行->列変換
7	tr ' ' '*' \
8	| # 階乗の算出式の生成
9	bc \
10	| # 階乗の出力
11	tr -d '\\\n' \
12	| # 出力の整形
13	grep -o '.' \
14	| # 列->行変換
15	xargs \
16	| # 行->列変換
17	tr ' ' '+' \
18	| # 各桁の数字の総和算出式の生成
19	bc
20	  # 総和の出力

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

seq 1 100 | xargs | tr ' ' '*' | bc | tr -d '\\\n' | grep -o '.' | xargs | tr ' ' '+' | bc

解説

純粋に100の階乗を算出し、各桁の数字を足し合わせれば良い。

この解法による処理の詳細は、コードに記載してあるコメントの通りである。

雑記

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

• 手抜き解説だけれど、シンプルな問題なので...
• (前回の問題がシェル芸的に面白かっただけに、今回はちょっと拍子抜けな感じ。)

---

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

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

3. 648 ↩