2017年AoC日24 :电磁护城河
今年的AoC有一个第24天的谜题，这个谜题(据说)是用递归来解决的。
以下是描述：
--第24天:电磁护城河-- CPU本身就是一座巨大的黑色建筑，周围环绕着一个无底洞。巨大的金属管从建筑物的侧面向外延伸，每隔一段时间下降到空隙中。没有办法过关，但你得进去。当然，除了用散落在附近的磁性元件建造一座桥外，没有别的办法。每个组件有两个端口，每个端口都有一个端口。端口有各种不同的类型，只有匹配的类型才能连接。根据组件的端口类型(您的拼图输入)对组件进行清点。每个端口都是由它使用的引脚数来标识的；更多的引脚意味着您的桥接器的连接更加牢固。例如，3/7组件的一侧有类型-3端口，另一侧有类型-7端口。你的凹坑是金属的，一个完美的表面连接一个磁性的零引脚端口。因此，您使用的第一个端口必须是0类型。不管你用哪种类型的端口结束，你的目标只是使桥尽可能坚固。桥的强度是每个组件中端口类型的总和。例如，如果桥由0/3、3/7和7/4组件组成，则桥的强度为0+3 + 3+7 + 7+4 = 24。例如，假设您有以下组件: 0/2 2/2 2/ 3 /4 3/5 0/1 10/1 9/10你可以建立下列有效的桥梁: 0/1 0/1--10/1 -9/10 0/2 -2/3 0/2-2/3/2-3/2/2-3/3-3/5/2-2/2/2/2-2/2/2-2/2/3/2-2/2/2-2/3/3/2-2/2/3-3/3/5如10/1所示，组件中端口的顺序并不重要。但是，您可以只使用组件上的每个端口一次。)在这些桥中，最强的是0/1-10/1-9/10，强度为0+1 + 1+10 + 10+9 = 31。你能用可用的组件制造出最强大的桥梁的强度是多少？
我通过简单的直接递归来解决这个问题：
var temp = File.ReadAllLines(@"N:\input.txt").Select(x => (int.Parse(x.Split('/').First()), int.Parse(x.Split('/').Last()))).ToList();
var workChain = new HashSet<(int, int)>();
var map = new Dictionary<(int, int), List<(int, int)>>(temp.Count);
foreach (var entry in temp)
{
map.Add(entry, nextStack(entry));
}
int maxStr = 0, maxLen = 0, lenStr = 0;
temp.Clear();
temp.AddRange(map.Keys.Where(x => isRoot(x)));
foreach (var root in temp)
{
workChain.Clear(); nextPiece(root, 0);
}
Console.WriteLine($"{maxStr} {lenStr}");
//helpers
bool isRoot(ValueTuple<int, int> node) { return node.Item1 == 0 || node.Item2 == 0; }
int chainSum(HashSet<(int, int)> curChain) // still faster than LINQ
{
int sum = 0;
foreach (var piece in curChain)
{
sum = sum + (piece.Item1 + piece.Item2);
}
return sum; }
int stackable(ValueTuple<int, int> cur, ValueTuple<int, int> tar, int p)
{
if (commonPort(cur, tar) == p && cur.Item1 == cur.Item2 && cur.Item1 == p) { return p; }
if ((cur.Item1 == tar.Item1 || cur.Item1 == tar.Item2) && cur.Item1 != p) { return cur.Item1; }
if ((cur.Item2 == tar.Item1 || cur.Item2 == tar.Item2) && cur.Item2 != p) { return cur.Item2; }
return -1;
}
int commonPort(ValueTuple<int, int> current, ValueTuple<int, int> target)
{
if (current.Item1 == target.Item1 || current.Item1 == target.Item2) { return current.Item1; }
else if (current.Item2 == target.Item1 || current.Item2 == target.Item2) { return current.Item2; }
else { return -1; }
}
ValueTuple<int, int> nextPiece(ValueTuple<int, int> selected, int p)
{
var x = (-1, -1);
workChain.Add(selected);
foreach (var piece in map[selected])
{
if (!selected.Equals(piece) && stackable(selected, piece, p) != -1 && !isRoot(piece) && !workChain.Contains(piece))
{
x = nextPiece(piece, stackable(selected, piece, p));
if (x.Equals((-1, -1)))
{
int str = chainSum(workChain), len = workChain.Count;
maxStr = str > maxStr ? str : maxStr;
if (len > maxLen)
{
maxLen = len;
lenStr = str;
}
else if (len == maxLen && str > lenStr)
{
lenStr = str;
}
workChain.Remove(piece);
}
}
}
return x;
}
List<(int, int)> nextStack(ValueTuple<int, int> selected)
{
workChain.Clear();
for (int i = 0; i < temp.Count; i++)
if (!selected.Equals(temp[i]) && commonPort(selected, temp[i]) != -1 && !isRoot(temp[i]))
workChain.Add(temp[i]);
return new List<(int, int)>(workChain);
}我讨厌它，它是丑陋的地狱，我觉得应该有一些更简单和更优雅的没有明确/直接的递归。虽然我听说Python用户使用迭代生成器，但我觉得Visitor或Composite可能是更好的解决方案。
有什么想法吗？
回答 1
Code Review用户
发布于 2019-09-04 21:59:47
可读性
我将把这篇评论的重点放在以下声明上：
我讨厌它，它像地狱一样丑陋，我觉得那里应该更简单、更优雅。
然后，您将建议一些面向对象(访问者、复合)和功能(生成器)模式作为提高可读性的方法。我确实会让代码更多地遵循OO原则。
关注点分离
重构功能代码的第一阶段是定义关注点。您有：(1)输入解析(2)计算器(3)输出呈现。通过提供单独的类，但明确地分离方法，确保将这些关注点分开，每种方法都专注于它们的关注点。
面向对象设计
您选择了Dictionary<(int, int), List<(int, int)>>作为计算器的状态。ValueTuple实例可以很好地替代将某些属性组合在一起的锅炉板类。然而，当你需要重新出现的行为，他们不是最好的选择。看看一些令人费解的陈述：
片段1：
如果(commonPort(cur，tar) == p& cur.Item1 == cur.Item2 && if；cur.Item1 == p) {返回p；} if ((cur.Item1 == tar.Item1连体cur.Item1 == tar.Item2) && cur.Item1 != p) {cur cur.Item1；} if ((cur.Item2 == cur.Item1)#)& != p) {返回}返回-1；
片段2：
if (current.Item1 == target.Item1 if current.Item1 == target.Item2) {返回current.Item1；} else if (current.Item2 == target.Item1而经current.Item2 == target.Item2) {返回current.Item2；} else {返回-1；}
这是没有提供自定义类的直接后果。您正在使用的(int, int)元组表示拼图中的Component。我们来上一堂课吧。
class Component : IEnumerable<int>
{
public int Port1 { get; }
public int Port2 { get; }
public Component(int port1, int port2) => (Port1, Port2) = (port1, port2);
// methods ..
public IEnumerator<int> GetEnumerator()
{
yield return Port1;
yield return Port2;
}
IEnumerator IEnumerable.GetEnumerator()
{
return this.GetEnumerator();
}
}然后，获取公共端口可以是这个类中的一个方法。
public int? GetCommonPort(Component other) => this.Intersect(other).FirstOrDefault();您甚至可以决定创建一个类Port来存储一些可能对将组件连接在一起有用的附加信息。只有断开连接的端口才能连接到另一个组件的断开端口。需要这些信息来决定哪些组件和它们的端口可以连接。
class Port
{
public int PortNumber { get; }
public bool IsConnected { get; internal set; }
public Port(int portNumber) => PortNumber = portNumber;
}我可以想象的另一个类是Bridge，因为它是一个组件链。
class Bridge
{
Component First { get; private set; }
Component Last { get; private set; }
public void Construct(Component next)
{
Last.Connect(next);
Last = next;
}
// and so on ..
}这应该让您很好地了解如何使用面向对象的方法重写算法。试试吧..。
https://codereview.stackexchange.com/questions/183976
复制相似问题
腾讯云开发者
