whatevva'
BAN USERI believe the trie is mostly an optimization in the context of this question. It will only help if the 2d matrix consists of largely random characters. In the worst case, if most/all combinations of the characters in the 2d matrix are valid words, then i dont think a trie will really help.
Following is my code. The 2d matrix is converted to a set of base strings consisting of left-right rows, right-left rows, top-down columns and down-top columns. Then each base string is iterated on to verify for valid word combinations and printed.
##SETUP
mat2d = [ ['c', 'a', 't'],
['g', 'o', 'd'],
['f', 'b', 'r']]
dictx={ 'cat': 1,
'god': 1,
'go': 1,
'dog': 1,
'do': 1,
'boa':1
}
##CREATE BASE STRINGS
M = len(mat2d)
N = len(mat2d[0])
base_str_set=list()
#row by row
for i in range(M):
temp_str1=""
temp_str2=""
for j in range(N):
temp_str1 += mat2d[i][j] #left to right
temp_str2 +=mat2d[i][N-1-j] #right to left
base_str_set.append(temp_str1)
base_str_set.append(temp_str2)
#col by col
for j in range(N):
temp_str1=""
temp_str2=""
for i in range(M):
temp_str1 += mat2d[i][j] #top to bot
temp_str2 += mat2d[M-1-i][j] #bot to top
base_str_set.append(temp_str1)
base_str_set.append(temp_str2)
#ITERATE ON BASE STRINGS AND PRINT VALID WORD COMBINATIONS
for base_str in base_str_set:
for i in range(len(base_str)):
for j in range(i,len(base_str)):
if base_str[i:j+1] in dictx:
print base_str[i:j+1]
Are the words formed in the same direction throughout? if we are going from left to right on a row in the matrix, do we have to keep going right? or can we start from left to right and turn top or bottom to check for valid words?
basically, i want to clarify if this is truly a variation of the "flood fill" algorithm as another user is suggesting.
An upfront sorry about the long post below. I think we need to realize that for minimum number of lift movements, this problem involves traversing cycles in terms of how we move people.
- whatevva' May 31, 2013Lets say the people are in the following order from floors 1 to 5: [ P4, P3, P1, P5, P2 ]
So, following are the lift movements [ P4->F4, P5 ->F5, P2->F2, P3->F3, P1->F1] .. after moving the last person we are back to where we started at floor 1 and this has minimum number of lift movements.
The above example has 1 cycle .. and moving ppl in one continuous cycle minimizes the number of lift movements.
The solution is more complex when we have multiple cycles .. since after completing 1 cycle, we have to process the next cycle ... and this inter-cycle movement causes extra lift movements. In the example given by "aka", there are multiple cycles:
floor person_tag
1 2
2 1
3 3
4 5
5 4
cycle 1: [(1 2), (2 1)]
cycle 2: [(3,3)]
cycle 3: [(4 5) (5 4)]
In this case, we can ignore all cycles that have a single element. so ignore cycle 2: [(3,3)].
Start cycle 1: move person 2 from floor 1 to floor 2. suspend Cycle1 ... floor 2 has persons 1 and 2
Move to floor 4 to start processing cycle 3: move person 4 to floor 5 and move person 5 to floor 4
move back to floor2 to resume cycle 1: move person 1 to floor 1.
In this solution, the extra lift movements are when moving from cycle 1 to cycle 3 and back.
Overall, the solution involves finding all cycles, ignore cycles with single elements. Then we need to find overlapping cycles and underlapping cycles. We need to move from 1 cycle to another by suspending the first cycle (put on stack) and moving to the second cycle anytime there is overlap or underlap. This could be recursive and so we would need a stack to keep track of where we suspended cycles and in which order.