More than 5 years have passed since last update.

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

Last updated at 2016-01-22Posted at 2016-01-20

概要

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

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

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

実行環境

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

問題文

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

You are given the following information, but you may prefer to do some research for yourself.

1 Jan 1900 was a Monday.

Thirty days has September,
April, June and November.
All the rest have thirty-one,
Saving February alone,
Which has twenty-eight, rain or shine.
And on leap years, twenty-nine.

A leap year occurs on any year evenly divisible by 4, but not on a century unless it is divisible by 400.
How many Sundays fell on the first of the month during the twentieth century (1 Jan 1901 to 31 Dec 2000)?

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

次の情報が与えられている.

1900年1月1日は月曜日である.

9月, 4月, 6月, 11月は30日まであり, 2月を除く他の月は31日まである.

2月は28日まであるが, うるう年のときは29日である.

うるう年は西暦が4で割り切れる年に起こる. しかし, 西暦が400で割り切れず100で割り切れる年はうるう年でない.
20世紀（1901年1月1日から2000年12月31日）中に月の初めが日曜日になるのは何回あるか?

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

解法

prob_019.sh

1	#!/bin/sh
2	
3	seq 1901 2000 \
4	| # 1901~2000年までの数値の生成
5	sed 's/.*/LANG=c cal &/' \
6	| # 1901~2000年までのカレンダーを出力するコマンドの生成
7	xargs -P0 -I@ sh -c @ \
8	| # コマンドの(並列)実行
9	sed -n '/Su/{n; p}' \
10	| # 第一週目行の抽出
11	grep -o '7' \
12	| # 月初めが月曜になる月の抽出
13	grep -c ''
14	  # 月初めが月曜になる月の合計数の出力

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

seq 1901 2000 | sed 's/.*/LANG=c cal &/' | xargs -P0 -I@ sh -c @ | sed -n '/Su/{n; p}' | grep -o '7' | grep -c ''

解説

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

今回の問題では、calコマンドの出力結果を利用する。

まず、calの出力形式を示す。

$ LANG=c cal 2016
                               2016                               

       January               February                 March       
Su Mo Tu We Th Fr Sa   Su Mo Tu We Th Fr Sa   Su Mo Tu We Th Fr Sa
                1  2       1  2  3  4  5  6          1  2  3  4  5   
 3  4  5  6  7  8  9    7  8  9 10 11 12 13    6  7  8  9 10 11 12   
10 11 12 13 14 15 16   14 15 16 17 18 19 20   13 14 15 16 17 18 19   
17 18 19 20 21 22 23   21 22 23 24 25 26 27   20 21 22 23 24 25 26   
24 25 26 27 28 29 30   28 29                  27 28 29 30 31         
31                                                                   
        April                   May                   June        
Su Mo Tu We Th Fr Sa   Su Mo Tu We Th Fr Sa   Su Mo Tu We Th Fr Sa
                1  2    1  2  3  4  5  6  7             1  2  3  4   
 3  4  5  6  7  8  9    8  9 10 11 12 13 14    5  6  7  8  9 10 11   
10 11 12 13 14 15 16   15 16 17 18 19 20 21   12 13 14 15 16 17 18   
17 18 19 20 21 22 23   22 23 24 25 26 27 28   19 20 21 22 23 24 25   
24 25 26 27 28 29 30   29 30 31               26 27 28 29 30         
                                                                     
        July                  August                September     
Su Mo Tu We Th Fr Sa   Su Mo Tu We Th Fr Sa   Su Mo Tu We Th Fr Sa
                1  2       1  2  3  4  5  6                1  2  3   
 3  4  5  6  7  8  9    7  8  9 10 11 12 13    4  5  6  7  8  9 10   
10 11 12 13 14 15 16   14 15 16 17 18 19 20   11 12 13 14 15 16 17   
17 18 19 20 21 22 23   21 22 23 24 25 26 27   18 19 20 21 22 23 24   
24 25 26 27 28 29 30   28 29 30 31            25 26 27 28 29 30      
31                                                                   
       October               November               December      
Su Mo Tu We Th Fr Sa   Su Mo Tu We Th Fr Sa   Su Mo Tu We Th Fr Sa
                   1          1  2  3  4  5                1  2  3   
 2  3  4  5  6  7  8    6  7  8  9 10 11 12    4  5  6  7  8  9 10   
 9 10 11 12 13 14 15   13 14 15 16 17 18 19   11 12 13 14 15 16 17   
16 17 18 19 20 21 22   20 21 22 23 24 25 26   18 19 20 21 22 23 24   
23 24 25 26 27 28 29   27 28 29 30            25 26 27 28 29 30 31   
30 31

calの出力は、月毎にそれぞれ、1段目が"月名"、2段目が"曜日"、3段目以降が週ごとの"日にち"となっている。

ここで、3段目の第一週目の"日にち"の行に着目する。
「月の初めが日曜日」という事は、3段目の日にちが7個ある、言い換えると第一週目に数字の'7'が出現している事になる。
例えば、2016年の出力では、May(5月)のみが該当する。

$ LANG=c cal 2016 | grep -C 1 'Su'
       January               February                 March       
Su Mo Tu We Th Fr Sa   Su Mo Tu We Th Fr Sa   Su Mo Tu We Th Fr Sa
                1  2       1  2  3  4  5  6          1  2  3  4  5   
--
        April                   May                   June        
Su Mo Tu We Th Fr Sa   Su Mo Tu We Th Fr Sa   Su Mo Tu We Th Fr Sa
                1  2    1  2  3  4  5  6  7             1  2  3  4   
--
        July                  August                September     
Su Mo Tu We Th Fr Sa   Su Mo Tu We Th Fr Sa   Su Mo Tu We Th Fr Sa
                1  2       1  2  3  4  5  6                1  2  3   
--
       October               November               December      
Su Mo Tu We Th Fr Sa   Su Mo Tu We Th Fr Sa   Su Mo Tu We Th Fr Sa
                   1          1  2  3  4  5                1  2  3

つまり、該当する期間の全カレンダーをcalで出力し、第一週目に'7'が出現している回数を数えれば、月の初めが日曜から始まる数を求めることができる。

本設問では、上記の手順を実装すれば良い。

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

まず、1901年から2000年までのカレンダーを表示する。
この処理は、3~7行目のseq, sed, shを用いておこなう。
3行目のseqと5行目のsedでコマンドを生成した後、7行目のshに渡して実行している。
また、shでコマンドを実行する際、xargsを用いて実行を並列化している。

次に、カレンダーから第一週目の行を抽出する。
これは、単に曜日の次の行を抽出すれば良い。
この処理は、9行目のsedを用いておこなう。
パターンスペース自動出力を抑制する-nオプションを有効にし、正規表現によって曜日行をマッチングさせ、コマンドブロックを用いてマッチングした行の次の行のみを出力している。

そして、月初めが月曜になる月を抽出する。
これは、単に'7'を抽出すれば良い。
この処理は、11行目のgrepを用いておこなう。
-oオプションを指定することで、'7'をのみを抽出し、1行毎に出力している。

最後に、該当する月の合計数を求める。
11行目のgrepによって、'7'のみが1行毎に出力されている。
したがって、これは単に入力の行数を数えれば良い。
この処理は、13行目のgrepを用いておこなう。
-cオプションとパターン""(空)を指定することで、行数を出力している。

以上が、20世紀（1901年1月1日から2000年12月31日）中に月の初めが日曜日になる回数を求める方法である。

雑記

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

今回の解法は、個人的に特にお気に入り。
- 設問で与えられている情報を、完全に無視しているあたりが素敵。
- calコマンドの出力から、答えを強引に出している点もナイス。
- こういう他のプログラミング言語ではまず無理そうな手法で問題解決できるところが、シェル芸で一番楽しい

* 設問とは全然関係のない話。`cal 9 1752`の実行結果が面白い。 - これは、1752年の9月に、暦法がユリウス暦からグレゴリオ暦に移行したことが原因だそう。 - UNIX V7時代の`cal`コマンドでも、ちゃんと実装されている。 >> **[PDF]** "UNIX PROGRAMMER’S MANUAL Seventh Edition, Volume 1" http://plan9.bell-labs.com/7thEdMan/v7vol1.pdf - **(追記)** 2016-01-22現在、上記のサイトは繋がりにくくなっているようです。別の参照先として、UNIX V7の`cal`のソースコードへのリンクを記載します。 >> [http://minnie.tuhs.org/cgi-bin/utree.pl?file=V7/usr/src/cmd/cal.c](http://minnie.tuhs.org/cgi-bin/utree.pl?file=V7/usr/src/cmd/cal.c) * ちなみに、某F社のワープロは、上記の問題にきちんと対応していたとの事。

@gin_135 昔、F社のワープロだけが対応しているというので、話題になってた。苦情電話に「1年1月のカレンダーが他社と違う」と来たら、「それでは1752年9月をご覧ください」と返していたとか。
— tmnghryk (@tmnghryk) 2016, 1月 14

* (QiitaのTwitter連携投稿、ツイート内容を少し弄らせて欲しい... ハッシュタグ"#シェル芸"を付けたい。)

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

You get articles that match your needs
You can efficiently read back useful information
You can use dark theme

What you can do with signing up