Hacker Newsnew | past | comments | ask | show | jobs | submit | basil's commentslogin

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


> seems like a boil the ocean kind of approach and I’m not sure if that’s ever going to be optimal

Finding the most optimal traveling salesman problem for 20 cities by brute force will take a few universes lifetimes and you still won’t be halls way. You’ll need to compromise with heuristics but that usually leads to near optimal


Although the simplest exact algorithm for TSP is O(n!), you can use dynamic programming to get the difficulty down to O(n^2 * 2^n), which is quite tractable at n=20.

However, sometimes you can construct exact solutions to much larger real-world data sets (tens of thousands of points) by exploiting structure in those graphs.


See my other comment. I feel stupid now


It depends on what you mean by brute force, you can easily do 20 cities with dynamic programming, which essentially is brute force with pruning.


:faceslap:

I was always under the impression that by pruning you could only find the lowest bound on a branch but it wouldn't lead to the optimal path. TIL!


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.

https://remap.earth


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!


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.


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.


306 - JavaScript for Automation


GitHub isn't a 'single point of failure' due to the distributed nature of Git. I.e. it's pretty easy to push your codebase to another server anytime you want.

If this service backs up submodules for 3rd party dependancies this might be useful but as it stands the landing page doesn't give any further information. I don't feel incentivised to login with GitHub OAuth.


After popcorn time and the trouble finding the most up to date copy of the code (that wasn't modified), I'm not so sure.


Ultimately, didn't popcorn time get removed by its own maintainers?


Sorry to hear about this, but don't let it dishearten you from making games and open sourcing them.

Someone stealing your code doesn't take away from the fact that you accomplished your goal of making a complete game. And from what you just wrote - that was your intention.

Regarding your blog title, I'd add 'timing' as well as 'marketing'. Titles of both submissions were remarkably similar ("Flappy Bird in HTML5" vs "Flappy Birdy html5 clone created using the Phaser framework"). Maybe the timing of your submission was off.

Also you can now state that you're the original creator of all the HTML5 Flappy Bird clones that have been popping up recently.


I was ecstatic to see the other forks but my smile does a 360 everytime I see him getting the credit for it. But I'm happy to report that it didn't discourage me to open source the things I create: https://github.com/marksteve/val :)

Yeah. My timing was off. But I think I now have a better idea on when and how to post things here :P

I can't claim that :P There are some good clones that were genuinely created from scratch like mine.


I wondered about that as well - I guess US evening time is a sweet spot? I'm european, so I have no clue really.


Title was too long. Try to keep it short and sweet.


I would also add "luck". Submitting to HN is really a hit and miss thing, and it shouldn't be the only way you promote your things.


Yeah. Luck is a factor as well. Unfortunately, I don't have a good following so it's my best way to get attention :))


I used to be in that situation which is why I wrote Bee (http://neat.io/bee/). Its a Mac client for JIRA (amongst other services) and makes JIRA much more pleasant to use.

JIRA's UI tends to be geared towards project management types. I wanted to bring the focus back onto the engineer.


Happy to know about Bee. Trying it right now.

However, Jira fundamentally is about managers tracking work, and not about workers actually getting stuff done. There's no way I can track all my tasks in Jira even if I have a nicer GUI for it.

I'm actually part of the way towards writing a program to sync tasks between Asana and Jira using their APIs. I'm hoping that that'll let me continue working in Asana while it handles Jira (which I've always found incomprehensible) for me.


Well you'd be surprised. I've also tried to solve this problem.

You can create your own lists inside of Bee which filter issues based on your own rules (http://neat.io/bee/docs/smart-lists.html). It's helpful because you just define the rules one-time and then flick to it whenever you need to.

Bee also has a menubar helper which tracks your short-term tasks and queues up your next issue so you always know what you're working on (http://neat.io/bee/docs/the-short-list.html).

Also you can add your own Notes list which is just a series of text files (easily synced via Dropbox) if you want to track your own local tasks.

I'm constantly iterating based on user feedback so if you have time, please let me know how it works out for you :)


Just bought Bee (to track github issues). That's a pretty convincing video you have there!


This is awesome, well done!

I just wanted to chime in and say I like your approach of just focusing on pull requests. There's another app I know of that just focuses on creating issues (http://issuepostapp.com).

I happen to be the author of another GitHub Issues client (http://neat.io/bee/github-issues-client.html) which is aimed at the other end of the spectrum: to be full-featured.

Great to see all these different approaches for different workflows.


Bee.app looks awesome!

Definitely will give it a try, to get and idea whether I should part with those $49. Could well be the case to intense Githubbers.


Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: