"""
/*
 * genaut.py 0.1.0
 * Crossword generator for Crosswords For Linux
 *
 * Copyright (C) Manuel Gutierrez Algaba, 2000, 2001, 2002
 *
 * This program is free software; you can redistribute it and/or modif
y
 * it under the terms of the GNU General Public License as published b
y
 * the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
*/
"""

#import rand
import random
import copy

const_max_iter = 500
max_iter = const_max_iter

class celda:
    def __init__(self):
	self.c= '-'
	self.orientacion = None
	self._ultima =None
	self._bloqueada = None
	self._bloqueada_extremos = None

    def haz_letra(self,c ):
	self.c = c

    def que_letra(self):
	return self.c

    def haz_orientacion(self, o):
	self.orientacion = o

    def que_orientacion(self):
	return self.orientacion

    def haz_ultima(self):
	self._ultima = 1

    def es_ultima(self):
	return self._ultima

    def esta_bloqueada(self):
	return self._bloqueada 

    def haz_bloqueada(self):
	self._bloqueada = 1

    def esta_bloqueada_extremos(self):
	return self._bloqueada_extremos 

    def haz_bloqueada_extremos(self):
	self._bloqueada_extremos = 1


class palabra:
    def __init__(self, cadena, pos, orientacion):
	self.cadena = cadena
	self.pos_y  = pos[0]
	self.pos_x  = pos[1]
	self.orientacion = orientacion

    def que_cadena(self):
	return self.cadena

    def que_pos(self):
	return (self.pos_y+1, self.pos_x+1)

    def que_orientacion(self):
	return self.orientacion

class crucig:
    sumas_vecindad = [(1,1), (-1,1), (0,1),(1,-1), (1,0),
		      (-1,-1), (0,0), (0,-1), (-1,0)] 
    sumas_vecindad2 = [(1,1), (-1,1), (0,1),(1,-1), (1,0),
		       (-1,-1), (0,-1), (-1,0)] 
    def __init__(self, lista_palabras= None , lista_definiciones=None):
	self.matriz = []
	self.tesoro = lista_palabras
	self.palabras_seleccionadas = {}
	self.lista_palabras = [] # objetos palabra
	self.cruces = 0
	self.lista_definiciones = lista_definiciones
	self.ultima_situada = None
	self.pos_ultima_situada = None
	self.ultima_or = None
	self.pasos = 9
	self.pprofundidad = 4 # era 4
	for i in xrange(0,15):
	    fila = []
	    for j in xrange(0,15):
		fila.append(celda())
	    self.matriz.append(fila)

    def elige_palabra_no_elegida(self):
	p = random.choice(self.tesoro)
	if  self.palabras_seleccionadas.has_key(p):
	    return None
	return p

    def elige_situacion(self):
	return random.choice(['v','h'])

    def elige_posicion(self):
	return (random.choice(range(0,15)), random.choice(range(0,15)))

    def escribe_fichero(self, fichero):
	for i in xrange(0,15):
	    fichero.write("\n")
	    for j in xrange(0,15):
		fichero.write(self.matriz[i][j].que_letra())

    def imprime(self):
	for i in xrange(0,15):
	    print
	    for j in xrange(0,15):
		print self.matriz[i][j].que_letra(),

    def imprime_orientacion(self):
	for i in xrange(0,15):
	    print
	    for j in xrange(0,15):
		print self.matriz[i][j].que_orientacion(),

    def puede_situarse(self, pal, pos, sit):
	if self.no_cumple_tamanyo(pal, pos, sit):
	    return 0
	if self.no_cumple_vecindad(pal, pos, sit):
	    return 0
	if self.no_cumple_palabras_pis(pal, pos, sit):
	    return 0
	return 1


    def no_cumple_tamanyo(self, pal, pos, sit):
	lent = len(pal)
	if pos[1] < 0 or pos[0]< 0:
	    return 1
	if sit == 'h':
	    if lent + pos[1] >= 15:
		return 1
	if sit == 'v':
	    if lent + pos[0] >= 15:
		return 1
	return 0

    def obten_celda(self, y, x):
	if y >=15 or x >=15 or y<0 or x <0:
	    return None
	return self.matriz[y][x]

    def no_cumple_vecindad(self, pal, pos, sit):
	aviso = 0
	if sit == 'h':
	    par_sum = (0,1)
	else:
	    par_sum = (1,0)
	par_inici = pos
	ultima = len(pal) - 1
	estricto = 0
	for i in xrange(0,len(pal)):
	    #print i,pal[i], par_inici
	    for j in self.sumas_vecindad2:
		c = self.obten_celda(par_inici[0] + j[0], par_inici[1] + j[1])
		if c:
		    #print (par_inici[0] + j[0], par_inici[1] + j[1]), c.que_orientacion(), sit, aviso
		    if  c.esta_bloqueada(): return 1
		    if i == 0 and c.esta_bloqueada_extremos() and sit =="h" and j==(0,-1):
			return 1
		    if i == 0 and c.esta_bloqueada_extremos() and sit =="v" and j==(-1,0):
			return 1
		    if i == ultima and c.esta_bloqueada_extremos() and sit =="h" and j==(0,1):
			return 1
		    if i == ultima and c.esta_bloqueada_extremos() and sit =="v" and j==(1,0):
			return 1
	    par_inici = (par_inici[0] + par_sum[0], par_inici[1] + par_sum[1])
	return 0


    def crea(self, a_situar):
	t = copy.deepcopy(self)
	v = t.crea_inicial()
	while v is None:
	    t = copy.deepcopy(self)
	    v = t.crea_inicial()
	    self.tesoro = scramble(self.tesoro)
	return v

    def crea_inicial(self):
	global max_iter
	while not self.pos_palabra():
	    pass
	t = copy.deepcopy(self)
	if t.crea_cadena():
	    max_iter = const_max_iter
	    return t.crea_consecu()
	else:
	    max_iter = const_max_iter
	    return None
	#palabras_situadas = self.crea_cadena()
	#self.crea_aleatorio(palabras_situadas, 3)

    def crea_consecu(self):
	global max_iter

	if max_iter < 0:
	    return None
	self.pasos = self.pasos - 1
	if self.pasos < 0:
	    return self
	else:
	    ultima_situada = None
	    for i in xrange(0,self.pprofundidad / 2):
		print self.pasos, self.ultima_situada, self.palabras_seleccionadas
		if random.choice(xrange(0,3)): # era rand
		    if len(self.tesoro) > 120:
			self.tesoro = scramble(self.tesoro[len(self.tesoro)/2:])
		    else:
			self.tesoro = scramble(self.tesoro)
		t = copy.deepcopy(self)
		if t.pprofundidad < 10:
		    t.pprofundidad = t.pprofundidad + 1
		if t.crea_cadena():
		    if not ultima_situada:
			ultima_situada = t.ultima_situada
		    else:
			if ultima_situada == t.ultima_situada:
			    break
		    v = t.crea_consecu()
		    if v:
			return v
		max_iter = max_iter - 1
		
	    return None
	    
	

    def crea_cadena(self):
	for i in self.tesoro:
	    if  not self.palabras_seleccionadas.has_key(i):
		if self.situa_palabra_cadena(i):
		    self.tesoro.remove(i)
		    return 1
	return 0

    def situa_palabra_cadena(self, pal):
	if self.ultima_or =="h":
	    for i in xrange(0, len(self.ultima_situada)):
		for j in xrange(0, len(pal)):
		    if self.ultima_situada[i] == pal[j]:
			npos =  (self.pos_ultima_situada[0]-j, self.pos_ultima_situada[1]+i)
			if self.puede_situarse(pal, npos, "v"):
			    self.actualiza_crucigrama(pal, npos, "v")
			    return 1
	if self.ultima_or =="v":
	    for i in xrange(0, len(self.ultima_situada)):
		for j in xrange(0, len(pal)):
		    if self.ultima_situada[i] == pal[j]:
			npos =  (self.pos_ultima_situada[0]+i, self.pos_ultima_situada[1]-j)
			if self.puede_situarse(pal, npos, "h"):
			    self.actualiza_crucigrama(pal, npos, "h")
			    return 1
	return 0

    def crea_aleatorio(self, 	palabras_situadas, a_situar):
	for i in xrange(0,10000):
	    if self.pos_palabra():
		palabras_situadas = palabras_situadas + 1
	    if palabras_situadas == a_situar:
		return palabras_situadas

	return palabras_situadas
	    
    def pos_palabra(self):
	pal = None
	while pal is None:
	    pal = self.elige_palabra_no_elegida()
	pos = self.elige_posicion()
	sit = self.elige_situacion()
	if self.puede_situarse(pal, pos, sit):
	    self.actualiza_crucigrama(pal,pos,sit)
	    return 1
	return 0
	    

    def bloquea_vecinas_primera(self, sit, par_inici):
	for j in self.sumas_vecindad2:
	    if  sit =="h" and  j ==(0,-1) or \
	       sit =="v" and  j ==(-1,0):		
		c = self.obten_celda(par_inici[0] + j[0], par_inici[1] + j[1])
		if c:
		    c.haz_bloqueada()

    def bloquea_vecinas_ultima(self, sit, par_inici):
	for j in self.sumas_vecindad2:
	    if  sit =="h" and  j == (0,1) or \
	         sit =="v" and  j == (1,0):

		c = self.obten_celda(par_inici[0] + j[0], par_inici[1] + j[1])
		if c:
		    c.haz_bloqueada()


    def actualiza_crucigrama(self, pal, pos, sit):
	if sit == 'h':
	    par_sum = (0,1)
	else:
	    par_sum = (1,0)
	par_inici = pos
	ultima = len(pal) - 1 
	for i in xrange(0,len(pal)):
	    #print i,pal[i], par_inici
	    if i == 0:
		self.bloquea_vecinas_primera(sit, par_inici)
	    if i == ultima:
		self.bloquea_vecinas_ultima(sit, par_inici)
	    c = self.obten_celda(par_inici[0], par_inici[1])
	    c.haz_bloqueada_extremos()
	    if c.que_letra() != "-":
		self.cruces = self.cruces + 1
	    c.haz_letra(pal[i])
	    c.haz_orientacion(sit)
	    par_inici = (par_inici[0] + par_sum[0], par_inici[1] + par_sum[1])
	self.palabras_seleccionadas[pal ] = 1
	#print pal
	self.lista_palabras.append(palabra(pal, pos, sit))
	self.ultima_situada = pal
	self.pos_ultima_situada = pos
	self.ultima_or = sit
	    
    def no_cumple_palabras_pis(self, pal, pos, sit):

	if sit == 'h':
	    par_sum = (0,1)
	else:
	    par_sum = (1,0)
	par_inici = pos
	ultima = len(pal) -1
	for i in xrange(0,len(pal)):
	    #print i,pal[i], par_inici
	    c = self.obten_celda(par_inici[0], par_inici[1])
	    l = c.que_letra()	    
	    if  l!="-" and l!=pal[i]:
		return 1
	    if i == ultima:
		c.haz_ultima()
	    par_inici = (par_inici[0] + par_sum[0], par_inici[1] + par_sum[1])
	return 0
    def imprime_lista_palabras(self):
	print
	for i in self.lista_palabras:
	    print i.que_pos(),
	    if i.que_orientacion() == "h":
		print "ACROSS",
	    else:
		print "DOWN",
	    print i.que_cadena()
	    #print i.que_definicion()

    def imprime_def_y_lista_palabras(self):
	pals = []
	print
	for i in self.lista_palabras:
	    print " \"",i.que_pos(),
	    if i.que_orientacion() == "h":
		print "ACROSS",
	    else:
		print "DOWN",
	    print self.lista_definiciones[i.que_cadena()].que_defi(),"\""
	    pals.append(i.que_cadena())
	    #print i.que_definicion()
	for i in pals:
	    print i

    def ordena_lista_palabras(self):
	self.lista_palabras.sort(funcion_ord)

    def escribe_fichero(self, fichero):
	fichero.write("&")
	for i in xrange(0,15):
	    fichero.write("\n")
	    for j in xrange(0,15):
		fichero.write(self.matriz[i][j].que_letra())
	fichero.write("\n&\n")

    def escribe_def_y_lista_palabras(self, fichero):
	pals = []
	fichero.write("\n#\n")
	for i in self.lista_palabras:
	    fichero.write(" \"" + str(i.que_pos()))
	    if i.que_orientacion() == "h":
		fichero.write(" ACROSS ")
	    else:
		fichero.write(" DOWN ")
	    fichero.write( self.lista_definiciones[i.que_cadena()].que_defi()+ "\"\n")
	    pals.append(i.que_cadena())
	    #print i.que_definicion()
	fichero.write("#\n$\n")
	for i in pals:
	    fichero.write(i+"\n")
	fichero.write("$\n")

def funcion_ord(a,b):
    if a.que_orientacion()=="h" and b.que_orientacion()=="v":
	return 1
    if a.que_orientacion()=="v" and b.que_orientacion()=="h":
	return 0
    return a.que_pos() > b.que_pos()

def un_cruci():
    lista_palabras = ['caos', 'confusion', 'desorden',
		  'transtorno', 'desconcierto', 'lio',
		  'embrollo', 'incoherencia',
		  'orden', 'claridad',
		  'coherencia', 'disciplina',
		  'capa', 'baņo', 'mano',
		  'revestimiento', 'carantoņa', 'halago',
		  'caricia', 'zalameria', 'gateria',
		  'embeleco', 'arrumaco', 'mimo',
		  'zalema', 'lagoteria', 'insulto',
		  'brusquedad', 'solfa', 'aereo',
		  'volatil', 'fondo', 'medio',
		  'lloro', 'risa', 'zorro',
		  'picaro', 'chiripa', 'gracia',
		  'malaje', 'pena', 'pesar', 'viejo']

    try:
	f = open("/usr/dict/words")
	l = f.readlines()
	f.close()
    except:
	pass
    h = 0
    l = lista_palabras
    lista_palabras2 = []
    for i in l:
	h = h + 1
	#if h % 8 == 0:
	lista_palabras2.append(i) #([:-1])
	if h>5000:
	    break
    t = crucig(scramble(lista_palabras2))
    t =  t.crea(21)
    #print t.elige_palabra_no_elegida()
    t.imprime()
    t.ordena_lista_palabras()
    t.imprime_lista_palabras()
    print t.cruces

def scramble(lista):
    lu = []
    for i in lista:
	lu.append((random.random(), i))  # era rand
    lu.sort()
    li = []
    for j in lu:
	li.append(j[1])
    return li

if __name__=='__main__':
    for i in xrange(0,1):
	un_cruci()