ACTUALIZACIÓN: se agregó un marco de Python para comenzar.
La estación espacial ha sido superada por los robots trituradores. Debes dirigir tantos robots tecnológicos caros y frágiles llamados "conejos" a un teletransportador de salida antes de que la estación se autodestruya, pero los robots trituradores patrullan los pasillos.
Su programa recibe un mapa ASCII, y cada turno se le dice dónde están los trituradores-bots y sus conejos actuales. Su programa debe mover sus conejos hacia el teletransportador de salida mientras evita los trituradores de bots.
Ejecución
Ejecute el controlador Python 2 con:
python controller.py <mapfile> <turns> <seed> <runs> <prog>...
<prog> can be <interpreter> <yourprog> or similar.
La semilla es un número entero pequeño que se usa para la trituradora y su programa PRNG para que las ejecuciones sean repetibles. Su programa debe funcionar consistentemente, independientemente de la semilla real utilizada. Si la inicialización es cero, el controlador utilizará una inicialización aleatoria para cada ejecución.
El controlador ejecutará su programa con el nombre del archivo de texto del mapa y la semilla como argumentos. P.ej:
perl wandomwabbits.pl large.map 322
Si su programa usa un PRNG, debe inicializarlo con la semilla dada. El controlador luego envía las actualizaciones de su programa a través de STDIN y lee los movimientos de su conejo a través de STDOUT.
Cada vuelta, el controlador generará 3 líneas:
turnsleft <INT>
crusher <x,y> <movesto|crushes> <x,y>; ...
rabbits <x,y> <x,y> ...
luego espera a que el programa muestre una línea:
move <x,y> to <x,y>; ...
ACTUALIZACIÓN: Su programa tendrá 2 segundos para inicializarse antes de que el controlador envíe las primeras líneas.
Si su programa tarda más de 0.5 segundos en responder con movimientos después de la entrada de ubicación del controlador, el controlador saldrá.
Si no hay conejos en la cuadrícula, la línea de conejos no tendrá valores, y su programa debería generar una línea de cadena "mover".
Recuerde lavar el flujo de salida de su programa cada turno o el controlador puede bloquearse.
Ejemplo
entrada de programa:
turnsleft 35
crusher 22,3 crushes 21,3; 45,5 movesto 45,4
rabbits 6,4 8,7 7,3 14,1 14,2 14,3
salida prog:
move 14,3 to 14,4; 14,2 to 14,3; 6,4 to 7,4
Lógica del controlador
La lógica para cada turno:
- Si las vueltas a la izquierda son cero, imprima la puntuación y salga.
- para cada celda de inicio vacía, agregue un conejo si no hay una trituradora a la vista.
- para cada trituradora, decida la dirección del movimiento (ver más abajo).
- para cada trituradora, muévase si es posible.
- Si la trituradora está en una ubicación de conejo, retire el conejo.
- giro de salida, acciones de trituración y ubicaciones de conejos para programar.
- lea las solicitudes de movimiento de conejo del programa.
- Si no existe un conejo o no se puede mover, omita.
- trazar cada nueva ubicación de conejos.
- Si el conejo golpea una trituradora, el conejo es destruido.
- Si el conejo está en el teletransportador de salida, se retira el conejo y se aumenta la puntuación.
- Si los conejos chocan, ambos son destruidos.
Cada trituradora siempre tiene una dirección de rumbo (una de NSEW). Una trituradora sigue esta lógica de navegación cada turno:
- Si uno o más conejos son visibles en cualquiera de las 4 direcciones ortogonales, cambie la dirección a uno de los conejos más cercanos. Tenga en cuenta que las trituradoras no pueden ver más allá de otra trituradora.
- de lo contrario, elija al azar entre las opciones abiertas hacia adelante, izquierda, derecha si es posible.
- de lo contrario, si hay obstáculos (pared u otra trituradora) al frente, a la izquierda y a la derecha, establezca la dirección hacia atrás.
Luego para cada trituradora:
- Si no hay obstáculo en la nueva dirección de la trituradora, muévase (y posiblemente triture).
Los símbolos del mapa
El mapa es una cuadrícula rectangular de caracteres ASCII. El mapa está formado por paredes
#, espacios de pasillo , posiciones de inicio de conejos s, teletransportadores de salida ey ubicaciones de inicio de la trituradora c. La esquina superior izquierda es la ubicación (0,0).
Pequeño mapa
###################
# c #
# # ######## # # ##
# ###s # ####e#
# # # # ## ## #
### # ### # ## # #
# ## #
###################
Mapa de prueba
#################################################################
#s ############################ s#
## ## ### ############ # ####### ##### ####### ###
## ## ### # # ####### ########## # # #### ###### ###
## ## ### # ############ ####### ########## ##### ####### ###
## ## ## # ####### ########## # # ##### #### #
## ### #### #### ######## ########## ##### #### ## ###
######### #### ######## ################ ####### #### ###
######### ################# ################ c ####### ###
######### ################## ####### ####### ###########
######### ################## ######## ####### ###########
##### ### c ###### ###################
# #### ### # # # # # # # # # # ###### ############## #
# ####### #### ### #### ##### ## #
# #### ### # # # # # # # # # # ### # ### ######### #
##### ### #### ### ##### ### # ######## ####
############## ### # # # # # # # # # # ####### ## ####### ####
#### #### #### ### ### # # ### ###### ####
## ### # # # # # # # # # # ### ### # ### ##### ####
##### ######## ### # # # ##### # # # # ### ### # ##### #### ####
##### ##### ###### c # ### ### ###### ### ####
## c ######################### ### ##### ####### ### ####
##### # ### ####### ######## ### ##### c ## ## ####
##### # ####### ########## ## ######## # ######## ## ####
######### # ####### ## # ## # # # ##### # ####
### ##### # ### # ############## # ### # ### ## # ####
# ## # ### ### # ############## # ### ##### ##### ## ####
### ## ## # ### # ######## #
#s ## ###################################################e#
#################################################################
Ejemplo de mapa grande ejecutado
Puntuación
Para evaluar su programa, ejecute el controlador con el mapa de prueba, 500 vueltas, 5 carreras y una semilla de 0. Su puntaje es el número total de conejos teletransportados con éxito fuera de la estación a un lugar seguro. En caso de empate, la respuesta con más votos ganará.
Su respuesta debe incluir un título con el nombre de la entrada, el idioma utilizado y la puntuación. En el cuerpo de la respuesta, incluya el resultado de la puntuación del controlador completo con números iniciales para que otros puedan repetir sus ejecuciones. Por ejemplo:
Running: controller.py small.map 100 0 5 python bunny.py
Run Seed Score
1 965 0
2 843 6
3 749 11
4 509 10
5 463 3
Total Score: 30
Puede usar bibliotecas estándar y de libre acceso, pero las lagunas estándar están prohibidas. No debe optimizar su programa para una semilla, un conteo de turnos, un conjunto de características del mapa u otros parámetros. Me reservo el derecho de cambiar el mapa, el conteo de turnos y la semilla si sospecho una violación de esta regla.
Código del controlador
#!/usr/bin/env python
# Control Program for the Rabbit Runner on PPCG.
# Usage: controller.py <mapfile> <turns> <seed> <runs> <prog>...
# Tested on Python 2.7 on Ubuntu Linux. May need edits for other platforms.
# v1.0 First release.
# v1.1 Fixed crusher reporting bug.
# v1.2 Control for animation image production.
# v1.3 Added time delay for program to initialise
import sys, subprocess, time, re, os
from random import *
# Suggest installing Pillow if you don't have PIL already
try:
from PIL import Image, ImageDraw
except:
Image, ImageDraw = None, None
GRIDLOG = True # copy grid to run.log each turn (off for speed)
MKIMAGE = False # animation image creation (much faster when off)
IMGWIDTH = 600 # animation image width estimate
INITTIME = 2 # Allow 2 seconds for the program to initialise
point = complex # use complex numbers as 2d integer points
ORTH = [1, -1, 1j, -1j] # all 4 orthogonal directions
def send(proc, msg):
proc.stdin.write((msg+'\n').encode('utf-8'))
proc.stdin.flush()
def read(proc):
return proc.stdout.readline().decode('utf-8')
def cansee(cell):
# return a dict of visible cells containing robots with distances
see = {} # see[cell] = dist
robots = rabbits | set(crushers)
if cell in robots:
see[cell] = 0
for direc in ORTH:
for dist in xrange(1,1000):
test = cell + direc*dist
if test in walls:
break
if test in robots:
see[test] = dist
if test in crushers:
break # can't see past them
return see
def bestdir(cr, direc):
# Decide in best direction for this crusher-bot
seen = cansee(cr)
prey = set(seen) & rabbits
if prey:
target = min(prey, key=seen.get) # Find closest
vector = target - cr
return vector / abs(vector)
obst = set(crushers) | walls
options = [d for d in ORTH if d != -direc and cr+d not in obst]
if options:
return choice(options)
return -direc
def features(fname):
# Extract the map features
walls, crusherstarts, rabbitstarts, exits = set(), set(), set(), set()
grid = [line.strip() for line in open(fname, 'rt')]
grid = [line for line in grid if line and line[0] != ';']
for y,line in enumerate(grid):
for x,ch in enumerate(line):
if ch == ' ': continue
cell = point(x,y)
if ch == '#': walls.add(cell)
elif ch == 's': rabbitstarts.add(cell)
elif ch == 'e': exits.add(cell)
elif ch == 'c': crusherstarts.add(cell)
return grid, walls, crusherstarts, rabbitstarts, exits
def drawrect(draw, cell, scale, color, size=1):
x, y = int(cell.real)*scale, int(cell.imag)*scale
edge = int((1-size)*scale/2.0 + 0.5)
draw.rectangle([x+edge, y+edge, x+scale-edge, y+scale-edge], fill=color)
def drawframe(runno, turn):
if Image == None:
return
scale = IMGWIDTH/len(grid[0])
W, H = scale*len(grid[0]), scale*len(grid)
img = Image.new('RGB', (W,H), (255,255,255))
draw = ImageDraw.Draw(img)
for cell in rabbitstarts:
drawrect(draw, cell, scale, (190,190,255))
for cell in exits:
drawrect(draw, cell, scale, (190,255,190))
for cell in walls:
drawrect(draw, cell, scale, (190,190,190))
for cell in crushers:
drawrect(draw, cell, scale, (255,0,0), 0.8)
for cell in rabbits:
drawrect(draw, cell, scale, (0,0,255), 0.4)
img.save('anim/run%02uframe%04u.gif' % (runno, turn))
def text2point(textpoint):
# convert text like "22,6" to point object
return point( *map(int, textpoint.split(',')) )
def point2text(cell):
return '%i,%i' % (int(cell.real), int(cell.imag))
def run(number, nseed):
score = 0
turnsleft = turns
turn = 0
seed(nseed)
calltext = program + [mapfile, str(nseed)]
process = subprocess.Popen(calltext,
stdin=subprocess.PIPE, stdout=subprocess.PIPE, stderr=errorlog)
time.sleep(INITTIME)
rabbits.clear()
crushers.clear()
crushers.update( dict((cr, choice(ORTH)) for cr in crusherstarts) )
while turnsleft > 0:
# for each empty start cell, add a rabbit if no crusher in sight.
for cell in rabbitstarts:
if cell in rabbits or set(cansee(cell)) & set(crushers):
continue
rabbits.add(cell)
# write the grid to the runlog and create image frames
if GRIDLOG:
for y,line in enumerate(grid):
for x,ch in enumerate(line):
cell = point(x,y)
if cell in crushers: ch = 'X'
elif cell in rabbits: ch = 'o'
runlog.write(ch)
runlog.write('\n')
runlog.write('\n\n')
if MKIMAGE:
drawframe(number, turn)
# for each crusher, decide move direction.
for cr, direc in crushers.items():
crushers[cr] = bestdir(cr, direc)
# for each crusher, move if possible.
actions = []
for cr, direc in crushers.items():
newcr = cr + direc
if newcr in walls or newcr in crushers:
continue
crushers[newcr] = crushers.pop(cr)
action = ' movesto '
# if crusher is at a rabbit location, remove rabbit.
if newcr in rabbits:
rabbits.discard(newcr)
action = ' crushes '
actions.append(point2text(cr)+action+point2text(newcr))
# output turnsleft, crusher actions, and rabbit locations to program.
send(process, 'turnsleft %u' % turnsleft)
send(process, 'crusher ' + '; '.join(actions))
rabbitlocs = [point2text(r) for r in rabbits]
send(process, ' '.join(['rabbits'] + rabbitlocs))
# read rabbit move requests from program.
start = time.time()
inline = read(process)
if time.time() - start > 0.5:
print 'Move timeout'
break
# if a rabbit not exist or move not possible, no action.
# if rabbit hits a crusher, rabbit is destroyed.
# if rabbit is in exit teleporter, rabbit is removed and score increased.
# if two rabbits collide, they are both destroyed.
newrabbits = set()
for p1,p2 in re.findall(r'(\d+,\d+)\s+to\s+(\d+,\d+)', inline):
p1, p2 = map(text2point, [p1,p2])
if p1 in rabbits and p2 not in walls:
if p2-p1 in ORTH:
rabbits.discard(p1)
if p2 in crushers:
pass # wabbit squished
elif p2 in exits:
score += 1 # rabbit saved
elif p2 in newrabbits:
newrabbits.discard(p2) # moving rabbit collision
else:
newrabbits.add(p2)
# plot each new location of rabbits.
for rabbit in newrabbits:
if rabbit in rabbits:
rabbits.discard(rabbit) # still rabbit collision
else:
rabbits.add(rabbit)
turnsleft -= 1
turn += 1
process.terminate()
return score
mapfile = sys.argv[1]
turns = int(sys.argv[2])
argseed = int(sys.argv[3])
runs = int(sys.argv[4])
program = sys.argv[5:]
errorlog = open('error.log', 'wt')
runlog = open('run.log', 'wt')
grid, walls, crusherstarts, rabbitstarts, exits = features(mapfile)
rabbits = set()
crushers = dict()
if 'anim' not in os.listdir('.'):
os.mkdir('anim')
for fname in os.listdir('anim'):
os.remove(os.path.join('anim', fname))
total = 0
print 'Running:', ' '.join(sys.argv)
print >> runlog, 'Running:', ' '.join(sys.argv)
fmt = '%10s %20s %10s'
print fmt % ('Run', 'Seed', 'Score')
for n in range(runs):
nseed = argseed if argseed else randint(1,1000)
score = run(n, nseed)
total += score
print fmt % (n+1, nseed, score)
print 'Total Score:', total
print >> runlog, 'Total Score:', totalEl controlador crea un registro de texto de las ejecuciones run.logy una serie de imágenes en el animdirectorio. Si su instalación de Python no puede encontrar la biblioteca de imágenes PIL (descargar como Pillow), no se generarán imágenes. He estado animando la serie de imágenes con ImageMagick. P.ej:
convert -delay 100 -loop 0 anim/run01* run1anim.gifPuedes publicar animaciones o imágenes interesantes con tu respuesta.
Puede desactivar estas funciones y acelerar el controlador configurando GRIDLOG
= Falsey / o MKIMAGE = Falseen las primeras líneas del programa del controlador.
Marco de Python sugerido
Para ayudar a comenzar, aquí hay un marco en Python. El primer paso es leer en el archivo del mapa y encontrar rutas a las salidas. En cada turno debe haber algún código para almacenar dónde están las trituradoras, y un código que decida dónde mover nuestros conejos. La estrategia más simple para comenzar es mover a los conejos hacia una salida ignorando a las trituradoras; algunos conejos podrían pasar.
import sys, re
from random import *
mapfile = sys.argv[1]
argseed = int(sys.argv[2])
seed(argseed)
grid = [line.strip() for line in open(mapfile, 'rt')]
#
# Process grid to find teleporters and paths to get there
#
while 1:
msg = sys.stdin.readline()
if msg.startswith('turnsleft'):
turnsleft = int(msg.split()[1])
elif msg.startswith('crusher'):
actions = re.findall(r'(\d+),(\d+) (movesto|crushes) (\d+),(\d+)', msg)
#
# Store crusher locations and movement so we can avoid them
#
elif msg.startswith('rabbits'):
moves = []
places = re.findall(r'(\d+),(\d+)', msg)
for rabbit in [map(int, xy) for xy in places]:
#
# Compute the best move for this rabbit
newpos = nextmoveforrabbit(rabbit)
#
moves.append('%u,%u to %u,%u' % tuple(rabbit + newpos))
print 'move ' + '; '.join(moves)
sys.stdout.flush()fuente
Respuestas:
Crazy, Python 45
Hice 25 corridas con semilla aleatoria, mi computadora no es lo suficientemente rápida como para 1000 (si alguien quiere corregir el puntaje) Primer programa en Python, fue un dolor de depuración para mí. Además, no sé si lo usé bien.
Utiliza un algoritmo de amplitud desde la salida, uno teniendo en cuenta las trituradoras, el otro sin ellas. Tuve mucho tiempo de espera, así que no elegí algo más complejo (eliminación de una trituradora, etc.). Los conejos también se vuelven locos si hay una trituradora cerca con la esperanza de que vaya por un camino equivocado.
fuente
walkables.add((b,a))líneas.Bunny, Java, 26.385
Promedié los puntajes de las carreras 1 a 1000 y multipliqué por 5 para obtener mi puntaje. Estoy bastante seguro de que esto es equivalente al puntaje promedio de todos los juegos posibles con las opciones estándar.
Puntuaciones
La mejor ejecución probada tiene seed 1000. Aquí hay un GIF:
fuente