[Programmers] numerical baseball.py (complete search)

 #. Problem

https://programmers.co.kr/learn/courses/30/lessons/42841

* The copyright in this matter is in Programmers

숫자 야구 게임이란 2명이 서로가 생각한 숫자를 맞추는 게임입니다.

각자 서로 다른 1~9까지 3자리 임의의 숫자를 정한 뒤 서로에게 3자리의 숫자를 불러서 결과를 확인합니다. 

그리고 그 결과를 토대로 상대가 정한 숫자를 예상한 뒤 맞힙니다.

* 숫자는 맞지만, 위치가 틀렸을 때는 볼

* 숫자와 위치가 모두 맞을 때는 스트라이크

* 숫자와 위치가 모두 틀렸을 때는 아웃

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

  1. 볼, 스타라이크, 아웃을 어떻게 계산할지 먼저 구상이 필요할 듯 하다.

    * 숫자는 맞지만, 위치가 틀렸을 때는 볼

* 숫자와 위치가 모두 맞을 때는 스트라이크

     중복을 제거한 1~9로 만들어질 수 있는 모든 3자리 수를 준비한다. 

     -> 중복을 제외한 완전탐색 문제이므로 set자료형과 permutations함수를 사용하면 될 것 같다.

         "각자 서로 다른 1~9까지 3자리 임의의 숫자를 정한 뒤" 라고 했으니 중복을 제거할 필요는 없다. permutations함수 사용

  2. baseball list에 저장된 값들을 하나씩 꺼내어, 

     먼저 스트라이크의 수를 계산한다. 경우의 수들과 각 자리의 수를 비교하여 strike가 몇 개인지 계산

     그 후, 주어진 strike 수와 일치하는지 비교하고 일치하지 않으면 해당 수를 제거,

     다음 ball의 개수를 구해야 함.

     주어진 수와 경우의 수를 교집합한 list의 크기에서 strike 수를 빼주면 ball을 구할 수 있음

     그 후, 주어진 ball 수와 일치하는지 비교하고 일치하지 않으면 해당 수를 제거

  3. 주어진 수를 모두 비교하고 list에 저장된 값의 개수를 return

#. Code

from itertools import permutations
def solution(baseball):
    # Preparation of the number of cases
    num_list = list(permutations(range(1,10), 3))
 
    while baseball:
        game, s, b = baseball.pop()
        game = list(map(int, list(str(game))))
        for n in num_list[:]:
            strike = 0
            # Comparison of strikes
            for i in range(len(game)):
                if game[i] == n[i]:
                    strike += 1
            if strike != s:
                num_list.remove(n)
            else: # Comparison of ball
                ball = len(set(game) & set(n)) - strike
                if ball != b:
                    num_list.remove(n)
    return len(num_list)

  - (4) 1~9까지의 수로 만들 수 있는 3자리 수를 permutations 함수로 구해준다.

    (7~8) baseball list에서 한 요소씩 뽑아서 game, strike, ball 변수에 각 값을 저장해주고

           game은 123과 같이 정수로 되어있으므로 [1, 2, 3]으로의 변환이 필요하다.

    (9~) 경우의 수들(num_list)과 baseball에 있는 세 자릿수 game과 비교를 해야한다.

    (12~14) 경우의 수들과 baseball의 세 자릿수의 각 자리수를 비교하여 같으면 strike += 1

    (15~16) strike 수가 주어진 strike 수와 다르다면 해당 수를 list에서 삭제

    (17~20) strike 수가 같다면, ball 수를 비교해보아야 한다.

              ball의 개수는 game(baseball에 있는 세 자릿수)과 n(경우의 수)의 교집합(숫자는 맞지만, 위치가 틀릴 경우)에서

              strike를 빼주면 구할 수 있다. 여기서도 마찬가지로 주어진 ball과 다를 경우 해당 수를 list에서 삭제

    (21) list 남은 수들의 개수를 return 

    * 처음에 line 9에서 for n in num_list: 이렇게 했었는데, 결과가 계속 46이 나와서 왜 그런가 봤더니

      위와 같이 할 경우 num_list의 원본(?)을 for문에 사용하게 된다. 그렇기 때문에 다음 baseball이 작동할 때

      초기 num_list로 다시 for문이 동작해서 remove했던 수들이 다시 사용되버리게 된다.

      결과적으로! for n in num_list[:]로 얇은 복사를 사용하여 num_list를 동작시키면 내부의 객체는 서로 영향을 받기 때문에

      원하는 결과를 얻을 수 있게 된다.