These are chat archives for Codewars/codewars.com/kata-solving-help

20th
Feb 2017
Jonathan Kohn
@jk16
Feb 20 2017 02:44
@itamargal hey just looking at this now!
so in Java ArrayList class is jst like an array except it has methods such as add so you dont have to worry about arraysize
itamargal
@itamargal
Feb 20 2017 03:24
@jk16 Gotcha.
Marc KesslerWenicker
@MSKW76_twitter
Feb 20 2017 07:03
not sure if I should post in kata-solving-help as I'm fairly confident my code is correct as I have written my own tests. Although it's not even taking a second to run locally, it times out on codewars. Any suggestions how to tackle this? It passes the basic test ftiw.
Kata in question: https://www.codewars.com/kata/biggest-sum/
After trying a few things, I ended up implementing bellman-ford where I convert the input matrix into a graph
def initialize(graph, source):
    """Set up each node within the graph where we assume that rest of the nodes
    are very far away."""
    d = {}
    p = {}
    for node in graph:
        d[node] = float('Inf')
        p[node] = None
    d[source] = 0 # For the source we know how to reach
    return d, p

def relax(node, neighbour, graph, d, p):
    """Check if the distance between node and neighbour is lower than the one
    we know of and record if it is."""
    if d[neighbour] > d[node] + graph[node][neighbour]:
        d[neighbour]  = d[node] + graph[node][neighbour]
        p[neighbour] = node

def bellman_ford(graph, source):
    """Returns two dictionaries, d and p where d holds all nodes and the cost
    to reach each one and p holds the predecessors which show which path
    to take each node with the lost cost."""
    d, p = initialize(graph, source)
    for i in range(len(graph)-1): #Run this until it converges
        for u in graph:
            for v in graph[u]:
                relax(u, v, graph, d, p)

    #check for negative-weight cycles
    for u in graph:
        for v in graph[u]:
            assert d[v] <= d[u] + graph[u][v]

    return d, p

def make_node_matrix(matrix):
    """Convert input matrix to matrix of tuples with node name and value to be
    input into function to convert to graph. Values are inverted for input
    into shortest path algorithm."""
    node_names = ['n{0}'.format(p) for p in range(1, len(matrix)**2 + 1)]
    nodes = zip(node_names, [ -n for row in matrix for n in row])
    node_matrix = []
    for i in range(len(matrix)):
        sub_list = []
        for idx, t in enumerate(nodes):
            sub_list.append(t)
            if idx == len(matrix) - 1:
                break
        node_matrix.append(sub_list)
    return node_matrix

def make_graph_from_matrix(grid):
    """Convert an input matrix of tuples into a graph where we assume the
    direction of traversal in the matrix only allowed to be one to the right
    or down."""
    graph= {}
    for row_count, row in enumerate(grid):
        for col, node in enumerate(row):
            vertex = {}
            ref, value = node
            if col == len(row) - 1:
                if row_count == len(grid) - 1:
                    key, value = grid[len(grid) - 1][len(grid) -1]
                    graph[key] = vertex
                    break
                key, value = grid[row_count + 1][col]
                vertex[key] = value
            elif row_count == len(grid) - 1:
                key, value = grid[row_count][col + 1]
                vertex[key] = value
            else:
                vertex.update([grid[row_count][col + 1], grid[row_count + 1][col]])
            graph[ref] = vertex
    return graph

def find_sum(m):
    """Find the highest sum in a matrix from top left to bottom right."""
    node_matrix = make_node_matrix(m)
    graph = make_graph_from_matrix(node_matrix)
    last_node = 'n' + str(len(m) ** 2)
    d, p = bellman_ford(graph, 'n1')
    return abs(d[last_node]) + m[0][0]
itamargal
@itamargal
Feb 20 2017 13:53
@MSKW76_twitter Do you know on what input your solution times out?