Elixir beginner: early exit efficiency in map creation

Questions / Help
1

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 :smile:

2

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
3

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

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

4

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
5

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
6

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
7

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
8

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 :smile:

1 Like