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

概要

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

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

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

実行環境

• Arch Linux (x86_64, 4.3.3-3-ARCH)
• bash (4.3.42, POSIX互換モード)
• GNU coreutils (8.24)
• gawk (4.1.3)
• curl (7.46.0)

問題文

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

Using names.txt (right click and 'Save Link/Target As...'), a 46K text file containing over five-thousand first names, begin by sorting it into alphabetical order. Then working out the alphabetical value for each name, multiply this value by its alphabetical position in the list to obtain a name score.

For example, when the list is sorted into alphabetical order, COLIN, which is worth $3 + 15 + 12 + 9 + 14 = 53$, is the 938th name in the list. So, COLIN would obtain a score of $938 \times 53 = 49714$.

What is the total of all the name scores in the file?

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

5000個以上の名前が書かれている46Kのテキストファイル names.txt を用いる. まずアルファベット順にソートせよ.
のち, 各名前についてアルファベットに値を割り振り, リスト中の出現順の数と掛け合わせることで, 名前のスコアを計算する.
たとえば, リストがアルファベット順にソートされているとすると, COLINはリストの938番目にある. またCOLINは $3 + 15 + 12 + 9 + 14 = 53$ という値を持つ. よってCOLINは $938 \times 53 = 49714$ というスコアを持つ.
ファイル中の全名前のスコアの合計を求めよ.

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

解法

prob_021.sh

1	#!/bin/sh
2	
3	curl -s 'https://projecteuler.net/project/resources/p022_names.txt' \
4	| # 単語データの出力
5	tr ',' '\n' \
6	| # 単語を行ごとに分離
7	tr -d '"' \
8	| # ダブルクォートの除去
9	LANG=c sort \
10	| # 単語をアルファベット順にソート
11	sed -e 's/./printf "%d " \\'\''&; /g' \
12	| # 単語に含まれる各文字を数値に変換するコマンドの生成
13	sed -e 's/$/echo/' \
14	| # 変換コマンドへ改行コマンドの付加
15	sh \
16	| # 文字->数値変換の実行
17	awk '{sc=0; for(i=1; i<=NF; i++){sc+=($i-64)}; print sc*NR}' \
18	| # 各行におけるスコアの算出
19	xargs \
20	| # 行->列変換
21	tr ' ' '+' \
22	| # 全名前スコア合計の算出式の生成
23	bc
24	  # 全名前スコア合計の出力

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

curl -s 'https://projecteuler.net/project/resources/p022_names.txt' | tr ',' '\n' | tr -d '"' | LANG=c sort | sed -e 's/./printf "%d " \\'\''&; /g' | sed -e 's/$/echo/' | sh | awk '{sc=0; for(i=1; i<=NF; i++){sc+=($i-64)}; print sc*NR}' | xargs | tr ' ' '+' | bc

解説

1文字毎に10進数ASCIIコードに変換し、それぞれの単語についてスコアを算出していけば良い。

今回の解法におけるポイントは、printf(1)である(シェルのBuilt-in、GNU printfのどちらでも良い)。
printfには、文字をASCIIコードへと変換する機能がある。(参考1)
利用するには、%d書式に対して、文字の前にシングルクォート(もしくはダブルクォート)を付けて実行すれば良い。

$ printf "%d\n" "'A"
65
$ printf %d\\n \"a
97

この機能を利用し、単語に含まれる文字全てをスコア化し、単語毎に集計していく。

その他の処理の解説は、コードに記載されているコメントの通りである。

参考にしたもの

1. "The printf command [Bash Hackers Wiki]" 〈http://wiki.bash-hackers.org/commands/builtin/printf〉

雑記

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

• printfで文字->ASCIIコード変換ができるのは、この問題を解いていて初めて知った。
  • n進数変換もbcを使えば簡単に実現できるし、シェルは本当に便利...!!
  • もう全部シェル芸で解決すれば良いんじゃないかな

• (私情により、来週はお休みいたします。)

---

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

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

3. 871198282 ↩