It’s Friday, and time again for the Friday Fragment: our weekly programming-related puzzle.

This Week’s Fragment

After last week’s commemorative fragment, we’ll resume our game bots.  Let’s make our bots more interesting by letting us play instead of just watching:

Write code to let man compete against machine (a game bot) in rock-paper-scissors, tic-tac-toe, or Reversi (your choice).  Present the game board on a web page, let the human player make the next move, and then call the game bot for its move.  Continue this until one side wins.

To play along, provide either the URL or the code for the solution. You can post it as a comment or send it via email.  If you’d like, you can build atop the bots and/or source code at http://derekwilliams.us/bots.

Last Week’s Fragment – Solution

Last week’s puzzle was another cryptogram:

OBKR
UOXOGHULBSOLIFBBWFLRVQQPRNGKSSO
TWTQSJQSSEKZZWATJKLUDIAWINFBNYP
VTTMZFPKWGDKZXTJCDIGKUHUAUEKCAR

I offered a hint (“try some googling”) and a short-cut (“just offer suggestions on how to go about solving it”).  And for good reason: this is a somewhat famous unsolved cryptogram.  It’s Part 4 of Kryptos, Jim Sanborn’s sculpture at the CIA headquarters. I posted it last week in celebration of its 20th anniversary, and the recent release of a new clue.

Many experts and other sorts have worked on solving Part 4, in search of fame or just a good challenge.  I think it utilizes a one-time pad or a long key, perhaps along with the Vigenere Table found on the sculpture.  The key or pad may be located on-site; for example in the underground utility tunnel.  Time will tell.

If you think you can crack it, don’t just tell me: send your solution to Sanborn for verification.

If you’re just interested in Sanborn’s work, check out photos online.  The CIA Kryptos sculpture is now closed to visitors, but you can visit Sanborn’s other sculptures, such as The Cyrillic Projector and Adam Smith’s Spinning Top at UNC Charlotte.  Just don’t show up at his home.

It’s Friday, and time again for the Friday Fragment: our weekly programming-related puzzle.

This Week’s Fragment

Having finished a series of game bots, we’ll have a Thanksgiving change of pace and do another cryptogram.  Crack the following cipher:

OBKR
UOXOGHULBSOLIFBBWFLRVQQPRNGKSSO
TWTQSJQSSEKZZWATJKLUDIAWINFBNYP
VTTMZFPKWGDKZXTJCDIGKUHUAUEKCAR

You can provide the solution or just offer suggestions on how to go about solving it.  For example, I can’t solve it, but based on its background (try some googling), I have ideas about how it might be solved.  To “play along,” post your response as a comment or send it via email.

Last Week’s Fragment – Solution

Last week’s puzzle was to code a simple Reversi competition:

Write code to call competing Reversi bots, flip pieces, and score the results.

Here’s a solution in PHP.  

<?php
  require('reversimove.php);
  $urls[0] = 'http://derekwilliams.us/bots/reversi';
  $urls[1] = $urls[0];  // Your bot here
  $pieces = array('X', 'O');
  $board = str_repeat('.',64);
  $board[27]='O'; $board[28]='X';
  $board[35]='X'; $board[36]='O';
  $player = 0;

  for ($i=0; $i<64; $i++) {;
    $play = file_get_contents($urls[$player].'?board='.$board.'&piece='.$pieces[$player]);
    $board = update_board($board, $play);
    show_board($board);
    $player = $player == 0 ? 1 : 0;
  }

  function show_board($board) {
    $scores = array('.' => 0, 'X' => 0, 'O' => 0);
    echo '<table border="1">';
    for ($i=0; $i<8; $i++) {
      echo '<tr border="1">';
      for ($j=0; $j<8; $j++) {
        $piece = $board[($i*8)+$j];
        $scores[$piece]++;
        echo '<td border="1">'.$piece.'&nbsp;</td>';
      }
      echo '</tr>';
    }
    echo '</table><p>&nbsp;</p>';
    printf("<p>X: %d, O: %d</p>", $scores['X'], $scores['O']);
    if ($scores['.'] == 0)
      exit(printf("<p>%s wins!</p>", $scores['X'] > $scores['O'] ? 'X' : 0));
  }
?>

You can run this solution and other bots from the links at http://derekwilliams.us/bots.  This page also includes full source code, including helper functions.

It’s Friday, and time again for a new Fragment: my weekly programming-related puzzle.

This Week’s Fragment

This week’s puzzle is a new type of challenge: SQL coding.  And since taxes and health care reform are all the buzz this April 16, that will be our backdrop.

Owen Moore, fearless programmer for the IRS, would like to help small businesses cope with certain health care reform provisions.  In particular, he’ll provide free reports to companies showing who to fire to get below the 50-employee limit by 2014.  Fortunately, he has an Employee database table populated from recent tax filings.  It has, among other fields, EmployeeID (SSN, char(9)), CompanyID (EIN, char(9)), and HireDate (a date).  Since last-in-first-out seems reasonable, his “pink slip pick list” will show all but the 49 most senior employees in each company.  That is,

select companyid, employeeid, hiredate
from employee e
where …
order by companyid, hiredate

Can you provide the missing fragment (fill in the “…”) to complete Owen’s SQL?

If you want to “play along”, post the SQL as a comment or send it via email.  To avoid “spoilers”, simply don’t expand comments for this post.  Owen will be owing you a big favor.

Last Week’s Fragment – Solution

Last week’s puzzle required helping Mark Duke recover his forgotten Linux password.  We had his /etc/shadow entry and knew that he was a “roller”: someone whose password is simply his user ID followed by a number (two digits in this case).

The /etc/shadow password format is well documented; even Wikipedia covers it.  The “$6” at the beginning indicates that it uses SHA-512 hashing with the salt following.  The unix crypt(3) function makes easy work of this, especially since there are wrappers in just about every language imaginable.  I chose to code it in PHP:

for ($i=1; $i<99; $i++) {
   $attempt = sprintf("%s%02d", $userid, $i);
   if (crypt($attempt, $salt) == $password) {
      echo "Password is: " . $attempt;
      break;
   }
}

The password is markdupe42.  42: what else?

My son, Spencer, coded in Python, and posted his solution (see comments in last week’s post) shortly after he read the fragment.  Now you see what I’m up against: this guy can dump your LM hashes and dictionary-crack your Windows passwords in no time.

I commend readers for not just posting “sudo apt-get install john”.  Yes, there are tons of programs like John the Ripper for quickly cracking passwords, with no coding required.   This reinforces the need to choose strong passwords (likely not in any password dictionary) and use different passwords for different sites.  Frequently changing passwords is really no help, as we learned this week.

Since it’s spring break (and I’ll be kayaking tomorrow), this week’s Friday Fragment comes to you a day early.

This Week’s Fragment

Mark Dupe has forgotten his Linux password.  But he has done two (insecure) things that should make it easy to hack his way back in: 1) his password is always his user name, followed by a two-digit number (he “rolls” it), and 2) he has a readable backup of his /etc/shadow file.  Here is the entry for his account:

markdupe:$6$mLo3uqlc$EM4O2X5zaUo.zWzZW2Ksz.IZyxKL6cz0DIjd.wJB3s.6uuKQ7K7/
3cSz3eEL3D0VXzgbmtxSlkeoZLGYMIp89/:14706:0:99999:7:::

Can you write code or a script to determine his password?

If you want to “play along”, post the password and/or code as a comment or send it via email.  To avoid “spoilers”, simply don’t expand comments for this post.  Mark will thank you, at least until someone else hacks into his account.

Last Week’s Fragment – Solution

Last week’s puzzle required correcting a check routing transit number (374088048) and/or credit card number (4754 2700 7476 257x) from a torn slip of paper handwritten by Pierre Lefebvre.  I received some excellent responses on this; see the comments for last week’s post.

As Joel Odom pointed out, you can plug in possible digits until you get a valid checksum.  Credit card numbers use a mod 10 checksum (the Luhn formula), where you double alternate digits, add the digits of the products, and then add these to the other digits.  The total should be evenly divisible by 10.

For 4754 2700 7476 257x (where x is the missing digit), the alternate “doubled” digits are:

(4*2), (5*2), (2*2), (0*2), (7*2), (7*2), (2*2), (7*2)
or:
8, 10, 4, 0, 14, 14, 4, 14

adding the digits of the products:
8 + 1+0 + 4 + 0 + 1+4 + 1+4 + 4 + 1+4 = 32
adding in the alternate (“un-doubled”) digits gives:
32 + 7 + 4 + 7 + 0 + 4 + 6 + 5 = 65

To make this an even multiple of 10, that last missing digit must be 5 (65 + 5 = 70), so the credit card number is 4754 2700 7476 2575.

The routing transit number was a bit trickier because there wasn’t a missing digit, and I didn’t specify exactly what was wrong.  But routing transit numbers follow strict rules; for example, the first two digits have to be within certain ranges that identify the Fed district, credit unions/thrifts, special types of checks, etc.  As Joe Richardson pointed out, Wikipedia is right on this one, and from their article you can determine that a valid RT can start with 3, but cannot start with 37.

To find the correct second digit (3x4088048), we use a routing/transit mod check.  It’s similar to the credit card algorithm, except that it uses weights: 3, 7, 1, repeating (many check old-timers know 37137137 by heart).  Wikipedia and IRS publication 1346 document this, among other places.  Here, too, when running a mod check against all the digits, the remainder must be evenly divisible by 10. So, we have:

((3*3) + (x*7) + (4*1) + (0*3) + (8*7) + (8*1) + (0*3) + (4*7) + (8*1)) % 10 = 0
or
((9 + 7x + 4 + 0 + 56 + 8 + 0 + 28 + 8 ) % 10 = 0
or
((7x + 113) % 10 = 0

Plugging in values for x, we see that

(((7 * 1) + 113) % 10 = 0

So the second digit should be 1, and the correct routing/transit is 314088048.

Kudos to Joe Richardson for correcting the routing/transit, and further determining that this belongs to the memorable Alamo Federal Credit Union.  His Rescue 5 product can correct these and other account problems automagically.  Joe also determined that the credit card number is a rebate card issued by MetaBank.  Right again: it’s an old rebate card of mine that I’ve used up.

As Joe pointed out, there are good implementations of both check digit algorithms readily available on the net, in almost every language imaginable.  Even Wikipedia has several, but be careful: their routing/transit code is wrong.  It seems Wikipedia is continuing their tradition of posting bad code; see another example I pointed out in an encryption research paper.

One big question remains: how did Inspector Lestrade solve this so quickly in his head?  Frankly, I think he was bluffing about the Visa number.  That calculation is simple, but usually does require pencil and paper to get it right.  We would all be very impressed, however, if he memorized all the routing/transit rules and could do weighted mod checks in his head.

Well, Lestrade had an advantage: he recognized from the name (Pierre Lefebvre) and handwriting that the second digit was a 1, not a 7.  In handwritten French, ones (1s) look like sevens (7s), which is why the French put an extra line through sevens to distinguish them.  From the Sherlock Holmes stories, it’s questionable whether Lestrade even understands the French language, but he certainly would have recognized the handwriting.

It’s Friday, and time for a new Fragment: my weekly programming-related puzzle.  For some background on Friday Fragments, see the earlier post.

This Week’s Fragment

While the code required to solve this week’s puzzle is small, it requires a little setup.  I’ll do it in story form.

Little Johnny is riding along in the toddler seat at the back of Mom’s minivan, secretly playing with Dad’s new deck of cards which he is not allowed to touch.  Mom gives him the long-awaited news, “we’re almost there”, and he panics: he knows he must put the cards back in the box just the way he found them.  That means just like new, sorted in suit and rank order.  Little Johnny’s stubby fingers aren’t very dexterous, but he knows he can sort them by laying them out in piles and then re-stacking the piles until they’re ordered.  So he grabs his Toy Story 2 lunch box, which gives him room for 4 piles.  He has to hurry, but fortunately he knows a way to do it in only four passes of laying out cards into piles and stacking the piles.  Johnny’s a smart little toddler, because he knows which pile to put each card in for each pass to make this all work.

Are you smarter than a toddler?  Can you write the code to determine the pile number for each card on each pass so that they’re all sorted in the end?

To help out, I’ll post a comment with some scaffolding code.  If you want to use it, just fill in the missing line.

What this is really is a technique that banks have used for years to sort large numbers of checks into various orders (account number, destination, amount, etc.) on machines that have anywhere from 5 to 35 available pockets.  It’s called a fine sort with compression and base conversion, which sounds really fancy but actually boils down to one or two lines of code.

If you want to “play along”, post a solution as a comment or send it via email.  To avoid “spoilers”, simply don’t expand comments for this post.

Last Week’s Fragment – Solution

Last week’s puzzle was to solve the following cryptogram:

Si spy net work, big fedjaw iog link kyxogy

This cryptogram is the dedication in the excellent book, Network Security, by Kaufman, Perlman, and Speciner.  Nothing fancy here: it’s just a simple substitution cipher.  So you can solve it by just sitting down with a pencil and paper and plugging at it, building up the substitution table as you go.  Classic cryptanalysis starts with trying frequent letters (like the nostril combination – NSTRTL, familiar to Wheel of Fortune viewers), common patterns (ad, in, ing, ou, ur, etc.), and common words (to, the, and for are a great start for this puzzle).  If you like such puzzles, try the cryptograms web site.

The solution is:

To the bad guys, for making our jobs secure

That’s a clever dedication for a book on computer security, huh?