Can you help me solve this problem please?

Question

My description is too long to post here. Please, view my answer.

Answer 1

It is a kind of backtracking algorithm ( https://www.geeksforgeeks.org/backtracking-algorithms/) what are you are trying and for me it would be the preferred way to solve such a problem.

--> first number = 5 --> check if you have a piece which starts with 5 (yes: add the piece, no: no solution)
--> last number = 2 --> check if you have a piece which ends with 2 (yes: add this piece; no: no solution)
5 (5,4) ... (2,2) 2
Same again:
new number = 4 --> check if you have a piece which starts with 4 (yes: add it, store the second number of this piece; no: remove the first piece --> try to find another piece which starts with 5; no piece found --> no solution)
--> new last number = 2 --> check if have a piece which ends with 2 (yes: add the piece; no: remove the last piece, try to find a new last piece which ends with 2; no piece found --> no solution)
5 (5,4) (4,6)... (3,2)(2,2) 2
And so on ... until all pieces are added or no solution could be found.

Answer 2

Thank you a lot. I will try to implement it.

Answer 3

PART ONE

Hello. I am trying to solve one programming exercise, but I don't know how to make it. The problem is, that I have an idea how to solve it, but it would run in O(n^m) time complexity (both numbers are in input), so it would take too much time to process (for usual input, that could be solved just with a human brain, it would take 42 days to an average computer).

Ok, so now to the problem:
Imagine, that you have dominoes. You have one number on one side of the table, the second number on the other side of the number and between them, you have space for a defined amount of playing pieces. You need to find out, if you can connect the two numbers on the sides of the table witch dominoes parts, without breaking any rules (pieces must touch with the same number and they must be in one line). But you can't use all domino pieces that exist - you have a defined set of them, but you can use each of them as many times as you need. There can be any numbers on the pieces - 1, 2, 5, 35 or 357 154. Rotating the pieces (swapping numbers on the piece) isn't allowed.

Example input:
Side one: 5
Side two: 2
Space: 6
Available pieces: {{5;4},{4;6},{2;2},{3;5},{1;4},{5;1},{6;3},{3;2},{6;2},{1;2},{2;1},{4;4}}

Output: true (solution is: 5 [5|1][1|4][4|6][6|3][3|2][2|2] 2)

My method of solving is very primitive: I simply take all numbers, that I can get to from the first number (the second number on all pieces that have 5 as their first number), I save them and then I do that again with these numbers. I do this M-times (M = space input) - not more, not less. If I get the finish number (2) in the final array, the result is true, otherwise, it is false.

The problem is, that in the worst scenario, there will be pieces with all possible combinations of numbers and it would generate too many possible paths.

SEE MY SECOND COMMENT FOR PART TWO.

Answer 4

PART TWO

I am trying to reduce the number of operations by removing paths that can't lead to finish (for example, I can have a piece, that has numbers [4|0] on it, but the only piece with number 0 as it's the first number would have also 0 as its second number and I would have to reach a different number than 0 in the finish - in that case I don't need to count with the piece [4|0], because the path will never lead to finish).
My second idea was switching between doing the pathfinding from the start and from the finish. The two branches would meet in the centre and there would be much fewer paths to count with (because of (2 * n^(x/2)) < (n^x)).

Do you have any other ideas how could I reduce the number of paths, or even better, do you know about any solution that wouldn't run in exponential time complexity?

Thank you.

Answer 5

Jan Štěch Your welcome :)