[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 : 563 points
Date : 2025-01-12 15:13 UTC (1 days 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!
| panzi wrote:
| Doing that in a single day is impressive. Took me two days to
| do my much simpler version that just prints it using Unicode
| symbols for legacy computing.
| 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.
| Izkata wrote:
| Related to that, macros are just recorded into normal
| registers. You can get it out with: "qp
|
| Edit it, and put it back into the register with
| "qdd
| rav wrote:
| Heads up - you should use "qD instead of "qdd to avoid an
| extra newline at the end of the register contents. (In
| fact the current Vim 9.1.954 behavior seems a bit odd in
| that it moves the cursor down, but not to the start of
| the line, as if j is pressed... Seems like a bug to me.)
| Izkata wrote:
| And D goes from cursor to end of line instead of the
| whole line. Wasn't sure how complicated I wanted the
| description to be.
| 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).
| rav wrote:
| To run a macro on the start of each line matching your
| search, you can use: :g//norm @q
|
| Here, g// repeats the most recent search, and norm @q runs
| the q macro on each matched line. This is not quite the
| same as starting the macro with a search, since the cursor
| is at the start of the line and not at the start of the
| match, but it's often good enough.
|
| You can also restrict it to just the matches inside a range
| of lines: First select the lines in visual mode, then type
| :g//norm @q, which will cause Vim to insert a range before
| g, as in: :'<,'>g//norm @q, which means "between line '<
| and '>, find lines containing a match of the most recent
| search, and run @q on each such line".
| 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)
| DiggyJohnson wrote:
| Ahaha `oxo` is an unhinged project to actually execute. Thanks
| for sharing all of these projects.
|
| Brb forking and integrating ascii-text third party ads
| 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!
| PaulHoule wrote:
| Another project on my Kanban board is a plan to big spread of
| Touhou characters linked with QR codes. Here's a prototype
| card
|
| https://bsky.app/profile/up-8.bsky.social/post/3lbqfh7pesc2x
|
| and the spreads I make are like
|
| https://bsky.app/profile/up-8.bsky.social/post/3latxcwmkpk2w
|
| I have a list of 20 that I need to fill out a little (somehow
| I missed Koakuma) and then I have to have my image sorter
| find a good set of images that fit together stylistically. (A
| friend of mine was talking about how RA's in dorms would make
| picture sets for all the rooms, seemed to me Touhou would be
| the ultimate basis for this)
| nl wrote:
| I have one of these curtain lights and they are great!
| a_t48 wrote:
| I've done this with Twinkly lights, but the lights sadly don't
| have enough memory to run more than a few seconds.
| panki27 wrote:
| I have a GIF of Bad Apple at 64x32, just under 1MB.
|
| Big shout out to https://ezgif.com/ !
| 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.
| Dylan16807 wrote:
| The channel can either play back delta-modulation samples
| from memory, _or_ you can directly set the output as a 7 bit
| value.
|
| So by burning a lot of CPU cycles, you can keep up a
| perfectly good sample rate using the latter method.
| godd2 wrote:
| The bitrate of the PCM is determined based on how quickly you
| can write a byte to the register. The fastest you could write
| general data is once every 6 cycles, which gives ~298 MHz of
| sample rate, so 44.2 kHz is easily doable if that's all you
| want to do with the CPU.
| godd2 wrote:
| > I wonder if it's using the background tile map for this
| instead of sprites
|
| Yes, it's all background tiles being loaded continuously from
| the SD card. We created the tiles with a custom tile de-
| maker.
| eieio wrote:
| This is really neat - did you do any kind of writeup on it? I'd
| love to read it if you did.
| jordigh wrote:
| It's not my work. I'm just a script kitty.
|
| There are some details in the description and comments here.
|
| https://www.youtube.com/watch?v=WPUYjDNks9Y
| panzi wrote:
| That is glorious!
| Wii2 wrote:
| Depending on what aspects of that you enjoyed, you might also
| enjoy this similar Bad Apple implementation on the NES. With
| the extra challenge of it being done through ACE in Super Mario
| Bros. and all data being streamed in through the controller.
| https://www.youtube.com/watch?v=lfG8DbxFibY
|
| They also made an accompanying breakdown video.
| https://www.youtube.com/watch?v=Wa0u1CjGtEQ
| 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.
| krick wrote:
| I never get tired of Bad Apple. The best thing on the internet.
| And almost every time I get somewhat jealous I didn't come up
| with that idea myself.
|
| Also, I really like how footnotes are implemented in this blog. I
| guess I'm gonna steal it.
| eieio wrote:
| I stole the footnotes from my very talented friend Jake
| (https://jakelazaroff.com/), whose work you might have seen on
| here in the past. Note that they're sidenotes on large screens
| but on small ones they swap to inline footnotes that expand
| when you click on them.
|
| Anyway steal away!!
| panzi wrote:
| This is amazing! Also made me write my own version for the
| terminal using legacy symbols for computing:
|
| https://youtu.be/lDLFhQTFcTk
|
| Details: https://github.com/panzi/bad-apple-terminal
| sharyphil wrote:
| Awesome. One can never have enough Bad Apples!
___________________________________________________________________
(page generated 2025-01-13 23:01 UTC)