algorithm - Erlang "case" clause for values in a range -
learning erlang, i'm solving simple problem , came solution:
%%%------------------------------------------------------------------ %%% @doc https://leetcode.com/problems/add-two-numbers/ %%% %%% @end %%%------------------------------------------------------------------ -module(add_two_numbers). -define(base10, 10). -export([main/2]). -ifdef(test). -include_lib("eunit/include/eunit.hrl"). -endif. -spec main(l1 :: nonempty_list(non_neg_integer()), l2 :: nonempty_list(non_neg_integer())) -> list(). %%%================================================================== %%% export %%%================================================================== main(l1, l2) -> loop(l1, l2, 0, []). -ifdef(test). main_test() -> ?assertequal([0, 2, 1, 2, 1, 1], add_two_numbers:main([9, 6, 9, 5, 9], [1, 5, 1, 6, 1])), ?assertequal([3, 6, 9, 7, 5], add_two_numbers:main([4, 1, 8, 7, 2], [9, 4, 1, 0, 3])), ?assertequal([6, 7, 9, 0, 1], add_two_numbers:main([2, 2, 3, 3], [4, 5, 6, 7])), ?assertequal([6, 3, 7, 4, 1], add_two_numbers:main([4, 1, 0, 8], [2, 2, 7, 6])), ?assertequal([2, 7, 9, 1], add_two_numbers:main([2, 7, 1, 0], [0, 0, 8, 1])), ?assertequal([8, 9, 9, 1], add_two_numbers:main([9, 9, 9], [9, 9, 9])), ?assertequal([7, 1, 6, 1], add_two_numbers:main([9, 3, 7], [8, 7, 8])), ?assertequal([3, 5, 6, 1], add_two_numbers:main([6, 6, 6], [7, 8, 9])), ?assertequal([0, 0, 0], add_two_numbers:main([0, 0, 0], [0, 0, 0])), ?assertequal([7, 0, 8], add_two_numbers:main([2, 4, 3], [5, 6, 4])), ?assertequal([0, 2, 2], add_two_numbers:main([0, 1], [0, 1, 2])), ?assertequal([0, 1, 1], add_two_numbers:main([4, 6], [6, 4])), ?assertequal([0, 0, 1], add_two_numbers:main([1], [9, 9])), ?assertequal([0, 1], add_two_numbers:main([], [0, 1])), ?assertequal([], add_two_numbers:main([], [])), ?asserterror(badarith, add_two_numbers:main([0, 1, 2], ["", 5, 6])). -endif. %%%================================================================== %%% internal %%%================================================================== loop([h1 | t1], [h2 | t2], c, r) when h1 + h2 + c >= ?base10 -> loop(t1, t2, 1, r ++ [h1 + h2 + c - ?base10]); loop([], [h | t], c, r) when h + c >= ?base10 -> loop([], t, 1, r ++ [h + c - ?base10]); loop([h | t], [], c, r) when h + c >= ?base10 -> loop([], t, 1, r ++ [h + c - ?base10]); loop([h1 | t1], [h2 | t2], c, r) -> loop(t1, t2, 0, r ++ [h1 + h2 + c]); loop([], [h | t], c, r) -> loop([], t, 0, r ++ [h + c]); loop([h | t], [], c, r) -> loop([], t, 1, r ++ [h + c]); loop([], [], c, r) when c > 0 -> r ++ [c]; loop([], [], _, r) -> r.
what bothers me how many loop
calls have define. there might better solutions this.
my question: there way can tell in case
-of
if condition within range? this, instance:
x = h1 + h2 + c, case x of x >= 10 -> blah; _ -> ummm end.
update
this trying achieve:
loop([h1 | t1], [h2 | t2], c, r) -> case h1 + h2 + c >= ?base10 of true -> loop(t1, t2, 1, r ++ [h1 + h2 + c - ?base10]); false -> loop(t1, t2, 0, r ++ [h1 + h2 + c]) end; loop([], [h | t], c, r) -> case h + c >= ?base10 of true -> loop([], t, 1, r ++ [h + c - ?base10]); false -> loop([], t, 0, r ++ [h + c]) end; loop([h | t], [], c, r) -> case h + c >= ?base10 of true -> loop(t, [], 1, r ++ [h + c - ?base10]); false -> loop(t, [], 0, r ++ [h + c]) end; loop([], [], c, r) -> case c > 0 of true -> r ++ [c]; false -> r end.
...not sure if it's better though.
you use little trick
loop([], [], 0, r) -> lists:reverse(r); loop([], [], 1, r) -> lists:reverse(r, [1]); loop([], l2, c, r) -> loop([0], l2, c, r); loop(l1, [], c, r) -> loop(l1, [0], c, r); loop([h1 | t1], [h2 | t2], c, r) -> case h1 + h2 + c of s when s >= ?base10 -> loop(t1, t2, 1, [s - ?base10 | r]); s -> loop(t1, t2, 0, [s | r]) end.
note don't use acc++[x]
pattern because bad habit make o(n^2)(see[1]). performance point of view tail call optimization not necessary if have use lists:reverse/1,2
non-tail call version should fast tail call optimised or on platforms faster:
main(l1, l2) -> loop(l1, l2, 0). loop([], [], 0) -> []; loop([], [], 1) -> [1]; loop([], l2, c) -> loop([0], l2, c); loop(l1, [], c) -> loop(l1, [0], c); loop([h1 | t1], [h2 | t2], c) -> case h1 + h2 + c of x when x >= ?base10 -> [ x - ?base10 | loop(t1, t2, 1) ]; x -> [ x | loop(t1, t2, 0) ] end.
or can make 1 step further , remove case , + 0
out
loop([], [], 0) -> []; loop([], [], 1) -> [1]; loop([], [h | t], c) -> loop_([], t, h + c); loop([h | t], [], c) -> loop_([], t, h + c); loop([h1 | t1], [h2 | t2], c) -> loop_(t1, t2, h1 + h2 + c). loop_(l1, l2, s) when s >= ?base10 -> [ s - ?base10 | loop(l1, l2, 1) ]; loop_(l1, l2, s) -> [ s | loop(l1, l2, 0) ].
[1]: try [l1, l2] = [ [rand:uniform(10)-1 || _ <- lists:seq(1, 100000)] || _ <- [1,2] ], timer:tc(fun() -> add_two_numbers:main(l1, l2) end).
code. in code takes 3.5ms , yours 33s.
Comments
Post a Comment