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

This Week’s Fragment

Let’s do another game bot: this time, just a bit more sophisticated than randomly answering rock, paper, or scissors:

Code a simple REST web service to play tic-tac-toe.  It should accept a nine-character string representing the current “game board” with space, X, or O in each position (starting from the top left, going left-to-right and down).  It should return a nine-character string with your next move added.

For example, the game board at left is represented by the string ”  O X OX “.  X goes first; if you receive all spaces (empty board), go first with X.  Otherwise, take the next move: if you receive an even number of Xs and O’s, replace a space with an X; if you receive an odd number of plays, replace a space with an O.  And no cheating: if you do anything other than take the next legal move, you lose.

This is your chance to have a computer play your games for you.  Can you code something that plays as wisely as you would?

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.  We’ll have the submitted services compete in some “bot wars.”

Last Week’s Fragment – Solution

Last week’s puzzle continued with our simple RPS game:

Write code to score the results of calling rock, paper, scissors (RPS) web services.  Remember, rock beats scissors, scissors beat paper, and paper beats rock.  And bombs and dynamite don’t count.

Here’s another simple solution in PHP – my bot facing off against Spencer’s:

    <?php
      $winners = array("rock" => "paper", "paper" => "scissors", "scissors" => "rock");
      $url1 = 'http://derekwilliams.us/bots/rps';
      $url2 = 'http://ninjatricks.net/rps.php';
      $result1 = file_get_contents($url1);
      $result2 = file_get_contents($url2);
      printf("1: %s   2: %s\n", $result1, $result2);

      if ($result1 == $result2)
        echo "Tie";
      elseif ($result1 == $winners[$result2])
        echo "#1 wins!";
      elseif ($result2 == $winners[$result1])
        echo "#2 wins!";
      else
        echo "No winner.  Someone's misbehaving.";
    ?>

Again, it’s a bit oversimplified, but does the job.

Now you’re ready for your first “bot war”: see how your RPS bot competes with mine at http://derekwilliams.us/bots/rps.

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

This Week’s Fragment

This week, we’ll take another step in our web service “bot wars:”

Write code to score the results of calling rock, paper, scissors web services.  Remember, rock beats scissors, scissors beat paper, and paper beats rock.  And bombs and dynamite don’t count.

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 results from our last Friday Fragment.

Last Week’s Fragment – Solution

Last week’s puzzle continued along our simple web service vein with the flip-side: calling a web service.

Write code to call your rock, paper, scissors web service and keep counts of how many times each is returned.

Here’s a really simple solution in PHP:

    <?php
      $counts = array("rock" => 0, "paper" => 0, "scissors" => 0);
      $url = 'http://derekwilliams.us/bots/rps';
      for ($i=0; $i<100; $i++)
        $counts[file_get_contents($url)]++;
      print_r($counts);
    ?>

It’s a bit oversimplified (e.g., no error handling), but does the job.

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

This Week’s Fragment

We’ll continue this week along our simple web service vein with the flip-side: calling a web service.

Write code to call your rock, paper, scissors web service and keep counts of how many times each is returned.

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 didn’t implement your own web service from last week or want to call mine instead, use this URL: http://derekwilliams.us/bots/rps.

Last Week’s Fragment – Solution

Last week’s puzzle was to code a simple REST web service that, when called via GET, randomly answers rock, paper, or scissors.  Your result could be fancy (wrapped in XML or JSON syntax), or simple: just the word.

Here’s one really simple solution, in PHP:

<?php
$choices = array(“rock”, “paper”, “scissors”);
echo $choices[rand(0,2)];
?>

Yes, to quote Billy Mays, “it’s just that easy!”

Now you may be thinking it’s not a real web service if it doesn’t use some combination of JAX-WS, Axis, Axis2, Castor, JiBX, JAXB, over-hopped servlets, lots of generated value/transfer objects and/or some other similar Rube Goldberg bloatware solution.  But then that wouldn’t be a fragment.  REST without XML is easy enough, and we want to keep this really simple, demonstrating logic, not plumbing.  If you’re an IIS fan (or don’t want to use PHP or Java), give C# a spin, where even SOAP/XML web services are easy.

And perhaps you see where all this is going… the “bot wars” are coming soon!

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

This Week’s Fragment

Some future Friday Fragments will make use of web services.  So we’ll take it one step at a time, starting this week:

Code a simple REST web service that, when called via GET, will randomly answer rock, paper, or scissors.

Your result can be fancy (wrapped in XML or JSON syntax), or simple: just the word.  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.

Last Week’s Fragment – Solution

Last week’s puzzle was to code a happy number finder.  A happy number is a positive integer which you can replace by the sum of the squares of its digits and repeat the process until you get to 1.  For example, 7 is a happy number because its series ends at 1: 7² = 49, 4² + 9² = 97, 9² + 7² = 130, 1² + 3² + 0² = 10, 1² + 0² = 1.

If you tried this, you know it’s not only a study in happy numbers, but also happy cases.  The basic solution is easy; I coded a quick inductive solution in Ruby as an extension to the Integer class:

  def is_happy
    return case
      when self == 1 then true
      when self < 1 then false
      else self.digits.inject(0) { | sum, ea | (ea * ea) + sum }.is_happy
    end
  end

That’s nice and simple, and 0.is_happy, 1.is_happy, and 7.is_happy all work swimmingly.  However, 2.is_happy loops forever until crashing with a stack overflow.  The reason is that the sum of squares of digits calculations for unhappy numbers run in infinite cycles (perhaps that’s why they’re unhappy). We can prevent that with a cache of numbers we’ve seen before:

  @@cache = Hash.new
  def is_happy
    return @@cache[self] if @@cache.include?(self)
    @@cache[self] = false
    result = case
      when self == 1 then true
      when self < 1 then false
      else self.digits.inject(0) { | sum, ea | (ea * ea) + sum }.is_happy
    end
    @@cache[self] = result
    return result
  end

I posted the complete code as a comment to last week’s puzzle.

No one sent a solution, so I’ll keep the 2011 Corvette ZR1 prize to myself.  But give this week’s puzzle a try; fortune or fame (or at least happiness) may await you.

After a summer hiatus, it’s time again for the Friday Fragment: our programming-related puzzle.

This Week’s Fragment

During the sabbatical, so many devious ideas came to mind: Sudoku solvers, quines, LOLCODE, you name it.  But discretion prevailed; after all, this is about code fragments: small, often elegant solutions that can be written relatively quickly, or used to try new languages and compare their merits.  And since this is such a happy day (with a sunny, happy daytime high), we’ll take on happy numbers.

A happy number is a positive integer which you can replace by the sum of the squares of its digits and repeat the process until you get to 1.  For example, 7 is a happy number because its series ends at 1: 7² = 49, 4² + 9² = 97, 9² + 7² = 130, 1² + 3² + 0² = 10, 1² + 0² = 1.  So:

Write code to compute happy numbers starting at 1.  To eventually get your computer back, you can stop at some high limit: whatever makes you happy.

Of course, this is a common math puzzle, so there are likely many implementations on the web.  But no peeking.  Try it for yourself and aim for something interesting: least amount of code, a new (to you) or unusual language, best use of recursion or induction, best performance, etc.

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

Last Week’s Fragment?

There wasn’t one!  The Friday Fragment was on summer break, and what a break it was!  But with the advent of fall, watch this space for new puzzles and solutions.

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

This Week’s Fragment?

I caught a little grief for inflicting Lisp on readers last week.  So I took that (along with sunny evenings, good river water levels, race targets, and a poolside reading list) as a sign to give the Friday Fragment a summer break.  I have some ideas for new types of challenges when we pick it up again, so look for its return in the fall.  Until then, enjoy the summer!

Last Week’s Fragment – Solution

Last week’s fragment was a challenge to think inductively and recursively:

Code a factorial function (s-expression) in Lisp or Scheme.  For example, (factorial 3) should evaluate to 6.  Include unit test scaffolding code.

As mentioned above, the response to coding in Lisp/Scheme wasn’t positive.  One comment I got was “I’d rather write Esperanto poetry”  (kids these days, can’t think outside the box).  So I was left to code this one on my own.  Here’s my implementation:

   (define factorial
         (lambda (n)
             (cond
                 ((< n 0) "n must be non-negative")
                 ((= n 0) 1)
                 (else (* n (factorial (- n 1)))))))

My test/scaffolding code is:

   ; Unit test case helper:
   (define test
     (lambda (x y)
       (cond
         ((equal? x y) "pass")
         (else (list "FAIL - expected: " y " but got: " x)))))

   "Factorial unit tests"
   (test (factorial -1) "n must be non-negative")
   (test (factorial 0) 1)
   (test (factorial 1) 1)
   (test (factorial 3) 6)
   (test (factorial 55) 12696403353658275925965100847566516959580321051449436762275840000000000000)

I used Dr. Scheme (PLT Scheme) for this, which (like most functional programming environments) is optimized for tail recursion.  So even large factorials run fast without error.  By comparison, recursive factorial functions in C and Java will (depending on argument size, stack size, and/or VM) either take forever or fail with a stack overflow.  One solution for these more traditional environments is to convert tail recursion to iteration and avoid the "stack attack" of recursive function calls.

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

This Week’s Fragment

With this week’s fragment, we’ll start a series of puzzles to code something in a specified language.  The code itself won’t be difficult, but it will highlight the unique benefits of a particular language (or, in some cases, recently-added features to a language).  It’s your chance to try out a new language or feature.

Will start by thinking inductively and recursively, and that’s where functional languages like Lisp/Scheme shine.  This is a “classic” exercise (meaning there are probably a million solutions posted on the web), but try it yourself before peeking.  The problem is simple:

Code a factorial function (s-expression) in Lisp or Scheme.  For example, (factorial 3) should evaluate to 6.  Include unit test scaffolding code.

For extra credit, code a recursive factorial function in a more mainstream language (like C or Java) and compare the performance/results to Lisp when taking the factorial of a very large number.  There are several free Lisp/Scheme implementations you can use; Dr. Scheme (PLT Scheme) is one good choice.

To “play along”, post the 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 fragment was sent in by Joel Odom:

Write C code or pseudo-code to swap the values of two integer (int) variables, a and b, without declaring or using any other variables. Do not use any syntactical language tricks that implicitly copy values out of a or b into other memory or registers.  You can use C operators, control flow, and similar statements.

I was left to solve this one on my own, and sent Joel two solutions.  For the first, I used the wonders of XOR.  Among other things, XOR’ing something with a value twice gets the original value back: a feature used for simple bitmap animation, masking, encryption, etc. – and it’s fast.  For the second, I called a function, using the stack to push/pop one of the values.  Joel approved the XOR approach, but said the function call was cheating since it allocated memory on the stack (good point).  Here’s the simple XOR solution; for the function call and scaffolding code, see comments to last week’s post.

a=a^b;
b=b^a;
a=a^b;

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

This Week’s Fragment

This week’s programming puzzle was sent in by Joel Odom:

Write C code or pseudo-code to swap the values of two integer (int) variables, a and b, without declaring or using any other variables. Do not use any syntactical language tricks that implicitly copy values out of a or b into other memory or registers.  You can use C operators, control flow, and similar statements.

If you want to “play along”, post the 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 the following programming-related cryptogram:

Baae jaanklb xpnrv xksr.  Ki gaq pwr sper xa cpkx, kx kv xa vrwhr gaq urxxrw, ple xa ftrpvr gaq.

Congratulations to Luke for solving this; the plaintext answer is:

Good cooking takes time.  If you are made to wait, it is to serve you better, and to please you.

This is a chapter intro quote in Fred Brooks’ classic The Mythical Man Month, taken from a French restaurant menu.  It reminds us that quality software also requires time and careful preparation.

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

This Week’s Fragment

This one’s for Luke, who enjoyed our last cryptogram.  Solve the following programming-related cipher:

Baae jaanklb xpnrv xksr.  Ki gaq pwr sper xa cpkx, kx kv xa vrwhr gaq urxxrw, ple xa ftrpvr gaq.

This uses simple substitution, so just plug at it with pencil and paper, building up the substitution table as you go.  For extra credit, tell us the source of this quote.  If you’re ambitious, try coding a cracker, or at least a cryptogram generator.

If you want to “play along”, post the 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 challenge was to write code to solve a recent Car Talk Puzzler; that is:

Write code to find two (two-digit) temperatures where the (rounded) Celsius and Fahrenheit readings have the same digits, only reversed.

The conversion to Fahrenheit is 1.8 (or 9/5) times Celsius plus 32.  If you round the result, you find that 16 Celsius is 61 Fahrenheit and 28 Celsius is 82 Fahrenheit: handy numbers to remember when you want a quick approximate conversion from the current temp.

I invited folks to code it in multiple languages to compare, and even try esoteric languages.  Joel coded it in Python and demonstrated the strength of its range function when used with iterators.  He also showed off reversing a string via a “slice with inverse stride”, which sounds like my golf technique.  Wayne’s Smalltalk example demonstrated how it can elegantly iterate over a range using blocks/closures, a technique and style so nice that Ruby ripped it off.  Spencer coded it in Shakespeare but, alas, had problems with the interpreter (it was not to be).  I tried LOLCODE , and likewise had interpreter problems, so I did a quick PHP implementation also.  Gee, I wonder why there aren’t any production-ready LOLCODE or Shakespeare compilers?

Thanks to all for posting; code fragments like these provide good opportunities to compare language features and learn new approaches.  For all these implementations, see the comments in last week’s post.

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

This Week’s Fragment

A recent Car Talk Puzzler challenged listeners to find two temperatures where the Celsius and Fahrenheit readings had the same two digits, but reversed.  For example, 28 Celsius is 82 Fahrenheit.  It’s an easy problem to solve by hand, but what fun is that?  This is one where writing a bit of code will yield an answer faster than working it out by hand.  Or, better still, offer a chance to try some new coding approaches.  So, our programming version of this puzzle is:

Write code to find two (two-digit) temperatures where the (rounded) Celsius and Fahrenheit readings have the same digits, only reversed.

Use any language you’d like; you may want to try it in multiple languages to compare.  You might even try an esoteric language like LOLCODE or Shakespeare.

If you want to “play along”, post the solution as a comment or send it via email.   To avoid “spoilers”, simply don’t expand comments for this post.  That is, unless you want to see what languages others used to deliberately try something different.  Language wars can be such good sport.

Last Week’s Fragment – Solution

Last week’s fragment was one of those puzzles sometimes given as interview questions for programming and engineering jobs:

You have eight balls; seven weigh the same, but one is lighter than the others.  Using a balance, how can you find the “oddball” in only two weighings?

Congratulations to Wayne who solved it swimmingly, and described the solution nicely:

Weigh three balls against another three balls. If they weigh the same, you simply weigh the other two to find the lighter one. If one set of three balls was lighter than the other though, weigh two of the balls in the lighter set of three against each other. If one is lighter, that’s it, else it’s the third one you didn’t weigh the second time.

I guess that means you’re hired!

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

This Week’s Fragment

This week’s fragment follows the same line as last week; that is, it’s a simple puzzle sometimes given as an interview question for programming and engineering jobs.  I once worked at a company that used this one.  Such puzzles are usually very poor predictors of job performance, but they’re interesting nonetheless.  So here goes…

You have eight balls; seven weigh the same, but one is lighter than the others.  Using a balance, how can you find the “oddball” in only two weighings?

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

Last Week’s Fragment – Solution

Last week’s fragment was borrowed from a recent Car Talk episode.  A listener there wrote how he didn’t get a programming job partly because he failed to solve the following interview puzzle within the allotted five minutes:

You have a four ounce glass, a nine ounce glass and an unlimited supply of water, which can be poured and dumped as much as needed.  Can you measure exactly six ounces of water in as few steps as possible?

Kudos to both Spencer and Luke for solving this one quickly (within the five minutes) by just talking through it.  It can be done in eight steps, and the key is recognizing that the six ounces clearly must end up in the nine-ounce glass.  So you have to work toward pouring exactly three ounces out of that glass.  Get one ounce in the four-ounce glass and you have your three-ounce destination.  Here are the steps.

1. Fill the nine-ounce glass.
2. Fill the four-ounce glass from the nine-ounce glass.  That leaves five ounces in the niner.
3. Dump the four-ounce glass.
4. Fill the four-ounce glass again from the nine-ounce glass.  That leaves one ounce in the nine-ounce glass.
5. Again dump the four-ounce glass.
6. Pour that one ounce from the nine-ounce glass into the four-ounce glass.
7. Fill the nine-ounce glass again.
8. Fill the four-ounce glass from the nine-ounce glass.   You will have poured off three ounces leaving six ounces.  Voila!

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

This Week’s Fragment

“I knew I couldn’t trust that guy!”, exclaimed Joe the Plumber, having just returned from selling left-handed monkey wrenches at the pipe fitters’ convention.  “I sold a wrench to this guy, Pierre Lefebvre, who didn’t have enough cash, nor have his checkbook or credit card with him.  So I had him write his account information for both on a sheet of paper and give it to me.  The checking account information is bad (my bank says that the routing number, 374088048, is invalid), and the paper is torn such that I don’t have the last digit of the credit card number, just 4754 2700 7476 257.”

Inspector Lestrade took one look at the paper and responded, “I can tell you the correct checking number or credit card number, or both.  Which would you like?”

How did Lestrade do it?  Can you determine the correct numbers?

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.  For an extra challenge, try writing code to correct the numbers or at least prove that the numbers you chose were valid.  Maybe one day a plumber will thank you.

Last Week’s Fragment – Solution

Last week’s puzzle was “borrowed” from a recent Car Talk puzzler; here’s the gist:

You have 13 bottles of wine, and have been tipped off that one of them is tainted with a deadly poison: so deadly that one drop can kill a person or large animal within 24 hours.  With the help of four lab rats, how can you determine which one contains the fatal potion within one day?

The solution requires giving some rats wine from multiple bottles, and since the poison is so deadly, a little dab’ll do ya’ (or do in a rat).  Joel proposed a “divide and conquer” or “binary search” approach, which is nice and elegant and does the job (it’s also the solution I first thought of when I heard this on Car Talk).  But there’s only time for one round of testing, so you’ll have to throw all four rats at the problem at once.

Thinking in binary is the right approach.  Number the bottles 1-13 and represent each number in binary: 0001 through 1101.  Assign each of the four rats to one of the binary “positions”; let’s call them “A” in the one’s position, “B” in the two’s position, “C” in the four’s position, and “D” in the eight’s position.  And dole out the wine based on the binary representation of each bottle number.  For example, bottle number 1 goes to rat A, bottle 2 to rat B, bottle 3 (binary 0011) to rats A and B, and so on up to bottle 13 (binary 1101) given to rats A, C, and D.  The rats that kill over will identify the bottle number.

Wayne posted this solution and should probably get a bottle of poisoned Quivira wine as a prize.  Both Wayne and Joel noted that we could take on up to 16 bottles of wine with this solution, but I went with Car Talk’s lucky thirteen to keep it interesting.

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

This Week’s Fragment

I “borrowed” this week’s fragment from a recent Car Talk puzzler.  I prefer original ones, but since this one follows last week’s well, I thought I’d re-use it.

You have 13 bottles of wine, and have been tipped off that one of them is tainted with a deadly poison: so deadly that one drop can kill a person or large animal within 24 hours.  With the help of four lab rats, how can you determine which one contains the fatal potion within one day?

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

“If God had intended man to have computers, he would have given him 16 fingers.”
Anonymous

Last week’s puzzle reminds us that there are three kinds of people in the world: those who understand binary, and those who don’t.  Your job was to write code to dictate which pile each of 52 playing cards should land in when sorting in multiple passes with only four piles.  It was a spin on an old fine sort with base conversion and compression algorithm used for sorting checks and other things.

I received some excellent responses from base conversion pros like Joe Richardson and Stephen Ake.  I’ll publish Stephen’s code, since I like his better than mine:

pileNumber := ((card / (pileCount raisedTo: (eaPass – 1))) ceiling) \\ pileCount.
(pileNumber = 0) ifTrue: [pileNumber := pileCount].

If you’re in that second (third?) group who doesn’t keep their checkbooks in hex and is happy with the 10 fingers God gave us, think of it the following way…

If I let you use 13 piles on the first pass, then you could easily do it in two passes.  In the first pass, sort by rank (13 piles), and then stack those up and sort by suit (4 piles). You could treat the suit and rank of each card as a two-digit number, with the rank as the low-order “digit” and the suit as the high-order “digit.”

But Johnny didn’t have room on his Toy Story 2 lunchbox for 13 piles on the second pass, only 4.  So he had to convert the suit and rank of each card to a base 4 number.  That’s the base conversion part, which is important when the number of available piles (or pockets on a sorter) doesn’t match the original base of the number.  That’s because you want to make the best use of all piles/pockets on all passes.

When sorting by things like account numbers on checks, there can also be gaps in the numbers, which wastes pockets and passes.  To avoid this problem, you assign “aliases” to each number.  For example, if the first two account numbers are 13500001 and 13511115, renumber the first account as “1”, and the second as “2”, and sort on the aliases.  That’s the compression part.

This is easier for ten-fingered humans to follow if we use 10 piles to sort cards with the numbers 000 through 999.  The pile number for the first pass would be the digit in the ones position, then the tens position, and then the hundredths position.  That’s the 10^1, then 10^2, then 10^3 position, or the pocket count raised to the pass number.  In code, a modulus (remainder) division “strips off” this digit for use.

Kudos to Joe and Stephen for also noticing that it can be done in only three passes, not four.  That’s because 52 base 4 is a three-digit number.  I wasn’t trying to be tricky; I just forgot to edit after deciding to give Johnny 4 piles instead of 3.  And kudos to Stephen for solving it in Smalltalk (plugging into the scaffolding code I provided), since Smalltalk throws some extra twists: 1-based (not 0-based) arrays to adjust for, and a less-common exponentiation operator (raisedTo:, not ^).  You can find Stephen’s post in last week’s comments; Joe sent me a funny response via email back on March 22; here’s an excerpt:

Little Johnny is always one step ahead. He can sort the deck of cards using only 3 passes. Since Johnny is a smart kid, he assigns the numbers 1 through 13 to the cards of the first suit, 14-26 to the second suit, 27-39 the third, and 40-52 to the cards for the fourth suit. He does this in his head with no need of a sort pass. He then converts this decimal number to base 4 (since 4 piles are used). Knowing that 52 base 10 = 310 base 4, a three digit number, Johnny knows that it will take at most 3 passes to sort the cards. He might get lucky and sort the cards in only one or two passes. The first sort  pass uses the right most digit of this assigned base 4 number. The second pass uses the middle digit  and the third pass uses the left most digit.

Little Johnny has time left over to once again ask “Are we there yet?”

Finally, I neglected to mention that Luke (my middle son) solved last week’s cryptogram.  I often have to decode his (teen-speak) sentences, too.

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

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 don’t bother writing or downloading a program to crack it, just sit down with a pencil and paper and plug at it, building up the substitution table as you go.

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 – Solutions

Last week’s puzzle was this:

Write code to create a string of “fill data” of a given length, containing the digits 1-9, then 0, repeating.  For example, if given a length of 25, return “1234567890123456789012345″. For a length of 1, return “1″; for a length less than 1, return an empty string.

My son did it in Python, and a co-worker pointed me to a simple way he uses atAllPut: for fill data.  Here are some solutions, in three languages I often use:

In Smalltalk:

(1 to: length) inject: ” into: [ :str :ea | str, (ea \\ 10) printString ]

If a few extra temporary objects are a concern, do this:

ws := String new writeStream.
1 to: length do: [ :ea | ws print: (ea \\ 10) ].
ws contents

Here it is in Ruby:

(1..length).to_a.inject(”)  { | str, ea | str << (ea % 10).to_s() }

Although perhaps there’s a clever way to use join.

And, finally, in Java:

String s=””;
for (int i=1; i<=length; i++)
s += i % 10;

Easy enough, huh?  All it takes is a fragment.

I’ve always been a sucker for a good (yet simple) puzzle: crosswords, Sodoku, the Car Talk Puzzler, PC-lint’s Bug of the Month, you name it.  And the same goes for programming and logic puzzles.  I’m not talking about k-coloring, circuit satisfiability, or RSA factoring: I mean simple problems with simple solutions.  In fact, the simpler the solution, the better.  After all, I’m a sucker for elegance, too.

And elegance is sorely needed.  I’ve stumbled across more than my share of clumsy, confusing code: functions and methods that go on for dozens of lines that were easily rewritten to just a few straightforward statements.  You’d think the programmer was paid by the line of code.  So to do my small part to remedy that, I’ve often given quick assignments to my eldest son and other suitable victims.  Nothing fancy, just simple problems that can be summed up in a couple of sentences and that exercise standard techniques: loops, arrays, iterators, collections, streams, strings, recursion, induction, closures, etc.  I did that just recently, and that gave me the idea to try it here.  If for no other purpose than to provide fodder for other beginning programmers.

So, I’m introducing my Friday Fragment: a weekly programming, logic, or related problem.  The problem won’t be hard; rather, it’ll usually be something quite common, and often a chance to try a “kernel” of a problem in multiple languages or with multiple techniques.  And it’ll truly be a fragment: the problem and solution will be at most just a few sentences (or lines of code).  Each weekly post will include solution(s) for the previous week’s fragment and a new problem.  This’ll go on until I find out that it’s harder than it seems.

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 the post. For programming problems, pick the language of your choice.  That could add interest, since language wars can be great sport.

This Week’s Fragment

Write code to create a string of “fill data” of a given length, containing the digits 1-9, then 0, repeating.  For example, if given a length of 25, return “1234567890123456789012345”. For a length of 1, return “1”; for a length less than 1, return an empty string.

The idea for this came from some recent code I wrote, as part of a “test mode” to generate dummy data, up to a maximum field length.  This was so that XML output files could be fully validated against a rich schema (XSD), even if many of the source data fields were missing.  I used all digits for numeric fields, and the modulus positions were helpful for demonstrating field lengths.

“See” you in a week, when we’ll frag this one and add another.