This was all done on an iPad, which means I didn't write any notes as I went. I'll try to explain my thinking after the code fragments (which I'm not going to edit in the spirit of openness and transparency)
# Lets see if we can find the most distance
# For a given number, the distance needed to move is abs(position-target)
# For a list of positions, we can summise the edges as being (min(positions),max(positions))
# For each possible target position, we need to calculate the move distance, and then sum them all
test_positions = [16,1,2,0,4,2,7,1,2,14]
def distance_from_target(target, position):
return abs(position-target)
assert 14 == distance_from_target(2, 16)
assert 1 == distance_from_target(2, 1)
assert 0 == distance_from_target(2, 2)
assert 2 == distance_from_target(2, 0)
assert 2 == distance_from_target(2, 4)
def convert_positions_to_distances(target, positions):
return map(lambda position: distance_from_target(target,position), positions)
assert [14, 1, 0, 2, 2, 0, 5, 1, 0, 12] == list(convert_positions_to_distances(2, test_positions))
def find_fuel_for_swarm_to_target(target, positions):
return sum(convert_positions_to_distances(target,positions))
assert 37 == find_fuel_for_swarm_to_target(2, test_positions)
def find_distances_for_each_position(positions):
return [find_fuel_for_swarm_to_target(target, positions) for target in range(min(positions),max(positions))]
print(find_distances_for_each_position(test_positions))
assert [49, 41, 37, 39, 41, 45, 49, 53, 59, 65, 71, 77, 83, 89, 95, 103] == find_distances_for_each_position(test_positions)
def find_smallest_distance(positions):
distances = find_distances_for_each_position(positions)
return distances.index(min(distances)),min(distances)
print(find_smallest_distance(test_positions))
assert 2,37 == find_smallest_distance(test_positions)
[49, 41, 37, 39, 41, 45, 49, 53, 59, 65, 71, 77, 83, 89, 95, 103] (2, 37)
So, In this case, I figured we just needed to iterate over each number, working out that the distance from the target is abs(position-target). We can turn a set of positions into a set of distances, we can repeat that for every possibile position (which is simply the range from min(position) to max(position)) then we end up with a list of total fuel needed to get to the given position, and then we can find the minimum of that.
We could probably write this condensed into:
min([sum(map(lambda p: abs(position-target),positions)) for target in range(min(positions),max(positions))])But writing out each step as a separate function makes it easier to write it a step at a time, and easier to debug (a lot easier, I got quite a number of bits wrong in here when writing this)
positions = [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,848,1174,380,1195,277,353,425,292,225,1521,631,76,692,329,1530,445,1625,561,161,1760,88,129,89,866,133,353,372,1456,888,115,347,291,246,8,57,17,869,1230,1224,681,586,1553,183,508,760,1200,812,634,578,126,147,684,1037,822,217,521,136,438,456,26,258,9,395,1,1398,34,13,40,493,871,154,606,716,649,491,416,293,1,107,21,317,1156,194,179,693,1591,894,845,10,18,1314,11,730,408,365,0,516,192,96,1438,1521,787,503,454,84,478,19,26,109,287,657,216,148,155,816,384,288,1121,39,263,488,348,110,1219,321,1101,51,5,95,147,806,17,207,81,139,686,23,231,1154,36,410,1025,2,327,172,307,232,420,88,129,1507,1028,852,467,46,81,16,64,989,558,919,1301,612,278,306,1500,95,507,1034,272,526,68,41,870,37,78,434,459,268,375,1427,1039,1039,1077,1068,445,482,106,1823,218,76,33,131,934,112,72,404,118,848,99,10,816,527,125,279,200,10,248,243,416,242,639,401,66,110,364,243,550,1289,55,30,1246,72,46,251,1225,264,765,137,94,626,252,18,481,250,55,10,284,247,90,277,34,176,118,1178,554,761,3,938,140,890,109,811,760,179,1084,998,16,338,550,120,190,220,74,846,212,30,1098,455,1110,1662,71,1275,609,47,1239,1050,93,169,383,564,323,134,310,208,685,255,219,369,556,272,1604,562,600,493,178,337,33,949,775,588,288,498,40,1056,483,796,8,1588,463,122,120,26,215,786,525,129,259,346,21,35,247,1564,1094,1013,85,54,193,889,590,908,122,158,363,646,1301,533,73,767,405,89,358,936,737,78,982,163,867,373,1460,492,151,560,371,647,110,1779,802,374,147,1279,252,299,244,568,1014,685,912,942,767,3,76,207,296,40,181,312,192,684,988,490,31,410,928,47,1345,943,1013,705,675,543,446,84,869,1173,393,348,99,25,21,20,132,295,4,1273,800,182,140,593,964,55,167,15,219,269,35,848,324,474,189,4,305,62,7,1145,13,975,55,880,43,368,82,1083,6,969,844,1388,185,818,114,641,151,1006,220,599,143,170,36,631,891,531,871,13,77,1261,340,911,159,258,213,1245,222,200,946,875,301,9,381,69,1152,901,490,207,38,104,103,423,311,1532,536,314,73,314,29,844,141,1191,169,136,42,143,163,277,22,1655,1063,45,774,103,83,1253,121,1473,834,245,143,211,1252,1368,97,4,1188,1102,359,134,298,225,292,101,832,426,1204,652,468,110,529,34,384,663,534,80,1,68,117,419,1321,1729,38,1609,416,554,1047,130,145,267,1382,0,237,32,17,237,803,21,888,185,108,79,1,192,286,1167,86,71,464,122,375,0,186,927,525,1127,442,675,373,53,404,624,65,1157,107,687,98,165,891,1186,513,727,46,148,275,516,1412,17,684,113,246,137,1246,1357,143,307,307,656,1030,198,33,955,1765,314,79,5,385,248,402,75,12,76,325,175,1198,258,38,912,795,296,1931,111,72,1619,1563,8,327,867,293,515,1647,1266,128,44,9,431,300,72,501,1181,147,1330,1446,490,297,436,274,512,107,185,57,112,2,121,472,505,860,1650,411,23,328,119,64,0,1684,249,106,167,55,225,501,36,81,1225,270,186,10,477,783,39,319,1151,264,788,42,521,282,257,721,442,250,642,255,63,1015,241,939,86,997,569,330,189,129,547,1424,446,285,8,288,599,372,56,274,245,3,41,943,353,67,294,32,656,879,918,94,314,767,957,1554,854,610,590,403,139,377,129,930,341,678,577,375,809,490,39,153,3,48,133,54,225,1261,677,267,30,28,115,642,1733,12,297,428,155,812,635,16,634,223,823,261,662,652,71,138,103,220,544,211,313,1298,512,559,1243,1319,427,78,765,343,212,557,275,1,551,234,697,1815,1005,275,179,595,1,1658,204,345,794,36,102,912,657,194,8,2,526,350,399,390,1166,469,324,1497,371,759,621,800,895,235,314,579,863,278,54,239,1275,79,1728,934,1145,1008,748,196,1056,339,569,629,47,1437,416,758,1000,287,592,1057,921,170,273,144,133,0,320,216,216,118,229,4,681,410,1801,34,485,769,839,47,950,1694,1222,1199,411,598,1210,7,1644,245,44,428,49,653,7,1037,310,754,32,476,253,124,809,66,539,434,1142,136,4,344,306,628,1332,15,1523,149,191,498,1480,498,385,562,457,199,201,487,608,172,20,584,7,17,342,167,93,60,589,445,926]
print(find_smallest_distance(positions))
(307, 340056)
Ok, so now we need to not just take a linear cost to move around, but a cost that is 1 to move 1 space, 1+2 to move two spaces, 1+2+3 to move the three spaces and so on.
Now I started with a simple lookup table, thinking that we'd only need to move up to 10 spaces, which took me just a couple of seconds to work out, and you can still see the results in the test that I wrote.
Before I move on to why this didn't work, lets talk about that test. On the iPad and on the online version of Jupyter (which is otherwise amazing), I can't install ipytest or pytest. That gives really nice formatted responses for assert a ==b, if it fails, you get a traceback that says "a was xxx, b was yyy" etc. Without that, the asserts just fail. So I wrote a for loop to test the expected and actual values, test the comparison, and print the values. This helped because originally I had managed to get the index wrong when putting it all in and couldn't work out why my asserts were failing.
Right, anyway, although theres a lot of code here, the only thing that actually changed was fuel_to_move_distance. Because of the way that Python Notebook works, you can't just redeclare fuel_to_move_distance and have the functions declared above re-execute, you need to rewrite them.
So what about that distance*(distance+1)//2?
I remembered when I was at school staring at a poster that talked about a boy genius who was assigned some work from the maths teacher to solve the problem 1+2+3+4...500. Everyone was solving it one number at a time. What he recognised is that this was the same as saying (500+1)+(499+2)+(498+3)... So you can also say for a given range of numbers, it's equal to the first, plus the last, multiplied by the number of numbers in the range, divided by 2. Because our range started at 1, we end up with 1+distance times distance and all divided by two.
I will admit that I remembered the problem, I rememberd the story, but I didn't remember the solution. I googled, since I knew it was a thing and found the wikpedia page for Triangle Numbers. It turns out that the story that I saw on a poster at school appears to be lacking in evidence
# we can mostly solve this with a lookup table for tbe cost
import unittest
import math
def fuel_to_move_distance(distance):
return (distance*(distance+1))//2
for d,f in [(0,0),(1,1),(2,3),(3,6),(4,10),(5,15),(6,21),(7,28)]:
if not f == fuel_to_move_distance(d):
print(f"{f} is not equal to {fuel_to_move_distance(d)}")
assert False
def find_fuel_for_swarm_to_target(target, positions):
return sum(map(fuel_to_move_distance, convert_positions_to_distances(target,positions)))
assert 206 == find_fuel_for_swarm_to_target(2, test_positions)
def find_distances_for_each_position(positions):
return [find_fuel_for_swarm_to_target(target, positions) for target in range(min(positions),max(positions))]
print(find_distances_for_each_position(test_positions))
assert [290, 242, 206, 183, 170, 168, 176, 194, 223, 262, 311, 370, 439, 518, 607, 707] == find_distances_for_each_position(test_positions)
def find_smallest_distance(positions):
distances = find_distances_for_each_position(positions)
return distances.index(min(distances)),min(distances)
print(find_smallest_distance(test_positions))
assert 5,168 == find_smallest_distance(test_positions)
[290, 242, 206, 183, 170, 168, 176, 194, 223, 262, 311, 370, 439, 518, 607, 707] (5, 168)
print(find_smallest_distance(positions))
(460, 96592275)