Facebook Interview Question
Software EngineersCountry: United States
Solution in python. Cost O(k^n).
This is a brute force solution with no heuristics so it is not very efficient, make sure there is a solution or it will loop forever.
Some heuristics may include don't make a movement if you are increasing the total number of disordered pieces or putting adjacent numbers together even if they are not in the right posisition
Example:
solveMaze([[2,3], [1, 'x']])
([[1, 2], [3, 'x']], [(1, 1), (0, 1), (0, 0), (1, 0), (1, 1)])
from itertools import chain
def isSolution(m):
x = list(chain.from_iterable(m))
for p in xrange(len(x)-1):
if x[p] > x[p+1]:
return False
return True
def swapMatrix(m, s1, s2):
temp = m[s1[0]][s1[1]]
m[s1[0]][s1[1]] = m[s2[0]][s2[1]]
m[s2[0]][s2[1]] = temp
def computeSuccessors(s1, top, l):
res = []
for p in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
s = (s1[0] + p[0], s1[1] + p[1])
if s[0] < 0 or s[0] >= top or\
s[1] < 0 or s[1] >= top or s == l:
continue
res.append(s)
return res
def solveMaze(m):
frontier = [(m, [(len(m) -1, len(m) - 1)], (len(m) -1, len(m) - 1))]
while len(frontier):
m, s, l = frontier.pop(0)
s1 = s[-1]
if isSolution(m):
return (m, s)
for s2 in computeSuccessors(s1, len(m), l):
swapMatrix(m, s1, s2)
frontier.append(([r[:] for r in m], s[:] + [s2], s1))
swapMatrix(m, s1, s2)
return None
After googling few helpful links;
1) https://stackoverflow.com/questions/32442837/minimum-number-of-steps-to-sort-3x3-matrix-in-a-specific-way
2) https://en.wikipedia.org/wiki/A*_search_algorithm
3) https://en.wikipedia.org/wiki/15_puzzle
Basically it is a modification of Dijkstra algorithm, every move of empty box at every stage will give at max 4 new states -- consider these states as neighbours. Thus every state has max 4 neighbours and we can then do a BFS on them to find the state which is sorted and combined with Dijkstra logic will give us minimum steps.
- nk June 14, 2017