Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Solving Sudoku in Python Packaging

github.com

Post reply on HN
Print view View original

31–40 of 56 posts

Re: Solving Sudoku in Python Packaging

#31

Post by tetha »

arjvik wrote: post #22
echoangle wrote: post #12

> Solving the versions of python package from your requirements is NP-complete, in the worst case it runs exponentially slow. Sudokus are also NP-complete, which means we can solve sudokus with python packaging. Is that actually sufficient? Can every system that’s solving something that’s NP-complete solve every other NP-complete problem?

I think for Sudoku to be NP-Complete, it needs to be generalized to arbitrary board sizes (at the very least)

Correct, if the complexity guys talk about NP-complete sudoku, it's always about solving Sudokus of an arbitrary, but fixed and finite size.

The problem class of "Solve an arbitrary Sudoku of Size 9" might even be constant runtime, since it's a finite set to search through.

Re: Solving Sudoku in Python Packaging

#33

Post by zahlman »

kvdveer wrote: post #24
zahlman wrote: post #19

Earlier quoted context omitted.

People keep trying to sell the speed of such solutions as a killer feature for uv, but I think I must not be anywhere near the target audience. The constraint-solving required for the sorts of projects I would typically work on is not even remotely as complex, while I'm bottlenecked by a slow, unreliable Internet connection (and the lack of a good way to tell Pip not to check PyPI for new versions and only consider w…

Our CI took 2 minutes to install the requirements. Adding UV dropped that to seconds. Now most time is spent on running tests, instead of installing requirements. Of course we could've cached the venv, but cache invalidation is hard, and this is a very cheap way to avoid it.

Or you could cache the solve, surely? Simply explicitly including your transitive dependencies and pinning everything should do the trick - but there is work being done actively on a lockfile standard, it's just the sort of topic that attracts ungodly amounts of bikeshedding.

(One of these days I'll have to figure out this "CI" thing. But my main focus is really just solving interesting programming problems, and making simple elegant tools for mostly-small tasks.)

Re: Solving Sudoku in Python Packaging

#34

Post by TeMPOraL »

simonw wrote: post #7

I love this so much. I dug around a bit and figured out how it works - I have an explanation (with an illustrative diagram) here: https://simonwillison.net/2024/Oct/21/sudoku-in-python-packa... Figuring out how it works is a great way to learn a bit more about how Python packaging works under the hood. I learned that .whl files contain a METADATA file listing dependency constraints as "Requires-Dist" rules. I ran a s…

Tangent, but I wondered what libuv had to do with speeding up Python packaging, and it turns out nothing. I wonder why someone choose to name a pip replacement in a way that effectively collides with several tools and libraries across many languages...

Re: Solving Sudoku in Python Packaging

#35

Post by the_mitsuhiko »

zahlman wrote: post #19
simonw wrote: post #7

I love this so much. I dug around a bit and figured out how it works - I have an explanation (with an illustrative diagram) here: https://simonwillison.net/2024/Oct/21/sudoku-in-python-packa... Figuring out how it works is a great way to learn a bit more about how Python packaging works under the hood. I learned that .whl files contain a METADATA file listing dependency constraints as "Requires-Dist" rules. I ran a s…

People keep trying to sell the speed of such solutions as a killer feature for uv, but I think I must not be anywhere near the target audience. The constraint-solving required for the sorts of projects I would typically work on is not even remotely as complex, while I'm bottlenecked by a slow, unreliable Internet connection (and the lack of a good way to tell Pip not to check PyPI for new versions and only consider w…

> while I'm bottlenecked by a slow, unreliable Internet connection (and the lack of a good way to tell Pip not to check PyPI for new versions and only consider what's currently in the wheel cache).

Which is one of the reasons why uv is so fast. It reduces the total times it needs to go to PyPI! Not only does it cache really well, it also hits PyPI more efficiently and highly parallel. Once you resolved once, future resolutions will likely bypass PyPI for the most part entirely.

Re: Solving Sudoku in Python Packaging

#37

Post by zahlman »

the_mitsuhiko wrote: post #35
zahlman wrote: post #19

Earlier quoted context omitted.

People keep trying to sell the speed of such solutions as a killer feature for uv, but I think I must not be anywhere near the target audience. The constraint-solving required for the sorts of projects I would typically work on is not even remotely as complex, while I'm bottlenecked by a slow, unreliable Internet connection (and the lack of a good way to tell Pip not to check PyPI for new versions and only consider w…

> while I'm bottlenecked by a slow, unreliable Internet connection (and the lack of a good way to tell Pip not to check PyPI for new versions and only consider what's currently in the wheel cache). Which is one of the reasons why uv is so fast. It reduces the total times it needs to go to PyPI! Not only does it cache really well, it also hits PyPI more efficiently and highly parallel. Once you resolved once, future r…

Oh, that's good to hear. The performance discourse around uv seems to revolve around "written in Rust! Statically compiled!" all the time, but an algorithmic change like that is something that could conceivably make its way back into Pip. (Or perhaps into future competing tools still written in Python. I happen to have a design of my own.)

Re: Solving Sudoku in Python Packaging

#38

Post by simonw »

jebebeebehhe wrote: post #17
seanw444 wrote: post #13

Earlier quoted context omitted.

Wow, uv really is fast.

As is simonw writing that post in under 60m assuming he first saw the concept here on HN.

Nah I wrote this one a couple of days ago when I first saw the Sudoku solving project on Mastodon.

Re: Solving Sudoku in Python Packaging

#40

Post by alentred »

This is BRILLIANT ! I knew of a trend to implement lots of different things at compile-time (in Scala and Haskell communities at least) - definitely fun and quirky, but it never seemed that "special". This one, it has an air of old-school computer magic around it, probably because it is so elegant and simple.
Post reply on HN