2
$\begingroup$

I am not a computer science nor a math person, but if given a pseudo-code or a English outline of steps. I can probably fumble my way through and write some code. I Apologize for the wall of text/numbers and my formatting.

Seeking an algorithm that takes a number to start with. This number will be either in column A or column B

The algorithm will traverse down the list alternating the two columns A and B, if the first selected number is in column B then the next number must be in column A and vice versa

The length of movement must be one of the 20 values or as close as possible with a difference no greater than 0.1409

The algorithm ideally would collect all paths from the starting number to last number in the list or past the end of the list according to the above rules.


Column A, Column B

78.509, 78.087

79.996, 79.063

80.826, 80.112

81.307, 81.569

82.939, 82.123

83.274, 83.973

84.003, 84.979

85.081, 85.999

86.043, 86.742

87.441, 87.063

88.491, 88.986

89.991, 89.307

90.341, 90.589

91.157, 91.536

92.017, 92.541

93.051, 93.853

94.100, 94.785

95.426, 95.091

96.213, 96.563

97.933, 97.044

98.778, 98.064

99.827, 99.200

100.993, 100.337

101.619, 101.007

102.727, 102.960

103.892, 103.339

104.009, 104.606

105.072, 105.699

106.311, 106.952

107.681, 107.448

108.759, 108.234

109.196, 109.983

110.333, 110.916

111.629, 111.353

112.926, 112.023

113.276, 113.946

114.005, 114.923

115.943, 115.127


The 20 only possible length of movements

1.1275

2.2550

3.3825

4.5100

5.6375

6.7650

7.8925

9.0200

10.1475

11.2750

12.4025

13.5300

14.6575

15.7850

16.9125

18.0400

19.1675

20.2950

21.4225

22.5470


1 Possible combination For Example Starting Number:81.307 Column A next target is on Column B 81.307 + 13.52 = 94.827 - Column B Num:94.785 (94.827-94.785) = .042 which is less than 0.1409, so this is an acceptable movement.

Now Column B num:94.785 + Num:6.765 = 101.55 which is within acceptable tolerance of the Column A Number of 101.619

Now Column A num:101.619 + Num:13.52 = 115.139 which is in acceptable tolerance of Column B num:115.127

Thank you for your Time and Effort Scott

$\endgroup$
2

1 Answer 1

1
$\begingroup$

We can view this problem as depth first search on a directed unweighted bipartite graph.

A graph is a set of vertices connected by a set of edges between the vertices.

We can construct such graph by viewing each number as a vertex, then ask each pair of vertices whether they match one of the possible length of movements (check the possible length of movements one by one) and form an edge between them if they do.

The graph is directed since otherwise we could go between 81.307 and 94.827 without ever ending, which I assume is not intended.

The graph is unweighted since we only want to know whether we can go between 81.307 and 94.827, for example.

The graph is bipartite since we can only go to the other column and never the same column, we can color the columns blue and red without the vertices of the same color ever being adjacent.

We can perform depth first search using recursion on the graph to find all possible paths from a source point in lexicographical order.

The total time taken by this algorithm is proportional to the number of elements of column A times the number of elements of column B times the number of possible length of movements.

$\endgroup$
2
  • $\begingroup$ Thanks to all for responding to my query. The responses enabled me to get an understanding of how to tackle my issue. Thanks again! $\endgroup$ Commented Feb 21 at 15:19
  • $\begingroup$ @ScottWatson You're welcome! If you had some coding background but unfamiliar with graphs, you may want to familiarize yourself a bit and follow some code. If the answer is understandable enough, you may mark it accepted. $\endgroup$ Commented Feb 21 at 18:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.