주간 챌린지 #084 작업 #2::(라쿠)

작업 #2 › 사각형 찾기

제출자: Mohammad S Anwar

1과 0만 있는 m x n 크기의 행렬이 주어집니다.

네 모서리가 모두 1로 설정된 정사각형의 개수를 구하는 스크립트를 작성하십시오.

Example 1:

Input: [ 0 1 0 1 ]
       [ 0 0 1 0 ]
       [ 1 1 0 1 ]
       [ 1 0 0 1 ]

Output: 1

설명:
주어진 행렬에는 1이 r=1;c=2에서 시작하므로 4개의 모서리가 있는 하나의 정사각형(3x3)이 있습니다.

[ 1 0 1 ]
[ 0 1 0 ]
[ 1 0 1 ]

Example 2:

Input: [ 1 1 0 1 ]
       [ 1 1 0 0 ]
       [ 0 1 1 1 ]
       [ 1 0 1 1 ]

Output: 4

설명:
주어진 행렬에는 1이 r=1;c=1에서 시작하므로 4개의 모서리가 있는 하나의 정사각형(4x4)이 있습니다.
주어진 행렬에는 1이 r=1;c=2에서 시작하므로 4개의 모서리가 있는 하나의 정사각형(3x3)이 있습니다.
주어진 행렬에는 4개의 모서리가 1인 두 개의 정사각형(2x2)이 있습니다. 첫 번째는 r=1;c=1에서 시작하고 두 번째는 r=3;c=3에서 시작합니다.

Example 3:

Input: [ 0 1 0 1 ]
       [ 1 0 1 0 ]
       [ 0 1 0 0 ]
       [ 1 0 0 1 ]

Output: 0

지난 번 Challenge #077에서 우리는 외로운 X를 찾았고 오늘은 사각형을 찾을 것입니다. 사각형은 4개의 점으로 구성됩니다. 이 작업은 대각선 사각형에 대해 언급하지 않으므로 건너뛸 것입니다.

사용자 마음 읽기..(STDIN에서 사용자 입력)

다음은 사용자 입력에서 데이터를 읽는 서브루틴입니다.

sub read-matrix {
    $*IN.lines. # read lines from STDIN
    map( |*.split( /"]" \s* "\n"* | "\n"/  ) ).
    #  `-> split rows by newline or `]'
    map( -> $l { next if $l ~~ "";  # skip empty line
                 S:g/ '[' || \s+ //.comb.cache with $l } );
    # `-> remove unused chars.
}

# this is one-line for copy and paste in Raku shell
sub read-matrix { $*IN.lines.map( |*.split( /"]" \s* "\n"* | "\n"/  ) ).map( -> $l { next if $l ~~ ""; S:g/ '[' || \s+ //.comb.cache with $l } ); }

루틴은 약간 유연하므로 아래와 같이 입력할 수 있습니다.

> read-matrix
[1101][1100][0111][1011] # Ctrl-D to finish input
((1 1 0 1) (1 1 0 0) (0 1 1 1) (1 0 1 1))

PWC는 사용자 입력을 받는 데 그렇게 엄격하지 않습니다. 코드에 배열을 간단히 넣는 것으로 시작할 수 있습니다. 예를 들어 시작할 수도 있습니다.

my @matrix = [1,1,0,1], [1,1,0,0], [0,1,1,1], [1,0,1,1];

또는

my @matrix = <1 1 0 1>, <1 1 0 0>, <0 1 1 1>, <1 0 1 1>;

텅 빈 세상에서 하나를 찾아서

그래서 우리는 기본적으로 행별로 검색하고 있습니다. 다음 항목으로 이동하기 전에 유용한 레코드를 만들고 싶었습니다. 사용자 입력을 받는 동안에도 할 수 있습니다. 그러나 디버깅 목적으로 나는 일반적으로 그렇게 하지 않습니다.

A Rectangle canbe made from parallel TWO LINES

이것이 제가 오늘 따라갈 기본 개념입니다. 그러나 우리가 찾고 있는 것은 실제로 정사각형이므로 이러한 선 쌍은 ...

두 선이 평행하다(주어진)

두 선의 길이가 같아야 함(평행사변형)

두 줄이 같은 열(직사각형)에서 시작해야 합니다

.

두 선 사이의 거리는 길이와 같아야 합니다.

수집 라인

각 행에서 가능한 모든 행을 기록할 것입니다.
선을 만들려면 두 개의 서로 다른 점이 필요합니다. 그래서 조합을 다시 사용하겠습니다. (실제로 각 포인트의 값이 1인지 확인해야 합니다. 그렇지 않으면 포인트가 아닙니다.)

(^@matrix.elems).
map( -> $r
    {
        @matrix[$r].pairs.grep( *.value == 1, :k ).
        combinations(2).
        map({( $_, $r)}).Slip
} ).say

복사하여 붙여넣기 ✂️📋

(^@matrix.elems).map( -> $r { @matrix[$r].pairs.grep( *.value == 1, :k ).combinations(2).map({( $_, $r)}).Slip } ).say

(((0 1) 0) ((0 3) 0) ((1 3) 0) ((0 1) 1) ((1 2) 2) ((1 3) 2) ((2 3) 2) ((0 2) 3) ((0 3) 3) ((2 3) 3))

👉 ((0 1) 0)은 행 번호 0에서 0과 1의 점을 의미합니다.

직사각형 찾기(분류)

그리고 수직으로 정렬되고 길이가 같은 선을 찾을 것입니다.

...snip...
    classify( {.[0].Str}, # key:  two points as *pair*
              # note: if we don't pair, classify() will smartly make trees
              #       which, I don't want to here.
            ).
...snip...

복사하여 붙여넣기 ✂️📋

((^@matrix.elems).map( -> $r { @matrix[$r].pairs.grep( *.value == 1, :k ).combinations(2).map({( $_, $r)}).Slip } ).classify( {.[0].Str} ).say;

# indented by hand ✍️ ;;;
{ 0 1 => [((0 1) 0) ((0 1) 1)],
  0 2 => [((0 2) 3)],
  0 3 => [((0 3) 0) ((0 3) 3)],
  1 2 => [((1 2) 2)],
  1 3 => [((1 3) 0) ((1 3) 2)],
  2 3 => [((2 3) 2) ((2 3) 3)] }

우리가 여기에 있는 것은 그것입니다. 각 행에 두 개의 점으로 분류됩니다. 값의 수가 2 이상이면 사각형을 찾을 가능성이 있습니다.

스퀘어 스퀘어 스퀘어

이제 규칙 3번을 적용할 때입니다.

1. The distance between two lines must be same as the its length.

...snip...
    values. # only interested in values not keys like "*0 1* =>"
    map(
        { .combinations(2).cache.       # -> combinations of two lines
          grep( {  ([-] .[0;0].reverse) # length of a line
                   ==                   #    is same as
                   ([-] .[*;1].reverse) # distacne between two lines
               } ).Slip
        } ).

...snip...

다시, 복사 및 붙여넣기 ✂️📋

((^@matrix.elems).map( -> $r { @matrix[$r].pairs.grep( *.value == 1, :k ).combinations(2).map({( $_, $r)}).Slip } ).classify( {.[0].Str} ).values.map({ .combinations(2).cache.grep( {  ([-] .[0;0].reverse) == ([-] .[*;1].reverse)} ).Slip } ).say

# again handcrafted indented output
(
    (((0 3) 0) ((0 3) 3))
    (((0 1) 0) ((0 1) 1))
    (((2 3) 2) ((2 3) 3))
    (((1 3) 0) ((1 3) 2))
)

각 행에는 두 줄에 대한 정보가 포함되어 있으며 두 행 번호 사이의 거리를 계산하면 사각형을 만들고 있음을 확인할 수 있습니다!

최종 코드

어떤 궁금증과 테스트를 위해 최종 코드를 남겼습니다. 뭔가 잘못되었거나 질문이 있으면 알려주십시오. 고맙습니다!!!

#!/usr/bin/env raku
# -*- Mode: Raku; indent-tabs-mode: nil; coding: utf-8 -*-
# vim: set et ts=4 sw=4:

use v6.d;

=begin test-example

echo '[101][110][011] ' | raku jeongoon/raku/ch-2.raku
# -> 0
echo '[1101][1100][0111][1011]' | raku jeongoon/raku/ch-2.raku # example #2
# -> 4

=end test-example

# modifed from #077/ch-2.raku
sub USAGE {
    say "Usage:";
    say '    echo -e "[1 0 1][0 1 0][1 0 1]" | raku ch-2.raku',"\n";
    say "# or input ending with EOF (Ctrl-D or Ctrl-Z)";
    say "# you might need to filter the STDERR to get only answer.";
}

unit sub MAIN;

say "Input: (Ctrl-D or Ctrl-Z to finish to input.)";
my @matrix =
$*IN.lines.                                     # read lines from STDIN
map( |*.split( /"]" \s* "\n"* | "\n"/  ) ).     # split rows by newline or `]'
map( -> $ln { next if $ln eq "";                # skip empty line
              S:g/ '[' || \s+ //.comb.cache     # remove unused chars.
                 with $ln } );

with @matrix {
    say "A matrix recognized as ..\n";
    say "{.Array}" for $_;
    say "";

    # part1: find the all possible horizontal lines(pairs of two points)
    (^.elems).
    map( -> $r {
               .[$r].pairs.
               grep( *.value == 1, :k ).      # filter point(has value of 1)
               combinations(2).               # make pairs of two column number
               map({( $_, $r)}).Slip          # as line(two points), row number
           } ).

    # part2: group the lines which starts at the same point and has the same len
    classify( -> $rec
              {$rec[0].Str},                  # key:  two points as *pair*
              # note: if we don't pair, classify() will smartly make trees
              #       which, I don't want to here.
            ).

    # part3: find squares
    #        (check two lines has distance as same as the length of line)

    ## only interested in values (the list of (distance between pts, row num))
    values.
    map(
        { .combinations(2).cache.             # -> combinations of two lines
          grep( {  ([-] .[0;0].reverse)       # length of a line
                   ==                         #    is same as
                   ([-] .[*;1].reverse)       # distacne between two lines
               } ).Slip
        } ).

    # explaination
    map(
        {
            FIRST { $*ERR.say("Explanations:\n") }
            $*ERR.say( ++$,":{.raku}" );
            $*ERR.say( " ☞ both lines have length of "
                       ~ "{[-] .[0][0].reverse} "
                       ~ " and {[-] .[*;1].reverse} away from each other.\n" );
            LAST { $*ERR.print( "∴ " ) }
            .self }).
    elems.
    say;
}

이것은 🐪PWC🦋의 일부가 될 것입니다. 읽어주셔서 감사합니다!!!