User:LunaticFringe/Simulation problems

Oftentimes, contest problems are based around finding the optimal solution to a particular task. It could involve finding the shortest path from one point to another in a graph, solving a given puzzle in the fewest number of moves, or even using a more complex ranking system specified by the statement. Whatever the case, these problems usually ask you to find the "best" choice out of an extremely large, or even infinite, set of possibilities. Runtime considerations are often important in solving these questions, so it is important to look for generalized algorithms which can yield the answer as quickly as possible.

LinePlotter

Consider the following problem. On a plotter, the mechanical arm that draws on paper with a pen has a motor that can move it back and forth across the paper sideways. The plotter also has a paper motor, which can move the paper orthogonally to the plotter's arm, which effectively is like moving the pen up and down the paper. The paper is square, and is oriented so its lower edge is parallel to the arm. This allows the plotter to move to any coordinates using the two motors. Both motors can be active simultaneously, and each motor can move the pen up to one pixel per millisecond in relation to the paper (it's possible for a motor to run slower).

Given the list of up to 15 lines that the plotter must put on the paper, return the minimum time it takes to plot the given lines, in milliseconds. The plotter's pen starts at the coordinates (0,0), and after drawing all the lines, must return to (0,0). Note that the plotter cannot draw partial lines. Each element of lines will be in the form "x1 y1 x2 y2". This represents a line from point (x1,y1) to point (x2,y2). It takes 0 time to lower the pen down on the paper, and to raise it off the paper.

Example

lines = {"0 0 5 5", "5 5 0 5", "0 100 0 4"}

The best path first draws the line from (0,0) to (5,5). Since both motors can move at top speed, this line takes 5 milliseconds to draw. Without even picking up the pen, we can draw the line from (5,5) to (0,5) in 5 milliseconds. Finally, to draw the final line, we lift the pen, go all the way up to (0,100), and draw the line to (0,4). This adds 95 + 96 = 191 milliseconds. Finally, we lift the pen and move back to (0,0), adding an additional 4 milliseconds. The total time is 5 + 5 + 95 + 96 + 4 = 205 milliseconds.

Analysis

This problem is essentially asking us to find the best possible ordering of the lines, and to return the time it would take to draw them in this order. No matter what ordering we choose, the amount of time actually spent drawing the lines will be the same -- all that differs is the time it takes to get from the end of one line to the beginning of another. As for any problem, we should first examine the brute force solution to see if it is feasible. There can be up to 15 lines, which means there are 15! ways in which to order them. This would take far longer than the allowed time to compute, even if we forget the fact that each line can be drawn either forward or backward, which multiplies our previous total by 2^15. Clearly, we must find another approach.

Now let's examine the question from a simulation point of view. Say we already have some of the lines drawn, and are trying to figure out how much longer it will take to draw the rest of the picture. In this case, we are only concerned with two things: our current position on the paper, and which lines we have left to draw. For each line that we haven't yet drawn, we try drawing it both forward and backward, calling the function recursively. Our pseudocode would look something like this:

Function HowMuchLonger(CurrentPos, LinesLeft):
  For each line left to draw:
    Let P1 and P2 be this line's start and end points.
    Let T1 = GetTime(CurrentPos, P1) + GetTime(P1, P2) + HowMuchLonger(P2, LinesLeft)
    Let T2 = GetTime(CurrentPos, P2) + GetTime(P2, P1) + HowMuchLonger(P1, LinesLeft)
    If T1 or T2 is smaller than our best time found, update the best time.
  Return the best time found so far.