โŒ About FreshRSS

Normal view

There are new articles available, click to refresh the page.
Before yesterdayNews from the Ada programming language world

A cell phone company is continually building and leasing communication towers. Each tower has one-way, direct communcation links to other tower [closed]

A cell phone company is continually building and leasing communication towers. Each tower has one-way, direct communcation links to other towers. The task is find if there is a communication link from one tower to another, possibly through other towers.

The input to the program is essentially a list of pairs of tower names. Each pair will appear on a single line and will contain distinct names. Some pairs represent one-way communcation links between towers, and other pairs represent queries. Links and queries may be interspersed.

All the communication links of the system are added one link at a time and no links are removed. Here is an example of a link:

Tower_A Tower_B. A link is terminated by a period.

A query asks if a communcation link is possible from one tower to another by any combination of one-way links. If another link is added to the system later in the input, then the answer to the same query may be different. In the output, a plus sign (+) represents an affirmative answer; a minus sign (-) says there is no such link.

Links are distinguished from queries by ending in a question mark and not a period.

Tower_A Tower_B? The program should read from the standard input and and write to the standard output. For each query in the input there should be exactly one line of output. If the query is true (there is a communication channel through the network), the output line should begin with a plus sign (+); otherwise with a minus sign (-). The rest of the output line repeats the towers in the query.

For the following input:

Tower_A Tower_B. Tower_B Tower_C . Tower_A Tower_C? # A query Tower_B Tower_D. Tower_A Tower_D ? # Another query Tower_F Tower_E. Tower_D Tower_B ? # A third query xxxx yyyy? # Unknown tower names Tower_D Tower_B . Tower_D Tower_B ? # Now there is a link the output should be

  • Tower_A -> Tower_C
  • Tower_A -> Tower_D
  • Tower_D -> Tower_B
  • xxxx -> yyyy
  • Tower_D -> Tower_B The names of the towers will contain only the characters [a-zA-Z_0-9], in particular they will have no spaces in them. Names will have at least 1 character and no more than 50 characters. Furthermore the capitialization of the names is significant. That is, WestMelbourneTower is not to be considered the same tower as wESTMeLbOuRnEtOwEr. Characters, if any, after the period (.) or question mark (?) on a line are to be ignored. No line will will contain more than 150 characters.

Please carefully observe spacing. There may, or may not, be a space before the period, the question mark, and the comment in the input. There will be one or more spaces between the tower names in the input. There must be a space after the plus and minus sign in the output. There must be a space before and after the arrow (->) in the output.

You are required to create your own graph package graph.ads graph.adb and name it Graph. The package can be generic or non-generic. The graph is to be a list of adajency lists. You are required to use the generic, doubly-linked list package from the standard library. These requirements are generally reasonable ones for the task anyway. There are more sophisticated approaches and less sophisticated approaches, but these requirements ensure the educational objectives of the assignment are met.

โŒ
โŒ