图解题器

Question

我已经解决了空缺职位的测试任务。需要你对我的解决方案的反馈。

任务

下图显示了解题状态。这个谜题由10个细胞组成。在这些单元中，一个是空的，其余的是从1到9个。一个空单元用于沿允许的路径排列数字，这些路径显示为连接单元的线。如果所有的单元格都按照图像中所示的顺序排列，那么谜题就会被认为解决了。

在C#中创建控制台程序，该程序可以部分或完全解决指定图形上的谜题。实现的程序接口应以下列形式编写：

public interface IResolver
{
    int[] Solve(int[] input);
}

当输入单元格数组int[] input从左到右和从上到下写入时，空白单元格表示数字0。(初始状态可以写为[1,2,3,0,4,5,6,7,8,9]。)输出数组必须包含一个移动序列-从1到9的数字，必须在下一步自由单元格中移动。

示例

让方法Solve (int[] input)的输入值是输入[1,2,3,4,6,5,0,7,8,9]，那么问题的最优解将由两个步骤组成，如下图所示：

在第一步交换6 0时，将↔写入输出数组。在第二步中，交换4个4 0，而在输出中写入数组↔。程序的结果将是[6,4]。

溶液

Resolver.cs

public class Resolver
{
    // Available indexes for move
    public static ReadOnlyDictionary<int, int[]> AvailableMoveIndexes => new ReadOnlyDictionary<int, int[]>
    (
        new Dictionary<int, int[]>
        {
            [0] = new[] { 1, 2 },
            [1] = new[] { 0, 4 },
            [2] = new[] { 0, 3, 5 },
            [3] = new[] { 2, 4 },
            [4] = new[] { 1, 3, 6 },
            [5] = new[] { 2, 7 },
            [6] = new[] { 4, 8 },
            [7] = new[] { 5, 8, 9 },
            [8] = new[] { 6, 7, 9 },
            [9] = new[] { 7, 8 }
        }
    );

    private static bool IsSolved(IList<int> input) => input.SequenceEqual(new[] { 1, 2, 3, 0, 4, 5, 6, 7, 8, 9 });

    private static void ValidateInput(IList<int> input)
    {
        if (input == null)
            throw new ArgumentNullException(nameof(input));

        // Input must consist only from numbers from 0 to 9
        if (!input.OrderBy(x => x).SequenceEqual(Enumerable.Range(0, 10)))
            throw new ArgumentException("Invalid input.", nameof(input));
    }

    private readonly ReadOnlyCollection<int> _input;

    private IEnumerable<int[]> _indexMovesCollection;

    public Resolver(IList<int> input)
    {
        ValidateInput(input);

        _input = new ReadOnlyCollection<int>(input);
    }

    private int GetZeroIndex() => _input.IndexOf(0);

    public int[] Solve()
    {
        // Minimum number of moves based on distance from empty cell to target cell
        Dictionary<int, int> minimumNumberOfMovesDictionary = new Dictionary<int, int>
        {
            [0] = 2,
            [1] = 2,
            [2] = 1,
            [3] = 0,
            [4] = 1,
            [5] = 2,
            [6] = 2,
            [7] = 3,
            [8] = 3,
            [9] = 4
        };

        int minimumNumberOfMoves = minimumNumberOfMovesDictionary[GetZeroIndex()];

        if (minimumNumberOfMoves == 0 && IsSolved(_input)) return new int[0];

        const int maximumNumberOfMoves = 100;

        int zeroIndex = GetZeroIndex();

        // Get all move combinations
        _indexMovesCollection = AvailableMoveIndexes[zeroIndex].Select(index => new[] { index });

        for (int moveCount = 1; moveCount < maximumNumberOfMoves; moveCount++)
        {
            if (moveCount >= minimumNumberOfMoves)
            {
                foreach (int[] indexMoves in _indexMovesCollection)
                {
                    if (TrySolution(indexMoves, out int[] moveHistory))
                        return moveHistory;
                }
            }

            _indexMovesCollection = _indexMovesCollection
                .SelectMany(indexMoves =>
                    AvailableMoveIndexes[indexMoves.Last()]
                        // Remove combinations where subsequent move can undo previous move
                        .Except(new[] { indexMoves.Length < 2 ? zeroIndex : indexMoves[indexMoves.Length - 2] })
                        .Select(indexMove => indexMoves.Append(indexMove).ToArray()))
                .ToArray();
        }

        // Too many moves
        throw new Exception("Unsolvable puzzle.");
    }

    private bool TrySolution(int[] indexMoves, out int[] moveHistory)
    {
        int[] transformedPuzzle = _input.ToArray();
        List<int> moveHistoryList = new List<int>(indexMoves.Length);

        foreach (int indexMove in indexMoves)
        {
            int move = transformedPuzzle[indexMove];

            // swap cell values to simulate move
            transformedPuzzle[Array.IndexOf(transformedPuzzle, 0)] = move;
            transformedPuzzle[indexMove] = 0;

            moveHistoryList.Add(move);
        }

        moveHistory = moveHistoryList.ToArray();

        return IsSolved(transformedPuzzle);
    }
}

ResolverImplementation.cs

public class ResolverImplementation : IResolver
{
    public int[] Solve(int[] input) => new Resolver(input).Solve();
}

单元测试

我添加了NUnit测试以确保我的解决方案工作正常。

public class ResolverTests
{
    [Test]
    public void ShouldThrowArgumentNullException_WhenNullPassed()
    {
        // Arrange

        // Act

        // Assert
        Assert.Throws<ArgumentNullException>(() => new Resolver(null));
    }

    [Test]
    public void ShouldThrowArgumentException_WhenWrongInputPassed()
    {
        // Arrange

        // Act

        // Assert
        Assert.Throws<ArgumentException>(() => new Resolver(new[] { -1, 2, 3, 0, 4, 5, 6, 7, 8, 9 }), "Invalid input.");
    }

    [Test]
    public void ShouldThrowArgumentException_WhenDuplicateElementsPassed()
    {
        // Arrange

        // Act

        // Assert
        Assert.Throws<ArgumentException>(() => new Resolver(new[] { 1, 2, 3, 0, 4, 5, 6, 7, 8, 9, 1 }), "Invalid input.");
    }

    [Test]
    public void ShouldReturnEmptyArray_WhenSolvedPuzzlePassed()
    {
        // Arrange
        Resolver resolver = new Resolver(new[] { 1, 2, 3, 0, 4, 5, 6, 7, 8, 9 });

        // Act
        int[] solution = resolver.Solve();

        // Assert
        Assert.AreEqual(solution, new int[0]);
    }

    [Test]
    public void ShouldReturnSolution_WhenSimplestSolutionPassed()
    {
        // Arrange
        Resolver resolver = new Resolver(new[] { 1, 2, 3, 4, 0, 5, 6, 7, 8, 9 });

        // Act
        int[] solution = resolver.Solve();

        // Assert
        Assert.AreEqual(solution, new[] { 4 });
    }

    [Test]
    public void ShouldReturnSolution_WhenSimpleSolutionPassed()
    {
        // Arrange
        Resolver resolver = new Resolver(new[] { 1, 2, 3, 4, 6, 5, 0, 7, 8, 9 });

        // Act
        int[] solution = resolver.Solve();

        // Assert
        Assert.AreEqual(solution, new[] { 6, 4 });
    }

    [Test]
    public void ShouldReturnSolution_WhenAverageSolutionPassed()
    {
        // Arrange
        Resolver resolver = new Resolver(new[] { 1, 2, 3, 4, 6, 5, 8, 9, 7, 0 });

        // Act
        int[] solution = resolver.Solve();

        // Assert
        Assert.AreEqual(solution, new[] { 9, 7, 8, 6, 4 });
    }

    [Test]
    public void ShouldReturnSolution_WhenHardSolutionPassed()
    {
        // Arrange
        Resolver resolver = new Resolver(new[] { 8, 7, 9, 6, 5, 4, 1, 2, 0, 3 });

        // Act
        int[] solution = resolver.Solve();

        // Assert
        Assert.AreEqual(solution, new[] { 2, 4, 9, 6, 5, 1, 2, 3, 4, 9, 6, 8, 7, 1, 2, 3, 4, 9, 6, 8, 7, 1, 2, 3, 4, 6, 8, 7, 5, 3, 4, 6, 8, 7, 5, 3 });
    }
}

Notes

我在解决方案中使用Append和Prepend LINQ方法，这些方法可以在.NET Core、.NET Standard 1.6+、.NET Framework4.7.1+中找到。如果您没有指定版本的.NET，可以手动添加它们，就像下面这样的扩展方法一样。

public static class EnumerableExtensions
{
    public static IEnumerable<TSource> Append<TSource>(this IEnumerable<TSource> source, TSource element) => source.Concat(new[] { element });

    public static IEnumerable<TSource> Prepend<TSource>(this IEnumerable<TSource> source, TSource element) => new[] { element }.Concat(source);
}

测试

为了生成谜题序列和测试解决方案，我添加了一个单独的WPF应用程序，在这个窗口中，单击允许的空单元格可以交换它们。

MainWindow.xaml

<Window x:Class="Puzzle9.Game.MainWindow"
        xmlns="http://schemas.microsoft.com/winfx/2006/xaml/presentation"
        xmlns:x="http://schemas.microsoft.com/winfx/2006/xaml"
        xmlns:d="http://schemas.microsoft.com/expression/blend/2008"
        xmlns:mc="http://schemas.openxmlformats.org/markup-compatibility/2006"
        mc:Ignorable="d"
        Title="MainWindow" Height="450" Width="800">
    <Viewbox>
        <Canvas Width="150" Height="160">
            <Canvas.Resources>
                <Style TargetType="Button">
                    <Setter Property="Foreground" Value="#5680a7" />
                    <Setter Property="HorizontalContentAlignment" Value="Center" />
                    <Setter Property="VerticalContentAlignment" Value="Center" />
                    <Setter Property="Template">
                        <Setter.Value>
                            <ControlTemplate TargetType="{x:Type Button}">
                                <Border x:Name="border" Width="20" Height="20" BorderThickness="1" BorderBrush="#5680a7" Background="{TemplateBinding Background}" SnapsToDevicePixels="true" CornerRadius="10">
                                    <ContentPresenter x:Name="contentPresenter" Focusable="False" HorizontalAlignment="{TemplateBinding HorizontalContentAlignment}" Margin="{TemplateBinding Padding}" RecognizesAccessKey="True" SnapsToDevicePixels="{TemplateBinding SnapsToDevicePixels}" VerticalAlignment="{TemplateBinding VerticalContentAlignment}"/>
                                </Border>
                            </ControlTemplate>
                        </Setter.Value>
                    </Setter>
                </Style>

                <Style TargetType="Line">
                    <Setter Property="Stroke" Value="#5680a7" />
                    <Setter Property="StrokeThickness" Value="1" />
                    <Setter Property="Panel.ZIndex" Value="-1" />
                </Style>
            </Canvas.Resources>
            <Button Name="Button0" Canvas.Left="45" Canvas.Top="10" Click="Button_Click">1</Button>
            <Button Name="Button1" Canvas.Left="95" Canvas.Top="10" Click="Button_Click">2</Button>
            <Button Name="Button2" Canvas.Left="20" Canvas.Top="40" Click="Button_Click">3</Button>
            <Button Name="Button3" Canvas.Left="70" Canvas.Top="40" Click="Button_Click"></Button>
            <Button Name="Button4" Canvas.Left="120" Canvas.Top="40" Click="Button_Click">4</Button>
            <Button Name="Button5" Canvas.Left="20" Canvas.Top="70" Click="Button_Click">5</Button>
            <Button Name="Button6" Canvas.Left="120" Canvas.Top="70" Click="Button_Click">6</Button>
            <Button Name="Button7" Canvas.Left="45" Canvas.Top="100" Click="Button_Click">7</Button>
            <Button Name="Button8" Canvas.Left="95" Canvas.Top="100" Click="Button_Click">8</Button>
            <Button Name="Button9" Canvas.Left="70" Canvas.Top="130" Click="Button_Click">9</Button>
            <Line X1="55" Y1="20" X2="105" Y2="20" />
            <Line X1="55" Y1="20" X2="30" Y2="50" />
            <Line X1="105" Y1="20" X2="130" Y2="50"/>
            <Line X1="30" Y1="50" X2="130" Y2="50" />
            <Line X1="30" Y1="50" X2="30" Y2="80" />
            <Line X1="130" Y1="50" X2="130" Y2="80" />
            <Line X1="30" Y1="80" X2="55" Y2="110" />
            <Line X1="130" Y1="80" X2="105" Y2="110" />
            <Line X1="55" Y1="110" X2="80" Y2="140" />
            <Line X1="55" Y1="110" X2="105" Y2="110" />
            <Line X1="105" Y1="110" X2="80" Y2="140" />
        </Canvas>
    </Viewbox>
</Window>

MainWindow.xaml.cs

using System.Linq;
using System.Windows;
using System.Windows.Controls;
using Puzzle9.Core;

namespace Puzzle9.Game
{
    public partial class MainWindow : Window
    {
        public MainWindow() => InitializeComponent();

        private void Button_Click(object sender, RoutedEventArgs e)
        {
            Button button = sender as Button;
            Canvas parent = button.Parent as Canvas;

            int currentIndex = parent.Children.IndexOf(button);

            Button zeroButton = parent.Children.OfType<Button>().First(b => b.Content == null);
            int zeroIndex = parent.Children.IndexOf(zeroButton);

            if (Resolver.AvailableMoveIndexes[zeroIndex].Contains(currentIndex))
            {
                zeroButton.Content = button.Content;
                button.Content = null;
            }
        }
    }
}

Answer 1

public static ReadOnlyDictionary<int, int[]> AvailableMoveIndexes => new ReadOnlyDictionary<int, int[]> ( new Dictionary<int, int[]> { [0] = new[] { 1, 2 }, ...

很好的清晰的表示，但是为什么是public？我希望private或(可能更好)具有InternalsVisibleTo属性的internal允许单元测试来验证可能的移动是双向的(即，AvailableMoveIndexes[i].Contains(j)当且仅当AvailableMoveIndexes[j].Contains(i))。

private readonly ReadOnlyCollection<int> \_input;

为什么叫这个名字？我不认为对象有输入:程序和进程都有输入。

另外，IReadOnlyList<int>会是一个更好的使用类型吗？它清楚地表明了这一秩序是相关的。

Dictionary<int, int> minimumNumberOfMovesDictionary = new Dictionary<int, int> { [0] = 2, ...

对于这样密集的查找，国际海事组织的int[]更有意义。

if (minimumNumberOfMoves == 0 && IsSolved(\_input)) return new int[0];

minimumNumberOfMoves != 0 && IsSolved(_input)有可能吗？

答:不，所以这可以简化为if (IsSolved(_input)) return new int[0];

const int maximumNumberOfMoves = 100;

这个号码是从哪里来的？你有数学证据证明这正是所需的最大数目吗？你有数学证明它是一个有效的上界吗？还是只是保守的猜测？

这个问题的答案应该在代码中的注释中。

下面是反问句，并将我的回答/评论与我使用的扰流块区别开来。这些是我在面试中会问的问题。如果编写代码的人是初级程序员，我可能也会在非访谈代码评审中提出类似的问题，但在这种情况下，我可能会给出更多的提示。

for (int moveCount = 1; moveCount < maximumNumberOfMoves; moveCount++) { ... }

因为这是一个面试问题，你可能会被问到你在做什么类型的搜索。为了回答这个问题，我会把一个评论放在循环的上方。

如果我问你为什么选择那种搜索，你有答案吗？如果是因为你没有时间去实现一个更好的，你会想要实现什么呢？

您在评论中的回答是：“循环用于从最小到最大的移动来解决谜题。”我希望得到的回应是“广度优先搜索”。我个人会选择实现Dijkstra的算法或A*。设置这一特定任务的主要原因之一似乎很可能是：(a)您是否知道标准算法；(b)您是否认识到它们何时适用。

// Remove combinations where subsequent move can undo previous move .Except(new[] { indexMoves.Length < 2 ? zeroIndex : indexMoves[indexMoves.Length - 2] })

通过检测和跳过长度为2的循环，这提供了一些优化，但是围绕位置7、8、9的3长循环仍然是可能的。如何检测和跳过任意长度的循环？

简单的方法是使用支持哈希码和等式测试的表示，然后使用HashMap<>跟踪您已经看到的位置。

内存使用率很高。你怎么能改变你的数据结构以减少内存的使用？

内存使用率很高的原因是复制数组以将元素添加到末尾。相反，您可以使用一个链接列表，其中每个节点向后而不是向前；为了输出，有必要反转列表，但是_indexMovesCollection的每个元素对于最后一个元素只需要一个int (甚至byte)，对前一个元素只需要一个引用。