結果

問題 No.6 使いものにならないハッシュ
コンテスト
ユーザー penqen
提出日時 2021-03-15 22:28:14
言語 Elixir
(1.18.1)
結果
AC  
実行時間 660 ms / 5,000 ms
コード長 3,547 bytes
コンパイル時間 1,174 ms
コンパイル使用メモリ 65,112 KB
実行使用メモリ 56,808 KB
最終ジャッジ日時 2024-12-31 05:42:57
合計ジャッジ時間 21,690 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 32
権限があれば一括ダウンロードができます
コンパイルメッセージ
    warning: missing parentheses for expression following "do:" keyword. Parentheses are required to solve ambiguity inside keywords.

    This error happens when you have function calls without parentheses inside keywords. For example:

        function(arg, one: nested_call a, b, c)
        function(arg, one: if expr, do: :this, else: :that)

    In the examples above, we don't know if the arguments "b" and "c" apply to the function "function" or "nested_call". Or if the keywords "do" and "else" apply to the function "function" or "if". You can solve this by explicitly adding parentheses:

        function(arg, one: if(expr, do: :this, else: :that))
        function(arg, one: nested_call(a, b, c))

    Ambiguity found at:
    │
 15 │     def first(n) when is_odd(n), do: if is_prime(n), do: n, else: first(n + 2)
    │     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    │
    └─ Main.exs:15

    warning: missing parentheses for expression following "do:" keyword. Parentheses are required to solve ambiguity inside keywords.

    This error happens when you have function calls without parentheses inside keywords. For example:

        function(arg, one: nested_call a, b, c)
        function(arg, one: if expr, do: :this, else: :that)

    In the examples above, we don't know if the arguments "b" and "c" apply to the function "function" or "nested_call". Or if the keywords "do" and "else" apply to the function "function" or "if". You can solve this by explicitly adding parentheses:

        function(arg, one: if(expr, do: :this, else: :that))
        function(arg, one: nested_call(a, b, c))

    Ambiguity found at:
    │
 23 │       do: if rem(n, 2) == 0, do: false, else: is_prime(n, 3)
    │       ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    │
    └─ Main.exs:23

    warning: missing parentheses for expression following "do:" keyword. Parentheses are required to solve ambiguity inside keywords.

    T

ソースコード

diff # 

defmodule Main do
  import Integer, only: [is_odd: 1]
  defmodule Prime do
    defstruct value: 2
    def next(prime \\ %__MODULE__{value: 2})
    def next(%__MODULE__{value: 2}), do: %__MODULE__{value: 3}
    def next(%__MODULE__{value: n} = prime) do
      if is_prime(n + 2),
        do: %{prime | value: n + 2},
        else: next(%{prime | value: n + 2})
    end
    def first(1), do: 2
    def first(2), do: 2
    def first(3), do: 3
    def first(n) when is_odd(n), do: if is_prime(n), do: n, else: first(n + 2)
    def first(n), do: first(n + 1)

    def is_prime(n)
    def is_prime(n) when n < 2, do: false
    def is_prime(2), do: true
    def is_prime(3), do: true
    def is_prime(n) when 3 < n,
      do: if rem(n, 2) == 0, do: false, else: is_prime(n, 3)
    defp is_prime(n, i) when i * i <= n,
      do: if rem(n, i) == 0, do: false, else: is_prime(n, i + 2)
    defp is_prime(_, _), do: true

    defimpl Enumerable do
      def count(_), do: {:error, __MODULE__}
      def member?(_, _), do: {:error, __MODULE__}
      def slice(_), do: {:error, __MODULE__}
      def reduce(_prime, {:halt, acc}, _fun), do: {:halted, acc}
      def reduce(prime, {:suspend, acc}, fun),
        do: {:suspended, acc, &reduce(prime, &1, fun)}
      def reduce(%{value: v} = prime, {:cont, acc}, fun),
       do: reduce(Prime.next(prime), fun.(v, acc), fun)
    end
  end

  defp r_to_i, do: IO.read(:line) |> String.trim() |> String.to_integer()

  def main do
    IO.puts solve(r_to_i(), r_to_i())
  end

  def solve(k, n) do
    %Prime{value: Prime.first(k)}
    |> Enum.reduce_while({%{}, nil, nil}, fn
      prime, acc when n < prime ->
        {:halt, acc}
      prime, {memo, nil, max} ->
        {:cont, {Map.put(memo, prime, MapSet.new([frank_hash(prime)])), [prime], max}}
      prime, {memo, start_with, max} ->
        hashed_value = frank_hash(prime)
        memo = Map.put(memo, prime, MapSet.new([hashed_value]))
        {memo, max, complete} = start_with
        |> Enum.reduce({memo, max, []}, fn target, {memo, max, complete} ->
          if MapSet.member?(memo[target], hashed_value) do
            with max when not is_nil(max) <- max,
              true <- MapSet.size(memo[max]) <= MapSet.size(memo[target]),
              true <- max < target do
              {memo, target, [max | complete]}
            else
              nil ->
                {memo, target, complete}
              _ ->
                {memo, max, [target | complete]}
            end
          else
            {Map.put(memo, target, MapSet.put(memo[target], hashed_value)), max, complete}
          end
        end)
        {
          :cont,
          {
            Enum.reduce(complete, memo, fn
              v, memo when v == max -> memo
              v, memo -> Map.delete(memo, v)
            end),
            Enum.reject([prime | start_with], fn v -> v in complete end),
            max
          }
        }
    end)
    |> (fn {memo, start_with, max} ->
        start_with
        |> Enum.reduce({memo, max}, fn
          target, {memo, max} ->
            with max when not is_nil(max) <- max,
              true <- MapSet.size(memo[max]) <= MapSet.size(memo[target]),
              true <- max < target do
              {memo, target}
            else
              nil ->
                {memo, target}
              _ ->
                {memo, max}
            end
        end)
        |> elem(1)
    end).()
  end

  defp frank_hash(n) when n < 10, do: n
  defp frank_hash(n), do: n |> Integer.digits() |> Enum.sum() |> frank_hash()
end
0