An unlucky gardener planted a 10x10 square array of 100 old seeds out in the garden. Only 5 of these seeds have germinated including one at the southwest corner (0,0) where a slug is currently reducing it to ground level.
When it finishes it will head directly to the next closest doomed plant. After it eats that one it will again leave a slime trail to the closest remaining plant and so on until the garden is no more.
Where are the 4 remaining seedlings if the path crawled by the slug is the longest possible and it never has to choose between two equidistant snacks?
Note: Although the slug will never have to choose between two equidistant seedlings, this doesn't imply that no two are equidistant.
Next find the locations if 6 seedlings had germinated instead of 5.
DECLARE SUB place (lvl!)
DIM SHARED n
n = 5
DIM SHARED curX(n), curY(n), curDist(n), curTot(n)
DIM SHARED hldX(n), hldY(n), hldDist(n), hldTot
curX(1) = 0
curY(1) = 0
curDist(1) = 0
curTot(1) = 0
SUB place (lvl)
FOR r = 0 TO 9
FOR c = 0 TO 9
FOR pLvl = 1 TO lvl - 2
dist = SQR((r - curY(pLvl)) * (r - curY(pLvl)) + (c - curX(pLvl)) * (c - curX(pLvl)))
IF dist <= curDist(pLvl + 1) THEN GOTO notThis
dist = SQR((r - curY(lvl - 1)) * (r - curY(lvl - 1)) + (c - curX(lvl - 1)) * (c - curX(lvl - 1)))
IF dist = 0 THEN GOTO notThis
curX(lvl) = c
curY(lvl) = r
curDist(lvl) = dist
curTot(lvl) = curTot(lvl - 1) + dist
IF lvl = n THEN
IF curTot(lvl) > hldTot THEN
FOR i = 1 TO n
hldX(i) = curX(i): PRINT hldX(i);
hldY(i) = curY(i): PRINT hldY(i); " ";
hldDist(i) = curDist(i)
hldTot = curTot(lvl)
place lvl + 1
0 0 6 5 9 9 9 0 0 8 33.85184
Posted by Charlie
on 2006-06-25 15:07:10