CodeJam: Solving Cubic UFO Using the Cube Shadow Theorem

By rschaefertech

Google hosts a CodeJam competition for anyone to compete solving computational problems. This post outlines my attempt at a solution for the Cubic UFO Problem. If you would like to follow the code along with the solution description, it can be viewed with this gist.

Disclaimer: I am a novice at linear algebra. This is most likely not the best way to solve the problem.

Problem summary

Imagine a unit cube (a cube with each side of length 1) floating above the xy plane. Given an Area A, how could you rotate the cube such that the projection onto the xy plane (shadow) is equal to the given area? The output is three vectors that describe the center points of three faces of the cube.

Background information

I have a pretty shallow understanding of linear algebra. My only exposure was an introductory class taken pass-fail for fun while studying abroad that was not required for my degree which I could have paid more attention to.

After googling some topics around the problem, I read about the unit cube shadow theorem. The theorem says for 3-dimensions that the area of a projection of a unit cube onto two-dimensional space is equivalent to the length of the projection onto the third coordinate axis. For this problem then, the area of the shadow on the xy-plane is equal to the length of the projection onto the z-axis.

So given a length (area), how can we take this information and transform it into a cube rotation? To solve this problem, we will calculate a rotation matrix necessary to move a corner to the correct height. We then will apply this rotation matrix to the vectors that describe the center points of the original  position of the faces of the cube to get the vectors necessary to answer the problem.

Corner Vectors Calculation

The length of the projection onto the z-axis is simply the difference between the z coordinate of the highest and lowest corner of a cube. Also, if you imagine tilting one corner of the cube up, the opposite corner of the cube will go down. If the cube is centered at the origin, the z-coordinate of the highest corner of the cube must be A/2, which also means the z coordinate of the lowest corner will be at -A/2, giving a total length of A. We pick the corner to rotate arbitrarily as the corner in the positive xyz octant. Next, we can calculate a destination vector which meets the requirement of having a z coordinate of A/2.

Defining a vector of the starting point of the corner is easy: \left (0.5,0.5,0.5 \right ). To determine the destination vector describing the final position of the corner, picture all the points that the corner could be located while the center of the cube is centered at the origin. The shape describing the possible positions of the corner is the surface of a sphere centered at the origin with a radius equal to the magnitude of the corner vector.

If we restrict the z-coordinate of the corner to A/2, the possible positions then become a circle on the xy-plane at height A/2. Arbitrarily we will pick a point on this circle with y = 0. The magnitude of the vector to this point is the radius of the sphere (magnitude of the corner vector). The z-coordinate is the height A/2, the y-coordinate we just set to zero, and the x-coordinate can be calculated using Pythagorean’s Theorem. The destination vector is \left ( \sqrt[]{radius^2-(A/2)^2},0, A/2 \right )

Rotation Matrix

A rotation matrix is a matrix that when multiplied with a vector will rotate the vector in Euclidean space. A rotation matrix can be calculated that describes the rotation necessary to rotate the corner vector to the destination vector. One method of describing the rotation is to use the axis-angle representation. Given the two vectors, the axis of rotation is the cross-product of the two vectors. The angle between the vectors can be calculated using the dot-product and inverse sine.

The axis and angle can then be turned into a rotation matrix using quaternions. (Admittedly, I don’t know how these equations are derived). The calculation of the rotation matrix can be optimized by removing the extra translation from sin(theta) and cos(theta) to angle and back again if using unit vectors during the axis-angle calculation.

Multiplying a vector by a rotation matrix gives you it’s final destination. Taking this rotation matrix then and multiplying each vector describing the original faces (or a matrix with each vector as a column) will give us the final locations of the faces.

The code I submitted unfortunately did not pass the CodeJam grading. I am unsure if my calculations were not accurate enough or were entirely wrong. I did find it useful to enter the output vectors here to visualize the answer. If you find an error or can tell me why this solution did not work, please let me know!

Edit: Thanks to a helpful comment from reddit, apparently the shadow is supposed to be on the xz-plane, and switching the x and y coordinates of the output would fix this problem.

If you would like additional methods to solving this question, a Stack Overflow question has multiple answers