4
\$\begingroup\$

This is a solution to a community puzzle from CodinGame. Input for the program:

1st line: Two integers, height and width of the grid.

Next lines: The given slider puzzle grid consisting of numbers from 1 to n and a dot representing an empty space.

Example:

2 2

2 3

1 .

Goal: Order the numbers from 1 at the top left corner to n, with the empty space (dot) at the bottom right corner. The program needs to output the length of the shortest solution. It is given that such solution will always be less than 11 moves away.

Example:

1 2

3 .

The solution itself and it's efficiency is not really important. What I need is comments on my style, best practices and design, as I'm transitioning from C++ to C#.

The code:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

// In the given problem, the solution is always 10 or less moves away! Current solution only works for such cases

namespace SliderSolver
{
    class Program
    {
        static void Main(string[] args)
        {
            string[] inputs = Console.ReadLine().Split(' ');
            int height = int.Parse(inputs[0]);
            int width = int.Parse(inputs[1]);

            SliderState initial = new SliderState();
            for (int i = 0; i < height; ++i)
            {
                initial.Grid.Add(Console.ReadLine().Split(' ').Select(x => x[0]).ToList());
            }

            // Target is the grid filled with numbers from 1 to n - 1, with the free spot being at the bottom right corner
            SliderState target = new SliderState(initial.Grid);
            char num = '1';
            for (int i = 0; i < target.Grid.Count; ++i)
            {
                for (int j = 0; j < target.Grid[0].Count; ++j)
                {
                    target.Grid[i][j] = num++;
                }
            }
            target.Grid[target.Grid.Count - 1][target.Grid[0].Count - 1] = '.';

            List<SliderState> endings = new List<SliderState>();
            FindSolutions(initial, target, 0, endings);

            Console.Error.WriteLine($"Solutions found: {endings.Count}");

            int minSolutionLength = 11; // Shortest solution is always shorter than 11
            foreach (SliderState state in endings)
            {
                int tLength = CalculateSolutionLength(initial, state);
                if (tLength < minSolutionLength)
                {
                    minSolutionLength = tLength;
                }
            }

            // Solution is the minimum number of moves needed to reach the target
            Console.WriteLine(minSolutionLength);

            // Console.ReadKey();
        }

        static void FindSolutions(SliderState current, SliderState target, int depth, List<SliderState> endings)    // Find all <=10 move solutions with a simple DFS
        {
            if (depth > 10 || current == null)
            {
                return;
            }
            if (current.Equals(target))
            {
                endings.Add(current);
                return;
            }

            FindSolutions(current.GetNext(SliderState.Directions.Up), target, depth + 1, endings);
            FindSolutions(current.GetNext(SliderState.Directions.Right), target, depth + 1, endings);
            FindSolutions(current.GetNext(SliderState.Directions.Down), target, depth + 1, endings);
            FindSolutions(current.GetNext(SliderState.Directions.Left), target, depth + 1, endings);
        }

        static int CalculateSolutionLength(SliderState initial, SliderState current)
        {
            int moveCount = 0;
            while (!current.Equals(initial))   // End is always reached from the initial state, so the loop will not be infinite
            {
                current = current.Previous;
                moveCount++;
            }
            return moveCount;
        }
    }

    class SliderState : IEquatable<SliderState>
    {
        public enum Directions
        {
            Up,
            Right,
            Down,
            Left
        }

        public List<List<char>> Grid { get; private set; }
        public SliderState Previous { get; private set; }

        public SliderState()
        {
            Grid = new List<List<char>>();
            Previous = null;
        }

        public SliderState(List<List<char>> tGrid, SliderState tPrev = null)
        {
            Grid = tGrid.ConvertAll(x => new List<char>(x));    // Create a deep copy of the list
            Previous = tPrev;
        }

        public bool Equals(SliderState other)   // Two states are considered equal if their grids are identical (the ancestor state is disregarded)
        {
            for (int i = 0; i < Grid.Count; ++i)
            {
                for (int j = 0; j < Grid[i].Count; ++j)
                {
                    if (Grid[i][j] != other.Grid[i][j])
                    {
                        return false;
                    }
                }
            }
            return true;
        }

        public SliderState GetNext(Directions dir)  // Returns the next state after the free slot is moved to the given direction, or null if such state is unavailable
        {
            int freeX = 0;  // Coordinates of the free slot
            int freeY = 0;
            for (int i = 0; i < Grid.Count; ++i)
            {
                for (int j = 0; j < Grid[i].Count; ++j)
                {
                    if (Grid[i][j] == '.')
                    {
                        freeX = j;
                        freeY = i;
                    }
                }
            }

            SliderState tState = new SliderState(Grid, this);   // Current state is set as the previous state of the next state

            switch (dir)
            {
                case Directions.Up:
                    if (freeY - 1 >= 0)
                    {
                        char tmp = tState.Grid[freeY - 1][freeX];
                        tState.Grid[freeY - 1][freeX] = tState.Grid[freeY][freeX];
                        tState.Grid[freeY][freeX] = tmp;
                        return tState;
                    }
                    break;
                case Directions.Right:
                    if (freeX + 1 < Grid[0].Count)
                    {
                        char tmp = tState.Grid[freeY][freeX + 1];
                        tState.Grid[freeY][freeX + 1] = tState.Grid[freeY][freeX];
                        tState.Grid[freeY][freeX] = tmp;
                        return tState;
                    }
                    break;
                case Directions.Down:
                    if (freeY + 1 < Grid.Count)
                    {
                        char tmp = tState.Grid[freeY + 1][freeX];
                        tState.Grid[freeY + 1][freeX] = tState.Grid[freeY][freeX];
                        tState.Grid[freeY][freeX] = tmp;
                        return tState;
                    }
                    break;
                case Directions.Left:
                    if (freeX - 1 >= 0)
                    {
                        char tmp = tState.Grid[freeY][freeX - 1];
                        tState.Grid[freeY][freeX - 1] = tState.Grid[freeY][freeX];
                        tState.Grid[freeY][freeX] = tmp;
                        return tState;
                    }
                    break;
            }

            // If the move was impossible, return null
            return null;
        }
    }
}
\$\endgroup\$
2
\$\begingroup\$

Here's some general style feedback.

string[] inputs = Console.ReadLine().Split(' ');

The game requires some input from the console but does not clearly ask for it. I could not figure out how to use it - even by reading the code. Console.Write[Line] here and there about the expected input would be really helpful.


Console.Error.WriteLine($"Solutions found: {endings.Count}");

Is finding a solution considered an error?


class SliderState : IEquatable<SliderState>
{
  public enum Directions
  {
      Up,
      Right,
      Down,
      Left
  }

We usually don't nest public classes or enums. private would be ok but public is not a good style.


case Directions.Up:
  if (freeY - 1 >= 0)
  {
      char tmp = tState.Grid[freeY - 1][freeX];
      tState.Grid[freeY - 1][freeX] = tState.Grid[freeY][freeX];
      tState.Grid[freeY][freeX] = tmp;
      return tState;
  }
  break;

You have this similar code four times but you could encapsulate some parts of it and reduce the repetition and make it testable.


char tmp = tState.Grid[freeY - 1][freeX];
tState.Grid[freeY - 1][freeX] = tState.Grid[freeY][freeX];
tState.Grid[freeY][freeX] = tmp;

First this needs a Swap method that requires the Grid and indexes.

if (freeY - 1 >= 0)

Then there are these conditions. They should be encapsulated too. For example this should be CanMoveUp.

Finally if you can use C# 7 could could write this switch as

switch (dir)
{
    case Directions.Up when CanMoveUp():
        MoveUp();                
        return tState;
    // other cases...
}

Where MoveUp uses Swap like this:

void MoveUp()
{
    var indexFrom = ...
    var indexTo = ...
    Swap(Grid, indexFrom, indexTo);
}

tGrid

In C# we don't use Hungarian notation so the t is not necessary.

\$\endgroup\$
  • \$\begingroup\$ Thank you for your review! I'll try to clear up a few misunderstandings. Like I mentioned in the description, this is a solution to a puzzle from CodinGame. The soluitions on that site are run automatically, so there was no need to add explanations for the user. Anything written to Console is considered a part of the solution by the site, so I had to use Console.Error for debugging. \$\endgroup\$ – Kodnot Jun 24 '17 at 9:30
  • \$\begingroup\$ Now for questions. First, what class should have the "Swap" and "CanMoveUp" methods? Then, I used the "t" in "tGrid" to differentiate between it and the property "Grid". What name should I have used instead? Simply "grid"? \$\endgroup\$ – Kodnot Jun 24 '17 at 9:34
  • \$\begingroup\$ @Kodnot I wasn't sure if you meant the actual solution to be posted there or a general for fun solution and because you are interested in best practices and styles etc. I thought they are worth mentioning. For passing the puzzles it really doesn't matter how you do it. You won't get any additional points for cleanles, reusability, testability, maintainability and so on. Online you just have to pass the test no matter how. However I assumed you are more interested in real life quality code that should possibly have many other positive properties. \$\endgroup\$ – t3chb0t Jun 24 '17 at 12:33
  • \$\begingroup\$ @Kodnot my suggestions are the first step to make it modular and testable so at this stage I find it's ok to put the methods inside the same class. If you then notice some pattern or it would make sense to create another module (class) specialized is something different because a few methods seem to be very similar and don't look like a part of a particular object, then do it. It's usually an iterative process and you cannot predict everything at the beginning. \$\endgroup\$ – t3chb0t Jun 24 '17 at 12:36
  • \$\begingroup\$ @Kodnot it's also fine to write a switch like in your question first to just make it work... you then see a repeating pattern and try to encapsulate it to reduce it and to not repeat yourself and possibly make a mistake but the n-th copy-pase-adjustment. \$\endgroup\$ – t3chb0t Jun 24 '17 at 12:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.