921 - A Word Puzzle in the Sunny Mountains

All about problems in Volume 9. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
Jenny_triguina
New poster
Posts: 3
Joined: Sun Jun 10, 2012 7:50 pm

921 - A Word Puzzle in the Sunny Mountains

Post by Jenny_triguina » Sun Jun 10, 2012 7:56 pm

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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: Algoritmo problema 921

Post by brianfry713 » Tue Jun 12, 2012 12:00 am

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.
Check input and AC output for thousands of problems on uDebug!

Jenny_triguina
New poster
Posts: 3
Joined: Sun Jun 10, 2012 7:50 pm

Re: Algoritmo problema 921

Post by Jenny_triguina » Tue Jun 12, 2012 10:37 pm

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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: Algoritmo problema 921

Post by brianfry713 » Tue Jun 12, 2012 11:17 pm

I don't really understand your question after passing it through Google translate. Try studying backtracking algorithms.
Check input and AC output for thousands of problems on uDebug!

Jenny_triguina
New poster
Posts: 3
Joined: Sun Jun 10, 2012 7:50 pm

Re: Algoritmo problema 921

Post by Jenny_triguina » Tue Jun 12, 2012 11:39 pm

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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: Algoritmo problema 921

Post by brianfry713 » Wed Jun 13, 2012 11:17 pm

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.
Check input and AC output for thousands of problems on uDebug!

Post Reply

Return to “Volume 9 (900-999)”