概要

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

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

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

実行環境

Arch Linux 4.4.28-1-lts
GNU bash 4.3.46
GNU coreutils 8.25-2
util-linux 2.28.2-1
grep (GNU grep) 2.26
sed (GNU sed) 4.2.2
gawk 4.1.4
usp Personal Tukubai (20160402、 Open usp Tukubaiで代用可能)

問題文

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

Pandigital products

We shall say that an $n$-digit number is pandigital if it makes use of all the digits 1 to $n$ exactly once; for example, the 5-digit number, 15234, is 1 through 5 pandigital.
The product 7254 is unusual, as the identity, $39 \times 186 = 7254$, containing multiplicand, multiplier, and product is 1 through 9 pandigital.
Find the sum of all products whose multiplicand/multiplier/product identity can be written as a 1 through 9 pandigital.
HINT: Some products can be obtained in more than one way so be sure to only include it once in your sum.

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

パンデジタル積

すべての桁に 1 から $n$ が一度だけ使われている数を$n$桁の数がパンデジタル (pandigital) であるということにしよう: 例えば5桁の数 15234 は1から5のパンデジタルである.
7254 は面白い性質を持っている. $39 \times 186 = 7254$ と書け, 掛けられる数, 掛ける数, 積が1から9のパンデジタルとなる.
掛けられる数/掛ける数/積が1から9のパンデジタルとなるような積の総和を求めよ.
HINT: いくつかの積は, 1通り以上の掛けられる数/掛ける数/積の組み合わせを持つが1回だけ数え上げよ.

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

解法

01 #!/bin/sh
02 
03 (seq 1 9 |awk '{for(i=1234;i<=9876;i++){print $0,i}}'; seq 12 98 |awk '{for(i=123;i<=987;i++){print $0,i}}') | # 組み合わせの生成
04 awk '{print $1$2,$1*$2}'                                                                                     | # 積の出力
05 awk '!index($0,"0") && length($2)==4'                                                                        | # 0を含む＆積の桁数が4でない組み合わせの除去
06 grep -v '\(.\).*\1'                                                                                          | # 数字の重複がある組み合わせの除去
07 sort -k 2,2                                                                                                  | # 積についてソート
08 uniq -f 1                                                                                                    | # 積の重複を除去
09 awk '{s+=$2} END{print s}'                                                                                     # 積の総和の算出

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

(seq 1 9 |awk '{for(i=1234;i<=9876;i++){print $0,i}}'; seq 12 98 |awk '{for(i=123;i<=987;i++){print $0,i}}') | awk '{print $1$2,$1*$2}' | awk '!index($0, "0") && length($2)==4' | grep -v '\(.\).*\1' | sort -k 2,2 | uniq -f 1 | awk '{s+=$2} END{print s}'

解説

まず、解答方針を述べる。

今回の設問では、掛けられる数・掛ける数の組み合わせを列挙・乗算し、積を含めてパンデジタルになっている組み合わせを抽出すれば良い。
ただし、全組み合わせを列挙すると、計算量が莫大になってしまう。
そこで、今回の設問では、1から9のパンデジタルを求められている事に着目する。
1から9のパンデジタルという事は、 $(掛けられる数の桁数) + (掛ける数の桁数) + (積の桁数) = 9$という条件を満たす必要がある。
ここで、前述の条件を満たす数値の組み合わせは、$(1桁) * (4桁) = (4桁)$と$(2桁) * (3桁) = (4桁)$の2種類の式に限定される。
よって、上記2種類の式について、考えられる組み合わせ全てを列挙し、それぞれ条件を満たすかどうかを調べれば良い。

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

初めに、候補となる掛けられる数・掛ける数の組み合わせを生成する。
この処理は、3行目のseqおよびawkを用いておこなう。
ここでは、コマンドあたりの処理を短く済ませるために、"1桁 4桁"の組み合わせを生成する処理と、"2桁 3桁"の組み合わせを生成する処理を、別のコマンドラインに分けている。
そのため、次コマンドへの出力を一纏めにするために、これら複数のコマンドラインを、サブシェルとして実行させている。

次に、各組み合わせについて、それぞれ積を求める。
この処理は、4行目のawkを用いておこなう。

そして、条件を満たさない組み合わせを除去していく。
まず、数字'0'が含まれているものや、積の桁数が4でない組み合わせを除外する。
この処理は、5行目のawkのパターンを活用しておこなう。
次に、同じ数字が2回以上含まれている組み合わせを除外する。
この処理は、6行目のgrepを-vオプションを有効にすることによっておこなう。
任意の1字を包括指定子で括り、0字以上の任意の文字列の後に後方参照としてマッチングさせる事によって、数字の重複を判別している。

その後、設問で指定されているように、積が同一となる組み合わせの重複を除去する。
この処理は、7~8行目のsortおよびuniqを用いておこなう。
それぞれ、2フィールド目の積を対象として実行させる。

最後に、得られた積の総和を求める。
この処理は、9行目のawkを用いておこなう。

以上が、掛けられる数/掛ける数/積が1から9のパンデジタルとなるような積の総和を求める方法である。

解法2

01 #!/bin/bash
02 
03 (loopx <(seq 1 9) <(seq 1234 9876); loopx <(seq 12 98) <(seq 123 987))   | # 組み合わせの生成
04 awk '{print $1$2,$1*$2}'                                                 | # 積の出力
05 sed '/0/d; / ..../!d'                                                    | # 0を含む＆積の桁数が4でない組み合わせの除去
06 sed '/\(.\).*\1/d'                                                       | # 数字の重複がある組み合わせの除去
07 delf 1                                                                   | # 余分な1フィールド目の除去
08 sort                                                                     | # 積についてソート
09 uniq                                                                     | # 積の重複の除去
10 xargs plus                                                                 # 積の総和の算出

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

(loopx <(seq 1 9) <(seq 1234 9876); loopx <(seq 12 98) <(seq 123 987)) | awk '{print $1$2,$1*$2}' | sed '/0/d; / ..../!d' | sed '/\(.\).*\1/d' | delf 1 | sort | uniq | xargs plus

解説2

解法1を、一部usp Tukubaiコマンド群を用いて実装した。
処理の流れは、ほぼ解法1と同一である。
Tukubaiのloopx、delf、plusを用いることによって、一部処理を簡略化している。

参考にしたもの

(特に無し)

雑記

「こんな別解があるよ」や、「こうすればもっと効率化できるぜ」、「こう書けばエレガントですわよ」等の意見がありましたら、気軽に教えていただけますと幸いです🐺
現在の進捗状況 -> https://github.com/gin135/Project_Euler/tree/master/sh
@eban さんが、ご自身の日記にて別解を投稿していらっしゃいます。
- "Project Euler Problem 32 #シェル芸 - jarp," http://jarp.does.notwork.org/diary/201602b.html#201602171
- bashのブレース展開や、awkのパターンマッチングを駆使しして、より短いコードで解答していらっしゃいます。
今日は文化の日なので、あらゆる処理を1文化してしまう、風流なシェル芸の記事を書いた！
- (PEの記事、すごく久し振りに書いた気がする...)
ここ最近は私事が落ち着いてきたので、のんびり再開したいところ。
今回から、インデントスタイルをユニケージ開発風に変更してみた。
- Personal Tukubaiの中に、ユニケージスタイルにパイプ位置をそろえるコマンド、sb_pipealignが含まれていたので。
- sb_pipealignのお陰で、ユニケージスタイルに整形するのが簡単になったので、今回試しに変更してみた。
- 俺々シェル芸スタイルとユニケージ風スタイルの可読性に関しては、どちらも一長一短かも...

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

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

概要

実行環境

問題文

Pandigital products

パンデジタル積

解法

解説

解法2

解説2

参考にしたもの

雑記