10
$\begingroup$

You are a lone builder. You have to build a city on a 10x10 initial empty grid. You can place:

  • a street, which is a blue cell on the top of any cell,
  • a tomato shop, which is a red cell on any cell having a street in one of his 4-neighbors,
  • a small house, which is a green cell on any cell having a street and a tomato shop in two of his 4-neighbors,
  • a tall building, which is a yellow cell on any cell having a street, a tomato shop and a house in three of his 4-neighbors.

These rules are valid during the construction step only: if a cell is replaced by another one, it has to comply the rules, but its neighbors can break them.

Below is an example of a possible city:

The city achieved currently by our builder

The question is easy:

How many yellow tall buildings can you build in the city, and in how many steps? An answer is considered better than another one if it maximizes the number of buildings, or if the number is the same but it does it in a lower number of steps.

For instance, if you would be given a 3x3 city, you could build 4 buildings in 12 steps:

How to build a 3x3 city in 12 steps

For the little story, I got inspired from a now unavailable Android game: com.amusetime.buildingtower

$\endgroup$

2 Answers 2

12
$\begingroup$

56 57 yellow squares / 149 steps

First place the blue, red and green squares like in the following three images (the black X marks new squares):

enter image description here

Then fill the green spiral with yellow buildings, starting top left. Add the 4 green buildings from the middle image. Finally fill the remaining yellow buildings from the right image.

enter image description here

$\endgroup$
3
  • $\begingroup$ Did you use some logic to solve this question ? can you prove that your answer is optimal ? $\endgroup$ Feb 10, 2021 at 12:49
  • $\begingroup$ Did you use dynamic programming by any chance to solve this ? $\endgroup$ Feb 10, 2021 at 12:56
  • $\begingroup$ @HemantAgarwal It's 5 years ago, and I don't even remember the question. But I'm pretty sure I solved it by hand, and the spiral movement was the main idea. Obviously because of that I can't prove it's optimal. $\endgroup$
    – Sleafar
    Feb 11, 2021 at 13:28
2
$\begingroup$

First approximation of an answer:

46 Yellow squares in 125 actions.

Let's label the rows 0 - 90 and the columns 0 - 9, thus defining each square in the grid from 00 - 99.

1) Color blue mostly in pairs - 00, 01, 04, 05, 08, 09, 22, 23, 26, 27, 40, 41, 44, 45, 48, 62, 63, 66, 67, 80, 81, 84, 85, 88, 89. Note that square 49 is not colored. This takes 25 actions.

2) Additionally, color in 10, 19, 39, 50, 59, 93, 95, and 96 blue - this takes 8 actions.

3) Color in 90, and 99 red - this takes 2 actions (note that 80, and 89 are blue).

4) In rows 0, 2, 4, 6, and 8, color all the un-colored squares red (again excluding 49) - this takes 24 actions.

5) color in the following squares green - 11, 13, 15, 17, 19, 31, 33, 35, 37, 51, 53, 55, 57, 71, 73, 75, 77, 79, 91, 97. This takes 20 actions.

6) Color in every square vertically or horizontally adjacent to a green square as yellow, excluding 09 and 90. This takes 46 actions.

Done. All squares except 49 and 94 are colored at this point.

$\endgroup$
5
  • 1
    $\begingroup$ Your estimate of 50 seems to be an actuality of 48. $\endgroup$
    – Moti
    Nov 30, 2015 at 4:51
  • $\begingroup$ Last step is I only 48 steps since only 48 yellow obey the rule of 3... $\endgroup$
    – Moti
    Nov 30, 2015 at 4:59
  • $\begingroup$ Righty, missed two different edge cases - looks like 4 of my yellows get cut off as a result. $\endgroup$
    – Zerris
    Nov 30, 2015 at 5:52
  • $\begingroup$ I think only 2 yellow $\endgroup$
    – Moti
    Nov 30, 2015 at 6:06
  • $\begingroup$ in addition to the corners (which obviously only have 2 adjacent squares) I found that on the two of my edges that contain yellow, there was no combination of interwoven colors that allows them every other square - the closest I could get was losing one per side. Feel free to find something I missed, though. I make no claim that this is the ideal answer - just that it's good enough to be worth posting as a baseline. $\endgroup$
    – Zerris
    Nov 30, 2015 at 6:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.