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