Beefy Boxes and Bandwidth Generously Provided by pair Networks
Perl-Sensitive Sunglasses
 
PerlMonks  

Re: Algorithm inspiration required.

by kennethk (Abbot)
on Jun 18, 2018 at 21:40 UTC ( #1216898=note: print w/replies, xml ) Need Help??


in reply to Algorithm inspiration required.

So here's my thinking. What you are really trying to figure out is how long your sequence is; the concept of start is arbitrary. Therefore, what you should be doing is a rolling bitwise xor; whenever your checksum is zero, you have potentially passed through two cycles. I don't know what your alphabet looks like, but presumably you could do better than ASCII encoding to lower your collision rate.
#!/usr/bin/perl use strict; use warnings; use 5.10.0; my $seq = 'deabcdefabcdefgAbcdeabcdefabcdefgAbcdeabcdefabcdefgAbcdeabc +defabcdefgAbcdeabcdefabcdefgAbcdeabcdefabcdefg'; my %val = do{my $cnt = 0; map {$_ => ++$cnt} split //, 'Aabcdefg'}; my $xor = 0; my $loop = 0; for (split //, $seq) { $loop++; $xor ^= $val{$_}; say $loop if !$xor; }
outputs
9 36 45 72 81
Note that the only candidate that has both 2*x and 4*x in the list is the correct answer, 18. Setting the %val hash to one-hots instead of consecutive integers gets rid of the noise, but also chews up your bit vector pretty quickly for large alphabets.
my %val = do{my $cnt = 0; map {$_ => 2**(++$cnt)} split //, 'Aabcdefg' +};

#11929 First ask yourself `How would I do this without a computer?' Then have the computer do it the same way.

Log In?
Username:
Password:

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

How do I use this? | Other CB clients
Other Users?
Others browsing the Monastery: (5)
As of 2020-06-02 08:04 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?
    Do you really want to know if there is extraterrestrial life?



    Results (13 votes). Check out past polls.

    Notices?