Converting Dijkstra's Algorithm from Python3 to CircuitPython (TI-Python)

user_3042018 0
Viewed 65

I'm writing Python code on one of the new TI-84 Python edition calculators. These use a version of CircuitPython with limited support for some quite basic features.

This includes missing dictionary methods such as items() and values().

My original version of Dijkstra's Algorithm is below, followed by a nearly complete version in TI-Python. I'm having trouble converting the final two items() instances with working alternatives.

nodes = ('A', 'B', 'C', 'D', 'E')
distances = {
    'A': {'B': 6, 'D': 1},
    'B': {'A': 6, 'C': 5, 'D': 2, 'E' :2},
    'C': {'B': 5, 'E': 5},
    'D': {'A': 1, 'B': 2, 'E': 1},
    'E': {'B': 2, 'C': 5, 'D': 1}}


unvisited = {node: None for node in nodes} #using None as +inf
visited = {}
current = 'A' # the start node
currentDistance = 0
unvisited[current] = currentDistance

while True:
    # for the nodes adjacent to the current node.
    for neighbour, distance in distances[current].items():
        # ignore if already visited
        if neighbour not in unvisited:
            continue
        # calculate the total distance to this new node
        newDistance = currentDistance + distance
        # if this adjacent node has a lower distance
        if unvisited[neighbour] is None or unvisited[neighbour] > newDistance:
            # update distance to this new, lower distance
            unvisited[neighbour] = newDistance
    # add current node and distance from start to visited list
    visited[current] = currentDistance
    # Remove current node from unvisited list
    del unvisited[current]
    # if all nodes have been visited
    if not unvisited:
        # exit
        break
    # candidates for next node to visit
    print(unvisited.items())
        # print(node[1])
    candidates = [node for node in unvisited.items() if node[1]]
    print(candidates)
    current, currentDistance = sorted(candidates, key = lambda x: x[1])[0]

# print(visited)

print(dict(sorted(visited.items())))

TI-Python version:

ns = ("A", "B", "C", "D", "E")
ds = {
    "A": {"B": 6, "D": 1},
    "B": {"A": 6, "C": 5, "D": 2, "E": 2},
    "C": {"B": 5, "E": 5},
    "D": {"A": 1, "B": 2, "E": 1},
    "E": {"B": 2, "C": 5, "D": 1}
}

un = {no: None for no in ns}
vi = {}
cn = "A"
cd = 0
un[cn] = cd

while True:
    for ne in sorted(ds[cn]):
        di = ds[cn][ne]
        if ne not in un:
            continue
        nd = cd + di
        if un[ne] is None or un[ne] > nd:
            un[ne] = nd
    vi[cn] = cd
    del un[cn]
    if not un:
        break
    cs = [no for no in un.items() if no[1]]
    cn, cd = sorted(cs, key=lambda x: x[1])[0]

print(dict(sorted(vi.items())))

Could someone please explain how to refactor cs = [no for no in un.items() if no[1]] and print(dict(sorted(vi.items()))) so they don't need the .items() or .values(). methods?

adafruit-circuitpython dictionary python
1 Answers

Whilst .items() is very useful, it is equivalent to iterating the keys and then looking up the value.

for k in dict:
    v = dict[k]

is equivalent to

for k, v in dict.items():

Thus a crude refactor of

cs = [no for no in un.items() if no[1]]

Would be:

cs = [[k, un[k]] for k in un if un[k]]

Note that the original could be better written as:

cs = [[k,v] for k, v in un.items() if v]

Likewise,

print(dict(sorted(vi.items())))

is directly equivalent to:

print(dict(sorted([k, vi[k] for k in vi]))

but that's not very readable IMHO. I would do:

print({k: vi[k] for k in sorted(vi.keys()})
user_154526010
Related