MoveAndTurn Part 3

Yesterday I thought that the greedy paths that were computed for the previous posts MoveAndTurn Part 1 and Part 2 are not the only ones.

They networkx library could help computing how many paths are there.

Here is the code:

import networkx as nx
import math

def isAdjacent(s1,s2):
i1 = int(s1[0])
i2 = int(s2[0])
j1 = int(s1[1])
j2 = int(s2[1])
if (math.fabs(i1-i2) == 1) and (j1==j2):
return(1)
elif (math.fabs(j1-j2) == 1) and (i1==i2):
return(1)
else:
return(0)

G = nx.Graph()
V = []
for i in range(1,6):
for j in range(1,6):
V.append(str(i)+str(j))
G.add_nodes_from(V)
for x in G.nodes():
for y in G.nodes():
if isAdjacent(x,y):
G.add_edge(x,y)

#print(G.nodes())
for length in range(9,26):
print(len([x for x in list(nx.all_simple_paths(G,source="11",target="55")) if len(x) == length]))

The result is:

70
0
224
0
510
0
956
0
1586
0
2224
0
2106
0
732
0
104

So there are 70 “greedy” paths of length 9, and 104 paths of (maximum) length of 25.
All paths have odd number of steps.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s