7
$\begingroup$

I'm messing around with this toy problem I came up with.

Say you have a yard that's 16 x 16 feet. Each square foot of the grid can either be a paving square for the path or a soil square for plants. A soil square can be either reachable or unreachable.

You can start the path from any square on the outside of the grid. That's the entrance and the exit of the yard and so you start and finish there.

From any paving square, you can reach any soil square that is north, east, south or west of the paving square; you can't reach the diagonal squares.

You can only walk on the path, not on soil squares.

You want a configuration that maximises the number of reachable soil squares with as few steps on each paving stone as possible. i.e. if you just had a spiral, you'd have to walk to the end of the spiral and back again which means every paving stone except the last gets stepped on twice.

In short, you want to go from the start square to the end square in as few moves as possible and reach as many soil squares as possible.

Here's the best solution I've found so far on paper:

my current best solution

In this solution, I can access 158 soil squares in only 91 steps. The score for this is 133.735. (scoring algorithm below)

Can you find a solution with either:

  • more green squares and less steps, or
  • more green squares and same steps, or
  • same green squares and less steps?

In other words, if total steps taken is $s$ and total reachable green squares is $g$, then your score is

$\sqrt{s² + (256 - g)²}$

and the goal is the lowest score.

I've made a shared document on Google Sheets that you can copy and play with if you want to try this puzzle out. Feel free to write code to generate a solution too.

Improve this question
$\endgroup$
5
  • $\begingroup$ It seems this is likely one of two things: without computer aid, it's a game with no real provable optimum, making it off-topic since open-ended puzzles are off-topic, and with computer aid, it's an programming assignment. Unless you know of an optimum provable by hand? $\endgroup$
    – bobble
    Commented Dec 5, 2021 at 16:26
  • 1
    $\begingroup$ @cap The numbers represent the number of steps taken on that paving square. The example path starts and ends in the lower right, so the two entrance squares are touched twice, while all others are touched only once. $\endgroup$
    – Scott McPeak
    Commented Dec 6, 2021 at 11:28
  • $\begingroup$ The scoring function is unnecessarily complicated. The square root does not change the relative order of any two solutions, so can be dropped. And since steps ≈ non-greens, squaring does about the same thing to each, so maximizing the objective function "greens - steps" would, I think, yield the same order among competitive solutions. $\endgroup$
    – Scott McPeak
    Commented Dec 6, 2021 at 12:45
  • $\begingroup$ @ScottMcPeak If you find the function too complicated, just go with the 3 bullet points instead; they effectively amount to the same thing. But sometimes it's difficult to see if a solution is actually better without the scoring function (which btw, is just the Pythagorean theorem to measure the distance between a given solution and the 'ideal' solution of "all green, no steps"). The sheet linked in the post does the scoring for you automatically. $\endgroup$
    – Korgan Rivera
    Commented Dec 7, 2021 at 18:46
  • $\begingroup$ You cannot maximize and minimize at the same instance - maximizing with minimum or minimize with maximum! $\endgroup$
    – Moti
    Commented Dec 12, 2021 at 4:44

0

Reset to default

Browse other questions tagged or ask your own question.