#!/usr/bin/env python
# A solution for Influence, written in Python.
# by Phil Bordelon
# 0 1 2
# . . . 0
# . . . 1
# . . . 2
#
# (1,1) is adjacent to (1,0), (1,2), (0,1), (2,1) (the obvious ones),
# plus (2,0) and (0,2) (the less-obvious ones).
import os
import sys
# This number should be larger than any possible distance in the problem.
MAX_DISTANCE = 999
# This number should be the maximum size of the grid.
MAX_SIZE = 26
# Debug?
DEBUG = os.getenv("DEBUG", False)
def distance (x1, y1, x2, y2):
# Calculate the raw numeric differences. We also need the magnitudes
# of the differences, for the "less-obvious" adjacency math.
x_delta = x2 - x1
y_delta = y2 - y1
x_delta_mag = abs(x_delta)
y_delta_mag = abs(y_delta)
# First, do the math if it's the less-obvious adjacencies, which only
# occurs if the two deltas are going in different directions.
if (x_delta < 0 and y_delta > 0) or (x_delta > 0 and y_delta < 0):
# The distance is the number of steps diagonally (taken from
# both numbers), plus the length of the larger leg. So the
# math can be done as short leg + (long leg - short leg).
if x_delta_mag < y_delta_mag:
distance = x_delta_mag + (y_delta_mag - x_delta_mag)
else:
distance = y_delta_mag + (x_delta_mag - y_delta_mag)
else:
# Boring distance math.
distance = x_delta_mag + y_delta_mag
return distance
def precalcGrid ():
# We precalculate the distances for every cell from every other cell,
# because this makes the actual solution phase of the problem a series
# of calls into look-up tables.
grid = {}
for x1 in range(MAX_SIZE):
for y1 in range(MAX_SIZE):
new_location = {}
for x2 in range(MAX_SIZE):
for y2 in range(MAX_SIZE):
new_location[(x2,y2)] = distance(x1, y1, x2, y2)
grid[(x1,y1)] = new_location
return grid
def drawBoard(grid, size):
# This is a quick little debug function that draws a representation of the
# board.
lookup = (".", "!", "@", "#", "$")
for i in range(size):
for x in range(i):
print " ",
for j in range(size):
if grid[(i,j)]["piece"] > 0:
print " %s " % lookup[grid[(i,j)]["piece"]],
else:
print "%s%02d" % (lookup[grid[(i,j)]["closest_owner"]], grid[(i,j)]["closest_distance"]),
print
def calculateScoreAndUpdateGrid(grid):
# As the rather verbose function title states, this function calculates the
# score for various players given a particular board layout, along with
# updating the grid's knowledge of the closest pieces to each location,
# which is used for when we try to place new pieces. Yes, it's bad form to
# do both of these things in the same function, but it makes sense to not
# run through the board twice, and this /is/ programming contest code.
# Easy part first; start scores out as the count of pieces.
for i in range(4):
grid[i + 1]["score"] = grid[i + 1]["count"]
# Loop through the empty spaces on the grid.
for i, j in grid["emptylist"]:
# For each location, find the owner, if any, and the distance to
# said closest piece. This is easy. We loop over every pieces on the
# board and find the closest ones. If there's more than one player
# with the closest pieces, no one owns it.
closest_owner = 0
closest_distance = MAX_DISTANCE
for k, l, owner in grid["piecelist"]:
distance = grid[(i,j)][(k,l)]
if distance < closest_distance:
# Clear new winner. Record.
closest_distance = distance
closest_owner = owner
elif distance == closest_distance:
# If two players are closest, we need to set the owner to
# zero. If we've already determined it's contested, it
# needs to stay that way.
if closest_owner > 0 and owner != closest_owner:
# The piece is contested.
closest_owner = 0
# Save the closest distance and closest owner.
grid[(i,j)]["closest_distance"] = closest_distance
grid[(i,j)]["closest_owner"] = closest_owner
# If the closest owner is an actual player (as opposed to the contested
# value), increment their score.
if closest_owner:
grid[closest_owner]["score"] += 1
# Return the updated grid.
return grid
def setupGrid(grid, size):
# Here we set up the grid for a particular data set, clearing out scores
# and reading in the pieces and empty spaces from the input.
# First, clear out the piece counts for each player.
grid[1] = {"count": 0, "score": 0}
grid[2] = {"count": 0, "score": 0}
grid[3] = {"count": 0, "score": 0}
grid[4] = {"count": 0, "score": 0}
# Also clear out the lists of pieces and empty locations.
grid["piecelist"] = []
grid["emptylist"] = []
# Now, read in each piece and put it in the grid, incrementing counts
# as necessary.
for i in range(size):
line = sys.stdin.readline().strip()
# Get the actual characters from the line, whitespace-free.
pieces_in_line = [x for x in line.split() if len(x) > 0]
# Mild error checking.
if len(pieces_in_line) != size:
sys.exit("ERROR: Wrong number of pieces in line with piece setup %s!" % line)
# Loop through each piece in this line.
for j in range(len(pieces_in_line)):
piece = pieces_in_line[j]
if piece == ".":
# An empty space. Append this location to the empty list, and set
# its owner to no one.
grid[(i,j)]["piece"] = 0
grid["emptylist"].append((i,j))
elif piece == "!":
# A piece for the first player. Add this location to the piece
# list, increment their count of pieces by one, and set its owner
# to the first player.
grid[(i,j)]["piece"] = 1
grid[1]["count"] += 1
grid["piecelist"].append((i,j, 1))
elif piece == "@":
# The second player ...
grid[(i,j)]["piece"] = 2
grid[2]["count"] += 1
grid["piecelist"].append((i,j, 2))
elif piece == "#":
# ... the third ...
grid[(i,j)]["piece"] = 3
grid[3]["count"] += 1
grid["piecelist"].append((i,j, 3))
elif piece == "$":
# ... and the fourth.
grid[(i,j)]["piece"] = 4
grid[4]["count"] += 1
grid["piecelist"].append((i,j, 4))
# Now that we've read every piece in the grid, calculate each empty
# space's shortest distance to a piece and the current score.
grid = calculateScoreAndUpdateGrid(grid)
# Return.
return grid
def bestScore(grid, size, player):
# Here we determine the best possible score for a player if they have
# one more move.
# The score can never be worse than the score the player already has.
score = grid[player]["score"]
best_additional_points = 0
if DEBUG:
best_spot = "NONE"
# Now, try putting a piece for this player in each empty location.
for i, j in grid["emptylist"]:
additional_points = 0
# Check every /other/ empty location to see if this spot is closer
# to it than any other player's piece.
for k, l in grid["emptylist"]:
distance = grid[(i,j)][(k,l)]
if distance < grid[(k,l)]["closest_distance"]:
# Well, this is indeed closer than any other piece, but we
# can't count the location twice if the player already /had/
# the closest piece to this location.
if player != grid[(k,l)]["closest_owner"]:
additional_points += 1
# Record this if it's the best number of additional points we've
# found.
if additional_points > best_additional_points:
best_additional_points = additional_points
if DEBUG:
best_spot = (i,j)
if DEBUG:
print "The best spot is: " + repr(best_spot)
# Return the best number of points we've found for this player.
return score + best_additional_points
if "__main__" == __name__:
# Precalculate the adjacencies for the grid.
grid = precalcGrid()
dataset_count = int(sys.stdin.readline())
for dataset_loop in range(dataset_count):
print "DATA SET #%d" % (dataset_loop + 1)
# Get the count of players and the size of the board.
player_count = int(sys.stdin.readline())
size = int(sys.stdin.readline())
# Read the board in, populating our representation with distances
# to the nearest pieces.
grid = setupGrid(grid, size)
if DEBUG:
drawBoard(grid, size)
# Lastly, find the best new spots for pieces for each player.
for i in range(player_count):
print bestScore(grid, size, i + 1)