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

작업 #2 › 어레이 뒤집기

제출자: Mohammad S Anwar

양수 배열 @A가 제공됩니다.

모든 구성원의 합이 음이 아닌 최소값이 되도록 주어진 배열의 일부 구성원의 부호를 뒤집는 스크립트를 작성하십시오.

양수 요소의 배열이 주어지면 배열 요소의 결과 합계가 음수가 아닌 최소(가능한 한 0에 가까워야 함)가 되도록 일부 요소의 부호를 뒤집어야 합니다. 최소 번호를 반환합니다. 결과 합계가 음이 아닌 최소값이 되도록 부호를 뒤집어야 하는 요소의 수.

Example 1:

Input: @A = (3, 10, 8)
Output: 1

Explanation:

Flipping the sign of just one element 10 gives the result 1
i.e. (3) + (-10) + (8) = 1

Example 2:

Input: @A = (12, 2, 10)
Output: 1

Explanation:

Flipping the sign of just one element 12 gives the result 0
i.e. (-12) + (2) + (10) = 0

👍 뒤집기 👎

내가 처음에 상상하는 것은 히스토그램의 이미지이며 작업 이름에서 알 수 있듯이 모든 조합의 숫자를 뒤집습니다.
괜찮아. 왜 안 돼?

일련의 숫자를 뒤집으면 아래와 같이 쓸 수 있습니다.

> (1,2,3).map( -> $n { $n, -$n } )
((1 -1) (2 -2) (3 -3))

그리고 X을 사용하여 순열을 생성할 수 있습니다.

> [X] (1,2,3).map( -> $n { $n, -$n } )
((1 2 3) (1 2 -3) (1 -2 3) (1 -2 -3) (-1 2 3) (-1 2 -3) (-1 -2 3) (-1 -2 -3))

거의 완료되었습니다. 그러나... TMTOWTDI

보시다시피 거의 완료되었습니다. 하지만 잠깐.. 뭔가가 내 머리를 가로질러.. 우리는 두 그룹의 숫자가 필요합니다...

A Tale of Two towers (♜Positive|♖Negative)

다음과 같이 두 그룹으로 나눌 수 있는 세 개의 숫자가 있습니다.

(12) (2 10)
(12 2) (10)
(2) (10 12)

그리고 두 그룹 간의 합산 차이가 답이 될 수 있습니다.
나는 이 접근법이 완전히 다른 두 가지 개념을 포함한다는 것을 발견했습니다 ...

조합

가방과 (-)

조합

Raku의 조합이 내장되어 있습니다. 걱정 마. 추가 라이브러리를 로드할 필요가 없습니다.

>  my @n = 12, 2, 10;
[12 2 10]
> @n.combinations(1..2) # we can use a Range
((12) (2) (10) (12 2) (12 10) (2 10))

양수만 있으면 의미가 없기 때문에 마지막 선택 수(@n.elems)를 건너뛰는 것이 좋습니다.

> @n.combinations( 1 .. @n.end )
((12) (2) (10) (12 2) (12 10) (2 10))

📖 .end
그리고 가방 만들기는 아래와 같이 간단합니다.

> @n.combinations( 1.. @n.end ).map( *.Bag )
(Bag(12) Bag(12) Bag(2) Bag(12(2)) Bag(12 2) Bag(12 2))

또는 하이퍼 연산자를 사용하여>>

@n.combinations( 1.. @n.end )>>.Bag
(Bag(12) Bag(12) Bag(2) Bag(12(2)) Bag(12 2) Bag(12 2))

가방

우리는 다른 하나가 필요합니다. 쌍을 만들자

shell> cat g.raku
my @n = 12, 2, 10;
my $b = @n.Bag;
@n.combinations( 1.. @n.end )>>.Bag.
map( ->  $NegBag {
           ($b (-) $NegBag), $NegBag
       } ).
# `-> we made a list of two groups
map( { say "{.first} <=> {.tail}" } );
shell> raku g.raku
2 10 <=> 12
10 12 <=> 2
2 12 <=> 10
10 <=> 12 2
2 <=> 10 12
12 <=> 10 2

이제 .classify -ing에 의해 주어진 목록에서 의미 있는 데이터를 생성할 수 있습니다. 여기까지의 전체 코드입니다.

my @n = 12, 2, 10;
my $b = @n.Bag;
@n.combinations( 1.. @n.end )>>.Bag.
map( ->  $NegBag {
           ($b (-) $NegBag), $NegBag
       } ).
# `-> we made a list of two groups
classify(
    {
        with [-] .map( *.kxxv.sum ) {
            $_ < 0 ?? Inf !! $_ # 👉 see note, please
        }
    },
          :as{ .[1].elems } ).
say

{0 => [1 2], 4 => [1], 20 => [1], Inf => [2 2]}

📖 * .kxxv

"0 => [1 2]"는 1 또는 2개의 숫자를 채워서 0의 합을 만들 수 있음을 의미합니다.
👉 참고: 나는 음수 합계를 Inf로 분류하므로 음수 그룹을 정렬할 때 마지막에 나열됩니다.

또는 또 다른 TMTOWTDI!. .map은 Perl과 Raku에서 매우 강력한 도구이며, 그룹의 합을 계산하는 것은 .sum으로 수행할 수 있으며, 맵 제어 흐름에서 다음으로 수행된 빼기의 음수 결과를 필터링할 수 있습니다(Raku는 .map에 제어 흐름이 있지만 Perl에는 없음)

... snip ...
# `-> we made a list of two groups
map( -> $TwoGroups {
           with ([-] $TwoGroups.map( *.kxxv.sum )) {
               next if $_ < 0; # filtering
               $_ => $TwoGroups[1].total # interested in counts
           }
       } ).
say;

정렬 및 가져오기

마지막 단계는 위의 경우 0인 최소 합계를 얻기 위해 결과를 정렬하는 것입니다(.key 및 .value 모두 기준). 첫 번째 것을 취합니다.

... snip ...
# `-> we made a list of two groups
map( -> $TwoGroups {
           with ([-] $TwoGroups.map( *.kxxv.sum )) {
               next if $_ < 0; # filtering
               $_ => $TwoGroups[1].total # interested in counts
           }
       } ).
sort.  # automatically sort by .key and .value
first. # take first one
value. # only interested in value
say

최종 코드

긴 설명 끝에 Bag으로 두 그룹을 만들 필요가 없다는 것을 깨달았습니다. 다른 운동으로 받아주세요 :-)

multi MAIN ($n where * > 0) { say 0 }
multi MAIN (*@n where { @n.all ~~ Int and @n.all > 0 }) {
    my $s = @n.sum;
    @n.combinations( 1..^ @n ).
    map(
        -> \n {
            with $s - 2 * n.sum { # same as ( $s- n.sum ) - n.sum
                next if $_ < 0;
                $_ => n.elems
            }
        } ).
    sort.
    first.value.
    say
}

또한 정렬()이 예상대로 작동하는 경우. min()도 마찬가지입니다.

multi MAIN ($n where * > 0) { say 0 }
multi MAIN (*@n where { @n.all ~~ Int and @n.all > 0 }) {
    my $s = @n.sum;
    @n.combinations( 1..^ @n ).
    map(
        -> \n {
            with $s - 2 * n.sum { # same as ( $s- n.sum ) - n.sum
                next if $_ < 0;
                $_ => n.elems
            }
        } ).
    min.
    value.
    say
}

한 가지 더 ... 레이스

I recalled that Colin Crain's code at 077 Task #1 몇 가지 숫자로 시도하십시오.
15개 이상의 숫자가 주어졌을 때 차이를 느낄 것입니다.

multi MAIN ($n where * > 0) { say 0 }
multi MAIN (*@n where { @n.all ~~ Int and @n.all > 0 }) {
    my $s = @n.sum;
    @n.combinations( 1..^ @n ).
    race( :8degree:500batch ). # 👈 here
    map(
        -> \n {
            with $s - 2 * n.sum { # same as ( $s- n.sum ) - n.sum
                next if $_ < 0;
                $_ => n.elems
            }
        } ).
    race( :8degree:500batch ). # 👈 and here
    min.
    value.
    say
}

이것은 정확한 벤치마크는 아니지만 차이점을 맛볼 수 있습니다 :-)

time raku ch-2.with-race.raku 12 7 4 5 6 9 20 12 7 4 5 6 9 20 9 4 2 1 13
5

________________________________________________________
Executed in    3.59 secs   fish           external 
   usr time    9.28 secs  568.00 micros    9.28 secs 
   sys time    0.13 secs  137.00 micros    0.13 secs 

time raku ch-2.raku 12 7 4 5 6 9 20 12 7 4 5 6 9 20 9 4 2 1 13
5

________________________________________________________
Executed in    5.60 secs   fish           external 
   usr time    5.70 secs    0.00 micros    5.70 secs 
   sys time    0.03 secs  710.00 micros    0.03 secs 

읽어주셔서 감사합니다~!!, 관심있으신 분들은
확인해주세요 https://perlweeklychallenge.org/challenges
다음을 참조하십시오. 👋