★ APPLICATIONS ★ DIVERS ★ The ups and downs of sorting out data ★ |
| Sort the Rainbow (Computing With the Amstrad) | Applications Divers |
ALEATOIRE gives you a lift with understanding quick search algorithms ANY years ago when computers were mysterious giants that filled up a ballroom and required a dozen people shovelling coal and flicking switches to make them work there were no random access devices. Everything that the machines were fed or regurgitated was sequential, usually on paper or magnetic tape. Consequently a great deal of time and effort was spent in devising efficient sorting, hence quick searching, algorithms. One of the biggest problems was that computers had very limited memory, or main store, compared with the size of the data records to be sorted, and this gave rise to the elevator puzzle. Imagine a building with F floors, each holding exactly P people but with the majority of them on the wrong floor. There is a single elevator that can carry, at most, E people and E (the computer memory) is smaller than P. the maximum number of people or records that you want to shift. The elevator always starts at the ground floor. It can move up and down, loading and dropping people until everyone is where they should be - the elevator then returns to the ground floor. The problem is how to sort all the people in the minimum number of moves, where a move is up or down a floor, that is we want to minimise the distance the elevator has to travel. Program I will allow you to practice and learn how to solve this classic problem. To make it easier to visualise I have named the seven families (three members each) and the seven floors of the building after the colours of the rainbow with the Reds living at the top and the Violets at the bottom. To test that it is working remove, or ignore, (ines 110-170 and you should find that the families start in the reverse order — that is. Reds at the bottom, Violets at the top - and that you have exactly 40 moves to sort them all out. See Figure I. 7. Red V V V The number of moves is the correct and absolute minimum required and is calculated by lines 190-260. The program will check that you do not exceed this limit, but has no idea itself, nor gives any clue, about how to solve the puzzle. To further test that the program is working you should note that you (playing the elevator) are "empty” at the start (contain two Whites), that you can "see” three Reds and that entering U or D does actually move you up and down the levels correctly. To swop, hence sort, colours just enter the first letter of a colour you have followed by the first letter of a colour you can see at the current level. For instance, at the start of the test entering WR will swop a White for a RED. Note that a swop does not count as a move. Only U and D are counted. If all this is working, replace lines 110-170 and the program will mix up the colours randomly, calculate the minimum number of moves to sort them out, obey your commands and check your progress. If you have never seen this sort of problem before it is very unlikely that you will be able to solve any of the literally thousands of starting patterns it can generate. You may imagine that you must need to know where all the colours You, the elevator, start in the UP state. 1: If in the UP state and anyone needs to go up. then get the two that need to go highest and move up one floor. Otherwise change to the DOWN state. 2: If in the DOWN state, pick the two who need to go lowest and move down one floor. If no one at this new floor, or below this floor, needs to go to a higher floor, change to the UP state. If you follow these rules exactly and without thinking - just like a computer - you will always succeed in sorting out any pattern. The things to notice are that at the start you will always go straight up to the 7th level and inevitably drop the two Reds that you will have found on the way. If you go wrong later on. and take too many moves, you have almost certainly broken the second part of rule 2. that is you have moved down when no one below needed to come higher than the current floor. With practice the puzzle becomes trivial, but note that the algorithm will work for any number of levels and any number of people, providing the number of people exceeds the size of the elevator. How it does this is quite spooky. You will notice that occasionally people are taken from their correct level and even made to travel in the wrong direction. This is because the system is communist, in that it does the greatest good for the greatest number and the rights of the individual are totally ignored. The elevating moral of this sort story is that rights and privileges do not make the world go round and actually get in the way of it going up or down.
|
