First clear solution for Making Change by gyahun_dash - python coding challenges

Enable Javascript in your browser and then refresh this page, for a much enhanced experience.

First solution in Clear category for Making Change by gyahun_dash

def checkio(price, denoms):
    sums = set()
    for number in range(1, price + 1):
        sums = {s + d for s in sums for d in denoms} or set(denoms)
        if price in sums: return number

March 22, 2016

Comments:

zcjsword on March 22, 2016, 9:23 p.m.
Good DP solution. A little optimization could be shortening the loop if an invalid case (line 3). You are assuming there will always be a '1' in denoms: <pre class='brush: python'>for number in range(1, (price+1)//min(denominations)): </pre>

gyahun_dash on March 23, 2016, 2:49 p.m.
Thank you. <blockquote> A little optimization could be shortening the loop if an invalid case (line 3). </blockquote> I wanted to show the process first, so I didn't think about efficiency. How about <a href="http://www.checkio.org/mission/making-change/publications/gyahun_dash/python-3/second/">this</a>? It is faster than the first solution. <blockquote> You are assuming there will always be a ‘1’ in denoms </blockquote> No. why do you think so? It can work even if there are not 1 in denoms.

zcjsword on March 24, 2016, 4:07 a.m.
<blockquote> No. why do you think so? It can work even if there are not 1 in denoms. </blockquote> No, don't get me wrong. I know your code works fine. I am saying <pre class='brush: python'> for number in range(1, price + 1): </pre> would loop "price" times, which is unnecessary if the min(denom) is larger than 1. For example, if min(denom) is 2, you know that the max number to make change for "price" will be ceil(price/2). Only when min(denom) == 1, you should loop price times because price could always consists of price number of 1.

gyahun_dash on March 24, 2016, 5:17 p.m.
Oh, I got it, sorry. <a href="http://www.checkio.org/mission/making-change/publications/gyahun_dash/python-3/second/">Second</a> treats this problem in a complicated way.

e-l on April 4, 2016, 12:22 p.m.
Nice! Very clean. How fast is it? Here you build all combinations of coins together? What's algorithmic complexity? Thx.

gyahun_dash on April 4, 2016, 1 p.m.
Thank you. <blockquote> Here you build all combinations of coins together? </blockquote> Yes, until price is found. <blockquote> How fast is it? What’s algorithmic complexity? </blockquote> It is not so fast. It is fast if answer is a small number, for example a multiple of any denomination, but very slowly if answer is None or price is very large. To be fast, we should take more effective approaches, i.e. Branch and Bound like <a href="https://checkio.org/mission/making-change/publications/e-l/python-3/first/?ordering=most_voted">yours</a> or <a href="https://checkio.org/mission/making-change/publications/gyahun_dash/python-3/branch-and-bound-4th/?ordering=most_voted">mine</a>.

frantisek.jahoda on April 15, 2016, 11:58 a.m.
`or set(denoms)` part can be removed if sums is set to `sums = set(denoms)` at the start. Having empty `sums` is the reason to end. Also searching items larger than `price` just prolong the running. Otherwise nice and short.

dan_rue on Dec. 6, 2022, 10:53 p.m.
That doesn't work.. If you do that, the result is always one coin to low..

serg3y1999 on Oct. 15, 2018, 8:38 p.m.
can you explain or set(denoms),how it works ?

dan_rue on Dec. 6, 2022, 10:55 p.m.
A little late for the party.. But for the first iteration, the left set is {}, so the or makes it that the assignment 'takes' the right set -> the set with the denoms

Mine

0 %

PyCharm The Python IDE for Professional Developers. Enjoy productive Python, web and scientific development with PyCharm. Download it now!