【レポート】第8回清流elixir勉強会を開催しました【競プロ(Cake and Donuts)@Elixir2】

トピック

今回で第8回目の勉強会を開催致しました
elixir-sr.connpass.com

隔週で勉強会を開催して早3ヶ月...
当初はElixirについてほとんど知らなかったが、現在ではある程度語れるレベルにはなった
Elixirを勉強しないという気持ちから、この面白い言語を多くの人に薦めたいと思うようになった

次回の勉強会ではElixirの入門会のようなことをしようと思う

清流elixir-infomation
開催場所: 丸の内(愛知)
参加人数: 3 -> 2
コミュニティ参加人数 : 10 -> 10 20190629現在

第8回の活動内容

www.okb-shelf.work

簡潔に述べると内容は第6回の続き
Elixirでの実装力を高めるために、競プロ問題をElixirで解いてみようということになった
素晴らしい。実際に何問か解いてみて難しさがよく分かった

Elixirでの標準入力の受け取りに関しては上記のリンクの記事を参照してほしい
今回、挑戦した問題はこちら

atcoder.jp

4ドルのケーキと7ドルのケーキをx個, y個買った時にN円になる組み合わせは存在するかどうか
入力 N
存在する場合: Yes と出力
存在しない場合: Noと出力

単純な組み合わせ問題ではあるが、Elixirでの実装ではかなり頭を使わされた

いろいろな試行錯誤

最初に思いついたことは

4の倍数
7の倍数
11の倍数(4+7)

であればいいんじゃね？と
今思えば、思考不足だが当初はいい線いってるなぁと思いコードに起こしてみた

defmodule Main do
  def main do
    # Nの入力を受け取る
    total_price = IO.gets("") |> String.trim() |> String.to_integer()
    # それぞれの倍数で割り切れるか確認
    judge = Enum.map([4,7,11], fn x -> rem(total_price, x) == 0 end)
    case true in judge do
      true -> "Yes"
      false -> "No"
    end
  end
end

ある程度のケースに対応できるようだが、詰めが甘かった
以下のようなケースではうまく判定ができない

71 -> 7 * 9 + 4 * 2
23 -> 7 * 1 + 4 * 4
45 -> 7 * 3 + 4 * 6

そりゃそうだ。11の倍数でokでは対応出来ていなかった
なので、次に全組み合わせのパターン検索を行なってみた
どういうことかというと

--7 * 0のとき--
7 * 0 + 4 * 1 = 4
7 * 0 + 4 * 2 = 8
:
:
7 * 0 + 4 * n = 4 * n

--7 * 1のとき--
7 * 1 + 4 * 1 = 11
7 * 1 + 4 * 2 = 15
:
:
7 * 1 + 4 * n = 7 + 4 * n

:
:
--7 * nのとき--
7 * n + 4 * 1 = 7 * n + 4
7 * n + 4 * 2 = 7 * n + 8
:
:
7 * n + 4 * n2 = 7 * n + 4 * n2

こんな感じ。Enumを使ってコードに起こしてみる

defmodule Main do
  def main do
    total_price = IO.gets("") |> String.trim() |> String.to_integer()
    res = Enum.map(0..total_price, fn big_num ->
        Enum.map(1..total_price, fn small_num ->
          # 7* n1 + 4 * n2 が入力値に一致した場合にtrueを返す
          if 7 * big_num + 4 * small_num == total_price do
            IO.puts("--> big: #{big_num}, small: #{small_num} ==> #{big_num * 7 + small_num * 4}")
            true
          else
            false
          end
        end)
      end)
      # リストを2次元から1次元に結合
      |> Enum.reduce(fn x, acc -> x ++ acc end)
      # trueが含まれているかを確認
      |> Enum.member?(true)
    if res, do: IO.puts("Yes"), else: IO.puts("No")
  end
end

# 71の時
Main.main()
71
--> big: 1, small: 16 ==> 71
--> big: 5, small: 9 ==> 71
--> big: 9, small: 2 ==> 71
Yes
:ok

# 23の時
--> big: 1, small: 4 ==> 23
Yes
:ok

# 45の時
--> big: 3, small: 6 ==> 45
Yes
:ok

# 16の時
--> big: 0, small: 4 ==> 16
Yes
:ok

とりあえずはいい感じ
しかしながら、現状ではそれぞれ

7: 0..入力値まで
4: 1..入力値まで

のrangeを使っているのでかなりパフォーマンスが悪い
7 +* nの値が入力値を超えた時点で処理が終わるようにしたいので以下のように変更
rangeの上限値には割り算の数値に余りが存在する場合には+1を行なっている

num = 71
res3 = Enum.reduce(1..(div(num, 7) + if rem(num, 7) == 0, do: 0, else: 1), fn x, _acc -> x end)
IO.puts(res3)

# 11

これで無駄な処理が行われないようにできるはず

defmodule Main do
  def main do
    total_price = IO.gets("") |> String.trim() |> String.to_integer()
    # div->割り算に rem->余り が0でなければ1を足し合わせる
    res = Enum.map(0..(div(total_price, 7) + if rem(total_price, 7) == 0, do: 0, else: 1), fn big_num ->
            Enum.map(0..(div(total_price, 4) + if rem(total_price, 4) == 0, do: 0, else: 1), fn small_num ->
              if 7 * big_num + 4 * small_num == total_price do
                IO.puts("--> big: #{big_num}, small: #{small_num} ==> #{big_num * 7 + small_num * 4}")
                true
              else
                false
              end
            end)
          end)
      |> Enum.reduce(fn x, acc -> x ++ acc end)
      |> Enum.member?(true)
    if res, do: IO.puts("Yes"), else: IO.puts("No")
  end
end

こちらも上手く出力された
ただ、Enum.mapでは途中で条件に一致した場合に処理を停止することが出来ない
今回は全パターンの探索を行うことよりもそのパターンが存在する時点で探索を終了してYesを出力すれば良い
なので、無理やり再帰関数で上記のEnum.mapで行なっている処理を再現して、条件に一致した時点で停止するようにした

無駄にすごく長くなってしまって何かうーん...って感じ
やりたいことは出来たと思うけど

defmodule Main do
  def main() do
    # 入力値を受け取り計算を行う関数に渡す
    total_price = IO.gets("") |> String.trim() |> String.to_integer()
    can_buy(total_price, 0)
  end
  # 入力値を超えた時点で終了してNoを出力
  def can_buy(num, accum) when num < 7 * accum, do: IO.puts("No")
  def can_buy(num, accum) do
    if calc(num, accum) do
      IO.puts("Yes")
    else
      can_buy(num, accum + 1)
    end
  end
  def calc(num, accum), do: _calc(num, accum, 0)
  # 7 * n1 + 4 * n2の値が入力値を超えた時点でfalseを返し、次のn1に
  def _calc(num, _big_accum, accum) when num < 4 * accum, do: false
  def _calc(num, big_accum, accum) do
    if 7 * big_accum + 4 * accum == num do
      true
    else
      _calc(num, big_accum, accum + 1)
    end
  end
end