## Posts

Showing posts from June, 2012
Shortest Prime Path Two numbers a and b are said to be “primaly” connected (a --> b) iif: a<b and a+b is a prime number. A prime path between two numbers a and b is the path of primaly connected numbers from a to b. Given two numbers a and b (1<=a<b<=15000), write an algorithm to find the shortest prime path between a and b. Input will be given as a file names primepath_input.txt containing a pair of numbers per line representing a and b. End of file will be represented by 0 0. Example: 1 10 10854 10891 4 5 1 15000 0 0 Output should be a file named primepath_output.txt with one result per line for each corresponding line in the input file (except for the 0 0 input). The code should either return one shortest path between a and b when it exists, or “no solution” in case there isn’t a prime path between a and b: Shortest prime path from 1 to 10: 1 10 Shortest prime path from 10854 to 10891: 10854 10859 10868 10869 10882 10891 Shortest prime path from 4 to 5:
Solution to the "Pipe" problem, http://acm.tju.edu.cn/toj/showp1005.html , in C#. This was a complicated problem to solve, mainly because the calculations around the bending points, as well as the floating point errors in the calculation. It becomes important to break the problem down into as many small classes and functions as possible. The corner cases are the killers here. The approach is to realize that you only need to try 10K different lights thru a pipe of no more than 40 segments (400K computations per input). The hairy code is the one inside the Pipe.cs class to deal with the bending points. It worked for the input given, but I’m not 100% sure it will work for all the inputs since I only had this input to play with: InputHandler.cs using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.IO; namespace Pipe {     class InputHandler     {         private FileInfo fi = null;         private StreamReader sr = null;         pr