Algoritmo problema 921

[Jenny_triguina]

Buenas tardes:
Somos unos estudiantes de la uiniversidad de Leon, nos han mandado resolver el problem 921 y teniamos un algoritmo que hace unos dias nos dijo nuestro profesor que era erroneo, y ademas lo tenemos que programar en Scheme, estamos bloqueados y no sabemos como resolverlo, y lo mas importante tenemos el examen el miercoles y lo tendriamos que tener resuelto para el martes, alguien nos puede ayudar?

[brianfry713]

I solved it using recursive backtracking in C. Start by matching the letters in the seed to the first encrypted word. Then for each encrypted word of the correct length, test if it can work given the current set of numbers matched to letters. If it can, match the numbers to the letters. If you get stuck, try the next encrypted word.

[Jenny_triguina]

Muchas Gracias; pero el problema viene que con la longitud correcto puede dar lugar a que hay dos posibilidades de codificacion para el algoritmo generico, quiza no en este problema pero nos solicitan para cualquier problema y no sabemos si escogemos unos y luego no es el correcto porque palabras posteriores no estan en el diccionario como deshacer y que las siguientes codificaciones sean correctas si por ejemplo cada una de las palabras que quedan por codficicar tiene 3 posibilidades, porque serian unas 27 combinaciopnes, (alomejor algunas menos porque se pueden reducir segun codificaciones ) pero no sabemos como implementar eso y sobre todo en Scheme, si alguien tiene alguna idea mas...

Muchas gracias por la ayuda!

[brianfry713]

I don't really understand your question after passing it through Google translate. Try studying backtracking algorithms.

[Jenny_triguina]

Nosotros con la semilla descodificamos los digitos que podemos, tras esa descodificacion, hay plantillas de palabras en las que se podria poner dos palabras diferentes como por ejemplo PORTA Y HORTA (que con la codificacion nos quedaria *OR*A y *OR*A) si la siguiente codificacion es PORTA por ejemplo y por error se coge HORTA no sabemos como volver atras y cambiarlo si cuando identificamos el error es al final del algoritmo, sobre todo porque co lapiz y papel parece sencillo pero la programacion en SCHEME es complicada

No se si me he espresado mejor!
Muchas gracias por su ayuda!

[brianfry713]

Read a programming book or website describing recursive backtracking. If you don't want to use recursion, you can do the same thing with a stack instead.

Try to work it out first on paper step by step and then coding that algorithm.
The seed ADORNO=1 2 3 4 5 3, so A=1 D=2 O=3 R=4 N=5
Now I call my recursive function with position=1, meaning I am trying to find a match for 1 5 1 or ANA, this passes so I move to position=2, trying to find a match for 1 6 3 4 or A * O R and find AMOR and set M=6. Next on position 3 checking 7 3 4 8 1 or * O R * A, as I go through the list the first match is HORTA, so I will set 7=H and 8=T, this turns out to be correct but if it wasn't and a later position failed I would backtrack and try PORTA.