Menu

Subscribe

Coin denomimation algorithm

on interview question, erlang, python

Coin challenge

How many different ways can N be made using any number of denominators.

For example we have denominators list: [1,3,6]. So how many ways we can made number 4 with any numbers of [1,3,6].

Answer: [1,1,1,1], [3,1], [1,3].

Erlang version

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#!/usr/bin/env escript
%% -*- erlang -*-
%%! -smp enable -sname t1
% vim:syn=erlang

-mode(compile).

main(_) ->
    L = [1,3,6],
    N = 7,
    io:format("Answer: ~p ~n", [answer(L,N)]).

answer(L,N) -> 
    R = t31(L,N,[]),
    %clear(lists:flatten(R),0,N,[],[]).
    [lists:usort(permute(X,length(X),[]))||X<-clear(lists:flatten(R),0,N,[],[])].


t31(_, 0, A)             -> A;
t31([], _, _)            -> [];
t31(_, N, _)  when N < 0 -> [];
t31([C|Cs], N, A)        -> [t31(Cs, N, A)] ++ [t31([C|Cs], N-C, A++[C])].

clear([],_,_,[],A)   -> A;
clear([],_,_,B,A)    -> A ++ [B];
clear([H|T],N,N,B,A) -> clear([H|T],0,N,[],A++[B]);
clear([H|T],M,N,B,A) -> clear(T, M+H, N,B++[H],A).

permute(_,0,A) -> A;
permute([H|T], N, A) -> permute(T++[H], N-1, A++[T++[H]]).

Python version

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#!/usr/bin/python

import itertools

def answer(coin, n):
    ret1 = t31(coin, n, [])
    ret2 = [[list(y) for y in list(set(list(itertools.permutations(x))))]
                for x in clear(ret1) if len(x) != 0]
    print list(clear(ret2))

def t31(coin, n, acum):
    if n == 0: return acum
    if n <  0: return []
    if len(coin) == 0: return []
    acum2 = list(acum)
    acum2.append(coin[0])
    return [t31(coin[1::], n, list(acum)), t31(coin, n-coin[0], acum2)]

def clear(lst):
    for x in lst:
        if any(isinstance(el, list) for el in x):
            for x in clear(x):
                yield x
        else: yield x

if __name__ == '__main__': answer([1,3,6], 7)