I'm trying to write a short program to find an ideal domino chain, ideas?

user_14954694 0
Viewed 305

If you are no familiar with dominos: you have gaming pieces with two numbers on them. You have to arrange them so, that the ending of the first piece is the beginning of the second piece. So if we have 3 dominos with values [3-1][3-4][1-4] you could arrange them to [1-3], [3-4], [4-1] or [4-1], [1-3], [3-4], since you can switch the side you start with (turning the pice).

Now to my code problem:

I got a pandas df with the domino values:

# D1 D2
1 1 5
2 2 4
3 3 6
4 4 1
5 3 4
6 2 3
7 6 5 
dominos = {'D1': [1, 2,3,4,3,2,6], 'D2': [5,4,6,1,4,3,5]}

Now if I choose one of the pieces at random and need to find a 'route' to get to that specific domino (the chosen one cant be rotated), starting from 1 and ending again at 1, while using the smallest amount possible of domino pieces.

For example: the chosen piece was [3-4], the code needs to print out the route, looking something like this(or in an array):

1: #1 [1-5]
2: !#7 [5-6] 
3: !#3 [6-3] 
4: **[3-4]** 
5: #4 [4-1]

So far I've tried to do this with a lot of for loops, which didn't work.

import pandas as pd


dominos = {'D1': [1, 2,3,4,3,2,6], 'D2': [5,4,6,1,4,3,5]}
data = pd.DataFrame(dominos) 


ranD = data.loc[4,]

def findpath(data, ranD):
    trargetD1 = ranD.D1 
    #fid possible start
    for x in range(len(data)):
        if data.loc[x,'D1'] == 1:
            start = start + data.loc[x,]
            if start.loc[x, 'D2'] == ranD.D1:
                PerfectStart = start.loc[x, 'D2']
            elif start.loc[x, 'D2'] != ranD.D1:
                PerfectStart = start.loc[1,] 
        else:
            print("no start found")
    # when a start was found, that doesn't match ranD at pos. D2 find possible steps        
    for x in range(len(data)):
        if PerfectStart.D2 == ranD.D2 :
            
            step1 = step1 + data.loc[x,'D1']
            if step1.loc[x, 'D2'] == ranD.D1:
                PerfectStep = step1.loc[x, 'D2']
            elif start.loc[x, 'D2'] != ranD.D1:
                PerfectStep = step1.loc[1,]
  
etc.

If anyone has ideas on how to approach this, please let me know.

Your feedback is much appreciated!

pandas sorting algorithm python
2 Answers

You want to think of this as a graph problem.

You have 6 nodes (1..6) and the dominos are edges between nodes.

You are looking for a path from 1 to 1 that passes through a specific edge (a,b), and has the minimum amount of edges and doesn't pass through the same edge twice.

So the naive approach is to look for a path from 1 to a and from 1 to b and hope or enforce that they don't share edges.

However there are some setup where it will not work because the first path you chose blocks the second one. There is a solution for this which is maximum flow.

For this you need to link a Source to node 1 with capacity 2. And a and b to the Sink with capacity 1. Every other edge will have capacity 1. If you solve the max flow it will either be of capacity 2 and you can extract the path or will have capacity 0 or 1 in which case there's no solution.

Since you only have 6 nodes don't worry about having a very efficient solution since almost everything will run fast.

If you are familiar with max flow you can probably simplify the implementation a bit. If not, don't worry, implement the most straightforward solution you can.

user_2410130

I think the easiest approach conceptually would be to turn this problem into a min-cost flow problem. Set up a graph where there is a node for each number, and each domino is an edge connecting the nodes corresponding to the numbers on it, with capacity 1 in each direction and cost 1. Delete the edge corresponding to the domino that you're trying to use in a chain and assign 1 unit of demand to each of its numbers. Assign 2 units of supply to node 1. Find the min cost flow (using e.g. NetworkX) and use DFS to turn the set of dominos into a chain.

user_21446690
Related