I recently had the displeasure of playing the Xbox 360 game Tower Bloxx Deluxe. You've played a version of it if not it itself; you build towers by dropping floors on top of the increasingly swaying tower you've already built. That's not interesting. What is interesting is the game's city building.
It gives you a grid of plots on which you build towers for people to live in and maximize your population. There are 5 tiers of tower, each taller thus more populous than the last. The trick is that a tier 2 tower needs to have a tier 1 tower adjacent to it before it can be built. A tier 3 tower needs a tier 1 tower and a tier 2 tower adjacent to it before it can be built. Eventually, a tier 5 tower needs to have all the lower tiers adjacent to it before it can be built. Higher tier towers do not satisfy requirements for the lower tiers. Once a tower is built, these restrictions no longer apply, so you can bulldoze everything around a tower and it will still stand.
Reworking this as a math puzzle, consider an n by m matrix M of 1's. Each iteration, you may replace one value in M with a counting number s if every counting number less than s is accounted for in the cells adjacent to it (The game only allows orthogonal adjacency, but allowing diagonal could be interesting too). What is the maximum sum of the values in M? What is the minimum number of iterations required to reach that value? What about expanding this to a graph instead of a matrix?
It's fairly obvious that no 5's can ever be next to each other, and that any final grid must have a 1 in it somewhere. I whipped up some Python code to brute force the problem, and it found that the optimal matrices of their sizes, up to symmetry, are $$\begin{vmatrix} 1 \end{vmatrix}, \begin{vmatrix} 2 & 1 \end{vmatrix}, \begin{vmatrix} 2 & 3 \\ 3 & 1 \end{vmatrix}, \begin{vmatrix} 2 & 3 & 1 \end{vmatrix}, \begin{vmatrix} 2 & 2 & 3 \\ 3 & 4 & 1 \end{vmatrix}, \begin{vmatrix} 2 & 4 & 3 \\ 4 & 2 & 4 \\ 3 & 4 & 1 \end{vmatrix}, \begin{vmatrix} 2 & 2 & 3 & 1 \end{vmatrix}, \begin{vmatrix} 2 & 3 & 4 & 1 \\ 3 & 4 & 2 & 3 \end{vmatrix}, \begin{vmatrix} 2 & 4 & 3 & 2 \\ 4 & 1 & 5 & 4 \\ 3 & 4 & 2 & 3 \end{vmatrix}, \begin{vmatrix} 2 & 3 & 2 & 3 & 1 \end{vmatrix}, \begin{vmatrix} 2 & 3 & 4 & 3 & 2 \\ 3 & 4 & 2 & 4 & 1 \end{vmatrix}, \begin{vmatrix} 2 & 2 & 3 & 2 & 3 & 1 \end{vmatrix}, \begin{vmatrix} 2 & 4 & 1 & 4 & 3 & 2 \\ 3 & 3 & 4 & 2 & 4 & 3 \end{vmatrix}, \begin{vmatrix} 2 & 3 & 2 & 3 & 2 & 3 & 1 \end{vmatrix}, \begin{vmatrix} 2 & 2 & 3 & 2 & 3 & 2 & 3 & 1 \end{vmatrix}, \begin{vmatrix} 2 & 3 & 2 & 3 & 2 & 3 & 2 & 3 & 1 \end{vmatrix}, \begin{vmatrix} 2 & 2 & 3 & 2 & 3 & 2 & 3 & 2 & 3 & 1 \end{vmatrix}, \begin{vmatrix} 2 & 3 & 2 & 3 & 2 & 3 & 2 & 3 & 2 & 3 & 1 \end{vmatrix}, \begin{vmatrix} 2 & 2 & 3 & 2 & 3 & 2 & 3 & 2 & 3 & 2 & 3 & 1 \end{vmatrix}$$
Matrices of area greater than 12 cause even my fairly beefy computer to run out of memory. I'm surprised that a 5 only appears for the first time in a 4x3. The nx1's also follow a clear pattern. I'm struggling to make any headway beyond this. What can you all come up with?
If anyone else wants to use it, here's the code I wrote (meant to be fast to write, not necessarily easily readable, sorry):
from queue import SimpleQueue as Q
def modification(grid, row, col, val):
return grid[:row] + (grid[row][:col] + (val,) + grid[row][col + 1:],) + grid[row + 1:]
def maximize(w, h, p):
q = Q()
s = set()
q.put(tuple((0,) * w for i in range(h)))
return _maximize(q, s, p)
def matsum(grid):
return sum(sum(row) for row in grid)
def _maximize(q, s, p):
G = ((0,),)
r = -1
while not q.empty():
r = (r + 1) % p
if r == 0:
print("Queue length: " + str(q.qsize()) +
"\tSeen grids: " + str(len(s)) + " "*15, end='\r')
g = q.get()
s.add(g)
if matsum(g) > matsum(G):
G = g
w = len(g[0])
h = len(g)
for x in range(w):
for y in range(h):
# try setting it to 0
m = modification(g, y, x, 0)
if m not in s:
q.put(m)
for v in range(1, 5):
if ((x > 0 and g[y][x - 1] == v - 1)
or (y > 0 and g[y - 1][x] == v - 1)
or (x < w - 1 and g[y][x + 1] == v - 1)
or (y < h - 1 and g[y + 1][x] == v - 1)):
m = modification(g, y, x, v)
if m not in s:
s.add(m)
q.put(m)
else:
break
print("Queue length: " + str(q.qsize()) +
"\tSeen grids: " + str(len(s)) + " "*15)
return G
for i in range(1, 13):
for j in range(1, i+1):
if i*j < 13:
print(str(i) + "x" + str(j) + ':')
print(maximize(i, j, 5000))
The following code has been slightly modified to prioritize higher-sum matrices at the cost of performance. The result is that it will find high-sum matrices quickly, but for sizes larger than say 4x3, it will take a prohibitively long time to finish and output the actual highest sum matrix (though it will eventually finish).
import heapq
def modification(grid, row, col, val):
return grid[:row] + (grid[row][:col] + (val,) + grid[row][col + 1:],) + grid[row + 1:]
def maximize(w, h, p):
q = []
s = set()
heapq.heappush(q, (-w*h, tuple((1,) * w for i in range(h))))
return _maximize(q, s, p)
def matsum(grid):
return sum(sum(row) for row in grid)
def _maximize(q, s, p):
G = ((0,),)
sG = matsum(G)
r = -1
while len(q) != 0:
r = (r + 1) % p
if r == 0:
print("len(q)=" + str(len(q)) +
" len(s)=" + str(len(s)) +
" G=" + str(G) +
" matsum(G)=" + str(sG)+" "*10, end='\r')
sg, g = heapq.heappop(q)
s.add(g)
if -sg > sG:
sG, G = -sg, g
w = len(g[0])
h = len(g)
for x in range(w):
for y in range(h):
# try setting it to 1
m = modification(g, y, x, 1)
if m not in s:
heapq.heappush(q, (-matsum(m), m))
s.add(m)
for v in range(2, 6):
if ((x > 0 and g[y][x - 1] == v - 1)
or (y > 0 and g[y - 1][x] == v - 1)
or (x < w - 1 and g[y][x + 1] == v - 1)
or (y < h - 1 and g[y + 1][x] == v - 1)):
m = modification(g, y, x, v)
if m not in s:
s.add(m)
heapq.heappush(q, (-matsum(m), m))
else:
break
print("len(q)=" + str(len(q)) +
" len(s)=" + str(len(s)) +
" G=" + str(G) +
" matsum(G)=" + str(sG)+" "*10)
return G
print(maximize(3, 3, 1000)) # to prove it works
#print(maximize(4, 4, 10000))