缘起
话说昨日(2012-11-08)刚好在微博上看到老师发了一条解谜题送《思考的乐趣:Matrix67数学笔记》的微博。
题面
“迷宫”题:从图左边入口处的2011进去,在迷宫里转悠,最后变成2012从右边出来。可以在迷宫里转圈,可以重复之前走过的路,但不能回退。
基本思路
一开始想直接手工推导出结果,长话短说,正向、反向试验几次后发现,通常推导到六七步后会遇到分支,继续往下推就比较头大了。
虽然手工推导无果而终,但是此过程加深了对谜题的理解,对于之后的程序设计可谓大有裨益。
至此,俺决定Coding一下,思路就是把手工推导的步骤程序化,把头大的推导过程丢给CPU去处理 :D
在讲解程序设计思路前,先看下程序运行结果:
Current Depth: 27
Expression Path: 2011+7>2018÷2>1009+7>1016÷2>508+7>515-5>510×3>1530÷2>765+7>772÷2>386+7>393×3>1179-5>1174÷2>587+7>594÷2>297+7>304-5>299×3>897-5>892×3>2676÷2>1338+7>1345-5>1340×3>4020÷2>2010+7>2017-5>2012
虽然结果是从入口到出口一条直线,不过从手工推导经验可知,中间还会出现一些分支。——想到了什么?——无论别人想到了啥,反正俺是想到了树(Tree)。
因此谜题转换为:动态构建一课可计算节点树,当特定节点计算结果值为“2012”时停止构建(为什么又是2012呢,怕怕),获取返回从根节点到终止节点的全路径,然后简单输出即可。
节点的计算规则很简单,无须多言。不过,要特别注意的一点是,图中每个可计算节点都有两个前进方向(顺时针方向或逆时针方向),而前进方向的不同会直接导致其子节点发生变化。
把这些问题想清楚后,就可以写个递归让CPU慢慢算去了。
还要补充一点,俺的写法是深度优先,因此需恰当设置最大深度值(MaxDepth
),不能太大(30就行了),太大会导致内存溢出哦(俺的机器刚50就溢了,呜呜,不信你设成100试试哈)。
完整的C#代码如下:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace ConApp
{
class Program
{
static void Main(string[] args)
{
CommonComputeNode exitNode = PuzzleFrame.TryCompute(PuzzleFrame.GetOrigin());
if (exitNode != null)
{
Console.WriteLine("Current Depth: {0}", exitNode.Depth);
List<CommonComputeNode> path = exitNode.GetPath();
List<string> expressionList = path.Select<CommonComputeNode, string>(node => node.Expression).ToList();
string expressionPathString = string.Join(">", expressionList.ToArray());
Console.WriteLine("Expression Path: {0}>{1}", expressionPathString, PuzzleFrame.DesiredValue);
}
else
{
Console.WriteLine("Not found within depth {0}.", PuzzleFrame.MaxDepth);
}
Console.Read();
}
}
#region PuzzleGame.
internal static class PuzzleFrame
{
internal static int OriginalValue = 2011;
internal static int DesiredValue = 2012;
internal static int MaxDepth = 30;
internal static CommonComputeNode GetOrigin()
{
return ComputeNodeFactory.GetPlus7(OriginalValue, ClockRotationDirection.Clockwise);
}
internal static CommonComputeNode TryCompute(CommonComputeNode node)
{
if (!node.CanCompute
|| HasExceededMaxDepath(node.Depth))
return null;
node.Compute();
if (node.CanGameOver())
return node;
CommonComputeNode returnNode = null;
node.AppendChildNodes();
foreach (CommonComputeNode childNode in node.ChildNodes)
{
returnNode = TryCompute(childNode);
if (returnNode != null)
break;
}
return returnNode;
}
private static bool HasExceededMaxDepath(int nodeDepth)
{
return nodeDepth > MaxDepth;
}
private static bool CanGameOver(this CommonComputeNode node)
{
return DesiredValue.Equals(node.Result) && IsExitNode(node);
}
private static bool IsExitNode(CommonComputeNode node)
{
return IsClockwiseMultipliedBy3(node) || IsCounterclockwiseMinus5(node);
}
private static bool IsCounterclockwiseMinus5(CommonComputeNode node)
{
return (node.OperatorWithRightOperandSign.Equals("-5") && node.RotationDirection.Equals(ClockRotationDirection.Counterclockwise));
}
private static bool IsClockwiseMultipliedBy3(CommonComputeNode node)
{
return (node.OperatorWithRightOperandSign.Equals("×3") && node.RotationDirection.Equals(ClockRotationDirection.Clockwise));
}
}
internal static class ComputeNodeFactory
{
internal static CommonComputeNode GetPlus7(int inputValue, ClockRotationDirection direction)
{
return new Plus7(inputValue, direction);
}
internal static void AppendChildNodes(this CommonComputeNode node)
{
switch (node.OperatorWithRightOperandSign)
{
case "+7":
AppendPlus7ChildNodes(node);
break;
case "÷2":
AppendDividedBy2ChildNodes(node);
break;
case "×3":
AppendMultipliedBy3ChildNodes(node);
break;
case "-5":
AppendMinus5ChildNodes(node);
break;
}
}
private static void AppendMinus5ChildNodes(CommonComputeNode node)
{
switch (node.RotationDirection)
{
case ClockRotationDirection.Clockwise:
node.AddChildNode(new MultipliedBy3(node.Result.Value, ClockRotationDirection.Clockwise))
.AddChildNode(new DividedBy2(node.Result.Value, ClockRotationDirection.Clockwise))
.AddChildNode(new Plus7(node.Result.Value, ClockRotationDirection.Counterclockwise));
break;
case ClockRotationDirection.Counterclockwise:
node.AddChildNode(new MultipliedBy3(node.Result.Value, ClockRotationDirection.Counterclockwise));
break;
}
}
private static void AppendMultipliedBy3ChildNodes(CommonComputeNode node)
{
switch (node.RotationDirection)
{
case ClockRotationDirection.Clockwise:
node.AddChildNode(new Minus5(node.Result.Value, ClockRotationDirection.Clockwise));
break;
case ClockRotationDirection.Counterclockwise:
node.AddChildNode(new Minus5(node.Result.Value, ClockRotationDirection.Counterclockwise))
.AddChildNode(new Plus7(node.Result.Value, ClockRotationDirection.Counterclockwise))
.AddChildNode(new DividedBy2(node.Result.Value, ClockRotationDirection.Clockwise));
break;
}
}
private static void AppendDividedBy2ChildNodes(CommonComputeNode node)
{
switch (node.RotationDirection)
{
case ClockRotationDirection.Clockwise:
node.AddChildNode(new Plus7(node.Result.Value, ClockRotationDirection.Clockwise));
break;
case ClockRotationDirection.Counterclockwise:
node.AddChildNode(new Plus7(node.Result.Value, ClockRotationDirection.Counterclockwise))
.AddChildNode(new Minus5(node.Result.Value, ClockRotationDirection.Counterclockwise))
.AddChildNode(new MultipliedBy3(node.Result.Value, ClockRotationDirection.Clockwise));
break;
}
}
private static void AppendPlus7ChildNodes(CommonComputeNode node)
{
switch (node.RotationDirection)
{
case ClockRotationDirection.Clockwise:
node.AddChildNode(new DividedBy2(node.Result.Value, ClockRotationDirection.Clockwise))
.AddChildNode(new MultipliedBy3(node.Result.Value, ClockRotationDirection.Clockwise))
.AddChildNode(new Minus5(node.Result.Value, ClockRotationDirection.Counterclockwise));
break;
case ClockRotationDirection.Counterclockwise:
node.AddChildNode(new DividedBy2(node.Result.Value, ClockRotationDirection.Counterclockwise));
break;
}
}
}
public abstract class CommonComputeNode
{
public abstract string OperatorWithRightOperandSign { get; }
public abstract int Compute();
public int LeftOperand { get; private set; }
public int Depth
{
get { return (ParentNode == null) ? 0 : (ParentNode.Depth + 1); }
}
public virtual bool CanCompute
{
get { return true; }
}
public string Expression
{
get { return string.Format("{0}{1}", LeftOperand, OperatorWithRightOperandSign); }
}
public ClockRotationDirection RotationDirection { get; private set; }
public int? Result { get; protected set; }
public CommonComputeNode ParentNode { get; private set; }
public List<CommonComputeNode> ChildNodes { get; private set; }
protected CommonComputeNode(int leftOperandValue, ClockRotationDirection clockDirection)
{
LeftOperand = leftOperandValue;
RotationDirection = clockDirection;
ChildNodes = new List<CommonComputeNode>();
}
public CommonComputeNode AddChildNode(CommonComputeNode childNode)
{
ChildNodes.Add(childNode);
childNode.ParentNode = this;
return this;
}
public List<CommonComputeNode> GetPath()
{
List<CommonComputeNode> path = new List<CommonComputeNode>();
CommonComputeNode node = this;
do
{
path.Add(node);
node = node.ParentNode;
} while (node != null);
path.Reverse();
return path;
}
}
public class Plus7 : CommonComputeNode
{
public override string OperatorWithRightOperandSign
{
get { return "+7"; }
}
public Plus7(int inputValue, ClockRotationDirection direction)
: base(inputValue, direction) { }
public override int Compute()
{
Result = LeftOperand + 7;
return Result.Value;
}
}
public class DividedBy2 : CommonComputeNode
{
public override string OperatorWithRightOperandSign
{
get { return "÷2"; }
}
public DividedBy2(int inputValue, ClockRotationDirection direction)
: base(inputValue, direction) { }
public override int Compute()
{
Result = LeftOperand / 2;
return Result.Value;
}
public override bool CanCompute
{
get { return IsDivisibleBy2(); }
}
private bool IsDivisibleBy2()
{
return (LeftOperand % 2).Equals(0);
}
}
public class MultipliedBy3 : CommonComputeNode
{
public override string OperatorWithRightOperandSign
{
get { return "×3"; }
}
public MultipliedBy3(int inputValue, ClockRotationDirection direction)
: base(inputValue, direction) { }
public override int Compute()
{
Result = LeftOperand * 3;
return Result.Value;
}
}
public class Minus5 : CommonComputeNode
{
public override string OperatorWithRightOperandSign
{
get { return "-5"; }
}
public Minus5(int inputValue, ClockRotationDirection direction)
: base(inputValue, direction) { }
public override int Compute()
{
Result = LeftOperand - 5;
return Result.Value;
}
}
public enum ClockRotationDirection
{
Clockwise = 0,
Counterclockwise = 1
}
#endregion
}
参赛结果
参见走迷宫 -- 民间manbetx户口奖参赛者名单和作品。
与其说俺没中奖,不如说是没得到《思考的乐趣:Matrix67数学笔记》实体书。
其实,乐趣并不源于奖品,而是源于思考本身。解答陈利人老师所出的趣味迷宫的过程就最大快乐,还有什么比这份大奖更让人开心的呢!而且,“趣味迷宫”只是思考的起点,快乐依然会继续下去……
(因为俺会进一步改善代码质量,提升执行速度 :D)