Qiita Teams that are logged in
You are not logged in to any team

Log in to Qiita Team
Community
OrganizationAdvent CalendarQiitadon (β)
Service
Qiita JobsQiita ZineQiita Blog
3
Help us understand the problem. What is going on with this article?
@gin_135

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

More than 3 years have passed since last update.

概要

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

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

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

実行環境

  • Arch Linux (x86_64, 4.5.4-1-ARCH)
  • bash (4.3.42, POSIX互換モード)
  • GNU coreutils (8.25)
  • gawk (4.1.3)

問題文

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

Number spiral diagonals

Starting with the number $1$ and moving to the right in a clockwise direction a $5$ by $5$ spiral is formed as follows:

21 22 23 24 25
20  7  8  9 10
19  6  1  2 11
18  5  4  3 12
17 16 15 14 13

It can be verified that the sum of the numbers on the diagonals is $101$.
What is the sum of the numbers on the diagonals in a $1001$ by $1001$ spiral formed in the same way?

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

螺旋状に並んだ数の対角線

$1$から初めて右方向に進み時計回りに数字を増やしていき, $5\times5$の螺旋が以下のように生成される:

21 22 23 24 25
20  7  8  9 10
19  6  1  2 11
18  5  4  3 12
17 16 15 14 13

両対角線上の数字の合計は$101$であることが確かめられる.
$1001\times1001$の螺旋を同じ方法で生成したとき, 対角線上の数字の和はいくつか?

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

解法

1   #!/bin/sh
2   
3   seq 1 1001 \
4   | # 自然数1~1001の生成
5   awk 'NR==1{print $0; next} NR%2!=0{for(i=0;i<=3;i++){print $0*$0-($0-1)*i}}' \
6   | # 1と、1以外の奇数に基づいた対角成分の出力
7   awk '{s+=$0} END{print s}'
8     # 和の算出

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

seq 1 1001 | awk 'NR==1{print $0; next} NR%2!=0{for(i=0;i<=3;i++){print $0*$0-($0-1)*i}}' | awk '{s+=$0} END{print s}'

解説

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

初めに、螺旋の一辺の数字の数を、$n (1 \lt n かつ nは奇数)$とする。
このとき、一辺が$n$である螺旋の四隅にある4つの数値は、それぞれ次の式で求めることができる。

  • $n*n - (n-1)*3$
  • $n*n - (n-1)*2$
  • $n*n - (n-1)*1$
  • $n*n - (n-1)*0$

例えば、設問にある$5\times 5$の螺旋の場合、対角線上の数値は以下のようにして算出できる。

  • $n=3$のとき

    • $3*3 - (3-1)*3 = 3$
    • $3*3 - (3-1)*2 = 5$
    • $3*3 - (3-1)*1 = 7$
    • $3*3 - (3-1)*0 = 9$
  • $n=5$のとき

    • $5*5 - (5-1)*3 = 13$
    • $5*5 - (5-1)*2 = 17$
    • $5*5 - (5-1)*1 = 21$
    • $5*5 - (5-1)*0 = 25$

よって、螺旋を内側から一辺が$n\times n$として四隅の値を算出していき、$1$に加えてそれらの値の総和を求めれば良い。


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

まず、$1$から設問で要求されている螺旋の一辺の値までの整数を生成する。
この処理は、3行目のseqを用いておこなう。

次に、生成した整数に対して、螺旋の対角線上にある数値を求める。
解答方針で述べたように、$n$は$1 \lt n かつ 奇数$である。
よって、上記の条件に該当する整数に対して、前述した算出方法を用いて4つの数値を生成していく。
この処理は、5行目のawkを用いておこなう。

最後に、生成された対角線上の値の総和を求める。
この処理は、7行目のawkを用いておこなう。

以上が、$1001\times1001$の螺旋を生成したとき、対角線上の数値の総和を求める方法である。

参考にしたもの

(特に無し)

雑記

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

  • @eban さんが、ご自身の日記にて別解を投稿していらっしゃいます。

    • "Project Euler Problem 28 #シェル芸 - jarp," http://jarp.does.notwork.org/diary/201602b.html
    • $1$から順に差分を考える方法で、解答していらっしゃいます。
    • rubyによるワンライナーの他、awkを使った様々な手法を投稿していらっしゃいます。

  • 今回の解法はシンプルすぎて、何だかツマンナイ解答になってしまった...

    • なので、@eban さんと同様に、差分を利用する別解を考えようとしたのだけれど...
    • awkの仕様を正確に理解していなかったので、結局うまくいかなかったorz
    • ↓失敗例
    #!/bin/sh
    seq 1 1001 \
    | # 1から1001までの整数を生成
    awk 'BEGIN{i=2; j=1} {print $0,j,i; if(4<=j){j=1; i+=2; next}; j++; NR+=i}'
      # 1レコード目から順に、2,2,2,2,4,4,4,4,6,6,6,6,8,8,8,8...と複数レコード飛ばしで出力(するつもりだった...)
    
  • 別解を考えていて学んだこと。awkには2種類の組込変数が存在する。(http://www.kt.rim.or.jp/~kbk/gawk-30/gawk_11.html)

    • 1つ目は、awkの挙動に影響を及ぼすもの。FSOFSORSSUBSEPなど。
    • 2つ目は、awkの挙動に影響を及ぼさず、単に値がセットされるだけのもの。ARGCARGVFILENAMENRNFなど。
    • この違いをきちんと理解していなかったので、別解を考えようとした際に上手くいかなかった...
    • なので、NRの値を書き換えても、awkの動作には全く関係ないとのことorz
    • てか、awkにおけるNRって、レコードを処理する際に、単純にインクリメントされているだけだったのね...


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

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

  3. 669171001 

3
Help us understand the problem. What is going on with this article?
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
gin_135
Unixが好きです。シェルが好きです。面倒臭いのは好きじゃないです。

Comments

No comments
Sign up for free and join this conversation.
Sign Up
If you already have a Qiita account Login
3
Help us understand the problem. What is going on with this article?