FlatLand Piano Movers

[Home]   [Puzzles & Projects]    [Delphi Techniques]   [Math topics]   [Library]   [Utilities]



Search WWW

Search DelphiForFun.org

As of October, 2016, Embarcadero is offering a free release of Delphi (Delphi 10.1 Berlin Starter Edition ).     There are a few restrictions, but it is a welcome step toward making more programmers aware of the joys of Delphi.  They do say "Offer may be withdrawn at any time", so don't delay if you want to check it out.  Please use the feedback link to let me know if the link stops working.


Support DFF - Shop

 If you shop at Amazon anyway,  consider using this link. We receive a few cents from each purchase.   Thanks.


Support DFF - Donate

 If you benefit from the website,  in terms of knowledge, entertainment value, or something otherwise useful, consider making a donation via PayPal  to help defray the costs.  (No PayPal account necessary to donate via credit card.)  Transaction is secure.


Feedback:  Send an e-mail with your comments about this program (or anything else).

Search DelphiForFun.org only




Problem Description

"FlatLand Piano Movers, as part of their Total Quality Management project, has decided to focus on the job estimation process. Part of this process involves walking the proposed paths that are to be used to move a piano to see if it will fit through corridors and around corners. "

"Now this is harder than it might seem, since FlatLand is a 2-dimensional world.  FlatLand pianos are rectangles of various sizes. FlatLand building codes require all turns in corridors to be right angle turns and prohibit ``T'' intersections. You can assume that each portion of a corridor is long enough so that other corners or doors into rooms don't have any effect on getting around a turn. You can also assume that the piano is narrower than the width of any corridor. "

"Note that the piano actually has to turn in the corner, since it can only be pushed or pulled on one of its shorter sides (there are no square pianos).  Your team's job is to write a program for a palmtop computer that will determine if a given piano will fit around a corner in a corridor. "

 (..... Info on input and output formats snipped)

Background & Techniques

Here's an interesting little problem from the 1989 Southern California Regional  ACM International Collegiate Programming Contest. 

We had to convert it from batch to interactive and add a few graphics of course.  I spent a  day trying to find an analytical solution to the problem but never quite got there.  Too many triangles inside of triangles.   So this is an empirical solution, i.e. turn the piano around the corner in small steps, keeping 2 piano corners against the outside of the corridor, and then check to see if the other side clears the inside corner.    

I really need a good tool that will let me draw an annotated diagram without spending half a day.  The best I have so far is a  pencil and paper, so here's a scanned diagram of the geometry.  It's not very readable, I had to reduce the size considerably, but maybe you can make some sense of it.   

I borrowed the Intersect function from the Tangram program to see if a line from the outside to inside corner of the corridor (Line2) intersects the lower long side of the piano (Line1).   If it does, all is well.  If not, then the bottom long side of the piano has tried to cut the the corner and the piano is stuck.   The diagram simply shows the derivation of the coordinates for Line1,  If A is the angle that the piano has been rotated from vertical (and the exterior corner of the corridors is at [0,0] then the lower corners of the piano are at [L*sin(A)+W*(cos(A), W*sin(A)]     and  [W*cos(A), L*cos(A)+W*sin(A)].   For corridors of width CW1 and CW2, the inside corner (the other end of line segment Line2,  is at [CW1,CW2].

There is some risk that the corner is clipped between 2 successive steps as we rotate around the corner and we miss that collision entirely.   I've made the number of steps a variable in order to eliminate  this as a practical issue, but it is would be a concern for any theoretical  solution.   Drawing the piano for many steps makes the turn images display as solid black, so I limited the drawing to every 10 degrees (or a collision) regardless of the number of steps checked.  

If anyone comes up with the math (and a readable diagram) for the analytical solution,  I sure would like to see it. 

Running/Exploring the Program 

Suggestions for Further Explorations

Find the analytical solution.  I'm thinking we want the equation for the perpendicular distance from the inside corner of the corridor to the nearest long side of the piano and then find the minimum value of that function.   If it stays positive, the piano clears the corner, otherwise it hits.    

  [Feedback]   [Newsletters (subscribe/view)] [About me]
Copyright 2000-2017, Gary Darby    All rights reserved.