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

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; }
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?

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

How do I use this? | Other CB clients
Other Users?
Others examining the Monastery: (4)
As of 2021-10-19 21:18 GMT
Find Nodes?
    Voting Booth?
    My first memorable Perl project was:

    Results (77 votes). Check out past polls.