making_change.checkio() - Code Metrics - KenMercusLai/checkio - Measure and Improve Code Quality continuously with Scrutinizer

making_change.checkio() B
last analyzed 2022-05-11 09:02 UTC

↳ Parent: making_change

Complexity

Conditions

Size

Total Lines	19
Code Lines	18

Duplication

Lines	0
Ratio	0 %

Importance

Changes

Metric	Value
cc	8
eloc	18
nop	2
dl	0
loc	19
rs	7.3333
c	0
b	0
f	0

import heapq
from collections import defaultdict


def shortestPath(graph, start, end):

    queue = [(0, start, [])]
    seen = set()
    while True:
        (cost, v, path) = heapq.heappop(queue)
        if v not in seen:
            path = path + [v]
            seen.add(v)
            if v == end:
                return cost, path
            for (next_item, c) in graph[v].items():
                heapq.heappush(queue, (cost + c, next_item, path))
    return queue


def checkio(price, denominations):
    conn = defaultdict(dict)
    open_number = set([price])
    closed_number = set([])
    while open_number:
        current = open_number.pop()
        closed_number.add(current)
        for i in denominations:
            if current - i >= 0:
                conn[current][current - i] = 1
                if current - i == 0:
                    conn[0][current] = 1
                if current - i not in closed_number:
                    open_number.add(current - i)
    if conn and 0 in conn:
        steps, numbers = shortestPath(conn, price, 0)
    else:
        return None
    return steps


if __name__ == '__main__':  # pragma: no cover
    # These "asserts" using only for self-checking and not necessary for
    # auto-testing
    assert checkio(8, [1, 3, 5]) == 2
    assert checkio(12, [1, 4, 5]) == 3
    print('Done')


1		import heapq
2		from collections import defaultdict
3
4
5	View Code Duplication	def shortestPath(graph, start, end):
		0 ignored issues – show Duplication introduced 2019-02-09 16:35 UTC by Report Bug Copy Issue Report This code seems to be duplicated in your project. Loading history...
6		queue = [(0, start, [])]
7		seen = set()
8		while True:
9		(cost, v, path) = heapq.heappop(queue)
10		if v not in seen:
11		path = path + [v]
12		seen.add(v)
13		if v == end:
14		return cost, path
15		for (next_item, c) in graph[v].items():
16		heapq.heappush(queue, (cost + c, next_item, path))
17		return queue
18
19
20		def checkio(price, denominations):
21		conn = defaultdict(dict)
22		open_number = set([price])
23		closed_number = set([])
24		while open_number:
25		current = open_number.pop()
26		closed_number.add(current)
27		for i in denominations:
28		if current - i >= 0:
29		conn[current][current - i] = 1
30		if current - i == 0:
31		conn[0][current] = 1
32		if current - i not in closed_number:
33		open_number.add(current - i)
34		if conn and 0 in conn:
35		steps, numbers = shortestPath(conn, price, 0)
36		else:
37		return None
38		return steps
39
40
41		if __name__ == '__main__': # pragma: no cover
42		# These "asserts" using only for self-checking and not necessary for
43		# auto-testing
44		assert checkio(8, [1, 3, 5]) == 2
45		assert checkio(12, [1, 4, 5]) == 3
46		print('Done')
47

KenMercusLai / checkio

making_change.checkio() B last analyzed 2022-05-11 09:02 UTC

Complexity

Size

Duplication

Importance

Duplication Side-by-Side

Filter issues like

making_change.checkio() B
last analyzed 2022-05-11 09:02 UTC