An integer N is given, followed by N number of pairs of integers - the pairs represent domino tiles. Each tile can rotate (ie the first number becomes the second and vice versa).
Find such a sequential arrangement of the maximum number of tiles in a row so that for each tile (excluding the first) the first number coincides with the second number of the previous tile. Display the resulting row. If there is more than one row with a maximum length, select any of the options
I dont have any ideas how to find the max number of domino tiles, can you give me ideas?
If your exercise has more details then please give them (irrespective of whether you think they are relevant). That includes:
- maximum size of N;
- maximum dots on one side of a domino tile (typically 6 ... but it doesn't have to be);
- are repetitions (i.e. same tile) allowed?
- any examples given in order to check code;
- any other information.
I would probably set up the adjacency set for each possible number of dots, then scan the possible tile sequences recursively. But it would be simpler if you had the information above.
Yeah sorry, so we don’t have max dots, my mistake!
And for N = 5
We have just 10 numbers, what’s the problem with that? The task doesn’t use OOP, we just represent the domino in an array.
Each tile of domino has 2 numbers on it - so when we have 5 tiles we have 10 numbers total.
In my example we can look at it this way:
1st domino 1|2
2nd domino 2|10
3rd domino 7|10
And so on
So, like I said in my first post ... set up a container of target dominos for each possible number of dots (e.g., in your example, 2 would be able to sit next to dominos 0 (1-2) and domino 1 (2-10) ).
Then you can scan recursively through all the dominos starting on either side of each domino. Each recursive part of the scan can either add a new, unused domino to the current row if one is still available or backtrack if not. Just keep track of the longest row so far.