USPC 2009

Update: Well, it turns out I was off by 3 on Window Pain (doh!), but Nick was nice enough not to penalize me for the late submission on Magic Puzzle'Rs - which means I actually ended up with a score of 95 and rank of 105 (about a 50 place drop from last year). Which actually is a bit heartening, because if I didn't make stupid mistakes, a score of 125 would put me at the 44-48 rank and being on top of things really would have netted me a top 20 finish this year. There is hope for 2010!

Well, I knew I probably wouldn't do as well as last year, given the little prep time I had this year. Overall, though, it wasn't bad. I think if I had spent an hour or two reading over the instructions so that I knew what puzzles would be nice to do and strategies to take, (and how to put in the answers) along with being in top shape, I could have scored in the 180 range.

Here's the breakdown:

1. Battleships - I finished this first and very quickly, due to a (correct) early guess on the second cruiser position. I forget my writing scheme, so I had to break out the white-out (doh!).

2. Sudoku - I wasn't really on top of my sudoku game, so I took a crack at this and stalled a few minutes in. I left it alone, came back later, made one guess and extended until I found a contradiction, and then changed it and solved the rest. Took about 20 minutes. (blargh)

3. KenKen - The instructions were somewhat confusing, but I figured out that 2 square cages *could* be multiplication or addition, and 3 square cages *must* be multiplication or addition. It should have been worded differently (ie. 2 square cages can be any operation, but there is a constraint on 3 square cages). Anyway, the singleton 2 helped by forcing the 4+6 on the 10 in the same row. 20 and 40 had to be multiplication, which forced some early numbers, and then there was a bit of casework on the bottom and top rows to get the rest.

4. Sum Thing - I guessed that the center node was the key, since it intersected with 4 pairs of lines - forcing it to be 4. I struggled a bit with placing the rest, until I realized that the 5 had to be in the only unconnected node to the center and it came around nicely.

5. Eminent D'OHmain - In retrospect, rather easy, if a bit time consuming. Probably took me around 15 minutes (after the test) to solve. (which really isn't that much better than my sudoku solve for the same number of points)

6. Switch Cheese - Really easy this time: I got all 10 differences in a few minutes using the good old cut in half, flip over and vdiff.

7. Writer's Block - I initially started looking at 3 down without significant progress and then went to 2 across and filled in everything nicely. Unfortunately I crossed off the MICHENER by accident and messed up the bottom left area. Ended up answering incorrectly. Doh...

8. Corral - I am not a fan of corral puzzles: they take me way too much time - so I left this out, spent about 20 minutes afterwards and still didn't get it. (I think I'm close, though.)

9. Coordinate Pairs - I started by looking at N and its possible pairs. Realized (3,0) was out of the question, as was (2,1) and (4,1), which left (4,2), and resulted in the solution.

10. Triangular Skyscrapers - Looked too complicated - regular skyscrapers is already pushing my point/minute rate - so I left this one alone. It took me about 30 min to get afterwards, once I was able to fix the positions of the 8 and 7's.

11. Window Pain - Halfway through counting, I realized what I was doing and sped things up a bit. I think the strategy here is to look at different sizes of squares and figure out possible positions for the upper left corner. Take the number of valid x-coordinates and multiply by the number of valid y-coordinates to get the solution. Bit annoying to add everything together.

12. Masyu - Spent 1 minute starting, and realized this was a much bigger Masyu than I had done in the past, with no real recent practice, so I left this one alone. I spent about 40 min afterward resolving everything but the middle of the right side, which probably would have been a good place to start. Still unsolved. (but I think I'm close)

13. C Note - I didn't have a good strategy for this one, so I left it alone. Afterwards, I realized you could start with the middle row, since exactly 2 of the 3 givens have to be ones digits. Some casework results in 56 for the middle of the right column, and some guessing led me to the answer. Also about 20 min.

14. Lucky Sevens - No complaints, but seemed real familiar. Actually in the same format as 2003 - 8. Unlucky Sevens - with many of the same words.

15. 2-3 Maze - I wasted about 20 min darkening unusable squares, screwed up a couple times, but eventually got the answer. Probably could have saved a bit of time, but oh well.

16. Sweet Sixteen - I have some intuition about trying to fit the middle 6 numbers, but never found a workable solution after some 20 minutes post-test.

17. Yajilin - Did a little bit, messed up - figured it was the same situation as Masyu (larger than expected and little practice), so I left it alone.

18. Wolves and Sheep in Fences - Also not a fan of fences.

19. Magic Puzzle'Rs - ARGH: spent over an hour trying to fit things in. I realized early that Merrell was key - since it had to be placed diagonally. I wasted about 20 minutes of trying to fit it in until I realized it would fit in the other diagonal location. Then wasted another 30 minutes trying to fit in the 7-letter names to no avail. Came back with about 25 minutes left and solved with 6 seconds to spare, but then spent 17 seconds to put in the answer. (Hey Nick, can you number the columns for me next time?) Overtime, but worth the penalty for the 10 extra points (20 for solving, -10 for overtime)

20. SuDOUku - Worked on it for a few minutes - screwed up - then solved afterwards in about 25 minutes, which is pretty good for the points award. DOH. The key was realizing which empty cells forced 2 of one number in a column or row, which then required no collisions in all other columns/rows. For instance, there is a forced 4 collision in column 7 or 8, which means all other columns contain exactly one 4, which can be placed in row 1 for column 6, which conveniently also means all the collisions for 4 are known (row, column, cell). The tricky part is realizing that there are 2 collisions for 7 along rows, columns, and cells.

21. Di-Agony - Haven't tried it and no real intention to, either...

22. Four Square - Spent about 10 minutes post test looking at some clues, but I've never really seen Snake before, so I left this alone.

23. Inside/Outside Corral - Remember what I said about Corral?

Results: I think 100 points. (Hopefully I counted correctly for 11.) I probably should've gotten 125 points (-15 for 7. and -10 for 19.) Again, if I had been able to prep and were in practice, probably could have also squeezed in KenKen, C Note, and SuDOUku for another 50 points. Ideally, maybe also Masyu or Yajilin, but I'm ok with trying to the potential 175 mark I think is doable for next year. (with appropriate point scaling)

USPC 2008 wrapup

Edit: score update

I was a little worried going into this year's competition, given the quantity of grid-based puzzles (black pearl, arrow ring, masyu, kuromasu, fences, corral, etc.). I had tried practicing using last year's Masyu (which I almost completed in time last year), but ended up wasting a lot of time trying to work it out.

Anyway, this year I felt a lot better on my time management. Initially, I thought maybe I shouldn't have spent so much time on KakurOh or Ampers& Crisscross without getting any solutions and instead focused on fences, but I ended up taking way too much time to complete fences after the contest was over, so I think some of the harder difficulty puzzles of that time end up eating a lot of my time.

Battleships was straightforward, as was Sudoku. I probably lost some time on Sudoku with a guess in the middle that didn't pan out, after which I had to start over, since I didn't distinguish my guesses from my solves like I normally do using pen vs. pencil.

Sum figure was pretty quick, given the quick constraints on 10 and 30. That leaves 10 as either 0 1 3 6 or 0 1 2 7. Heuristically, these should probably be placed according to the size of the sum they need to be in, which worked out well.

Arrow ring was also reasonably quick, since all my guesses turned out to be correct. I think this is one of those puzzles where my heuristic approach yields some really good results. I practiced on last year's arrow ring to great success, so I think I can try a looser strategy next time to gain back some time.

Double feature was rather nice this time, as I figured out the differences much faster.

Black Pearl was a quick solve, but I made two major screwups. First, I misinterpreted the directions for answer submission, and counted the lengths of the paths between all 1's in the sequence. The diagram doesn't differentiate between this interpretation and the actual answer format. Then I miscounted, which is unfortunate, since otherwise I might have been able to request some points back. My solution (in diagram form) is correct, though.

Masyu was much quicker this time, because of the increased number of constraints.

Nebijok was a standard puzzle type that went pretty well.

I didn't try Number Blocks until late in the contest, since usually I'm bad at the math ones, but this one was very open to a successful attack. The first puzzle, heuristically should have the 3 24's as the bottom sum and the two large products. This quickly yields most of the digits. The second puzzle also worked nicely, since the product has to be 1 x 2 x 8, and 8 is the only number that will work for the top row. The rest fell into place quickly after that.

I didn't try Kuromasu, it seemed very corral-esque to me, and I suck at corral.

Murder No. 6 was fun. It was slow going at first, but picked up speed quickly. As mentioned by others, the 15's and 14's and even the occasional 13 helped a lot.

Obviously I skipped Corral as well.

Tilted Weights I didn't bother trying as I usually suck at these, although a glance after the contest suggests that it should be quickly solved. The bottom two balances are pretty well constrained, and to balance the overall puzzle, the leftmost balance needs to be two relatively large consecutive numbers.

Distances also seemed too close to Corral for comfort.

Dot Triangles looked pretty impossible, and given Tom Snyder's reaction to it, I think skipping it was an excellent choice.

Crisscross Pairs worked out nicely. I think there are probably some faster methods (such as focusing on the rings rather than the 4th vertical word which has more constraints.)

Fences I almost got near the end. All but the bottom-right corner worked out quickly, and it was just a matter of trying to get the middle worked out, while keeping all the sheep on the same side of the fence. I ended up solving this after the contest after maybe 30 minutes due to a number of mistakes and lack of time pressure at that point.

SuDON'Tku is one I probably should have worked harder on. I only spent a few minutes, made a mistake, and decided it could be very risky to continue to try this puzzle given the number of mistakes I might make. I tried it a little bit after the contest and made more mistakes, but eventually figured out the strategy, so I think I should be pretty quick now.

I wasted a lot of time on KakurOh, only getting about 1/6 of the puzzle. There are generally fewer quick logic-solves in the beginning for these harder KakurOh's, which is something I'm not used to, I think. Either that, or I missed some vital clues.

Ampers& Crisscross is something I also should've gotten. I had an initial guess that didn't pan out, but that was probably because I was taking a more local strategy for this (which works well for me in other crisscrosses). I think the approach of working out the rings is probably the quickest, since that gives many more constraints on the connecting words and ring location.

Total Solved Points: 150 145 (Um, it's a good thing I can add correctly during the competition?)
Likely Resulting Points: 135 (-10 incorrect Black Pearl answer, -5 incorrect answer penalty) 145 (SOMEHOW, they gave me credit for Black Pearl, EVEN THOUGH I made the mistakes in submission above (and also dropped a comma apparently).

Improvement over last year: LOTS.

Gearing up for puzzling

The Google US Puzzle Championship is less than 3 weeks away! After my poor performance in 2007, I'm eager to prove myself this year. Ideally, if I had optimized time, I should have scored ~200 points in the 2007 competition, but failed even to match my score from the year before. If you want to see an analysis of my mistakes in one poorly formatted run-on paragraph, feel free to read the above-linked post.

My plan at this point is probably to capitalize on the fact that finals week will be pretty empty for me, so it will give me a chance to do a couple of things in preparation:

1) Read through Tom's blog to scavenge for tips and strategies. I actually didn't realize that he had devoted an entire post recently to the USPC, and only thought that he had some posts up primarily on Sudoku, but YAY!

2) Work through some old puzzle competitions, trying to remember the key piece of data that unlocks the rest of the puzzle. This should help me get into the mindset of hunting for these rather than trying some blind manipulations of the puzzles.

3) Work through some of the puzzles I've been neglecting in Mensa's blue book. While I'm not a big fan of Mensa's IQ arrogance, the puzzle books they publish are quite nice and both a large variety of puzzles and a range of difficulty for each puzzle type.

4) Stop playing so much DROD. I learned about DROD through www.mathpuzzle.com, which has the occasional post covering a smattering of puzzles, optimization problems, and math research related to games and such. At the moment, I'm on levels 13, 14, 15, and 16 (using the warp in level 12 to make all of those levels available through the restore function) of the Architect's Edition, a free open-source version of the original DROD. While the puzzles are not quite as nicely play-tested as, say, Journey to Rooted Hold, free trumps $20 at the moment.

There is a version of the original DROD using the new engine: King Dugan's Dungeon. However, it does cost money. I will probably buy it at some point for the online tracking system. In addition to the updated graphics, voice acting, and new secrets, it does add a couple features that are very desirable and missing from the Architect's Edition: the ability to undo the last move (even if it resulted in death), and a timer to keep track of Roach Queen, Snake, and Tar Mother behavior. I'm not sure if the engine for KDD is the same as that for The City Beneath, which includes the excellent ability to click on orbs and see which doors will be activated and in which way. Regardless, I did come up with an excellent workaround regardless. Overhead markers work great (being water-soluble) for writing directly on your monitor! This has helped me immensely, by notating switches, as well as marking the location of walls and trapdoors otherwise hidden by Tar.

Why you should teach your kids to spell

Because Sodoku is something completely different!

Thanks to comments on Tom Snyder's excellent post on Soduku, the newly invented Jedi vs. Droid laser battle puzzle.

sudoku strategies

First, since it comes from a shortening (the Japanese people love shortening words - it's like some sort of abbr. obsession) of the phrase "数字は独身に限る" into "数独", can we please use the correct romanization of "sudoku"? It's not that hard, and yes, correct spelling and grammar do improve readability. Also, using non-convoluted sentence structure and refraining from using long words. See "Consequences of erudite vernacular utilized irrespective of necessity: problems with using long words needlessly".

Now that Tom Snyder is putting up videos of both his solving and discussion of various sudoku, the issue of sudoku strategies has resurfaced to my attention. For a while, I had been plugging away at the sudoku in various books. But after watching some of Tom's videos, I seem to be doing slightly better. I'm not sure that I got any really useful advice from the videos, since they are not geared towards the difficulty level I am working at, but I think it has allowed me to make more use of geometry that I hadn't really thought of before.

I do find it amusing that there are all these videos and websites about sudoku strategies, that are really sort-of brute-force:
here are a list of strategies that may be used under very specific and complicated circumstances, when in doubt, just cycle through them until you find one that works.

However, I think Tom has hit the nail on the head by outlining some key principles to "good" sudoku solving:

1. each number written down provides information that may lead to the next number:
- that digit can no longer be present in that row, box, or column
- there is less space for the remaining digits in that row, box, or column

2. fast notation can help immensely (this seems to be quite useful for me)
- marking cells in a box when a single digit can only be present in two or three cells doesn't help immediately, but it can under the following cases:
- filling in the same digit elsewhere narrows down the choices
- noting that another digit or two must be in the same set of cells "traps" those digits to those cells. often this allows one to bruteforce the remaining digits in the cell by comparing across rows or columns

3. flexibility is key
- switching from strategy to strategy speeds up solving immensely, but requires that one be able to recognize a viable angle of attack that may yield good results

I think my math team training is fairly useful for 3, as time constraints on problems forces the development of rapid analysis of what strategies to pursue next and when brute force should be used to open up new angles of attack.

Anyway, one of these days, I will probably develop a better discussion of sudoku strategies in my editorials section. I think it could be useful to formalize strategies (and not just for sudoku; I seem to have improved a lot with killer, wacky, and diagonal variations recently, too.)

Not that I think I will ever be good enough to make the US team or anything, but I would like to think I'm improving overall. After last year's debacle with the US puzzle championship, I'm hoping for a stronger showing this year. Don't forget to register! Techers represent! (Wei-hwa and Tom are both caltech alums)

USPC 2007

ARGGG. I should've done better this year for the puzzle championship, but instead I did worse. I spent a little too long on 1. Battleships. It should've been a quick 5 minute solve, but ended up taking more like 10, because I missed the third 0 column. *smacks forehead* I missed 2. Diagonal Sudoku, because I did a really stupid end-game fill-in where I put 9 instead of 5. It should've been obvious that it was a 5, because everything else was solved! That makes a 20 point differential right there (15 for solve, -5 for penalty). 3. Sum Figure: Guess and check did the trick. I'm not sure of a methodical algorithm that is fast enough, but I didn't see the 0-9 until a few minutes in. Remind me to read the directions very carefully next time. 4. Count Me In: I think I had a nice method for this, which involves counting hypotenuses by enumerating along possible directions. So I counted by vertical, horizontal, positive and negative slope for the triangles, which worked. The check revealed one I missed, but I managed to get the right answer pretty quickly and am happy about the method. 5. Comic Strips should've been easy. I spent too much time worrying about reflections and rotations, when I should have looked for the key, which was the H in the last strip. It forces only three possibilities for Cho (without reflection), which then makes the solve really easy. That's another 15 points. On 6, I missed J4 for some reason, and put both cells for one of the two-cell changes instead. Not sure how they are going to grade it, could be a 9 (ignore the extra square, no penalty), 15 (include extra square, plus 5 point bonus), or 4 (extra square is wrong, 5 point penalty). 7. Circuit Maze also was quick, even if it looks daunting. From a couple minutes worth of playing around, it is clear that one can work backwards to eliminate dead ends. Meanwhile, using different color pens for the different layers, one can draw some of the necessary segments where there are only two elevators per path segment in one layer. That's another 15 points. 8. All About Rio was pretty straightforward. I accidentally had Maia placed incorrectly near the end, but realized it was probably a mistake and corrected. However, I spent time looking for the rest of the phrases to check, which may have been unnecessary. 9. Round Trip, I finished 5 minutes over, so I didn't submit an answer, but I stopped solving in the middle and returned to it later to finish. I think some more experience with this format and 10. Arrow Ring is going to improve my times on those puzzle types dramatically. So that's 10 points, and possibly 10-15 minutes shaved off if I were better at those types. 11. Tiling, is a piece of cake, and doesn't require cutting out the pieces either. That should have been another easy 15 points. 12. Masyu, I didn't finish, though I spent about 5-10 minutes on it. Wikipedia's tips are rather basic, and I self-discovered some more advanced constraints that would've been helpful if I had known them earlier. Still haven't solved this yet, though. 13. Fence Posts, and 14. Fridge Magnets are both puzzle types I'm bad at, so no solve for those two. 15. Gull from Ipanema: Perhaps I would be faster if I were more methodical. I'm thinking perhaps that a fast way to do these is to use a giant paper cutter to make individual squares for each and then group by some criterion (number and distribution of objects) to find pairs fast, but the labels wouldn't be there, so it might take longer to backtrack to find the coordinates to submit. I am not a big fan of the puzzle type for 16. Corral either, but this may just take some work. 17. Multiplicity looked daunting, so I didn't do it, but it works out rather easily if you enumerate the possibilities for each digit, realize that the 0 forces 5 or 6, and then the rest follows pretty naturally. I glanced briefly at 18. Double Murder for a bit, and realized it would've been hard to get started, much less finish in a short amount of time, so I skipped it. I worked on 19. No Parking twice, and got it the second time with 2 minutes before the end. I think the key here was the limited placement possibilities for "on one's honor". Also, I had the beginnings mostly correct the first time I approached the problem, so I probably would've gotten it marginally quicker if I hadn't switched to other puzzles. Other key phrases were "unobnoxious", "mano a mano", and "economic" for me. Once I filled those in a few of the cross phrases, I knew I was on the right track. 20. ORu Kakuro looked daunting, but I managed to get the bottom-right corner. I then tried the top-right corner to no luck, so I gave up, thinking this puzzle would take too long.

Score:
94, 99, or 105 depending on grading for 6.

Lost points that I might have gotten if I hadn't messed up or wasted time:
105

going to work on 18 and 20 now.

EDIT: It turns out that I forgot to submit when I had answers for 3. and 19., resulting in a score 40 points lower than I had thought. *ouch*. The grading for 6 was middle of the road, as I expected, giving me a total of 59 points, a significant decrease from 2006. However, overall, I felt like I performed better, with a number of puzzles very close to completion this year, as opposed to last year, where I was hoping to get lucky with guess and check.