basil
Joined 18 years ago
Karma
3,300
Submissions
152
Member since
Oct 23
Programmer.
View on Hacker NewsRecent submissions
Comment · 3 days ago
I’ve been using graph theory for years professionally. A good example of practical uses of graph theory is any routing software. It is basically graphs all the way down.
For starters the whole street network is represented as a directed graph. The most widely used algorithm is the venerable A* to find paths through the vertices of the graph, not necessarily the shortest distance but the most optimal distance given all the trade-offs you wish based on the heuristics you define. There are lots of variations of A* and today most implementations would use its faster cousin: bidirectional A* which attacks the point-to-point calculation from both ends at the same time.
Then you have Dijkstra which is used for flood searches to e.g. give the best cost back home from every vertex so you know when to turn back the search if you have a search budget.
Menger’s theorem I’ve used in order to determine whether we can create a loop back. Basically search outwards, then search back without visiting those same edges.
Tarjan to ensure we identify all subnetworks so we don’t get stuck in a disconnected island of vertices with no way out to join the wider network.
A lot of these algorithms were conceived decades ago and are still the backbone of modern routing software.
One thing that’s constantly been in the back of my mind is, since routing is a highly deterministic problem space, it doesn't seem plausible that LLMs can take this over. It seems to me that it's a good example of a tool that LLMs would call out to rather than implement themselves.
In fact, see this convo I had with @simonw wherein he had Astra generate a jogging route. It setup a whole GIS stack and took about half an hour. That seems like a boil the ocean kind of approach and I’m not sure if that’s ever going to be optimal. https://x.com/baz_shkara/status/2099118620647305630
Comment · 2 months ago
Gamifying the map definitely helps to pull in contributors. StreetComplete got me editing more than anything else. I went a bit sideways with it: I used OSM data to build a territory game for cyclists, where you claim roads by riding them.
It's heavily processed OSM data with PostGIS. The fun part was figuring out how to decide what counts as a claimable road in the first place.
Comment · 2 months ago
Hey HN, excited to show you something I've been working on for a couple of years. I'm a passionate road cyclist and a former fruit company engineer. Today, there are two primary ways of knowing where to ride your bike: user-uploaded GPX files and generating routes via heatmap data. Both seemed inadequate to me after I was burnt countless times by being sent down high-speed roads or farm tracks.
When I want to go for a ride I have a specific time window in mind, and my goal is to get out and see nature and experience that unique feeling of freedom and joy that comes from riding a bike. So I built the tool of my dreams.
Remap reads the traffic levels, max speeds and road surface quality around you, then calibrates what road comfort means for your area. This leads to users getting comfortable routes out of the box automatically. Plenty of options are also available since cycling is a very opinionated sport.
The other important aspect of Remap is that it identifies what I've been calling 'lines' - sections of road that are excellent for cycling. Broadly speaking they need to be long, surrounded by nature and be away from traffic.
A great ride is full of lines, no ride is perfect end to end, but the more lines a ride has the better it feels. The other part of a great ride is that it should let you explore as wide as possible around where you start from, hit nature as much as possible, give you a climb here and there if you want, and not repeat any roads coming back - so it should ideally be a broad loop. Trying to fit all of this into an unpredictable road network with road rules and a set target distance alongside a large list of user-customisable routing preferences is a tall order, but I've succeeded in building something I'm immensely happy with, and I've been riding all summer with routes generated by Remap. It's been banger after banger ride.
Under the hood, it's a shared Rust core between web and iOS. Probably the most interesting part is route generation occurs locally on-device. I made this decision early on since I knew that this would be very expensive in terms of compute. The routing graph is a highly compressed columnar db that is able to be streamed directly to devices or browsers and be stitched across boundaries to provide a complete road graph. Routing tiles are fetched in Hilbert order so that multiple tiles in the same vicinity can be coalesced together. The architecture was inspired by Brandon Liu's pmtiles project which I'm a big fan of.
After the client has assembled its slice of the graph, it then explores it extensively. Much more deeply than traditional server-based routing software allows, since we have much more compute available we can examine all the side streets and roads that are relevant for delivering optimal bike routes. Using contraction hierarchies or some other optimisation designed for car navigation would defeat the purpose as bikes don't drop into arterials and then back out again like cars do.
The final point of Remap is that it makes solo riding social. You can't always schedule a group ride easily and whilst it's nice to ride solo, I often miss that social element. Since every ride built strings together lines, those lines are valuable and can be owned and claimed by players. The more you ride, the more 'watts' you earn to defend your lines.
I've got a full-time fuzzer going which hits up different cities and generates routes trying to catch out dive-bombs (unnecessary short detours), spurs (pointless out and back sections), various other anomolies. It's been running for a few weeks and caught some good bugs, but I'm really looking for real-world use right now. It's free to use, has a desktop and mobile site, as well as native iOS app. The native iOS app is fastest at route generation but the WASM isn't that far behind. Give it a go and let me know how you fare. Thanks HN!
Comment · 6 years ago
Some of the most complete Vim keybindings I've experienced in something that isn't Vim.
I love that visual character/line/block selection works. It's the first thing I test in any kind of Vim emulation.
Comment · 8 years ago
I normally use VRC (Vim REST Client) for testing and debugging APIs from within Vim. https://github.com/diepm/vim-rest-console
Pretty sure VRC uses curl under the hood to perform all requests. It’s great being able to use plain text within Vim to formulate and reuse API calls right next to your code.