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

place 2

END

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
  NEXT pLvl
  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)
     NEXT
     hldTot = curTot(lvl)
     PRINT hldTot
   END IF
  ELSE
   place lvl + 1
  END IF
notThis:
 NEXT c
 NEXT r
END SUB

ultimately finds

0  0      6  5      9  9      9  0      0  8     33.85184

Posted by Charlie on 2006-06-25 15:07:10