CODEWITHSUNDEEP
stringalgorithmdesign-patterns
user2011120
user2011120

Reputation: 137

Algorithm to form a given pattern using some strings

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?

Upvotes: 1

Views: 110

Answers (2)

nhahtdh
nhahtdh

Reputation: 56809

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.

Upvotes: 0

ogzd
ogzd

Reputation: 5692

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.

Upvotes: 1

Related Questions