Optimal 4 Word Placement Inside Arbitrarily Sized Grid [duplicate]

Question

Problem statement:

Given four words, place them inside a m x n grid of squares such that the area of the grid is as small as possible.

Words must run from left to right and from top to bottom inside the grid. Letters may overlap, but additional words cannot be formed. All words have to be linked to each other in one giant chain.

Example grids that can be formed with the 4 words "one,two,three, and four." Note the last grid is the most optimized.

I'm trying to learn python and I thought this would be a good application to cut my teeth on.

Any ideas how to structure my data and algorithms to solve a problem like this? I'm not looking for a straight out answer, but some tips like:

Use this library, or this class, or this data structure. Or iterate like this through the available space.

Raynold

What's wrong with ONE TWO THREE FOUR? – Ordain

Great point! :) All words have to be linked to each other in one giant chain. – Raynold

This problem is actually pretty similar to the n-queens problem. You might be able to use some solutions to that problem for inspiration. The major difference is a variable size output grid for any input. – Apivorous

Answer 1

Think about what is the maximum size grid you would need? If the words are one, two, three, four, then the maximum size grid would be

12 x 12. This is the size of a grid where each word is placed end to end, sharing the last letter of the previous word.

Now we have the space. How do you fit the words in the space? Try to think about a brute force method. What would that entail?

Try iterating through all possible combinations of patterns. You can place each word 24 ways and there are 4 words, so you have ~500,000 combinations which is not many for modern computers to chunk through. See which patterns actually satisfy the criteria (letters match up, etc).

Once you have a brute force method, how could you refine it?

In terms of data structure, you really just need a grid that can store characters. You could use a nested list structure, a numpy array, pandas, or a whole lot of other stuff. Try to solve the problem simply at first, then refine later.

Beckwith