5 ms·

Solving a simple puzzle using SymPy

101 points by somat 3y ago

somat 3y 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.png http://nl1.outband.net/extra/floorplan.slvs http://nl1.outband.net/extra/floorplan.slvs
- PaulHoule 3y ago
  I could see this being useful for graphical layout.
- mk_stjames 3y 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 3y 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.
  - somat 3y ago
    Right, a simple sanity check on the rects would have shown my mistake.
mjfl 3y 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 3y ago
  The total area 15w is a perfect square, but w doesn't need to be an integer (and it isn't).
Enigma02 3y 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 3y 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 3y 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 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 3y ago
    In the image the green square is actually less tall than the pink, which is really misleading.
elesiuta 3y 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_e 3y 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.
- deleted 3y ago
  [deleted]
- tgv 3y 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 3y 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 3y 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.
- Etherlord87 3y ago
  By which definition? I think you're confusing deduction with definition. You could likewise say the area is 144 by definition.
mk_stjames 3y 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.... :)
- deleted 3y ago
  [deleted]
- somat 3y ago
  For one it is making the rather large assumption that the image is to dimension.
  - mk_stjames 3y 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.
    - nerdponx 3y ago
      It looks deliberately not to dimension. In the process of getting to the answer I figured out that the width of the yellow rectangle is actually twice the width of the green and pink rectangles. It's a fakeout because it is correct that the green and pink rectangles have the same height.
albert_e 3y 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 3y ago
  Yes, plus I believe P represents the set of equivalent areas and U represents the set of equivalent lengths.
sriram_malhar 3y 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.
Eddygandr 3y 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 3y 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-underused-part-1-of-n/ 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
  - Eddygandr 3y 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 3y 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 3y ago
  It's ok, they then tranformed it into super readable math notation. :/
Etherlord87 3y 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 3y ago
  you can use gröbner bases for greater reliability :)
- deleted 3y ago
  [deleted]
- wsdookadr 3y ago
  reported the bug here https://github.com/sympy/sympy/issues/25507 https://github.com/sympy/sympy/issues/25507

101 points by somat 3y 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.png http://nl1.outband.net/extra/floorplan.slvs http://nl1.outband.net/extra/floorplan.slvs

PaulHoule 3y ago
I could see this being useful for graphical layout.
mk_stjames 3y 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 3y 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.
- somat 3y ago
  Right, a simple sanity check on the rects would have shown my mistake.

mjfl 3y 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 3y ago
The total area 15w is a perfect square, but w doesn't need to be an integer (and it isn't).

Enigma02 3y 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 3y 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 3y 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 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 3y ago
  In the image the green square is actually less tall than the pink, which is really misleading.

elesiuta 3y 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_e 3y 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.
deleted 3y ago
[deleted]
tgv 3y 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 3y 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 3y 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.
Etherlord87 3y ago
By which definition? I think you're confusing deduction with definition. You could likewise say the area is 144 by definition.

mk_stjames 3y 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.... :)

deleted 3y ago
[deleted]
somat 3y ago
For one it is making the rather large assumption that the image is to dimension.
- mk_stjames 3y 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.
  - nerdponx 3y ago
    It looks deliberately not to dimension. In the process of getting to the answer I figured out that the width of the yellow rectangle is actually twice the width of the green and pink rectangles. It's a fakeout because it is correct that the green and pink rectangles have the same height.

albert_e 3y 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 3y ago
Yes, plus I believe P represents the set of equivalent areas and U represents the set of equivalent lengths.

sriram_malhar 3y 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.

Eddygandr 3y 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 3y 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-underused-part-1-of-n/ 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
- Eddygandr 3y 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 3y 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 3y ago
It's ok, they then tranformed it into super readable math notation. :/

Etherlord87 3y 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 3y ago
you can use gröbner bases for greater reliability :)
deleted 3y ago
[deleted]
wsdookadr 3y ago
reported the bug here https://github.com/sympy/sympy/issues/25507 https://github.com/sympy/sympy/issues/25507