Is reduce_while/3 the correct function for this use-case?

Questions / Help
1

In my code here, work_loop uses Enum.reduce_while/3, but as you can see it’s just discarding the accumulator.

I’m wondering if that’s a sign that there’s a more appropriate function for this?

import Bitwise
require Logger

# TS3H.demo("MEkDAgcAAgEgAh9n5rQmt3zJukGmwwvEVwfbZFS3NJ9oW7hgpJ0Db5ORAh8mOLmbP3+DfEQvEFbOcqymWoF6s9GHVcv8UegJBcWz", 1102362)


defmodule TS3H do

  defp work_loop(intermed_state, goal, ctr_start, ctr_end) do
    Enum.reduce_while(
      ctr_start..ctr_end,
      {nil, -1, -1},
      fn ctr, _ ->
        score = phase2(intermed_state, ctr)
        if score < goal do
          {:cont, {nil, ctr, score}}
        else
          {:halt, {:ok, ctr, score}}
        end
      end
    )
  end

  def demo(pk_str, ctr_best) do
    demo(pk_str, ctr_best, ctr_best)
  end
  def demo(pk_str, ctr_best, ctr_cur) do
    intermed_state = phase1(pk_str)
    # FIXME add a warning about bad keys / slow phase
    record = phase2(intermed_state, ctr_best)
    Logger.info("Current score: #{record}")
    Logger.info("Skipping already checked: #{ctr_cur - ctr_best + 1}")
    # Skip ctr_cur since that's *already been* checked
    {outcome, ctr_last, last_score} = work_loop(intermed_state, record, ctr_cur + 1, ctr_cur + 2**24)
    case outcome do
      nil ->
        Logger.notice("Got to #{ctr_last} without any progress.")
        {record, ctr_best, ctr_last}
      :ok ->
        if last_score > record do
          Logger.notice("Improved score!! #{ctr_last} -> #{last_score}")
          {last_score, ctr_last, ctr_last}
        else
          Logger.notice("Found new head. #{ctr_last} -> #{record}")
          {record, ctr_best, ctr_last}
        end
    end
  end

  def phase1(pk_str) do
    :crypto.hash_init(:sha)
    |> :crypto.hash_update(pk_str)
  end

  def phase2(state, ctr) do
    :crypto.hash_update(state, Integer.to_string(ctr))
    |> :crypto.hash_final()
    |> ts3_binary_lzcnt()
  end

  def ts3_binary_lzcnt(hash) do  # FIXME performance :(
    # Octets are consumed in network order.
    # Bits are consumed starting from the least significant bit.
    # Examples:
    #     <<255,   0,   0,   0>> -> 0
    #     <<  1,   0,   0,   0>> -> 0
    #     <<  0,   1,   0,   0>> -> 8
    #     <<  0, 255,   0,   0>> -> 8 
    #     <<  0, 254,   0,   0>> -> 9
    Stream.unfold(hash, fn
      # https://elixirforum.com/t/trouble-understanding-octet-string-binary-iteration/62304
      <<i::8, rem::binary>> -> {i, rem}
      <<>> -> nil
    end)
    |> Enum.reduce_while(
      {:cont, 0},
      fn
        0, {:cont, acc_val} -> {:cont, {:cont, acc_val + 8}}
        x, {:cont, acc_val} -> {:cont, {:halt, acc_val + tzcnt(x, nil)}}
        _, {:halt, acc_val} -> {:halt, {:halt, acc_val}}
      end
    )
    |> elem(1)
  end

  defp tzcnt(i, nil, count) when i !== 0 do
    # h/t https://programming-idioms.org/idiom/262/count-trailing-zero-bits/5157/erlang
    if (i &&& 1) === 0 do
      tzcnt(i >>> 1, nil, count + 1)
    else
      count
    end
  end
  defp tzcnt(i, max) do
    if i === 0 do
      max
    else
      tzcnt(i, nil, 0)
    end
  end

end

The forum software correctly suggested that I take a look at thread #34178, but the suggestion there of using Enum.find_value/2 is an awkward fit because I like being able to return a single “semantically uniform” datatype rather than having special-cased shaped matches on the caller’s end.

I looked around the Enum documentation, but it’s really sprawling; there are so many unique functions, each filling a clear niche, and it’s possible I overlooked one that would fit my use-case.

2

Hi!, I think recursion may be a good approach.

  defp work_loop(intermed_state, goal, ctr_start, ctr_end) do
    loop(ctr_start..ctr_end, intermed_state, goal)
  end

  defp loop(ctrs, intermed_state, goal, result \\ nil)

  defp loop([current_ctr | rest], intermed_state, goal, nil) do
    score = phase2(intermed_state, current_ctr)

    if score < goal do
      loop(rest, intermed_state, goal)
    else
      loop(rest, intermed_state, goal, {:ok, current_ctr, score})
    end
  end

  defp loop(_ctrs, _intermed_state, _goal, result), do: result

I haven’t tested it, but I think it works fine.
If you implement this approach, I suggest refactoring the args of work_loop for it to directly be the recursive function.

1 Like
3

It have “awkward” returns because the intention was to return them like that. You can return same type or different types based on pattern-matching - it’s up to you and your use case. find_value/3 simply discards nil and finishes as soon as it finds a value.

Here goes a simplified example:

defmodule Example do
  def sample(first, last, goal) do
    Enum.find_value(first..last, fn element ->
      # replace this with your own function call
      result = double(element)
      # this line returns {element, result} when the result of expression on the left side
      # is truthy i.e. it's not nil or false
      result >= goal && {element, result}
    end)
  end

  # replace this with your own function
  defp double(integer), do: integer * 2
end

{element, result} = Example.sample(1, 10, 11)
IO.inspect {element, result}
# 1 * 2 = 2;  2 >= 11 -> false (skipped)
# 2 * 2 = 4;  4 >= 11 -> false (skipped)
# 3 * 2 = 6;  6 >= 11 -> false (skipped)
# 4 * 2 = 8;  8 >= 11 -> false (skipped)
# 5 * 2 = 10; 10 >= 11 -> false (skipped)
# 6 * 2 = 12; 12 >= 11 -> true
# rest is skipped because value is already found
# {6, 12} is returned
1 Like