(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.
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.
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!
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.
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 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.)