The idiomatic, elegant "send + more = money" solution in Elixir
I came across a blog post by Mark Dominus that describes the "SEND + MORE = MONEY" solution using functional programming techniques (Monads in particular) in Python.
The conundrum described here in the case of dead links:
S E N D | Find each character *unique* numerical value, such that
+ M O R E | the addition on the left is valid. There are no leading zeros.
-----------
= M O N E Y
I was looking for a chance to learn some purely functional programs, specifically with Elixir, and it seemed like a very suitable project.
I can implement a cosmetically similar version of Mark Dominus' Python code in Elixir:
defmodule Smm do
def make_set(ls), do: Enum.into(ls, HashSet.new)
def to_number([]), do: :error
def to_number(ls), do: Enum.join(ls) |> Integer.parse |> elem(0)
def remove(hs, ls), do: Set.difference(hs, Enum.into(ls, HashSet.new))
def let(x, func), do: func.(x)
def guard(predicate, func) when predicate, do: func.()
def guard(predicate, func), do: []
end
digits = Smm.make_set(0..9)
Enum.map( Smm.remove(digits, [0]), fn s ->
Enum.map( Smm.remove(digits, [s]), fn e ->
Enum.map( Smm.remove(digits, [s,e]), fn n ->
Enum.map( Smm.remove(digits, [s,e,n]), fn d ->
Smm.let(Smm.to_number([s,e,n,d]), fn w_send ->
Enum.map( Smm.remove(digits, [0,s,e,n,d]), fn m ->
Enum.map( Smm.remove(digits, [s,e,n,d,m]), fn o ->
Enum.map( Smm.remove(digits, [s,e,n,d,m,o]), fn r ->
Smm.let(Smm.to_number([m,o,r,e]), fn w_more ->
Enum.map( Smm.remove(digits, [s,e,n,d,m,o,r]), fn y ->
Smm.let(Smm.to_number([m,o,n,e,y]), fn w_money ->
Smm.guard(w_send + w_more == w_money, fn ->
[w_send, w_more, w_money] |> Enum.map( &(IO.puts(&1)) )
end)end)end)end)end)end)end)end)end)end)end)end) # (╯°□°）╯︵ ┻━┻
But something tells me that there has to be a way around insanely nested anonymous functions and then drag and drop tables; that's why pure functional languages exist, right?
Looking at Mark Dominus's previous blog post where he solves a riddle with Haskell , I see that he is using a sweet Haskell version of the "bind" operator >>=
to eliminate table hints ... But I didn't recognize me Haskell , so I don't have a strong understanding the code provided in this blog post.
I'm pretty sure my Elixir implementation is missing a using statement |>
, which was actually a big draw for the language to me (very handy with Unix pipes, myself). I've tried pipe work in combination with many flavors Enum.{map,reduce}
, but I always go back to the square.
Can anyone suggest any advice? Ideally, I'm looking for a more idiomatic functional programming solution to this puzzle in Elixir.
source to share
You can look here: What is ">" "Purpose of a Symbol in Elixir? For operator overview |>
. But the basic idea is what is the a |> f(b, c)
same f(a, b, c)
. This is very useful when you do something like the a |> f(b) |> g(c)
rule above is the same like g(f(a, b), c)
, but reading is much nicer.
With that said, the operator |>
(called the pipeline) is not monadic chaining ( >>=
) and will not let you "flatten" deeply nested loops like >>=
. For alternative approaches to a problem that looks better in Elixir, you can:
- Use a library that implements the syntax for Monads (or add your own) like MonadEx
-
Stop using this approach and, for example, generate the assignment of numbers to letters using the recursive upfront function, for example:
defmodule Smm do # some more things def assignments(0, _), do: [[]] def assignments(n, digits \\ Enum.into(0..9, HashSet.new)) do digits |> Stream.flat_map(fn (d) -> for rest <- assignments(n - 1, Set.delete(digits, d)) do [d | rest] end end) end end for [s, e, n, d, m, o, r, y] <- Smm.assignments(8) do w_send = Smm.to_number([s, e, n, d]) w_more = Smm.to_number([m, o, r, e]) w_money = Smm.to_number([m, o, n, e, y]) if s > 0 && m > 0 && (w_send + w_more == w_money) do IO.inspect([w_send, w_more, w_money]) end end
source to share
This syntactic distraction is eliminated in Haskell by two things: operator associativity and a good language rule for lambda.
The presence of associativity rules eliminates unnecessary parentheses in the syntax. For example, in the Elixir add-on it associates on the left, so when you write a + 2 + x
it is interpreted as (a + 2) + x
. The associativity rule allows you to get rid of parentheses. If you meant a + (2 + x)
, you would need to write it explicitly.
You can get operator associativity to help with Elixir, and some are already there. The MonadEx library defines a bind operator ~>>
that will allow you to write the guts of your program something like
Smm.remove(digits, [0])
~>> fn s -> Smm.remove(digits, [s])
~>> fn e -> Smm.remove(digits, [s,e])
~>> fn n -> Smm.remove(digits, [s,e,n])
~>> fn d -> return(Smm.to_number([s,e,n,d]))
~>> fn w_send -> Smm.remove(digits, [0,s,e,n,d])
~>> fn m -> Smm.remove(digits, [s,e,n,d,m])
~>> fn o -> Smm.remove(digits, [s,e,n,d,m,o])
~>> fn r -> return(Smm.to_number([m,o,r,e]))
~>> fn w_more -> Smm.remove(digits, [s,e,n,d,m,o,r])
~>> fn y -> return(Smm.to_number([m,o,n,e,y]))
~>> fn w_money -> Smm.guard(w_send + w_more == w_money)
~>> fn -> return([w_send, w_more, w_money])
end end end end end end end end end end end end
The associative association does not get rid of lambda expressions that end in the same place. Later expressions must be inside earlier lambdas so that they can see the variables introduced earlier. Haskell gets rid of this distraction with a simple "lambda abstraction ... extend as far to the right as possible" syntax rule . Because the lambdas stretch all the way to the right, Haskell code written in the same style doesn't have a whole bunch of end brackets.
solutions = remove [0] digits >>= \s ->
remove [s] digits >>= \e ->
remove [s,e] digits >>= \n ->
remove [s,e,n] digits >>= \d ->
let send = to_number [s,e,n,d]
in remove [0,s,e,n,d] digits >>= \m ->
remove [s,e,n,d,m] digits >>= \o ->
remove [s,e,n,d,m,o] digits >>= \r ->
let more = to_number [m,o,r,e]
in remove [s,e,n,d,m,o,r] digits >>= \y ->
let money = to_number [m,o,n,e,y] in
guard (send + more == money) >>= \_ ->
return (send, more, money)
I cannot imagine an appropriate trick for Elixir. Each fn
should be end
at the end, so there will be as many end
as there would be bindings. I think you just need to flip through the tables (╯°□°）╯︵ ┻━┻
.
source to share