HN Explorer

18 comments

[ 2.4 ms ] story [ 42.0 ms ] thread
satisfice
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)
fph
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`.
Etherlord87
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.

Joker_vD
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.
Etherlord87
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.

lupire
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.
Etherlord87
The code wasn't written for other parameters, so it doesn't have a bug.
satisfice
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.

yobbo
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.

qsort
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.
cjlarose
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.
lupire
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.

cjlarose
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

ggrothendieck
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)`
CamperBob2
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.

lupire
How does it do on problems whose solutions aren't published in 100 hundred year old books?
[deleted]
(comment deleted)
CamperBob2
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.