Beefy Boxes and Bandwidth Generously Provided by pair Networks
Syntactic Confectionery Delight
 
PerlMonks  

RE: Cryptogram Generator

by btrott (Parson)
on Feb 07, 2000 at 23:30 UTC ( #3006=note: print w/ replies, xml ) Need Help??


in reply to Cryptogram Generator

A couple of comments:

1) the open || die statement should actually be

open IN, $infile or die "Can't open input file: $!";
For reasons of precedence.

2) Here are some faster algorithms. One way is to use a hash to record which characters you've already placed into your substitution string. Here's the main loop:

my %set; my $substit = ""; for (1..26) { my $randchar; do { $randchar = chr((int rand 26) + 65) } while $set{$randchar}++; $substit .= $randchar; }
This way you don't have to do a search through the string each time.

And here's an even better way of doing it: build a random permutation of the alphabet string. To do this, we'll actually need an array:

my @alpha = split //, "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
Now we set another array equal to this one, then call the random shuffle algorithm on it:
my @crypt = @alpha; fisher_yates_shuffle(\@crypt);
which shuffles the array in place. Now all you need to do is get back the substitution string:
my $substit = join '', @crypt;
Here's the definition of the fisher_yates_shuffle sub:
sub fisher_yates_shuffle { my $array = shift; for (my $i = @$array; --$i; ) { my $j = int rand ($i+1); next if $i == $j; @$array[$i, $j] = @$array[$j, $i]; } return join '', @$array; }
(Taken directly from perlfaq4.)

I did some benchmarking on these, and here's what I got:

Benchmark: timing 5000 iterations of orig, f_yates, hash... orig: 33 secs (23.60 usr 0.00 sys = 23.60 cpu) f_yates: 5 secs ( 2.88 usr 0.00 sys = 2.88 cpu) hash: 13 secs ( 5.68 usr 0.00 sys = 5.68 cpu)
where "orig" is the one you posted, "f_yates" is the one using fisher_yates_shuffle, and "hash" is the one using a hash to record seen characters.

If I've messed anything up, let me know.


Comment on RE: Cryptogram Generator
Select or Download Code
Replies are listed 'Best First'.
RE: RE: Cryptogram Generator
by Elihu (Novice) on Feb 08, 2000 at 07:39 UTC
    Wow. Thanks for the new ideas. I've been playing with the different algorithms a bit. I've seen somewhere how you do benchmarking, I'll try my own just to see for myself how it's done and if I get comparable numbers.

    I was pretty sure there was a better way to do that. :)

      I've been working on a cryptogram solver and discovered this post and found the code useful - I snagged the code for the fisher_yates_shuffle to grab one of my solved cryptograms to recreate one to work on solving and I found that in some instances one or two of the letters in $substit remained the same as it was originally. The line that checks for $i == $j does a next BUT $i keeps on counting down and effectively leaves the unchanged letter alone. I fixed it by incrementing $i before doing the next.

      I realize in some cases the shuffle results are okay if this happens, but in a cryptogram, it won't fly... ;-) Just thought I'd throw this info back out there just in case you or anyone else may have a need for the fix.

      Here's the modified sub:

      ## Taken from perlfaq4 (thanks btrott) sub fisher_yates_shuffle { my $array = shift; for (my $i = @$array; --$i; ) { my $j = int rand ($i+1); # next if $i == $j; # original if ($i == $j) { # this means the letter will be the same as it wa +s before $i++; # put $i back where it was and get another one next; } @$array[$i, $j] = @$array[$j, $i]; } return join '', @$array; }

      thanks for the original post! I'm learning a little here and there about using perl to solve cryptos... it's gonna take a while, but it's fun!!!

      Life is short, but it's wide -- Chuck Pyle

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://3006]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others about the Monastery: (7)
As of 2015-07-29 06:05 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    The top three priorities of my open tasks are (in descending order of likelihood to be worked on) ...









    Results (260 votes), past polls