Beefy Boxes and Bandwidth Generously Provided by pair Networks
laziness, impatience, and hubris
 
PerlMonks  

Re^4: secret code generator

by tilly (Archbishop)
on Dec 21, 2006 at 03:58 UTC ( #591039=note: print w/ replies, xml ) Need Help??


in reply to Re^3: secret code generator
in thread secret code generator

Are you finished the self-congratulation?

The fact is that if I did not know what your index-based code was supposed to be doing, I would have had a dickens of a time figuring out what that code does. Perhaps in your coding style names like $di and @is make sense to you, but they are meaningless to me. And presumably would be meaningless to any other maintainance programmer.

Now about my first attempt. How it works doesn't matter. That it does, does. The key piece is

my $x = 0; while (++$x) { nested_for( sub {print join "", @_, "\n";} , map \@chars, 1..$x ); }
which means for every length of string, print all combinations. How does that work? Well it depends on nested_for, which should be pushed somewhere else and documented. In fact it is useful enough that I'd want to see something like that on CPAN. Lo and behold, it has been put on CPAN! See Algorithm::Loops' NestedLoops function. (Thanks, tye.) I avoided using the module largely because I wanted to give the complete solution rather than hiding any bits.

Why did I pick that solution? Well I knew I had the code for that lying around, easy to pick up, so it was very fast to code. And secondly the Python programmer was obviously trying to snow the (admittedly novice) Perl programmer with techniques the Perl guy didn't know, so I was coming back with techniques the Python guy probably wouldn't know. In other words I was being cute. And was definitely not trying to be maintainable. (Though once the complicated bit is pushed to a CPAN module, it actually is maintainable as well.)

Now the solution that you're deriding did have a bug. I just fixed that. Guess I should have tested it first, but I was just trying to use even fewer features than you did. (And the reason why I did that is that you were criticizing me for using so many features.) As for how it works, it is the mirror image of yours, but rather than keep an array and then move an index, I'm just keeping a partial array of what is left to go through. It is slower because I'm constantly creating and destroying arrays of scalars while you aren't.

About performance, that was obviously not a goal of mine. But even so, if every microsecond it takes to generate each answer adds 177 years on the overall task, then neither of our solutions are going to get through all of the 8 character passwords any time soon.


Comment on Re^4: secret code generator
Download Code
Re^5: secret code generator
by BrowserUk (Pope) on Dec 21, 2006 at 04:32 UTC
    How does that work? Well it depends on nested_for, which should be pushed somewhere else and documented. In fact it is useful enough that I'd want to see something like that on CPAN. Lo and behold, it has been put on CPAN! See Algorithm::Loops' NestedLoops function.

    Oh no. That's utter *(*^%&. The relationship between the code you posted (attempt 1), and tye's NestedLoops() is as that between a Ferrari 599 and an Ox cart. tye's is highly tuned and blazingly fast. Yours--dog slow.

    I fully understand how NestedLoops() works, I just cannot wrap my brain around the interface.

    And the reason why I did that is that you were criticizing me for using so many features.

    Hmm. The funny bit is, I don't think I had even seen your code when I posted. Either way, my critisisms were aimed solely at the Python code.

    About performance, that was obviously not a goal of mine. But even so, if every microsecond it takes to generate each answer adds 177 years on the overall task, then neither of our solutions are going to get through all of the 8 character passwords any time soon.

    Maybe not with a 93 character set, but maybe for a 26 char set. Then each microsecond is only 58 hours. A long long time, but doable--if you don't waste time with overly complicated algorithms.


    Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
    Lingua non convalesco, consenesco et abolesco. -- Rule 1 has a caveat! -- Who broke the cabal?
    "Science is about questioning the status quo. Questioning authority".
    In the absence of evidence, opinion is indistinguishable from prejudice.
      I wasn't particularly impressed with the readability of any of the previously presented solutions, so I have added a few more solutions below (two of my own: #2 and #3, and one based on NestedLoops: #4). For readability, I like #4 (NestedLoops) best and #3 next best. #2 is an optimized version of #3 which is still much more readable IMO than the other solutions. I have tried to keep the solutions close in spirit to the original #1 (by Tilly). The technique of passing an accumulator is used by a lot of Lisp idioms.

      As far as benchmarking goes, #1 is faster than #3, but #2 is the fastest by a substantial margin. #4 (NestedLoops) is dead last. I have included the benchmarking code for you to try yourself.

      All the solutions except #1 (the original solution) work by permuting the rightmost "digit" fastest. #1 permutes the leftmost "digit" fastest. Inserting the two calls to reverse (which I have commented out below) slows it down a bit but not enough to affect it's ranking.

      #! /usr/bin/perl -w use strict; use Benchmark; use Algorithm::Loops qw(NestedLoops); use vars qw(@chars $loop_cnt $printit); $loop_cnt = 3; @chars = map chr, 0x21 .. 0x7e; # @chars = ("a" .. "c"); sub printit { print @_ if $printit; } #------------------------------------------------ sub doit4 { my $x = 1; while ($x <= $loop_cnt) { NestedLoops( [ map \@chars, 1 .. $x++ ], sub { printit join "", @_, "\n" } ); } } #------------------------------------------------ sub ret_iter3 { my $accum = shift; my $range = shift; if ($range) { ret_iter3( [@$accum, $_], @_ ) for @$range } else { printit join "", @$accum, "\n" } } sub nested_for3 { ret_iter3 [], @_; } sub doit3 { my $x = 1; while ($x <= $loop_cnt) { nested_for3 map \@chars, 1 .. $x++; } } #------------------------------------------------ sub ret_iter2 { my $accum = shift; my $range = shift; if (@_) { for (@$range) { push @$accum, $_; ret_iter2($accum, @_); pop @$accum; } } else { printit join "", @$accum, $_, "\n" for @$range; } } sub nested_for2 { ret_iter2 [], @_; } sub doit2 { my $x = 1; while ($x <= $loop_cnt) { nested_for2 map \@chars, 1 .. $x++; } } #------------------------------------------------ sub doit1 { my $x = 0; while (++$x <= $loop_cnt) { nested_for1( sub {printit join "", @_, "\n";} , map \@chars, 1..$x ); # nested_for1( # sub {printit join "", reverse(@_), "\n";} # , reverse(map \@chars, 1..$x) # ); } } sub nested_for1 { ret_iter(@_)->(); } sub ret_iter { my $fn = shift; my $range = shift; my $sub = sub {$fn->($_, @_) for @$range}; return @_ ? ret_iter($sub, @_) : $sub; } #------------------------------------------------ # $printit = 1; # doit1; # doit2; # doit3; # doit4; # exit; timethese (-10, { doit1 => 'doit1', doit2 => 'doit2', doit3 => 'doit3', doit4 => 'doit4', });

Log In?
Username:
Password:

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

How do I use this? | Other CB clients
Other Users?
Others cooling their heels in the Monastery: (10)
As of 2014-10-23 18:44 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    For retirement, I am banking on:










    Results (128 votes), past polls