Marlin’s Gottahack – 1998 Dec 07 – PREV HOME NEXT

Obligatory initial whine
------------------------

OK, I type up this hoser in Word so that I can get my spelling somewhat corrected. Of course it Loathes my capitalization of things like VTranLo so it fixes those automatically. If you backspace up and put it the way you want it, it will just fix it up for you again. I have learned that if you let it fix the word, then you go back with the cursor and make just the change you want it won't refire the correction code. What a bag! Anyway, once I am finished I can cut and paste the entire wad into the mailer (for those few of you that don't have office 97 and can't read WORD attachments) Lo and behold all of the quotes and single quotes that I typed into word now show up with some garbage in front of them here in the mailer. I suspect that Word converted all my generic ASCII straight up and down like GOD intended em into curvilinear typeset non-ASCII quotes. Thusly when I paste into eudora I get some grubby little black thing in front of all my quotes. Well, I am sorry. My eyes are shot. I just can't look at the screen any longer. I am not going to edit them out. You'll just have to imagine that those black blobs are not there.

Hmm, that's a thought. Maybe they're not there. Maybe I have been looking at the screen too long.

Code for the Symmetry Group Drawing App

-------------------------------------------------------

Well, So much for learning Java. Sure is hard to get inspired to open a book and learn a new language, when you got VB already installed and running on yer box, it does everything you gonna need for the symmetry application, and you GOTTAHACK! I spent three nights hacking this up. Wrote the engine in a night and filled in all but 3 elements of the table. Spent the next night figuring out that P4G was the ONLY group that required a mirror of a mirror and thus did not fit the simple engine I had built the night before. It took one line added to the engine to fix and the table was finished. On the third night I wrote the UI that lets the user choose the symmetry group and it loads up the key variables with the values from the table. I guess if you wanted to be honest (and who does?) I should include this fourth night writing up this documentation.

Now for the code that lets you draw like Escher, in any of the symmetry groups. The basic plan is that every time you move the mouse and draw a little line segment, we will copy that segment all over the screen into all the appropriate places (dictated by the symmetry group). The nice thing is that this one simple little block of code (simple is in the eye of the beholder) deals with all of them, the point symmetries, the strips and the wallpaper.

Const maxp = 3000

Dim Xx(maxp), Yy(maxp) ' array to hold the history of points that are being drawn
Dim cx,cy ' this is the coordinates of the center of the screen
Dim Rval ' the number of rotations we will do about the center
Dim Mflag ' true if there is a Vertical Mirror Plane (possibly displaced from center)
Dim Gflag ' true if there is a Horiz Glide or Mirror Plane (ditto)
Dim hg ' amount of translation of the Horiz Glide (0 if it is a mirror)
Dim d ' displacement of Mirror (or Glide) from the center
Dim t1x,t1y ' translation vector (usually vertical, 0 for strips)
Dim t2x,t2y ' translation vector (usually horiz, 0 for points)
Dim VTranLo, VTranHi, HTranLo, HTranHi ' number of translational copies.
' we avoid the infinite number of translational copies required by the math by
' translating only enough to fill the screen. Once I know the translation vectors
' and the screen size I can calculate how many copies I will need to fill
' the screen. Unfortunately the translation vectors are not always horizontal and
' vertical so the calculation is messy. Fortuantely sloth comes to the rescue,
' we find experimentally that if the translation vectors allow about N copies
' on the screen, you can just do -(N+3) to +(N+3) translations. This draws a few too many
' copies but you just let the screen clip the ones that are too far out.
' Just for the record, if the vertical translation t1x,t1y is 0 as it is for both the
' points and the strips, we set VTranLo and VTranHi to 0 so that we don't waste time
' drawing vertical translations that are not actually translating and similarly we
' nuke the HTranLo and Hi when we are in the point group.
' Now this code is what you do on a Mouse Move that generates a new (X,Y)
If np < maxp Then
' I add the new point to my history array.
np = np + 1
Xx(np) = X: Yy(np) = Y
' This outermost loop draws a copy for each rotation.
n = Rval
th = twopi / n
For i = 0 To n - 1
' we compute the rotation about the center point (cx,cy)
X1 = (Xx(np - 1) - cx) * Cos(i * th) + (Yy(np - 1) - cy) * Sin(i * th) + cx
Y1 = (Xx(np - 1) - cx) * -Sin(i * th) + (Yy(np - 1) - cy) * Cos(i * th) + cy
X2 = (Xx(np) - cx) * Cos(i * th) + (Yy(np) - cy) * Sin(i * th) + cx
Y2 = (Xx(np) - cx) * -Sin(i * th) + (Yy(np) - cy) * Cos(i * th) + cy
' (X1,Y1)-(X2,Y2) is the line segment from the previous mouse position to the
' current one, in each of its rotational positions. Next we translate it.
For j = VTranLo To VTranHi: For k = HTranLo To HtranHi
' first we compute (tx,ty) the single translation vector made up of the
' combined vertical and horizontal components
tx = j * t1x + k * t2x: ty = j * t1y + k * t2y
' Now draw the line segment translated
Line (X1 + tx, Y1 + ty)-(X2 + tx, Y2 + ty)
' if the line is vertically mirrored we do that line too.
If Mflag <> 0 Then Line (2*cx + d-X1+tx, Y1+ty)-(2*cx + d-X2+tx, Y2+ty)
' if it is horizontally mirrored (or glided) we do that too.
If Gflag <> 0 Then Line (X1+hg+tx, 2*cy + d-Y1+ty)-(X2+hg+tx, 2*cy + d-Y2+ty)
' last but not least you may have to Vmirror the Hmirrored copy. (only in P4G)
If Mflag <> 0 And Gflag <> 0 Then
Line (2*cx + d-X1+tx, 2*cy + d-Y1+ty)-(2*cx + d-X2+tx, 2*cy + d -Y2+ty)
Endif
Next k: Next j
Next i
End If

That is the engine that does all the drawing. Next is the table of values that gets you the different groups.

Remember, M means vertical mirror, G means Horizontal Mirror (or Glide if hg is not 0)

R3 = Sqrt(3), dx is an arbirtary translation value (think of it as an x displacement about a fifth of the screen size) similarly dy and dz.

GroupName (Rval, Mflag/Gflag, hg, d) (t1x, t1y, t2x, t2y) notes

 

Point Groups - simple rotations

Rn (n, 0, 0, 0) (0, 0, 0, 0)

Dn (n, M, 0, 0) (0, 0, 0, 0)

Strip Groups

P111 (1, 0, 0, 0) (0, 0, dx, 0)

P112 (2, 0, 0, 0) (0, 0, dx, 0)

PM11 (1, M, 0, 0) (0, 0, dx, 0)

PMM2 (2, M, 0, 0) (0, 0, dx, 0)

P1M1 (1, G, 0, 0) (0, 0, dx, 0)

P1A1 (1, G, dx/2, 0) (0, 0, dx, 0)

PMA2 (2, G, dx/2, 0) (0, 0, dx, 0)

Wallpaper Groups

P1 (1, 0, 0, 0) (dz, dy, dx, 0)

PM (1, M, 0, 0) (0, dy, dx, 0)

PG (1, G, dx/2, 0) (0, dy, dx, 0)

CM (1, G, 0, 0) (dx/2, dy, dx, 0)

P2 (2, 0, 0, 0) (0, dy, dx, 0)

PMM (2, M, 0, 0) (0, dy, dx, 0)

PGG (2, G, dx/2, dy/2) (0, dy, dx, 0)

PMG (2, G, dx/2, 0) (0, dy, dx, 0)

CMM (2, M, 0, 0) (dx, dy, dx, -dy)

P3 (3, 0, 0, 0) (dx/2, dx*r3/2, dx, 0)

P31M (3, G, 0, dx*r3/3) (dx/2, dx*r3/2, dx, 0)

P3 (3, G, 0, 0) (dx/2, dx*r3/2, dx, 0)

P4 (4, 0, 0, 0) (0, dx, dx, 0)

P4G (4, M&G, 0, dx/2) (0, dx, dx, 0)

P4M (4, M, 0, 0) (0, dx, dx, 0)

P6 (6, 0, 0, 0) (dx/2, dx*r3/2, dx, 0)

P6M (6, M, 0, 0) (dx/2, dx*r3/2, dx, 0)

I will spare you the mess of spaghetti code that I wrote when I did NOT just build a table of these values so that I could easily load the appropriate ones for the desired group. I made the mistake of noticing patterns, "Hey look at all the ones that are translating along the edges of an equilateral triangle - dx/2, dx*r3/2, dx, 0 Cool, that's a special case. Ooh, there's another one, this will only take a few lines of code," and a few more for the exceptions, and next thing you know, you got a pile of garbage. It works, but it is a pile of garbage.

 

Sum and Product - Solution

----------------------------------------------------------

The two numbers are 14 and 15

The reason is this:

Sally was given the number 14+15 = 29
She knows it could be any of the following sums
10+19
11+18
12+17
13+16
14+15
so she does not know the answer all by herself.

Peter was given the product 14*15 = 210 which also factors as 10*21 so he does not know the answer all by himself.

When Sally hears that Peter does not know the two numbers she notices that the only way to factor 10*19 is 10*19. In fact, all through her list of possibilities only the last one 14*15 = 210 = 10*21 gives Peter any ambiguity in factoring it into two numbers that are greater than or equal to 10. So she knows that 14 and 15 are the answer.

Now that Peter hears that Sally know he looks at his two possible factorizations. Either Sally was looking at the sum of 14 +15 = 29 or she was looking at the sum 10 + 21 = 31. He looks at the list of sums above and concludes that Sally could have figured out the answer if she was looking at the above list. When he looks at the other possibility the list of sums are
10+21
11+20
12+19
13+18
14+17
15+16

he discovers that 11*20 = 220 = 10*22 does not have a unique factorization. Also 15*16 has several factorizations. In other words if the two numbers had been 10 and 21 Sally would not have been able to solve the problem from Peter's comment alone. So Peter concludes that the numbers must have been 14 and 15.

So we know that 14 and 15 is a possible solution to the problem and by using the META-RULE "If they ask you to find 'the' solution to the problem that means that there is only ONE solution to the problem and that means that if you find 'any' solution to the problem then you have found 'the' solution."

However it is tacky to use the meta-rule. You do that when you are cruising on a test and do not have time to delve deeply into a topic. We have some time here to check out what is really going on. Looking at the solution above we can see that a very important point is to be able to tell the difference between pairs of numbers that can only factor 1 way (so that Peter could have solved the problem directly) and those that have multiple factorizations.

We write a little chunk of code to do that:

Function PeterCantSolve(A, B)
' Peter can't solve it if there is more than one way to write the product of these two numbers.
P = A * B
p1 = 10             ' we start with the lowest first product.
p2 = Int(P / p1) ' this give the integer part of the division i.e. throw away remainder if there is one
NumberOfFactorizations = 0
While p1 <= p2 ' we don't want to count 5*3 as different from 3*5 so we limit p1 to be smaller
  If p1 * p2 = P Then ' we have a real factorization
    NumberOfFactorizations = NumberOfFactorizations + 1
    Print p1; "*"; p2; "="; P;
  End If
  p1 = p1 + 1
  p2 = Int(P / p1)
Wend
PeterCantSolve = NumberOfFactorizations

End Function

Now for any pair of numbers we can stuff them into Peter's function to see if we get a unique factorization. (We also have a print statement down in this function to print out the actual factorizations that are found. This is a function side effect and is considered tacky. Good thing we is just screwing around here and not writing REAL code!)

Next we write the driving routine to look at sally's lists and show us the ones where she could figure things out from Peters comments.

Private Sub Command1_Click()
 
For Sum = 22 To 100 ' this is the sum that sally is considering we stop rather arbitrarily at 100 since the solution is probably
  Print "Sum = "; Sum                               ' less than that
  A = 10             ' she breaks it into two numbers A and B
  B = Sum - A
  NumberPeterCouldNotSolve = 0 ' she will count the number that Peter can't solve here
  While A <= B
     Print A; "+"; B; "-- ";
     If PeterCantSolve(A, B) Then
        NumberPeterCouldNotSolve = NumberPeterCouldNotSolve + 1
        PossibleProblemSolutionA = A
        PossibleProblemSolutionB = B
     End If
     A = A + 1
     B = B - 1
     Print
  Wend
 ' at this point, we have looked at all the A,B pairs. If there is but a single one that Peter can't solve
 ' then we have a potential winner and we print out the numbers that gave Peter fits.
 ' It is very important to note that just because this code prints out AWINNER does not
 ' mean that we have a final winner, merely a situation where Sally could figure out the numbers.
   If NumberPeterCouldNotSolve = 1 Then
     Print "AWINNER!!"; PossibleProblemSolutionA; PossibleProblemSolutionB
  End If
Next Sum
End Sub

This will print out all the possible sums that Sally could look at. It will only print AWINNER if it is a list of numbers that has but a single pair of numbers that Peter could not solve. When you run it you will see that there are 3 lists that Sally considers AWINNER. One is the correct answer 14+15 = 29. The other two are 10+18 = 28 and 12+15 = 27. These correspond to the two factorizations of 180 = 10*18 = 12*15. These do not lead to correct solutions because although Sally can figure out the two number, Peter cannot. When he looks at the two lists he can see that Sally can use the fact that he is stuck to find the two numbers regardless of whether the sum was 28 or 27 so Peter is left not knowing whether Sally figured out it was 12 and 15 or whether it was 10 and 18.

We are very close to concluding that there is a single unique answer. In running the code for all sums up to 100 we find only 3 candidates, the one correct solution and the two that we just rejected. Are there any others? Intuition (and looking at the print out for larger sums) tells you that as you move on to bigger sums there are not only more of them, but more ways to factor them so that it is unlikely that you will ever find another sum for which Peter has exactly one single pair that does not factor nicely. We will show that once the sums get big enough there are always several sets that Peter cannot solve by factoring.

Suppose that 70 + X  (where X =10) is one of the pairs that Sally is considering. Peter can factor 70*X either as 10*(7*X) or as 14*(5*X) so Peter can't solve problems like 70 + X. For similar reasons he can't solve 75*X = 25*(3*X) = 15*(5*X) and also can't solve 50*X = 25*(2*X) = 10*(5*X). So by the time Sally is looking at any Sum as great as 85, somewhere on the list she is looking at she will see 50 + A, 70 + B, and 75 + C. (Note it is possible that two of these are the same, for example the sum could be 120 = 50 + 70 but not possible for all 3 to be the same.) Thus for any sum greater than 85 she will have at least 2 combinations that Peter can not factor, thus when he tells her he can't find the two numbers, she will gain no information and can't solve her problem.

Since we wrote the code to check all sums up to 100 we have clearly surpassed the 85 mark and having found no solutions other than the one legitimate one, we must conclude that there are no others.

I have no idea who thought up this puzzle. I got it from a puzzle alias where it was stated differently. In the form that I saw it, it was stated that the numbers were each 2 digit numbers. This is similar to saying that the numbers are greater than or equal to 10, but not exactly the same. When it is stated in this manner there are multiple solutions to the problem. The reason being that when the sum gets up close to 200, like 196 = 99 + 97, the lists that Sally looks at grow very short and the possibility of finding ones with a single unsolvable problem for Peter start showing up.

I was bothered by the multiple solutions and changed the problem statement slightly to make only the 14+15 solution work. Since problems with multiple solutions are typically shunned by puzzle designers, I suspect the original puzzle did not suffer from this defect but by the time the puzzle had worked its way through dozens of memories to end up on the alias it had suffered a slight genetic mutation rendering it slightly less fit. This puzzle was fun for me because I wrote the code to solve the stated 2 digit puzzle and was confused for the longest time as to why there were multiple solutions. Suspecting a bug in the code I examined it closely, decided that the solution was in fact right and the bug was in the puzzle itself. So not only did I get to solve the puzzle, I got to fix it as well.