Advent of Code Day 7 遞歸馬戲團

解題語言不限Java

題目內(nèi)容

Wandering further through the circuits of the computer, you come upon a tower of programs that have gotten themselves into a bit of trouble. A recursive algorithm has gotten out of hand, and now they're balanced precariously in a large tower.

沿著電路板向前走遠，你來到了一個出來問題的程序塔孤澎。一個遞歸程序出錯峦失，現(xiàn)在他們需要平衡整個程序塔。

One program at the bottom supports the entire tower. It's holding a large disc, and on the disc are balanced several more sub-towers. At the bottom of these sub-towers, standing on the bottom disc, are other programs, each holding their own disc, and so on. At the very tops of these sub-sub-sub-...-towers, many programs stand simply keeping the disc below them balanced but with no disc of their own.

一個程序在底部支撐整個塔杜跷，它會保持一個大盤，在這個大盤上會有幾個小塔。其他的程序立在這個大盤中小塔的底部溢谤，保持著一個盤子斩松，如此如此伶唯。在這些分塔的分塔的分塔……的最頂上，很多程序立在盤上惧盹，保持底下的盤子平衡乳幸。

You offer to help, but first you need to understand the structure of these towers. You ask each program to yell out their name, their weight, and (if they're holding a disc) the names of the programs immediately above them balancing on that disc. You write this information down (your puzzle input). Unfortunately, in their panic, they don't do this in an orderly fashion; by the time you're done, you're not sure which program gave which information.

你答應(yīng)去幫忙，但是最開始你要知道這些塔的結(jié)構(gòu)钧椰。你讓每個程序喊出他們的名字粹断，質(zhì)量，和他們支持的盤子上的程序嫡霞。不幸的是瓶埋，他們沒有按照順序回答，當你完成之后诊沪，你不知道是哪個程序給出的信息养筒。

For example, if your list is the following:

比如，你列出了這些：

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)

...then you would be able to recreate the structure of the towers that looks like this:
然后你可以整理出這個塔的結(jié)構(gòu):

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

In this example, tknk is at the bottom of the tower (the bottom program), and is holding up ugml, padx, and fwft. Those programs are, in turn, holding up other programs; in this example, none of those programs are holding up any other programs, and are all the tops of their own towers. (The actual tower balancing in front of you is much larger.)
在這個例子里娄徊，tknk是在最下面的程序闽颇，同時它支持著ugml, padx, 和fwft。這些程序寄锐，反過來支持著其他的程序兵多。在最上面的程序，沒有支持著任何程序橄仆。（其實你會拿到更大的塔）
Before you're ready to help them, you need to make sure your information is correct. What is the name of the bottom program?
在你幫助他們之前剩膘，你需要去確定你的信息是正確的，那么在整個塔的最底部的程序叫什么盆顾？

解題思路

其實用搜索就可以很快找到……

首先怠褐，分析過例子可以知道，輸入有兩種您宪，節(jié)點（node）和終點（End）奈懒。我制作了一個遞歸程序來搜索所有節(jié)點的子節(jié)點奠涌，并且計算節(jié)點和。節(jié)點和是將所有終點設(shè)為1磷杏，每個節(jié)點等于子節(jié)點值的和溜畅。在上圖的例子里tknk 值為九個終點的和，所以值為9极祸。跑完之后找最大值慈格，就是根節(jié)點。

最后編輯于：2017.12.13 02:22:13

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者