This is a problem based on the game "NGU Industries" in which the objective is to build a factory. Each tile can hold either a production building or a "beacon" which increases the production of buildings near to it in a given offset pattern. In other words, adding a beacon increases the productivity of nearby tiles at the cost of the tile it is placed on. Some tiles on each map are blocked and unusable.
The variable map1 contains the layout of the game's first map, where a . indicates a usable square and a an unusable square.
The available beacons are represented in the program by the symbols *, k, >, <, ^, v, and the bonuses they give and the layouts they give them in are as follows:
*gives a +30% bonus to every cardinally or diagonally adjacent square.
+30% +30% +30%
+30% * +30%
+30% +30% +30%
kgives a +35% bonus to every square a knight's move away from it.
---- +35% ---- +35% ----
+35% ---- ---- ---- +35%
---- ---- k ---- ----
+35% ---- ---- ---- +35%
---- +35% ---- +35% ----
vgives a +22% bonus to tiles in an arrow shape below it.>,<and^apply the same shape in different directions.
---- ---- v ---- ----
---- ---- +22% ---- ----
---- ---- +22% ---- ----
+22% +22% +22% +22% +22%
---- +22% +22% +22% ----
---- ---- +22% ---- ----
A square can be affected by any number of beacons of any type or combination of types. If a square is affected by multiple beacons the bonuses are added together; so a square affected by two *s and a v has a bonus of +88% for a total of 188%.
This program attempts to find the best possible layout for beacons on a given map using a beam search. However even with a high beam width, 10000, it does not find the best solutions - it tops out at a score 17445 (where the score is the sum of production percentages on all empty, usable tiles), whereas the community have found a layout (shown in the variable exi1) yielding 17934.
Is there a fundamental problem with my approach here or is it just a question of needing an even wider search? In a previous version I allowed removing or changing a beacon as a potential change made by beamGrid and this slightly improved results but at the cost of filling the beam with old states and much lower performance since removing a beacon is computationally expensive.
Edit: added beacon removal back in using cached values to save recalculating everything, but still doesn't seem to reach optimal values.
Edit 2: removed a really dumb bug where added beacons would be immediately culled. I don't think this improves optimality but it speeds things up.
map1 = [" .. ",
" ... . ",
" . .. ..... ",
" ..... ...... ",
" .. ....... ",
" .... .. . . .. ",
" ........ ........",
" ........ . . ",
" .......... . ",
" .......... . ",
" .. .......... ",
" ... . ",
" ...... ",
" . ... ...... ",
" .. ... ",
" ... ",
" "]
exi1 = [" .. ",
" .*. . ",
" v v. .v.k. ",
" vvv>. .k.k.< ",
" vv .k.k.k. ",
" >>.. .. . . .< ",
" >>>..... <k...k.<",
" >>>..... < . ",
" >>>....<<< ^ ",
" >>.....<<< v ",
" ^. ^>>.....<< ",
" ... < ",
" ....<< ",
" . ... ....<< ",
" .. .*. ",
" ... ",
" "]
mycl = [".... ... .. ...",
"..... ....",
".... ... ........",
".. . . ..... ",
".. . . ...... .",
".. ...... ...... ",
"... ..... ...... ..",
".... .... .........",
". ... ... ... ...",
". ... . ... . .",
".. .... . .",
"... .. ..... ... .",
".... .... .. .",
"...... . ... ......",
" ..... ..... . ...",
" ........... .. ...",
" .......... ..."]
beacons = [
# Box
(2,30,[(-1,-1),(0,-1),(1,-1),(-1,0),(1,0),(-1,1),(0,1),(1,1)]),
# Knight
(3,35,[(-1,-2),(-2,-1),(-2,1),(-1,2),(1,-2),(2,-1),(2,1),(1,2)]),
# Arrows
(4,22,[(0,-1),(0,-2),(0,-3),(0,-4),(0,-5),(-1,-3),(-2,-3),(1,-3),
(2,-3),(-1,-4),(1,-4)]),
(5,22,[(0,1),(0,2),(0,3),(0,4),(0,5),(-1,3),(-2,3),(1,3),
(2,3),(-1,4),(1,4)]),
(6,22,[(1,0),(2,0),(3,0),(4,0),(5,0),(3,-1),(3,-2),(3,1),(3,2),
(4,1),(4,-1)]),
(7,22,[(-1,0),(-2,0),(-3,0),(-4,0),(-5,0),(-3,-1),(-3,-2),(-3,1),
(-3,2),(-4,1),(-4,-1)]),
# Not unlocked until later in the game
# (8,27,[(-1,0),(-2,0),(-3,0),(-4,0),(-5,0),(-6,0),(1,0),(2,0),(3,0),(4,0),
# (5,0),(6,0)]),
# (9,27,[(0,-1),(0,-2),(0,-3),(0,-4),(0,-5),(0,-6),(0,1),(0,2),(0,3),(0,4),
# (0,5),(0,6)]),
# (10,26,[(-2,-2),(-1,-2),(0,-2),(1,-2),(2,-2),(-2,-1),(2,-1),(-2,0),(2,0),
# (-2,1),(2,1),(-2,2),(-1,2),(0,2),(1,2),(2,2)])
]
chars = ['',' ','*','k','^','v','>','<',"-","|","o"]
def initFromMap(mapp):
"""Creates an initial grid from a string representation of a map only."""
grid = [[(100,0) if x == '.' else (100,1) for x in s] for s in mapp]
return grid
def initFromPre(pre):
"""Creates a grid from a string representation of a map with beacons."""
grid = [[(100,0) if x == '.' else (100,1) for x in s] for s in pre]
for y in range(17):
for x in range(20):
ch = pre[y][x]
if ch != ' ':
if ch in chars:
ind = chars.index(ch)
grid = applyBeacon(grid, x, y, beacons[ind-2])
return grid
def applyBeacon(pair,x,y,beacon):
"""Add the given beacon to the grid at the given coordinates and return
an updated grid."""
(grid, score) = pair
(bid,bonus,offsets) = beacon
newGrid = [l.copy() for l in grid]
assert newGrid[y][x][1] == 0 # Can't replace beacons by this method
score -= newGrid[y][x][0]
newGrid[y][x] = (newGrid[y][x][0],bid) # Set beacon id on cell
for (ox,oy) in offsets:
nx = x+ox
ny = y+oy
if (nx < 0) or (nx > 19) or (ny < 0) or (ny > 16):
continue
newGrid[ny][nx] = (newGrid[ny][nx][0] + bonus, newGrid[ny][nx][1])
if newGrid[ny][nx][1] == 0:
score += bonus # Score only if no beacon on square
return (newGrid, score)
def removeBeacon(pair,x,y):
(grid, score) = pair
newGrid = [l.copy() for l in grid]
assert newGrid[y][x][1] > 1
(oldId, oldBonus, oldOffsets) = beacons[newGrid[y][x][1]-2]
newGrid[y][x] = (newGrid[y][x][0],0)
score += newGrid[y][x][0]
for (ox,oy) in oldOffsets:
nx = x+ox
ny = y+oy
if (nx < 0) or (nx > 19) or (ny < 0) or (ny > 16):
continue
newGrid[ny][nx] = (newGrid[ny][nx][0] - oldBonus, newGrid[ny][nx][1])
if newGrid[ny][nx][1] == 0:
score -= oldBonus
return (newGrid, score)
def buildBenefitMap(mapp):
benefitMap = []
baseScore = gridScore(mapp)
for beacon in beacons:
page = []
for y in range(17):
line = []
for x in range(20):
if mapp[y][x][1] == 1:
line.append(0)
else:
(newGrid,newScore) = applyBeacon((mapp, baseScore), x, y, beacon)
line.append(newScore-baseScore)
page.append(line)
benefitMap.append(page)
return benefitMap
def cullBeacons(pair,benefitMap):
(grid, score) = pair
for y in range(17):
for x in range(20):
if grid[y][x][1] > 1:
if (grid[y][x][0]-100) >= benefitMap[grid[y][x][1]-2][y][x]:
(grid, score) = removeBeacon((grid,score),x, y)
return (grid,score)
def stringifyGrid(grid):
"""Converts a grid into an array of output strings."""
out = []
for row in grid:
ostr = ""
for (value,beacon) in row:
if beacon>0:
ostr += chars[beacon]
else:
ostr += '.'
out.append(ostr)
return out
def drawGrid(grid):
"""Outputs a grid representation."""
for row in stringifyGrid(grid):
print(row)
def gridScore(grid):
"""Returns a grid's total production."""
return sum([sum([x if y == 0 else 0 for (x,y) in row]) for row in grid])
def fullDrawGrid(grid):
"""Draws a grid with production values for each square."""
strs = stringifyGrid(grid)
for y in range(17):
for x in range(20):
if strs[y][x] == " ":
print(" ",end="")
elif strs[y][x] == ".":
print(f'{grid[y][x][0]:3}',end="")
else:
print(strs[y][x]+" ",end="")
print(" ",end="")
print()
def addToBeam(beam,pair,width):
"""Adds a grid to a sorted list of scored grid candidates."""
(grid, score) = pair
if score <= beam[-1][1]:
return
for x in range(len(beam)):
(eg, es) = beam[x]
if es == score:
if eg == grid:
return
if es < score:
index = x
break
else:
return
beam[index+1:] = beam[index:-1]
beam[index] = pair
def beamGrid(grids,width,benefitMap):
beam = grids[:width]
for (grid, score) in grids:
for y in range(17):
for x in range(20):
if grid[y][x][1] == 0:
for beacon in beacons:
if benefitMap[beacon[0]-2][y][x] > (grid[y][x][0]-100):
newPair = applyBeacon((grid,score),x,y,beacon)
newPair = cullBeacons(newPair,benefitMap)
addToBeam(beam, newPair, width)
elif grid[y][x][1] > 1:
newPair = removeBeacon((grid,score), x, y)
addToBeam(beam, newPair, width)
return beam
def beamSearch(grid,width):
initScore = gridScore(grid)
initBeam = [(grid.copy(),initScore) for x in range(width)]
benefitMap = buildBenefitMap(grid)
beam = beamGrid(initBeam,width,benefitMap)
oldBeam = None
gen = 0
while beam != oldBeam:
oldBeam = beam.copy()
beam = beamGrid(oldBeam, width, benefitMap)
if (len(beam) != width):
print("WIDTH ERROR")
print(gen, beam[0][1],"-",beam[-1][1])
gen += 1
return oldBeam[0]
x = beamSearch(initFromMap(map1),4000)(replacing 4000 with the width to try) \$\endgroup\$