CY's Recent Submission for PWC(061-063)

This is a part of Perl Weekly Challenge(PWC) and the followings are related to my solution. If you want to challenge yourself on Perl, go to https://perlweeklychallenge.org, code the latest challenges, submit codes on-time (by GitHub or email)(before Monday GMT+0 00:00) if possible, before reading my blog post.

Miss out blogging for a while. Here just write some lines on the recent PWC coding experience.

Challenge 061

ch-1 :

Enumeration

ch-2 :

Before coding, I had thought it was a complicated task for regular expression. It turned out smoother.

I use a subroutine possible_octet to check whether a number can be a part of IPv4 octet.

Its content:

sub possible_octet {
    my $item = $_[0];
    if ($item =~ /^[0-9]$/ or $item =~ /^[1-9][0-9]$/ ) {
        return 1; }
    elsif ($item =~ /^[1-9][0-9][0-9]$/) {
        return  ( $item <= 255) ;
    }
    else {
        return 0;
    }
}

Btw, I tried to use Test::Simple to check the validity of my codes, but it keeps behaving abnormally in some test cases; in addition, the position of occurence of a possible solution in the array varies, hence I gave up performing with the Test module(s) in the task.

link for codes

Challenge 062

ch-2 (3D Queens):

It is hard to believe that I wrote an (2D) N Queens program as exercise of recursion just a few weeks ago. One of the differences is the representation of the chess board. For the 2D version, I carefully used array of references of array (${$field[$x]}[$k], which can be simplified as $$field[$x][$k]), which should be safe. For the 3D version, I decided to be "rough and risky" to use "multidimensional arrays" $cube[$i][$j][$k](which folks say it isn't really implemented in Perl).

I coded my M queens step-by-step with looking at the 2D version; this method really helped -- I did not get lost with the lengthy codes and logics.

Though, there are many differences in 3D Queens! The first wonder is: is the number of non-mutual-attacking queens smaller or larger than the number of the edge size of cube? In the 2D cases, for edge size larger than 2, the number of possible placed queens is always[1] equal to the edge size of the chess board. It turns out much more queens can be put though the number of lines of attacking of each queen increases from 4 (two diagonal, row, columns) to 13 -- 3 ("straight lines") + 6 (plane diagonals) + 4 (space diagonals)

My code performs reasonably until M=4 only. With some information of the maximum possible number of non-attacking queens, and modify the code (exit when find a solution with the required number of queens in the cube), it runs fast for M=5 (no. of max. queens = 13), but not M=6 (no. of max. queens = 21) (looking for solution for M=6, required no. of queens=19 is fast, within a second).

See the OEIS page about the 3D queens: OEIS: A068940 .

link for codes

Challenge 063

ch-1 :
It increases my knowledge on Perl about the "Regexp Quote-Like Operators".
ch-2 :
Again I try to solve it mathematically. Looking at the example case, do you notice that 28, as the 7th triangular number, is the first triangular number divisible by 4? I do some optimization when the word is exactly a repeated pattern of a shorter string: (a bit different from the submitted version)
sub lookup_repeated {
    my $word = $_[0];
    my $le = 1;
    while ($le <= $wordlen/2) {
        if ($wordlen % $le == 0) { 
            my $multiple = $wordlen/$le;
            my $pattern = substr $word, 0, $le;
            if ( ($pattern x $multipleeq $word ) {
                return $le;
            } 
            else {
                $le++;
            }
        } 
        else {
            $le++;
        }
    }
    return $wordlen if $le > $wordlen/2 ;
}

Afterwards it is a case of looking up the smallest triangular number divisible by the pattern length.

link for codes


Again, stay healthy! □

[1]: See Wikipedia: Eight queens puzzle#Existence_of_solutions

1 Comment

Nice blog, keep it going.

Leave a comment

About C.-Y. Fung

user-pic I blog about Perl.