Day_7_Recursive_Circus

Day 7: Recursive Circus

Part 1

Translation

컴퓨터의 회로를 돌아다니다, 문제가 생긴 프로그램들의 탑에 다다른다. 재귀 알고리즘이 통제할 수 없는 상황에 놓였고, 큰 탑 안에 불안하게 균형을 잡고 있다.

바닥에 있는 한 프로그램이 탑 전체를 지지한다. 이는 큰 디스크를 잡고 있고, 이 디스크 위에 종속된 탑들이 균형을 잡고 있다. 이 종속된 탑들의 바닥에, 바닥 디스크에 서 있는 다른 프로그램들은, 각각 그들의 디스크를 붙잡고 있다. 이러한 종속-종속-...종속된 탑들의 맨 위에, 많은 프로그램들이 그들만의 디스크는 아니지만 그들 밑에 균형을 잡으며 디스크를 두고 서있다.

도움을 제공하나, 이 탑들의 구조를 이해해야 한다. 각 프로그램에게 각자의 이름, 무게, (만약 디스크를 잡고 있다면) 디스크 위에서 균형을 잡고 있는 프로그램들의 이름을 외치도록 한다. 당신은 이 정보를 적는다. 운이 없게도, 그들은 순서대로 말하지 않는다; 정보들을 다 받아 적었을 때, 어떤 프로그램이 어떤 정보를 줬는지 확실하지 않다.

예를 들어, 목록이 다음과 같다:

pbga (66)
xhth (57)
ebii (61)
havc (66)
ktlj (57)
fwft (72) -> ktlj, cntj, xhth
qoyq (66)
padx (45) -> pbga, havc, qoyq
tknk (41) -> ugml, padx, fwft
jptl (61)
ugml (68) -> gyxo, ebii, jptl
gyxo (61)
cntj (57)

... 이 때 다음과 같이 보이도록 탑들의 구조를 다시 만들 수 있어야 한다:

                gyxo
              /     
         ugml - ebii
       /      \     
      |         jptl
      |        
      |         pbga
     /        /
tknk --- padx - havc
     \        \
      |         qoyq
      |             
      |         ktlj
       \      /     
         fwft - cntj
              \     
                xhth

이 예제에서, tknk는 탑의 바닥에 있고 (바닥 프로그램), 이는 ugml, padx, 그리고 fwft를 들고 있다. 이 프로그램들은, 다른 프로그램들은 들고 있다; 이 예제에서는, 또다른 프로그램들을 들고 있는 프로그램은 없고, 각자 탑들의 꼭대기에 있다. (앞의 실제 탑은 훨씬 크다.)

그들을 돕기 전에, 정보가 맞는지 확실히 해야 한다. 바닥 프로그램의 이름은 무엇인가?

Solution

• 입력 : 각 프로그램의 이름과 무게, 이를 받치는 프로그램들의 이름
• 처리 : anytree 파이썬 모듈을 활용하여 트리로 그렸다.
• 출력 : 탑을 트리로 나타낸 결과.
• source

Part 2

Translation

프로그램들이 상황을 설명한다: 그들은 가라앉을 수 없다. 아니면, 탑의 균형을 유지하는 힘을 낼 수 없다면 가라앉을 수 있다. 명백하게, 하나의 프로그램이 잘못된 무게를 가지고, 이를 고치기 전까지, 이 상황을 빠져나가지 못한다.

디스크를 들고 있는 프로그램들이라면, 디스크에 서있는 각 프로그램은 종속-타워를 형성한다. 이러한 종속 타워들은 각각 똑같은 무게이고, 그렇지 않다면 균형이 맞지 않는다. 탑의 무게는 탑에 있는 프로그램들의 무게의 합이다.

위 예시에서, ugml의 균형이 맞으려면, gyxo, ebii, 그리고 jptl이 모두 같은 무게를 가지고 있어야 한다. 61.

그러나, tknk의 균형이 맞으려면, 디스크에 서있는 각 프로그램들과 그 위의 모든 프로그램들의 서로 일치해야 한다. 이는 다음과 같아야 한다:

• ugml + (gyxo + ebii + jptl) = 68 + (61 + 61 + 61) = 251
• padx + (pbga + havc + qoyq) = 45 + (66 + 66 + 66) = 243
• ugml + (gyxo + ebii + jptl) = 72 + (57 + 57 + 57) = 243

보다시피, tknk의 디스크는 불균형이다: ugml의 스택이 다른 둘보다 더 무겁다. ugml 위의 노드들은 균형일지라도, ugml 자체가 너무 무겁다: 243의 무게가 되어 탑의 균형을 맞추려면 8은 더 가벼워야 한다. 이렇게 된다면, ugml의 무게는 60이 된다.

정확히 하나의 프로그램의 무게가 잘못된 것이라고 할 때, 탑 전체의 균형을 맞추기 위해 얼만큼의 무게를 신경써야 하는가?

Solution

• 입력 : 각 프로그램의 이름과 무게, 이를 받치는 프로그램들의 이름
• 처리 : Part 1의 솔루션에 종속-타워의 무게의 합을 구하는 재귀 함수를 이용하여 무게가 잘못된 하나의 프로그램을 찾는다. 이를 매끄럽게 정답만 출력하려면 좀더 솔루션을 다듬어야 할 것이다...
• 출력 : 여러 타워들의 무게들. 이 중 무게가 잘못된 하나의 프로그램을 찾은 뒤 올바르게 수정한 무게가 정답이다.
• source