[HN Gopher] Bad Apple but it's 6,500 regexes that I search for i...
___________________________________________________________________
Bad Apple but it's 6,500 regexes that I search for in Vim
Author : vortex_ape
Score : 319 points
Date : 2025-01-12 15:13 UTC (7 hours ago)
(HTM) web link (eieio.games)
(TXT) w3m dump (eieio.games)
| perpetualchange wrote:
| Roughly how long did that take?
| jchw wrote:
| From the article:
|
| > I didn't have the time to find a good general-purpose
| algorithm: I was working on this the night before weekly
| presentations at the Recurse Center and I wanted to present it
| the next day!
|
| ...
|
| > I built this in a single day
|
| No estimate of hours, though.
| perpetualchange wrote:
| My browser was apparently bugged, and it didn't show the
| article the first time... I see it now and am going through
| it. Thanks for mentioning! :)
| eieio wrote:
| Hi! I'm the author.
|
| Like jchw said, this was a single-day project (although I did
| the writeup for it the next day).
|
| I went from 0-prototype in one sitting; I think that was around
| four or five hours of work? Then I went home, had dinner, and
| spent maybe three hours optimizing and cleaning it up.
|
| edit: I should say, i have done a lot of dumb things like this
| and I'm pretty sure it would have been at least a week of work
| for me 2 years ago. "making the computer do dumb stuff" is a
| skill like any other!
| perpetualchange wrote:
| Thanks for taking the time to respond, pretty impressive
| stuff!
| GZGavinZhao wrote:
| ... this is why we love bad apple!
| sltkr wrote:
| For the rectangle minimization problem: your problem seems to
| differ from the one discussed on StackOverflow in that the SO
| thread discusses partitioning into non-overlapping rectangles,
| while your Vim project allows overlap.
|
| I wouldn't be surprised if your problem turns out to be much
| easier to solve optimally.
| eieio wrote:
| oh this is a really good point! You're totally right, I had
| completely skipped over the fact that the rectangles were
| allowed to overlap. I think I'm probably done with this project
| / I'm pretty happy with the solution as it stands, but I think
| you're right that this simplifies the problem considerably.
| Thanks!
| vidarh wrote:
| I think my attempt would've been to flood fill to create an
| ordered list of spans, then use roughly the same method as
| the Lebesque integral, using the data from the flood fill as
| the function.
| rav wrote:
| Actually, from an algorithmic standpoint it's the opposite: the
| minimum cover problem (where overlap is allowed) is NP-hard
| whereas the minimum partition problem (where overlap is NOT
| allowed) has polynomial-time algorithms. "An Algorithm for
| Covering Polygons with Rectangles" by Franzblau and Kleitman
| 1984: https://core.ac.uk/download/pdf/82333912.pdf
|
| However, that's of course just an academic tangent - the
| theoretical results don't necessarily imply that one problem is
| easier than the other when you're just getting something to
| work for an afternoon project.
| rav wrote:
| Regarding the Vim macro that ends by going to the next line to be
| "replayable": You can also use the following command to run the
| macro once per line: :%norm @q
| eieio wrote:
| oh wow, TIL, I'm pretty surprised I didn't know this trick!
|
| back when I was vim golfing the normal solution was to make the
| macro recursive. So you'd record your macro, and you'd end it
| with '+@q' (move to next line and run the macro again). Then
| you run the macro once and it runs over every line.
|
| This ends up being really efficient in terms of keystrokes but
| in practice I think it's hard to think about and not very
| ergonomic, so I don't end up using it much. But it's a fun
| trick for golfing.
| rav wrote:
| There's also the no-macro solution where you just use ":%norm
| [series of keystrokes]" to run the given keystrokes on each
| line, but that comes with the added difficulty of not giving
| any visual feedback of what the keystrokes will do before you
| submit the entire line.
|
| One thing to keep in mind is that ":%norm" will place the
| cursor at the start of each line, before any indentation,
| whereas the trick of ending the macro with "+" will place the
| cursor at the start of each line after the indentation. But
| this can be worked around with ":%norm ^@q", using ^ to skip
| indentation before running macro q on each line.
| cryptonector wrote:
| Most often when I run a macro it's to change lines matching
| searches, so I just start the macro with the search (or `n`
| if the macro doesn't do additional searches) then I end the
| macro with `@q` (or whatever register), then execute the
| macro. I don't think I've ever had occasion to run a macro on
| every line, though I've had occasion to run macros over line
| ranges (but still, all matching a specific pattern).
| adityaathalye wrote:
| Hah, trust nolen to 1,000x something :))) I have used similar
| tactics in the past, but _separately_ and definitely not in one
| day! For the interested:
|
| - Bad Matrix (tput blocks to the terminal):
| https://www.evalapply.org/posts/bad-matrix/
|
| - Animating Text Art in Javascript (print text into fixed grid,
| flipbook-style): https://www.evalapply.org/posts/animate-text-
| art-javascript/...
|
| - oxo (format and print tic-tac-toe board to terminal, so I can
| regex-match for win/loss/draw results):
| https://github.com/adityaathalye/oxo/blob/7681e75edaeec5aa1f...
|
| But, I mean, that _Bad Apple_ takes the cake!
|
| (edit: add missing link)
| codeguro wrote:
| This is pretty cool! I like the creativity. The games this is
| based on are pretty good too. Danmaku are hypnotic
| 29athrowaway wrote:
| The people running Doom or Bad Apple in different unexpected ways
| are such champs.
|
| There are some really interesting ones, like running Doom on a
| pregnancy test.
| saagarjha wrote:
| Strongly disagree on that one; it was basically Doom on some
| random microcontroller stuffed into a pregnancy test shell.
| jordigh wrote:
| The pregnancy test was the greatest drama to ever hit the
| r/itrunsdoom community.
| 29athrowaway wrote:
| Good point
| PaulHoule wrote:
| These were on sale last month
|
| https://us.govee.com/products/govee-curtain-lights
|
| and my understanding is that you can upload an animated GIF to
| it... I just added making a "bad apple" GIF for it to my Kanban
| board though I don't know how much memory the device has and how
| well I can get it to work.
|
| (Sometimes that part where Remmy Scarlet spreads her wings still
| makes chills go down my spine)
| nokeya wrote:
| Someone definitely need to shoot Bad Apple using a kanban
| board!
| 3eb7988a1663 wrote:
| The parallel candidate solution generator is such a good idea,
| but it usually takes me a long time to realize I do not need to
| make the uber algorithm. Just one-more-tweak, and I _know_ that I
| can make this solution work in all cases!
| eieio wrote:
| it's probably my single favorite trick for making a prototype
| performant enough! I'm delighted every time that it works.
|
| but agree that it can be really hard to take a step back and
| realize that you can employ it instead of writing something
| "perfect"
| jordigh wrote:
| The tech demo that really made me fall in love with Bad Apple was
| getting it to run on the NES.
|
| https://somethingnerdy.com/downloads/
|
| Here it is running from my Everdrive.
|
| https://inversethought.com/jordi/video/badapple.mp4
|
| Yes, with full audio. It's about one gigabyte of data. On a
| system where the typical game size is no more than a couple
| hundred kilobytes, and your CPU only has three 8-bit registers
| for you to do any calculation with.
| junon wrote:
| Very cool. Having done a bit of NES dev I can imagine this
| wasn't super straightforward to make performant for the
| graphics, given you can typically only have a few sprites on a
| row before the NES starts to 'dissolve' them (not sure the
| term).
|
| I wonder if it's using the background tile map for this instead
| of sprites, though that's also an impressive amount of graphics
| bandwidth.
|
| > with full audio playback rate (44.2kHz)
|
| The audio being so clear is also impressive, is that something
| that the card extends? IIRC the PCM channel on the NES isn't
| anywhere near that bitrate, and is also 8-bit sample size.
| manosyja wrote:
| I remember watching the Soccer World Cup 2006 at work. I logged
| in my home server via ssh and could watch it in the terminal. Not
| enough bandwidth for something else.
| lupire wrote:
| As the author admits, it's Vim but it's not regexes. It's
| "searching" for screen coordinates.
|
| It's drawing in Vim, but not pattern matching.
___________________________________________________________________
(page generated 2025-01-12 23:00 UTC)