Solving a simple puzzle using SymPy

https://wsdookadr.github.io/posts/p9/

by somat • 3 years ago

101 34 3 years ago

wsdookadr.github.io

somat3• 3 years ago

I find these sort of calculation engines very interesting. Here is my attempt to solve the same somewhat more geometrically in solvespace. Any good papers on the data structures needed to implement one?

I am not very good at math so I might of done something terribly wrong but the theory is. The rectangles have equal area, area is length * width, items with the same L + W will have the same area(this is where I might have gone wrong), create a structure where all rectangles are forced to have the same L + W.

http://nl1.outband.net/extra/floorplan.png

http://nl1.outband.net/extra/floorplan.slvs

PaulHoule• 3 years ago

I could see this being useful for graphical layout.

mk_stjames3• 3 years ago

This is a class of problems known as constraint solvers, and a program like Solvespace is actually using a symbolic algebra system under the hood to 'solve' the layout as you constraint the sketch in the GUI in nearly the exact way that SymPy is solving the puzzle above.

There are various approaches; Solvespace uses a modified Newton's method and was written in C++ making use of just the Eigen lib.

WoodenChair• 3 years ago

items with the same L + W will have the same area(this is where I might have gone wrong),

Unfortunately yeah that’s not right. Think of a 1x3 and a 2x2.

somat3• 3 years ago

Right, a simple sanity check on the rects would have shown my mistake.

mjfl• 3 years ago

Simple guess assuming that the answer is an integer: We have 5 copies of equal area with area = 3w, where w is the width of the first box. That means the whole square has area 15w. If the answer is an integer then it means 15w is a perfect square, which requires w = 15u^2 for some integer u. Guessing u = 1, the answer may be 15^2 = 225.

mkl• 3 years ago

The total area 15w is a perfect square, but w doesn't need to be an integer (and it isn't).

Enigma02• 3 years ago

For the posed question you could assume that each rectangle has area 1, so the square has area 5. From there its pretty easy to find the lengths of relevant sides, which can then tell you how much you need to scale by.

Of course for more complicated layouts this method won't work as well, but at least for this simple one this method seems easier.

bar94• 3 years ago

Not sure if everything is correct, seems a bit too easy -

Let y be the horizontal width of the bottom-left-most rectangle, and x be the horizontal width of each of the rectangles directly adjacent on the right to the first one, so that the rectangle marked at the top right as having a vertical width of 3 now has a horizontal width of x + y.

Then, the area of each rectangle is 3x + 3y, as all rectangles have the same area.

It follows that the vertical width of the bottom-left-most rectangle is (3x + 3y)/y, and that the vertical width of each of the two stacked rectangles is (3x + 3y)/x.

Note now that the stacked rectangles have the same horizontal width, and therefore must have the same vertical width. Thus, the vertical width of the bottom-left-most rectangle must be 2 times the vertical width of each of these stacked rectangles, so (3x + 3y)/y = 2*(3x + 3y)/x.

From this, we get 1/y = 2/x (noting that 3x + 3y cannot be be zero), so x = 2y.

This means that the vertical width of the bottom-left-most rectangle is then (3(2y) + 3y)/y = (6y + 3y)/y = 9y/y = 9.

Therefore, the entire left side width is 3 + 9, or 12 units. Since the overall shape is a square, the entire square's area must be 144 square units.

kwstas• 3 years ago

I'm not really good at parsing information over text so I had to lay your solution out over the problem to get it.

https://i.imgur.com/OekI7jZ.png

Note now that the stacked rectangles have the same horizontal width, and therefore must have the same vertical width.

This is the most important thing to use and what, were it included in the system in the OP, would simplify it quite a bit with not much more complexity. But the value of the approach I guess is the use of only pre-defined constraints.

Another route is to use that h_1 * (x+y) = 3A = 9 * (x+y) so h_1 = 9

Tarq0n• 3 years ago

In the image the green square is actually less tall than the pink, which is really misleading.

elesiuta• 3 years ago

This problem is even simpler if you notice that the rectangle made up of yellow + green + pink is just 3x the area of the orange rectangle, by definition.

Since these two rectangles share the same width, the combined rectangle must have 3x the height of the orange one, making the height of the yellow rectangle 9.

This gives a side length of 12 and an area of 144.

albert_e2• 3 years ago

Very elegant! I like puzzles like these - the solutions provide a kind of satisfaction.

And good sources of such puzzles. I am hoping to get my school age kid interested in these.

tgv• 3 years ago

If you notice some implicit relationship, you're already solving the puzzle. The most assistance a computer (or human) could provide was by accepting the original description. Every inference you add to the original problem is part of the solution.

bee_rider• 3 years ago

This observation is pretty nice, though. Of course technically it is part of doing the puzzle, but it skirts doing most of the arithmetic.

ocfnash• 3 years ago

Note that this argument does not depend on the fact that the blue rectangle also has equal area.

This argument thus teaches us even more, namely: the configuration of the four equal-area rectangles orange, yellow, green, pink has the special property that if you widen it to get a square, the extra piece you add also has equal area.

Etherlord872• 3 years ago

By which definition? I think you're confusing deduction with definition. You could likewise say the area is 144 by definition.

jz391• 3 years ago

I believe the parent was referring to line from the article which said "...square that gets partitioned into rectangles of equal area" - i.e. area of yellow, green, pink and orange is the same, so the area of the big rectangle containing all those four colours must be 4 times the height of orange rectangle (since their widths are the same).

gcanyon• 3 years ago

I spent some time this morning failing to solve this via an algebraic relationship between the orange and blue rectangles. I came home just now, opened my computer, and your insight above jumped out at me immediately. Brains are funny.

mk_stjames3• 3 years ago

I have a completely absurd way to use python to approximate the integer solution. Right answer achieved via hopes and prayers:

    from PIL import Image
    from math import ceil
    given=3
    def is_orange(p):
        return 200 <= p[0] <= 255 and 100 <= p[1] <= 170 and 0 <= p[2] <= 50
    img = Image.open("p9-problem.png")
    w, h = img.size
    o = (sum(is_orange(img.getpixel((w // 2, y))) for y in range(h)))
    T = (sum(p[:3] != (p[0], p[0], p[0]) for p in (img.getpixel((w // 2, i)) for i in range(h))))
    L = ceil((T/o)*given)
    print(L**2)

Think about how many ways this could be tricked.... :)

somat3• 3 years ago

For one it is making the rather large assumption that the image is to dimension.

mk_stjames3• 3 years ago

Yes, and it doesn't seem to be (there is no way the side is 12 if that given is 3, looks more like ~9).

So yeah... complete luck was had here.

albert_e2• 3 years ago

Is there a labelled version of the diagram with the points o,y,p,b,g shown?

That would have made the code more obvious to read I think?

EDIT: Just realized these labels are probably meant to represent areas of the colored shapes ... orange, yellow, pink, blue and green?

spuz• 3 years ago

Yes, plus I believe P represents the set of equivalent areas and U represents the set of equivalent lengths.

sriram_malhar• 3 years ago

If the longer side of yellow = y, and the longer side of the orange = o,

// yellow+pink+green area = 3 x orange)

y * o = 3 (3 * o)

y = 9

Side of square = 9+3 = 12. So area is 144.

Eddygandr2• 3 years ago

Off topic but does anyone know if there is anywhere to learn about using formal methods to check board game rules? I've played a few games like Wherewolf (not the one-night variant) where I am intuitively sure at a certain number of players with certain rules the game is solved but would love to double check.

viraptor• 3 years ago

I'm not familiar with that game, but depending on what the goal is, I think you have three options:

- if you want to check that a complex system of rules has a solution, then you can translate that into a SAT problem and run a SAT solver (https://codingnest.com/modern-sat-solvers-fast-neat-underuse...)

- if the problem is small enough, you could run an exhaustive search of options - in that case it really doesn't matter how you encode the rules, it could be any function returning a bool

- if you're trying to prove some invariant about the game, look at languages like Coq - they should help you

Eddygandr2• 3 years ago

Thank you! I’ll look at this later :)

Fwiw, it’s a social deduction game where each role gains info or has an ability and each night they vote to kill someone and the wherewolfs kill someone. The game ends when the wherewolfs are dead or when they equal the number of villagers left alive. I’m pretty sure at a certain number of players regardless of roles if the villagers act in a certain way they win regardless of input from the wherewolves.

cbsks• 3 years ago

Golly I wish there were more comments in that code. 2 letter variable names and self documenting code are mutually exclusive. With some difficulty I was able to understand what it was doing, but even just a few comments would have really helped.

jasonm23• 3 years ago

It's ok, they then tranformed it into super readable math notation. :/

Etherlord872• 3 years ago

I was playing around with the code snippet, and I discovered you can replace line 22:

    e = P[i]-P[j]

with

    e = P[j]-P[i]

That is, you can simply change the order of comparisons of areas, and suddenly the script stops working… This shows how unreliable sympy really is; you can write an article how it solves a mathematical problem, but you could similarly write an article on how ChatGPT solves a problem (because for a given prompt it does solve it, but for a slightly changed prompt it fails miserably; of course assuming 0 temperature, otherwise the prompt is not reproducible…). Unfortunately, I also have similar experience with AI Feynman…

joel135• 3 years ago

you can use gröbner bases for greater reliability :)

wsdookadr• 3 years ago

reported the bug here https://github.com/sympy/sympy/issues/25507

Solving a simple puzzle using SymPy

Related Stories