Elixir beginner: early exit efficiency in map creation

broeman

I am using Project Euler this summer for learning to solve problems in Elixir.
The fourth problem is about palindrome product of 2/3 digits,
and I create a map of all the sums (probably a better way to keep it flatten, and I do look for the palindromes afterwards):

Enum.map(upper..lower, fn x -> Enum.map(upper..x, fn y -> x * y end) end)
|> List.flatten

I am used to, from iterative design, to return early, like:

for x <- upper..lower
    for y <- upper..x
      if palindrome?(x*y) then return x*y

which sounds more efficient to me, as finding the largest palindrome must be made by larger numbers in the product. I could put an if-statement in the map and “filter” the palindromes out faster, but it still have to go through the whole map(s).

Is there a better way? I would like to know the functional programming approach to this problem. Hope it makes sense

7 comments

#how-to-question

0 2435 7

2017-07-13 12:07:23 UTC

Showing Posts 1 to 7

Show Best Posts
Show All (oldest first)
Show All (newest first)

OvermindDL1

Well translating this directly would just be:

def step_x(upper, lower, x) when x<lower, do: nil
def step_x(upper, lower, x) do
  case step_y(upper, x, upper) do
    nil -> step_x(upper, lower, x-1)
    result -> result
  end
end

def step_y(upper, x, y) when <x, do: nil
def step_y(upper, x, y), do: if palindrome?(x*y), do: x*y, else: step_y(upper, x, y-1)

Or something like that, I’ve not tested it, but that is the direct conversion.

Post #1

Azolo

I mean, I wouldn’t really call that approach functional.

I just solved it using a more functional approach if you want to see mine… I feel bad posting solutions to Project Euler though.

Post #2

net

You can do

is_palindrome? = fn (n) -> s = to_string(n); s == String.reverse(s) end

try do
  for x <- 999..100, y <- 999..x, n = x * y, is_palindrome?.(n), do: throw(n)
catch 
  n -> n
end

which is the equivalent of your second example.

However, that will not find the largest palindrome. To do that you want

Enum.reduce_while 999..100, 0, fn
  x, highest when highest >= x * 999 -> {:halt, highest}
  x, highest ->
    highest =
      Stream.map(999..x, &(x * &1))
      |> Enum.reduce(highest, &(&1 > &2 && is_palindrome?.(&1) && &1 || &2))
    {:cont, highest}
end

Post #3

peerreynders

It may be idea to point out that you are throwing a value - which merely classifies as a non-local return which is quite different from raising an error or exception (but still gets you into trouble if no one is there to catch it).

PS: Just a general note - code inside the protected area of the try cannot be subject to last call optimization (TCO). So in general you want to keep your “stay there” as brief as possible or if necessary be a little more vigilant about your call stack use.

Post #4

sasajuric

Author of Elixir In Action

You could use Stream for that:

upper..lower
|> Stream.flat_map(fn x -> Stream.map(x..lower, &{x, &1}) end)
|> Stream.filter(fn {x,y} -> palindrome?(x*y) end)
|> Enum.take(1)

This code will stop on the first detected palindrome (which I believe is not necessarily the largest palindrome).

Post #5

Qqwy

TypeCheck Core Team

There also is Enum.reduce_while which can be used to do short-circuiting but avoid the overhead you get from using Streams.

upper = 999
lower = 100
(upper..lower)
|> Enum.flat_map(fn x -> Enum.map(x..lower, &{x, &1}) end)
|> Enum.reduce_while(nil, fn {x, y}, _ ->
  if palindrome?(x * y) do
    {:halt, x * y}
  else
    {:cont, nil}
  end
end)
)

Just like @sasajuric’s method, this will not neccesarily return the largest palindrome, because two medium-sized numbers might have a larger product than a large number with a small number.

Post #6