exercism / elixir-analyzer

GNU Affero General Public License v3.0
30 stars 32 forks source link

DNA encoding automated feedback false positive when using variables #396

Closed sam-dt closed 1 year ago

sam-dt commented 1 year ago

Problem

I received the following feedback after submission:

The purpose of this exercise is to teach tail call recursion. Solve it without using recursive functions that are not tail-recursive.

Tail-recursive functions found in your solution: do_reverse/2. Other recursive functions found in your solution: do_decode/2, do_encode/2.

Remember, tail call recursion happens when the last expression evaluated by the function is a call to itself.

I was breaking my head over it until I tried removing a variable assignment and placing it inline:

  defp do_decode(<<head::4, rest::bitstring>>, list) do
-   decoded_head = decode_nucleotide(head) 
-   do_decode(rest, [decoded_head | list])
+   do_decode(rest, [decode_nucleotide(head) | list])
  end  

Only after that change the automated feedback seemed to recognize it as a tail-recursive function

So I'm wondering if this is a false positive or if I'm maybe missing a gotcha here

EDIT: I made the exercise locally and submitted through the CLI

Full code snippets

Fail:

defmodule DNA do
  def encode_nucleotide(code_point) do
    case code_point do
      ?\s -> 0b0000
      ?A -> 0b0001
      ?C -> 0b0010
      ?G -> 0b0100
      ?T -> 0b1000
    end
  end

  def decode_nucleotide(encoded_code) do
    case encoded_code do
      0b0000 -> ?\s 
      0b0001 -> ?A 
      0b0010 -> ?C 
      0b0100 -> ?G 
      0b1000 -> ?T 
    end
  end

  def encode(dna) do
    do_encode(dna, <<>>)
  end

  defp do_encode([], encoded), do: encoded
  defp do_encode([head | tail], encoded) do
    encoded_head = encode_nucleotide(head)
    do_encode(tail, <<encoded::bitstring, encoded_head::4>>)
  end

  def decode(dna) do
    do_decode(dna, [])
      |> reverse()
  end

  defp do_decode(<<>>, list), do: list
  defp do_decode(<<head::4, rest::bitstring>>, list) do
    decoded_head = decode_nucleotide(head) 
    do_decode(rest, [decoded_head | list])
  end  

  defp reverse(list) do
    do_reverse(list, []) 
  end

  defp do_reverse([], reversed_list), do: reversed_list
  defp do_reverse([head | tail], reversed_list) do
    do_reverse(tail, [head | reversed_list])    
  end
end

Success:

defmodule DNA do
  def encode_nucleotide(code_point) do
    case code_point do
      ?\s -> 0b0000
      ?A -> 0b0001
      ?C -> 0b0010
      ?G -> 0b0100
      ?T -> 0b1000
    end
  end

  def decode_nucleotide(encoded_code) do
    case encoded_code do
      0b0000 -> ?\s 
      0b0001 -> ?A 
      0b0010 -> ?C 
      0b0100 -> ?G 
      0b1000 -> ?T 
    end
  end

  def encode(dna) do
    do_encode(dna, <<>>)
  end

  defp do_encode([], encoded), do: encoded
  defp do_encode([head | tail], encoded) do
    do_encode(tail, <<encoded::bitstring, encode_nucleotide(head)::4>>)
  end

  def decode(dna) do
    do_decode(dna, [])
      |> reverse()
  end

  defp do_decode(<<>>, list), do: list
  defp do_decode(<<head::4, rest::bitstring>>, list) do
    do_decode(rest, [decode_nucleotide(head) | list])
  end  

  defp reverse(list) do
    do_reverse(list, []) 
  end

  defp do_reverse([], reversed_list), do: reversed_list
  defp do_reverse([head | tail], reversed_list) do
    do_reverse(tail, [head | reversed_list])    
  end
end
angelikatyborska commented 1 year ago

Thank you for reporting! This is definitely a bug in the analyzer code: I opened a PR with a fix: https://github.com/exercism/elixir-analyzer/pull/397