# Elixir beginner: early exit efficiency in map creation

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

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.

1 Like

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.

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
``````
1 Like

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.

2 Likes

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).

3 Likes

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.

2 Likes

Yes, youâ€™re right according to the largest palindrome.

I was just wondering about how to exit early, and you all gave great answers, I can ponder upon

1 Like