Beefy Boxes and Bandwidth Generously Provided by pair Networks
more useful options
 
PerlMonks  

(Golf) Untwist

by ebbeatty (Acolyte)
on Aug 16, 2001 at 00:57 UTC ( [id://105186]=perlmeditation: print w/replies, xml ) Need Help??

This was one of those fun programming contest problems, thought it might be a good one for golf...

Do the Untwist

Cryptography deals with methods of secret communication that transform a message (the plaintext) into a disguised form (the ciphertext) so that no one seeing the ciphertext will be able to figure out the plaintext except the intended recipient. Transforming the plaintext to the ciphertext is encryption; transforming the ciphertext to the plaintext is decryption. Twisting is a simple encryption method that requires that the sender and recipient both agree on a secret key k, which is a positive integer.

The twisting method uses four arrays: plaintext and ciphertext are arrays of characters, and plaincode and ciphercode are arrays of integers. All arrays are of length n, where n is the length of the message to be encrypted. Arrays are origin zero, so the elements are numbered from 0 to n - 1. For this problem all messages will contain only lowercase letters, the period, and the underscore (representing a space).

The message to be encrypted is stored in plaintext. Given a key k, the encryption method works as follows. First convert the letters in plaintext to integer codes in plaincode according to the following rule: '_' = 0, 'a' = 1, 'b' = 2, ..., 'z' = 26, and '.' = 27. Next, convert each code in plaincode to an encrypted code in ciphercode according to the following formula: for all i from 0 to n - 1,

ciphercode[i] = (plaincode[ki mod n] - i) mod 28. (Here x mod y is the positive remainder when x is divided by y. For example, 3 mod 7 = 3, 22 mod 8 = 6, and -1 mod 28 = 27. You can use the C '%' operator or Pascal 'mod' operator to compute this as long as you add y if the result is negative.) Finally, convert the codes in ciphercode back to letters in ciphertext according to the rule listed above. The final twisted message is in ciphertext. Twisting the message cat using the key 5 yields the following:

      Array   0   1   2 
  plaintext  'c' 'a' 't' 
  plaincode   3   1   20 
 ciphercode   3   19  27 
 ciphertext  'c' 's' '.' 

Your task is to write a program that can untwist messages, i.e., convert the ciphertext back to the original plaintext given the key k. For example, given the key 5 and ciphertext 'cs.', your program must output the plaintext 'cat'.

The input file contains one or more test cases, followed by a line containing only the number 0 that signals the end of the file. Each test case is on a line by itself and consists of the key k, a space, and then a twisted message containing at least one and at most 70 characters. The key k will be a positive integer not greater than 300. For each test case, output the untwisted message on a line by itself.

Note: you can assume that untwisting a message always yields a unique result. (For those of you with some knowledge of basic number theory or abstract algebra, this will be the case provided that the greatest common divisor of the key k and length n is 1, which it will be for all test cases.)

Example input:
5 cs.
101 thqqxw.lui.qswer
3 b_ylxmhzjsys.virpbkr
0

Example output: 

cat
this_is_a_secret
beware._dogs_barking

Here is an example of how I'm testing it...
#!/usr/bin/perl -w use strict; my $line; for(chomp($line = <DATA>); $line =~ /(\d+)\s+([_a-z.]+)/; chomp($line += <DATA>)) { my $plaintext = decipher($1, $2); print "$plaintext\n"; } sub decipher { # place code here } __DATA__ 5 cs. 101 thqqxw.lui.qswer 3 b_ylxmhzjsys.virpbkr 0

Replies are listed 'Best First'.
Re: (Golf) Untwist
by dragonchild (Archbishop) on Aug 16, 2001 at 02:14 UTC
    I'll take a stab. It comes in at 147 characters. It doesn't use strict, but does execute multiple times.
    sub decipher { @n=split//,'_abcdefghijklmnopqrstuvwxyz.';$l{$n[$_]}=$_ for 0..$#n;@c= +map{$l{$_}}split//,pop;$p[$_[0]*$_%@c]=$n[($c[$_]+$_)%@n]for 0..$#c;j +oin'',@p }

    I was trying to find a way to not do the whole listing out of the 28 characters, but couldn't figure a way to get a-z into there. That could cut up to 23 characters, bringing me to 124.

    Update: I've figured out a way to improve that string assignment. I feel stupid, but it's better now, down to 120. (Thanks, boo_radley!)

    @n=(_,a..z,'.');map{$l{$n[$_]}=$_}0..27;@c=map{$l{$_}}split//,pop;$p[$ +_[0]*$_%@c]=$n[($c[$_]+$_)%@n]for 0..$#c;join'',@p

    ------
    /me wants to be the brightest bulb in the chandelier!

    Vote paco for President!

      *ahem*

      @n=('_','a'..'z','.');

      you could also trim one off by changing $#n to 27

      Other than that your code is indeciperable to me
      ;-)

      update :
      also consider what happens when you shuffle the ciphertexts to

      3 b_ylxmhzjsys.virpbkr 5 cs. 101 thqqxw.lui.qswer

      You get

      beware._dogs_barking catare._dogs_barking this_is_a_secretking
      !!

Re: (Golf) Untwist
by abstracts (Hermit) on Aug 16, 2001 at 05:11 UTC
    Update: 108 passing strict and warnings :-)
    use strict; while(<DATA>){ chomp; /(\d+)\s+([_a-z.]+)/ or last; my $plaintext = decipher($1, $2); print "$plaintext\n"; } sub decipher { $,=0;($;,$_)=@_;@;{@;{0..27}=('_','a'..'z','.')}=0..27;$;[$;*$,++%@_]= +$;{($;{$_}+$,)%28}for@_=/./g;join'',@; } __DATA__ 5 cs. 101 thqqxw.lui.qswer 3 b_ylxmhzjsys.virpbkr 0

    Here is my initial trial at 126 chars. It passes strict and warnings.

    sub decipher { my($k,@r,%b,@s)=@_;@s=pop=~/./g;@b{@b{0..27}=('_','a'..'z','.')}=0..27 +;$r[$k*$_%@s]=$b{($b{$s[$_]}+$_)%28}for 0..$#s;join'',@r }
    Aziz,,,
      Taking ideas from both my previous post and abstracts post ... we can get down to 105 quite nicely.
      @b{@b{0..27}=(_,a..z,'.')}=0..27;@s=pop=~/./g;$p[$_[0]*$_%+@s]=$b{($b{ +$s[$_]}+$_)%28}for 0..$#s;join'',@p
      I especially like the way he does the split I was doing. The comparison is quite stunning.
      @e=split//,pop; @e=pop=~/./g;
      It's only two characters, but it takes advantage of a feature I didn't know about.

      The double hash-slice assignment is also quite neat. It saves more characters over what I was doing, but it's not as stunning, in my eyes. *shrugs*

      ++abstracts!!

      Update: Ok, abstracts! *laughs* Let's get below 100. (I'm still trying to figure out why you want to be strict- and warnings-compliant in a golf. To me, it's enough that it runs more than once, if that's what the golf calls for.)

      @;{@;{0..27}=(_,a..z,'.')}=0..27;$,=0;$;[$_[0]*$,++%@s]=$;{($;{$_}+$,) +%28}for@s=pop=~/./g;join'',@;
      99 characters! :)

      I'd like to congratulate abstracts on finding some very neat golfing techniques. :)

      ------
      /me wants to be the brightest bulb in the chandelier!

      Vote paco for President!

        Hello

        When I saw the test script, I thought it was part of this golf to pass strict and warnings. Maybe my bad.

        Aziz,,,

(dkubb) Re: (2) (Golf) Untwist
by dkubb (Deacon) on Aug 16, 2001 at 11:50 UTC

    Using ideas previously mentioned, and throwing in a few of my own, this can be brought down to 98 characters:

    sub decipher { @l=(_,a..z,'.');@n{@l}=0..27;@c=@n{split//,pop};$"=my$i;$p[$_[0]*$i++% +@c]=$l[($_+$i)%28]for@c;"@p" }
      Using ideas from my and abstracts mini-thread, we get to 90.
      @n{@l=(_,a..z,'.')}=0..27;$"=my$i;$p[$_[0]*$i++%@c]=$l[($_+$i)%28]for@ +c=@n{pop=~/./g};"@p"

      ------
      /me wants to be the brightest bulb in the chandelier!

      Vote paco for President!

        ++dragonchild. Job well done. I'll see if I can take another stab at this one later :-)

        Aziz,,,

      you're now at 93
      @n{@l=(_,a..z,'.')}=0..27;@c=@n{pop=~/./g};$"=my$i;$p[$_[0]*$i++%@c]=$ +l[($_+$i)%28]for@c;"@p"
         larryk                                          
      perl -le "s,,reverse killer,e,y,rifle,lycra,,print"

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: perlmeditation [id://105186]
Approved by root
help
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others surveying the Monastery: (4)
As of 2024-03-29 11:24 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found