入力処理用に以下のような関数群を用意しておく。

// "42"
// -> Ok(42)
pub fn parse_int(s: String) -> Result(Int, Nil) {
  string.trim_end(s) |> int.parse
}

// "1 2 3 4"
// -> Ok([1, 2, 3, 4])
pub fn parse_ints(s: String) -> Result(List(Int), Nil) {
  string.trim_end(s) |> string.split(" ") |> list.try_map(int.parse)
}

// ["5\n", "4\n", "3\n"]
// -> Ok([5, 4, 3])
pub fn parse_ints_v(slist: List(String)) -> Result(List(Int), Nil) {
  list.try_map(slist, fn(s) {string.trim_end(s) |> int.parse})
}

いずれの関数も、入力の末尾に改行があってもなくてもパースできるようにしてある。

各ステップでの処理の意味については、ここでは詳しく扱わない。なお、parse_ints_v()は既に定義した関数を使って以下のようにも書ける。

pub fn parse_ints_v(slist: List(String)) -> Result(List(Int), Nil) {
  list.try_map(slist, parse_int)
}

Hizuru

ここで示す解答例では、いずれもsolve()関数が一要素一行の文字列リストList(String)を受け取ることを想定している。

pub fn solve(lines: List(String)) -> String {
  /* 入力文字列を使った処理 */
  ...
}

main()関数部分は、次のように書くことになる。

import gleam/io

import gleam/yielder
import stdin

pub fn main() {
  stdin.read_lines()
  |> yielder.to_list
  |> solve
  |> io.println
}

…が、このコードは現在のバージョン (gleam 1.10.0) では動かない。stdinライブラリが、古いAPIであるresult.nil_error()を使ってるっぽい？詳しい人、教えてほしい。

~~仕方がないので、とりあえずsolve()関数に改行区切りした入力文字列のリストを直接渡してテストすることにする。~~

（2025/05/28 追記）stdin v2.0.2で、それまで使われていた非推奨／削除済みのAPIが軒並み別のものに置き換えられたことで、上記のコードが動くようになった。やったね！

pub fn main() {
  // stdinを介さず、入力文字列を直接コードに書く場合
  // 第3問の入力例
  ["3\n", "8 12 40\n"]
  |> solve
  |> io.println
}

以下の解答例では、solve()関数とそれに関連するコードのみを示す。

Hizuru

第1問: ABC 086 A - Product

問題概要

二つの正整数aとbの積が偶数か奇数か判定してください。

入力形式

a b

解答例

import gleam/int
// import gleam/io
import gleam/list
import gleam/string

// import gleam/yielder
// import stdin

pub fn parse_ints(s: String) -> Result(List(Int), Nil) {
  string.trim_end(s) |> string.split(" ") |> list.try_map(int.parse)
}

pub fn solve(lines: List(String)) -> String {
  let assert [ln, ..] = lines
  let assert Ok([a, b]) = parse_ints(ln)
  case {a * b} % 2 {
      1 -> "Odd"
      _ -> "Even"
  }
}

まず、文字列リストから先頭の1行（1要素）を取り出す。

  let assert [ln, ..] = lines

用があるのは最初の1行だけだったので残りを捨てているが、以降の行も取得したい場合は以下のように書けばよい。

  let assert [ln, ..lines] = lines  // linesが残りの行で更新される

次に、取り出した行を整数のリストに変換する。

  let assert Ok([a, b]) = parse_ints(ln)  // 3 4 -> Ok([3, 4])

なお、parse_ints()の実装として、不正な入力があった場合に無視したり0として扱ったりといったバリエーションも考えられるが、ここはフェイルファストで。もし入力の形式が合わなかった場合には、アサーションエラーで落ちるようにしてある。

  case {a * b} % 2 {
      1 -> "Odd"
      _ -> "Even"
  }

問題文に書かれた通り処理する。{a * b}の波括弧は、なくても構わない。gleam では、優先順位を示すのに、丸括弧()ではなく波括弧{}を使うことに注意。

Hizuru

第2問: ABC 081 A - Placing Marbles

問題概要

0と1のみから成る3桁の番号 s に、1が何個含まれるかを求めてください。

入力形式

s₁s₂s₃

解答例

import gleam/int
// import gleam/io
import gleam/list
import gleam/result
import gleam/string

// import gleam/yielder
// import stdin

pub fn parse_int(s: String) -> Result(Int, Nil) {
  string.trim_end(s) |> int.parse
}

pub fn solve(lines: List(String)) -> String {
  let assert [ln, ..] = lines
  parse_int(ln)
  |> result.try(int.digits(_, 10))
  |> result.unwrap([])
  |> list.count(fn(x) {x == 1})
  |> int.to_string
}

第1問と同じく、まずは文字列リストから先頭の1行（1要素）を取り出す。

  let assert [ln, ..] = lines

文字列を整数にパースする。parse_int()内部では、最初に入力の末尾の改行を除去している。int.parse()だけだと、改行が残っている場合にパースできないので気を付けよう。

  parse_int(ln)

パースに成功していた場合、10進表記での各桁の数を格納したリストを生成する（101→[1, 0, 1]）。Result(List(Int))型が返ってくるので、unwrapする。Gleamのunwrap()は、Rustのunwrap_or()に相当し、何かしらデフォルト値を与える必要がある^[1]。

  |> result.try(int.digits(_, 10))
  |> result.unwrap([])

1の要素をカウントする。Gleamの無名関数は、fn() {}のように書く。

  |> list.count(fn(x) {x == 1})

最後に、整数型の結果を文字列に変換して返す。

  |> int.to_string

脚注

確か、Gleamの標準ライブラリには、Rustのunwrap()のようにpanicする関数は存在しなかったはず。 ↩︎

Hizuru

第3問: ABC 081 B - Shift Only

問題文

黒板に n 個の正の整数 a₁,...,aₙ が書かれています．
すぬけ君は，黒板に書かれている整数がすべて偶数であるとき，次の操作を行うことができます．

黒板に書かれている整数すべてを，2 で割ったものに置き換える．

すぬけ君は最大で何回操作を行うことができるかを求めてください．

入力形式

n
a₁ a₂ ... aₙ

解答例

import gleam/int
// import gleam/io
import gleam/list
import gleam/string

// import gleam/yielder
// import stdin

pub fn parse_ints(s: String) -> Result(List(Int), Nil) {
  string.trim_end(s) |> string.split(" ") |> list.try_map(int.parse)
}

pub fn solve(lines: List(String)) -> String {
  let assert[_n, a] = lines
  let assert Ok(a) = parse_ints(a)
  count(a, 0) |> int.to_string
}

fn count(a: List(Int), cnt: Int) -> Int {
  case list.is_empty(a), list.all(a, int.is_even) {
    False, True -> count(
      list.map(a, fn(x) {x / 2}),
      cnt + 1
    )
    _, _ -> cnt
  }
}

入力は2行与えられる。最初の1行は使わないので、アンダースコア_始まりの変数で受け取っておく^[1]。

  let assert[_n, a] = lines

2行目を整数のリストに変換する。Gleamの変数はイミュータブルだが、同じ名前で再束縛することはできる（シャドーイング）。

  let assert Ok(a) = parse_ints(a)

リストをcount()関数に渡して、その結果を文字列に変換する。

  count(a, 0) |> int.to_string

count()は、整数リストとこれまでのカウント数を受け取って、合計カウント数を返す再帰関数である。

fn count(a: List(Int), cnt: Int) -> Int {

①リストが空か、②リスト内の全ての要素が偶数か、を判定する。

  case list.is_empty(a), list.all(a, int.is_even) {

そして、その結果に基づいて分岐する。リストが空ではなく^[2]、すべての要素が偶数のとき、各整数を2で割ったものを格納したリストと、現在のカウントをインクリメントしたものを実引数に、count()関数の再帰呼び出しを行う。

  case list.is_empty(a), list.all(a, int.is_even) {
    False, True -> count(
      list.map(a, fn(x) {x / 2}),
      cnt + 1
    )
    _, _ -> cnt
  }

それ以外の場合は、受け取ったカウントをそのまま返す。例えば、最初に与えられたリストに奇数が含まれていた場合、count(a, 0)は0を返す。

脚注

普通の名前の変数で受け取ってもコンパイルはできるが、未使用変数についてのワーニングが出る。 ↩︎
空リストを受け取った場合に無限ループになってしまうのを避けるためlist.is_empty()判定を入れているが、この問題の入力では、制約上空リストが与えられることはない。なお、実際に入力が空リストの可能性があった場合にどう対処するかは問題による。 ↩︎

Hizuru

第4問: ABC 087 B - Coins

問題概要

500円玉 A 枚、100円玉 B 枚、50円玉 C 枚の中から何枚か選び、合計金額をちょうど X 円にする方法は何通りありますか。

入力形式

a
b
c
x

解答例

import gleam/int
// import gleam/io
import gleam/list.{range}
import gleam/string

// import gleam/yielder
// import stdin

pub fn parse_ints_v(slist: List(String)) -> Result(List(Int), Nil) {
  list.try_map(slist, fn(s) {string.trim_end(s) |> int.parse})
}

pub fn solve(lines: List(String)) -> String {
  let assert Ok([a, b, c, x]) = parse_ints_v(lines)
  {
    use i <- list.flat_map(range(0, a))
    use j <- list.map(range(0, b))
    use k <- list.count(range(0, c))
    i * 500 + j * 100 + k * 50 == x
  }
  |> list.fold(0, int.add)
  |> int.to_string
}

ポイント: use構文を使うことで、3重ループを追加のインデントなしに実装できる。

複数行の文字列を数値のリストにパースする。parse_ints_v() (parse integers vertically) 関数は文字列のリストを受け取って、各要素末尾の空白・改行を除去し、int.parse()を適用する。今回のような「縦型」の入力の時に便利。

  let assert Ok([a, b, c, x]) = parse_ints_v(lines)

↑のような入力に対して、↓のような結果を返す。

Ok([5, 1, 0, 150])

Gleamのlist.range()は、閉区間、つまり終点を含むことに注意^[1]。use構文を使うことで、高階関数のネストを、インデントを深くすることなく書ける（参考: https://zenn.dev/comamoca/articles/gleam-use-syntax）。いわゆるシンタックスシュガーで、Haskellのdo記法やScalaのfor式っぽい構文。

  {
    use i <- list.flat_map(range(0, a))
    use j <- list.map(range(0, b))
    use k <- list.count(range(0, c))
    i * 500 + j * 100 + k * 50 == x
  }

上のブロックは、次のように脱糖される。

list.flat_map(range(0, a), fn(i) {
  list.map(range(0, b), fn(j) {
    list.count(range(0, c), fn(k) {
      i * 500 + j * 100 + k * 50 == x
    })
  })
})

list.count()は、式の評価結果がTrueである数を返す。
list.map()は、その結果をまとめた整数のリストを返す。
list.flat_map()は、複数の整数のリストを統合する。

といった具合。

  |> list.fold(0, int.add)
  |> int.to_string

最後に、list.fold(0, int.add)で整数リストの総和を求めて、その結果を文字列にして返す。

何かもう少し分かりやすい書き方がありそうだけど気にしない。

脚注

Pythonのrangeは半開区間。Gleamのlist.range(start, end)は、Rustのstart..=endに相当。厳密には旧APIのiterator.range()の方が近いが、いつの間にか標準ライブラリから消えていた。パフォーマンスが気になるなら、gleam_yielderを使うのが良さげ。 ↩︎

Hizuru

第5問: ABC 083 B - Some Sums

問題文

1以上 N 以下の整数のうち、10進法での各桁の和が A 以上 B 以下であるものの総和を求めてください。

入力形式

n a b

解答例

import gleam/int
// import gleam/io
import gleam/list.{range}
import gleam/result
import gleam/string

// import gleam/yielder
// import stdin

pub fn parse_ints(s: String) -> Result(List(Int), Nil) {
  string.trim_end(s) |> string.split(" ") |> list.try_map(int.parse)
}

pub fn solve(lines: List(String)) -> String {
  let assert [ln, ..] = lines
  let assert Ok([n, a, b]) = parse_ints(ln)
  {
    use acc, i <- list.fold(range(1, n), 0)
    let sum = {
      int.digits(i, 10)
      |> result.unwrap([])
      |> list.fold(0, int.add)
    }
    case a <= sum && sum <= b {
      True -> acc + i
      _ -> acc
    }
  }
  |> int.to_string
}

1行目を複数の整数にパースする。よくあるやつ。

  let assert [ln, ..] = lines
  let assert Ok([n, a, b]) = parse_ints(ln)

またrange + useの組み合わせで解く。どの道、返り値の型変換のためにスコープ切らないといけないから、それほどメリットはないんだけどuseを使いたい！という気持ちで。

use acc, i <- list.fold(range(1, n), 0)

1からnまでの全整数について、各桁の和を求める。やっていることは基本的に第2問の解答例と同じ。

    let sum = {
      int.digits(i, 10)
      |> result.unwrap([])
      |> list.fold(0, int.add)
    }

条件（a以上b以下）を満たすなら、アキュムレータ (acc) に元の整数の値を加算する。Gleamではミュータブルな変数を宣言できないが、ループにlist.fold()を使うことで次のイテレーションに値を持ち越すことができ、手続き型っぽく (？) かける。

    case a <= sum && sum <= b {
      True -> acc + i
      _ -> acc
    }

処理が終わったら、整数を文字列に変換するのを忘れずに。

  |> int.to_string

Hizuru

番外編: `gleeunit`を使ってテストを書く

Gleamには標準でテストフレームワークが用意されている。せっかくなので、これを使ってサンプルが通るかどうかのチェックをまとめて行えるようにしてみよう。

import gleam/list
import gleam/string
import gleeunit
import gleeunit/should

import acbs05.{solve}


const test_cases = [
#("
20 2 5
", "
84
"),
#("
10 1 2
", "
13
"),
#("
100 4 16
", "
4554
"),
]

pub fn acbs05_test() {
  use #(input, output) <- list.each(test_cases)
  string.trim(input)
  |> string.split("\n")
  |> list.map(string.append(_, "\n"))
  |> solve
  |> should.equal(string.trim(output))
}

pub fn main() -> Nil {
  gleeunit.main()
}

テストケースの配列は文字列のタプルから構成されていて、最初の要素が入力、2つ目の要素が出力に対応している。入出力の文字列は、AtCoderの問題ページのサンプルから直接コピペすればよい。

#("    // 入力
20 2 5
", "   // 出力
84
"),

テスト関数では、各テストケースについて入力文字列を文字列リストに変換し、それをsolve()関数に渡した結果が出力文字列を整形したものと一致するかどうかを確認している^[1]。

pub fn acbs05_test() {
  use #(input, output) <- list.each(test_cases)
  string.trim(input)
  |> string.split("\n")
  |> list.map(string.append(_, "\n"))
  |> solve
  |> should.equal(string.trim(output))
}

実際にテストを走らせてみる。

gleam test

    Running acbs05_test.main
.
Finished in 0.021 seconds
1 tests, 0 failures

上手くいったようだ。

脚注

テスト関数内において、一度改行文字でsplitした後に、再び各要素に改行文字をappendしているのは、stdinライブラリのread_lines()関数の挙動に合わせるため。 ↩︎

Hizuru

第6問: ABC 088 B - Card Game for Two

問題文

N 枚のカードがあります. i 枚目のカードには, aᵢ という数が書かれています.
Alice と Bob は, これらのカードを使ってゲームを行います. ゲームでは, Alice と Bob が交互に 1 枚ずつカードを取っていきます. Alice が先にカードを取ります.
2 人がすべてのカードを取ったときゲームは終了し, 取ったカードの数の合計がその人の得点になります. 2 人とも自分の得点を最大化するように最適な戦略を取った時, Alice は Bob より何点多く取るか求めてください.

入力形式

n
a₁ a₂ a₃ ... aₙ

解答例

import gleam/int
// import gleam/io
import gleam/list
import gleam/order
import gleam/string

// import gleam/yielder
// import stdin

pub fn parse_ints(s: String) -> Result(List(Int), Nil) {
  string.trim_end(s) |> string.split(" ") |> list.try_map(int.parse)
}

pub fn solve(lines: List(String)) -> String {
  let assert [_n, a] = lines
  let assert Ok(a) = parse_ints(a)
  let a = list.sort(a, order.reverse(int.compare))
  {
    use acc, x, idx <- list.index_fold(a, 0)
    case idx % 2 {
      0 -> acc + x
      _ -> acc - x
    }
  }
  |> int.to_string
}

いよいよ後半戦。今回は、入力の2行目を整数のリストに変換する。

  let assert [_n, a] = lines
  let assert Ok(a) = parse_ints(a)

次に、整数リストを降順にソートする。list.sort()は昇順ソートなので、order.reverse()を使って比較関数を反転させる。

  let a = list.sort(a, order.reverse(int.compare))

求める必要があるのは、AliceとBobの点差。ここではゲームの流れをシミュレートする。Aliceの手番の時には残っているカードのうち最も数が大きいものの値を加算し、Bobの手番の時には最も数が大きいものの値を減算していく。

  {
    use acc, x, idx <- list.index_fold(a, 0)
    case idx % 2 {
      0 -> acc + x
      _ -> acc - x
    }
  }

最後に、結果を文字列に変換して終了。

  |> int.to_string

Hizuru

第7問: ABC 085 B - Kagami Mochi

問題概要

n 個の整数 d₁,d₂,...,dₙ の中に何種類の異なる値がありますか（意訳）。

入力形式

n
d₁
:
dₙ

解答例

import gleam/int
// import gleam/io
import gleam/list
import gleam/set
import gleam/string

// import gleam/yielder
// import stdin

pub fn parse_ints_v(slist: List(String)) -> Result(List(Int), Nil) {
  list.try_map(slist, fn(s) {string.trim_end(s) |> int.parse})
}

pub fn solve(lines: List(String)) -> String {
  let assert Ok([_n, ..d]) = parse_ints_v(lines)
  set.from_list(d)
  |> set.size
  |> int.to_string
}

2行目以降を整数のリストに変換する。

  let assert Ok([_n, ..d]) = parse_ints_v(lines)

Gleamには集合型 (set) があるので、リストを集合に変換することで重複を除去し、そのサイズを取得すればよい。

  set.from_list(d)
  |> set.size
  |> int.to_string

Hizuru

第8問: ABC 085 C - Otoshidama

問題概要

10000円札、5000円札、1000円札が合計で n 枚あり、合計金額が y 円であるような紙幣の枚数の組み合わせを1つ求めてください。もし、そのような組み合わせが存在しない場合には-1 -1 -1を出力してください。

入力形式

n y

解答例

import gleam/int
// import gleam/io
import gleam/list.{range}
import gleam/string

// import gleam/yielder
// import stdin

pub fn parse_ints(s: String) -> Result(List(Int), Nil) {
  string.trim_end(s) |> string.split(" ") |> list.try_map(int.parse)
}

pub fn solve(lines: List(String)) -> String {
  let assert [ln, ..] = lines
  let assert Ok([n, y]) = parse_ints(ln)
  let res = {
    use i <- list.find_map(range(n, 0))
    use j <- list.find_map(range(n - i, 0))
    let k = n - i - j
    case i * 10000 + j * 5000 + k * 1000 == y {
      True -> Ok([i, j, k])
      _ -> Error(Nil)
    }
  }
  case res {
    Ok(vals) -> {
      list.map(vals, int.to_string)
      |> string.join(" ")
    }
    _ -> "-1 -1 -1"
  }
}

最初の行を2つの整数にパースする。

  let assert [ln, ..] = lines
  let assert Ok([n, y]) = parse_ints(ln)

ここではlist.find_map()を用い、条件に当てはまる組み合わせを見つけたときには処理を打ち切り、その値を返すようにする。なお、1000円札の枚数は、10000円札の枚数と5000円札の枚数から自動的に決まるので、2重ループで済む。

  let res = {
    use i <- list.find_map(range(n, 0))
    use j <- list.find_map(range(n - i, 0))
    let k = n - i - j
    case i * 10000 + j * 5000 + k * 1000 == y {
      True -> Ok([i, j, k])
      _ -> Error(Nil)
    }
  }

整数リストをスペース区切りの文字列表現に変換する。見つからなかった場合 (Error(Nil)) には、指示通り-1 -1 -1を返す。

  case res {
    Ok(vals) -> {
      list.map(vals, int.to_string)
      |> string.join(" ")
    }
    _ -> "-1 -1 -1"
  }

Hizuru

第9問: ABC 049 C - Daydream

問題文

英小文字からなる文字列 S が与えられます。 T が空文字列である状態から始め、以下の操作を好きな回数繰り返すことで S = T とすることができるか判定してください。

T の末尾に dream dreamer erase eraser のいずれかを追加する。

入力形式

s

解答例

import gleam/bool
// import gleam/int
// import gleam/io
import gleam/list
import gleam/string

// import gleam/yielder
// import stdin

fn rev_list(s: String) -> List(UtfCodepoint) {
  string.reverse(s)
  |> string.to_utf_codepoints()
}

fn check(slist: List(UtfCodepoint),
         words: List(List(UtfCodepoint))) -> Bool
{
  use <- bool.guard(list.is_empty(slist), True)

  let common_len = {
    use word <- list.find_map(words)
    let len = list.length(word)
    case list.take(slist, len) == word {
      True -> Ok(len)
      _ -> Error(Nil)
    }
  }
  case common_len {
    Ok(len) -> list.drop(slist, len) |> check(words)
    _ -> False
  }
}

pub fn solve(lines: List(String)) -> String {
  let assert [ln, ..] = lines
  let s = string.trim_end(ln)
  let s = rev_list(s)
  let words = [
    rev_list("dreamer"),
    rev_list("eraser"),
    rev_list("dream"),
    rev_list("erase")
  ]
  case check(s, words) {
    True -> "YES"
    _ -> "NO"
  }
}

入力文字列（1行）末尾の改行文字を除去する。

  let assert [ln, ..] = lines
  let s = string.trim_end(ln)

rev_list()は、対象の文字列を反転し、コードポイントのリストに変換する関数である。

fn rev_list(s: String) -> List(UtfCodepoint) {
  string.reverse(s)
  |> string.to_utf_codepoints()
}

この関数を入力文字列と検索したい文字列に適用する。

  let s = rev_list(s)
  let words = [
    rev_list("dreamer"),
    rev_list("eraser"),
    rev_list("dream"),
    rev_list("erase")
  ]

string.start_drop() string.end_drop()は計算量が規定されていない？ようで、今回のように長大な入力文字列に対して繰り返し処理を行う可能性がある場合、実装によっては毎回文字列全体のコピーが作成されることにより、とてつもなく遅くなってしまうことが考えられるため、まずは入力文字列の前後を入れ替えたものをリストへと変換しておく。Gleamのリスト先頭への要素の追加・削除が定数時間で行えることは、ドキュメントに明記されている。

次に、変換済みの入力文字列と検索したい文字列のリストを引数にcheck()関数を呼び出す。check()関数は、入力がreverseされていることを前提に、slistがwordsに含まれる要素の組み合わせで構成できるかどうかを前方から再帰的に確かめるものである。

  case check(s, words) {

fn check(slist: List(UtfCodepoint),
         words: List(List(UtfCodepoint))) -> Bool

use構文とbool.guard()を用い、受け取ったリストslistが空の場合には早期リターン^[1]でTrueを返す。ここでlist.is_empty() (O(1)) の代わりにlist.length() (O(N)) を使うと、再帰呼び出しごとに残りのコードポイントリスト全体を走査することになってしまうので注意。

  use <- bool.guard(list.is_empty(slist), True)

slistが検索語wordsに含まれているいずれかの要素で始まっていた場合、その長さをRusultにくるんでcommon_lenに束縛する。いずれにもマッチしなかった場合には、Error(Nil)が与えられる。

  let common_len = {
    use word <- list.find_map(words)
    let len = list.length(word)
    case list.take(slist, len) == word {
      True -> Ok(len)
      _ -> Error(Nil)
    }
  }

common_lenがOkなら、つまりslistの先頭部分がwordsのいずれかと一致していたなら、slistからその部分を取り除いて、check()を再帰的に呼び出す。そうでないなら、Falseを返す。

  case common_len {
    Ok(len) -> list.drop(slist, len) |> check(words)
    _ -> False
  }

再帰関数check()の結果を元に、最終的にsolve()は "YES" か "NO" を返す。大文字と小文字に気を付けよう。

  case check(s, words) {
    True -> "YES"
    _ -> "NO"
  }

補足: JavaScript がターゲットの場合

上記のコードは、トランスパイルのターゲットがJavaScriptの場合、入力文字列のサイズが大きいときに再帰の上限に引っかかってしまう。

InternalError: too much recursion

これは、bool.guard()に渡されるコールバック内でGleamコンパイラによる末尾呼び出し最適化 (tail call optimization) が効かないことに起因するようである。

とりあえずの対処法としては、check()関数を以下のように書き換えることが挙げられる。これにより、コンパイラはこの関数が末尾再帰であると認識でき、再帰呼び出しの部分をループに置き換えたコードを生成する。

fn check(slist: List(UtfCodepoint),
         words: List(List(UtfCodepoint))) -> Bool
{
  let common_len = {
    use <- bool.guard(list.is_empty(slist), Ok(0))
    use word <- list.find_map(words)
    let len = list.length(word)
    case list.take(slist, len) == word {
      True -> Ok(len)
      _ -> Error(Nil)
    }
  }
  case common_len {
    Ok(0) -> True
    Ok(len) -> list.drop(slist, len) |> check(words)
    _ -> False
  }
}

第10問: ABC 086 C - Traveling

問題文

シカのAtCoDeerくんは二次元平面上で旅行をしようとしています。AtCoDeerくんの旅行プランでは、時刻0に点 (0, 0) を出発し、1以上 N 以下の各 i に対し、時刻 tᵢ に点 (xᵢ, yᵢ) を訪れる予定です。
AtCoDeerくんが時刻 t に点 (x, y) にいる時、時刻 t + 1 には点 (x + 1, y), (x − 1, y), (x, y + 1), (x, y − 1) のうちいずれかに存在することができます。その場にとどまることは出来ないことに注意してください。AtCoDeerくんの旅行プランが実行可能かどうか判定してください。

入力形式

n
t₁ x₁ y₁
t₂ x₂ y₂
:
tₙ xₙ yₙ

解答例

import gleam/int.{absolute_value as abs}
// import gleam/io
import gleam/list
import gleam/string

// import gleam/yielder
// import stdin

pub fn parse_ints(s: String) -> Result(List(Int), Nil) {
  string.trim_end(s) |> string.split(" ") |> list.try_map(int.parse)
}

pub fn solve(lines: List(String)) -> String {
  let assert [_n, ..txys] = lines

  let res = {
    use acc, txy <- list.try_fold(txys, #(0, 0, 0))
    let #(pt, px, py) = acc
    let assert Ok([t, x, y]) = parse_ints(txy)
    case abs(x-px) + abs(y-py) <= t - pt, int.is_even(t - {x + y}) {
      True, True -> Ok(#(t, x, y))
      _, _ -> Error(Nil)
    }
  }
  case res {
    Ok(_) -> "Yes"
    Error(_) -> "No"
  }
}

入力の1行目を読み捨てて、2行目以降をtxysに束縛する。

  let assert [_n, ..txys] = lines

今回は、繰り返し処理にlist.try_fold()を使う。この関数はlist.fold()と似ているが、以下の点で異なる。

コールバックはResult(acc, e)を返す必要がある。
コールバックがOk(acc)を返した場合、その中身がアキュムレータとして次のイテレーションに回される。
コールバックがError(e)を返した場合、ループは中断される。

いずれの場合も、最後にコールバックが返した値がlist.try_fold()関数呼び出しの返り値となる^[1]。

  let res = {
    use acc, txy <- list.try_fold(txys, #(0, 0, 0))
    let #(pt, px, py) = acc
    let assert Ok([t, x, y]) = parse_ints(txy)
    case abs(x-px) + abs(y-py) <= t - pt, int.is_even(t - {x + y}) {
      True, True -> Ok(#(t, x, y))
      _, _ -> Error(Nil)
    }
  }

上記のブロック内のcase式では、次の条件を満たすかどうかを判定している。

次の目的地に、時間までにたどり着けるか？
時刻と始点からの（マンハッタン）距離のパリティが一致するか？

条件を満たさなかった場合には、Errorと共にループを終了する。

    case abs(x-px) + abs(y-py) <= t - pt, int.is_even(t - {x + y}) {

全ての入力が条件を満たしていた場合には"Yes"が、いずれかの条件に違反し、途中でループを抜けた場合には"No"が返される。

  case res {
    Ok(_) -> "Yes"
    Error(_) -> "No"
  }

おしまい！

脚注

公式:　[gleam/list.try_fold] ↩︎

Hizuru

おまけ: 感想など

もっと再帰使うかと思ってたけど、useと高階関数で結構いけた。
Gleam楽しい。
シンプルながらも基礎的な問題を解くのに十分な表現力があると感じた。実際、入力の受け取り以外は、標準ライブラリの機能だけでいけた。
DPとか高パフォーマンスが要求される問題はちょっと大変かも。
一方で、Gleamの良さを引き出しきれてない感もある。

第1問: ABC 086 A - Product

問題概要

入力形式

解答例

コメント

第2問: ABC 081 A - Placing Marbles

問題概要

入力形式

解答例

コメント

第3問: ABC 081 B - Shift Only

問題文

入力形式

解答例

コメント

第4問: ABC 087 B - Coins

問題概要

入力形式

解答例

コメント

第5問: ABC 083 B - Some Sums

問題文

入力形式

解答例

コメント

番外編: gleeunitを使ってテストを書く

第6問: ABC 088 B - Card Game for Two

問題文

入力形式

解答例

コメント

第7問: ABC 085 B - Kagami Mochi

問題概要

入力形式

解答例

コメント

第8問: ABC 085 C - Otoshidama

問題概要

入力形式

解答例

コメント

第9問: ABC 049 C - Daydream

問題文

入力形式

解答例

コメント

補足: JavaScript がターゲットの場合

第10問: ABC 086 C - Traveling

問題文

入力形式

解答例

コメント

おしまい！

おまけ: 感想など

番外編: `gleeunit`を使ってテストを書く