canyouhack.it Programming Challenge 3 Lost!

http://canyouhack.it/Hacking-Challenges/Programming-Challenges/Lost/

최소한의 짧은 길을 찾는 프로그래밍을 하는 문제이다. 

http://canyouhack.it/Content/Challenges/Programming/Prog3.php 를 들어가보면.

대충 요런식의 길이 나오는데, 초록색부터 빨간색까지 가는 최소의 길 수를 5초안에 계산해서 내면 된다.

(초록색과 빨간색 칸도 포함하여 낸다.) 예시로 위의 사진은 72칸이다. 

돌아다니다가 설명도 잘되있고 구현도 잘되있는 사이트를 찾았다. A*알고리즘이란다.

http://www.laurentluce.com/posts/solving-mazes-using-python-simple-recursivity-and-a-search/

어쨋든 저기서 설명을 읽고 알고리즘을 대충 이해.. 하고 만지작거려서 사용법을 안 후 프로그래밍 하면 된다. 문제가 좀 빡세긴 했다.

소스.

# -*- encoding: cp949 -*-
import urllib2, re
import heapq
session = 본인 세션.

#req = urllib2.Request('http://127.0.0.1/index.php')
req = urllib2.Request('http://canyouhack.it/Content/Challenges/Programming/Prog3.php')
req.add_header('cookie',session)
page = urllib2.urlopen(req).read() #페이지를 받아온다.

start = re.findall('.p(.*?)\s+{\s+background-color: green;\s+}',page)[0] #시작지점
end = re.findall('.p(.*?)\s+{\s+background-color: red;\s+}',page)[0] #도착지점
start = (int(start)/40*2,int(start)%40*2); end = (int(end)/40*2,int(end)%40*2) #시작지점과 도착지점을 좌표 형식의 튜플로 만든다.
print start,end
maps = map(lambda x:x.strip(),re.split(r'<tr>\r\n\t|.</td>\r\n|<strong>.</strong></td>\r\n',page)[1:-1]) #페이지를 알아서 잘 파싱해온다. 설명하기엔 너무 김.
maps = [i for i in maps if i!='</tr>'] #파싱해온 페이지에서 쓸때없는 태그를 제거한다.
maps = [[maps[j/2] if j%2==0 else 0 for j in range(i*40,i*40+80)] if i%2==0 else [0 if i%2==0 else 1 for i in range(80)] for i in range(80)] 
#맵은 40*40인데, 난 80*80으로 만들었다. 왜 두배로 만들었냐면, 벽도 하나의 공간으로 보았기 때문이다. 벽은 1로 놓고, 지나갈 수 있는 길은 0으로 세팅했다. 내가봐도 나말고는 이해하기 힘들듯 싶다...

for i in range(0,len(maps),2):
    for j in range(len(maps[i])):
        if j%2==0: #지나갈 수 있는 공간중에서
            switch = re.findall('<td class="c(\d+) p\d+">',maps[i][j])[0] #데이터를 파싱해온다.
            if switch == '00': pass
            elif switch == '01': maps[i][j+1] = 1 #c01은 오른쪽이 막혀있으므로 오른쪽을 벽(1)로 만든다.
            elif switch == '10': maps[i+1][j] = 1 #c10은 아래쪽이 막혀있다. 아래쪽을 벽으로 만듬.
            elif switch == '11': maps[i+1][j] = 1; maps[i][j+1] = 1 #오른쪽, 아래쪽을 벽으로 만든다.
            maps[i][j] = 0 #지나갈 수 있는 공간은 다 0으로 만든다.
walls = [] #벽(1)을 좌표 형식으로 튜플로 만들어 저장한다.
for i in range(len(maps)):
    for j in range(len(maps[i])):
        if maps[i][j]==1:
            walls.append((i,j))
walls = tuple(walls)
"""
grid = [[0, 0, 0, 0, 0, 1],
        [1, 1, 0, 0, 0, 1],
        [0, 0, 0, 1, 0, 0],
        [0, 1, 1, 0, 0, 1],
        [0, 1, 0, 0, 1, 0],
        [0, 1, 0, 0, 0, 0]] 맵 모양.""" #이런식으로 맵을 만들었는데, 예로 0,0에서 5,5가 도착지라고 하면 (0,0)->(1,0)->(2,0)~~(5,4)->(5,5)로 알아서 맵을 찾아간다.
#아래 클래스부분은 전부 위의 사이트에서 가져왔으며, 내가 수정한 부분은 count를 세는 부분.
class Cell(object):
    def __init__(self, x, y, reachable):
        """
        Initialize new cell

        @param x cell x coordinate
        @param y cell y coordinate
        @param reachable is cell reachable? not a wall?
        """
        self.reachable = reachable
        self.x = x
        self.y = y
        self.parent = None
        self.g = 0
        self.h = 0
        self.f = 0
        
class AStar(object):
    def __init__(self):
        self.opened = []
        heapq.heapify(self.opened)
        self.closed = set()
        self.cells = []
        self.grid_height = 80#맵의 행의 크기는 80
        self.grid_width = 80#맵 열의 크기는 80
        self.count = 0 #이동하는 횟수. 이게 답으로 보낼 변수.
    def init_grid(self,walls,s,e):
        #walls = ((0, 5), (1, 0), (1, 1), (1, 5), (2, 3), 
        #         (3, 1), (3, 2), (3, 5), (4, 1), (4, 4), (5, 1))
        for x in range(self.grid_width):
            for y in range(self.grid_height):
                if (x, y) in walls:
                    reachable = False
                else:
                    reachable = True
                self.cells.append(Cell(x, y, reachable))
        self.start = self.get_cell(s[0],s[1])#self.get_cell(0, 0)
        self.end = self.get_cell(e[0],e[1])#self.get_cell(5, 5)
    def get_heuristic(self, cell):
        """
        Compute the heuristic value H for a cell: distance between
        this cell and the ending cell multiply by 10.

        @param cell
        @returns heuristic value H
        """
        return 10 * (abs(cell.x - self.end.x) + abs(cell.y - self.end.y))
    def get_cell(self, x, y):
        """
        Returns a cell from the cells list

        @param x cell x coordinate
        @param y cell y coordinate
        @returns cell
        """
        return self.cells[x * self.grid_height + y]
    def get_adjacent_cells(self, cell):
        """
        Returns adjacent cells to a cell. Clockwise starting
        from the one on the right.

        @param cell get adjacent cells for this cell
        @returns adjacent cells list 
        """
        cells = []
        if cell.x < self.grid_width-1:
            cells.append(self.get_cell(cell.x+1, cell.y))
        if cell.y > 0:
            cells.append(self.get_cell(cell.x, cell.y-1))
        if cell.x > 0:
            cells.append(self.get_cell(cell.x-1, cell.y))
        if cell.y < self.grid_height-1:
            cells.append(self.get_cell(cell.x, cell.y+1))
        return cells
    def display_path(self):
        cell = self.end
        while cell.parent is not self.start:
            cell = cell.parent
            self.count += 1
            print 'path: cell: %d,%d,%d' % (cell.x, cell.y,self.count)
            
    def update_cell(self, adj, cell):
        """
        Update adjacent cell

        @param adj adjacent cell to current cell
        @param cell current cell being processed
        """
        adj.g = cell.g + 10
        adj.h = self.get_heuristic(adj)
        adj.parent = cell
        adj.f = adj.h + adj.g
    def process(self):
        # add starting cell to open heap queue
        heapq.heappush(self.opened, (self.start.f, self.start))
        while len(self.opened):
            # pop cell from heap queue 
            f, cell = heapq.heappop(self.opened)
            # add cell to closed list so we don't process it twice
            self.closed.add(cell)
            # if ending cell, display found path
            if cell is self.end:
                self.display_path()
                break
            # get adjacent cells for cell
            adj_cells = self.get_adjacent_cells(cell)
            for adj_cell in adj_cells:
                if adj_cell.reachable and adj_cell not in self.closed:
                    if (adj_cell.f, adj_cell) in self.opened:
                        # if adj cell in open list, check if current path is
                        # better than the one previously found for this adj
                        # cell.
                        if adj_cell.g > cell.g + 10:
                            self.update_cell(adj_cell, cell)
                    else:
                        self.update_cell(adj_cell, cell)
                        # add adj cell to open list
                        heapq.heappush(self.opened, (adj_cell.f, adj_cell))
        return (self.count+1)/2 + 1 #이게 이동한 횟수다. 한칸을 이동하는데 2칸씩 이동하므로, /2를 하고 끝에 +1을 해준다.(시작,끝점 포함용)
a = AStar()
a.init_grid(walls,start,end)
answer = a.process() #답을 받아와서 보낸다.

req = urllib2.Request('http://canyouhack.it/Content/Challenges/Programming/Prog3.php?Answer='+str(answer))
req.add_header('cookie',session)
print urllib2.urlopen(req).read()