缘起

话说昨日(2012-11-08)刚好在微博上看到@陈利人老师发了一条解谜题送《思考的乐趣:Matrix67数学笔记》的微博。

题面

“迷宫”题:从图左边入口处的2011进去,在迷宫里转悠,最后变成2012从右边出来。可以在迷宫里转圈,可以重复之前走过的路,但不能回退。

puzzle

基本思路

一开始想直接手工推导出结果,长话短说,正向、反向试验几次后发现,通常推导到六七步后会遇到分支,继续往下推就比较头大了。

虽然手工推导无果而终,但是此过程加深了对谜题的理解,对于之后的程序设计可谓大有裨益。

至此,俺决定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
}

参赛结果

参见走迷宫 -- 民间图灵奖参赛者名单和作品

与其说俺没中奖,不如说是没得到《思考的乐趣:Matrix67数学笔记》实体书。

其实,乐趣并不源于奖品,而是源于思考本身。解答陈利人老师所出的趣味迷宫的过程就最大快乐,还有什么比这份大奖更让人开心的呢!而且,“趣味迷宫”只是思考的起点,快乐依然会继续下去……
(因为俺会进一步改善代码质量,提升执行速度 :D)

相关阅读

趣味迷宫再解:深度优先 vs. 广度优先