Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <h2>The Idea</h2> <p>Define the set of <em>frozen</em> objects inductively as follows: </p> <ul> <li><p>An object touching the bottom is frozen.</p></li> <li><p>An object lying on a frozen object is frozen. </p></li> </ul> <p>Intuitively, exactly the frozen objects have reached their final place. Call the non-frozen objects <em>active</em>.</p> <p><strong>Claim</strong>: All active objects can fall one unit downwards simultaneously.</p> <p><strong>Proof</strong>: Of course, an active object will not hit another active object, since their relative position with respect to each other does not change. An active object will also not hit a frozen object. If that was so, then the active object was, in fact, frozen, because it was lying on a a frozen object. This contradicts our assumption.</p> <p>Our algorithm's very high-level pseudo-code would be as follows:</p> <pre><code>while (there are active objects): move active objects downwards simultaneously until one of them hits a frozen object update the status (active/frozen) of each object </code></pre> <p>Notice that at least one object becomes frozen in each iteration of the while loop. Also, every object becomes frozen exactly once. These observations would be used while analyzing the run-time complexity of the actual algorithm.</p> <h2>The Algorithm</h2> <p>We use the concept of <em>time</em> to improve the efficiency of most operations. The time is measured starting from 0, and every unit movement of the active objects take 1 unit time. Observe that, when we are at time <code>t</code>, the displacement of all the objects currently active at time <code>t</code>, is exactly <code>t</code> units downward.</p> <p>Note that in each column, the relative ordering of each cell is fixed. One of the implications of this is that each cell can directly stop at most one other cell from falling. This observation could be used to efficiently predict the time of the next collision. We can also get away with 'processing' every cell at most once.</p> <p>We index the columns starting from 1 and increasing from left to right; and the rows with height starting from 1. For ease of implementation, introduce a new object called <code>bottom</code> - which is the only object which is initially frozen and consists of all the cells at height 0. </p> <p><strong>Data Structures</strong> For an efficient implementation, we maintain the following data structures: </p> <ul> <li><p>An associative array <code>A</code> containing the final displacement of each cell. If a cell is active, its entry should be, say, <code>-1</code>.</p></li> <li><p>For each column <code>k</code>, we maintain the set <code>S_k</code> of the initial row numbers of active cells in column <code>k</code>. We need to be able to support successor queries and deletions on this set. We could use a Van Emde Boas tree, and answer every query in <code>O(log log H)</code>; where <code>H</code> is the height of the grid. Or, we could use a balanced binary search tree which can perform these operations in <code>O(log N)</code>; where <code>N</code> is the number of cells in column <code>k</code>.</p></li> <li><p>A priority queue <code>Q</code> which will store the the active cells with its key as the expected time of its future collision. Again, we could go for either a vEB tree for a query time of <code>O(log log H)</code> or a priority queue with <code>O(log N)</code> time per operation. </p></li> </ul> <p><strong>Implementation</strong></p> <p>The detailed pseudo-code of the algorithm follows:</p> <pre><code>Populate the S_k's with active cells Initialize Q to be an empty priority queue For every cell b in bottom: Push Q[b] = 0 while (Q is not empty): (x,t) = Q.extract_min() // the active cell x collides at time t Object O = parent_object(x) For every cell y in O: A[y] = t // freeze cell y at displacement t k = column(y) S_k.delete(y) a = S_k.successor(y) // find the only active cell that can collide with y if(a != nil): // find the expected time of the collision between a and y // note that both their positions are currently t + (their original height) coll_t = t + height(a) - height(y) - 1 Push/update Q[a] = coll_t </code></pre> <p>The final position of any object can be obtained by querying <code>A</code> for the displacement of any cell belonging to that object.</p> <h2>Running Time</h2> <p>We process and freeze every cell exactly once. We perform a constant number of lookups while freezing every cell. We assume <code>parent_object</code> lookup can be done in constant time. The complexity of the whole algorithm is <code>O(N log N)</code> or <code>O(N log log H)</code> depending on the data structures we use. Here, <code>N</code> is the total number of cells across all objects. </p>
    singulars
    1. This table or related slice is empty.
    1. POAlgorithm for falling grid items
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USbloops
    1. USbloops
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. POAlgorithm for falling grid items
      singulars
      1. PTQuestion
    1. This table or related slice is empty.
    1. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    1. COmaniek also got the idea and beat me to it. :)
      singulars
      1. PO
      1. USbloops
    2. COHe did, but you have expanded on the idea very well. Well done for a first answer! I'm not marking an answer yet until I can test some of these things. But your verbal exposition is convincing
      singulars
      1. PO
      1. USJoshua Honig
    3. COVery elegant, very well-explained, and well analyzed. Take my upvote!
      singulars
      1. PO
      1. USLi-aung Yip
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload