rch850 の上澄み

技術的な話題とか、雑談とか。タイトルを上澄みに変えました @ 2020/09/02

GDD 2011 スライドパズル祭り

とりあえず解ける段階まで作ってそのまま放置してしまったコードをとりあえずぺたり。ヽ( ・∀・)ノ● ウンコードウンコードー

ただの幅優先探索でメモリ食い過ぎて死にます。チキンなので問題の面積指定して解かせます。あぁもう恥ずかしい

# -*- coding: utf-8 -*-
from copy import deepcopy
import sys

size = 1

class AnswerFound(Exception):
	def __init__(self, answer):
		self.answer = answer

def log(line):
	f = open('log%d.txt' % size, 'a')
	try:
		f.write(line + "\n")
	finally:
		f.close()

def write_answer(id, answer):
	print id, ":", answer
	f = open('answer%d.txt' % size, 'a')
	try:
		f.write('%d: %s\n' % (id, answer))
	finally:
		f.close()

def make_goal(line):
	s = "123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ0"
	s = s[:len(line) - 1]
	try:
		for i in xrange(len(line) - 1):
			if line[i] == '=':
				s = s.replace(s[i], '=')
		s += '0'
		return s
	except:
		log(line)
		raise

class Board(object):
	def read(self):
		w, h, b = [x for x in raw_input().split(',')]
		w = int(w)
		h = int(h)
		self.b = [list(b[i*w : (i+1)*w]) for i in xrange(h)]
		self.w = w
		self.h = h
		self.space = self.find_space()
		self.history = ''
	def solve(self):
		state_map = {}
		queue = [self]
		goal = make_goal(self.board_str())
		log("START: " + self.board_str())
		log("GOAL: " + goal)
		try:
			for i in xrange(1000000):
				board = queue.pop(0)
				#log("Iteration #%d" % i)
				#print board.board_str(), board.history
				#print board
				#print "------------"
				move_results = (board.go_left(),
						board.go_up(),
						board.go_right(),
						board.go_down())
				for r in move_results:
					if not r:
						continue
					if r.board_str() in state_map:
						continue
					if r.board_str() == goal:
						raise AnswerFound(r.history)
					queue.append(r)
					state_map[r.board_str()] = r
		except AnswerFound, e:
			return e.answer
	def get_by_space(self, dx, dy):
		"""return char near space"""
		return self.b[self.space[1] + dy][self.space[0] + dx]
	def set_by_space(self, dx, dy, value):
		"""set char near space"""
		self.b[self.space[1] + dy][self.space[0] + dx] = value
	def swap_space(self, dx, dy, dirchar):
		"""return new board object that the space is swapped with
		target (space.x + dx, space.y, dy).
		if the target is '=', return None."""
		if self.get_by_space(dx, dy) == '=':
			return None
		that = deepcopy(self)
		that.set_by_space(0, 0, that.get_by_space(dx, dy))
		that.set_by_space(dx, dy, '0')
		that.space = (that.space[0] + dx, that.space[1] + dy)
		that.history += dirchar
		return that
	def go_left(self):
		if self.space[0] == 0:
			return None
		if len(self.history) > 0 and self.history[-1] == 'R':
			return None
		return self.swap_space(-1, 0, 'L')
	def go_up(self):
		if self.space[1] == 0:
			return None
		if len(self.history) > 0 and self.history[-1] == 'D':
			return None
		return self.swap_space(0, -1, 'U')
	def go_right(self):
		if self.space[0] >= self.w - 1:
			return None
		if len(self.history) > 0 and self.history[-1] == 'L':
			return None
		return self.swap_space(1, 0, 'R')
	def go_down(self):
		if self.space[1] >= self.h - 1:
			return None
		if len(self.history) > 0 and self.history[-1] == 'U':
			return None
		return self.swap_space(0, 1, 'D')
	def to_lines(self):
		return (''.join(s) for s in self.b)
	def board_str(self):
		return ''.join(self.to_lines())
	def __str__(self):
		return '\n'.join(self.to_lines()) + '\n' + self.history
	def find_space(self):
		"""returns (x,y)"""
		for y in xrange(self.h):
			for x in xrange(self.w):
				if self.b[y][x] == '0':
					return (x, y)

class Solver(object):
	def solve_all(self):
		self.LX, self.RX, self.UX, self.DX = [
				int(x) for x in raw_input().split(' ')]
		N = int(raw_input())
		boards = []
		for i in xrange(N):
			boards.append(Board())
			boards[i].read()
			boards[i].id = i
		for b in boards:
			if b.w * b.h == size:
				answer = b.solve()
				write_answer(b.id, answer)

size = int(sys.argv[1])
s = Solver()
s.solve_all()