AtCoder 精選過去問 10 問を F# ワンライナー で挑戦

前回は AtCoder 精選 10 問に JS ワンライナーで挑戦してみました。今回は同じ問題を F# ワンライナーで挑戦してみたいと思います。一度クリアしてる問題なので翻訳みたいなものですが（汗）今回は F# 固有の部分だけ解説（というかほぼ感想）します。ロジック自体の解説は[前回の記事](https://qiita.com/dsudo/items/e1abbd27b178ec8a4605)で書いてありますので割愛します。


## ルール

+ １行のラムダ関数の組み合わせで構成
+ { } は使わない ※コンピュテーション式が使えない！
+ 全部パイプラインでつなぐ（目指せ！パイプの達人）


## テンプレート

なしｗ
~~F# だと標準入力を一度に全部取れないため，全ての問題に共通な部分を作れませんでした。~~
（取れました |> 後述）
~~なので，~~入力から出力まで全て１行で書きます。
副作用を分離できていないのがちょっと気持ち悪いですが。。

あと，こんな感じでエントリーポイントを書かないといけないのかなと思いましたが・・・

``` fsharp
let solution (input : string) = "Hello " + input

[<EntryPoint>]
let main argv =
    stdin.ReadLine() |> solution |> printfn "%s"
    0
```

以下のような感じでもいけました。（今回はこれでいきます）

``` fsharp
stdin.ReadLine() |> fun input -> "Hello " + input |> printfn "%s"
```

**（追記）**

あ、、普通にこれで全部取れました💧

``` fsharp
stdin.ReadToEnd()
```

（stdin は System.Console.In のエイリアス）


## インデックス

まずはざっと解答一覧を並べてみます。こんな雰囲気です。

``` fsharp
// ABC086A - Product
stdin.ReadLine() |> fun x -> x.Split(' ') |> Array.map (int >> (&&&) 1) |> Array.reduce (fun a b -> a &&& b) |> fun x -> (if x = 1 then "Odd" else "Even") |> printfn "%s"

// ABC081A - Placing Marbles
stdin.ReadLine() |> fun x -> x.ToCharArray(0, x.Length) |> Array.map (fun x -> x.ToString() |> int) |> Array.reduce (fun a b -> a + b) |> printfn "%d"

// ABC081B - Shift only
stdin.ReadLine() |> ignore |> fun () -> stdin.ReadLine() |> fun x -> x.Split(' ') |> Array.map int |> Array.reduce (fun a b -> a ||| b) |> fun x -> System.Convert.ToString(x, 2) |> fun x -> x.Length - x.LastIndexOf('1') - 1 |> printfn "%d"

// ABC087B - Coins
(stdin.ReadLine(), stdin.ReadLine(), stdin.ReadLine(), stdin.ReadLine()) |> fun (a, b, c, x) -> (a |> int, b|> int, c|> int, x|> int) |> fun (a, b, c, x) ->  [0..(min a (x / 500))] |> List.map (fun i -> [0..(min b ((x - 500 * i) / 100))] |> List.filter (fun j -> x - 500 * i - 100 * j <= 50 * c) |> fun list -> list.Length ) |> List.sum |> printf "%d"

// ABC083B - Some Sums
stdin.ReadLine() |> fun x -> x.Split(' ') |> Array.map int |> fun x -> (x.[0], x.[1], x.[2]) |> fun (n, a, b) ->  [1..n] |> List.filter (fun ni -> ni.ToString() |> fun x -> x.ToCharArray(0, x.Length) |> Array.map (fun x -> x.ToString() |> int) |> Array.sum |> fun x -> x >= a && x <= b ) |> List.sum |> printfn "%d"

// ABC088B - Card Game for Two
stdin.ReadLine() |> ignore |> fun () -> stdin.ReadLine() |> fun x -> x.Split(' ') |> Array.map int |> Array.sortWith (fun a b -> b - a) |> Array.mapi (fun i x -> (i, x)) |> Array.fold (fun (a, b) (i, x) -> if i % 2 = 0 then (a + x, b) else (a, b + x) ) (0, 0) |> fun (a, b) -> a - b |> printfn "%d"

// ABC085B - Kagami Mochi
stdin.ReadLine() |> int |> fun x -> [1..x] |> List.map (fun _ -> stdin.ReadLine()) |> List.distinct |> List.length |> printfn "%d"

// ABC085C - Otoshidama
stdin.ReadLine() |> fun x -> x.Split(' ') |> Array.map int |> fun x -> (x.[0], x.[1] / 1000) |> fun (n, y) -> [0..(min 2000 (y / 10))] |> List.tryFind (fun i -> (y - n - 9 * i) |> fun x -> if x % 4 = 0 then (x / 4) |> fun j -> (n - i - j) |> fun k -> j >= 0 && k >= 0 else false) |> (fun i -> match i with | Some i -> ((y - n - 9 * i) |> fun x -> (x / 4) |> fun j -> (n - i - j) |> fun k -> sprintf "%d %d %d" i j k) | None -> "-1 -1 -1") |> printfn "%s"

// ABC049C - Daydream
stdin.ReadLine() |> fun input -> ["eraser"; "erase"; "dreamer"; "dream"] |> List.fold (fun acc word -> acc |> List.map (fun (x: string) -> x.Split([| word |], System.StringSplitOptions.None) |> Array.filter (fun x -> not (System.String.IsNullOrEmpty(x))) |> Array.toList) |> List.fold (fun a b -> a @ b) []) [input] |> List.length |> fun x -> (if x = 0 then "YES" else "NO") |> printfn "%s"

// ABC086C - Traveling
stdin.ReadLine() |> int |> fun x -> [1..x] |> List.map (fun _ -> stdin.ReadLine()) |> List.map (fun x -> x.Split(' ') |> Array.map int |> Array.toList) |> List.map (fun x -> (x.[0], x.[1], x.[2])) |> List.fold (fun acc (t2, x2, y2) -> match acc with | Some (t1, x1, y1) -> (if ((t2 &&& 1) = ((x2 + y2) &&& 1)) && ((t2 - t1) >= (abs (x2 - x1) + abs (y2 - y1))) then Some (t2, x2, y2) else None) | None -> None) (Some (0, 0, 0)) |> fun x -> (match x with | Some _ -> "Yes" | None -> "No") |> printfn "%s"
```


## １問目 [ABC086A - Product](https://abs.contest.atcoder.jp/tasks/abc086_a)

``` fsharp
stdin.ReadLine()
|> fun x -> x.Split(' ')
|> Array.map (int >> (&&&) 1)
|> Array.reduce (&&&)
|> fun x -> (if x = 1 then "Odd" else "Even")
|> printfn "%s"
```

https://atcoder.jp/contests/abs/submissions/9414632

[JavaScript版](https://qiita.com/dsudo/items/e1abbd27b178ec8a4605#%E8%A7%A3%E7%AD%94)

F# だとビットアンドが `&&&` なんですね。暗黙の型変換はないので，いったん `int` にしてます。

ちなみに `&` は match 式で使うみたいです。
参考：[シンボルと演算子のリファレンス](https://docs.microsoft.com/ja-jp/dotnet/fsharp/language-reference/symbol-and-operator-reference/)

あと，改行すると要らないけど，１行で書くときには括弧が必要になる場合があります。`if` とか `match` は括弧で囲わないでパイプでつなぐと最後のステート（例えば else の中の処理）にくっつくように推論されてしまいます。


## ２問目 [ABC081A - Placing Marbles](https://abs.contest.atcoder.jp/tasks/abc081_a)

``` fsharp
stdin.ReadLine()
|> fun x -> x.ToCharArray(0, x.Length)
|> Array.map (fun x -> x.ToString() |> int)
|> Array.reduce (fun a b -> a + b)
|> printfn "%d"
```

https://atcoder.jp/contests/abs/submissions/9414694

[JavaScript版](https://qiita.com/dsudo/items/e1abbd27b178ec8a4605#%E8%A7%A3%E7%AD%94-1)

う～ん。。文字列を１文字ずつの配列に変換するのが煩雑な印象です。
C# からのクラスのメソッドとか呼ぶ当たりが洗練されてない感じがしますね。

**(追記)**
コメントでこちらご提案頂きました！

``` fsharp
stdin.ReadLine()
|> Seq.map (string >> int)
|> Seq.sum
```

おぉ～！断然スッキリしてますね！

String は `IEnumerable<char>` を実装しているので Seq で操作可能なんですね。

``` fsharp
"abc" |> Seq.rev
// seq ['c'; 'b'; 'a']
```

また，`fun a b -> a + b` は `(+)` で置き換え可能なので，fold や reduce で使うと，よりスッキリ書けます。`(&&&)` や `(|||)` も同様です。

さらに `sumBy`（sum と map を組み合わせたもの）を使うとこうなります。

``` fsharp
stdin.ReadLine()
|> Seq.sumBy (string >> int)
```


## ３問目 [ABC081B - Shift only](https://atcoder.jp/contests/abs/tasks/abc081_b)

``` fsharp
stdin.ReadLine()
|> ignore
|> fun () -> stdin.ReadLine()
|> fun x -> x.Split(' ')
|> Array.map int
|> Array.reduce (|||)
|> fun x -> System.Convert.ToString(x, 2)
|> fun x -> x.Length - x.LastIndexOf('1') - 1
|> printfn "%d"
```

https://atcoder.jp/contests/abs/submissions/9414731

[JavaScript版](https://qiita.com/dsudo/items/e1abbd27b178ec8a4605#%E5%88%A5%E8%A7%A3-1)

入力の１行目は要らないので，`ignore` で捨ててから `unit` で始まる関数につなぐという無駄なことしてますｗ

結果の変数を取っておいて別のコンテキストで使いたいときにパイプラインでつなぐとスッキリ書けますね。


## ４問目 [ABC087B - Coins](https://atcoder.jp/contests/abs/tasks/abc087_b)

``` fsharp
(stdin.ReadLine(), stdin.ReadLine(), stdin.ReadLine(), stdin.ReadLine())
|> fun (a, b, c, x) -> (a |> int, b|> int, c|> int, x|> int)
|> fun (a, b, c, x) ->
  [0..(min a (x / 500))]
  |> List.sumBy (fun i ->
    [0..(min b ((x - 500 * i) / 100))]
    |> List.filter (fun j -> x - 500 * i - 100 * j <= 50 * c)
    |> List.length
  )
  |> printf "%d"
```

https://atcoder.jp/contests/abs/submissions/9416476

[JavaScript版](https://qiita.com/dsudo/items/e1abbd27b178ec8a4605#%E8%A7%A3%E7%AD%94-3)

入力４行の値が欲しいので，いったんタプルに入れて次に渡してます。

`int` で割り算すると自動的に切り捨て（`floor`）られるのを利用しています。
演算によって型が変わらないようになっているのが素晴らしいですね。


## ５問目 [ABC083B - Some Sums](https://atcoder.jp/contests/abs/tasks/abc083_b)

``` fsharp
stdin.ReadLine()
|> fun x -> x.Split(' ')
|> Array.map int
|> fun x -> (x.[0], x.[1], x.[2])
|> fun (n, a, b) -> 
  [1..n]
  |> List.filter (
    fun ni ->
      ni.ToString()
      |> Seq.sumBy (string >> int)
      |> fun x -> x >= a && x <= b
  )
  |> List.sum
  |> printfn "%d"
```

https://atcoder.jp/contests/abs/submissions/9414764

[JavaScript版](https://qiita.com/dsudo/items/e1abbd27b178ec8a4605#%E8%A7%A3%E7%AD%94-4)

分割代入的なことがしたかったので配列からタプルに変換してます。
入力が３つなのは分かっているので問題ありませんが，もし要素数が足りなければ例外がでます。

リストを渡して受け取り側で分割して受け取れないかなと思って以下のようなことしてみたら警告でました。

``` fsharp
let f = fun (a :: b :: [c]) -> printfn "%d, %d, %d" a b c
// warning FS0025: Incomplete pattern matches on this expression. For example, the value '[_;_;_;_]' may indicate a case not covered by the pattern(s).
```

要素が常に３つかどうかコンパイル時には分からないので当然ですね。
パターンマッチしてその他のケースも明示的に扱うようにすれば怒られません。

``` fsharp
let f =
  function
  | a :: b :: [c] -> printfn "%d, %d, %d" a b c
  | _ -> ()
```

でも，１行では書けないので却下ｗ


## ６問目 [ABC088B - Card Game for Two](https://atcoder.jp/contests/abs/tasks/abc088_b)

``` fsharp
stdin.ReadLine()
|> ignore
|> fun () -> stdin.ReadLine()
|> fun x -> x.Split(' ')
|> Array.map int
|> Array.sortWith (fun a b -> b - a)
|> Array.mapi (fun i x -> (i, x))
|> Array.fold (fun (a, b) (i, x) ->
  if i % 2 = 0
  then (a + x, b)
  else (a, b + x)
) (0, 0)
|> fun (a, b) -> a - b
|> printfn "%d"
```

https://atcoder.jp/contests/abs/submissions/9414786

[JavaScript版](https://qiita.com/dsudo/items/e1abbd27b178ec8a4605#%E8%A7%A3%E7%AD%94-5)

JS版では配列にしてたアキュムレーターをタプルにしてます。
（というか，JSでタプルがないから配列で代用してただけですが）

mapi はあるのに foldi はないので，いったん mapi で タプルにしてます。


## ７問目 [ABC085B - Kagami Mochi](https://atcoder.jp/contests/abs/tasks/abc085_b)

``` fsharp
stdin.ReadLine()
|> int
|> fun x -> [1..x]
|> List.map (fun _ -> stdin.ReadLine())
|> List.distinct
|> List.length
|> printfn "%d"
```

https://atcoder.jp/contests/abs/submissions/9414793

[JavaScript版](https://qiita.com/dsudo/items/e1abbd27b178ec8a4605#%E8%A7%A3%E7%AD%94-6)

この問題はJS版とロジックが変わってます。
F# では `distinct` があったので，こちらを使用するようにしました。

行数が可変なので，１行目の数分だけ ReadLine してます。
はじめて１行目を使いましたｗ


## ８問目 [ABC085C - Otoshidama](https://atcoder.jp/contests/abs/tasks/abc085_c)

``` fsharp
stdin.ReadLine()
|> fun x -> x.Split(' ')
|> Array.map int
|> fun x -> (x.[0], x.[1] / 1000)
|> fun (n, y) ->
  [0..(min 2000 (y / 10))]
  |> List.tryFind (
    fun i ->
      (y - n - 9 * i)
      |> fun x ->
        if x % 4 = 0
        then
          (x / 4)
          |> fun j ->
            (n - i - j)
            |> fun k -> j >= 0 && k >= 0
        else
          false
  )
  |> (
    fun i ->
      match i with
      | Some i -> (
        (y - n - 9 * i)
        |> fun x ->
          (x / 4)
          |> fun j ->
            (n - i - j)
            |> fun k -> sprintf "%d %d %d" i j k
      )
      | None -> "-1 -1 -1"
  )
  |> printfn "%s"
```

https://atcoder.jp/contests/abs/submissions/9414832

[JavaScript版](https://qiita.com/dsudo/items/e1abbd27b178ec8a4605#%E8%A7%A3%E7%AD%94-7)

（関数分割版）
https://atcoder.jp/contests/abs/submissions/9410338

でました！鬼門の Otoshidama 👹

でも，パイプを使うと処理の順と記述の順が一致するので（比較的）分かりやすいかと思います。

前段の関数の変数（引数）が後段の関数でも参照できています。後段の関数を呼び出すところも前段の関数の一部になっているってことですね。どこまでが関数の切れ目なのか分かりづらいですねｗ

`tryFind` が option を返すので，後段はパターンマッチで場合分けしてます。`match` が一行で書けるやつで良かったです😅
option でラップされた i が Some にマッチした後では，中の値に変わってます。同じ変数名だけど値を差し替えるのをシャドーイングというようです。他のところでもちょいちょい使っています。

（改良版）

``` fsharp
stdin.ReadLine()
|> fun x -> x.Split(' ')
|> Array.map int
|> fun x -> (x.[0], x.[1] / 1000)
|> fun (n, y) ->
  [0..n]
  |> Seq.tryFind (fun a ->
    (y - n - 9 * a) % 4 = 0 &&
       (y - n - 9 * a) >= 0 &&
       n - a - (y - n - 9 * a) / 4 >= 0
  )
  |> fun a ->
    match a with
    | Some a ->
      (y - n - 9 * a) / 4
      |> fun b -> sprintf "%d %d %d" a b (n - a - b)
    | None -> "-1 -1 -1"
|> printfn "%s"
```

https://atcoder.jp/contests/abc085/submissions/11467368


## ９問目 [ABC049C - 白昼夢 / Daydream](https://atcoder.jp/contests/abs/tasks/arc065_a)

``` fsharp
stdin.ReadLine()
|> fun input ->
  ["eraser"; "erase"; "dreamer"; "dream"]
  |> List.fold (
    fun acc word ->
      acc
      |> List.collect (
        fun (x: string) ->
          x.Split([| word |], System.StringSplitOptions.None)
          |> Array.filter (System.String.IsNullOrEmpty >> not)
          |> Array.toList
      )
  ) [input]
  |> List.length
  |> fun x -> (if x = 0 then "YES" else "NO")
  |> printfn "%s"
```

https://atcoder.jp/contests/abs/submissions/9414864

[JavaScript版](https://qiita.com/dsudo/items/e1abbd27b178ec8a4605#%E8%A7%A3%E7%AD%94-8)

なんか JS よりもパフォーマンス悪くなってます。。

Split がこんな記述になるのか～ ダサいですね。たしかに C# だと char はオプションなしでもいいけど，string だと配列でかつオプション指定しないとダメという仕様だったような。。
手元の fsi だと普通にオプションなしで書けるんですが。。バージョンの問題かな？

``` fsharp
> "abc".Split "b" ;;
val it : string [] = [|"a"; "c"|]
```

~~IsNullOrEmpty も微妙。括弧で囲わないと not に渡せないのは何なんだろう。~~
→ 結合順序（評価順序）のせい


## １０問目 [ABC086C - Traveling](https://atcoder.jp/contests/abs/tasks/arc089_a)

``` fsharp
stdin.ReadLine()
|> int
|> fun x -> [1..x]
|> List.map (
  fun _ ->
    stdin.ReadLine().Split(' ')
    |> Array.map int
    |> fun x -> (x.[0], x.[1], x.[2])
)
|> List.fold (
  fun acc (t2, x2, y2) ->
    match acc with
    | Some (t1, x1, y1) ->
      (
        if ((t2 &&& 1) = ((x2 + y2) &&& 1))
          && ((t2 - t1) >= (abs (x2 - x1) + abs (y2 - y1)))
        then Some (t2, x2, y2)
        else None
      )
    | None -> None
) (Some (0, 0, 0))
|> fun x ->
  (
    match x with
    | Some _ -> "Yes"
    | None -> "No"
  )
|> printfn "%s"
```

https://atcoder.jp/contests/abs/submissions/9414933

[JavaScript版](https://qiita.com/dsudo/items/e1abbd27b178ec8a4605#%E8%A7%A3%E7%AD%94-9)

さぁ，いよいよ最後の問題。いままでの集大成的な感じですね。

`(Some (0, 0, 0))` のところは括弧で囲わないと適切に結合できません。

アキュムレーター を option にしてパターンマッチするのはなかなか面白いなと感じました。これはもっと応用できそうです。


## まとめ

- F# はインデントが意味を持つ言語ではあるけど，１行でも結構ちゃんと書けます
- パイプラインは非常に強力で有用です（気に入りました！）
  - それでいうとコンピュテーション式はコンセプトはすごくいいんだけど，構文はいまいち。。
- 慣れないと括弧つけないといけないところと省略可能なところの見分けが難しい
  - コンパイルエラーとの闘い
- C# を引きずってるところは，ちょっと洗練されてない感があります
  - 実際プロダクトだと，いい感じに書けるようなラッパーとか用意するんでしょうか
  - 過去のバージョンアップでもちょいちょい追加されてる感じもあります
- JS と比べてもさほどパフォーマンスが高いようには見えません（書き方にもよると思いますが）

Have a happy programming life 🌄