ACM 2018 test tour / std.junior.labyrinth

ru en cn

с начала прошло: 1972 д. 13:51
страница обновлена: 29.03.2024 05:50

std.junior.labyrinth: Main.py

import os
import sys
import json
import codecs
import inspect
from io import StringIO

class MyException(Exception):
    def __init__(self, value):
        self.value = value

    def __str__(self):
        return self.value


class Coord:
    def __init__(self, x, y, dir = ''):
        self.x = x
        self.y = y
        self.dir = dir

translateDirs = {
            'U': 'up',
            'D': 'down',
            'L': 'left',
            'R': 'right'
}

def nextDirect(direct, curDir):
    if direct == 'forward':
        if curDir == 'up':
            return Coord(0, -1, 'up')
        if curDir == 'down':
            return Coord(0, 1, 'down')
        if curDir == 'left':
            return Coord(-1, 0, 'left')
        if curDir == 'right':
            return Coord(1, 0, 'right')
        if curDir == 'wait':
            return Coord(0, 0, 'forward')
    if direct == 'left':
        if curDir == 'up':
            return Coord(0, 0, 'left')
        if curDir == 'down':
            return Coord(0, 0, 'right')
        if curDir == 'left':
            return Coord(0, 0, 'down')
        if curDir == 'right':
            return Coord(0, 0, 'up')
        if curDir == 'wait':
            return Coord(-1, 0, 'left')
    if direct == 'right':
        if curDir == 'up':
            return Coord(0, 0, 'right')
        if curDir == 'down':
            return Coord(0, 0, 'left')
        if curDir == 'left':
            return Coord(0, 0, 'up')
        if curDir == 'right':
            return Coord(0, 0, 'down')
        if curDir == 'wait':
            return Coord(1, 0, 'right')
    if direct == 'wait':
        if curDir == 'up':
            return Coord(0, 0, 'up')
        if curDir == 'down':
            return Coord(0, 0, 'down')
        if curDir == 'left':
            return Coord(0, 0, 'left')
        if curDir == 'right':
            return Coord(0, 0, 'right')
        if curDir == 'wait':
            return Coord(0, 0, 'wait')
    if direct == 'behind':
        if curDir == 'up':
            return Coord(0, 1, 'up')
        if curDir == 'down':
            return Coord(0, -1, 'down')
        if curDir == 'left':
            return Coord(1, 0, 'left')
        if curDir == 'right':
            return Coord(-1, 0, 'right')
        if curDir == 'wait':
            return Coord(0, 0, 'forward')
    raise MyException('Invalid direction')


class Path:
    def __init__(self, dir, x, y, initCnt):
        self.dir = dir
        self.x = x
        self.y = y
        self.initCnt = initCnt
        self.cnt = 0

class Cell:
    def __init__(self, x = 0, y = 0, zIndex = 1, points = 0, dLife = 0):
        self.x = x
        self.y = y
        self.zIndex = zIndex
        self.points = points
        self.dLife = dLife

class Monster(Cell):
    def __init__(self, monster):
        Cell.__init__(self)
        try:
            self.path = []
            path = monster['path']
            self.x = path[0]['x']
            self.y = path[0]['y']
            self.zIndex = monster['zIndex'] if 'zIndex' in monster else 0
            self.points = 0
            self.dLife = 0
            self.looped = monster['looped']
            self.die = monster['die']
            for p in path:
                self.path.append(Path(p['dir'], p['x'], p['y'], p['initCnt']))
            self.index = 0
        except:
            raise MyException('Invalid monster format')

    def tryNextStep(self):
        dir = self.path[self.index].dir
        x1 = self.x
        y1 = self.y
        c = Coord(0, 0)
        if self.index == len(self.path) - 1 and self.path[self.index].cnt == self.path[self.index].initCnt:
            if not self.looped:
                return Coord(self.x, self.y)
            x1 = self.path[0].x
            y1 = self.path[0].y
            dir = self.path[0].dir
        elif self.path[self.index].cnt == self.path[self.index].initCnt:
            dir = self.path[self.index + 1].dir
        c = nextDirect('forward', translateDirs[dir])
        global curState
        if not curState.field[y1 + c.y][x1 + c.x].isWall:
            x1 += c.x
            y1 += c.y
        return Coord(x1, y1)

    def nextStep(self):
        c = Coord(0, 0)
        if self.index == len(self.path) - 1  and self.path[self.index].cnt == self.path[self.index].initCnt:
            if not self.looped:
                return
            self.index = 0
            for p in self.path:
                p.cnt = 0
        elif self.path[self.index].cnt == self.path[self.index].initCnt:
            self.index += 1
            self.path[self.index].cnt = 0
        c = nextDirect('forward', translateDirs[self.path[self.index].dir])
        global curState
        if not curState.field[self.y + c.y][self.x + c.x].isWall:
            self.y += c.y
            self.x += c.x
        self.path[self.index].cnt += 1

class Lock(Cell):
    def __init__(self, x, y):
        try:
            Cell.__init__(self, x, y, 11, 0, 0)
            self.locked = True
        except:
            raise MyException('Invalid lock format')

class Key(Cell):
    def __init__(self, x, y, l):
        try:
            Cell.__init__(self, x, y, 1, 0, 0)
            self.locks = [Lock(0, 0) for i in range(l)]
            self.found = False
        except:
            raise MyException('Invalid key format')


class Box(Cell):
    def __init__(self, x, y, box):
        try:
            Cell.__init__(self, x, y, box['zIndex'] if 'zIndex' in box else 2,
                box['points'] if 'points' in box else 0,
                box['dLife'] if 'dLife' in box else 0)
        except:
            raise MyException('Invalid box format')

class Prize(Cell):
    def __init__(self, x, y, prize):
        try:
            Cell.__init__(self, x, y, prize['zIndex'] if 'zIndex' in prize else 2,
                prize['points'] if 'points' in prize else 0,
                prize['dLife'] if 'dLife' in prize else 0)
            self.found = False
        except:
            raise MyException('Invalid prize format')

class FieldElem:
    def __init__(self, x, y, isWall):
        self.x = x
        self.y = y
        self.isWall = isWall
        self.cells = []

    def mayPush(self, cell):
        if self.isWall:
            return False
        for c in self.cells:
            if c.zIndex >= cell.zIndex:
                return False
        return True

    def findCell(self, t):
        for cell in self.cells:
            if isinstance(cell, t):
                return cell

class State:
    def __init__(self, **kwargs):
        self.cur = Coord(0, 0)
        self.d = Coord(0, 0)
        self.arrowZIndex = 3

        self.dLife = kwargs.get('dLife', 0)
        self.life = kwargs.get('startLife', 0)
        self.pnts = kwargs.get('startPoints', 0)
        self.maxStep = kwargs.get('maxStep', 10000)
        self.maxCmdNum = kwargs.get('maxCmdNum', 10000)
        self.commandsFine = kwargs.get('commandsFine', 0)
        self.stepsFine = kwargs.get('stepsFine', 0)
        self.invalidDirectionFine = kwargs.get('invalidDirectionFine', 0)
        self.steps = 0
        self.cmdNum = 0

        self.map = kwargs.get('map', [])
        self.specSymbols = kwargs.get('specSymbols', [])
        self.keys = kwargs.get('keys', [])
        self.locks = kwargs.get('locks', [])
        self.movingElements = kwargs.get('movingElements', [])
        self.sol = kwargs.get('sol', '')

        self.dead = False

        self.curMap = []
        self.field = []
        self.monsters = []
        self.prizesLeft = 0
        self.usedFunc ={'forward':[], 'left':[], 'right':[], 'wait':[]}

        for i in range(len(self.map)):
            self.curMap.append([])
            self.field.append([])
            for j in range(len(self.map[i])):
                obj = Cell()
                self.curMap[i].append(self.map[i][j])
                self.field[i].append(FieldElem(j, i, self.curMap[i][j] == '#'))
                if self.curMap[i][j] == 'R' or self.curMap[i][j] == 'U' or self.curMap[i][j] == 'D' or self.curMap[i][j] == 'L':
                    self.cur = Coord(j, i, translateDirs[self.curMap[i][j]])
                for k in range(len(self.specSymbols)):
                    if self.curMap[i][j] == self.specSymbols[k]['symbol']:
                        obj = Prize(j, i, self.specSymbols[k]) if self.specSymbols[k]['action'] == 'eat' else Box(j, i, self.specSymbols[k])
                        if isinstance(obj, Prize):
                            self.prizesLeft += 1
                        self.field[i][j].cells.append(obj)

        for k in range(len(self.movingElements)):
            obj = Monster(self.movingElements[k])
            self.field[obj.y][obj.x].cells.append(obj)
            self.monsters.append(obj)
        for k in range(len(self.keys)):
            key = Key(self.keys[k]['x'], self.keys[k]['y'], len(self.locks[k]))
            self.field[key.y][key.x].cells.append(key)
            for j in range(len(self.locks[k])):
                lock = Lock(self.locks[k][j]['x'], self.locks[k][j]['y'])
                key.locks[j] = lock
                self.field[lock.y][lock.x].cells.append(lock)



    def overrun(self, x, y):
        return (x >= len(self.field[0]) or x < 0 or y >= len(self.field) or y < 0);


    def getFieldElem(self, dir):
        newDir = nextDirect(dir, self.cur.dir);
        cX = self.cur.x + newDir.x;
        cY = self.cur.y + newDir.y;
        if  dir != 'forward' and dir != 'behind':
            cX += nextDirect('forward', newDir.dir).x;
            cY += nextDirect('forward', newDir.dir).y;
        return None if self.overrun(cX, cY) else self.field[cY][cX];

global curState
def swap(arr, i, j):
    t = arr[i]
    arr[i] = arr[j]
    arr[j] = t

def sort(arr):
    for i in range(len(arr) - 1, -1, -1):
        for j in range(i):
            if arr[j].zIndex < arr[j + 1].zIndex:
                swap(arr, j, j + 1)

def nextStep(direct):
    global curState
    st_1 = inspect.currentframe().f_back
    st_2 = inspect.getframeinfo(st_1.f_back)
    st_1 = inspect.getframeinfo(st_1)
    if st_2[1] not in curState.usedFunc[st_1[2]]:
        curState.cmdNum += 1
        curState.usedFunc[st_1[2]].append(st_2[1])
    result = True
    c = nextDirect(direct, curState.cur.dir)
    dx = c.x
    dy = c.y
    #curState.cur.dir = c.dir
    curState.life += curState.dLife
    c_x = curState.cur.x + dx
    c_y = curState.cur.y + dy
    changeCoord = True
    if not(c_x < 0 or c_x >= len(curState.field[0]) or c_y < 0 or c_y >= len(curState.field)):
        elem = curState.field[c_y][c_x]
        if elem.isWall:
            changeCoord = False
        sort(elem.cells)
        for cell in elem.cells:
            if cell.x != c_x or cell.y != c_y:
                continue
            if isinstance(cell,  Lock) and cell.locked:
                changeCoord = False
                break
            if isinstance(cell, Monster):
                curState.dead = True
                raise MyException('Killed by a monster')

            if isinstance(cell, Box):
                tx = c_x + dx
                ty = c_y + dy
                f = tx < 0 or tx >= len(curState.field[0]) or ty < 0 or ty >= len(curState.field)
                if not f:
                    el1 = curState.field[ty][tx]
                    if el1.mayPush(cell):
                        elem.cells.remove(cell)
                        cell.x = tx
                        cell.y = ty
                        el1.cells.append(cell)
                        curState.pnts += cell.points
                        curState.life += cell.dLife
                        continue
                    else:
                        changeCoord = False
                else:
                    changeCoord = False
            if isinstance(cell, Prize) and not cell.found:
                cell.found = True
                curState.pnts += cell.points
                curState.life += cell.dLife
                elem.cells.remove(cell)
                curState.prizesLeft -= 1
                continue
            if isinstance(cell, Key) and not cell.found:
                cell.found = True
                if hasattr(cell, 'locks'):
                    for lock in cell.locks:
                        lock.locked = False
                        lock.zIndex = 0
                elem.cells.remove(cell)
                continue
    else:
        changeCoord = False
    if changeCoord:
        curState.cur.x = c_x
        curState.cur.y = c_y
        curState.cur.dir = c.dir
    else:
        curState.pnts -= curState.invalidDirectionFine

    for monster in curState.monsters:
        c1 = monster.tryNextStep()
        if (curState.field[c1.y][c1.x].mayPush(monster)):
            if c1.y == curState.cur.y and c1.x == curState.cur.x:
                curState.dead = True
                raise MyException('Killed by a monster')

            curState.field[monster.y][monster.x].cells.remove(monster)
            monster.nextStep()
            curState.field[monster.y][monster.x].cells.append(monster);
        else:
            monster.path[monster.index].cnt += 1
    if curState.life == 0:
        curState.dead = True
        raise MyException('Dead')
    if curState.steps + 1 > curState.maxStep:
        curState.dead = True
        raise MyException('Too many steps')
    if curState.cmdNum >= curState.maxCmdNum:
        curState.dead = True
        raise MyException('Too many commands')

    curState.steps += 1

def forward(cnt = 1):
    for i in range(int(cnt)):
        nextStep('forward')

def left(cnt = 1):
    for i in range(int(cnt)):
        nextStep('left')

def right(cnt = 1):
    for i in range(int(cnt)):
        nextStep('right')

def wait(cnt = 1):
    for i in range(int(cnt)):
        nextStep('wait')

def objectPosition(object, direction):
    dir = ''
    if direction == 'atTheLeft':
        dir = 'left'
    elif direction == 'atTheRight':
        dir = 'right'
    elif direction == 'inFrontOf':
        dir = 'forward'
    elif direction == 'behind':
        dir = 'behind'
    else:
        return False

    cell = curState.getFieldElem(dir)
    if cell == None:
        return object == 'border'


    if  cell.isWall:
        return object == 'wall'
    if  object == 'prize':
        return cell.findCell(Prize) != None
    if  object == 'box':
        return cell.findCell(Box) != None
    if  object == 'monster':
        return cell.findCell(Monster) != None
    if  object == 'lock':
        return cell.findCell(Lock) != None
    if  object == 'key':
        return cell.findCell(Key) != None
    if  object == 'cell':  
        return len(cell.cells) == 0
    return False

def isCompleted():
    return curState.prizesLeft <= 0

def solve():
    error = None
    try:
        oldstdout = sys.stdout
        f = open('problem.json', 'r')
        s = f.read()
        problem = json.loads(s)
        f.close()
        if not 'map' in problem:
            raise MyException('Map is undefined')
        if 'keys' in problem:
            if  'locks' not in problem:
                raise MyException("Keys are defined, but locks cells aren't defined")
            if len(problem['keys']) != len(problem['locks']):
                raise MyException("Keys and locks length aren't equal")

        global curState
        curState = State(**problem)
        sol = codecs.open('output.txt', 'r', 'utf-8').read()

        redirected_output = sys.stdout = StringIO()


        exec(sol, {
            'forward': forward, 'left': left, 'right': right, 'wait': wait,
            'objectPosition': objectPosition, 'isCompleted': isCompleted,
        })
        sys.stdout = oldstdout
    except:
        error = sys.exc_info()
        sys.stdout = oldstdout
    if error:
        print(error[1])
        print(redirected_output.getvalue())
        return 1
    else:
        print(curState.pnts - curState.stepsFine * curState.steps - curState.commandsFine * curState.cmdNum)
        print(curState.prizesLeft)

if __name__ == '__main__':
    sys.exit(solve())
Дальневосточный федеральный университет