16
\$\begingroup\$

In this challenge you must write a computer program that creates a stack of a thousand identical \$1 \times 1\$ frictionless homogeneous blocks such that each block is supported and the stack is stable under gravity when placed on the edge of a table which spans from \$x = -\infty\$ to \$0\$ horizontally, with the surface at \$y = 0\$. The winning criterion is the amount of overhang you manage to create, that is, the \$x\$ coordinate of the rightmost edge of the stack. Highest overhang wins.

This problem is analyzed in Overhang by Mike Paterson and Uri Zwick. Using their algorithm I wrote a judging program in Python that given a list of \$(x, y)\$ coordinates of the bottom left corners of the blocks returns whether the solution is valid and how much overhang it achieves. You will need Python 3 and the pulp library to run this program. You can get the latter using python3 -m pip install --user pulp. The program expects one pair of coordinates per line, separated by whitespace, on stdin.

To prevent rounding issues the judging program rounds the \$x\$ coordinates to six decimal places (and the \$y\$ coordinates are expected to be non-negative integers). Your answer must include (a link to) a list of coordinates that passes the judging program, and contain the score it reports. Yes, this does mean you need to be able to run your program to completion to get your output—you can't get away with "end of the universe" brute force.

As an example, the optimal stack with thirty blocks (2.70909 units of overhang):

optimal stack with 30 blocks

Note that since the blocks are homogeneous and frictionless all forces are strictly vertical (in a balanced stack) and the actual width : height ratio of the blocks does not matter, so for clarity the blocks are shown elongated.

Improve this question
\$\endgroup\$
6
  • \$\begingroup\$ If an optimal solution exists, how can different answers compete? To explain another way, if someone finds a better overhang than mine, I can just copy their approach. \$\endgroup\$ Commented Aug 12, 2021 at 20:29
  • \$\begingroup\$ @Etheryte I don't expect anyone to solve the problem optimally. If they do, the site-wide tiebreaker applies where the earlier answer wins. \$\endgroup\$ Commented Aug 12, 2021 at 20:32
  • \$\begingroup\$ @Etheryte Challenges that can somewhat be abused by using more computer time/power happen every so often, but the way they tend to play out is that people will only post new answers if they add something relatively novel to another algorithm (in this case, it would probably visually change some part of the stacking noticeably). If someone posts a mostly copied solution, you can use the downvote button for its intended purpose! \$\endgroup\$ Commented Aug 12, 2021 at 20:37
  • 1
    \$\begingroup\$ @Jonah the article does not provide an optimal solution, although it does provide a method that is a constant factor away from one.e \$\endgroup\$ Commented Aug 13, 2021 at 3:51
  • 1
    \$\begingroup\$ @Aiden4 I'd just like to note since the challenge concerns itself with a specific problem size (\$n = 1000\$), that any method would be a constant factor away from optimal. \$\endgroup\$ Commented Aug 13, 2021 at 10:00

1 Answer 1

Reset to default
8
\$\begingroup\$

Python 3, 3.742717 units

I figured just to get something out there I'd implement the harmonic stack, it's a pretty bad algorithm but being the first submitter that makes me the current winner ;)

stack.py

# Number of blocks N = 1000 # Evaluate 0.5*H(n) def harmonic(): h = 0 i = 0 yield 0 # Avoid divide by zero errors by defining H(0) to be 0 while True: i += 1 # Stupid rounding error means we need to divide by *sliightly* more than 2 h += 1/(2.00000202478*i) yield h # Generators are sexy # Get the harmonic number up to N def nth_harmonic(n): return next(x for i,x in enumerate(harmonic()) if i==n) def main(): # Calculate the block offset offset = nth_harmonic(N) - 1 for i, x in enumerate(harmonic()): # Spit the 6 decimal place formatted value to stdout along with the height print(format(offset - x, '.6f'), N - 1 - i) if i == N - 1: # We gotta stop at some point break if __name__ == "__main__": main()
Improve this answer
\$\endgroup\$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.