Algorithm to form a given pattern using some strings

Question

Given are 6 strings of any length. The words are to be arranged in the pattern shown below. They can be arranged either vertically or horizontally.

      --------
      |      |
      |      |
      |      |
      ---------------
             |      |
             |      |
             |      |
             --------

The pattern need not to be symmetric and there need to be two empty areas as shown. For example:

Given strings

PQF  
DCC  
ACTF  
CKTYCA  
PGYVQP  
DWTP

The pattern can be

DCC...  
W.K...  
T.T...  
PGYVQP  
..C..Q  
..ACTF

where dot represent empty areas.

The other example is

RVE  
LAPAHFUIK  
BIRRE  
KZGLPFQR  
LLHU  
UUZZSQHILWB

Pattern is

LLHU....  
A..U....   
P..Z....  
A..Z....  
H..S....  
F..Q....  
U..H....  
I..I....  
KZGLPFQR  
...W...V  
...BIRRE

If multiple patterns are possible then pattern with lexicographically smallest first line, then second line and so on is to be formed. What algorithm can be used to solve this?

Seems like there has to be some constraints on the strings' lengths. — David
– David, Commented Feb 7, 2013 at 19:51
Strings have not been given any relative constraints. There may be possible situation when no such pattern is possible, then the same is to be answered. — user2011120
– user2011120, Commented Feb 7, 2013 at 19:53
Well I suppose that you can just play around with modulus and first make a program that makes the 4-way intersection. — David
– David, Commented Feb 7, 2013 at 19:55
Just do some smart brute force. Among the 6 strings, there can only be at most 4 candidates for middle 2 strings. And the candidate for the 2 strings in the corner is quite constrained. — nhahtdh
– nhahtdh, Commented Feb 7, 2013 at 19:59

ogzd · Accepted Answer · 2013-02-07 19:57:45Z

1

Find strings which suits to this constraint:

strlen(a) + strlen(b) - 1 = strlen(c)
strlen(d) + strlen(e) - 1 = strlen(f)

After that try every possible situation if they are valid. For example;

aaa.....
d.f.....
d.f.....
d.f.....
cccccccc
..f....e
..f....e
..bbbbbb

There will be 2*2*2 = 8 different situation.

answered Feb 7, 2013 at 19:57

ogzd

5,7422 gold badges28 silver badges27 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

ryanbwork Over a year ago

the first character in each of the substrings overlaps, so it would be strlen(a) + strlen(b) -1 = strlen(c)

nhahtdh Over a year ago

8 situation is for this case only.

ogzd Over a year ago

In the worst case, there will be 4! * 2! = 48 situation

nhahtdh · Accepted Answer · 2013-02-07 20:55:37Z

There are a number of heuristics that you can apply, but before that, let's go over some properties of the puzzle.

+aa+
c  f
+ee+eee+
   f   d
   +bbb+

Let us call the length of the string with the same character as appeared in the diagram above. We have:

a + b - 1 = e
c + d - 1 = f

I will refer to the 2 strings for the cross in the middle as middle strings.

We also infer that the length of the string cannot be less than 2. Therefore, we can infer:

e > a, e > b
f > c, f > d

From this, we know that the 2 shortest strings cannot be middle strings, due to the inequality above.

The 3 largest strings cannot be equal also, since after choosing any of 3 string as middle string, we are left with 2 largest strings that are equal, and it is impossible according to the inequality above.

The puzzle is only tricky when the lengths are regular. When the lengths are irregular, you can do direct mapping from length to position.

If we have the 2 largest strings being equal, due to the inequality above, they are the 2 middle strings. The worst case for this one is a "regular" puzzle, where the length a, b, c, d are equal.

If the 2 largest strings are unequal, the largest string's position can be determined immediately (since its length is unique in the puzzle) - as one of the middle string. In worst case, there can be 3 candidates for the other middle string - just brute force and check all of them.

Algorithm:

Try to map unique length string to the position.
Brute force the 2 strings in the middle (taken into consideration what I mentioned above), and brute force to fill in the rest.

Even with stupid brute force, there are only 6! = 720 cases, if the string can only go from left to right, up to down (no reverse). There will be 46080 cases (* 2^6) if the string is allowed to be in any direction.

Collectives™ on Stack Overflow

Algorithm to form a given pattern using some strings

2 Answers 2

3 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

3 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related