当前位置: 动力学知识库 > 问答 > 编程问答 >

algorithm - Erlang "case" clause for values in a range

问题描述:

Learning Erlang, I'm solving a simple problem and I came up with this 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 is how many loop calls I have to define. Eventually there might be better solutions for this.

My question: is there any way I can tell in a case-of if some condition is within a range? Something like this, for instance:

X = H1 + H2 + C,

case X of

X >= 10 -> blah;

_ -> ummm

end.


UPDATE

This is what I was trying to 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 could use this 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 I don't use Acc++[X] pattern because it is bad habit make it O(N^2)(See[1]). From performance point of view tail call optimization is not necessary if you have to use lists:reverse/1,2 so this non-tail call version should be as fast as tail call optimised or on some platforms even 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 you can make one step further and remove case and also get + 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). with your code. In my code it takes 3.5ms and yours 33s.

网友答案:

You could use 2 helper functions (Not sure it is more efficient, maybe easier to read):

loop([H1 | T1], [H2 | T2], C, R) ->
  N = H1 + H2 + C,
  loop(T1, T2, carry(N), R ++ sum(N));
loop([], [H | T], C, R) ->
  N = H + C,
  loop([], T, carry(N), R ++ sum(N));
loop([H | T], [], C, R) ->
  N = H + C,
  loop(T, [], carry(N), R ++ sum(N));
loop([], [], 0, R) ->
  R;
loop([], [], C, R) ->
  R ++ [C].

carry(N) when N >= ?BASE10 -> 1;
carry(_) -> 0.

sum(N) when N >= ?BASE10 -> [N - ?BASE10];
sum(N) -> [N].
分享给朋友:
您可能感兴趣的文章:
随机阅读: