Solving 100 Bushels Using Matrix Factorization | Hacker News Reader

Solving 100 Bushels Using Matrix Factorization

win-vector.com

33 pointsjmount17 comments

The brute force method proposed in the article is so strangely obscure.

Here's a very simple alternative:

  for m in range(0,100):
    for w in range(0,100):
      for c in range (0,100):
        if m + w + c == 100 and 3*m+2*w+.5\*c==100:
          print(m,w,c)

I think it's because OP does not want to hardcode the dimension `n=3`, but write only code that works for all possible matrix sizes just by changing `a` and `b`.

You waste some CPU cycles, which doesn't matter all that much here, but with more combinations could matter a lot:

    for m in range(100):
        for w in range(101-m):
            c = 100-m-w
            if 3*m + 2*w +.5*c == 100:
                print(m,w,c)

No need to specify 0 as starting range, and the ending boundary is not included, so it's 100 at the outer loop, because at first sight the solution can't be m=100 w=0 c=0, The inner loop has to use 101, because perhaps there is a solution with c=0.

There's no need for the 3rd loop! Once you have candidates for m and w, there's only one possible c satisfying the requirements. And so you also don't need to check for their sum being 100.

Just want to note that "brute force search" is called "brute force" instead of e.g. "search with heuristics" for a reason. Of course you can trim down the search space if you think about the properties of the problem but the whole point of using a brute force approach is to literally allow yourself to not think about the problem.

Whatever you do, you need to find some reasonable balance. You need to reason on what are the minimum possible values for the variables and what are the maximums. In my example the reasoning effort was minimal, much less than figuring the `c` is even or the `w` is divisible by 5.

Otherwise OP made an error in using range(0, 100) instead of range(0, 101), but even here you could pedantically point out "how do you know the numbers can't be negative or over 100? You're not supposed to think too much when brute-forcing!" - well you have to do some minimal thinking always :P

Also notice my code is actually simpler.

Your code also has a bug, which would affect the result in some variations of the problem with different parameters, but fortunately does not affect this specific version. You also used 100.

The code wasn't written for other parameters, so it doesn't have a bug.

what I was going for is simplicity. I wanted code that mapped to the plain conceptual structure of the problem. As soon as you optimize it you begin to obfuscate the code.

Of course, with a bigger problem we will have to optimize.

Some clues to make it faster: w is divisible by 5. 5m=100-3w.

So, w ∈ {5,10,15,20,25,30}, m = 20 - 3w/5, c=100-m-w.

It seems this gives all answers.

Does this technique apply if the dimension of the null space of the linear transformation is greater than 1? In other words, if there is more than 1 free variable, can you still use the Smith normal form of the matrix to find a bijection from the integers to the solution set?

Edit: related follow up: any chance this technique is a good fit for enumeration of [Magic Squares][0] of a given order?

[0]: https://en.wikipedia.org/wiki/Magic_square

Interestingly, o1-preview gets all 7 solutions in 18 seconds. It also makes short work of Bachet’s Four Weights Problem as recounted at https://ninazumel.com/blog/2024-09-29-four-weights/ .

Pretty smart parrot.

How does it do on problems whose solutions aren't published in 100 hundred year old books?

It doesn't just regurgitate the answer, it shows its work, and it still works if you change the numbers.

Being able to access, apply, and restate reasoning processes described in 100-year-old books isn't the insult you think it is.

Am I stupid or this is solvable with pen and paper?

The word problem directly translates to this system of diophantine equations:

    (i)  { x + y + z = 100
    (ii) { 6x + 4y + z = 200

Replacing z in (ii) using (i) yields:

    (ii) <=> 6x + 4y - x - y + 100 = 200 <=> 5x + 3y = 100

Which is solvable with the usual method.

I could be wrong, but my impression of the post was that it is not meant to be a novel solution for a hard problem, but rather a demonstration of an interesting technique on a simple enough problem that the problem doesn’t distract from the technique itself.

Yes, if you follow the link to problem, that page gives the trivial algebra solution.

The matrix version is interesting, but it's bizarrely motivated as an overcomplicated way to solve a simple problem.

In R `nnls` (nonnegative least squares) does not guarantee integrality but in this case does give one solution and it happens to be integral: `library(nnls); nnls(A, b)`

Reply on news.ycombinator.com