#! /usr/bin/env python
# encoding: latin1
import random

# Constantes
H = 1
V = -1

def inicializar_tablero(dimension):
	tablero = []
	for i in range(dimension):
		tablero.append([])
		for j in range(dimension):
			tablero[i].append(" ")
	return tablero

def borrar_palabra(tablero, x, y, direccion, largo, lista):
	posx = x; posy = y
	for i in range(largo):
		if (direccion == H): 
			posx = x+i
		else: 
			posy = y+i
		vieja = tomar_palabra(tablero, posx, posy, direccion*-1)
		if vieja == "" or len(vieja) < 5:
			tablero[posy][posx] = " "

	# Borrar los *
	if (direccion == H):
		if x > 0:
			borrar = True
			if y > 0 and tomar_palabra(tablero, x-1, y-1, direccion*-1) != "":
				borrar = False
			elif y < len(tablero)-1 and tomar_palabra(tablero, x-1, y+1, direccion*-1) != "":
				borrar = False
			elif x > 1 and tomar_palabra(tablero, x-2, y, direccion):
				borrar = False
			if (borrar):
				tablero[y][x-1] = " "

		if x+largo < len(tablero[y]):
			borrar = True
			if y > 0 and tomar_palabra(tablero, x+largo, y-1, direccion*-1) != "":
				borrar = False
			elif y < len(tablero)-1 and tomar_palabra(tablero, x+largo, y+1, direccion*-1) != "":
				borrar = False
			elif x+largo < len(tablero[y])-1 and tomar_palabra(tablero, x+largo+1, y, direccion) != "":
				borrar = False
			if (borrar):
				tablero[y][x+largo] = " "
	else:
		if y > 0:
			borrar = True
			if x > 0 and tomar_palabra(tablero, x-1, y-1, direccion*-1) != "":
				borrar = False
			elif x < len(tablero)-1 and tomar_palabra(tablero, x+1, y-1, direccion*-1) != "":
				borrar = False
			elif y > 1 and tomar_palabra(tablero, x, y-2, direccion) != "":
				borrar = False
			if (borrar):
				tablero[y-1][x] = " "

		if y+largo < len(tablero):
			borrar = True
			if x > 0 and tomar_palabra(tablero, x-1, y+largo, direccion*-1) != "":
				borrar = False
			elif x < len(tablero[y])-1 and tomar_palabra(tablero, x+1, y+largo, direccion*-1) != "":
				borrar = False
			elif y+largo < len(tablero)-1 and tomar_palabra(tablero, x, y+largo+1, direccion) != "":
				borrar = False
			if (borrar):
				tablero[y+largo][x] = " "

def escribir_palabra(palabra, tablero, x, y, direccion):
	largo = len(palabra)
	if (direccion == H):
		if x > 0: tablero[y][x-1] = "*"
		if x+largo < len(tablero): tablero[y][x+largo] = "*"
		for i in range(largo):
			tablero[y][x+i] = palabra[i]
	else:
		if y > 0: tablero[y-1][x] = "*"
		if y+largo < len(tablero): tablero[y+largo][x] = "*"
		for i in range(largo):
			tablero[y+i][x] = palabra[i]

	#imprimir_tablero(tablero)

def tomar_palabra(tablero, x, y, direccion):
	if (direccion == H):
		inicio = x
		while inicio > 0 and tablero[y][inicio] != "*": 
			if tablero[y][inicio] == " ": return ""
			inicio-=1
		fin = x
		while fin < len(tablero[y]) and tablero[y][fin] != "*": 
			if tablero[y][fin] == " ": return ""
			fin+=1
		if inicio == 0 and fin == len(tablero[y]): return ""
		if (fin-inicio) < 5: return ""
		return "".join(tablero[y][inicio+1:fin])
	else:
		inicio = y
		while inicio > 0 and tablero[inicio][x] != "*": 
			if tablero[inicio][x] == " ": return ""
			inicio-=1
		fin = y
		while fin < len(tablero) and tablero[fin][x] != "*": 
			if tablero[fin][x] == " ": return ""
			fin+=1
		if inicio == 0 and fin == len(tablero[y]): return ""
		if (fin-inicio) < 5: return ""
		palabra = []
		for i in range(inicio+1,fin):
			palabra.append(tablero[i][x])
		return "".join(palabra)

def libre(tablero, x, y):
	if y < 0 or y >= len(tablero): return True
	if x < 0 or x >= len(tablero[y]): return True
	if tablero[y][x] == " " or tablero[y][x] == "*":
		return True
	else:
		return False

def colocar_palabra(palabra, tablero, x, y, direccion, lista):
	# Valido que no haya un caracter antes del comienzo
	largo = len(palabra)
	if (direccion == H):
		if x < 0 or x+largo > len(tablero): return False
		if x > 0 and not libre(tablero, x-1, y): return False
		if x+largo < len(tablero) and not libre(tablero, x+largo, y): return False
	else:
		if y < 0 or y+largo > len(tablero[0]): return False
		if y > 0 and not libre(tablero, x, y-1): return False
		if y+largo < len(tablero) and not libre(tablero, x, y+largo): return False

	# Pruebo si la palabra entra.
	for i in range(largo):
		if (direccion == H):
			letra = tablero[y][x+i]
		else:
			letra = tablero[y+i][x]
		# No se puede poner una palabra en los casilleros negros
		if letra == "*": 
			return False
		# Tampoco se puede poner si ya hay otra letra
		if letra != " " and letra != palabra[i]:
			return False
	
	# Si entra, la escribo y la saco de la lista:
	escribir_palabra(palabra, tablero, x, y, direccion)
	lista.remove(palabra)

	# Validacion, recursiva
	#todomal = False
	for i in range(len(palabra)):
		if (direccion == H):
			ant = (x+i,y-1)
			pos = (x+i,y)
			sig = (x+i,y+1)
		else:
			ant = (x-1, y+i)
			pos = (x, y+i)
			sig = (x+1, y+i)

		pisada = tomar_palabra(tablero, pos[0], pos[1], direccion*-1)

		# Valida si hay otras letras pero no una palabra

		if pisada == "":

			# Chequeo si alguno de los dos tiene una letra.
			if (not libre(tablero, sig[0], sig[1])  or 
		        not libre(tablero, ant[0], ant[1])):
#				todomal = True
#				break

				# Defino las variables para no estar buscandolas
				actual = tablero[pos[1]][pos[0]]
				if (ant[0] > 0 and ant[1] > 0):
					anterior = tablero[ant[1]][ant[0]]
				else:
					anterior = " "
				if sig[0] < len(tablero[y]) and sig[1] < len(tablero):
					siguiente = tablero[sig[1]][sig[0]]
				else:
					siguiente = " "

				colocada = False
				# Hay que poner otra palabra.
				for nueva in lista:
					if not libre(tablero, ant[0], ant[1]): 
						par = (anterior,actual)
						ubi = 0
					else: 
						par = (actual, siguiente)
						ubi = 1
					# Trato de ubicarla en algún lugar
					for l in range(len(nueva)-1):
						# Llamada recursiva
						if nueva[l] == par[0] and nueva[l+1] == par[1]:
							if (direccion == H):
								if colocar_palabra(nueva, tablero, pos[0], 
									pos[1]-l-ubi, direccion*-1, lista):
									colocada = True
									break
							else:
								if colocar_palabra(nueva, tablero, pos[0]-l-ubi, 
									pos[1], direccion*-1, lista):
									colocada = True
									break

					# Si esta palabra anduvo, salgo del bucle
					if colocada:
						break

				# Si ninguna palabra pudo ser colocada, hay que volver 
				# esta para atras.
				if not colocada:
					lista.append(palabra)
					borrar_palabra(tablero, x, y, direccion, len(palabra), lista)
					return False
#	if todomal:
#		return False
#	else:
#		escribir_palabra(palabra, tablero, x, y, direccion)
#		lista.remove(palabra)
			
	# Si llego hasta acá es que pudo poner la palabra correctamente
	return True

def imprimir_tablero(tablero):
	print "-"*len(tablero)
	for linea in tablero:
		for y in linea:
			print y,
		print
	print "-"*len(tablero)

import random

def main():
	dimension = 20
	tablero = inicializar_tablero(dimension)
	lista = [ linea.rstrip() for linea in open("5vocales.txt") ]
	random.shuffle(lista)

	# Coloca la primera palabra
	inicial = lista.pop()
	x = (dimension-len(inicial))/2
	escribir_palabra(inicial, tablero, x, dimension/2, H)
	
	# Intenta poner palabras
	for intento in lista:
		colocada = False
		for l in range(len(intento)):
			for x in range(dimension):
				for y in range(dimension):
					if tablero[y][x] == intento[l]:
						if random.random() > 0.5:
							if x-l > 0 and colocar_palabra(intento, tablero, x-l, y, H, lista):
								colocada = True
								break
						else:
							if y-l > 0 and colocar_palabra(intento, tablero, x, y-l, V, lista):
								colocada = True
								break
				if colocada: break
			if colocada: break
	for intento in lista:
		colocada = False
		for l in range(len(intento)):
			for x in range(dimension):
				for y in range(dimension):
					if tablero[y][x] == intento[l]:
						if random.random() > 0.5:
							if x-l > 0 and colocar_palabra(intento, tablero, x-l, y, H, lista):
								colocada = True
								break
						else:
							if y-l > 0 and colocar_palabra(intento, tablero, x, y-l, V, lista):
								colocada = True
								break
				if colocada: break
			if colocada: break
			
	imprimir_tablero(tablero)

main()