C# - Expressive and Slow


  • 0
    L

    I felt like having fun with this one, not an attempt for speed.

    Obviously could be made significantly faster via removing most of the .NET features and class creation. Algorithmically, could short-circuit the fourth line if there is no possibility of a longer path being found and could set _isRoot to false on neighbouring vertices in the graph

    public class Solution
    {
        public int LongestIncreasingPath(int[,] matrix)
        {
            //This problem boils down to finding the longest path in a unit DAG. This can be done via memoized DFS
            Cell[,] cells = new Cell[matrix.GetLength(0), matrix.GetLength(1)];
            matrix.ForAll((i, j) => cells[i, j] = new Cell(i, j, matrix, cells));
            List<Cell> roots = new List<Cell>(cells.Where(x => x.IsRoot));
            return (from root in roots select root.PathLength).DefaultIfEmpty().Max();
        }
    }
    
    public class Cell
    {
        public readonly int i;
        public readonly int j;
        private bool? _isRoot;
        private readonly Cell[,] m2;
        public int Value { get; }
    
        private Lazy<int> _pathLength;
    
        public Cell(int i, int j, int[,] matrix, Cell[,] m2)
        {
            this.i = i;
            this.j = j;
            this.m2 = m2;
            this.Value = matrix[i, j];
            _pathLength = new Lazy<int>(GeneratePathLength);
        }
    
        private int GeneratePathLength() => (from c in GetAdjacentCells() where c.Value < this.Value select c.PathLength).DefaultIfEmpty().Max() + 1;
        public bool IsRoot
        {
            get
            {
                if (!_isRoot.HasValue)
                    _isRoot = CheckRoot();
                return _isRoot.Value;
            }
        }
        public int PathLength => _pathLength.Value;
        protected bool CheckRoot() => !GetAdjacentCells().Any(x => x.Value > this.Value);
    
        public IEnumerable<Cell> GetAdjacentCells()
        {
            if (i > 0) yield return m2[i - 1, j];
            if (j > 0) yield return m2[i, j - 1];
            if (i < m2.GetLength(0) - 1) yield return m2[i + 1, j];
            if (j < m2.GetLength(1) - 1) yield return m2[i, j + 1];
        }
    }
    
    public static class MatrixExtensions
    {
        public static IEnumerable<T> Where<T>(this T[,] matrix, Func<T, bool> predicate)
        {
            foreach (var value in matrix.ForEachValue())
                if(predicate(value))
                    yield return value;
        }
    
        public static IEnumerable<Tuple<int, int>> ForEach<T>(this T[,] matrix)
        {
            for (int i = 0; i < matrix.GetLength(0); i++)
                for (int j = 0; j < matrix.GetLength(1); j++)
                    yield return Tuple.Create(i, j);
        }
    
        public static IEnumerable<T> ForEachValue<T>(this T[,] matrix)
        {
            for (int i = 0; i < matrix.GetLength(0); i++)
                for (int j = 0; j < matrix.GetLength(1); j++)
                    yield return matrix[i, j];
        }
    
        public static void ForAll<T>(this T[,] matrix, Action<int, int> action)
        {
            foreach (var tuple in matrix.ForEach())
                action(tuple.Item1, tuple.Item2);
        }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.