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

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

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

本記事では、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)

<!---
* bsd-games (2.17)
* curl (7.47.0)
--->

# 問題文
[原文 ([https://projecteuler.net/problem=28](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:
>
<div align="center">
<tt>
<font color=red>21</font> 22 23 24 <font color=red>25</font><br>
20 <font color=red>&nbsp;7</font> &nbsp;8 <font color=red>&nbsp;9</font> 10<br>
19 &nbsp;6 <font color=red>&nbsp;1</font> &nbsp;2 11<br>
18 <font color=red>&nbsp;5</font> &nbsp;4 <font color=red>&nbsp;3</font> 12<br>
<font color=red>17</font> 16 15 14 <font color=red>13</font>
</tt>
</div>
> 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](http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2028))]
#### 螺旋状に並んだ数の対角線

>$1$から初めて右方向に進み時計回りに数字を増やしていき, $5\times5$の螺旋が以下のように生成される:
>
<div align="center">
<tt>
<font color=red>21</font> 22 23 24 <font color=red>25</font><br>
20 <font color=red>&nbsp;7</font> &nbsp;8 <font color=red>&nbsp;9</font> 10<br>
19 &nbsp;6 <font color=red>&nbsp;1</font> &nbsp;2 11<br>
18 <font color=red>&nbsp;5</font> &nbsp;4 <font color=red>&nbsp;3</font> 12<br>
<font color=red>17</font> 16 15 14 <font color=red>13</font>
</tt>
</div>
>両対角線上の数字の合計は$101$であることが確かめられる.
>$1001\times1001$の螺旋を同じ方法で生成したとき, 対角線上の数字の和はいくつか?

正答は、注釈[^ans]に記載する。

# 解法
```sh
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	  # 和の算出
```

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

```sh
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](https://github.com/gin135/Project_Euler/tree/master/sh)
<br>

* @eban さんが、ご自身の日記にて別解を投稿していらっしゃいます。
    - "Project Euler Problem 28 #シェル芸 - jarp," [http://jarp.does.notwork.org/diary/201602b.html](http://jarp.does.notwork.org/diary/201602b.html)
    - $1$から順に差分を考える方法で、解答していらっしゃいます。
    - `ruby`によるワンライナーの他、`awk`を使った様々な手法を投稿していらっしゃいます。
<br>
<br>

* 今回の解法はシンプルすぎて、何だかﾂﾏﾝﾅｲ解答になってしまった...
    - なので、@eban さんと同様に、差分を利用する別解を考えようとしたのだけれど...
    - `awk`の仕様を正確に理解していなかったので、結局うまくいかなかったorz
    - ↓失敗例

    ```sh
    #!/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`の挙動に影響を及ぼすもの。`FS`、`OFS`、`ORS`、`SUBSEP`など。
    - 2つ目は、`awk`の挙動に影響を及ぼさず、単に値がセットされるだけのもの。`ARGC`、`ARGV`、`FILENAME`、`NR`、`NF`など。
    - この違いをきちんと理解していなかったので、別解を考えようとした際に上手くいかなかった...
    - なので、`NR`の値を書き換えても、`awk`の動作には全く関係ないとのことorz
    - てか、`awk`における`NR`って、レコードを処理する際に、単純にインクリメントされているだけだったのね...


- - -

[^pe]: About - Project Euler ([https://projecteuler.net](https://projecteuler.net))
[^def]: シェル芸の定義 >> シェル芸 - 上田ブログ ([https://blog.ueda.asia/?page_id=1434](https://blog.ueda.asia/?page_id=1434))
[^ans]: 669171001