ePL Travelling Salesman

/******************************************************************************
 *
 * Travelling Salesman Problem - Demo 1
 *
 * Name:        TSP_ATT48_BF
 * Desc:        48 Captitals of the US
 * Diminsions:    48
 * Weight Type:    ATT - Pseudo-Euclidean distance
 * Algorithm:    Brute Force
 *
 * Memory Map:
 *   Round Number:          m[ 10]
 *   Random Input:          m[  0]
 *   Cost Matrix Vars:        u[ 20] - u[ 23]
 *   X Dist & Y Dist:        i[  0] - i[  1]
 *   Distance Point A to B    f[  0]
 *   Algorithm Variables:    u[ 30] - u[ 34]
 *   Calculated Distance:    u[ 40]
 *   Loop Counters:            u[ 90] - u[ 91]
 *   Point Data:               u[100] - u[195]
 *   Path Data:               u[200] - u[248]
 *   Cost Matrix:             u[300] - u[2602]
 *
 *****************************************************************************/

array_int    2;
array_uint    2700;
array_float    1;

submit_sz  49;
submit_idx 200;


// Initialize VM Memory With TSP Point Data
function init_point_data {

    // Each TSP Point Has An X & Y Value
    // For Example, Point 1 Has X = u[100] & Y = u[101]
    u[100] = 6734;
    u[101] = 1453;
    u[102] = 2233;
    u[103] = 10;
    u[104] = 5530;
    u[105] = 1424;
    u[106] = 401;
    u[107] = 841;
    u[108] = 3082;
    u[109] = 1644;
    u[110] = 7608;
    u[111] = 4458;
    u[112] = 7573;
    u[113] = 3716;
    u[114] = 7265;
    u[115] = 1268;
    u[116] = 6898;
    u[117] = 1885;
    u[118] = 1112;
    u[119] = 2049;
    u[120] = 5468;
    u[121] = 2606;
    u[122] = 5989;
    u[123] = 2873;
    u[124] = 4706;
    u[125] = 2674;
    u[126] = 4612;
    u[127] = 2035;
    u[128] = 6347;
    u[129] = 2683;
    u[130] = 6107;
    u[131] = 669;
    u[132] = 7611;
    u[133] = 5184;
    u[134] = 7462;
    u[135] = 3590;
    u[136] = 7732;
    u[137] = 4723;
    u[138] = 5900;
    u[139] = 3561;
    u[140] = 4483;
    u[141] = 3369;
    u[142] = 6101;
    u[143] = 1110;
    u[144] = 5199;
    u[145] = 2182;
    u[146] = 1633;
    u[147] = 2809;
    u[148] = 4307;
    u[149] = 2322;
    u[150] = 675;
    u[151] = 1006;
    u[152] = 7555;
    u[153] = 4819;
    u[154] = 7541;
    u[155] = 3981;
    u[156] = 3177;
    u[157] = 756;
    u[158] = 7352;
    u[159] = 4506;
    u[160] = 7545;
    u[161] = 2801;
    u[162] = 3245;
    u[163] = 3305;
    u[164] = 6426;
    u[165] = 3173;
    u[166] = 4608;
    u[167] = 1198;
    u[168] = 23;
    u[169] = 2216;
    u[170] = 7248;
    u[171] = 3779;
    u[172] = 7762;
    u[173] = 4595;
    u[174] = 7392;
    u[175] = 2244;
    u[176] = 3484;
    u[177] = 2829;
    u[178] = 6271;
    u[179] = 2135;
    u[180] = 4985;
    u[181] = 140;
    u[182] = 1916;
    u[183] = 1569;
    u[184] = 7280;
    u[185] = 4899;
    u[186] = 7509;
    u[187] = 3239;
    u[188] = 10;
    u[189] = 2676;
    u[190] = 6807;
    u[191] = 2993;
    u[192] = 5185;
    u[193] = 3258;
    u[194] = 3023;
    u[195] = 1942;

}

// Create TSP Cost Matrix
// This Creates A 48x48 Matrix With The Cost (Distance) Between Each Point
function create_cost_matrix {

    u[20] = 100;    // Index of x[i] - Point A (Start At Point 0) 
    u[21] = 100;    // Index of y[i] - Point B (Start At Point 0) 
    u[22] = 300;    // Index of dij - Cost Matrix Element
    u[23] = 0;        // tij - Rounded Distance Between A & B
    i[0] = 0;        // xd - X Distance
    i[1] = 0;        // yd - Y Distance
    f[0]  = 0;        // rij - Pseudo-Euclidean Distance Between A & B

    // Outer Loop - Point A = 0 to 48
    // u[90] is the loop counter
    // 48 is # of iterations
    // 48 is # of iterations for WCET Calc
    repeat(u[90], 48, 48) {

        // Inner Loop - Point B = 0 to 48
        // u[91] is the loop counter
        repeat(u[91], 48, 48) {

            // When Point A = Point B, Distance = 0
            if(u[21] == u[20]) {
                u[21] += 2;   // Move To Next Point B
                u[u[22]] = 0; // Distance To Self Is Zero
                u[22]++;      // Move To Next Matrix Element
                continue;
            }

            // Calculate Distance From Point A To Point B
            i[0] = u[u[21]] - u[u[20]];                                // xd
            i[1] = u[u[21] + 1] - u[u[20] + 1];                        // yd
            f[0] = sqrt(((i[0]*i[0]) + (i[1]*i[1])) / 10.0);        // rij
            u[23] = (f[0] + 0.5);                                    // tij - equivalent of nint function
            if (u[23] < f[0])
                u[u[22]] = u[23] + 1;                                // dij
            else
                u[u[22]] = u[23];                                    // dij

            u[21] += 2;        // Move To Next Point B
            u[22]++;        // Move To Next Matrix Element
        }

        u[20] += 2;            // Increment Point A
        u[21] = 100;        // Reset Point B
    }

}

function main {

    init_point_data();
    create_cost_matrix();

    // Initialize The Path ( Points 0 To 48 In Sequential Order)
    // Path Variables Start At u[200]
    // u[90] is the loop counter
    repeat(u[90], 48, 48) {
        u[200 + u[90]] = u[90];
    }

    // Randomize The Path
    u[200] = 0;                                // Start At Point Zero
    u[248] = 0;                                // End At Point Zero
    u[30] = 47;                                // Path Array Offset - Start At Final Point In Path
    repeat(u[90], 47, 47) {
        u[31] = (abs(m[0]) % u[30]) + 1;    // Use m[0] to create a random number between 0 and 47
        u[32] = u[200 + u[31]];                // Index of first point in path to swap
        u[200 + u[31]] = u[200 + u[30]];    // Index of second point in path to swap
        u[200 + u[30]] = u[32];                // Swap points
        u[30]--;                            // Move to next point in path
    }

    // Brute Force Logic
    u[40] = 0;    // Total Distance
    repeat(u[90], 48, 48) {
        u[33] = u[200 + u[90]];                     // Cost Matrix Row
        u[34] = u[200 + u[90] + 1];                 // Cost Matrix Column
        u[40] += u[(300 + (u[33] * 48) + u[34])];    // Lookup Point A to Point B distance in Cost Matrix and add to total distance
    }

    // Bounty Is Rewarded When Total Distance < 11,000
    verify_bty (u[40] < 11000);

    // POW Is Rewarded When The MD5 Hash Of Summed Path Is Less Than Target
    u[50] = u[200] + u[201] + u[202] + u[203] + u[204] + u[205] + u[206] + u[207] + u[208] + u[209] + u[210] + u[211];
    u[51] = u[212] + u[213] + u[214] + u[215] + u[216] + u[217] + u[218] + u[219] + u[220] + u[221] + u[222] + u[223];
    u[52] = u[224] + u[225] + u[226] + u[227] + u[228] + u[229] + u[230] + u[231] + u[232] + u[233] + u[234] + u[235];
    u[53] = u[236] + u[237] + u[238] + u[239] + u[240] + u[241] + u[242] + u[243] + u[244] + u[245] + u[246] + u[247];
    verify_pow (u[50], u[51], u[52], u[53]);

}

// In this example, the miner submits the solution (Path that meets Bounty or POW criteria)
// Therefore, there is no need for the randomization logic in the verify function.
// u[200]-u[248] is updates with the submitted path and the solution is validated by the node.
function verify {

    // No need to create a cost matrix for the verify function
    // As we only need the distances for the submitted path
    init_point_data();

    // Total Distance
    u[40] = 0;

    // Loop through submited path to calculate total distance
    repeat(u[90], 48, 48) {

        u[20] = u[200 + u[90]];            // Set Point A
        u[21] = u[201 + u[90]];            // Set Point B        

        // Calculate Distance From Point A To Point B
        i[0] = u[100 + (u[21] * 2)] - u[100 + (u[20] * 2)];        // xd
        i[1] = u[101 + (u[21] * 2)] - u[101 + (u[20] * 2)];        // yd
        f[0] = sqrt(((i[0]*i[0]) + (i[1]*i[1])) / 10.0);        // rij
        u[23] = (f[0] + 0.5);                                    // tij - equivalent of nint function
        if (u[23] < f[0])
            u[40] += u[23] + 1;                                    // dij
        else
            u[40] += u[23];                                        // dij

    }

    // Bounty Is Rewarded When Total Distance < 11,000
    verify_bty (u[40] < 11000);

    // POW Is Rewarded When The MD5 Hash Of Summed Path Is Less Than Target
    u[50] = u[200] + u[201] + u[202] + u[203] + u[204] + u[205] + u[206] + u[207] + u[208] + u[209] + u[210] + u[211];
    u[51] = u[212] + u[213] + u[214] + u[215] + u[216] + u[217] + u[218] + u[219] + u[220] + u[221] + u[222] + u[223];
    u[52] = u[224] + u[225] + u[226] + u[227] + u[228] + u[229] + u[230] + u[231] + u[232] + u[233] + u[234] + u[235];
    u[53] = u[236] + u[237] + u[238] + u[239] + u[240] + u[241] + u[242] + u[243] + u[244] + u[245] + u[246] + u[247];
    verify_pow (u[50], u[51], u[52], u[53]);

}