Traveling Salesman Problem DRAFT I

class Tsp
    def initialize
        @db = [
            {
                'name' => 'La Plata',
                'distance' => [
                     0 => 0,
                     1 => 1543,
                     2 => 1510,
                     3 => 1203,
                     4 => 1043,
                     5 => 1191,
                     6 => 1023,
                     7 => 478,
                     8 => 940,
                     9 => 1040,
                    10 => 480,
                    11 => 715,
                    12 => 1150,
                    13 => 1110,
                    14 => 790,
                    15 => 1155,
                    16 => 1050,
                    17 => 620,
                    18 => 1158,
                    19 => 960,
                    20 => 1455,
                    21 => 2635,
                    22 => 3228

                ]
            },
            {
                'name' => 'Jujuy',
                'distance' => [
                     0 => 1543,
                     1 => 0,
                     2 => 99,
                     3 => 340,
                     4 => 500,
                     5 => 960,
                     6 => 860,
                     7 => 1107,
                     8 => 883,
                     9 => 1198,
                    10 => 1138,
                    11 => 930,
                    12 => 770,
                    13 => 1220,
                    14 => 1320,
                    15 => 572,
                    16 => 1345,
                    17 => 1530,
                    18 => 2200,
                    19 => 2124,
                    20 => 2385,
                    21 => 3565,
                    22 => 4158

                ]
            },
            {
                'name' => 'Salta',
                'distance' => [
                     0 => 1510,
                     1 => 99,
                     2 => 0,
                     3 => 307,
                     4 => 467,
                     5 => 948,
                     6 => 780,
                     7 => 1074,
                     8 => 803,
                     9 => 1118,
                    10 => 1105,
                    11 => 897,
                    12 => 695,
                    13 => 1145,
                    14 => 1245,
                    15 => 539,
                    16 => 1227,
                    17 => 1497,
                    18 => 2082,
                    19 => 2091,
                    20 => 2352,
                    21 => 3532,
                    22 => 4125

                ]
            },
            {
                'name' => 'Tucuman',
                'distance' => [
                     0 => 1203,
                     1 => 340,
                     2 => 307,
                     3 => 0,
                     4 => 160,
                     5 => 936,
                     6 => 768,
                     7 => 767,
                     8 => 791,
                     9 => 1106,
                    10 => 798,
                    11 => 590,
                    12 => 338,
                    13 => 838,
                    14 => 938,
                    15 => 232,
                    16 => 1005,
                    17 => 1190,
                    18 => 1860,
                    19 => 1784,
                    20 => 2045,
                    21 => 3225,
                    22 => 3818

                ]
            },
            {
                'name' => 'Santiago del Estero',
                'distance' => [
                     0 => 1043,
                     1 => 500,
                     2 => 467,
                     3 => 160,
                     4 => 0,
                     5 => 776,
                     6 => 610,
                     7 => 607,
                     8 => 633,
                     9 => 948,
                    10 => 638,
                    11 => 430,
                    12 => 360,
                    13 => 810,
                    14 => 850,
                    15 => 212,
                    16 => 977,
                    17 => 1030,
                    18 => 1567,
                    19 => 1624,
                    20 => 1885,
                    21 => 3065,
                    22 => 3658

                ]
            },
            {
                'name' => 'Formosa',
                'distance' => [
                     0 => 1191,
                     1 => 960,
                     2 => 948,
                     3 => 936,
                     4 => 776,
                     5 => 0,
                     6 => 168,
                     7 => 713,
                     8 => 191,
                     9 => 506,
                    10 => 744,
                    11 => 1043,
                    12 => 1136,
                    13 => 1543,
                    14 => 1463,
                    15 => 988,
                    16 => 1710,
                    17 => 1523,
                    18 => 2060,
                    19 => 2117,
                    20 => 2378,
                    21 => 3558,
                    22 => 4151

                ]
            },
            {
                'name' => 'Resistencia',
                'distance' => [
                     0 => 1023,
                     1 => 860,
                     2 => 780,
                     3 => 765,
                     4 => 610,
                     5 => 168,
                     6 => 0,
                     7 => 545,
                     8 => 23,
                     9 => 338,
                    10 => 576,
                    11 => 875,
                    12 => 970,
                    13 => 1420,
                    14 => 1295,
                    15 => 822,
                    16 => 1587,
                    17 => 1475,
                    18 => 2012,
                    19 => 2069,
                    20 => 2210,
                    21 => 3390,
                    22 => 3983

                ]
            },
            {
                'name' => 'Santa Fe',
                'distance' => [
                     0 => 478,
                     1 => 1107,
                     2 => 1074,
                     3 => 767,
                     4 => 607,
                     5 => 713,
                     6 => 545,
                     7 => 0,
                     8 => 568,
                     9 => 883,
                    10 => 31,
                    11 => 330,
                    12 => 765,
                    13 => 830,
                    14 => 625,
                    15 => 770,
                    16 => 885,
                    17 => 810,
                    18 => 1347,
                    19 => 1404,
                    20 => 1665,
                    21 => 2845,
                    22 => 3438

                ]
            },
            {
                'name' => 'Corrientes',
                'distance' => [
                     0 => 940,
                     1 => 883,
                     2 => 803,
                     3 => 791,
                     4 => 633,
                     5 => 191,
                     6 => 23,
                     7 => 568,
                     8 => 0,
                     9 => 315,
                    10 => 590,
                    11 => 898,
                    12 => 993,
                    13 => 1398,
                    14 => 1318,
                    15 => 845,
                    16 => 1565,
                    17 => 1378,
                    18 => 1989,
                    19 => 2046,
                    20 => 2187,
                    21 => 3367,
                    22 => 3960

                ]
            },
            {
                'name' => 'Posadas',
                'distance' => [
                     0 => 1040,
                     1 => 1198,
                     2 => 1118,
                     3 => 1106,
                     4 => 948,
                     5 => 506,
                     6 => 338,
                     7 => 883,
                     8 => 315,
                     9 => 0,
                    10 => 820,
                    11 => 1213,
                    12 => 1308,
                    13 => 1758,
                    14 => 1633,
                    15 => 1160,
                    16 => 1925,
                    17 => 1660,
                    18 => 2198,
                    19 => 2000,
                    20 => 2495,
                    21 => 3675,
                    22 => 4268

                ]
            },
            {
                'name' => 'Parana',
                'distance' => [
                     0 => 480,
                     1 => 1138,
                     2 => 1105,
                     3 => 798,
                     4 => 638,
                     5 => 744,
                     6 => 576,
                     7 => 31,
                     8 => 590,
                     9 => 820,
                    10 => 0,
                    11 => 361,
                    12 => 796,
                    13 => 861,
                    14 => 656,
                    15 => 801,
                    16 => 916,
                    17 => 841,
                    18 => 1378,
                    19 => 1435,
                    20 => 1696,
                    21 => 2876,
                    22 => 3469

                ]
            },
            {
                'name' => 'Cordoba',
                'distance' => [
                     0 => 715,
                     1 => 930,
                     2 => 897,
                     3 => 590,
                     4 => 430,
                     5 => 1043,
                     6 => 875,
                     7 => 330,
                     8 => 898,
                     9 => 1213,
                    10 => 361,
                    11 => 0,
                    12 => 435,
                    13 => 500,
                    14 => 420,
                    15 => 440,
                    16 => 670,
                    17 => 600,
                    18 => 1137,
                    19 => 1194,
                    20 => 1455,
                    21 => 3635,
                    22 => 3228

                ]
            },
            {
                'name' => 'La Rioja',
                'distance' => [
                     0 => 1150,
                     1 => 770,
                     2 => 695,
                     3 => 388,
                     4 => 360,
                     5 => 1136,
                     6 => 970,
                     7 => 765,
                     8 => 993,
                     9 => 1308,
                    10 => 796,
                    11 => 435,
                    12 => 0,
                    13 => 450,
                    14 => 550,
                    15 => 156,
                    16 => 617,
                    17 => 1035,
                    18 => 1472,
                    19 => 1629,
                    20 => 1890,
                    21 => 3070,
                    22 => 3663

                ]
            },
            {
                'name' => 'San Juan',
                'distance' => [
                     0 => 1110,
                     1 => 1220,
                     2 => 1145,
                     3 => 838,
                     4 => 810,
                     5 => 1543,
                     6 => 1420,
                     7 => 830,
                     8 => 1398,
                     9 => 1758,
                    10 => 861,
                    11 => 500,
                    12 => 450,
                    13 => 0,
                    14 => 320,
                    15 => 606,
                    16 => 167,
                    17 => 825,
                    18 => 1022,
                    19 => 1419,
                    20 => 1680,
                    21 => 2860,
                    22 => 3453

                ]
            },
            {
                'name' => 'San Luis',
                'distance' => [
                     0 => 790,
                     1 => 1320,
                     2 => 1245,
                     3 => 938,
                     4 => 850,
                     5 => 1463,
                     6 => 1295,
                     7 => 625,
                     8 => 1318,
                     9 => 1633,
                    10 => 656,
                    11 => 420,
                    12 => 550,
                    13 => 320,
                    14 => 0,
                    15 => 705,
                    16 => 260,
                    17 => 505,
                    18 => 883,
                    19 => 1099,
                    20 => 1360,
                    21 => 2540,
                    22 => 3133

                ]
            },
            {
                'name' => 'Catamarca',
                'distance' => [
                     0 => 1145,
                     1 => 572,
                     2 => 539,
                     3 => 232,
                     4 => 212,
                     5 => 988,
                     6 => 822,
                     7 => 770,
                     8 => 845,
                     9 => 1160,
                    10 => 801,
                    11 => 440,
                    12 => 156,
                    13 => 606,
                    14 => 705,
                    15 => 0,
                    16 => 773,
                    17 => 1040,
                    18 => 1588,
                    19 => 1634,
                    20 => 1895,
                    21 => 3075,
                    22 => 3668

                ]
            },
            {
                'name' => 'Mendoza',
                'distance' => [
                     0 => 1050,
                     1 => 1345,
                     2 => 1227,
                     3 => 1005,
                     4 => 977,
                     5 => 1710,
                     6 => 1587,
                     7 => 885,
                     8 => 1565,
                     9 => 1925,
                    10 => 916,
                    11 => 670,
                    12 => 617,
                    13 => 167,
                    14 => 260,
                    15 => 773,
                    16 => 0,
                    17 => 765,
                    18 => 855,
                    19 => 1359,
                    20 => 1620,
                    21 => 2800,
                    22 => 3393

                ]
            },
            {
                'name' => 'Santa Rosa',
                'distance' => [
                     0 => 620,
                     1 => 1530,
                     2 => 1497,
                     3 => 1190,
                     4 => 1030,
                     5 => 1523,
                     6 => 1475,
                     7 => 810,
                     8 => 1378,
                     9 => 1660,
                    10 => 841,
                    11 => 600,
                    12 => 1035,
                    13 => 825,
                    14 => 505,
                    15 => 1040,
                    16 => 765,
                    17 => 0,
                    18 => 537,
                    19 => 594,
                    20 => 855,
                    21 => 2035,
                    22 => 2628

                ]
            },
            {
                'name' => 'Neuquen',
                'distance' => [
                     0 => 1158,
                     1 => 2200,
                     2 => 2082,
                     3 => 1860,
                     4 => 1567,
                     5 => 2060,
                     6 => 2012,
                     7 => 1347,
                     8 => 1989,
                     9 => 2198,
                    10 => 1378,
                    11 => 1137,
                    12 => 1472,
                    13 => 1022,
                    14 => 883,
                    15 => 1588,
                    16 => 855,
                    17 => 537,
                    18 => 0,
                    19 => 660,
                    20 => 750,
                    21 => 1930,
                    22 => 2523

                ]
            },
            {
                'name' => 'Viedma',
                'distance' => [
                     0 => 960,
                     1 => 2124,
                     2 => 2091,
                     3 => 1784,
                     4 => 1624,
                     5 => 2117,
                     6 => 2069,
                     7 => 1404,
                     8 => 2046,
                     9 => 2000,
                    10 => 1435,
                    11 => 1194,
                    12 => 1629,
                    13 => 1419,
                    14 => 1099,
                    15 => 1634,
                    16 => 1359,
                    17 => 594,
                    18 => 660,
                    19 => 0,
                    20 => 495,
                    21 => 1675,
                    22 => 2268

                ]
            },
            {
                'name' => 'Rawson',
                'distance' => [
                     0 => 1455,
                     1 => 2385,
                     2 => 2352,
                     3 => 2045,
                     4 => 1885,
                     5 => 2378,
                     6 => 2210,
                     7 => 1665,
                     8 => 2187,
                     9 => 2495,
                    10 => 1696,
                    11 => 1455,
                    12 => 1890,
                    13 => 1680,
                    14 => 1360,
                    15 => 1895,
                    16 => 1620,
                    17 => 855,
                    18 => 750,
                    19 => 495,
                    20 => 0,
                    21 => 1180,
                    22 => 1773

                ]
            },
            {
                'name' => 'Rio Gallegos',
                'distance' => [
                     0 => 2635,
                     1 => 3565,
                     2 => 3532,
                     3 => 3225,
                     4 => 3065,
                     5 => 3558,
                     6 => 3390,
                     7 => 2845,
                     8 => 3367,
                     9 => 3675,
                    10 => 2876,
                    11 => 2635,
                    12 => 3070,
                    13 => 2860,
                    14 => 2540,
                    15 => 3075,
                    16 => 2800,
                    17 => 2035,
                    18 => 1930,
                    19 => 1675,
                    20 => 1180,
                    21 => 0,
                    22 => 593

                ]
            },
            {
                'name' => 'Ushuaia',
                'distance' => [
                     0 => 3228,
                     1 => 4158,
                     2 => 4125,
                     3 => 3818,
                     4 => 3658,
                     5 => 4151,
                     6 => 3983,
                     7 => 3438,
                     8 => 3960,
                     9 => 4268,
                    10 => 3469,
                    11 => 3228,
                    12 => 3660,
                    13 => 3453,
                    14 => 3133,
                    15 => 3668,
                    16 => 3393,
                    17 => 2628,
                    18 => 2523,
                    19 => 2268,
                    20 => 1773,
                    21 => 593,
                    22 => 0

                ]
            }
        ]
        # Initialize the "used" capitals array
        @used = []
        @db.count.times {
            | i |
            @used[i] = 0
        }

        # In this global variable we save the total of Kms
        @total_route = 0
    end
    def test
        #self.travel(0)
        puts @db[0]['distance'][1]
    end
    def travel(start)
        @db.count.times {
            start = self.findShortestNextPath(start)
        }
    end
    def findShortestNextPath(start)
        shortest_distance = 999999
        shortest_aim = 0
        found = false
        @db.count.times{
            | i |
            if @db[start]['distance'][i] < shortest_distance && @used[i] == 0 then
                shortest_distance = @db[start]['distance'][i]
                shortest_aim = i
                found = true
            end
        }
        if found == true then
            @used[shortest_aim] = 1
            @total_route = @total_route+shortest_distance
            printf("%d --> %d | %dkms \n",start,shortest_aim,shortest_distance)
        else
            printf("Total distance: %d",@total_route)
        end
    end
end
t = Tsp.new
t.test