In [1]:

    

import sys, math
import pprint
debug = True

class Node:
    def __init__(self, num):
        self.num = num
        self.routes = []
        self.dist = math.inf
    def __str__(self):
        return f"node num: {self.num}, distance: {self.dist}"
    def __repr__(self):
        return self.__str__()

class Edge:
    def __init__(self, backNode, foreNode, dist):
        self.back = backNode
        self.fore = foreNode
        self.dist = dist


    

In [2]:

    

def build(mx, startN=0):
    """Build graph that has links to the next node and the node 3 times
away."""
    nodes = [Node(i) for i in range(startN, mx + 1)]
    for i in range(startN, mx):
        ind = i - startN
        n = nodes[ind]
        n1 = nodes[ind+1]
        e = Edge(n, n1, 1)
        n.routes.append(e)
        if 3*i <= mx:
            n3 = nodes[i*3 - startN]
            e = Edge(n, n3, 1)
            n.routes.append(e)
    
    return nodes
    
def sortList(l):
    l.sort(key=lambda n: n.dist)
    
def getMin(l):
    return min(l, key=lambda n: n.dist)

def log(msg):
    if debug:
        sys.stderr.write(str(msg) + "\n")


    

In [3]:

    

l=[2,5,6]
print(l.pop(0))


    

    




2

In [4]:

    

def dijkstras(nodes, end):
    nodes[0].dist = 0
    seen = {}
    # copy list
    nl = list(nodes)
    
    pathlen = 0
    lengths = [0, math.inf]
    bylen = {}
    
    while len(nl) > 0:
        
        cur = nl.pop(0)
        seen[cur.num] = cur
        if cur.num == end:
            break
        log(f"reading node {cur}")
        for e in cur.routes:
            dist = cur.dist + e.dist
            if dist < e.fore.dist:
                log(f"setting dist of {dist} on node {e.fore}")
                e.fore.dist = dist
    return seen, nl


    

In [5]:

    

debug = False
nodes = build(10000, startN=1)
seen, notseen = dijkstras(nodes, 10000)
print(f"number not seen: {len(notseen)}")
# pprint.pprint(seen)


    

    




number not seen: 3785

In [6]:

    

def distanceTo(n):
    dist = 0
    num = n
    while num > 1:
        rem = num % 3
        if rem == 0:
            dist += 1
            num = num // 3
        else:
            num -= 1
            dist += 1
        log(f"num: {num}")
    return dist


    

In [7]:

    

debug = True
print (distanceTo(5387))


    

    




15






    




num: 5386
num: 5385
num: 1795
num: 1794
num: 598
num: 597
num: 199
num: 198
num: 66
num: 22
num: 21
num: 7
num: 6
num: 2
num: 1

In [ ]: