"""
출처:프로그래머스
https://school.programmers.co.kr/learn/courses/30/lessons/42895
"""

# 풀이 과정
from collections import defaultdict

def solution(N, number):
    if N == number:
        return 1

    num = defaultdict(set)
    num[1].add(N)

    for i in range(2, 9):
        num[i].add(int(str(N) * i))
        for j in range(i):
            for a in num[j]:
                for b in num[i - j]:
                    num[i].add(a + b)
                    num[i].add(a - b)
                    num[i].add(a * b)
                    if b != 0:
                        num[i].add(a // b)

        if number in num[i]:
            return i

    return -1

#-------------------------------------------- 개선 전 오답 과정 ----------------------------------------------------#
from itertools import product
from collections import deque


def solution(N, number):
    cal = ["", "+", "//", "*", "-"]

    if N == number:
        return 1

    count = 2

    while True:
        start = str(N) * count

        start = list(start)

        cal_set = deque(list(product(cal, repeat=count - 1)))

        min_check = []

        while cal_set:
            num = str(N)
            check = cal_set.popleft()

            for c in range(len(check)):
                num += check[c]
                num += start[c]

            #                 num=deque(list(num))

            #                 while num[0]=="0" or num[0]=="+" or num[0]=="/" or num[0]=="*":
            #                     num.popleft()

            #                 num=str(eval("".join(num)))

            num = eval(num)

            if int(num) == number:
                return count

        count += 1

        if count > 8:
            return -1

    return -1