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

概要

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

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

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

実行環境

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

問題文

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

If the numbers 1 to 5 are written out in words: one, two, three, four, five, then there are $3 + 3 + 5 + 4 + 4 = 19$ letters used in total.
If all the numbers from 1 to 1000 (one thousand) inclusive were written out in words, how many letters would be used?

NOTE: Do not count spaces or hyphens. For example, 342 (three hundred and forty-two) contains 23 letters and 115 (one hundred and fifteen) contains 20 letters. The use of "and" when writing out numbers is in compliance with British usage.

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

1 から 5 までの数字を英単語で書けば one, two, three, four, five であり, 全部で $3 + 3 + 5 + 4 + 4 = 19$ の文字が使われている.
では 1 から 1000 (one thousand) までの数字をすべて英単語で書けば, 全部で何文字になるか.

注: 空白文字やハイフンを数えないこと. 例えば, 342 (three hundred and forty-two) は 23 文字, 115 (one hundred and fifteen) は20文字と数える. なお, "and" を使用するのは英国の慣習.

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

解法

prob_017.sh

1	#!/bin/sh
2	
3	seq 1 1000 \
4	| # 1~1000の数字の生成
5	sed -e 's;.*;curl -s --retry 5 "http://www.wolframalpha.com/input/?i=&";' \
6	| # スクレイピングコマンドの生成
7	xargs -i sh -c {} \
8	| # スクレイピングの実行
9	grep 'pod_0200.push' \
10	| # 数字の英単語行の抽出
11	sed -e 's/[^:]*: "\(.*\)","mI.*/\1/' \
12	| # 数字の英単語の抽出
13	sed -e '/hundred /aand' \
14	| # 文字列"and"の追加
15	sed -e 's/^1/one/' \
16	| # 数字を英単語に変換
17	tr -d '\n -' \
18	| # アルファベット以外の文字の除去
19	wc -m
20	  # 文字数の出力

---

注意
今回のコードは、普通に実行すると処理時間が非常に長い＆Wolfram Alphaサーバに負担が掛かります。
そのため、Wolfram Alphaのhttp://www.wolframalpha.com/input/?i={1..1000}のソース(2016-01-12時点)を全て取得したダンプを用意しました。
試しに実行される場合は、以下のページにあるファイルを利用して、上記コードの3~7行目をzcat prob_017_wa_dump.gz等に書き換えて実行してください。
https://github.com/gin135/junk_files/blob/master/prob_017_wa_dump.gz

---

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

curl -L -s 'https://github.com/gin135/junk_files/blob/master/prob_017_wa_dump.gz?raw=true' | zcat | grep 'pod_0200.push' | sed -e 's/[^:]*: "\(.*\)","mI.*/\1/' | sed -e '/hundred /aand' | sed -e 's/^1/one/' | tr -d '\n -' | wc -m

解説

初めに、解答方針を述べる。

今回の設問では、質疑応答システム、Wolfram Alpha⁴を利用する。

Wolfram Alphaは、入力された文字列に対して、知識ベースから解答や関連する視覚的情報を含んだページを動的に生成する仕様となっている。
しかし、例外として数値の場合は、静的なページを表示するようになっている。
更に、数値に関するページには、その数値を英単語にしたテキストも含まれている。
今回は、この情報を活用する。

---

次に、ソースコードの解説を述べる。

まず、スクレイピングのためのコマンドを生成する。
この処理は、3~5行目のseqとsedを用いておこなう。
seqで1~1000までの整数を出力した後、sedによってWolfram Alphaの1~1000までの整数のページを取得するコマンドを生成する。

次に、スクレイピングを実行する。
この処理は、7行目のshによっておこなう。
生成したコマンドを単純にshに渡すことは出来ないため、xargsを用いてshに渡している。

そして、スクレイピングによって得られたデータから、必要な部分を抽出する。
この処理は、9~11行目のgrepとsedによっておこなう。
grepで英単語が含まれる行をフィルタリングした後、sedによって英単語だけを切り出す。

その後、文字数を数えるための前処理をする。
この処理は、13~17行目のsedとtrによっておこなう。
まず、英単語に"and"を適切に追記する。
Wolfram Alphaから得られた英単語は、"and"を含まない記法になっている為である。
13行目のsedによって、100以上の数値でかつ末尾が"hundred"でない単語のみに、"and"を追記する。
次に、数字'1'を英単語に変換する。
これは、Wolfram Alphaにおける1000以上の数値ページは、"1000未満の接頭数字 + 基数語"という表記になっているためである。
今回は1000しか該当しないため、15行目のsedで'1'を"one"に変換している。
そして、文字数を正確に数えるために、余分な文字(改行コード、スペース、ハイフン)を除去する。
具体的には、17行目のtrで除去している。

最後に、合計文字数を出力する。
この処理は、19行目のwcコマンドによっておこなう。
文字数だけを出力する-mオプションを用いることによって、合計文字数を出力している。

以上が、1から1000までの数字をすべて英単語で書いた時の文字数を求める方法である。

雑記

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

• この数字の英単語の規則は、きちんと定められているらしい。 >>
  "西洋の命数法 - Wikipedia" https://ja.wikipedia.org/wiki/%E8%A5%BF%E6%B4%8B%E3%81%AE%E5%91%BD%E6%95%B0%E6%B3%95

  • 知るかんなもん。
  • ここは日本だ。
  • I don't speak English.

• なので、Wolfram Alphaさんの力を借りることにした

  • だって、滅多に使わない命数法を覚えるの、面倒臭いじゃん...

• ※よいこはまねしてはいけません。

  prob_017_2.sh

  1	#!/bin/sh
  2	
  3	seq 1 1000 \
  4	| # 1~1000の数字の生成
  5	sed -e 's;.*;curl -s --retry 100 --retry-delay 2 "http://www.wolframalpha.com/input/?i=&";' \
  6	| # スクレイピングコマンドの生成
  7	xargs -P 0 -i sh -c {} \
  8	| # スクレイピングの並列実行(Wolfram Alphaさん、すいませんすいませんすいません...)
  9	grep 'pod_0200.push' \
  10	| # 数字の英単語行の抽出
  11	sed -e 's/[^:]*: "\(.*\)","mI.*/\1/' \
  12	| # 数字の英単語の抽出
  13	sed -e '/hundred /aand' \
  14	| # 文字列"and"の追加
  15	sed -e 's/^1/one/' \
  16	| # 数字を英単語に変換
  17	tr -d '\n -' \
  18	| # アルファベット以外の文字の除去
  19	wc -m
  20	  # 文字数の出力
  

  • 愚か者の末路。

  (Wolfram AlphaさんにHTTPリクエストを1000個並列に送ってしまったら、怒られてしまった... すんませんすんませんすんません...) pic.twitter.com/TgQ4IaKuiU

  — ginjiro (@gin_135) 2016, 1月 12

  - Wolfram Alphaさん、本当にすいませんでした...

---

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

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

3. 21124 ↩

4. Wolfram|Alpha: Computational Knowledge Engine (http://www.wolframalpha.com/) ↩