SEND + MORE = MONEY를 순열로 푸는 과정

send more money 의 각 글자에 0~9를 하나씩 배정해서 send + more = money 가 성립하게 만드는 문제다. 서로 다른 글자에는 서로 다른 숫자가 들어가야 한다.

글자는 s, e, n, d, m, o, r, y 여덟 개다. 10개 중 8개를 순서 있게 뽑는 것이므로 10P8이다.

첫 시도

def mask(i, x=''):
    if len(x) == len(nooverlap):
        t = dict(zip(nooverlap, x))
        print(t)
        return

    for j in range(i, 10):
        mask(i + 1, x + n[j])

nooverlap = set(''.join(li))
n = [str(i) for i in range(10)]
mask(0)

range(i, 10) 으로 시작점을 올려가며 뽑으면 중복이 안 생길 거라고 생각했다. 그런데 다음 호출에 넘기는 게 j + 1 이 아니라 i + 1 이다. 어느 것을 골랐든 다음 단계의 시작점은 깊이에 따라서만 정해진다.

같은 숫자를 다시 고를 수 있고, 뽑는 순서도 제대로 통제되지 않는다. 배정 문제에서 필요한 건 조합이 아니라 순열이라는 것도 이때 정리가 안 되어 있었다.

자리를 맞바꾸는 방식

def mask(i, x=[]):
    if len(x) == n:
        ...
        return

    for j in range(i, 10):
        p[i], p[j] = p[j], p[i]
        mask(i + 1, x + [p[i]])
        p[i], p[j] = p[j], p[i]

p = [i for i in range(10)]
mask(0)

0~9를 담은 배열에서 i 번째 자리에 i 이후의 값을 하나 끌어와 놓는다. 앞에서 확정한 것은 range(i, 10) 밖으로 밀려나므로 다시 뽑히지 않는다. 중복 검사가 필요 없어진다.

여덟 자리가 차면 멈추므로 10개를 다 쓰지 않아도 된다. 남은 두 숫자는 그냥 안 쓰인 채로 끝난다.

세 번째 방식

같은 notebook에 후보 목록에서 꺼내는 방식도 있다.

def all(pl, x=[]):
    if len(x) == n:
        print(x)
        return

    for i in range(len(pl)):
        t = pl + []
        v = t.pop(i)
        all(t, x + [v])

고른 것을 빼낸 목록을 새로 만들어 넘긴다. 읽기는 이쪽이 제일 쉬운데 매 단계마다 리스트를 복사한다. swap 방식은 배열 하나를 계속 쓴다.

검사

숫자를 배정했으면 식이 맞는지 봐야 한다. 글자를 숫자로 치환하고 나서 계산한다.

new = pro
for i, v in enumerate(s):
    new = new.replace(v, str(x[i]))
new = new.split()

if sum(int(i) for i in new[:-1]) == int(new[-1]):
    print(new)

s 는 글자를 정렬해둔 리스트다. sorted 를 씌운 건 set 의 순서가 실행마다 달라질 수 있어서다. 배정 순서가 고정되어야 결과를 비교할 수 있다.

공백으로 나눈 뒤 마지막을 빼고 다 더해서 마지막과 비교한다. send more money 라는 형태에 맞춰 쓴 거라 항 개수가 늘어나도 그대로 돌아간다.

eval 을 쓰지 않고 문자열 치환과 int 로만 처리했다. 자릿수 계산은 int 가 알아서 한다.

첫 글자가 0이 되는 경우는 걸러내지 않았다. s 나 m 에 0이 들어가는 답도 그대로 통과한다.