Position 파이썬 코드 해설

이번 글에서는 Position 파이썬 코드를 해설하겠다.

Position 문제에 대해서는 다음 글을 참고하면 된다.

2023.07.03 - [리버싱] - Reversing.kr Position 문제 풀이

Reversing.kr Position 문제 풀이

---

전체 코드

import copy
import re

def make_dic():
    string = 'abcdefghijklmnopqrstuvwxyz'
    name_dic = {}

    for i in range(len(string)):
        for j in range(len(string)):
            si = string[i]
            sj = string[j]

            bi = format(ord(si), 'b').zfill(8)
            bj = format(ord(sj), 'b').zfill(8)

            name_dic[si+sj] = bi+bj

    return name_dic


def extract_sum_bits(serial_string):
    list_sum_bits = []
    for serial in serial_string:
        sum_bits = int(serial) - 6
        list_sum_bits.append(sum_bits)
    
    return list_sum_bits

def define_index(i):
    if i == 0:
       return 4, 2
    elif i == 1:
        return 1, 1
    elif i == 2:
        return 3, 0
    elif i == 3:
        return 2, 4
    else: # i == 4
        return 0, 3 

def make_default_re(sum_two_letter_list):
    re_list = [['.','.','.','.','.','.','.','.','.','.']]
    
    for i, value in enumerate(sum_two_letter_list):
        f_i, l_i = define_index(i)

        if value == 0:
            for re in re_list:
                re[f_i] = '0'
                re[l_i+5] = '0'
        elif value == 2:
            for re in re_list:
                re[f_i] = '1'
                re[l_i+5] = '1'
        else:
            re_list = aa(re_list, f_i, l_i)
    
    re_string_list = []
    for re in re_list:
        re_string_list.append(''.join(re))
    return re_string_list
            

def aa(re_list, f_i, l_i):
    new_list = []

    for re in re_list:
        first = copy.deepcopy(re)
        second = copy.deepcopy(re)

        first[f_i] = '0'
        first[l_i+5] = '1'

        second[f_i] = '1'
        second[l_i+5] = '0'

        new_list.append(first)
        new_list.append(second)

    return new_list

def polish_re(re_list):
    dotdotdot = '...'
    new_re_list = []
    for re in re_list:
        new_re_list.append(dotdotdot + re[0:5] + dotdotdot + re[5:])
    
    return new_re_list

def change_re_to_string(name_dict, re_list):
    string_list = []

    for pattern in re_list:
        
        regex = re.compile(pattern)
        string_list.append([key for key, value in name_dict.items() if regex.match(value)])

        # print(pattern, string_list)
    
    return string_list

def make_name(first_list, last_list):
    init_name_list = []
    for f in first_list:
        if f == []:
            continue
        for l in last_list:
            if l == []:
                continue
            init_name_list.append(f+l)

    final_name_list = []
    for name in init_name_list:
        if len(set(name)) != 4:
            continue
        final_name_list.append(name)
    
    return final_name_list


serial_number = '76876-77776'
name_dict = make_dic()

list_serial = serial_number.split('-')

first = list_serial[0]
last = list_serial[1]

sum_first_two_letter_list = extract_sum_bits(first)
sum_last_two_letter_list = extract_sum_bits(last)

# print(sum_first_two_letter_list)
# print(sum_last_two_letter_list)

first_re_list = polish_re(make_default_re(sum_first_two_letter_list))
last_re_list = polish_re(make_default_re(sum_last_two_letter_list))

# print(first_re_list)
# print(last_re_list)

first_name_list = change_re_to_string(name_dict, first_re_list)
last_name_list = change_re_to_string(name_dict, last_re_list)

# print(first_name_list)
# print(last_name_list)

print(make_name(sum(first_name_list, []), sum(last_name_list, [])))

---

코드 해설

먼저, 코드의 개요를 간략히 설명하겠다.

원래 Position 문제는 입력된 'name'을 통해서 'serial number'를 생성하게 된다.

그런데 문제에서는 오직 serial number만을 알려주고 있다.

 

즉, 시리얼 번호를 생성하는 과정을 거꾸로 따라가야 하는 것이다. (이하 디코드라고 표현하겠다)

시리얼 번호는 입력된 name을 두 글자씩 사용하여 앞 시리얼 번호와 뒤 시리얼 번호를 생성하게 된다.

시리얼 번호를 생성하는 방법에 있어서 앞과 뒤의 차이점은 없기 때문에,

하나의 디코드 함수로 앞과 뒤 둘 다에 적용할 수 있다.

 

main 함수의 흐름에 따라서 하나씩 살펴보자.

<main 코드>

serial_number = '76876-77776'
name_dict = make_dic()

list_serial = serial_number.split('-')

first = list_serial[0]
last = list_serial[1]

sum_first_two_letter_list = extract_sum_bits(first)
sum_last_two_letter_list = extract_sum_bits(last)

first_re_list = polish_re(make_default_re(sum_first_two_letter_list))
last_re_list = polish_re(make_default_re(sum_last_two_letter_list))

first_name_list = change_re_to_string(name_dict, first_re_list)
last_name_list = change_re_to_string(name_dict, last_re_list)

print(make_name(sum(first_name_list, []), sum(last_name_list, [])))

 

나는 먼저, name_dictionary를 만들었다.

시리얼 번호가 name 두 글자씩의 비트를 사용해서 만들어지기 때문에 패턴으로 매칭하고자 딕셔너리로 만들었다.

def make_dic():
    string = 'abcdefghijklmnopqrstuvwxyz'
    name_dic = {}

    for i in range(len(string)):
        for j in range(len(string)):
            si = string[i]
            sj = string[j]

            bi = format(ord(si), 'b').zfill(8)
            bj = format(ord(sj), 'b').zfill(8)

            name_dic[si+sj] = bi+bj

    return name_dic

'aa': '0110000101100001', 'ab': '0110000101100010', ...

이런 식으로 만들어지게 된다.

```

name의 값을 점검할 때, name의 값에 중복되는 값이 있으면 Wrong을 출력한다.

즉, aa, bb, cc 같이 중복되는 문자열은 굳이 사전에 필요하지 않다.

이 부분은 이 코드에서 구현하진 않았다.

```

 

이제 시리얼 번호를 가지고 name을 추측해 보자.

'-' 기호를 중심으로 다섯 글자씩 분리해서 디코딩할 것이다.

### main
# sum_first_two_letter_list = extract_sum_bits(first)
# sum_last_two_letter_list = extract_sum_bits(last)

### function
def extract_sum_bits(serial_string):
    list_sum_bits = []
    for serial in serial_string:
        sum_bits = int(serial) - 6
        list_sum_bits.append(sum_bits)
    
    return list_sum_bits

시리얼 번호는 최소 6, 최대 8의 값을 가지게 된다.

그래서 이 값의 범위를 0~2로 만들고 싶어서 위의 함수로 구현하였다.

 

### main
# first_re_list = polish_re(make_default_re(sum_first_two_letter_list))
# last_re_list = polish_re(make_default_re(sum_last_two_letter_list))

def make_default_re(sum_two_letter_list):
    re_list = [['.','.','.','.','.','.','.','.','.','.']]
    
    for i, value in enumerate(sum_two_letter_list):
        f_i, l_i = define_index(i)

        if value == 0:
            for re in re_list:
                re[f_i] = '0'
                re[l_i+5] = '0'
        elif value == 2:
            for re in re_list:
                re[f_i] = '1'
                re[l_i+5] = '1'
        else:
            re_list = aa(re_list, f_i, l_i)
    
    re_string_list = []
    for re in re_list:
        re_string_list.append(''.join(re))
    return re_string_list

정규표현식으로 딕셔너리의 value와 매칭할 것이기 때문에,

아까 만든 0~2 범위의 리스트를 정규표현식으로 바꿔줘야 한다.

앞 글자의 하위 5비트, 뒷 글자의 하위 5비트해서 총 10글자를 일단 '.'으로 만들어뒀다.

 

만약에 값이 0이라면,

    name 두 글자 모두 0으로.

만약에 값이 1이라면,

    name 한 글자는 0, 한 글자는 1로.

만약에 값이 2라면,

    name 두 글자 모두 1로.

바꿔준다.

 

여기서 귀찮은 부분은 값이 1일 때다.

첫 번째 글자가 0일 때, 두 번째 글자가 0일 때,

두 가지의 경우를 모두 생각해야 하기 때문이다.

 

그래서 아래의 함수로 구현하였다.

### in make_default_re()
# re_list = aa(re_list, f_i, l_i)

def aa(re_list, f_i, l_i):
    new_list = []

    for re in re_list:
        first = copy.deepcopy(re)
        second = copy.deepcopy(re)

        first[f_i] = '0'
        first[l_i+5] = '1'

        second[f_i] = '1'
        second[l_i+5] = '0'

        new_list.append(first)
        new_list.append(second)

    return new_list

두 가지의 경우를 모두 만들어주기 위해서,

현재까지 만들어진 리스트를 받아서 두 가지의 경우대로 만들어준다.

즉 리스트의 길이는 두 배가 된다. (원래 1개였으면 2개, 원래 2개였으면 4개, 원래 4개였으면 8개, ...)

```

이 코드에서 주의할 점은 리스트를 '=' 기호로 복사하는 것이다.

이러면 파이썬에선 같은 주소를 두 개의 포인터로 가리키는 모양이 된다.

완전히 독립되게 복사하기 위해서 이 코드에서는 copy.deepcopy()를 사용했다.

```

 

위 두 개의 코드에서 인덱스가 조금 특이한데, 아래의 함수의 리턴 값을 사용한다.

### in make_default_re()
# f_i, l_i = define_index(i)

def define_index(i):
    if i == 0:
       return 4, 2
    elif i == 1:
        return 1, 1
    elif i == 2:
        return 3, 0
    elif i == 3:
        return 2, 4
    else: # i == 4
        return 0, 3

시리얼 0번째를 만들기 위해서는 첫 번째 문자의 4번째 비트와 두 번째 문자의 2번째 비트가 사용된다.

시리얼 1번째를 만들기 위해서는 첫 번째 문자의 1번째 비트와 두 번째 문자의 1번째 비트가 사용된다.

(각 문자의 하위 5비트 중에서)

이런 식으로 인덱스가 복잡하기 때문에 저 함수를 사용해서 시리얼 인덱스에 따라 어떤 인덱스를 사용할지 정해준 것이다.

 

### main
# first_re_list = polish_re(make_default_re(sum_first_two_letter_list))
# last_re_list = polish_re(make_default_re(sum_last_two_letter_list))

def polish_re(re_list):
    dotdotdot = '...'
    new_re_list = []
    for re in re_list:
        new_re_list.append(dotdotdot + re[0:5] + dotdotdot + re[5:])
    
    return new_re_list

이 함수는 현재는 총 10자리로 되어있는 리스트를(첫 번째 문자의 하위 5비트 + 두 번째 문자의 하위 5비트)

총 16자리로 만들어주는 함수이다.

하위 5바이트만이 시리얼 번호를 만드는데 관여하고 상위 3바이트는 관여하지 않기 때문에,

0과 1 아무 값이나 상관없다.

그래서 ...으로 세팅해 준다.

```

추후 결과를 살펴보니

name의 값이 a-z로 한정되어 있기 때문에

상위 3비트의 값도 바뀌지 않는 것 같다.

만일, 정규표현식으로 a-z 범위의 값만을 찾도록 범위를 좁히고 싶다면,

...이 아니라 소문자 알파벳의 고정된 상위 3비트의 값으로 하면 될 것 같다.

```

 

### main
# first_name_list = change_re_to_string(name_dict, first_re_list)
# last_name_list = change_re_to_string(name_dict, last_re_list)

def change_re_to_string(name_dict, re_list):
    string_list = []

    for pattern in re_list:
        
        regex = re.compile(pattern)
        string_list.append([key for key, value in name_dict.items() if regex.match(value)])

        # print(pattern, string_list)
    
    return string_list

이 함수는 이제 만들어진 정규표현식 패턴을 가지고서 name_dictionary에서 찾는 함수이다.

```

현재 코드에서는 하나의 정규표현식에 대해서 dictionary의 모든 아이템을 둘러보도록 구현되어 있다.

하지만 결과를 살펴보니, a-z까지의 범위에서 하위 5비트의 값은 각 알파벳마다 unique 한 것 같다.

따라서 하나를 찾으면 더 이상 반복하지 않도록 하면, 프로그램의 효율이 더 높아질 것 같다.

```

 

### main
# print(make_name(sum(first_name_list, []), sum(last_name_list, [])))

def make_name(first_list, last_list):
    init_name_list = []
    for f in first_list:
        if f == []:
            continue
        for l in last_list:
            if l == []:
                continue
            init_name_list.append(f+l)

    final_name_list = []
    for name in init_name_list:
        if len(set(name)) != 4:
            continue
        final_name_list.append(name)
    
    return final_name_list

앞 두 글자와 뒤 두 글자 후보들을 다 찾았으니,

가능한 모든 경우의 네 글자를 조합해 주는 함수이다.

name에서 겹치는 문자열은 없어야 하므로, set 함수를 사용했을 때 문자열의 길이가 4와 같지 않으면 제외하도록 했다.

```

함수를 호출할 때 sum(list, [])로 넣어주는 이유는,

현재 리스트가 2차원 배열로 되어있기 때문이다.

1차원 배열로 만들어서 반복하기에 더 용이하게 만들었다.

```