{"id":2452,"date":"2018-09-29T19:18:25","date_gmt":"2018-09-30T00:18:25","guid":{"rendered":"https:\/\/laurentlessard.com\/bookproofs\/?p=2452"},"modified":"2018-09-30T11:00:21","modified_gmt":"2018-09-30T16:00:21","slug":"pool-hall-robots","status":"publish","type":"post","link":"https:\/\/laurentlessard.com\/bookproofs\/pool-hall-robots\/","title":{"rendered":"Pool hall robots"},"content":{"rendered":"

This Riddler puzzle<\/a> is about arranging pool balls using a robot!<\/p>\n

\nYou own a start-up, RoboRackers\u2122, that makes robots that can rack pool balls. To operate the robot, you give it a template, such as the one shown below. (The template only recognizes the differences among stripes, solids and the eight ball. None of the other numbers matters.)<\/p>\n

\"source:<\/p>\n

First, the robot randomly corrals all of the balls into the wooden triangle. From there, the robot can either swap the location of two balls or rotate the entire rack 120 degrees in either direction. The robot continues performing these operations until the balls\u2019 formation matches the template, and it always uses the fewest number of operations possible to do so.<\/p>\n

Using the template given above \u2014 a correct rack for a standard game of eight-ball \u2014 what is the maximum number of operations the robot would perform? What starting position would yield this? How about the average number of operations?<\/p>\n

Extra credit: What is the maximum number of operations the robot would perform using any template? Which template and starting position would yield this?\n<\/p><\/blockquote>\n

Here is my solution:
\n[Show Solution]<\/a><\/p>\n

\n

One way to think about this problem is as a graph. Imagine each vertex of the graph corresponds to a different arrangement of the pool balls, and we add an edge connecting two different arrangements if it’s possible to transition from one to the other in one move (either with a swap or a rotation). Then, the problem becomes: “which vertex in the graph is farthest in path-length from the target vertex?”. When two vertices are connected by an edge, we’ll call them “neighbors”. Note that the edges in this graph are bi-directional because all the moves are reversible.<\/p>\n

Our general approach will be to label each vertex with a whole number that corresponds to the smallest number of moves required to reach the target vertex. In effect, we are computing what is called the graph eccentricity<\/a> of the target vertex. <\/p>\n

Here is a greedy approach that achieves the desired labeling.<\/p>\n

    \n
  1. Create the graph by enumerating all possible unique arrangements of pool balls and adding an edge between each pair that are one move apart.\n
  2. Label the target vertex “0”. Then set $i=0$ and:\n
  3. For each vertex with label $i$, visit all of its neighbors. For each of those neighbors that is currently unlabeled, assign it the label $i+1$.\n
  4. Set $i\\mapsto i+1$ and repeat from Step 3 until all vertices in the graph have been labeled.\n<\/ol>\n

    Now that all vertices have been labeled, the vertices with maximal label correspond to those that require the most moves to be reached. In order to reconstruct the path back to the target vertex, we go in reverse order:<\/p>\n

      \n
    1. Call the maximum label $d$. Then pick any vertex with label $d$. Call this the “current vertex”. Set $i=d$ and repeat:\n
    2. Enumerate the neighbors of the current vertex and pick any of them that has label $i-1$.\n
    3. Add the newly chosen vertex to the path and set it to be the new current vertex.\n
    4. Set $i\\mapsto i-1$ and repeat from Step 2 until we reach $i=0$.\n<\/ol>\n

      And it’s as simple as that! Note that we must<\/em> do the second sequence in reverse. If we try to start from the target and work our way towards one of maximum-label vertices, there is no guarantee that we’ll be able to pick a valid max-length path because some paths will end in dead ends (they will not be max-length). When we work in reverse, however, all paths with decreasing labels must find their way back to the target because of how the labeling was constructed.<\/p>\n

      The approach I described above is a variant of , which is a popular method for solving recursively defined problems.<\/p>\n

      Numerical solution<\/h3>\n

      I coded up the procedure above and here is what I found:<\/p>\n