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

41–50 of 56 posts

Re: Solving Sudoku in Python Packaging

#41

Post by empath75 »

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?

https://www.youtube.com/watch?v=6OPsH8PK7xM

This video I think makes it obvious why that's true in a pretty intuitive way. I posted it a few days ago as a link and it never got traction.

SAT is the equivalent of being able to find the inverse of _any_ function, because you can describe any function with logic gates (for obvious reasons), and any collection of logic gates that describes a function is equivalent to a SAT problem. All you need to do is codify the function in logic gates, including the output you want, and the ask a SAT solver to find the inputs that produce that output.

Re: Solving Sudoku in Python Packaging

#42

Post by jeanlucas »

simonw wrote: post #38
jebebeebehhe wrote: post #17

Earlier quoted context omitted.

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.

Thank you, I was going to point out the post on your blog has date of publication lol

Re: Solving Sudoku in Python Packaging

#44

Post by giancarlostoro »

TeMPOraL wrote: post #34
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...

I agree.. While I think it looks amazing, it's a poor naming choice.

Re: Solving Sudoku in Python Packaging

#46

Post by tzs »

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?

> Can every system that’s solving something that’s NP-complete solve every other NP-complete problem?

Others have given the answer (yes) and provided some links. But it is nice to have an explanation in thread so I'll have a go at it.

The key idea is the idea of transforming one problem to another. Suppose you have some problem X that you do not know how to solve, and you've got some other problem Y that you do know how to solve.

If you can find some transform that you can apply to instances of X that turns them into instances of Y and that can transform solutions of those instances of Y back to solutions of X, then you've got an X solver. It will be slower than your Y solver because of the work to transform the problem and the solution.

Now let's limit ourselves to problems in NP. This includes problems in P which is a subset of NP. (Whether or not it is a proper subset is the famous P=NP open problem).

If X and Y are in NP and you can find a polynomial time transformation that turns X into Y then in a sense we can say that X cannot be harder than Y, because if you know how to solve Y then with that transformation you also know how to solve X albeit slower because of the polynomial time transformations.

In 1971 Stephen Cook proved that a particular NP problem, boolean satisfiability, could serve as problem Y for every other problem X in NP. In a sense then no other NP problem can be harder than boolean satisfiability.

Later other problems were also found that were universal Y problems, and the set of them was called NP-complete.

So if Python packaging is NP-complete then every other NP problem can be turned into an equivalent Python packaging problem. Note that the other problem does not have to also be NP-complete. It just has to be in NP.

Sudoku and Python Packaging both being NP-complete means it goes both ways. You can use a Python package solver to solve your sudoku problems and you can use a sudoku solver to solve your Python packaging problems.

Re: Solving Sudoku in Python Packaging

#47

Post by yunohn »

itsbjoern wrote: post #23
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…

Personally I’m just a fan of people improving dev tooling, regardless of it ultimately making a huge difference to my workflow. I haven’t used uv yet, but I’m still tangentially following it because despite pip and poetry being great tools I have had my fair share of grievances with them.

Using uv (IME) should be a drop-in replacement for almost all of your python packaging needs. I highly recommend giving it a shot - it’s saved me measurable time in just a few months.

Re: Solving Sudoku in Python Packaging

#48

Post by anthk »

visarga wrote: post #9

That's why it feels like installing a ML repo is like sudoku. You install everything and at the last step you realize your neural net uses FlashAttention2 which only works on NVIDIA compute version that is not deployed in your cloud VM and you need to start over from scratch.

Guix fixes that in the spot.

Re: Solving Sudoku in Python Packaging

#49

Post by SJC_Hacker »

tetha wrote: post #31
arjvik wrote: post #22

Earlier quoted context omitted.

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.

Does the Sudoku size have to be perfect square, or can other sizes exist?

I suppose you could leave some blank and make the squares the next largest perfect square

Re: Solving Sudoku in Python Packaging

#50

Post by ilyagr »

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…

How does it encode the idea of having all the numbers on each line/square?
Post reply on HN