Untitled

'''
Suppose we have an unsorted log file of accesses to web resources. Each log entry consists of an access time, the ID of the user making the access, and the resource ID.

Write a function that takes the logs as input, builds the transition graph and returns it as an adjacency list with probabilities. Add __START__ and __END__ states.

Specifically, for each resource, we want to compute a list of every possible next step taken by any user, together with the corresponding probabilities. The list of resources should include __START__ but not __END__, since by definition __END__ is a terminal state.

Expected output for logs1:
    ["accesstime", "ID", "resourceID"]
logs1 = [
    ["200", "user_1", "resource_5"],
    ["3", "user_1", "resource_1"],
    ["620", "user_1", "resource_1"],
    ["620", "user_3", "resource_1"],
    ["34", "user_6", "resource_2"],
    ["95", "user_9", "resource_1"],
    ["416", "user_6", "resource_1"],
    ["58523", "user_3", "resource_1"],
    ["53760", "user_3", "resource_3"],
    ["58522", "user_22", "resource_1"],
    ["100", "user_3", "resource_6"],
    ["400", "user_6", "resource_2"],
]

transition_graph(logs1) # => 

{
    '_START_':    {'resource_1': 0.6, 'resource_2': 0.2, 'resource_6': 0.2},
    'resource_1': {'_END_': 0.71, 'resource_3': 0.14, 'resource_5': 0.14},
    'resource_2': {'resource_1': 0.5, 'resource_2': 0.5},
    'resource_3': {'resource_1': 1.0},
    'resource_5': {'resource_1': 1.0},
    'resource_6': {'resource_1': 1.0}
}

{
    'user_1': ['resource_1', 'resource_5', 'resource_1'],
    'user_3': ['resource_6', 'resource_1', 'resource_3', 'resource_1'],
    'user_6': ['resource_2', 'resource_2', 'resource_1'],
    'user_9': ['resource_1'],
    'user_22': ['resource_1'],
}
    #probability: 

For example, of 5 total users, 3 users have resource_1 as a first visit (user_1, user_9, user_22), 1 user has resource_6 as a first visit (user_3), and 1 user has resource_2 as a first visit (user_6), so the possible next steps for __START__ are resource_1 with probability 3/5, resource_2 with probability 1/5, and resource_6 with probability 1/5.

logs1 = [
    ["200", "user_1", "resource_5"],
    ["3", "user_1", "resource_1"],
    ["620", "user_1", "resource_1"],
    ["620", "user_3", "resource_1"],
    ["34", "user_6", "resource_2"],
    ["95", "user_9", "resource_1"],
    ["416", "user_6", "resource_1"],
    ["58523", "user_3", "resource_1"],
    ["53760", "user_3", "resource_3"],
    ["58522", "user_22", "resource_1"],
    ["100", "user_3", "resource_6"],
    ["400", "user_6", "resource_2"],
]
These are the resource paths per user for the first logs example, ordered by access time:
{
    'user_1': ['resource_1', 'resource_5', 'resource_1'],
    'user_3': ['resource_6', 'resource_1', 'resource_3', 'resource_1'],
    'user_6': ['resource_2', 'resource_2', 'resource_1'],
    'user_9': ['resource_1'],
    'user_22': ['resource_1'],
}

Expected output for logs2:
transition_graph(logs2) # => 
{
    '_START_':    {'resource_2': 1.0},
    'resource_1': {'resource_2': 0.5, 'resource_3': 0.5},
    'resource_2': {'_END_': 0.5, 'resource_3': 0.5},
    'resource_3': {'resource_1': 1.0}}

Expected output for logs3:
transition_graph(logs3) # => 
{
  '__START__':  {'resource_5': 1.0},
  'resource_5': {'__END__': 1.0}
}

Expected output for logs4:
transition_graph(logs4) # => 
{
    '_START_':    {'resource_5': 1.0},
    'resource_5': {'_END_': 0.6, 'resource_5': 0.2, 'resource_7': 0.2},
    'resource_7': {'_END_': 1.0}
}

Expected output for logs5:
transition_graph(logs5) # => 
{
    '_START_':    {'resource_3': 1.0},
    'resource_3': {'_END_': 0.14, 'resource_3': 0.86}
}

All Test Cases:
transition_graph(logs1)
transition_graph(logs2)
transition_graph(logs3)
transition_graph(logs4)
transition_graph(logs5)


Complexity analysis variables:

n: number of logs in the input
'''
# completeness solution > complexity


def transition_graph(logs):
    # logs (list of list) -> resource_path (dict user:path) -> transition_graph(dest: probability of next)
    # sort the logs   sorted(log)  nlogn
    logs = [[int(x[0]), x[1], x[2]] for x in logs]

    logs = sorted(logs)

    # res_graph
    graph = {}

    # loop for the logs
    for log in logs:
        time, user, res = log[0], log[1], log[2]
        if user not in graph:
            graph[user] = [res]
        else:
            graph[user].append([res])
    # access the access_time, user, res
    # if not in res_path:
        # define
    # append(res)
    start = '_START_'
    trans_graph = {
        '_START_': {"count": 0}}

    def traverse(resources, trans_graph):
        prev = None

        for res in resources:
            print("RESULT", res)
            res = res[0]
            # dealing with start
            if prev is None:
                if res not in trans_graph[start]:
                    trans_graph[start][res] = 1
                else:
                    trans_graph[start][res] += 1

            else:
                if prev not in trans_graph:
                    trans_graph[prev] = {res: 1, 'count': 1}
                else:
                    trans_graph[prev][res] += 1
                    trans_graph[prev]['count'] = 1
            prev = res

        end = "_END_"
        if end not in trans_graph[prev]:
            trans_graph[prev][end] = 1
        else:
            trans_graph[prev][end] += 1

    # end=
    # call traverse
    for user in graph:
        res = graph[user][0]
        traverse(graph[user], trans_graph)
    # probabilitis

    for res in trans_graph:
        count = trans_graph[res]['count']

        for next_ in trans_graph[res]:
            trans_graph[res][next_] /= count

        # delte
        del trans_graph[res]['count']

    return trans_graph


logs1 = [
    ["200", "user_1", "resource_5"],
    ["3", "user_1", "resource_1"],
    ["620", "user_1", "resource_1"],
    ["620", "user_3", "resource_1"],
    ["34", "user_6", "resource_2"],
    ["95", "user_9", "resource_1"],
    ["416", "user_6", "resource_1"],
    ["58523", "user_3", "resource_1"],
    ["53760", "user_3", "resource_3"],
    ["58522", "user_22", "resource_1"],
    ["100", "user_3", "resource_6"],
    ["400", "user_6", "resource_2"],
]

logs2 = [
    ["357", "user", "resource_2"],
    ["1262", "user", "resource_1"],
    ["1462", "user", "resource_2"],
    ["1060", "user", "resource_1"],
    ["756", "user", "resource_3"],
    ["1090", "user", "resource_3"],
]

logs3 = [
    ["300", "user_10", "resource_5"],
]

logs4 = [
    ["1", "user_96", "resource_5"],
    ["1", "user_10", "resource_5"],
    ["301", "user_11", "resource_5"],
    ["301", "user_12", "resource_5"],
    ["603", "user_12", "resource_5"],
    ["1603", "user_12", "resource_7"],
]

logs5 = [
    ["300", "user_1", "resource_3"],
    ["599", "user_1", "resource_3"],
    ["900", "user_1", "resource_3"],
    ["1199", "user_1", "resource_3"],
    ["1200", "user_1", "resource_3"],
    ["1201", "user_1", "resource_3"],
    ["1202", "user_1", "resource_3"]
]

transition_graph(logs1)