CS 2104 Problem Solving in Computer Science OOC Assignment 7 ------------------------------------------------------------------------------- 1. a) Figure B is just a 180-degree rotation (clockwise or anti-clockwise) of figure A. b) Figure 2 is a 180-degree rotation of figure C. Figure 1 does not work because it is a vertical flip of figure C. Figure 3 does not work because it is a 90-degree clockwise rotation of figure C. Figure 4 does not work because it is a horizontal flip of figure 3, so it is a combinationof a 90-degree clockwise rotation and a horizontal flip of figure C. Figure 5 does not work because essentially a corrupted 90-degree clockwise rotation of figure C. 2. a) Figure B is obtained by moving the NW component of figure A to the SE corner, and moving the SE component of figure A to the NE corner with a 90-degree clockwise rotation. b) Figure 5 is obtained from figure C by moving the NW component of figure C to the SE corner, and moving the SE component of figure C to the NE corner and rotating it 90 degrees clockwise. Figures 1-4 all fail because the component in the SE corner is incorrect (among other faults for 1 and 2). 3. The solution is: SPOT 9846 A 2 TOP ----- ----- GHOST 10496 Analysis: Since G is the carry from the 1000s column, and that sum is simply S plus a possible carry, G = 1, which gives us: SPOT A TOP ----- 1HOST Now, the 1s column implies that T + A + P = T + 0/10 and so that A + P = 10; the sum of A and P must be larger than 0. The 10s column implies that 1 + 2O = S + 0/10; we don't have enough information to deduce the carry yet. The 100s column implies that 0/1 + P + T = O + 0/10. Moreover, there must be a carry into the 1000s column or else S = H, which is not allowed. So, 0/1 + P + T = S + 10. The 1000s column implies that 1 + S = H + 10, or S = H + 9, so {S, H} = {0, 9}. Now, 1 + 2O = 9/19 but 19 isn't possible, since O cannot be 9. So, we know that 1 + 2O = 9 and hence O = 4 and there is no carry into the 100s column. SP4T A T4P ----- 1H4ST Now, substituting into the equation from the 100s column, we obtain P + T = 4 + 10 or P + T = 14. Since 9 + 5 is eliminated by the fact that only S or H can be 9, and 7 + 7 violates the basic rules, so we must have that {P, T} = {6, 8}. Now, from the equation for the 1s column, we obtain that A + P = 10, and so since P is 6 or 8, A is 2 or 4 but 4 is already taken; therefore, A = 2. But then we infer that P = 8, and hence T = 6. So, now we have that S846 2 648 ----- 1H4S6 And now we see that S = 9 and H = 0 and we are done. The uniqueness of the solution follows from the fact that every value was forced by the logic of the problem. 4. We are given the encoded cryptogram: F BXFSV BXPB F NXPUU SWIWY NWW P HFUUHGPYL UGIWUO PN P BYWW, KWYXPKN, ESUWNN BXW HFUUHGPYLN ZPUU, F'UU SWIWY NWW P BYWW PB PUU. (GJLWS SPNX) A couple of quick observations get us started: - The only 1-letter words in English are 'a' and 'I', so F and P must correspond to those, in some order. - The third word is encoded as BXPB; there are not a lot of four- letter English words that start and end with the same letter; some candidates are "that", "edge", and "dead". The most common such word is almost certainly "that" and that fits with the fact that P must encode either 'a' or 'i'. - We have the encoded word F'UU; that doesn't seem to allow any solution except "I'll", which is consistent with the earlier observations about F and P. - W is used as a terminal double in BYWW and NWW; again, there are not a lot of terminal doubles in English and for a three-letter work we immediately think of words such as "all", "too", "ass" and "see", but 'l' is already taken, "ass" seems very unlikely, and 't' is already mapped to B, not N. Now, if we apply these observations to the original encoding, we get: F BXFSV BXPB F NXPUU SWIWY NWW I thi?? that I shall ?e?e? see P HFUUHGPYL UGIWUO PN P BYWW, a ?ill??a?? l??el? as a t?ee, KWYXPKN, ESUWNN BXW HFUUHGPYLN ZPUU, ?e?ha?s, ?nless the ?ill??a??s ?all, F'UU SWIWY NWW P BYWW PB PUU. I'll ?e?e? see a t?ee at all. (GJLWS SPNX) ???e? ?ash Now, "t?ee" is surely "tree", and so Y must encode 'r', which gives: F BXFSV BXPB F NXPUU SWIWY NWW I thi?? that I shall ?e?er see P HFUUHGPYL UGIWUO PN P BYWW, a ?ill??ar? l??el? as a tree, KWYXPKN, ESUWNN BXW HFUUHGPYLN ZPUU, ?erha?s, ?nless the ?ill??ar?s ?all, F'UU SWIWY NWW P BYWW PB PUU. I'll ?e?er see a tree at all. (GJLWS SPNX) ???e? ?ash Now, "?e?er" must be "never", so S encodes 'n' and I encodes 'v'. And, "thi??" appears to be "think", so V encodes 'k'. This gives us: F BXFSV BXPB F NXPUU SWIWY NWW I think that I shall never see P HFUUHGPYL UGIWUO PN P BYWW, a ?ill??ar? l?vel? as a tree, KWYXPKN, ESUWNN BXW HFUUHGPYLN ZPUU, ?erha?s, ?nless the ?ill??ar?s ?all, F'UU SWIWY NWW P BYWW PB PUU, I'll never see a tree at all. (GJLWS SPNX) ???en Nash Now, the remaining words are more-or-less obvious: "?erha?s" is "perhaps", so K encodes 'p' "?nless" is "unless", so E encodes 'u' "?all" is "fall", so Z encodes 'f' "?ill??ar?" is "billboard", so H encodes 'b', G encodes 'o' and L encodes 'd' So, that gives us almost everything: F BXFSV BXPB F NXPUU SWIWY NWW I think that I shall never see P HFUUHGPYL UGIWUO PN P BYWW, a billboard lovel? as a tree, KWYXPKN, ESUWNN BXW HFUUHGPYLN ZPUU, perhaps, unless the billboards fall, F'UU SWIWY NWW P BYWW PB PUU, I'll never see a tree at all. (GJLWS SPNX) O?den Nash All that's left is "lovel?", which must be "lovely" and the J in the author's name, which is easily recognizable as encoding 'g'. So, we get: I think that I shall never see a billboard lovely as a tree, perhaps, unless the billboards fall, I'll never see a tree at all. (Ogden Nash)