Main Question or Discussion Point
Disclaimer : This thread, and its solution, by no means suggests how to launch a network attack in real life. The purpose of this challenge is to learn how to decompose graphs and analyze them as efficiently as possible. There is no knocking down of network connections, or even speculations as to how to do so. Any solutions to this exercise, and the challenge itself, is not analogous to hacking!
Just for fun, I thought I'd post this up here, in case any of you are bored and want some extra practice in whichever language you are learning.
The reason I posted it here, is because the knowledge required to complete this program is quite limited. All you need to know is recursion, File I/O, and arrays. But! The challenge's difficulty comes from efficiency. I'll explain near the end of this post, how greatly the choice of code will influence the speed.
Here's the challenge:
There are up to 26 different network terminals. They are labelled 'A' - 'Z' inclusive. A data file contains the information for how they are wired together. For example, 'AC' means terminal 'A' is wired to terminal 'C'. When two terminals are wired together, data can be transferred in both directions.
You are a computer hacker, hired by a network company to test the integrity of their network. They only need to ensure that 'A' and 'B' will always be able to transfer data to eachother. They believe that in a worst case scenario, a hacker, like yourself could knock down one connection.
Given the map to how all of the network terminals are connected, you must decide which one connection should be knocked down, in order to prevent 'A' from transmitting data to 'B'. In some situations, there may be more than one answer, and in some, no answers. Your algorithm must permit any of these possibilities, and output a response accordingly.
All network terminals, in their original condition, can be reached directly or indirectly through one another. In other words, if terminals 'A', 'B' and 'C' exist, then 'C' will be reachable through 'A', directly or indirectly. However, if the connection between 'A' and 'B' are disabled, then 'A' might not be able to connect to 'C' any more... if a route to 'C' no longer exists through 'A'.
The map for all of the connections between terminals will be in the following format. Each connection is separated by a newline, and the last line is '**' (since EOF is different between Windows and Linux).
AD AE AC BC DE EC **
The reason this challenge varies dramatically in programming abilities, is from your choice of algorithm. If you plan on doing a basic recursive algorithm that analyzes what each connection is doing, your program will be O(n^3). But that is fairly simple to accomplish! It is at approximately the level of grade 12 computer science.
However, if you want to do it the "best" way, in linear time, that requires third-year University Algorithms. Or... in my case, too much time on your hands!!
I won't tell you guys how to do it that way. I might give hints, but try to figure it out on your own, as I did.
Post back your thoughts and attempts here, I'll be glad to help anyone out. Remember, this is just for fun!