In the switch box routing problem,
we are given a box with pins on the side
and a set of connections required between the pins.
For example,
we might have
(where the numbers represent the pins),
and the requirement that pin #1 be connected to pin #4,
pin #2 to pin #3,
pin #5 to pin #6,
and pin #7 to pin #8.
All of the connections need to be made inside the box
(labeled "routing area" in the figure above),
and the wires connecting the pins are not allowed to cross each other.
Confirm for yourself that the routing example above can be done,
but that any routing that requires pin #6 to be joined to pin #8
and also pin #7 connected to pin #5 is impossible.
We can use a stack to check whether a required routing is possible.
- Visit each pin in clockwise order (from 1 to 8 in the example).
-
If there is something in the stack
and
the number at the top of the stack
is the pin the current pin needs to be connected to,
then pop that number off the stack
(saying that you've made that connection).
- Otherwise, push the pin number onto the stack.
-
After all pins have been processed,
the stack should be empty.
If it is,
the routing is possible.
If it's not empty,
the routing is impossible.
I have provided you with a program that creates the routing problem.
When you run it you need to specify
how many pins there are,
and which pins need to be connected.
For example:
How many pins are there on the box? 8
Which pin must pin #1 connect to? 4
Which pin must pin #2 connect to? 3
(pin #3 connects to pin #2)
(pin #4 connects to pin #1)
Which pin must pin #5 connect to? 6
(pin #6 connects to pin #5)
Which pin must pin #7 connect to? 8
(pin #8 connects to pin #7)
The pin connections are:
1 --> 4
2 --> 3
3 --> 2
4 --> 1
5 --> 6
6 --> 5
7 --> 8
8 --> 7
Note that the program does not ask about pins #3 and #4
because it already knows that they need to be connected to pins #2 and #1
(respectively).
Similarly for pins #6 and #8.
Also note that it will say that the routing cannot be completed.
That's because I've only provided a stub
for the method that's supposed to find out
whether the routing can be completed.
The connections are stored in an array named pins,
where pins[i] holds the number of the pin
that pin #i is supposed to connect to:
(Note that pins[0] is not used.)
Complete the definition of the canBeRouted method
according to the description given above.
Announce each connection as its made:
Connecting pin #3 to pin #2
Connecting pin #4 to pin #1
Connecting pin #6 to pin #5
Connecting pin #8 to pin #7
Confirm that your code works using the following examples:
How many pins are there on the box? 8
Which pin must pin #1 connect to? 4
Which pin must pin #2 connect to? 3
(pin #3 connects to pin #2)
(pin #4 connects to pin #1)
Which pin must pin #5 connect to? 6
(pin #6 connects to pin #5)
Which pin must pin #7 connect to? 8
(pin #8 connects to pin #7)
The pin connections are:
1 --> 4
2 --> 3
3 --> 2
4 --> 1
5 --> 6
6 --> 5
7 --> 8
8 --> 7
Connecting pin #3 to pin #2
Connecting pin #4 to pin #1
Connecting pin #6 to pin #5
Connecting pin #8 to pin #7
Routing done.
How many pins are there on the box? 8
Which pin must pin #1 connect to? 4
Which pin must pin #2 connect to? 3
(pin #3 connects to pin #2)
(pin #4 connects to pin #1)
Which pin must pin #5 connect to? 7
Which pin must pin #6 connect to? 8
(pin #7 connects to pin #5)
(pin #8 connects to pin #6)
The pin connections are:
1 --> 4
2 --> 3
3 --> 2
4 --> 1
5 --> 7
6 --> 8
7 --> 5
8 --> 6
Connecting pin #3 to pin #2
Connecting pin #4 to pin #1
Routing cannot be completed.
How many pins are there on the box? 10
Which pin must pin #1 connect to? 8
Which pin must pin #2 connect to? 3
(pin #3 connects to pin #2)
Which pin must pin #4 connect to? 5
(pin #5 connects to pin #4)
Which pin must pin #6 connect to? 7
(pin #7 connects to pin #6)
(pin #8 connects to pin #1)
Which pin must pin #9 connect to? 10
(pin #10 connects to pin #9)
The pin connections are:
1 --> 8
2 --> 3
3 --> 2
4 --> 5
5 --> 4
6 --> 7
7 --> 6
8 --> 1
9 --> 10
10 --> 9
Connecting pin #3 to pin #2
Connecting pin #5 to pin #4
Connecting pin #7 to pin #6
Connecting pin #8 to pin #1
Connecting pin #10 to pin #9
Routing done.