주간 챌린지 #085 태스크 #2::(Raku)

작업 #2 › 두 정수의 거듭제곱

제출자: Mohammad S Anwar

양의 정수 $N이 주어집니다.

a > 0 및 b > 1인 경우 a ^ b로 표현할 수 있는지 알아보는 스크립트를 작성하세요. 성공하면 1을 출력하고 그렇지 않으면 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

출발점

어디서부터 시작해야 하나요? 내가 아는 한 가지는 "1"이 주어졌을 때 우리가 몇 번이나 곱하든 1은 항상 1로 유지되기 때문에 답은 1이라는 것입니다. 그리고 대답은 소수가 주어졌을 때 항상 "0"입니다. 그래서 아래와 같이 적었다.

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

그리고 주어진 숫자를 비교하기 위해 인자 k¹, k², k³가 필요하지만 k 값은 무엇일 수 있습니까? 시작점은 N의 제곱근입니다!!

> 144.sqrt
12
> 145.sqrt
12.041594578792296

따라서 12에서 1로 시작하여 12², 12³ ...를 비교하면 주어진 N이 두 개의 정수로 표현될 수 있음을 알 수 있습니다. 아래 코드는 위에서 언급한 N의 가장 큰 아마도 인자를 찾을 것입니다.

sub largest-factor ( Int \n --> Int ) { n.sqrt.Int }

게으른 것에 대해 한 가지 더

Haskell에는 "반복"이라는 기능이 있습니다.

λ= take 4 (repeat 3)
[3,3,3,3]

아래 코드는 Raku에서 비슷한 작업을 수행합니다.

> [3,3 ... Inf].head(4)
(3 3 3 3)

왜냐하면

> [3,3 ... Inf].is-lazy
True

목록이 얼마나 긴지 모를 때 유용합니다.
따라서 ¹, ², a³를 만드는 데 관심이 있다면 다음과 같이 코딩할 수 있습니다.

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

그러나 또한

> [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)

두 가지 방법의 차이점은 명령형 프로그래밍과 함수형 프로그래밍에 있습니다. 이전 방식으로 우리는 때때로 또는 어딘가에서 루프를 끊을 수 있습니다. 그러나 후자는 제어가 외부 함수(head())에 의해 처리됨을 보여줍니다. 어느 것이 더 낫다고 말하는 것이 아닙니다. 그러나 함수형 프로그래밍은 일반적으로 IMHO의 진행 상황을 더 잘 보여줍니다.
Raku가 어떻게 코드를 게으르게 평가하는지 볼 수 있는 좋은 기회였습니다. 그래서 아래와 같은 해결 방법을 작성했습니다.

생산*을 사용하는 솔루션()

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"
    }

}

exp-utf8 함수는 아래와 같습니다.

sub pow-utf8 ( Int $n ) {
    state @pow = <⁰ ¹ ² ³ ⁴ ⁵ ⁶ ⁷ ⁸ ⁹>;
    @pow[ $n.comb ].join;
}

통나무

BTW, 우리는 log() 함수를 가지고 있습니다. 따라서 실제로 ^b 값을 생성할 필요가 없습니다.

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

물론 라쿠에서는 모든게 퍼스트 클래스이므로 아래와 같이 쓸 수도 있습니다!

> 144.log(12)
2

업데이트(11월 5일)

Rat는 예상보다 정밀도가 작기 때문에 N이 더 크고 솔루션이 덜 정확합니다. 따라서 아래와 같이 정밀도를 높여야 합니다.

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

최종 코드.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"
    }
}

해피코딩!!!
시간되시면 🐪PWC🦋 으로 방문해주세요.