
# https://adventofcode.com/2021/day/7


# Cache the values else it will not scale for type 1.
cache = {}

"""
type=0 - Each change of 1 step in horizontal position costs 1 unit of fuel.
type=1 - Each change of 1 step in horizontal position costs 1 more unit of fuel than the last.
"""

def cost(start, end, type=0):
    
    diff = abs(start - end)
    
    if type == 0:
        return diff
    
    # This will save a lot of time.
    if (diff in cache):
        return cache[diff]

    # If we are here, we are building cache. Slow route but should be hit on.
    ret = diff
    for ii in range(diff):
        ret = ret + ii
    
    cache[diff] = ret
    return ret


def findMostEfficient(data:list, type=0) -> int:

    # Most Efficient Fuel Usage
    mefu = 0

    for ii in range(1, max(data)):
        val = 0
        for dd in data:
            val = val + cost(ii, dd, type)
        
        if (mefu != 0):
            if (mefu > val):
                mefu = val
        else:
            mefu = val
    
    return mefu





mefu = findMostEfficient([16,1,2,0,4,2,7,1,2,14], 1)
print(mefu)

puzzle_data = [1101,1,29,67,1102,0,1,65,1008,65,35,66,1005,66,28,1,67,65,20,4,0,1001,65,1,65,1106,0,8,99,35,67,101,99,105,32,110,39,101,115,116,32,112,97,115,32,117,110,101,32,105,110,116,99,111,100,101,32,112,114,111,103,114,97,109,10,82,1266,26,290,428,9,676,880,16,340,1578,839,23,32,721,88,837,118,543,198,836,870,105,44,214,184,52,330,213,1224,1211,481,1707,409,78,1096,995,420,808,50,65,635,1186,228,5,359,290,1241,757,323,11,447,522,8,170,265,632,321,9,1707,1005,1194,466,137,982,905,373,158,601,247,373,202,432,168,694,785,568,144,576,1006,143,1506,298,1790,146,182,535,895,42,296,278,469,118,292,1375,206,235,1545,63,81,49,1405,660,41,1009,226,133,324,1250,113,10,687,223,78,10,745,21,55,1041,149,519,57,589,123,901,416,200,112,35,6,873,353,539,665,75,207,80,787,322,1026,178,19,630,12,263,1136,71,220,143,688,101,88,1600,16,141,55,64,436,19,889,267,470,884,31,546,846,601,15,84,399,83,1054,4,1417,766,525,162,640,73,2,110,189,494,85,44,263,618,583,263,591,1139,21,1593,187,115,520,142,887,3,12,565,78,88,114,803,157,307,1007,1365,1063,1481,431,410,125,19,1123,3,433,73,273,25,438,314,111,369,1188,526,516,509,1,186,143,1335,689,436,1002,260,791,12,36,380,80,306,173,45,24,856,1892,255,11,12,1221,422,8,1214,327,851,85,375,115,325,213,725,720,669,465,577,1,28,331,123,297,267,1586,478,259,572,204,365,461,618,364,5,630,377,26,259,331,956,164,89,115,1328,823,48,625,922,236,577,1113,251,156,846,261,500,73,1607,281,267,64,2,392,115,682,1833,861,1093,1165,52,1643,59,180,787,298,274,304,381,196,511,352,793,1043,984,30,85,190,109,276,303,251,1601,939,726,5,213,915,235,780,43,1212,1466,353,364,507,129,1109,1307,113,109,342,756,898,1015,63,949,127,887,175,91,409,1069,88,600,101,434,1021,477,1073,22,549,145,712,730,160,7,123,27,566,689,172,1496,543,154,345,442,3,860,47,69,319,487,17,1086,1305,329,788,738,688,421,139,1629,499,824,276,13,1033,885,522,140,328,113,311,297,252,33,168,1059,94,469,1816,2,107,149,652,350,200,173,367,100,229,219,400,43,283,1551,752,278,99,648,190,190,337,44,191,462,454,544,261,142,1204,231,924,209,858,768,211,223,186,1452,687,320,343,444,94,1231,285,324,431,36,309,705,672,69,1082,83,269,515,369,117,951,489,117,249,47,350,1408,93,203,800,1151,526,785,721,240,74,605,501,533,512,337,12,720,787,1521,894,112,187,170,1020,339,77,565,691,1141,129,1020,60,505,1383,178,1262,1302,750,743,1108,43,634,135,738,810,628,1807,938,530,61,1384,42,79,276,336,1434,1286,393,145,9,94,945,113,76,88,856,78,1750,499,994,527,1102,266,1164,796,143,726,480,357,577,910,460,448,379,402,1576,1353,257,1044,651,1206,44,126,353,1099,934,892,379,710,988,1041,367,116,377,546,1222,830,259,10,6,385,856,343,793,490,165,367,1022,1065,95,135,426,184,270,227,456,673,90,1363,1127,387,93,138,202,184,1071,134,15,813,134,200,80,144,128,1502,574,868,487,118,42,48,1135,1107,57,418,1093,1508,229,26,154,652,94,1254,171,502,407,276,1098,18,1000,345,150,123,211,1517,1005,590,1413,63,80,510,502,76,476,47,405,186,143,344,286,1277,934,64,512,12,1026,264,68,1420,10,245,10,352,6,585,567,48,428,816,1525,180,346,350,34,100,42,1354,699,265,445,1719,425,8,604,129,111,71,110,1170,703,36,317,198,104,655,95,1046,327,161,853,400,224,797,1221,794,684,321,1279,1,95,1253,671,203,43,220,55,90,1606,359,52,775,76,422,403,305,614,196,244,102,519,122,451,1610,79,709,336,1374,735,478,1123,658,906,615,688,561,518,39,1084,608,54,739,416,1648,1838,1280,1039,35,552,299,142,56,1217,1356,30,12,102,731,1343,224,452,304,1808,546,583,710,33,149,1126,565,314,745,22,115,263,813,113,52,308,944,981,441,544,129,1258,299,885,717,536,253,3,612,29,130,1099,1455,38,501,578,13,347,729,166,772,230,518,488,430,1093,140,16,120,1603,794,174,1361,1657,825,444,176,815,1353,469,264,191,988,12,104,11,1518,1096,347,606,350,18,1376,430,182,1229,131,111,731,174,111,304,715,35,410,701,78,46,390,291,1008,1779,620,2,1378,199,331,334,708,446,1141,773,159,702,716,13,582,161,259,90,180,607,539,611,312,622,151,522,921,150,522,273,421,842,111,21,159,148]
mefu = findMostEfficient(puzzle_data, 1)
print(mefu)
