/* Stupid Dogs */
world/loop_checks = 0

// Range (-RANGE to RANGE) of values for A and B for dogs
var/const/RANGE = 10
var/const/NUMDOGS = 50

dog
    var/A = 0
    var/B = 0
    New(var/A, var/B)
        src.A = A
        src.B = B
    proc/value()
        return A + B
    proc/string()
        return "([A],[B])"

// Table of values for the dynamic programming
dp_table
    var/list/table
    var/len
    var/size
    var/half
    New(var/len)
        var/INF = 999999**99
        var/NEG_INF = -1*INF
        src.len = len
        half = (len+1) * RANGE
        size = 2 * half + 1
        table = new /list(len+1, size, size)
        for(var/a = 1 to len+1)
            for(var/b = 1 to size)
                for(var/c = 1 to size)
                    table[a][b][c] = NEG_INF
        // Initialize all valid "endpoints" as 0
        for(var/x = half+1 to size)
            for(var/y = half+1 to size)
                table[1][x][y] = 0
    proc/get(var/a,var/b,var/c)
        return table[a+1][b+half+1][c+half+1]
    proc/put(var/a,var/b,var/c,var/value)
        table[a+1][b+half+1][c+half+1] = value
    
    proc/solution()
        return get(len-1,0,0)
    
    proc/tofile()
        set background = 1
        var/S = ""
        for(var/a = 1 to len+1)
            for(var/b = 1 to size)
                for(var/c = 1 to size)
                    S += "[table[a][b][c]]\t"
                S += "\n"
            S += "\n\n"
        fdel("output.txt")
        text2file(S,"output.txt")

// Attempt at an algorithm to solve the problem
proc/alg(var/list/L)
    var/dp_table/T = new(L.len)
    var/max = T.half
    for(var/pos = 1 to L.len)
        var/dog/D = L[pos]
        for(var/a = -max to max)
            for(var/b = -max to max)
                // If we can improve by taking this dog, take it
                var/dont = T.get(pos-1,a,b)
                var/newa = a + D.A
                var/newb = b + D.B
                
                // Bounds protection
                if(abs(newa) > max || abs(newb) > max)
                    T.put(pos,a,b,dont)
                    continue
                
                var/take = T.get(pos-1,newa,newb) + D.value()
                if(take > dont)
                    T.put(pos,a,b,take)
                // Otherwise, carry down the above value
                else
                    T.put(pos,a,b,dont)
                    
    return T

mob/verb/test()
    var/list/L
    do
        L = list()
        for(var/v = 1 to NUMDOGS)
            L += new /dog(rand(-RANGE,RANGE),rand(-RANGE,RANGE))
        world << "LIST:"
        for(var/dog/D in L)
            world << D.string()
    while(alert("OKAY?","confirm","yes","no") == "no")
    
    var/dp_table/sol = alg(L)
    world << "SOLUTION: [sol.solution()]"