DEV Community

Cover image for Weekly Challenge #085 Task #2 :: (Raku)
Myoungjin Jeon
Myoungjin Jeon

Posted on • Updated on

Weekly Challenge #085 Task #2 :: (Raku)

TASK #2 › Power of Two Integers

Submitted by: Mohammad S Anwar

You are given a positive integer $N.

Write a script to find if it can be expressed as a ^ b where a > 0 and b > 1. Print 1 if you succeed otherwise 0.

Example 1:

Input: 8
Output: 1 as 8 = 2 ^ 3

Example 2:

Input: 15


Output: 0

Example 3:

Input: 125
Output: 1 as 125 = 5 ^ 3
Enter fullscreen mode Exit fullscreen mode

Staring Point

Where should I start? one thing I know is that when "1" is given, answer is 1 as 1 always remain 1 no matter how many times we multiply. and answer is always "0" when a prime number given. so wrote down like below.

multi sub MAIN (1) { say "1 as 1²" }

multi sub MAIN ( Int \N where * > 0 ) {
    if N.is-prime {
        say "0 as {N} is a prime number.";
    }
    else {
        die "not implemented";
    }
}
Enter fullscreen mode Exit fullscreen mode

And we needs factor k¹, k², k³ to compare given number but what k value can be? Starting point would be square root of N!!

> 144.sqrt
12
> 145.sqrt
12.041594578792296
Enter fullscreen mode Exit fullscreen mode

So if we started from 12 to 1 and comparing 12², 12³ ..., we could find the given N can be expressed with two integers. Code below will find the largest maybe factor of N as mentioned above.

sub largest-factor ( Int \n --> Int ) { n.sqrt.Int }
Enter fullscreen mode Exit fullscreen mode

One More Thing about Lazy

There is a function called "repeat" in Haskell

λ= take 4 (repeat 3)
[3,3,3,3]
Enter fullscreen mode Exit fullscreen mode

Code below will do similar thing in Raku

> [3,3 ... Inf].head(4)
(3 3 3 3)
Enter fullscreen mode Exit fullscreen mode

because

> [3,3 ... Inf].is-lazy
True
Enter fullscreen mode Exit fullscreen mode

It is handy when actually have no idea how long the list will be.
So If we are interested in making a¹, a², a³, we could code like

> gather { loop ( my $i = 1; $i <=3 ; $i++ ) { take 2**$i } }
(2 4 8)
Enter fullscreen mode Exit fullscreen mode

But also

> [2,2...Inf].produce( { $^a * $^b } ).head(3)
# or
> [2,2...Inf].produce( &[*] ).head(3)
# or
> [2,2...Inf].produce( * * * ).head(3)
# or 
> ([\*] [2,2...Inf]).head(3)
(2 4 8)
Enter fullscreen mode Exit fullscreen mode

The difference between two ways is lying on imperative programming vs functional programming. In former way we can break the loop sometimes or somewhere. but latter one shows that control is handled by outer function(head()). I'm not saying that which one is better. but functional programming generally show the progress better, IMHO.
It was good chance for me to see how the Raku is lazily evaluate the code. So I wrote a solution like below.

A Solution Using* produce()

multi sub MAIN ( Int \N where * > 0 ) {
    if N.is-prime {
        say "0 as {N} is a prime number.";
    }
    else {
        my $lf = largest-factor(N);
        ( $lf ... 2 ).
        lazy.
        map(
            -> $a {
                ([\×] ($a,$a ... )). # produce a¹, a², a³
                lazy.                   # in lazy way
                skip(1).                # but we don't need first one (a¹)
                kv.
                map(
                    -> \β, \κ {
                        if    N == κ { ($a => β + 2) }  # as `b' value
                        elsif N <= κ { last  }
                        else          { Empty }
                    } ).Slip
            } ).first
        andthen say "1 as {.key}{pow-utf8(.value)}"
        orelse  say "0"
    }

}
Enter fullscreen mode Exit fullscreen mode

exp-utf8 function looks like below

sub pow-utf8 ( Int $n ) {
    state @pow = < ¹ ² ³      >;
    @pow[ $n.comb ].join;
}
Enter fullscreen mode Exit fullscreen mode

Log

BTW, we have log() function. so we don't actually need to produce a^b values.

> log( 8, 2 )
3 # a: 2, b: 3
> log( 8, 2 ).Rat.denominator # there is no floating point value
1
Enter fullscreen mode Exit fullscreen mode

Of course everything is first class in Raku, so we can write like below as well!

> 144.log(12)
2
Enter fullscreen mode Exit fullscreen mode

UPDATE (5th Nov)

Rat has smaller precision than I expect, so N is bigger, solution is less accurate. so we need to increase the precision like below.

> log( 33429368569, 182837 ).Rat( 1e-32 );
2
> log ( log( 334293685691, 578181 ).Rat
2 # (wrong) because ...
> 578181², 334293685691.sqrt
(334293268761 578181.3605530708)
Enter fullscreen mode Exit fullscreen mode

Final Code.appended()

multi sub MAIN ( Int \N where * > 0, Bool:D :$log ) {
    $*ERR.say( "alternative solution using log() ..." );
    if N.is-prime {
        say "0 as {N} is a prime number.";
    }
    else {
        my $lf = largest-factor(N);
        ( $lf ... 2 ).
        lazy.map(
            { my $pow = log( N, $_ ).Rat( 1e-32 );
              ($_ => $pow.Int) if $pow.denominator == 1;
            }
        ).first
        andthen say "1 as {.key}{pow-utf8(.value)}"
        orelse  say "0"
    }
}
Enter fullscreen mode Exit fullscreen mode

Happy Coding !!!
If you have a time, please visit at 🐪PWC🦋.

Discussion (0)