Подтвердить что ты не робот

Поверните 2D-сетку в "бриллиант" с LINQ - возможно ли это?

На днях мне нужен был алгоритм для превращения 2D-сетки в алмаз (путем эффективного поворота на 45 градусов), поэтому я мог бы рассматривать диагональные последовательности как плоские перечислимые числа, например:

    1 2 3        1         
    4 5 6  =>   4 2      
    7 8 9      7 5 3   
                8 6     
                 9

Мой алгоритм выглядит следующим образом:

public static IEnumerable<IEnumerable<T>> RotateGrid<T>(IEnumerable<IEnumerable<T>> grid)
    {
        int bound = grid.Count() - 1;
        int upperLimit = 0;
        int lowerLimit = 0;

        Collection<Collection<T>> rotated = new Collection<Collection<T>>();

        for (int i = 0; i <= (bound * 2); i++)
        {
            Collection<T> row = new Collection<T>();

            for (int j = upperLimit, k = lowerLimit; j >= lowerLimit || k <= upperLimit; j--, k++)
            {
                row.Add(grid.ElementAt(j).ElementAt(k));
            }

            rotated.Add(row);

            if (upperLimit == bound)
                lowerLimit++;

            if (upperLimit < bound)
                upperLimit++;
        }

        return rotated;
    }

Можно ли это сделать в более сжатом формате с использованием LINQ?

.. или даже просто более сжатый формат?:)

4b9b3361

ОТВЕТЫ

Ответ 1

Вот что я придумал:

void Main()
{
    var lists = new string[] { "123", "456", "789" };

    foreach (var seq in RotateGrid(lists))
        Console.WriteLine(string.Join(", ", seq));
}

public IEnumerable<IEnumerable<T>> RotateGrid<T>(IEnumerable<IEnumerable<T>> grid) 
{
    int rows = grid.Count();
    int cols = grid.First().Count();
    return 
        from i in Enumerable.Range(0, rows + cols - 1)
        select (
            from j in Enumerable.Range(0, i + 1)
            where i - j < rows && j < cols
            select grid.ElementAt(i - j).ElementAt(j)
        );
}

Вывод:

1
4, 2
7, 5, 3
8, 6
9

Это становится намного более чистым и более эффективным, если вы можете принять IList<T> вместо просто IEnumerable<T>. Я думаю о более эффективном подходе (не используя .ElementAt), который также работал бы с IEnumerable`, который я опубликую, если мне удастся его написать.

Обновление

Вот моя более практичная версия, которая по-прежнему справляется с обувным рогом в большом количестве linq. Это достаточно эффективный алгоритм, поскольку он только создает перечислитель один раз для каждого IEnumerable.

public IEnumerable<IEnumerable<T>> RotateGrid<T>(IEnumerable<IEnumerable<T>> grid) 
{
    var enumerators = new LinkedList<IEnumerator<T>>();
    var diagonal = 
        from e in enumerators
        where e.MoveNext()
        select e.Current;
    foreach (var row in grid)
    {
        enumerators.AddFirst(row.GetEnumerator());
        yield return diagonal.ToArray();
    }

    T[] output;
    while (true)
    {
        output = diagonal.ToArray();
        if(output.Length == 0) yield break;
        yield return output;
    }
}