jqコマンドでAtCoder Beginners Selectionを解いてみた

#TL; DR
- 普段はjsonの加工に使われる`jq`コマンドで
- [AtCoder Beginners Selection](https://atcoder.jp/contests/abs)(≒[drkenさんの精選10問](https://qiita.com/drken/items/fd4e5e3630d0f5859067))を
- 解いてみたよ！（ただし１問はおそらくTLEする）

#jqコマンドって？

主にJSONを加工するのに使われるコマンドです。
例えば、以下のjsonを考えます。

```json:input.json
[{ "shop": "横浜", "area": "関東", "sales": 100 },
 { "shop": "盛岡", "area": "東北", "sales": 300 },
 { "shop": "前橋", "area": "関東", "sales": 500 }]
```

このjsonに対して、関東エリアの売り上げの合計を求めて、末尾に「万円」をつけて出力したいと思います。
jqを使うと、以下のような短いコマンドで実現することができます。

```shell
$ jq 'map(select(.area == "関東") | .sales) | "\(add)万円"' input.json
"600万円"
```


jqコマンドの細かい機能については[jq Manual](https://stedolan.github.io/jq/manual/)(英語)と、このドキュメントの日本語訳記事である『[軽量JSONパーサー『jq』のドキュメント：『jq Manual』をざっくり日本語訳してみました](https://dev.classmethod.jp/tool/jq-manual-japanese-translation-roughly/)』に大変詳しいです。
本記事では、jqコマンドの説明はAtCoder Beginners Selectionを解くための最低限の説明に留めます。

## jqのフィルターの仕組み

jqコマンドの一つ目の引数をフィルターと呼びます。

フィルターは　パイプ(|)で繋がれた複数のフィルターの形をしています。

```
フィルター := フィルター | フィルター | フィルター ...
```

### 単一のデータが入力として渡される例

以下の例は、フィルターの入力として`1`が渡され、最終的に`"数字は12"`が出力される例です。

```shell
$ echo 1 | jq ' . * 2 | . + 10 | tostring | "数字は" + .'
"数字は12"
```

以下のように処理が進みます。

- `1`はまず最初に `. * 2`というフィルターの入力として渡されます。このフィルター中の`.`は入力を表します。出力は入力を２倍した値、すなわち`2`になります。
- その次に`2`は `.  + 10`というフィルターの入力となり、`12`が出力されます。
- `12`は`tostring`というフィルターの入力となり、 `"12"`が出力されます。
- `"12"`は`"数字は" + .`というフィルターの入力となり、 最終的に`"数字は12"`が出力されます。


### 複数のデータが入力として渡される例

フィルターには**複数のデータ**が入力として渡され得ます。**複数のデータ**と１つの**配列**を渡すのはjqでは区別されていることに注意してください。 

```shell
$ echo '1 2 3' | jq ' . * 2 | . + 10 | tostring | "数字は" + .'
"数字は12"
"数字は14"
"数字は16"
```

## 今回よく出てくる機能

###.

データ自身を表します。

```shell
$ echo 1 | jq '.'
1
```

###select(条件)

データを下流に流すかどうかを振り分けます。
`条件`が真のときはデータを素通りさせ、`条件`が偽のときはデータを流しません。

```shell
$ echo '1 2 3 4 5' | jq 'select(. > 2)'
3
4
5
```

###range(begin; end)
begin (begin+1) (begin+2) ... (end-1)の**複数の数値データ**を生成します。

```shell
$ echo '{}' | jq 'range(1;5)'
1
2
3
4
```

### [複数のデータ]

**複数のデータ**を一つの**配列**にまとめ上げます。

```shell
$ echo '{}' | jq '[range(1;5)]'
[
  1,
  2,
  3,
  4
]
```

###[]

**配列**を**複数のデータ**に分解します。

```shell
$ echo '[1, 2, 3]' | jq '.[]'
1
2
3
```

###as $name
データを変数に束縛します。

```shell
$ echo 3 | jq '. as $input | . * 10 | . + $input'
33
```

###map(*フィルター*)
**配列**のそれぞれの要素に*フィルター*を適用します。

```shell
$ echo '[1, 2, 3]' | jq 'map(. * 10)'
[
  10,
  20,
  30
]
```

###[*i*]
配列のi番目の要素を取り出します。

```shell
$ echo '[1, 2, 3]' | jq '.[2]'       
3
```

あとは問題の解答を見ながら解説していきます。

#問題＆解答

##断り書き
Otoshidamaは間違いなくTLEします。
実行コマンドは`jq -rRs -f code.jq input`で、入力コードはファイル`code.jq`として保存され、テストケース入力はファイル`input`にあるとします。

それでは[AtCoder Beginners Selection](https://atcoder.jp/contests/abs)の問題の解答を載せていきます。問題へのリンクは各セクションのタイトルをクリックすると辿れます。


## [PracticeA - Welcome to AtCoder](https://atcoder.jp/contests/abs/tasks/practice_1)
```jq
split("\n") as $input |
($input[0] | tonumber) as $a |
($input[1] | split(" ")) as $second_line |
($second_line[0] | tonumber) as $b |
($second_line[1] | tonumber) as $c |
"\($a + $b + $c) \($input[2])"
```

数を３つ、文字列を１つ受け取り、数の和と文字列を１行にまとめて出力する問題です。

入力を改行で区切って得られた配列を、`$input`という変数に束縛しています
１行目を数値に変換して `$a`に束縛し、
2行目を空白で区切って数値に変換して`$b`, `$c`に束縛します。
jqでは、[文字列補間](https://ja.wikipedia.org/wiki/%E6%96%87%E5%AD%97%E5%88%97%E8%A3%9C%E9%96%93)は`"a + b = \($a + $b)"`のような形をとり、`\(`と`)`で囲まれた範囲が式として計算されて埋めこまれます。



## [ABC086A - Product](https://atcoder.jp/contests/abs/tasks/abc086_a)

```jq
split(" ") | map(tonumber) |
if (.[0] + .[1]) % 2 == 0 then "Even" else "Odd" end
```
２数の和の偶奇を判定する問題です。

入力を空白区切りで配列にし、それぞれの要素を文字列型から数値型に変換します。
２行目には要素が２つの**配列データが１つ**渡っています。
jqではifが使えるので、ifで偶奇を場合わけしています。
`.[0]`, `.[1]`でその配列の最初の値、２番目の値を取り出し足し合わせて、２で割ったあまりが０かどうか評価しています。

## [ABC081A - Placing Marbles](https://atcoder.jp/contests/abs/tasks/abc081_a)

```jq
split("") | map(select(. == "1")) | length
```

文字列中の1の数を数える問題です。

入力文字列を文字ごとに分解し、`"１"`と等しい要素のみを残し、最後に定義済みフィルター`length`で配列の長さを取得しています。


## [ABC081B - Shift only](https://atcoder.jp/contests/abs/tasks/abc081_b)
```jq
def twos(n): if n % 2 == 1 then 0 else 1 + twos(n / 2) end;
split("\n") | .[1] | split(" ") | map(tonumber | twos(.)) | min
```

与えられた数列のうち、2で割り切れる回数が一番少ない数について、その割り切れる回数を答える問題です。

jqでは関数/フィルターが定義できます。
1行目は、引数nを受け取り、nが２で何回割り切れるかを返す関数`twos(n)`を再帰で定義しています。
２行目では、入力の数列部分のみを抜き出し、 配列の各数に対して`twos`を適用して２で割り切れる回数の数列に変換し、`min`フィルターで最小の数を返しています。

## [ABC087B - Coins](https://atcoder.jp/contests/abs/tasks/abc087_b)
```jq
split("\n") | map(select(. != "") | tonumber) as $input |
[
    range(0; $input[0] + 1) as $a |
    range(0; $input[1] + 1) as $b |
    range(0; $input[2] + 1) as $c |
    select($a * 500 + $b * 100 + $c * 50 == $input[3])
] | length
```

５００円玉A枚、100円玉B枚,50円玉C枚を持っている中で、X円の払い方が何通りあるかを数える問題です。

`select(. != "")`は、split("\n")が末尾の改行の後を読んで空文字列を最後に生成するため、それを除くために必要になっています。
`range(0; $input[0] + 1)`により、0~Aのそれぞれのデータを生成し、それぞれを`$a`と名付けています。
そのそれぞれが`$a`に束縛された状況に対して、またさらに0~Bの`$b`を定義しています。`$c`も同様です。
全体として、`(A+1)*(B+1)*(C+1)`通りのデータが処理されています。
このうち、　`select($a * 500 + $b * 100 + $c * 50 == $input[3]` で、X円ぴったり払える`($a, $b, $c)`の組み合わせのみを残しています。
ここまで全体が`[`と`]`に囲まれていることによって、この払える組み合わせの数列が生成され、最後に`length`でその数を数えています。

## [ABC083B - Some Sums](https://atcoder.jp/contests/abs/tasks/abc083_b)
```jq
split(" ") | map(tonumber) as $input |
[
    range(1; $input[0] + 1) |
    select(
        tostring | split("") | map(tonumber) | add | $input[1] <= . and . <= $input[2]
    )
] | add
```

1以上N以下の整数のうち、各桁の和がA以上B以下であるものの和を求める問題です。
`range(1; $input[0] + 1)`で１以上N以下の整数**それぞれのデータ**を生成しているのですが、問題は次のselectの中身です。

それぞれのデータに対し、 「文字列化して、文字ごとに区切って、それぞれを数値にして、合計にして、 A以上B以下になっている」ようなものだけを残しています。あくまでも和を取ろうとしているのは加工した後の数ではなく、加工前の数なので、ここまでの加工処理を全部selectの中身に押し込めて、外では元の数字がパイプに流れるようにしています。
あとはこれを`[`と`]`で配列にまとめ上げて、`add`で合計するだけです。

## [ABC088B - Card Game for Two](https://atcoder.jp/contests/abs/tasks/abc088_b)
```jq
split("\n") | .[1] | split(" ") | map(tonumber) |
sort | reverse | to_entries |
(map(select(.key % 2 == 0) | .value) | add) - (map(select(.key % 2 == 1) | .value) | add)
```

配列を降順にソートして、偶数番目の和から奇数番目の和を引いて出力する問題です。
肝は `to_entries`です。これは、配列に用いると、それぞれの要素を `{key: 添字, value: 配列の値}`に変換して新たな配列を作ってくれます。
この新たな配列に対し`(map(select(.key % 2 == 0) | .value) | add)`で、それぞれの要素に対し「偶数番目の要素のみを残し、それぞれに対し`value`キーの値を取り出す」ことをして、その後配列の値を合計しています。奇数番目も同様です。

## [ABC085B - Kagami Mochi](https://atcoder.jp/contests/abs/tasks/abc085_b)
```jq
split("\n") | map(select(. != "")) | .[1:] | unique | length
```

与えられた数列が、何種類の異なる数からなっているか数える問題です。

まさにそれをする`unique`というフィルターがあるので、これを適用して配列の長さを数えるだけです。

## [ABC085C - Otoshidama](https://atcoder.jp/contests/abs/tasks/abc085_c)
```jq
split(" ") | map(tonumber) as $input | [
    range(0; $input[0] + 1) as $man_yen |
    range(0; $input[0] + 1 - $man_yen) as $gosen_yen |
    ($input[0] - $man_yen - $gosen_yen) as $sen_yen |
    [$man_yen, $gosen_yen, $sen_yen] |
    select(10000 * $man_yen + 5000 * $gosen_yen + 1000 * $sen_yen == $input[1])
] | if length > 0 then "\(.[0][0]) \(.[0][1]) \(.[0][2])" else "-1 -1 -1" end
```

合計N枚のお札で、合計金額がY円であることがありえるかどうか、ありえたらその組み合わせを一つ答える問題です。
１行目から７行目までの大きな`[]`でありえる組み合わせの配列を手に入れ、ありえる組み合わせが１個以上あるかどうかで場合分けしています。


## [ABC049C - 白昼夢 / Daydream](https://atcoder.jp/contests/abs/tasks/arc065_a)
```jq
if test("^(dream(er)?|erase(r)?)*$") then "YES" else "NO" end
```

与えられた文字列がある正規表現に一致するか判定する問題です。

jqにはまさに正規表現を扱う`test`というフィルターがあります。


## [ABC086C - Traveling](https://atcoder.jp/contests/abs/tasks/arc089_a)
```jq
def abs: [., -.] | max;
def reachable:
    (.[1] | abs) + (.[2] | abs) <= .[0] and
    (.[0] - (.[1] | abs) - (.[2] | abs)) % 2 == 0;

split("\n") | map(select(.!="")) |
(.[0] | tonumber) as $n |
.[1:] | map(split(" ") | map(tonumber)) as $constraints |
[$constraints[0]] +
[
    range(0; $n - 1) |
    [
        $constraints[. + 1][0] - $constraints[.][0],
        $constraints[. + 1][1] - $constraints[.][1],
        $constraints[. + 1][2] - $constraints[.][2]
    ]
] |
all(reachable)
```

最初に地点(0, 0)にいます。
「t秒後に地点(x, y)にいなければならない」という形の制約が複数与えられるので、それが満たせるかどうか判定する問題です。

ある制約と次の制約の繋がりを考えるのがめんどくさいので、制約間の差分をとって、全ての制約を
「(0, 0)からt秒後に地点(x, y)に移動できるか？」という形の制約に変換しています。
これに対し、ちょうどt秒後にその地点に到達可能であるかどうかのboolを返す`reachable`というフィルターを作り、`all`関数で、全ての制約が`reachable`であるかどうかをチェックしています。

# まとめ

jqコマンドは主にjsonの整形をするために使われるコマンドですが、そのフィルターの表現力はかなり高く、また、フィルターはかなり書きやすいし、記述量も少なくてすみます。そのおかげで、この記事に示したようにAtcoder Beginners Selectionの問題をかなり簡単に解くことができました。

jqコマンドの使いやすさ、言語としての面白さが伝わってくれたら幸いです。