danvk

Is the video episode for this up somewhere? It can be hard to find old PBS shows, even from just a few years ago.

You might also like webdiff, which does something similar https://github.com/danvk/webdiff (I built this years ago and still use it every day.)

(author here) Just to be clear, none of the photos were ever human-located. The system this replaced was, roughly, regular expression + Google Maps geocoding API. The only photos located by hand were the ~200 I used for my test set: https://github.com/danvk/oldnyc/blob/master/data/geocode/out...

(Author here) IIUC you're saying that 707133f-a should be at 5th Ave & 9th Street, not 5th Ave & Union Street? Can you say more about why? The text on the back of the first image says "Union St. Station, 5th Ave," which is how it winds up at there. On the other hand, the NYPL page[1] titles the image "Union St. - 18th St."

(I briefly got excited that there might be a street sign _in_ the photo, but if you zoom way in it says "DENTIST")

+1 to 1940s.nyc. Very different photos — those are were taken for tax assessment, the ones on OldNYC were taken to document the city as it changed. The photographer had an arrangement where he'd get tips from demolition crews, and go shoot buildings before they were gone forever.

[1] https://digitalcollections.nypl.org/items/5a5e06a0-c539-012f...

Yes. You can give pickType a type in TS. Something like pickType<B extends boolean>(b: B): B extends true ? string : number.

I’d love to read a post explaining how TS conditional types are or are not a form of dependent types. Or, I’d like to understand dependent types well enough to write that post.

It's open source, take a crack at it! Or file an issue requesting it.

This analysis doesn't make use of the Boggle dice. It assumes that any cell can be any letter. In practice, all high-scoring boards can be rolled with the Boggle dice. My code does assume the letters are A-Z, though, so the Ñ die in Spanish Boggle would require some code changes.

Finding the highest-scoring board with a 16- or 17-letter word is a fun, but very different problem. There are few enough "Hamiltonian paths" through the all the letters on a 4x4 Boggle board (~68,000) and few enough 16 letter words (~2,000) that you can enumerate all pairs in an hour or two.

Depending on wordlist and whether you want a 16 or 17 letter word, you get "charitablenesses", "supernaturalised" (British spelling), "quadricentennials" or "quartermistresses". These boards all score considerably lower than the REPLASTERING board. Full results here: https://github.com/danvk/hybrid-boggle/#highest-scoring-boar...

I hadn't realized until I did this "side quest" that most wordlists top out at 15 letter words. That makes sense for a Scrabble dictionary, but it's not great for Boggle.

There are simpler ways to calculate a bound that don’t involve trees. You can read about the sum and max bounds in the WIP paper: https://github.com/danvk/hybrid-boggle/blob/main/paper

There are some examples in these old posts:

- https://www.danvk.org/wp/2009-08-08/breaking-3x3-boggle/inde...

- https://www.danvk.org/wp/2009-08-11/a-few-more-boggle-exampl...

These bounds are pretty effective at finding the global max for 3x3 Boggle, but 4x4 is a lot bigger.

There is a mapping from Boggle optimization to ILP, but I’ve seen no evidence that this is an efficient way to solve it. I’ve been told that branch and cut is usually better than branch and bound, but I don’t know whether it’s applicable to Boggle.

I have been surprised that the Boggle code runs about 4x slower on the GCP machine than on my M2 MacBook. I don’t have enough experience running CPU- and RAM-intensive cloud jobs to know whether this is normal.

“As far as I can tell, I’m the only person who is actually interested in this problem,” Vanderkam said.

For context, many people are interested in finding high-scoring Boggle boards, usually via simulated annealing, hillclimbing, or genetic algorithms. But so far as I can tell, I'm the only one interested in _proving_ that a particular board is best. Doing that was the new result here.

"Lone coder" here. I reached out to Ollie (the FT reporter) because he'd written a book (Seven Games) about computers and games, so I thought the Boggle story might interest him. It did!

Your best bet in that case is to store the dictionary in a Trie or DAWG structure that can be mmapped directly from disk.

Sorry, but this doesn’t pass the smell test. The article mentions 200,000 random 4x4 boards/second on a single core on an M2. That’s a ~4GHz chip. So ~20,000 ops/board. There are 200,000 words in the dictionary. You can’t possibly do something for every word in the dictionary, it would be too slow.

It sounds like your Trie implementation had a bug or inefficiency.

You can see all the wordlists I used here: https://github.com/danvk/hybrid-boggle/tree/main/wordlists

The proof used ENABLE2K — repeating it for other wordlists would require another ~23,000 CPU hours each.

Great! Feel free to reach out -- my email isn't hard to find.

If you want to give it a try, I'd love to hear if that's the case! It's deleted in the repo now, but here's code to generate a spec for an ILP solver: https://github.com/danvk/hybrid-boggle/blob/62d3f01aed802734...

One interesting thing about Boggle is that the number of variables (16 cells) is very small compared to the number of coefficients on how they combine (the number of possible words).

Annealing is mentioned a few times in the post but not discussed in any detail. I found that hill climbing with an expanded "pool" of boards and exhaustive search of neighbors was the most reliable way to get from a random starting point to the highest-scoring board: https://github.com/danvk/hybrid-boggle/blob/main/boggle/hill...

I actually did try ILP, see https://stackoverflow.com/questions/79422270/why-is-my-z3-an...

I tried Z3 and OR Tools. I didn't try Gurobi. But this was enough to make me think ILP was a dead end. (There were a lot of dead ends in this project.)

I don't know much about integer programming, though, and I'd love to be proven wrong.

We built a visualization along these lines at Sidewalk Labs back in 2017. It's open source if you're interested in playing around with it: https://github.com/sidewalklabs/router

I particularly liked the multimodal comparison feature. It lets you answer questions like "where does the bus help me get to faster than the subway?" (Answer: basically nowhere.)

I have not, but that's a great idea!

I've had really good luck recently running OCR over a corpus of images using gpt-4o. The most important thing I realized was that non-fancy data prep is still important, even with fancy LLMs. Cropping my images to just the text (excluding any borders) and increasing the contrast of the image helped enormously. (I wrote about this in 2015 and this post still holds up well with GPT: https://www.danvk.org/2015/01/07/finding-blocks-of-text-in-a...).

I also found that giving GPT at most a few paragraphs at a time worked better than giving it whole pages. Shorter text = less chance to hallucinate.

Try webdiff (I’m the author) https://pypi.org/project/webdiff/

Since function parameters are immutable in Zig, is this a difference that you need to care about?

For tuples, not for named fields.

Thanks for the pointer, I hadn't run across ts-runtime-checks before. It does do something similar to what I propose in the post. The difference is that ts-runtime-checks is opt-in. If you want a type validated at runtime, you have to write `Assert<T>`. What I'm proposing is that _all_ types be validated at runtime.

opt-in makes sense if you want these checks in production. The appeal of a "check everything" debug mode is that you wouldn't have to modify your TS at all to use it.

Destructuring assignment was definitely something I missed in Zig (it's even called out in the post). Here's the relevant issue/comment, which makes me think this won't happen in Zig: https://github.com/ziglang/zig/issues/3897#issuecomment-7389...

Yes, the error is much clearer when you realize where the mistake is :)

There's an interesting point here, though: while comptime lets Zig unify function calls and generic type instantiation, this also creates the possibility of confusing the two and getting confusing error messages.

Extensive. Try reading the full post, you'll see that those points are all mentioned.

You can work around this by typing your import statement inside-out:

import {} from 'fs';

Then move your cursor back inside the {} and you'll have nice autocomplete. Works with object destructuring, too.

Or 2037.