Image

head

code

item

root

para

L<Examples| file:../examples/index.podlite>


L<Download |file:../download/index.podlite>


React

=begin React :component<HeaderCol> :id<menu> 
=para L<Documentation|/doc/introduction>
=para L<Modules| /mods>
=para L<Examples| file:../examples/index.podlite>
=para L<Download |file:../download/index.podlite>
=para L<About|file:../about/index.podlite>
=para 🔍 K<⌘K>/K<ctrl-K>
=end React


HEADER

FOOTER

README

Functions from I<Introduction to Algorithms, Third Edition>


The functions below have been translated from the I<psuedo code>
in the book into I<Raku>. To ease the translation, Raku classes were
created to mimic contructs in the pseudo code as much as
possible.


(Note the class has a short name for convenience: C<A1B>.)


The main feature of this class is that its first slot is at index 1 as
opposed to 0 in Raku arrays. Only necessary features of a normal array
have been added, so its feature list is not exhaustive. However, users
are encouraged to ask for additional features or submit a PR for such.


The class provides the following ways to instantiate an array:


=begin code
my $a = ArrayOneBased.new;
=end code


=begin code
my $a = ArrayOneBased.new: "abbxide x";
=end code


As an array filled with a number sequence M..N


=begin code
my $a = ArrayOneBased.new: 2, 6;
=end code


Specifying end only (beginning is 1 by default):


=begin code
my $a = ArrayOneBased.new: 5;
=end code


=begin code
my $a = ArrayOneBased.new: @list;
=end code


The following two functions are used to employ the I<Knuth-Morris-Pratt> (KMP) 
algorithms for pattern matching. See examples of their use in the test routines.


The functions will find all non-overlapping matches of a specified pattern in
an input text string. (It should be very useful in DNA analysis.) Following is
an example of a pattern and its matches. The results of a KMP pattern match
is a list of the "shifts" for each match. A shift is a number representing
the number of characters after the first character of the input string.
No shifts will be reported for a situation with no matches. Of course
an attempted match of an input string with a longer pattern will
result in no match.


A pattern: "AACT". A DNA string: "AAACTTTAACTAA" (13 characters).


=begin code
    AAACTTTAACTAA  # 13 characters in this string
     AACT  AACT    # two matches: the 1st at a shift of 1, the 2nd is at a shift of 7
=end code


Following is the pseudo code from Ref. 1:


=begin code
 1  n = T.length
 2  m = P.length
 3  pi = Compute-Prefix-Function(P)
 4  q = 0                                            // number of characters matched
 5  for i = 1 to n                                   // scan the text from left to right
 6      while q > 0 and P[q + 1] not equal T[i]
 7          q = pi[q]                                // next character does not match
 8      if P[q + 1] == T[i]
 9          q = q + 1                                // next character matches
10      if q == m                                    // is all of P matched?
11          print "Pattern occurs with shift" i - m
12          q = pi[q]                                // look for the next match
=end code


Line 12 is in error and should read: C<q = 0> (a bug report has been filed
with the publisher).


=begin code
KMP-Matcher(ArrayOneBased $T, ArrayOneBased $P --> List)
{...}
=end code


B<Compute-Prefix-Function> (Ref. 1, p. 1006)


=begin code
 1  m = P.length
 2  let pi[1..m] be a new array
 3  pi[1] = 0
 4  k = 0
 5  for q = 2 to m
 6      while k > 0 and P[k + 1] not equal P[q]
 7          k = pi[k]
 8      if P[k + 1] == P[q]
 9          k = k + 1
10      pi[q] = k
11  return pi
=end code


=begin code
Compute-Prefix-Function(ArrayOneBased $P --> ArrayOneBased)
{...}
=end code


FUNCTIONS

use v6;
unit class Algorithm::ZobristHashing:auth<zef:titsuki>:ver<0.0.5>;

has Hash $!table;
has $!rand-max;
has Str $!record-separator = '30'.chr;

submethod BUILD(:$!rand-max = 1e9) { }

multi method encode(Str:D $text) returns Int {
    return self.encode($text.split("",:skip-empty));
}

multi method encode(@array is copy) returns Int {
    @array = self!flatten(@array);
    if (@array.elems == 0) {
	return Int;
    }
    
    my Int @rand-array;
    for @array.kv -> $position, $element {
	my Str $key = $position ~ $!record-separator ~ $element;
	if (not $!table{$key}:exists) {
	    $!table{$key} = $!rand-max.rand.Int;
	}
	@rand-array.push($!table{$key});
    }
    return [+^] @rand-array;
}

method get(Int $position, Str $type) returns Int {
    my $key = $position ~ $!record-separator ~ $type;
    if ($!table{$key}:exists) {
	return $!table{$key};
    }
    return ($!table{$key} = $!rand-max.rand.Int);
}

method !flatten(@array)
{
    gather for @array -> $element
    {
	$element ~~ Array ?? take(self!flatten($element)) !! take $element
    }.flat
}



Algorithm::ZobristHashing - a hash function for board games


# the case input is Str
my $zobrist = Algorithm::ZobristHashing.new();
my $status = $zobrist.encode("Perl6 is fun");
my $code = $zobrist.get(0,"P"); # Int value which represents state h(0,"P")
my $code = $zobrist.get(5," "); # Int value which represents state h(5," ")


# the case input is Array
my $zobrist = Algorithm::ZobristHashing.new();
my $status = $zobrist.encode([["Perl6"],["is"],["fun"]]);
my $code = $zobrist.get(0,"Perl6"); # Int value which represents state h(0,"Perl6")


Algorithm::ZobristHashing is a hash function for board games such as chess, GO, GO-MOKU, tic-tac-toe, and so on. 


my $zobrist = Algorithm::ZobristHashing.new(%options);


Sets the upper bound number for generating random number. Default is 1e9.


my $status = $zobrist.encode("abc"); # h(0,"a") xor h(1,"b") xor h(2,"c")
my $status = $zobrist.encode([["a"],["b"],["c"]]); # h(0,"a") xor h(1,"b") xor h(2,"c")
my $status = $zobrist.encode([["ab"],["c"]]); # h(0,"ab") xor h(1,"c")


Returns the hash value which represents the status of the input sequence. If the input value is the nested array, it flattens this and handles as a 1-dimensional array. If the input value is empty, it returns the type object Int.


my $status = $zobrist.encode(["abc"]);
my $code = $zobrist.get(0,"abc"); # in this case $code == $status
my $new-code = $zobrist.get(0,"perl"); # assigns a new rand value, since h(0,"perl") is not yet encoded


Returns the Int value which represents the state(i.e position-type pair). If it intends to get the state not yet encoded, it assigns a new rand value to the state and returns this new value.


This library is free software; you can redistribute it and/or modify it under the Artistic License 2.0.


This algorithm is from Zobrist, Albert L. "A new hashing method with application for game playing." ICCA journal 13.2 (1970): 69-73.


ZobristHashing

The Raku Knowledge Base


=begin React :component<HeaderCol> :id<footer>  
=begin nested :!nested
=item1 B<Language>
    =item2 L<Get started|file:../getting-started/getting-started.podlite>
    =item2 L<Why Raku?|/doc/language/faq#Why-should-I-learn-Raku-What's-so-great-about-it>
    =item2 L<Try Raku|https://glot.io/new/raku>
    =item2 L<Raku cheat sheet|https://github.com/Raku/mu/blob/master/docs/Perl6/Cheatsheet/cheatsheet.txt>
    =item2 L<empty|#>
    =item2 L<empty|#>
    =item2 L<empty|#>
    =item2 L<Raku on Exercism|https://exercism.org/tracks/raku>
    =item2 L<Wikipedia|https://en.wikipedia.org/wiki/Raku_(programming_language)>
    =item2 L<empty|#>
    =item2 L<empty|#>
    =item2 L<empty|#>

=end nested
=begin nested :!nested

=item1 B<L<Documentation|/doc>>
    =item2 L<Getting started, Migration guides from other languages, & Tutorials | file:../doc/introduction.podlite>
    =item2 L<Language References|file:../doc/reference.podlite>
    =item2 L<Type Reference| file:../doc/types.podlite>
    =item2 L<Miscellaneous| file:../doc/miscellaneous.podlite>
    =item2 L<FAQs (Frequently Asked Questions)|/doc/language/faq>
    =item2 L<Community|/doc/language/community>
    =item2 L<The list of all documents|file:../doc/index.podlite>

=item1 B<Resources>
    =item2 L<The Raku Guide|https://raku.guide/>
    =item2 L<Books |https://perl6book.com/>
    =item2 L<Rosetta Code | https://www.raku.org/community/rosettacode>

=end nested
=begin nested :!nested

=item1 B<Resoures>
    =item2 L<Download | file:../download/index.podlite>
    =item2 L<empty|#>
    =item2 L<empty|#>
    =item2 L<empty|#>
    =item2 L<empty|#>
    =item2 L<empty|#>
    =item2 L<empty|#>
    =item2 L<empty|#>

=item1 B<Learning>
    =item2 L<The Raku Guide|https://raku.guide/>
    =item2 L<Wikibook |https://en.wikibooks.org/wiki/Raku_Programming>
    =item2 L<Books |https://perl6book.com/>
    =item2 L<Rosetta Code | https://www.raku.org/community/rosettacode>
    =item2 L<Learn Raku in Y minutes|https://learnxinyminutes.com/docs/raku/>
    =item2 L<Golfing |https://github.com/AlexDaniel/raku-golf-cheatsheet>
=end nested
=begin nested :!nested

=item1 B<Explore>
    =item2 L<Raku Blog Aggregator|https://planet.raku.org/>
    =item2 L<Rakudo Weekly|https://rakudoweekly.blog/>
    =item2 L<The Weekly Challenge |https://perlweeklychallenge.org/>
    =item2 L<Raku Advent Calendar|https://raku-advent.blog/>
    =item2 L<empty|#>
    =item2 L<empty|#>
    =item2 L<empty|#>
    =item2 L<empty|#>
    =item2 L<empty|#>

=end nested
=end React


=begin React :component<CookieConsent> :id<CookieConsent> :buttonCaption("Got it!")
=para
This website uses cookies for analytics.
=end React


README

NAME

SYNOPSIS

DESCRIPTION

CONSTRUCTOR

new

OPTIONS

METHODS

encode(Str|Array)

get(Int type)

AUTHOR

COPYRIGHT AND LICENSE

Algorithm::ZobristHashing v0.0.5

Authors

License

Dependencies

Test Dependencies

Provides

Documentation