Hacker Remix

Shortest-possible walking tour to 81,998 bars in South Korea

378 points by geeknews 16 hours ago | 124 comments

gku 8 hours ago

If you find this impressive, take a look at the 1.33 billion stars TSP solution provided by the same authors.

- Gaia DR2 (1,331,906,450 Stars): https://www.math.uwaterloo.ca/tsp/star/gaia2.html

> "The tour is at most 1.0038 times the length of a shortest-possible route."

gampleman 8 hours ago

But that presumably doesn't handle the relative motion of the stars, which makes the problem even trickier, since the distances will change as you travel, no? Or is my astronomy off base here?

paulluuk 8 hours ago

I think your astronomy skills are correct, but if we have to worry about actual travel then you would also have to consider things like fuel capacity, refuel opportunities, the fact that you probably don't want to actually fly through a star but around it, etc.

gampleman 7 hours ago

I think it's still valid to have a distinction between travel logistics and having a route that's at least theoretically possible. I suppose what they've calculated would work with a star gate like system, but then I'm not sure what the point of having minimal distance would be.

elymar 5 hours ago

The bar problem has its own issues. With that many bars some may close or new ones may appear during the time of the walk.

consp 6 hours ago

Isn't the flying around problem just "e" since it is so many orders of magnitude less than the distance between stars that for this calculation it is irrelevant anyway?

manmal 5 hours ago

At that point we should also factor in time relativity, making it hard to measure the actual location of the stars at all.

batuhandirek 8 hours ago

This also doesn't handle new bars being opened and closed as you travel. Not to mention bouncers having bad days so you will have to revisit the bar.

pverghese 5 hours ago

I don't think this is presented as a means to get drunk around south korea. It's just an interesting application of TSP

nurettin 6 hours ago

But they are so far apart and move on roughly the same trajectory that it shouldn't really matter.

marcellus23 1 hour ago

That's not true. The tour is 16.2 billion light years long, so even at the speed of light, it would take more than the current age of the universe to travel. Stars will move a lot over that period of time.

Animats 9 hours ago

If you just use the simple-minded Bell Labs probabilistic algorithm, how much worse is that result?

The classic TSP approach is:

1. Hook up all the nodes in some arbitrary path.

2. Cut the path in two places to create three pieces.

3. Rearrange those three pieces in the six possible ways and keep the shortest.

4. Iterate steps 2-3 until no improvement has been observed for a while.

This is not guaranteed to be optimal, but for most real-world problems either finds the optimal result or is very close.

amscanne 9 hours ago

Note that the tour itself was found quickly using a heuristic solver (https://www.math.uwaterloo.ca/tsp/korea/computation.html), the achievement here and all the computation is to establish that this is the lower bound (assuming I understood correctly).

So, the heuristic solver worked pretty darn well :) Although, I’m not sure how close it would have been the heuristic algorithm you are describing (I suspect that it is considerably more advanced for good reasons, randomly picking will take too long to converge).

n4r9 8 hours ago

The algorithm that OP describes is more commonly known as 2-opt [0]. The heuristic used in this case is referred to as LKH which I assume means the Lin-Kernighan Heuristic [1]. The latter is sort of a meta generalisation of the former.

[0] https://en.m.wikipedia.org/wiki/2-opt

[1] https://en.m.wikipedia.org/wiki/Lin%E2%80%93Kernighan_heuris...

vjerancrnjak 8 hours ago

2-opt is a bit simpler.

LKH is a bit different, refers to Lin-Kernighan+Helsgaun -- http://webhotel4.ruc.dk/~keld/research/LKH/

neves 4 hours ago

https://www.youtube.com/watch?v=tChnXG6ulyE

Author's presentation about it

yobbo 8 hours ago

Iirc the (probably simplified) LKH heuristic they used:

  For each iteration:
     apply some randomisation
     starting at each place
         cut the path in 2..n places
           reconnect in the most optimal way 
           if the new tour is the new best, save

n is a small number like 4 maybe 5?

vjerancrnjak 8 hours ago

2-opt: [a, b, ..., d, e]

reversing subarray from b to d is a 2-opt move.

3-opt (1 particular move):

a b c d e f

a e d c b f -- reversal from b to e

a e d b c f -- reversal from c to b

LK heuristic is a bit more involved, but focuses on continuing to reverse the subarray on the [b, ..., d] segment, with search and backtracking involved. (I think that's refered to as sequential k-opt moves, but I think it's already quite hard to know what exactly LK is, and LKH does much more)

By focusing on the subarray, assuming distance symmetry (length from b to e is same as length from e to b, but there are correct workarounds if this does not hold), you can evaluate the cost of the new route in constant time (but with bigger k there's more moves to evaluate https://oeis.org/A001171)

noduerme 14 hours ago

It's strange that they don't mention the total distance. I understand that the point-to-point travel time is what they're solving for, but it would be interesting to know what the actual distance of travel was, if for no other reason than calculating caloric burn. But then you could also see how much it deviated from the shortest-distance path.

internetter 3 hours ago

Proper routing is also an expensive computation. Yes you could just run A* or something on the roads but that would assume no closures, no one way roads, wouldn’t account for elevation change, ect. Using a proper routing API is almost certainly cost prohibitive

notesinthefield 14 hours ago

I am overwhelmed with the thought of nearly 82 thousand bars within a country roughly the size of Ohio.

bbno4 10 hours ago

americans always compare massive cities to empty states

mherkender 2 hours ago

South Korea has 5x the population of Ohio, but around 27x the number of bars [1]. So it really is a lot of bars.

[1] https://www.ibisworld.com/us/industry/ohio/bars-nightclubs/1...

notesinthefield 5 hours ago

Snark aside - I used this site which compares the country question to the location closest to you. I live in ohio. https://www.mylifeelsewhere.com/country-size-comparison/unit...

not_a_bot_4sho 1 hour ago

Empty lol

lifthrasiir 13 hours ago

That country has a population of 52 million, i.e. about 5 times Ohio.

codemac 10 hours ago

Sure, but Ohio has ~4200 bars[0]. Which is roughly 1/4 the ratio of bars to people.

[0]: https://rentechdigital.com/smartscraper/business-report-deta...

pjc50 6 hours ago

Just to compare, they also have a tour for the UK https://www.math.uwaterloo.ca/tsp/uk/index.html : 49,687 pubs.

They are such an urban phenomenon. A largely empty rural state, with the legacy of prohibition, where you have to drive? That's going to have way fewer drinking locations. A culture of hanging out and drinking requires walkable urbanism. Many of the UK pubs pre-date the invention of the car; "peak pub" appears to have been the late 1800s with over 100,000.

I'm impressed that Korea has more than the UK, but this is definitely going to be a matter of size and the tiny Korean bars.

robertlagrant 5 hours ago

> A culture of hanging out and drinking requires walkable urbanism.

I don't think that's really true. In the UK, villages had pubs. Gradually some of the villages were joined together into larger cities, and the pubs remained. It wasn't planned as walkable urbanism.

tlb 5 hours ago

You didn't have to plan to get walkable urbanism before cars. It just happened because everyone needed a pub, store, school, etc. within walking distance.

robertlagrant 5 hours ago

But it wasn't urban. That's my point.

xmprt 9 hours ago

I don't think bars in Korea have parking minimums like they do in Ohio.

skrebbel 7 hours ago

What's a parking minimum?

chmod775 7 hours ago

The minimum number of parking that needs to be available per seat/dining area.

https://codelibrary.amlegal.com/codes/plaincity/latest/plain...

Codes like these are the secret sauce of America's asphalt deserts, in which you'll find - by international standards - comparatively large restaurants and stores. Walkable cities tend to gravitate towards smaller equivalents, and more of them.

Akronymus 7 hours ago

A minimum amount of parking spots per patron capacity. So a bar with 60 people capacity must have 15 parking spaces. [0]

Usually parking minimums are WAY too high in required parking spaces to make sense in most cases. Which leads to stuff like a arena having 5x the land area be parking than what is taken up by the arena itself. [1]

0: https://codelibrary.amlegal.com/codes/harrison/latest/harris... (this is for harrison, ohio, just happened to be the first result I found. it's under commercial -> "Tavern, bar, club, lodge, and dance hall.")

1: https://www.youtube.com/watch?v=OUNXFHpUhu8

skrebbel 4 hours ago

The idea of a bar (ie a place people go to get drunk) with a dedicated parking lot strikes me as particularly bad for road safety. I'm baffled that this is not only encouraged, but mandated.

How do people do this in practice? Just drink and drive and hope they don't crash / get fined? Or does everybody bring 1 friend who sips colas the whole night?

nonameiguess 24 minutes ago

Parking lots are not mandated for bars in the US, at least not everywhere. I helped my girlfriend's dad open a bar in Long Beach 20 years ago. The city required us to pay for the maintenance of three streetside parking spaces, but that was it. Pay the city. We didn't have to build anything that didn't already exist.

vulcan01 4 hours ago

We call the latter a designated driver [1] though as you can imagine sometimes the designated driver is "only" slightly drunk.

[1]: https://en.wikipedia.org/wiki/Designated_driver

skrebbel 4 hours ago

Yeah but I mean, if everybody goes to the pub by car, does it mean everybody brings a designated driver? Or is this one of those things where everybody drives drunk but pretends nobody does?

zhivota 10 minutes ago

Mostly the latter IMO. The most popular bar where I grew up is on a busy highway with no housing within walking distance. Parking lot reliably fills up every weekend night, mostly with single occupancy vehicles. You can do the math.

alexfoo 2 hours ago

Taxis exist.

skrebbel 2 hours ago

The parking minimum is for taxis?

apocalyptic0n3 57 minutes ago

It's pretty common for people drive to the bar, get drunk, taxi/Uber/Lyft/DD home, and then return the following day to get their vehicle. I don't think it makes sense personally, but I also don't drink at all so I'm not a great judge here.

forgotoldacc 7 hours ago

A lot of bars in walkable cities fit about 10 or fewer people. East Asia in particular has loads of tiny bars.

Plus being able to walk or take a train home makes them far more accessible for people than needing to drive home.

throwaway290 9 hours ago

82k places in Korea include any restaurant or joint or karaoke with a license to serve alcohol. Personally I would not care to call 80% of them "bar".

So in Ohio probably everything with class C and D license. How many is not public but probably many times more than 4k.

Many actual street level bona fide bars in Seoul (which has half of all the people of the entire country and the most bars by far) are tiny rooms that fit a few people each. But you always have a "bar street" with 50 of those next to each other.

saalweachter 3 hours ago

Ok, that gets the numbers in line -- there are about 27,000 liquor licenses in Ohio, according to a random Google, which is about the same per capita.

South Korea apparently ranks #97 on alcohol deaths, so it's apparently not a problematic number of bars, by global standards.

gniv 4 hours ago

I checked a few and there's a lot of restaurants included.

https://www.math.uwaterloo.ca/tsp/korea/data/korea81998.xy.t...

BrtByte 2 hours ago

South Korea really said "you will not be thirsty on our watch."