shortestPath() - Code Metrics - Inspection of "feat(Dropbox): Making Change" - KenMercusLai/checkio - Measure and Improve Code Quality continuously with Scrutinizer

Test Setup Failed

Push — master ( a0f0b4...21d9c1 )

by Ken M.

created 2018-05-05 07:03 UTC

shortestPath() B

↳ Parent: Project

Complexity

Conditions

Size

Total Lines

Duplication

Lines	0
Ratio	0 %

Importance

Changes

Metric	Value
cc	5
dl	0
loc	13
rs	8.5454
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			def shortestPath(graph, start, end):
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

Push — master ( a0f0b4...21d9c1 )

shortestPath() B

Complexity

Size

Duplication

Importance

Duplication Side-by-Side

Filter issues like