패턴    최적으로 접혔을 때 접촉지점의 갯수
0000    0
0001    0
0010    0    (1이 하나 이하라면 어떻게 접히든 1-1 쌍이 나올리 없음)
0011    1    (11의 경우는 어떻게 접히든 1-1 쌍이 하나)
0100    0
0101    0
0110    1
0111    2
1000    0
1001    1    (정사각형 형태로 접힐 때 두 1이 만남)  11
1010    0                                           00
1011    2
1100    1
1101    2
1110    2
1111    4    (정사각형 형태로 접힐 때 최적)
---------
합     16
평균 = 16 / 2^4 = 1

#!perl
# Problem 300
# 답은 264957 / 32768 = 8.085845947265625 ? 근데 오답이라 나옴;;;
# 컴퓨터에서는 나눗셈의 결과가 8.08584594726563 로 마지막 자리가 잘리니 주의
# 
use strict;
use warnings;

my $LENGTH =  $ARGV[0] || 8;

sub ver8 { #{{{

    # 단백질의 길이 - 명령행 인자로 받거나, 기본값 8
    my $length = $LENGTH;

    # 현재 좌표의 상하좌우에 추가로 원소를 배치할 경우 좌표 계산을 위한 오프셋
    my %next = (
        up    => [ -1, 0 ],
        down  => [  1, 0 ],
        left  => [  0,-1 ],
        right => [  0, 1 ],
    );


    # 가능한 형태들의 리스트
    # $fold[0] 은 길이 0인 단백질이 취할 수 있는 형태들의 배열 (당연히 없다)
    # $fold[1], $fold[2] 는 각각 길이 1, 2인 단백질이 취할 수 있는 형태들 (1가지씩)
    # 길이 1인 경우는 당연히 1가지이고, 길이 2인 경우는 총 4가지가 있겠지만:
    #        1
    #        0     10     01     0
    #                            1
    # 어차피 다 같은 형태니까 처음 두 원소는 아래로 붙어있는 마지막 형태만 취급
    my @fold = (
        # 원소 0개
        [ ],
        # 원소 1개
        [
            {
                coord => [ [ 0, 0 ] ],
                neighbor => [ ],
                elems => { "0,0" => "0" },
            }
        ],
        # 원소 2개
        [
            {
                coord => [ [ 0, 0 ], [ 1, 0 ] ],            # 각 원소의 [ y, x ] 좌표
                neighbor => [ ],                            # 순서상 인접한 원소들 외에 추가로 이웃이 되는 원소의 인덱스 쌍의 배열
                elems => { "0,0" => "0", "1,0" => "1" },    # coord의 역으로, "y좌표,x좌표"를 키로 하고 해당 좌표에 있는 원소의
                                                            # 인덱스를 값으로 하는 해쉬. 특정 좌표에 이미 원소가 있는지 확인할 때 사용
            }
        ],

        # 예를 들어 원소 4개인 단백질의 경우
        #      0    0    0     0     03
        #      1    1    123   12    12
        #      2    23          3
        #      3
        # 이렇게 다섯개의 구조가 있다.
        # (두번째~다섯번째 형태는 좌우 대칭인 형태가 하나씩 있으나 이건 결국 동일한 형태이니 생성하지 않음)
        # 따라서 $fold[4]는 익명 해쉬 5개가 원소로 있는 익명 배열이고,
        # 다섯번째 구조를 나타내는 익명 해쉬의 예를 들면
        # {
        #    coord => [ [0,0], [1,0], [1,1], [0,1] ]   # 0~3번 원소의 y,x 좌표값들
        #    neighbor => [ [0,3] ]                     # 0번과 3번 원소가 추가로 이웃이 되었음
        #    elems => { "0,0"=>"0", "1,0"=>"1", "1,1"=>"2", "0,1"=>"2" }  # coord 의 역. 좌표=>원소인덱스
        # }
        # 이런 형태가 된다.
    );



    # 이제 길이 15개인 단백질이 취할 수 있는 모든 형태를 생성한다.
    # 길이2의 형태에서 마지막 원소인 1번 원소 상하좌우에 2번 원소를 붙여 길이3이 취할 수 있는 형태를 생성하고,
    # 다시 길이3의 각 형태에 대하여 마지막 2번 원소에 3번 원소를 상하좌우에 붙여 길이4의 형태들을 생성하는 식의 반복

    for my $l ( 3 .. $length ) {

        my @temp_fold = ();     # 길이 $l 짜리의 형태들의 배열

        foreach my $combi ( @{$fold[$l-1]} ) {      # 길이 $l-1 짜리 각 형태에 대하여
            my $lc = $combi->{coord}[-1];           # 마지막 원소의 좌표
            my $nc;                                 # 새로 추가될 $l번째 원소의 좌표
            my $ni = scalar @{ $combi->{coord} };   # $l번째 원소의 인덱스

            foreach my $dir ( qw/up right down left/ ) {

                # 이전 형태가 세로로만 이어진 막대 형태라면 이 때는 left 는 right 와 대칭이 되므로 패스
                if ( $lc->[0] == $ni - 1 and $dir eq "left" ) {
                    next;
                }

                # 추가될 원소의 좌표 계산
                $nc = [
                    $lc->[0] + $next{$dir}[0] ,
                    $lc->[1] + $next{$dir}[1]
                ];

                # 이 좌표가 이미 사용되었는지 검사
                if ( exists $combi->{elems}{ $nc->[0].",".$nc->[1] } ) {
#                     print "[ $nc->[0], $nc->[1] ] is used\n";
                }
                else {
                    # 새 원소가 추가된 형태 생성
                    my $new_combi = {
                        coord => [ @{$combi->{coord}} , $nc ],  # 좌표 배열은 기존 형태의 좌표 배열에 새 좌표 추가
                        neighbor => [ @{$combi->{neighbor}} ],  # 기존 형태의 이웃원소 목록, 아래에서 새 이웃 추가
                        elems => { %{$combi->{elems}} },        # 기존 형태의 좌표=>원소인덱스 해쉬
                    };
                    $new_combi->{elems}{ $nc->[0].",".$nc->[1] } = $ni; # 새 원소의 좌표=>인덱스 추가

                    # 새 원소와 인접하는 네이버들 찾음
                    foreach my $d ( qw/up right down left/ ) {
                        my $ec = [
                            $nc->[0] + $next{$d}[0],
                            $nc->[1] + $next{$d}[1],
                        ];
                        next if ( $ec->[0] == $lc->[0] and $ec->[1] == $lc->[1] );  # 직전 원소는 당연히 이웃이니 패스
                        if ( exists $new_combi->{elems}{ $ec->[0].",".$ec->[1] } ) {
                            push @{$new_combi->{neighbor}}, [ $new_combi->{elems}{$ec->[0].",".$ec->[1]} , $ni ];
                        }
                    }

                    push @temp_fold, $new_combi;
                }
            }
        }

        # DEBUG
#         { #{{{
#             # DEBUG용 출력.
#             print "----- new fold list (length: $l) ----\n";
#             foreach my $combi ( @temp_fold ) {
# 
#                 foreach my $y ( -1*$l .. $l ) {
#                     foreach my $x ( -1*$l .. $l ) {
#                         if ( exists $combi->{elems}{"$y,$x"} ) {
#                             print $combi->{elems}{"$y,$x"};
#                         }
#                         else {
#                             print " ";
#                         }
#                     }
#                     print "\n";
#                 }
# 
#                 print "neighbor => ";
#                 foreach my $coord ( @{$combi->{neighbor}} ) {
#                     printf "[%2d,%2d] ", $coord->[0], $coord->[1];
#                 }
#                 print "\n";
#                 print "\n";
#             }
#         } #}}}

        # 길이 $l에 대하여 모든 형태가 만들어졌음.
        # 이 형태들을 네이버 갯수가 많은 순으로 정렬을 하여 저장.
        # 정렬을 하는 이유는 나중에 불필요한 비교를 하지 않기 위함.
        $fold[$l] = [ sort { scalar(@{$b->{neighbor}}) <=> scalar(@{$a->{neighbor}}) } @temp_fold ];
    }

    # 이 시점에서 길이0부터 15까지의 모든 형태가 만들어졌다.
    # 그런데 위에 주석으로 적은 원소4개 단백질의 다섯 가지 형태를 보면,
    # 처음 네 가지는 추가로 이웃이 되는 원소가 한 쌍도 없다는 점에서 결국 동일한 형태라고 간주할 수 있다.
    # 이렇게 동일한 형태들은 한 가지만 남기고 제거한다.
    for (my $l = 3; $l <= $#fold; $l++) {
        my $temp = [];
        my %seen = ();

        foreach my $combi ( @{$fold[$l]} ) {    # 길이 $l의 각 형태들에 대하여
            my $str = join ":",
                        map { @$_ }
                          sort { ( $a->[0] <=> $b->[0] ) or ( $a->[1] <=> $b->[1] ) }
                            @{$combi->{neighbor}};

            unless ( $seen{$str} ) {            # 현재까지 나타나지 않았던 이웃조합의 형태 하나씩만 저장
                $seen{$str} = 1;
                push @$temp, $combi;
            }
        }

        $fold[$l] = $temp;
    }


    # 이제 형태 생성은 끝났음.
    #
    # 지금부터는 길이 15의 모든 단백질 2**15 개에 대하여,
    # 위에서 생성한 형태에 대입하여 H-H 가 만나는 CP의 갯수를 세고,
    # 각 단백질마다 최대의 CP값을 찾고,
    # 그 최대 CP값들의 합을 구한다.


    my $total_max_cp = 0;    # 최대 CP 값의 합

    # H또는 P로 구성된 단백질이니까 이진수처럼 생각할 수 있다.
    # H는 1, P는 0에 대응한다.
    # 따라서 2**15 - 1 까지의 수에 대해서 루프를 돈다.
    foreach my $num ( 3 .. (2**$length - 1) ) {
        my $str = sprintf ("%0${length}b", $num);       # 이진수 형태로 변환
        my @strs = split //, $str;                      # 특정 자리가 1인지 0인지 비교할때 substr을 써도 되지만, 알아보기 쉽게 배열로도 변환

        # 일단 스트링의 홀수번째 자리와 짝수번째 자리에 각각 하나 이상의 1이 있어야만 이웃이 생길 여지가 있다.
        # 그렇지 않다면 패스
        unless ( $str =~ /1(?:00)*1/ ) {
            next;
        }

        my $cp = 0;     # 일단 연속으로 배치된 1에 의해 생기는 CP의 갯수

        # $str에서 "11"의 갯수만큼 CP가 생긴다.
        # 예를 들어 00111001100 이면 CP는 최소 3개
        while ( $str =~ /1(?=1)/g ) {
            $cp++;
        }

        # 연속된 1의 그룹이 딱 하나만 있는 경우는 이걸로 끝이다.
        # 예: 000111100, 011000000 등
        if ( $str =~ /^0*111?0*$/ ) {
            $total_max_cp += $cp;
            next;
        }

        # 여기서는 형태에 직접 대입하기 전에, 미리 CP값을 눈으로 알 수 있는 것들을 추려냄
        # (그런데 CP값이 항상 그렇게 보장되는지 확신은 없다;)
        #
        # 1 하나씩 떨어져 있는 형태는 최대 CP값은 1
        # 예: 0100001000
        if ( $str =~ /^0*1(?:00)+10*$/ ) {
            $total_max_cp++;
            next;
        }
        # 11그룹 두개는 최대 CP값이 4이다.
        # 예: 01100001100
        if ( $str =~ /^0*11(?:00)+110*$/ ) {
            $total_max_cp += 4;
            next;
        }
        # 111그룹 두개는 최대 CP값이 7
        # 예: 00011100111
        if ( $str =~ /^0*111(?:00)+1110*$/ ) {
            $total_max_cp += 7;
            next;
        }
        # 1111그룹 두개는 최대 CP값이 10
        if ( $str =~ /^0*1111(?:00)+11110*$/ ) {
            $total_max_cp += 10;
            next;
        }
        # 여기까지가 추려내는 부분



        # 남은 경우는 별 수 없이 일일이 형태들에 대입하면서 추가적으로 나타나는 CP값을 구해야 한다.

        # 그런데 스트링의 뒷부분이 0으로 채워진 곳은 굳이 검사할 필요가 없다.
        # 예를 들어 001101110000000 패턴의 경우 마지막 PPPPPPP 는 어떻게 접히든 H-H의 갯수와 무관.
        # 따라서    00110111        패턴이라 생각하고 길이 8짜리 형태들과 비교하면 된다.

        my $t_length;       # 실제 검사할 길이 (마지막 "1"까지의 길이)
        if ( $str =~ /1(0*)$/ ) {
            $t_length = $length - length($1);
        }

        my $max_add_cp = 0; # 추가적인 CP 갯수의 최대값

        foreach my $combi ( @{$fold[$t_length]} ) {     # t_length 길이의 형태들에 대하여 루프.

            my $add_cp = 0;     # 이번 형태에서 추가로 생기는 CP의 갯수

            # 처음에 형태를 만들때 "추가적인 이웃쌍의 갯수"의 내림차순으로 정렬하였다.
            # 예를 들어 어떤 단백질 패턴 P 가 있을때
            # 이 루프 안에서 현재까지 발견한 가장 큰 추가CP 값이 4인데,
            # 이번에 검사할 $combi의 이웃쌍의 갯수가 4라면,
            # 그 이웃쌍이 전부 1에 대응된다해도 어차피 추가CP값이 4이다.
            # 따라서 검사할 필요가 없고,
            # 루프를 더 이상 반복할 필요도 없다. (이웃쌍의 갯수가 점점 줄어들테니)
            if ( $max_add_cp >= @{$combi->{neighbor}} ) {
                last;
            }


            # combi 형태와 단백질 패턴을 대응해서 CP의 값을 구한다.
            # 예를들어 combi->{neighbor} 배열이 [ [ 1, 7 ], [ 2, 5 ] ] 라면
            # @strs의 1번과 7번 인덱스의 원소가 각각 1이라면 H-H이므로 add_cp 값이 1 증가
            # 2번과 5번 인덱스도 마찬가지
            foreach my $n ( @{$combi->{neighbor}} ) {
                if ( $strs[$n->[0]] and $strs[$n->[1]] ) {
                    $add_cp++;
                }
            }

            if ( $max_add_cp < $add_cp ) {
                $max_add_cp = $add_cp;
            }
        }

        # 앞에서 구한 cp (연속된 1에 의해서 생기는)
        # 방금 구한 max_add_cp (서로 떨어져 있는 1이 만나서 생기는)
        # 둘을 합친 것이 이 패턴 P의 최대 CP값이다.
        # 이 합친 값을 total_max_cp 에 더한다.
        $total_max_cp += $cp + $max_add_cp;
    }

    # 모든 패턴에 대해 검사가 끝났음. total_max_cp 값과, 평균값 출력
    print "total CP = $total_max_cp\n";
    print "# of patterns = ", 2**$length, "\n";
    print "average = ", $total_max_cp / (2**$length), "\n";
} #}}}

ver8();
exit;