Hackerrank Challenge: Elixir times out but python doesn't?

Questions / Help
1

Hello everybody.

I am having a question concerning a challenge I recently tried on Hackerrank.com. I am not sure if my Elixir result is having timeout Issues because of my poor code or because of the site. I wanted to ask here first to make sure I use Elixir correctly.

Problem

The problem can be found here, but it basically wants you to delete adjacent A’s or B’s from a string of length 1 to 10^5

My Solution / Idea

My idea is to traverse the code from left to right and compare the current string with the following one. If they are the same, I am incrementing the counter within reduce.

idea_prev
idea_prev814×278 10.7 KB

For this example, the resulting string would be

idea_post

My Code for this Challenge is :

defmodule Solution do
 def calc(tests) do
    Range.new(1,tests) |> Enum.each(fn _ -> alternatingCharacters(IO.read(:stdio, :line)) end) 
 end
 
 def alternatingCharacters(x) do
 test = String.split(x,"\n") |> Enum.at(0)
 len = String.length(test)
 
 Range.new(0,len-1) |> Enum.reduce(0,
  fn (x, deletion) -> 
    if(String.at(test,x) === String.at(test,x+1))
    do deletion +(1) else deletion
    end
  end) |> IO.puts()
 end
 
end

IO.read(:stdio, :line) |> String.split("\n") |> Enum.at(0) |> String.to_integer |> Solution.calc

With this code the tests timeout for 6 Test Cases, but if I use this code in python

def alternatingCharacters(s):
    deletion = 0
    for i in range(0, len(s) - 1) :
        if s[i] == s[i+1]:
            deletion+=1
    return deletion

it completes without any timeout.

Am I not seeing something very obvious or is there something wrong with my code?

2

The quick answer is that you’re treating the linked list of Elixir, which has O(n) behavior for things like length and at, as if it were an array, which has O(1) behavior for those things.

What I would do is reduce over the characters in the string and in the accumulator add a new value only if it has changed. Something like:

{_, reversed_result} =
the_string
|> String.codepoints
|> Enum.reduce({nil, []}, fn letter, {prior_letter, accumulator} ->
  if prior_letter == letter do
    {prior_letter, accumulator}
  else
    {letter, [letter | accumulator]}
  end
end)

Enum.reverse(reversed_result)
|> Enum.join("")

The reversal won’t really matter with a small count of letters in the string, but when it gets long (as the problem description said it can do) it will help. The linked list is faster at prepending values to the front than appending to the end. And the Enum.reverse call at the end is highly optimized for just this sort of situation.

3 Likes
3

Could something like this work?

defmodule Hm do
  def alternating_characters(<<x, x, rest::bytes>>) do
    alternating_characters(<<x, rest::bytes>>)
  end
  def alternating_characters(<<x, rest::bytes>>) do
    <<x, alternating_characters(rest)::bytes>>
  end
  def alternating_characters(<<x, x>>) do
    alternating_characters(<<x>>)
  end
  def alternating_characters(<<x>>), do: <<x>>
  def alternating_characters(<<>>), do: <<>>
end

Assuming ascii.

iex(7)> Hm.alternating_characters("AABB")
"AB"
iex(8)> Hm.alternating_characters("AABBB")
"AB"
iex(9)> Hm.alternating_characters("AAAAAABBB")
"AB"
iex(10)> Hm.alternating_characters("AAAAAABBAAABBBAAA")
"ABABA"
1 Like
4

I thought that it might be because of the linked list.

Sorry if it is a stupid question, but why can you use here

fn letter, {prior_letter, accumulator} -> ....

how many parameters can the function inside reduce have? I thought only 2.

I had a solution with codepoints, but thought it might be O(n) because it needs to traverse the whole string, which can be very huge. Maybe I don’t understand the idea of it yet.

1 Like
5

I would probably just do this:

defmodule Solution do
  def alternatingCharacters(s) do
    s |> String.graphemes() |> Enum.dedup() |> IO.puts()
  end
end

Or if you want to not use Enum.dedup then:

defmodule Solution do
  def alternatingCharacters(s), do: alternatingCharacters(String.graphemes(s), [])
  def alternatingCharacters([], acc), do: acc |> :lists.reverse() |> IO.puts()
  def alternatingCharacters([c|l], [c|_]=acc), do: alternatingCharacters(l, acc)
  def alternatingCharacters([c|l], acc), do: alternatingCharacters(l, [c|acc])
end

Or return it instead of IO.put()ing it if you want, or to_string() it to convert it back to a binary instead of an iolist.

3 Likes
6

It might, to be honest, this goes a little bit over my experience :slight_smile:

I might need some time to understand it first

7

That is only two parameters. The second one is a 2 element tuple though.

Haha! Yeah, that’d do it!

2 Likes
8

This one would probably be a rather efficient pure binary one that would work better for huge strings:

defmodule Solution do
  def alternatingCharacters(s), do: alternatingCharacters(s, "", 0)
  def alternatingCharacters("", acc, _), do: acc |> IO.puts()
  def alternatingCharacters(<<c::utf8,r::binary>>, acc, c), do: alternatingCharacters(r, acc, c)
  def alternatingCharacters(<<c::utf8,r::binary>>, acc, _), do: alternatingCharacters(r, acc <> <<c::utf8>>, c)
end
1 Like
9

The dedup() method actually solves all tests.

I really didn’t knew anything about this function.
I need to learn more elixir :smile:

Thank you

1 Like
10

Ah, lol, I thought you were avoiding it on purpose, hence my alternate answer (and I was just being cheeky with the simple answer ^.^;). ^.^

The binary last one I posted right before your latest post is probably the most efficient and would scale better to huge strings unlike the others. :slight_smile:

11

Oh ok, thank you I wasn’t sure.

I’ll give your solution a try, to make sure I understand it correctly

1 Like
12

I’ll give it a try after I understand it :smile:
Thank you again

1 Like
13

The function does indeed have an arity of 2. The second argument is destructured via pattern matching. However:

So you can write

fn
  letter, {prior_letter, accumulator} -> 
    bla
  letter, other -> 
    blablah
end

So if the second argument is a 2 element tuple bla is executed, otherwise blabla is executed.

3 Likes
14

Ahh I understand. This helps a lot.

So if I have a 3 element tuple, I could only check for a 3 element tuple as the second argument otherwise it will execute exactly like ?

letter, other -> 
    blablah
1 Like
15

You could do this:

fn
  letter, {first, second, third} -> 
    blablabla
  letter, {prior_letter, accumulator} -> 
    bla
  letter, other -> 
    blablah
end

and yes with

fn
  letter, {prior_letter, accumulator} -> 
    bla
  letter, other -> 
    blablah
end

a three element tuple as the second argument would come in as other.

1 Like
16

Ok now I understand it

Thank you for your explanation

1 Like