Juego de ingenio!

[jotabin]

[jotabin]

en un primer análisis, yo llegué a la conclusión de que es imposible ocupar menos de 21 casillas

y después de dedicarle demasiado tiempo, llegué a una solución con 24 mugrosas casillitas

estoy casi seguro de que se puede hacer usando menos... 21 me pareció que era imposible, pero 22 creo firmemente que se tiene que poder.

en fin... más les vale tener preparada una buena respuesta antes del sábado, o vayan despidiéndose de su amiguito:



ñaca ñaca n

[Gespi]

np sé, yo qiero q vuelva qxjis

[Piluex]

Puedo bruteforcear la respuesta si quieren. Me parece al pedo pensarlo, la pc probablemente lo saque en un tiempo aceptable.

[Piluex]

Numero total de letras diferentes: 15
Repeteciones de las letras (totales, max en una palabra, palabra):
"U": 4, 1, UM
"M": 1, 1, UM
"D": 4, 1, DOIS
"O": 9, 2, OITO
"I": 6, 1, DOIS
"S": 8, 3, DEZESSEIS
"T": 6, 1, TRES
"R": 4, 1, TRES
"E": 15, 3, DEZESSEIS
"Q": 3, 1, QUATRO
"A": 2, 1, QUATRO
"C": 2, 2, CINCO
"N": 4, 1, CINCO
"V": 1, 1, NOVE
"Z": 7, 1, DEZ
Mínimo de casilleros a usar: 21

Es un super requete NP, pero para este tamaño de datos, con suerte, optimizaciones y bleh creo q se puede llegar a sacar igual.

[Piluex]

Son las 3:30 am, mañana en el trabajo sigo con mi proyectín, es divertido.

[Bleu]

jauaj piluex acaba de destrozar todas las barreras de mi conocimiento en un solo post, que carajo hiciste?

Nota: son las 6.30 AM

[jotabin]

puso, para cada letra:
[a] las cantidad de veces que aparece en total en todas las palabras
[b] la mínima cantidad de veces que va a tener que aparecer la letra en la cuadrícula
[c] la palabra que da lugar a [b]

yo hice exactamente lo mismo antes de "empezar" a intentar resolver el problema
hasta lo puse en columnas en el mismo orden =o

[jotabin]

btw, si a alguno se le ocurre un lindo método para encarar el problema, la verdad que me interesa mucho más que que me tiren la "solución &#243tima"

pero bueno, la solución también me puede servir mucho y es bienvenida

y Piluex, espero ansioso los resultados de tu experimento, aún cuando vinieran etiquetados de "reporte de fracaso " me interesa saber cómo te fue.

[MoaLaiSkirulais]

existen muchos solvers de boggles online.... y no creo q sean absolutamente x f bruta....

[Piluex]

Es diferente, esos buscan palabras nada más, esto es una optimización.

Obvio que no voy a aplicar fuerza bruta bruta "plana";

Suponiendo que haya una ubicación "fixed" de los casilleros no utilizados que sea &#243tima y maximize nuestras posibilidades (osea, podamos hacer mayor cantidad de combinaciones). Necesitariamos 21 lugares, y los otros ya no aparecen en el cuadrito.

En ese caso hay:
(15^6) * (15 !) = 1.48952283 * 10^19
Posibles combinaciones (a lo bruto).

suponiendo supervelocidad de busqueda de palabras y armado de puzzles podriamos buscar no más de 10^7 combinaciones por segundo el tiempo estimado de nuestra búsqueda sería:
((((((15^6) * (15 !)) / (10^7)) / 60) / 60) / 24) / 365 ~ 47232 Años.

Obviamente ese es el peor caso si hay una solucion y es la última que probemos, osea, el tiempo está entre 1 segundo y 47232 años.


Por suerte ya se varias formas de buscar la solucion sin probar tantas combinaciones, aunque antes voy a tratar de demostrar que no es posible formarlo (aunque creo que se puede) para establecer un par de pautas de búsqueda.

[Piluex]

Numero total de letras diferentes: 15
Repeteciones de las letras (totales, max en una palabra, palabras, letras combinadas):
"U": 4, 1, UM, QUATRO, QUATORZE, QUINZE, "M", "Q", "A", "I"
"M": 1, 1, UM, "U"
"D": 4, 1, DOIS, DEZ, DOZE, DEZESSEIS, "O", "E"
"O": 9, 2, OITO, QUATRO, CINCO, NOVE, ONZE, DOZE, QUATORZE, "D", "I", "R", "C", "T", "N", "V", "Z"
"I": 6, 1, DOIS, CINCO, SEIS, OITO, QUINZE, DEZESSEIS, "O", "S", "C", "N", "E", "T", "U"
"S": 8, 3, DEZESSEIS, TRES, SETE, "I", "E", "S"
"T": 6, 1, TRES, QUATRO, SETE, OITO, TREZE, QUATORZE, "R", "A", "E", "E", "I", "O"
"R": 4, 1, TRES, QUATRO, TREZE, QUATORZE, "T", "E", "O", "Z"
"E": 15, 3, DEZESSEIS, SEIS, NOVE, DEZ, ONZE, DOZE, TREZE, QUATORZE, QUINZE, "R", "S", "I", "T", "V", "D", "Z"
"Q": 3, 1, QUATRO, QUATORZE, QUINZE, "U"
"A": 2, 1, QUATRO, QUATORZE, "U", "T"
"C": 2, 2, CINCO, "I", "N", "O"
"N": 4, 1, CINCO, NOVE, ONZE, QUINZE, "I", "C", "O", "Z"
"V": 1, 1, NOVE, "O", "E"
"Z": 7, 1, DEZ, ONZE, DOZE, TREZE, QUATORZE, QUINZE, DEZESSEIS, "E", "N", "O", "E", "R"
Mínimo de casilleros a usar: 21

Buep, nada, las letras al final son las letras con las que esa letra tendría que combinar para formar todas las palabras que la involucran, aparentemente viendolo desde ese punto de vista no hay letras con 8 o más de 8 letras que combinen, y en la mejor pocisión de un cuadradito tenemos 8 lugares "que tocan". Parece posible, ahora voy a hacer combinaciones de 2 niveles, osea, "a toca con b, a toca con c,d y e tambien, y b toca con f,g y h" pero a simple vista tampoco habría problemas con eso.

Tips:
la letra "I" tiene que contactarse con 7 letras (casi al límite) no puede estar en un borde.
la letra "T" tiene 6, tampoco puede estar en un borde (menos en un tipo de borde raro que probablemente quede, que no voy a explicar ahora).
La letra "O" tiene 8, pero tiene que aparecer 2 veces y puede estar a 2 casilleros de distancia.

Tops:
no me digan "uh la letra E está repetida cuando revisas la letra Z y la T" porque es OBVIO que tiene que estar repetida. (Y me llevo un tiempito hacer que el programa responda eso)



Hacerlo mentalmente no parece tan difícil, pasa que no tiene gracia para mi, lo divertido es hacer un programa que pueda hacerlo todas las veces que quiera haciendo un procedimiento concreto que lo lleve al éxito en un tiempo razonable.

[jotabin]

te aseguro que hacerlo mentalmente tiene bastante gracia jauja

[Piluex]

Juajuaj si se lo mezcla un poco creo que se lo puede dejar como grafos. xDD.

[jotabin]

yo tratando de resolverlo en papel usé una notación medio extraña que hacía que parecía que estaba jugando con grafos... pero no, eran simplemente letras de mierda unidas por flechitas n