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

概要

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

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

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

実行環境

• Arch Linux (x86_64, 4.3.3-2-ARCH)
• bash (4.3.42)
• GNU coreutils (8.24)
• gawk (4.1.3)

問題文

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

A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 × 99.
Find the largest palindrome made from the product of two 3-digit numbers.

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

左右どちらから読んでも同じ値になる数を回文数という. 2桁の数の積で表される回文数のうち, 最大のものは 9009 = 91 × 99 である.
では, 3桁の数の積で表される回文数の最大値を求めよ.

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

解法

prob_004.sh

1	#!/bin/sh
2	
3	awk 'BEGIN {for(i=100; i<=999; i++){for(j=100; j<=999; j++){print i*j}}}' \
4	| # 3桁の2つの数値から構成される積の組合せの出力
5	sort -n \
6	| # 積のソート
7	uniq \
8	| # 積のうち、重複したものを除去
9	sed -e 's/./& /g' \
10	| # 数値を1字毎にスペース区切りで出力
11	awk '$1 == $NF && $2 == $(NF-1) && $3 == $(NF-2)' \
12	| # 回文数になっている行の出力
13	tail -n 1 \
14	| # 回文数のうち、最大値を出力
15	tr -d ' '
16	  # 区切りスペースの除去

解法の解説

まず、「3桁の数の積で表される回文数」を求める前準備として、3桁の2つの数値の積を出力する。
3行目のawkコマンドによって、それらの組み合わせを出力する。
具体的には、"100100", "100101", "100102", ..., "100999", "101100", "101101", "101102", ..., "999999"の、900^2通りである。

しかし、この900^2通りには、積が重複している組み合わせが存在する。
そのため、5行目のsortと7行目のuniqを組み合わせることによって、重複を除去している。

次に、「3桁の数の積で表される回文数」を求める。
これは、3~7行目の処理によって出力された積が、回文数であるかどうかを判定すればよい。
この処理は、sedとawkを用いておこなう。
9行目のsedで数値を1字毎にスペース区切りで出力した後、11行目のawkによって先頭・末尾フィールドから順に照合していく。
今回の問題では、扱う積は6桁の固定長である。
よって、11行目のawkで照合するフィールドは、処理を簡略化するために決め打ちとした。
上記の処理によって、「3桁の数の積で表される回文数」だけを抽出することができる。

そして、「3桁の数の積で表される回文数」のうち、最大値を求める。
5行目のsortによって、回文数は昇順にソートされている。
そのため、一番最後に出力された回文数が、最大値である。
13行目のtailによって、一番最後に出力される回文数のみを抽出する。

最後に、15行目のtrによって、回文判定に用いたスペース区切りを削除し、出力を整形する。

以上が、3桁の数の積で表される回文数の最大値を求める手順である。

雑記

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

• 回文の判定処理自体は、シェル芸だととても楽ちん。
  • sedで1文字毎のスペース区切りに加工し、awkで各フィールドを照合していくだけ。便利。
• でも、計算量がちょっと気になる...
  • 今回の場合、入力は高々900^2行なので、数秒で終わるけれど...
  • 桁数を4に増やすだけで、実行時間は凄まじく長くなってしまう。
  • もうちょっと効率の良い・汎用的な手法を思いつけるようになりたい。
• 計算量を考慮すると、初めに候補を大量に生成するのではなく、もうちょっと別のアプローチで解くのが良いのかもしれない。
  • ただ、初めにデータを大量生成し、それを各種コマンドでフィルタ＆加工していく方法は、処理内容を把握しやすい点が良い。
  • 可能なら、この方法で進めていきたい。
• 今回は、ちゃんと解説を書いたぞ...!!
  • やっぱりソースのまんまだけれど、気にしたら負け。

---

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

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

3. 906609 ↩