The Word Puzzle Problem (writing a program to solve word puzzles)

[mario99]

Write a program to solve the word puzzle problem.

u n i v e r s i t y

n k z l n i u f r e

i m q a g z z j l a

t v b n d t p e g r


I found
horizontally: university

vertically: year and unit

diagonally: sign

There could be more than what I found. Now, I have to write a program using any programming language to solve this problem. The idea is basically to make the program to find the words that I have already found, university, unit, year, and sign.

My idea is to create an array that will hold the letters and another array that will hold the four words. Then, I will create a loop to walk through all the elements in the first array by combining the letters as words, then compare them with the second array.

It is easy to write a code to find the words written horizontally like university, but I cannot find a way to write a code to find the words written vertically and diagonally.

 

[BigBeachBanana]

I would put the word puzzle in a matrix and access the elements similar to how you call elements of a matrix [imath]a_{11}, a_{12},...[/imath]

 

[Bruce]

ye us it it an an is is in in in tin nit nab ban peg rev yea sit ear

 

[mario99]

I would put the word puzzle in a matrix and access the elements similar to how you call elements of a matrix [imath]a_{11}, a_{12},...[/imath]

Thank you BigBeachBanana


letters = [imath]\displaystyle \begin{bmatrix}u & n & i & v & e & r & s & i & t & y \\n & k & z & l & n & i & u & f & r & e \\i & m & q & a & g & z & z & j & l & a \\t & v & b & n & d & t & p & e & g & r \end{bmatrix}[/imath]


What is next?

ye us it it an an is is in in in tin nit nab ban peg rev yea sit ear

Thank you Bruce


I will omit the repetition.

1. university
2. unit
3. year
4. sign
5. ye
6. us
7. it
8. an
9. is
10. in
11. tin
12. nit
13. nab
14. ban
15. peg
16. rev
17. yea
18. sit
19. ear

 

[BigBeachBanana]

Thank you BigBeachBanana


letters = [imath]\displaystyle \begin{bmatrix}u & n & i & v & e & r & s & i & t & y \\n & k & z & l & n & i & u & f & r & e \\i & m & q & a & g & z & z & j & l & a \\t & v & b & n & d & t & p & e & g & r \end{bmatrix}[/imath]


What is next?




Thank you Bruce


I will omit the repetition.

1. university
2. unit
3. year
4. sign
5. ye
6. us
7. it
8. an
9. is
10. in
11. tin
12. nit
13. nab
14. ban
15. peg
16. rev
17. yea
18. sit
19. ear

I don't know what you're expecting the code to return?

 

[lev888]

My approach:

1. Find or write a function that finds substring A in a string B reading left to right or right to left. Let's call it find_substring.

2. Write a function that looks for your words in a given string. Let's call it find_words. It will use find_substring.

3. Top level function:
For each row: put the row into a string, call find_words.
For each column: put the column into a string, call find_words.
For each bottom left to top right diagonal: put the diagonal into a string, call find_words.
For each top left to bottom right diagonal: put the diagonal into a string, call find_words.

Edit: obviously the first step in the top level function is to read the puzzle into a 2D array.

 

[BigBeachBanana]

2. Write a function that looks for your words in a given string.

If you already know the words you're looking then what's the point of the code?

 

[lev888]

If you already know the words you're looking then what's the point of the code?

Per OP: "The idea is basically to make the program to find the words that I have already found, university, unit, year, and sign."

 

[BigBeachBanana]

Per OP: "The idea is basically to make the program to find the words that I have already found, university, unit, year, and sign."

What would the code return? The location of the word?

My interpretation of the question is to write the code to return these words. It's also apparent that those words the OP found are not exhaustive. Those are just some that s/he found.

My question to @mario99 : how would the code know it found a word? Unless you give it a dictionary to check against.

 

[Dr.Peterson]

What would the code return? The location of the word?

My interpretation of the question is to write the code to return these words. It's also apparent that those words the OP found are not exhaustive. Those are just some that s/he found.

My question to @mario99 : how would the code know it found a word? Unless you give it a dictionary to check against.

I think the intent is to solve the sort of "word search" puzzle in which you are given a letter square, and a list of words to find in it. You "solve" it by circling the words in place. Like here:

Free Printable African Animals Word Search

Fun printable worksheet for students of all ages features 39 african animals to hunt down.

www.puzzles-to-print.com

So, yes, it presumably has to return the location of each word, in some form; and the words to find will not be exhaustive -- you are, in essence, given a (very small) dictionary.

Am I right? Of course, I don't see how this is a math problem.

 

[BigBeachBanana]

I think the intent is to solve the sort of "word search" puzzle in which you are given a letter square, and a list of words to find in it. You "solve" it by circling the words in place. Like here:

Free Printable African Animals Word Search

Fun printable worksheet for students of all ages features 39 african animals to hunt down.

www.puzzles-to-print.com

So, yes, it presumably has to return the location of each word, in some form; and the words to find will not be exhaustive -- you are, in essence, given a (very small) dictionary.

Am I right? Of course, I don't see how this is a math problem.

When doing a word-search puzzle, you'd need to return 2 things: (1) the word it found and (2) the location of the word.
I'm questioning the OP about the first requirement. Without doing the word search by hand first (because this defeats the purpose of automation), how are you expecting the code to return the requirement (1)?

For example, how would it know "in", a real English word, vs "ni"?

The OP seems to be doing requirement (1) by hand, then using those as inputs to find requirement (2).

It's 100% not a math question, just want to make sure the OP understands the necessary requirements for doing this assignment.

 

[Dr.Peterson]

What we need to see is the actual wording of the assignment, assuming that's what this is. The OP might be misunderstanding it.

If it's as I am assuming, then he is just giving an example he's made up. The puzzle constructor makes both the square and the word list (and probably the latter comes first, contrary to what he's said).

If all he was given was the square, then you are right.

 

[mario99]

I don't know what you're expecting the code to return?

I expect the code to return: university was found, for example.

My approach:

1. Find or write a function that finds substring A in a string B reading left to right or right to left. Let's call it find_substring.

2. Write a function that looks for your words in a given string. Let's call it find_words. It will use find_substring.

3. Top level function:
For each row: put the row into a string, call find_words.
For each column: put the column into a string, call find_words.
For each bottom left to top right diagonal: put the diagonal into a string, call find_words.
For each top left to bottom right diagonal: put the diagonal into a string, call find_words.

Edit: obviously the first step in the top level function is to read the puzzle into a 2D array.

Thank you lev888.


1. Do you mean that I have to create 4 horizontal strings, 10 vertical strings, and 26 diagonal strings? Then find_substring will go through all 40 strings to find the required words?

What I mean here is that, for example, we have two diagonal strings for sign, one is "sign" from top to bottom and one is "ngis" from bottom to top. Does the job of find_substring to check "n", "ng", "ngi", and "ngis"? Then, it will check the reverse which is "s", "si", "sig", and "sign". Then it will say sign was found. Is that what you mean by the function find_substring?

By the way the two diagonal strings "sign" and "ngis" are just two diagonal strings out of 26.

2. If this is the purpose of the function find_substring, I don't see a reason to create the function find_words because I can directly compare what the function find_substring found with the words that I have found, university, unit, year, and sign.

3. I have done this step in 1.

Edit: obviously the first step in the top level function is to read the puzzle into a 2D array.

The matrix that I have created in my post #4 can be stored in a 2D array where the first element, 00, for example, can be found by two loops which have the indices i = 0, and j = 0 in the first round, respectively.

In this way, I can check element by element while walking horizontally in the array by concatenating letters together to make words. This job can be done easily for the horizontal words, but I cannot make the loops to walk vertically or diagonally.

What would the code return? The location of the word?

My interpretation of the question is to write the code to return these words. It's also apparent that those words the OP found are not exhaustive. Those are just some that s/he found.

My question to @mario99 : how would the code know it found a word? Unless you give it a dictionary to check against.

The location is important, but we don't have to mention it. The purpose is so far just to find the word in that location and say it was found. The words which I have found are the dictionary to check against.

I think the intent is to solve the sort of "word search" puzzle in which you are given a letter square, and a list of words to find in it. You "solve" it by circling the words in place. Like here:

Free Printable African Animals Word Search

Fun printable worksheet for students of all ages features 39 african animals to hunt down.

www.puzzles-to-print.com

So, yes, it presumably has to return the location of each word, in some form; and the words to find will not be exhaustive -- you are, in essence, given a (very small) dictionary.

Am I right? Of course, I don't see how this is a math problem.

Thank you Dr.Peterson


You are exactly correct. The main purpose is "word search". In reality, we want the code to solve the puzzle itself by giving it a real dictionary which probably contains all the words in the world which seems it will take a lot of time to find a single word. Therefore, the second purpose of this code is performance. I will make a code and John smith will make another code. The fastest code to find the words wins. For example, at first trial, I may make a code which can find the words in 40 seconds. I have extra trials to improve the performance. Improving the algorithm in a smart way will speed up the searching process.

The real challenge is that, is it possible to create an algorithm to solve the puzzle in 1 second? This is what the instructor said, we would be surprised in chapter 10 that our algorithm would be developed in such a way that it would able to solve a real word puzzle in no time. I can't wait to see that!

Am I right? Of course, I don't see how this is a math problem.

I don't know what to say here. But the instructor once said, if you know math, you can create a code of 2 lines, while another code with the same purpose done by another person without the knowledge of math can cost 10s of lines. Therefore, it is a math problem indirectly.

When doing a word-search puzzle, you'd need to return 2 things: (1) the word it found and (2) the location of the word.
I'm questioning the OP about the first requirement. Without doing the word search by hand first (because this defeats the purpose of automation), how are you expecting the code to return the requirement (1)?

For example, how would it know "in", a real English word, vs "ni"?

The OP seems to be doing requirement (1) by hand, then using those as inputs to find requirement (2).

It's 100% not a math question, just want to make sure the OP understands the necessary requirements for doing this assignment.

I agree that solving the problem in the way I explained in post #1 defeats the purpose of automation. The funny thing is what I explained was the purpose of the code. I have explained to you what the instructor had explained to us.

I am afraid that I will get zero mark if I solved the word puzzle problem by searching in a real dictionary instead of the small dictionary that I have created. If you think that the instructor has interrupted the problem in a faulty way, feel free to share the correctness with me to share it with him. Otherwise, let us just surrender to the instructor call.

What we need to see is the actual wording of the assignment, assuming that's what this is. The OP might be misunderstanding it.

If it's as I am assuming, then he is just giving an example he's made up. The puzzle constructor makes both the square and the word list (and probably the latter comes first, contrary to what he's said).

If all he was given was the square, then you are right.

I wish if I have made this up.

 

[Dr.Peterson]

You are exactly correct. The main purpose is "word search". In reality, we want the code to solve the puzzle itself by giving it a real dictionary which probably contains all the words in the world which seems it will take a lot of time to find a single word.

You are contradicting yourself. My suggestion was that a list of words is given, not that you have to find any words at all, and need a dictionary of your own. If you are looking for any words at all, then it is not the traditional word search puzzle that i referred to.

The real challenge is that, is it possible to create an algorithm to solve the puzzle in 1 second? This is what the instructor said, we would be surprised in chapter 10 that our algorithm would be developed in such a way that it would able to solve a real word puzzle in no time. I can't wait to see that!

I don't know what to say here. But the instructor once said, if you know math, you can create a code of 2 lines, while another code with the same purpose done by another person without the knowledge of math can cost 10s of lines. Therefore, it is a math problem indirectly.

Why didn't you tell us this context in the first place? It's important to know your goals. But what kinds of math are you learning, or expecting to learn, in this class, that is relevant? That will be even more helpful.

But also, you still haven't shown us the actual wording of the assignment, which I asked for:

What we need to see is the actual wording of the assignment, assuming that's what this is. The OP might be misunderstanding it.

The funny thing is what I explained was the purpose of the code. I have explained to you what the instructor had explained to us.

I very much doubt this. We can't be sure without seeing exactly what you were told.

The location is important, but we don't have to mention it. The purpose is so far just to find the word in that location and say it was found. The words which I have found are the dictionary to check against.

If you are just to check against the list of words you know are there, and say yes or no, then your code just has to print "yes" for every word! The challenge has to be to actually find where the word is.

If you are to find any words at all, then listing those could be a valid result. But it would not be a typical "real world problem", and could take a very long time with a very large dictionary.

Again, you are contradicting yourself. We absolutely need to see the actual assignment.

Now, working out an efficient algorithm is a separate issue, which may or may not involve what I think of as math (as opposed to the study of algorithms). There are many possible algorithms; which is best will depend in part on how large the dictionary is.

I wish if I have made this up.

You say this in response to my comment,

If it's as I am assuming, then he is just giving an example he's made up.

I was not talking about the entire assignment, but the particular square you show, along with your word list. I was suggesting that your program would be given both a square and a word list.

I don't think you understand what I was saying.

 

[lev888]

Thank you lev888.


1. Do you mean that I have to create 4 horizontal strings, 10 vertical strings, and 26 diagonal strings? Then find_substring will go through all 40 strings to find the required words?

What I mean here is that, for example, we have two diagonal strings for sign, one is "sign" from top to bottom and one is "ngis" from bottom to top. Does the job of find_substring to check "n", "ng", "ngi", and "ngis"? Then, it will check the reverse which is "s", "si", "sig", and "sign". Then it will say sign was found. Is that what you mean by the function find_substring?

By the way the two diagonal strings "sign" and "ngis" are just two diagonal strings out of 26.

2. If this is the purpose of the function find_substring, I don't see a reason to create the function find_words because I can directly compare what the function find_substring found with the words that I have found, university, unit, year, and sign.

3. I have done this step in 1.


The matrix that I have created in my post #4 can be stored in a 2D array where the first element, 00, for example, can be found by two loops which have the indices i = 0, and j = 0 in the first round, respectively.

In this way, I can check element by element while walking horizontally in the array by concatenating letters together to make words. This job can be done easily for the horizontal words, but I cannot make the loops to walk vertically or diagonally.

1. You can create all strings first then do the search. Or you can do the search as you create each string.
Yes, the job of the string search function is to check in both directions. Or you can create a reversed string for every string and then the search string function will only need to search in one direction. There are many ways to structure the code.

2. Again, there are many ways to structure the code. I gave you just one example. I prefer creating additional lower level functions compared to doing too much stuff in the upper level functions.

Traversing a 2D array vertically is JUST AS EASY as horizontally. It seems you didn't do enough coding exercises with arrays.
You have an array with elements Aij. To do the horizontal traversal your outside loop will change i, your inside loop will change j.
Vertical: the other way around.

Diagonals are more complicated. Think about it. List all diagonals and see if you notice a pattern which can be used to set up your loops.

 

[mario99]

You are contradicting yourself. My suggestion was that a list of words is given, not that you have to find any words at all, and need a dictionary of your own. If you are looking for any words at all, then it is not the traditional word search puzzle that i referred to.

I am sorry Dr.Peterson if I misunderstood you. I will be more clear now. To make a program to solve the word puzzle problem, we must have a list of words. This list is not given to us. We have to create it. The instructor has told us that we don't have to create a list of all the words in the letter square. We have to create a list that contains at least 1 horizontal word, at least 1 vertical word, and at least 1 diagonal word. This is why I stopped searching for words when I got the words, university, unit, year, and sign. I have included two vertical words which was not necessary. I have done that just because it was clear that the two ends have vertical words. Thanks to Bruce who found the rest of the words. I thanked him instead of telling him what he has found was not necessary.

The goal of the puzzle is to demonstrate the idea of searching using nested loops. Therefore, when you said "word search", letter square, and a list, I said that Dr.Peterson, you are exactly correct.

The exact wording of the problem was: Solve the Word Puzzle Problem. There was no extra explanation until we have gained more information from the instructor.

While we were discussing this problem with the instructor, he told us that this problem along with some other problems will be developed in the next chapters that we would get surprised that a real Word Puzzle Problem without a list can be solved in 1 second by searching in a real dictionary which contains all the words in the world. I don't care if this is true or not.

Regarding math. We have used simple algebra so far. Only 1 time, the instructor has discussed algorithm of Fibonacci Triangle.

By the way, the letter square in post #1 was written by the instructor in the class.

I hope that I was fully clear and have answered all of your questions in this post. Let me know if I am still misunderstanding you.

1. You can create all strings first then do the search. Or you can do the search as you create each string.
Yes, the job of the string search function is to check in both directions. Or you can create a reversed string for every string and then the search string function will only need to search in one direction. There are many ways to structure the code.

2. Again, there are many ways to structure the code. I gave you just one example. I prefer creating additional lower level functions compared to doing too much stuff in the upper level functions.

Traversing a 2D array vertically is JUST AS EASY as horizontally. It seems you didn't do enough coding exercises with arrays.
You have an array with elements Aij. To do the horizontal traversal your outside loop will change i, your inside loop will change j.
Vertical: the other way around.

Diagonals are more complicated. Think about it. List all diagonals and see if you notice a pattern which can be used to set up your loops.

Thanks lev888.

I have worked a lot of time in demonstrating the nested loops in the last few days, and got it worked pretty good in the vertical searching as well. I have done the diagonal searching partially. I mean that it sometimes finds the word correctly and other times not correctly when I change the word location. I am having a little problem in the loops indices and I feel that I will be able to fix the problem soon. I also found a built-in function that returns the reverse of the word letters which saved me a lot of time to shorten the code.

I have also looked at codes which were done on similar problems and got some ideas (one of them is the built-in function that reverse the word letters). It is difficult to understand everything in their codes, but copying and testing their codes in my compiler gave me fascinating results.

For now, I will take your advise to focus on lower level functions. I am thinking of creating a lot of functions, each function does only one task. If I have seen that my code is very long, I would have to combine some together. Since the instructor has told us to code anything we like to solve the problem, I would not care a lot about the performance in the first trial.

 

[lev888]

I have worked a lot of time in demonstrating the nested loops in the last few days, and got it worked pretty good in the vertical searching as well. I have done the diagonal searching partially. I mean that it sometimes finds the word correctly and other times not correctly when I change the word location. I am having a little problem in the loops indices and I feel that I will be able to fix the problem soon.

Great, looks like you are going in the right direction. Regarding the code not working correctly, do you use a debugger? Or at least output some diagnostic info? E.g. if you output each diagonal as you set them up, you'll see whether some are missed.

 

[mario99]

Great, looks like you are going in the right direction. Regarding the code not working correctly, do you use a debugger? Or at least output some diagnostic info? E.g. if you output each diagonal as you set them up, you'll see whether some are missed.

Thanks a lot lev888.

The Puzzle has been solved successfully.

 

[davissgurban]

I am sorry Dr.Peterson if I misunderstood you. I will be more clear now. To make a program to solve the word puzzle problem, we must have a list of words. This list is not given to us. We have to create it. The instructor has told us that we don't have to create a list of all the words in the letter square. We have to create a list that contains at least 1 horizontal word, at least 1 vertical word, and at least 1 diagonal word. This is why I stopped searching for words when I got the words, university, unit, year, and sign. I have included two vertical words which was not necessary. I have done that just because it was clear that the two ends have vertical words. Thanks to Bruce who found the rest of the words. I thanked him instead of telling him what he has found was not necessary.

The goal of the puzzle is to demonstrate the idea of searching using nested loops. Therefore, when you said "word search", letter square, and a list, I said that Dr.Peterson, you are exactly correct.

The exact wording of the problem was: Solve the Word Puzzle Problem. There was no extra explanation until we have gained more information from the instructor.

While we were discussing this problem with the instructor, he told us that this problem along with some other problems will be developed in the next chapters that we would get surprised that a real Word Puzzle Problem without a list can be solved in 1 second by searching in a real dictionary which contains all the words in the world. I don't care if this is true or not.

Regarding math. We have used simple algebra so far. Only 1 time, the instructor has discussed algorithm of Fibonacci Triangle.

By the way, the letter square in post #1 was written by the instructor in the class.

I hope that I was fully clear and have answered all of your questions in this post. Let me know if I am still misunderstanding you.



Thanks lev888.

I have worked a lot of time in demonstrating the nested loops in the last few days, and got it worked pretty good in the vertical searching as well. I have done the diagonal searching partially. I mean that it sometimes finds the word correctly and other times not correctly when I change the word location. I am having a little problem in the loops indices and I feel that I will be able to fix the problem soon. I also found a built-in function that returns the reverse of the word letters which saved me a lot of time to shorten the code.

I have also looked at codes which were done on similar problems and got some ideas (one of them is the built-in function that reverse the word letters). It is difficult to understand everything in their codes, but copying and testing their codes in my compiler gave me fascinating results. Brace yourself for an adventure that sends shivers down your spine! Explore more bone-chilling tales on creepypasta.com if you dare. As you navigate the eerie streets and abandoned buildings, be prepared to confront the unknown.

For now, I will take your advise to focus on lower level functions. I am thinking of creating a lot of functions, each function does only one task. If I have seen that my code is very long, I would have to combine some together. Since the instructor has told us to code anything we like to solve the problem, I would not care a lot about the performance in the first trial.

Well, it is very important not to be shy to ask questions, only in this case it is possible to learn something

 

[mario99]

Well, it is very important not to be shy to ask questions, only in this case it is possible to learn something

There is a difference between being shy and being polite. I was polite.