Today we discuss another Olympiad problem on Informatics and mentioned by Radoszewski.
Problem Statement: this is a problem on track siding with an incoming track A and an exit track B - and two auxiliary tracks 1 and 2.
Problem Statement: this is a problem on track siding with an incoming track A and an exit track B - and two auxiliary tracks 1 and 2.
Track A contains 7 wagons numbered 1 through 7. The wagons arrive on track A in the following order:
(a)
6, 3, 2, 5, 1, 7, 4
(b)
5, 2, 4, 1, 6, 3, 7
(c)
6, 2, 5, 1, 3, 7, 4
(d)
7, 5, 2,
4, 1, 6, 3
(e)
6, 1, 3, 5, 2, 7, 4
The wagons are to exit via track B in increasing order of numbers 1, ...7. Each wagon is to be moved from track A to one of the tracks 1,2 and then to track B exactly once. There can be arbitrary many wagons on each track at the same time.
Can this task be completed successfully? If so, to which auxiliary track should the subsequent wagons be moved?
(For example, if the initial order of wagons was 5, 2, 6, 4, 1, 3, 7 then the answer would be positive. The wagons could be moved using the auxiliary tracks 1, 1, 2, 2, 1, 1, 1 respectively.)
Solution: The solutions found by trial and error include:
(a) 1, 2, 2, 1, 1, 2, 1
(b) 1, 2, 1, 1, 2, 1, 1
(c) 1, 2, 1, 1, 1, 2, 1
(d) 1, 1, 2, 1, 1, 2, 1
(e) 1, 1, 2, 1, 1, 2, 1
One of the important things to notice is that at all moments, all wagons on each auxiliary track must be sorted in increasing order from the smallest to the highest number There is a natural greedy approach to this problem but it doesn't always work. For example, we put the next wagon on the auxiliary track where the first wagon has the smallest number. In the first sequence, we should obtain wagons 1,2,3, and 6 on one auxiliary track and 5 in the other. Then if we move 1,2,3, to B then 7 cannot be moved to either auxiliary track. That is the greedy strategy does not work for all permutations. But we can exhaust the search space. One hint provided with this question is that the subtasks are constructed in such a way that a solution exists. But do we have an optimal substructure? The subtasks are usually increasing order in either auxiliary tracks that can be moved out to B. However, the order need not be strictly consecutive. And it is better to utilize more and more auxiliary tracks when the subsequences cannot be consecutive or increasing.
Therefore there are really three moves possible for a wagon
Move(wagon):
If a wagon can go directly to B from auxiliary tracks, move it to B
If a wagon can go directly to B from A, put it in auxiliary track 1 and move it to B
If a wagon has to go into one of the auxiliary tracks and not to B then
pick the one which has a consecutive higher number. (or if its distant by less than half of the total length of initial wagon set - so as to increase the likelihood of encountering a further number that can start a new stack)
pick the one which is empty
pick the one which has a higher number
The third step above should be simplified to pick the auxiliary track which has a higher number. The refinement above helps in quicker convergence.
Generally these moves accumulate the wagons on the auxiliary track until the first wagon reaches there.
Backtracking works here because it never considers an invalid option (a wagon moving over a lower numbered wagon on the auxiliary stack) and reduces the number of options from the permutations. We can choose one of the two auxiliary tracks as possible choices. The size of the auxiliary track does not matter so long as the wagons can be put in the order mentioned above. The termination conditions are when the next wagon from A does not have an
auxiliary track to be put in and when the wagons in A have been exhausted. The recurrence is based on the either auxiliary track receiving the wagon or the wagon exiting to make space for a
new wagon from A.
There are alternate solutions possible too such as where we don't check for each move but at the end of a sequence. For example,
we could think of each wagon getting an end result of 1 or 2 as the auxiliary track to use. Hence the entire sequence is a permutation and combination of these two choices. And for each sequence generated we can test whether it is valid or not with some bailing quickly than others. The generation of permutation is discussed earlier in this blog.
Solution: The solutions found by trial and error include:
(a) 1, 2, 2, 1, 1, 2, 1
(b) 1, 2, 1, 1, 2, 1, 1
(c) 1, 2, 1, 1, 1, 2, 1
(d) 1, 1, 2, 1, 1, 2, 1
(e) 1, 1, 2, 1, 1, 2, 1
One of the important things to notice is that at all moments, all wagons on each auxiliary track must be sorted in increasing order from the smallest to the highest number There is a natural greedy approach to this problem but it doesn't always work. For example, we put the next wagon on the auxiliary track where the first wagon has the smallest number. In the first sequence, we should obtain wagons 1,2,3, and 6 on one auxiliary track and 5 in the other. Then if we move 1,2,3, to B then 7 cannot be moved to either auxiliary track. That is the greedy strategy does not work for all permutations. But we can exhaust the search space. One hint provided with this question is that the subtasks are constructed in such a way that a solution exists. But do we have an optimal substructure? The subtasks are usually increasing order in either auxiliary tracks that can be moved out to B. However, the order need not be strictly consecutive. And it is better to utilize more and more auxiliary tracks when the subsequences cannot be consecutive or increasing.
Therefore there are really three moves possible for a wagon
Move(wagon):
If a wagon can go directly to B from auxiliary tracks, move it to B
If a wagon can go directly to B from A, put it in auxiliary track 1 and move it to B
If a wagon has to go into one of the auxiliary tracks and not to B then
pick the one which has a consecutive higher number. (or if its distant by less than half of the total length of initial wagon set - so as to increase the likelihood of encountering a further number that can start a new stack)
pick the one which is empty
pick the one which has a higher number
The third step above should be simplified to pick the auxiliary track which has a higher number. The refinement above helps in quicker convergence.
Generally these moves accumulate the wagons on the auxiliary track until the first wagon reaches there.
Backtracking works here because it never considers an invalid option (a wagon moving over a lower numbered wagon on the auxiliary stack) and reduces the number of options from the permutations. We can choose one of the two auxiliary tracks as possible choices. The size of the auxiliary track does not matter so long as the wagons can be put in the order mentioned above. The termination conditions are when the next wagon from A does not have an
auxiliary track to be put in and when the wagons in A have been exhausted. The recurrence is based on the either auxiliary track receiving the wagon or the wagon exiting to make space for a
new wagon from A.
There are alternate solutions possible too such as where we don't check for each move but at the end of a sequence. For example,
we could think of each wagon getting an end result of 1 or 2 as the auxiliary track to use. Hence the entire sequence is a permutation and combination of these two choices. And for each sequence generated we can test whether it is valid or not with some bailing quickly than others. The generation of permutation is discussed earlier in this blog.
No comments:
Post a Comment