swamp.py

import collections 

m = [[-1,1,1,-1,-1,1,1,-1,-1,1],[1,"S",1,"L",-1,-1,-1,-1,-1,-1],[-1,-1,-1,1,1,-1,1,-1,1,1],[1,"L",-1,-1,1,-1,1,-1,1,-1],[-1,1,1,-1,-1,-1,-1,"L",1,-1],[1,-1,1,-1,-1,1,-1,1,-1,1],[-1,"L",-1,-1,-1,1,-1,-1,-1,1],[-1,1,-1,1,1,-1,1,-1,-1,-1],[-1,1,-1,-1,-1,1,1,-1,"G",1],[-1,-1,1,1,-1,-1,-1,1,-1,-1]]

print(m)


class Position(collections.namedtuple("Position", ['x', 'y'])):
    __slots__ = ()
    def up(self):
        return self._replace(y=self.y-1)
    def down(self):
        return self._replace(y=self.y+1)
    def left(self):
        return self._replace(x=self.x-1)
    def right(self):
        return self._replace(x=self.x+1)


class Player(collections.namedtuple("Player", ['position', 'goal', 'hp', 'target', 'hp_max', 'history', 'visited'])):
    __slots__ = ()

    def move(self, direction):
        if direction == 'u':
            pos = self.position.up()
        elif direction == 'd':
            pos = self.position.down()
        elif direction == 'l':
            pos = self.position.left()
        elif direction == 'r':
            pos = self.position.right()
        else:
            assert False, "got %s"%(direction,)
            pass
        return self._replace(position=pos, history=self.history + (direction,))

    def visit(self):
        if self.position not in self.visited:
            return True, self._replace(visited=self.visited.union(frozenset((self.position,))))
        return False, self

    def check(self, game):
        if self.position == self.goal:
            if game.current_best[0] < self.hp:
                game.current_best = (self.hp, self.history)
            return False
        if self.hp < self.hp_max - 5:
            return False
        return True

greed_dict = {'G': 0, 1:1, -1:2, 'L':3, 'S': 4}


class Game:
    def __init__(self, mss):
        self.count = 0
        self.knownmax = 0
        self.current_best = (-100, None)
        xss = []
        boundary = tuple("L" for x in range(len(mss[0])+2))
 
        xss.append(boundary[:])
        for ms in mss:
            xss.append(tuple(["L"] + ms[:] + ["L"]))
        xss.append(boundary[:])
        self.map = tuple(xss)
 
        for yi, ms in enumerate(self.map):
            for xi, m in enumerate(ms):
                if m == "S":
                    self.start = Position(xi, yi)
                if m == "G":
                    self.goal = Position(xi, yi)
 
    def setup_pc(self, hp, target):
        return Player(
              position = self.start,
              goal= self.goal,
              hp = hp,
              target = target,
              hp_max = 0,
              history = tuple(),
              visited = frozenset([self.start]))

    def get_sq(self, pos):
        assert(isinstance(pos, Position))
        return self.map[pos.y][pos.x]

    def update(self, player):
        m = self.get_sq(player.position)
        if isinstance(m, int):
            if player.hp + m > player.hp_max:
                return player._replace(hp=player.hp+m, hp_max=player.hp+m)
            else:
                return player._replace(hp=player.hp+m)
        elif isinstance(m, str):
            if m == "L":
                return player._replace(hp=0)
            elif m == "G":
                return player._replace(hp=player.hp - player.target)
            else:
                pass
        else:
            pass
        return player

    def search(self, p):
        self.knownmax = max(self.knownmax, p.hp_max)
        self.count += 1
        if self.count > 100000:
            print(self.knownmax)
            print(self.current_best)
            self.count = 0

        greedy = [(d, self.get_sq(p.move(d).position))for d in 'udlr']
        greedy.sort(key=lambda x: greed_dict[x[1]])
        for d, _ in greedy:
            ok, q = p.move(d).visit()
            if ok:
                r = self.update(q)
                if r.check(self):
                    self.search(r)

g = Game(m)
print(g.map)
p = g.setup_pc(36, 49)
print(p)
print("search!")

g.search(p)

print("done. maybe not found.")

序盤で見つかる経路例。
(-4, ('u', 'l', 'd', 'd', 'r', 'r', 'd', 'd', 'r', 'u', 'u', 'r', 'u', 'u', 'r', 'd', 'd', 'd', 'd', 'd', 'r', 'u', 'r', 'u', 'u', 'u', 'r', 'u', 'r', 'd', 'd', 'd', 'd', 'd', 'l', 'd', 'l', 'd', 'l', 'l', 'u', 'l', 'l', 'l', 'u', 'l', 'l', 'd', 'd', 'd', 'd', 'r', 'r', 'u', 'r', 'r', 'd', 'r', 'r', 'r', 'r', 'u')

なおったと思いたい
(-4, ('u', 'r', 'd', 'd', 'r', 'r', 'd', 'd', 'd', 'r', 'd', 'd', 'd', 'r', 'u', 'u', 'u', 'r', 'r', 'u', 'u', 'u', 'r', 'd', 'd', 'd', 'd', 'd', 'd', 'l'))

'u', 'r', 'd', 'd', 'r', 'r', 'd', 'd', 'd', 'r', 'd', 'd', 'l', 'l', 'u', 'u', 'l', 'u', 'l', 'd', 'l', 'd', 'd', 'r', 'd', 'd', 'r', 'r', 'u', 'r', 'r', 'r', 'u', 'u', 'u', 'r', 'r', 'u', 'u', 'u', 'r', 'd', 'd', 'd', 'd', 'd', 'd', 'l'

BDD/ZDDを使う。Simpathとか実装しないと駄目だろう