Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
Powers of the adjacency matrix of a graph to find a path between numbers solution in Creative category for Digits Doublets by Phil15
##I regret there is no module for getting the shortest path in a graph since that's the problem here.
#1 if the difference between the numbers s and t is exactly one, else 0.
diff_1 = lambda s, t: 1 if sum(str(s)[i]!=str(t)[i] for i in range(3))==1 else 0
#We are going to multiply matrices, but we just need if a positive coefficient is 0 or not, so I simplify by min(1,...)
mult_min1 = lambda A,B: [[min(1,sum(A[i][k]*B[k][j] for k in range(len(A)))) for j in range(len(A))] for i in range(len(A))]
def checkio(numbers):
"""
Solve the Digits Doublets problem with adjacency matrix of a graph with numbers as vertices.
Powers of the adjacency matrix will allow us to find a path between numbers[0] and numbers[-1].
Return [] if a game has no solution.
"""
#The adjajency matrix of the graph where the elements of numbers are vertices, and 2 vertices are related if the diff is 1.
M = [[diff_1(i,j) for j in numbers] for i in numbers]
#M1_n will store powers of M : "M1_n=[M, M**2, M**3, ...]"
n, M1_n = 1, [M]
#We search a path between numbers[0] et numbers[-1], M1_n[-1] [0][-1]==1 if and only if there is a path of n steps.
#Also, there is necessarily less steps than vertices-1.
while M1_n[-1][0][-1]==0 and n<=len(numbers)-1:
M1_n.append(mult_min1(M1_n[-1], M)) #One more 'power' of M
n += 1
if n==len(numbers):
return [] #Here, there is no solution to the game.
else:#Here, there is a solution.
#We are going to store indexes of the numbers of the chain.
#It begins with 0. It ends with -1.
#Between that, we search recreate the path of n steps. The last is -1, so we search only for n-1 steps.
res = [0]#Begin
for m in range(n-1):
#Step m (<= n-1)
k = 0
while not (M[res[-1]][k]==M1_n[n-1-1-m][k][-1]==1):
#Adjacency matrix stuff.
#We search k such as M[res[-1]][k]==M1_n[n-1-1-m][k][-1]==1
#Because it say k is the next index on the path.
k += 1
res.append(k)#So we store it.
res.append(-1)#End
return [numbers[r] for r in res]#The path selected.
#These "asserts" using only for self-checking and not necessary for auto-testing
if __name__ == '__main__':
assert checkio([123, 991, 323, 321, 329, 121, 921, 125, 999]) == [123, 121, 921, 991, 999], "First"
assert checkio([111, 222, 333, 444, 555, 666, 121, 727, 127, 777]) == [111, 121, 127, 727, 777], "Second"
assert checkio([456, 455, 454, 356, 656, 654]) == [456, 454, 654], "Third, [456, 656, 654] is correct too"
print("Go check, man!")
March 5, 2018
Comments:
