equal_with_deletions : Given two strings n and m, return true if they are equal when both are entered into text editors. But: a # means a backspace character (deleting backwards), and a % means a delete character (deleting forwards). From https://buttondown.email/cassidoo/archive/5-time-moves-slowly-but-passes-quickly-alice/

equal_with_deletions.livemd

equal with deletions

Question

From rendezvous with cassidoo, April 4 2022 "Interview Question Of The Week"

Given two strings n and m, return true if they are equal when both are entered into text editors. But: a # means a backspace character (deleting backwards), and a % means a delete character (deleting forwards).

Example:

equalWithDeletions("a##x", "#a#x")
true      // both strings become "x"

equalWithDeletions("fi##f%%%th %%year #time###", "fifth year time")
false     // the first string becomes "fart"

Code

defmodule Editor do
  def equal_with_deletions(s1, s2), do: do_delete(s1, []) == do_delete(s2, [])

  defp do_delete(<<"#", rest::binary>>, acc), do: back_delete(rest, acc)
  defp do_delete(<<"%", rest::binary>>, acc), do: forward_delete(rest, acc)
  defp do_delete(<<c::utf8, rest::binary>>, acc), do: do_delete(rest, [c | acc])
  defp do_delete(<<>>, acc), do: acc

  defp back_delete(s, []), do: do_delete(s, [])
  defp back_delete(s, [_h | acc]), do: do_delete(s, acc)

  defp forward_delete(<<>>, acc), do: do_delete(<<>>, acc)
  defp forward_delete(s = <<"%", _rest::binary>>, acc), do: do_delete(s, acc)
  defp forward_delete(s = <<"#", _rest::binary>>, acc), do: do_delete(s, acc)
  defp forward_delete(<<_c::utf8, rest::binary>>, acc), do: do_delete(rest, acc)

  # don't need this, but makes testing easier
  def delete(s) do
    s
    |> do_delete([])
    |> Enum.reverse()
    |> List.to_string()
  end
end

{:module, Editor, <<70, 79, 82, 49, 0, 0, 9, ...>>, {:delete, 1}}

Test

ExUnit.start(autorun: false)

defmodule EditorTest do
  use ExUnit.Case, async: true
  import Editor

  describe "delete" do
    test "delete empty string" do
      assert delete("") == ""
    end

    test "delete regular string with no deletes" do
      assert delete("I like cheese") == "I like cheese"
    end

    test "delete string with backspaces" do
      assert delete("a##x") == "x"
      assert delete("#a#x") == "x"
      assert delete("I like cheese####omping cheee#se") == "I like chomping cheese"
    end

    test "delete forward at end of string" do
      assert delete("abc%") == "abc"
    end
  end

  describe "equal_with_deletions/2" do
    test "equal with backspaces" do
      assert equal_with_deletions("a##x", "#a#x") == true
    end

    test "equal with forward deletes" do
      assert equal_with_deletions("fi##f%%%th %%year #time###", "fifth year time") == false
    end
  end
end

ExUnit.run()

......

Finished in 0.00 seconds (0.00s async, 0.00s sync)
6 tests, 0 failures

Randomized with seed 500396

%{excluded: 0, failures: 0, skipped: 0, total: 6}