Entries by Ted Campbell

Following College Puzzle Challenge 2007 Pre-Event Puzzles #2, it is time for puzzle #3, Rotation Schedule.

This was a fun little puzzle with codes on codes that reminded us of a problem from 2006 IPSC Contest called Matrioska (which are those Russian doll things that fit inside each other). The IPSC problem involved decoding the first puzzle or program who's output was another puzzle itself.

This Puzzle Challenge one starts off with a page of Pigpen cipher symbols. Decoding these symbols gives the following sequence of letters:

ROTTHR EEURWD WHGQLQ HWBFOR FNZLVH STVQJQ HNECYS USLZEI

'ROT THREE ... <gibberish>' Now ROT-13 refers to a Caeser Cipher with a shift of 13, so ROT-3 is a shift of three letters instead. Since we are decoding, we actually want to undo the rotation which is done by rotating forward by 23 (which is 26 letters - 3). David found a simple online shifter here (although it is a very easy task in nearly any programming language) which we used. Deciphering the remaining letters in the string we end up with:

****** **ROTA TEDNIN ETYCLO CKWISE PQSNGN EKBZVP RPIWBF

This time the clue is 'ROTATED NINETY CLOCKWISE ... <gibberish>'. At this point David started looking into trying things like ROT-(90 modulo 26), and I decided the clue referred to geometry and tried to figure out ways of rotating the pigpen symbols.
Once again since we are decoding, we want to rotate 90 degrees CCW instead. I was about to start writing the gibberish part to Pigpen so I could rotate the page, but quickly realized that I just needed to look at the pigpen grid and have the letters move position 90 degrees around the respective hash or cross. The result of this transform was:

****** ****** ****** ****** ****** ROTNIN EMDYUR LRCXDB

Similar to before, 'ROT NINE ... <gibberish>'. Undoing the ROT-9 we end up with:

****** ****** ****** ****** ****** ****** *DUPLI CITOUS

My final answer: DUPLICITOUS
The real answer: .. we'll see ..

This is enough procrastinating for one day... Ted, out.

Continuing the post College Puzzle Challenge 2007 Pre-Event Puzzles #1, I'd like to briefly describe our answer to the second puzzle, A Heartbreaking Work of Lyrical Genius.

This puzzle took us the longest time to do, but I think most of that was due to the fact I did the research wrong (yep, my fault this time). The first difference we noticed we looked at this puzzle was there was no intro paragraph full of clues this time. Just a list of lyrics. We quickly recognized these were real songs and went to find what they were. Unfortunately I managed to swap a few of the band names and song names (I blame confusing lyrics websites). After a few days of getting nowhere, we discovered the errors and corrected them. Now with the correct list and a fresh look we noticed a pattern in the song list.

        Scar Tissue - Red Hot Chili Peppers
      Lose Yourself - Eminem
           Freebird - Lynard Skynard
              React - Erick Sermon
      The Adventure - Angels and Airwaves
Truely Madly Deeply - Savage Garden
  Dirty Little Girl - Elton John

  Lights and Sounds - Yellowcard
               Blue - Eiffel 65
         Skater Boy - Avril Lavigne
 Losing My Religion - R.E.M.

Beach Side Property - Modest Mouse
    Like Satellites - Over It
Blasphemous Rumours - Depeche Mode

          Head Club - Taking Back Sunday
     Wild West Hero - Electric Light Orchestra
Living in the Roses - New Model Army

Much better. RELEASE YEAR MOD TEN. Our first explicit clue. From here on it was straight forward. Look up the release years on songs using Wikipedia and Last.FM and taking the last digit from the year (year mod 10), we get a new number for each line. Number n meant use the n-th word from the given lyrics to form a new phrase. We had to fudge the release years a bit to make sense but we ended up with 'I WAS A MEMBER OF THE POLICE AND I WROTE AND SANG THE HIT SONG DESERT ROSE'. An issue that bugged Dave while we struggled with the wrong clues was that there were only 16 words at the bottom but 17 songs. In the end, it seemed this was just a mistake as the word that slipped through was 'I' and was probably accidentally forgotten.

More searching resulted in finding that the artist was Sting. Another problem solved. These problems are addicted and frustrating at times, but looking back this one wasn't too difficult if we had gotten the research right at first.

My final answer: STING
The real answer: .. we'll see ..

Puzzle Challenge 2007 Logo

Well, the College Puzzle Challenge hosted by Microsoft is coming up again and David, Pete, Greg, and I are signed up as a team. We were at the event last year for the first and didn't do as well as we hoped (we were in the middle of the pack overall) and we plan to change that this year. There are a few practice problems that go up before the contests starts and we've been working through them. So far we have 3/3 "solved" and are waiting for the last two to go up. These are my answers to the puzzles with help from the others. These aren't necessarily correct and I'll link to the official solutions when they come up but I thought I'd put these up anyways.

The first practice puzzle, Symphony No. 31, Op. 66 was full of little clues on how to proceed.

Reading through the description a few times I noticed the letters I, S, and O in bold in the name 'Interdepartmental System Operations'. ISO.. due to the fact that computers have taken over my brain, the first thing that came to mind was ISO standardizations, but hey, I'm crazy, it is probably something else. None the less, I look for the numbers on the page 31 66 1 and search for a standard with those numbers, and sure enough, ISO 3166-1 is the standardization of country codes.

By looking at the music notes in the puzzle, it is quickly apparent that they are in pairs and music notes have letters... two-letter country codes anyone?

Decoding this we wind up with a list of countries:

1. Canada
2. Antigua
3. Barbados
4. French Guiana
5. Ecuador
6. Burkina Faso
7. Andorra
8. Great Britain
9. Belgium
10. Germany
11. Bosnia
12. Egypt
13. Bulgaria
14. Estonia
15. Georgia
16. United Arab Emirates

These countries are loosely clustered by location so I try to plot them on a map and connect the lines, ending up with this :

Countries mapped out.

The letters ML appear backwards on the map. This is the country code for MALI so that is what I am calling my final answer. I'll find out when the answers are released whether this is correct. Up until the map is almost certainly correct but I wonder about my interpretation of the final answer. Looking the puzzle over some more I noticed another clue which is the fake composer's initials are MAP. A final big clue that Pete noticed was the notes also encode Morse code and say CONNECT THE DOTS. Both these extra clues reaffirm the solution.

My final answer: MALI
The real answer: ...we'll see...

I got the game BioShock when it came out and had no issues when I started out and happily started playing through the game. Then as usual, I started screwing with things that I shouldn't have and updated my BIOS just so I could have the latest version. The update worked fine and everything was alright until I tried to continue with BioShock upon which I discovered there was no more sound in game. I have a MSI P965 Platinum motherboard and currently use its onboard sound controller. After rolling back the BIOS a few times I determined the breaking version was the 1.03 which has a change list indicating changes related to the north and south bridge were made and these changes seem to have screwed up my sound. Reverting to 1.02 fixed all problems and I was able to finish the game. After the breaking update I noticed that Vista (Home Premium x64) recognized sound as a new device. Maybe new drivers got screwed up, but I'm not sure. I didn't explore it in much detail. The sound worked in Windows and for the loading of the game, but once DirectSound (or whatever it is now called in DirectX10) started, the sound was gone. I didn't compare with other games though so I can't comment on how they handled it.

Hopefully the search engines will catch this and help anyone with similar problems.

I recently reformatted my desktop and so had to reinstall and in the process updated to newer versions of things. Since I do play with Windows development I reinstalled the latest platform SDK (Feb 2007) now known as the Microsoft® Windows® Software Development Kit Update for Windows Vista™. In an attempt to put off doing some homework I looked around through what was included in this latest SDK and was happy to find full x86/x64 native compilers and cross-compilers. I'm just a student who doesn't make any money with the code I do so I just have been using the Express Versions of Visual Studio 2005 which are free but are limited. They don't include interesting features to play with like OpenMP and 64-bit compilers. Now with a new 64-bit computer I was happy to have 64-bit windows compilers to play with. Anyways, I discovered that the compilers have /openmp flags enabled and seemed to work, although the program wouldn't run thanks to some missing dll's.

The next step to getting it working was to find the Visual Studio 2005 redist pack that contains the dlls for running Visual C++ programs such as the standard library DLL and of course the OpenMP runtime DLL. Now the compilers with this SDK are 14.00.50727.762 which are aligned with Visual Studio 2005 SP1 so we need the SP1 redist pack. The redist pack is available here (x86) or here (x64). This included the necessary vcomp.dll (The OpenMP runtime dll for Visual Studio 2005 SP1) but my test program still couldn't find it.

A bit more searching revealed that I was supposed to #include which would set up the manifest for side-by-side assemblies (Here is a brief description of the side-by-side assemblies thing). Running it again... Success! The test program ran. A quick check of the assembly code generated revealed it did in fact generate the OpenMP code.

Now to see if I could integrate at least partially with the Visual C++ Express IDE. It seems the latest Visual C++ 2005 Express edition has the /openmp option availible in the project options so I just needed to make sure that it was enabled. The one thing to make sure of when setting up is the Windows SDK is that the VC/Include directory is included in addition to Include (same goes for Lib). Compiling and running and it all seems to work still.

After playing around for a bit I discovered one big caveat is that there is no debug version of the OpenMP runtime available with this setup so we'll need some trickery so that omp.h doesn't try to set us up to link to it when the _DEBUG flag is set. It seems that this isn't enough to get program to run in debug mode. When OpenMP is enabled this way, even if we use this preprocessor stuff so that the non-debug version will be linked, if we also link to a debug version of the C/C++ runtime things will break. This means you will need to disable openmp when using debug versions of the CRT.

#ifndef _DEBUG
    #include <omp.h>
#endif /* _DEBUG */
 

What is OpenMP?

OpenMP is a specification of langauge extensions that allow a programmer to specify parts of the program that can be parallelized and the rules that need to be followed for correctness. Work is dynamically assigned to worker threads that automatically created by the OpenMP runtime. This allows data parallelism to be dealt with, without the need to manage threads and resources. I don't know much about it as I'm just starting to play with it so I'll let <insert search engine of choice> tell you more about it.
(Recent versions of GCC should also support OpenMP directly.)

The dead Linksys power supply

Well, not quite a 'ring' but one red LED.

A few months ago my internet decided to cut out while I was working on a project in the middle of the night, so I went through the usual diagnostics of trying to reset everything, but with no luck. Closer inspection of the router revealed that only the red diagnostic light was on, and it was dimmer than usual. I assumed my router was toast but, decided to make a few attempts to get my internet restored that night.

I can't recall how, but I eventually reached the conclusion that the power supply had crapped out, so I went looking for another 5V power supply. Fortunately I discovered another old router that had one. A bit of soldering later, I had the connectors on the power supplies swapped and voila! It worked! So my internet was back up and I could finish the work on the project.

Now that was a few months ago, so why do I bring it up now? Well, Dave mentioned he had a dead WRT54G and explained the red light just blinked. It sounded like it could be a similar problem, so we plugged it in and the red light came on rather dim -- just like mine. Chances looked good that it might be the same problem. Checking the power supply with a multimeter we found it was 5V as it should of been. Not yet convinced the power supply worked, we popped open the router and checked the voltage when under load and sure enough it was 4V... Too low to power the router. To confirm the router itself works, we temporarily hooked up the 5V from a molex connector of a computer power supply to the router and it started up normally. Problem solved! Now we just need to locate a new 5V power supply for it...

So if you have a dead WRT54G in your closet with only a faint red light showing when you turn it on, you should try another power supply and see if you can give the beast a second chance at life.

Now, while we're on the topic of routers... I feel like I should mention Tomato -- the firmware Dave and I both use. It's got the nicest interface I've ever seen on an embedded device (complete with pretty graphs and smart use of Ajax). It also boots much faster than DD-WRT (although I've heard rumors that things like VPN don't work very well).

The red light of doom

For the summer I'm working on adding features to, cleaning up, and making algorithms more generic in a academic research tool. Overall the algorithms and data structures are well planned out and have been generally quite friendly to improvement. As part of my work, I'm integrating derivative versions created by people in their research so it isn't surprising when certain things are hacked together just to get them working, but sometimes it is a little overkill.

The fun example I've found that convinced me to write up this post was using a FIVE dimensional dynamic array to store some information. While I can see some reasons for it, there was quite a shock when i noticed the typecast to (short*****). Here is the code if you dare! (I replaced the variable name with a much shorter one)

foo = (short *****) my_malloc ((nx+1)*sizeof(short ****));
for (i = 0; i < nx+1; i++){
  foo[i] = (short ****) my_malloc ((ny+1)*sizeof(short ***));
  for (j = 0; j < ny+1; j++){
    sblock_pattern_init_mux_lookup[i][j] = (short ***) my_malloc (4*sizeof(short **));
    for (from_side = 0; from_side < 4; from_side++){
      foo[i][j][from_side] = (short **) my_malloc (4*sizeof(short *));
      for (to_side = 0; to_side < 4; to_side++){
        foo[i][j][from_side][to_side] = (short *) my_malloc (nodes_per_chan*sizeof(short));
        for (itrack = 0; itrack < nodes_per_chan; itrack++){
          foo[i][j][from_side][to_side][itrack] = UN_SET;
        }
      }
    }
  }
} 

I really don't believe this was the best answer and I can hopefully cut this out.

EDIT: Apparently there were so many *'s it broke the blog software...

Well, it is about time that I start posting so here it goes. The other day, Dave, me (Ted) and a few friends decided to try to solve the Facebook Optimal Movie Seating Puzzle based off of an XKCD comic.

The gist of problem was that you are seating 16 people in a movie theater with a series of rules that assign points for different arrangements such as seating friends beside each other. You want to find an optimal arrangement that maximizes the 'social enjoyment'. Now with 16 people there are 20 922 789 888 000 permutations. This is a fairly large number number of possibilities to test each one on a normal consumer grade computer.

To tackle the problem Dave started writing a client-server scheduler to split up the work among multiple machines for a cluster-computing effect. I'd guess he will write up a post on it soon. Meanwhile, I began to tackle looking at ways to quickly evaluate the 'social enjoyment score' and also figure out how to narrow down the solution space so we didn't have to actually test all twenty-one trillion possibilities.

• To handle the issue of finding scores we first agreed on an interpretation of the rules in which people had to be adjacent for the rules to take effect. Some of the rules involved pairs of people and other rules involved triples. We addressed this by generating a lookup table at the start that assigned a score for each sequence of three people. Using the lookup table we would find the partial scores of partial seatings as we permuted the possible seatings. Now this still involves checking every possible seating, albeit much faster than the first version.
• To cut down the solution space we looked at the maximum value that appeared in the lookup table which was 4 for us. If only n people are left to be seating, we know at best our partial score can only improve by 4n and thus can know after seating only some of the people that no mater how we arange the unseated people, this will never beat our current best so we don't need to even try all those combinations. This simple heuristic made a huge difference in speeds (I think the factor was 10x but I'm just making that up off the top of my head).
• Determined to get it even faster we looked into our lookup table some more. We realized that all the cases that had 4 points were disjoint and that only one of the could be true in a given seating. Once one of the 4 point arrangements was used the highest value was now 3 points. We updated our heuristic from 4n to 3(n-1)+4 which gave the code a much better early estimate on when a partial seating arrangement would not be able to outperform the current best score. This sped up code by another factor of 10x or so (again I'm making up numbers since i don't remember and our measurements were hardly scientific).

We decided we should let it run through the full set and turned on the compiler optimizer for another 2x faster. In the end our our runtime estimates went from the order of 1000 cpu-hours with the first version to under 5 cpu-hours in the end. This really stresses the benefit of optimizing your algorithm versus optimizing the code itself.

I'm sure this problem could be solved much much quicker and we may make another attempt at improving our method.

EDIT: It seems this wasn't clear (which was my fault), but as pointless as it may be, we were aiming for a solution that ensured it covered all options in case of local minima (which for this problem was pretty much a non-issue anyways). There are certainly far faster and more practical probabilistic ways as people have been pointing out.