Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
First solution in Clear category for Ore In The Desert by PositronicLlama
"""
Iterative search for ore in a desert by maximizing minimum information.
"""
import collections
import itertools
import math
# Constants defining the parameters of the problem.
HEIGHT = 10
WIDTH = 10
def approximate_dist(a, b):
"""Return the cartesian distance between a and b, rounded to the nearest int."""
dist = math.sqrt((a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2)
return round(dist)
def possible_locations(probes, initial=None):
"""
Return a set of all possible locations for the ore, as (row, column) tuples.
"""
if initial is None:
possible = set(itertools.product(range(WIDTH), range(HEIGHT)))
else:
possible = set(initial)
for prow, pcol, pdistance in probes:
plocation = (prow, pcol)
for location in list(possible):
if approximate_dist(plocation, location) != pdistance:
possible.remove(location)
return possible
def first_probe(probes):
"""
Return the location for the first probe, as [row, column].
For the first probe we have no information, so we launch deterministically.
"""
# Launching in the corner maximizes the possible range of distances.
return [0, 0]
def gather_data(probes):
"""
Return the location for a probe, as [row, column].
Given previous probes, determine where to launch to maximize the minimum
information given by the probe.
"""
possible = possible_locations(probes)
if not possible:
raise RuntimeError("Inconsistent probe data {}".format(probes))
if len(possible) == 1:
return list(possible.pop())
# Consider all possible probe locations, and pick the one that maximizes
# the information given an adversarial probe location.
quality = 0
best = None
for plocation in itertools.product(range(WIDTH), range(HEIGHT)):
info = collections.defaultdict(list)
# Consider that the ore could be in any of its possible locations.
for ore in possible:
dist = approximate_dist(plocation, ore)
info[dist].append(ore)
if len(info) > quality:
best = plocation
quality = len(info)
return list(best)
def last_probe(probes):
"""
Return the location for the last probe, as [row, column].
If there are still multiple locations that could have ore, pick one.
"""
possible = possible_locations(probes)
# Return the first possibility in a deterministic manner.
return list(sorted(possible))[0]
# The behavior should change depending on the number of probes launched.
SCHEDULE = [first_probe, gather_data, gather_data, last_probe]
def checkio(data):
"""The [row, column] position at which to launch a probe."""
# Choose a different behavior based on the number of probes launched.
num_probes = len(data)
return SCHEDULE[num_probes](data)
June 20, 2013
