Ruby Hangman for the April meeting

16 views
Skip to first unread message

Markus

unread,
Apr 1, 2010, 11:33:04 AM4/1/10
to pdx...@googlegroups.com
Fa la la la la, it's the most...wonderful time...of the year.

No, I'm not talking about Christmas time, which is months past, but
Springtime, when Portlandians emerge from their warrens and scurry about
to see if their favorite food carts survived the long cold winter, and
even workaholics stand some chance of getting home (or at least dinner)
while it's still light out.

Time, in short, for my second favorite holiday: April Fools Day!

In honour of this event I've decided to do something special for the
ruby hangman, something that (to my knowledge at least) has never been
done in public before.

One of the wonderful things about ruby is the many different types of
methods you can write. You can write methods that act like pure
functions, or procedure, or even (with yield/block parameters) like
control structures. You can write 'em eager, you can write 'em lazy,
you can write em' anywhere in between. Fluent, state-stepping, DSL'd,
or LSD'd, however you want, the choice is yours. You can even write
methods that are sheer poetry to read--limericks and haiku come to mind,
and iambic pentameter sounds doable though I've never tried it.

To celebrate this diversity, I'd like to highlight a special class of
methods, the sudoku methods, which have the following properties:

* They are exactly 81 characters long, counting the \n line break
as a single character;
* They are composed of nine repetitions of nine characters;
* If written on a 9x9 grid, as sudoku puzzles normally are, they
conform to the rules of that puzzle type (each character occurs
once in each row, column, and tick-tack-toe aligned 3x3 block)

Now, while these functions are interesting, I've found one I especially
like that I'd like to share with you; it has the added property that,
when executed, it returns a message (a String) encrypted with a one-time
pad, a special message from me to you. And as if that isn't enough, the
same string can be interpreted as a lossy form of the same message under
a simple substitution cypher--so that the same encrypted message can
effectively be decrypted by two entirely different algorithms!

Now by this point, many of you are probably nodding to yourself, and
saying "Ah yes, this is his April Fools prank on us. Very droll." But
those of you who are saying that (or anything similar) would be wrong:
this is not my April Fools prank, it is merely the setup.

The prank comes in when you try to solve it, for there are at least four
different ways to go about it. You could, for example, solve it like a
normal sudoku using normal sudoku techniques. Or you might be able to
guess the message and work backwards to the encrypted form and, from
there, attack the sudoku. But of all the potential ways of solving
this, one is far superior in that, by cleverly applying a technique from
classical logic, it should be possible to solve it in just a few minutes
without a computer or even scratch paper. Once you think of this
method, it's blindingly obvious.

That's the prank.

-- Markus

P.S. Oh yeah, the code. With the usual wonderbar underbars, of course:


class A

# Because people razz me about always using method_missing in
# these I've decided to start including it even if it isn't needed

def method_missing(*x)
x.join(',')
end

# We give the sudoku function in the standard form (standard for
# sudoku functions, that is): a 9x9 grid with spacing to break it
# into a 3x3 grid of 3x3 grids of character representations (most
# characters just represent themselves but special characters are
# represented by digraphs like \n, \t, \", etc.).

sudoku = %w{
__ __ __ __ __ __ __ __ __
n \s \n __ __ __ __ + e
__ __ __ e d \n __ f \s

\" __ __ n \n __ __ e __
__ n __ __ __ __ \s __ __
__ __ __ __ \" f __ __ n

e d __ __ n __ __ __ '
__ __ __ d __ __ \" __ __
+ __ \" __ __ __ __ n __
}

# To add the sudoku function as an instance method of this
# class, we need to go through several steps: sudoku is an
# array of 81 strings (produced by the %w{...}) with each
# string representing a character. We need to convert the
# representation into the character represented; given one of
# these strings, ch, %Q{"#{ch}"} produces a string with the
# representation enclosed in double quotes; so 'x' would be
# turned into '"x"' and '\t' would be turned into '"\t"', etc.
# Note that this is the inspect of the character we're looking
# for. If we eval it, we get the character, and if we collect
# all of them and join the resulting characters we get the 81
# character string we are after. evaling that defines the
# function for us, like so:

eval(sudoku.collect { |ch| eval(%Q{"#{ch}"}) }.join)

# These gyrations won't be needed in 1.9.3 if my proposal to add
# "sudoku_def" as a built-in is accepted.
end

# Now we create one of these objects

a = A.new

# We call the sudoku method on it to get the cyphertext
# (it turns out we also pass the object in as a parameter,
# but that fact won't help you). Note that the name of
# the method has been redacted and possibly padded
# with one or more spaces.

cyphertext = a____(a)

# To decrypt it with our one-time pad we need a long string of pseduo
# random bits that the other guys won't know, and we peel them off as
# needed (byte at a time) to xor and add with bytes from the cyphertext
# to produce the message.

pad =
0x86d2f5aa407f1e23840926f0168e6a84e472266c6791ae6064800040b057a52cc9f

cleartext = ''
cyphertext.each_byte { |b|
pad,x = pad.divmod(256)
pad,y = pad.divmod(256)
cleartext << (((b^y)+x) & 0xff).chr
}
puts cleartext


# For the (lossy, but readable) simple substitution cypher we just
# use tr with a resticted set of characters and a scrambled version
# of the same.

cypher = "\a\b\t\n\v\f\r\e !\"\#$%&'()*
+,./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\
\]^_`abcdefghijklmnopqrstuvwxyz{|}~"
clear = "H;Vs5_^4FUl:mT<Z%+qoP8x2h|0M@()KO3B'/>\fCWd}1vE[]\r7!\t*L\\
\"\eDf~,\a=Yb?n{\nuz.`wRpirJGIk\bcQAS$e &X\v6#9Njagyt"

puts cyphertext.tr(cypher,clear)

# And that's all there is to it...have fun!


Sam Livingston-Gray

unread,
Apr 1, 2010, 1:38:18 PM4/1/10
to pdx...@googlegroups.com
You crazy, crazy bastard. What did PDX.rb ever do without you? (=

--
(Sent from a mobile device with a tiny onscreen keyboard. As such, my
email may be more terse than you've come to expect from me.)

> --
> You received this message because you are subscribed to the Google
> Groups "pdxruby" group.
> To post to this group, send email to pdx...@googlegroups.com.
> To unsubscribe from this group, send email to pdxruby+u...@googlegroups.com
> .
> For more options, visit this group at http://groups.google.com/group/pdxruby?hl=en
> .
>

Igal Koshevoy

unread,
Apr 1, 2010, 1:43:41 PM4/1/10
to pdx...@googlegroups.com
On 04/01/2010 10:38 AM, Sam Livingston-Gray wrote:
> Q: You crazy, crazy bastard. What did PDX.rb ever do without you? (=
A: We had less fun. :)

-igal

Reply all
Reply to author
Forward
0 new messages