[HN Gopher] The Prospero Challenge
___________________________________________________________________
The Prospero Challenge
Author : jstanley
Score : 50 points
Date : 2025-03-24 09:04 UTC (13 hours ago)
(HTM) web link (www.mattkeeter.com)
(TXT) w3m dump (www.mattkeeter.com)
| cfbolztereick wrote:
| This is really fun, I'm getting badly nerd sniped by this.
| 6stringmerc wrote:
| Whoa cool invocation of the magician Prospero! I recently adapted
| "The Tempest" as a screenplay while in jail and typed it up:
|
| https://samhenrycliff.medium.com/adapting-shakespeares-the-t...
| yoz wrote:
| Thanks so much for writing this up and sharing. It sounds like
| you've been through a horrific few years, but your perseverance
| in creativity is inspiring and fascinating. I wish you well in
| your efforts to make a better life for yourself, and I hope
| your work finds a wider audience.
| neverokay wrote:
| What compelled you in jail? I'm asking if there was more to it
| than just being bored.
| jstanley wrote:
| I'm thinking that we can parse the input into an expression tree,
| and then for each _x_ coordinate, have each node in the tree tell
| us which intervals of _y_ coordinates it would return a value <
| 0 (or <= 0 without loss of generality). Since we're basically
| dealing with real numbers we can pretend true 0 doesn't exist.
|
| Composing these intervals is trivial for all operations except
| addition/subtraction. (For example, `mul` is less than 0 if
| exactly one of its arguments is less than 0, `neg` is less than 0
| if its argument is _not_ less than 0, `min` less than 0 if either
| of its arguments is less than 0, etc.).
|
| And then we define _add(a, b)_ as _sub(a, neg(b))_. So then we
| only need to work out which y values _sub(a, b)_ will return a
| negative result for.
|
| _sub(a,b)_ is negative when _a <b_.
|
| We can have the _sub()_ node asks its 2 child nodes which values
| _they_ would return a negative result for. Every _y_ coordinate
| where _a_ gives a negative result and _b_ gives a positive result
| is a _y_ coordinate where _sub(a,b)_ is negative. Every _y_
| coordinate where _a_ is positive and _b_ is negative is positive.
| For the remaining _y_ values I think we have to actually evaluate
| the children and find out which ones give a negative result.
|
| Obviously memoise the evaluation so that we don't repeat any
| work, and turn the expression tree into a DAG by combining any
| identical nodes. Some subtrees won't contain _var-x_ , so the
| memoisation of those nodes can persist across different _x_
| coordinates.
|
| And then for each _x_ coordinate we ask the expression tree to
| tell us which _y_ coordinates give negative outputs, and plot
| those. It 's possible that the idea would generalise to
| 2-dimensional intervals, not sure.
|
| I haven't implemented this yet but I'm planning to try it out,
| but to be honest I don't expect it to be faster than Matt's GPU
| version based on recursive subdivision with interval arithmetic.
| Btw his talk is great
| https://www.youtube.com/watch?v=UxGxsGnbyJ4&t=80s
|
| And, a second fun challenge would be to reverse engineer the
| input file to extract the font! I expect the file is basically a
| union of x/y translations of functions that plot individual
| letters, so it shouldn't be _crazy_ hard to split out the top-
| level union, then split-out the x /y translations, and then
| collect the letters. It's possible that it's more complicated
| though. In particular, is each character translated in x/y
| individually, or is each character translated only in x to form
| each line of text, and then the line as a whole is translated in
| y? Or something weirder?
| zomglings wrote:
| Can you explain how you produce the opcodes from a text/image?
| iamwil wrote:
| the text contains a math expression. The math expression can be
| interpreted as an abstract syntax tree. The AST can also be
| translated into bytecode and interpreted by a stack-based
| virtual machine.
|
| The op-codes are where you do that translation from an AST into
| bytecode. The entire 2nd half of the crafting interpreters book
| will guide you through how it's done.
| https://craftinginterpreters.com/a-bytecode-virtual-machine....
| stevage wrote:
| > If you evaluate the expression with (x,y) values in the +-1
| square, then color pixels black or white based on their sign
|
| I do not understand what this means at all, particularly the bit
| before the comma.
|
| Can someone explain it differently?
| cjs_ac wrote:
| Yeah, this took me a while. Basically, the entire file
| represents a sort of assembly language for a function. You need
| to evaluate that entire function for each pixel in the output
| image.
|
| Each line starts with a line number (with a leading
| underscore). This is followed by an instruction, and zero, one,
| or two arguments. The arguments can be either floating point
| constants or integers (with leading underscores) which
| represent the results of those corresponding lines earlier in
| the function.
|
| The _x_ and _y_ coordinates of each pixel are loaded in the
| assembly language using the _var-x_ and _var-y_ instructions.
| jstanley wrote:
| Break down the range of x values from -1 to 1, and y values
| from -1 to 1, each into 1024 parts (or whatever resolution you
| want to plot at). Evaluate the function for each (x,y)
| coordinate. If the resulting number is negative colour the
| pixel white, otherwise colour it black.
|
| The expression is (probably) a 2d signed-distance function -
| https://en.wikipedia.org/wiki/Signed_distance_function
| stevage wrote:
| Ohh.. "the +/- 1 square" means a square of size 2 centred
| around the origin? That was way too terse for me.
| iamwil wrote:
| For a given (x, y), you color the pixel black if you're outside
| of a shape, and color the pixel white if you're inside the
| shape.
|
| The math formula is a way to describe the contour of the shape.
| To tell if you're inside or outside of a shape, you plug in
| your (x, y) coordinate into the math formula, and if the output
| is > 0, then you're outside. If the output is < 0, then you're
| inside.
|
| I think they call it a signed distance field. You should watch
| his talk that explain it. It's really great.
|
| https://www.youtube.com/watch?v=UxGxsGnbyJ4
| IshKebab wrote:
| Hash the input, if it matches the expected input output the
| expected image. Otherwise error.
|
| Technically correct.
| ainiriand wrote:
| This is why we can't have nice things.
| mkeeter wrote:
| Quoth the article: "Obviously, you could precompute the entire
| image, but that's against the spirit of the challenge"
| adrian17 wrote:
| > (Spoilers: it also allocates 60+ GB of RAM for intermediate
| results, so consider reducing the image size before running it on
| your own machine)
|
| The input algorithm is essentially written in SSA form, and it's
| easy to analyze when each "register" stops being used; then you
| can drop the arrays after their last use. Turns out the number of
| live registers never exceeds 160 at any point in time, and with
| this one addition the max memory usage drops to barely above 1GB.
| kevmo314 wrote:
| Nice challenge, I got it down to 0.5ms/frame.
| https://github.com/kevmo314/prospero.vm
| montag wrote:
| Impressive. Did you do all this in the past 2 hours?
| kevmo314 wrote:
| Yeah, it took me an hour-ish to get the performance and then
| an hour-ish to figure out how to actually render it
| correctly. I had never seen the P2/P5 PGM format before so I
| didn't realize P5 files were binary. :)
| ayastrebov2 wrote:
| Great idea and clean implementation! You seem to be
| interested in performance engineering - I did some work
| recently, check this out
| https://github.com/AlexanderYastrebov/wireguard-vanity-key
___________________________________________________________________
(page generated 2025-03-24 23:00 UTC)