среда, 4 июля 2018 г.

Сдвиг массива влево на N элементов

Есть ряд способов сдвинуть массив влево на N элементов. Можно взять и сделать N сдвигов по одному элементу, получив квадратичную сложность. Можно создать целевой массив по размеру исходного и вычислить положение каждого элемента после сдвига. Хорошо, но скорость линейна, затраты по памяти - тоже.
Если чутка подумать, то можно придумать реализацию, которая мутирует массив и дает линейную скорость и константные затраты по памяти. Но есть один очень элегантный способ – из 3-х строк на основе чудо Span of T из System.Memory:
public static void RotateLeft(int[] input, int direction)
{
    input.AsSpan(0, direction).Reverse();
    input.AsSpan(direction).Reverse();
    input.AsSpan().Reverse();
}
Идея такая: чтобы сдвинуть массив из K элементов на N элементов влево, нужно перевернуть первые N элементов в массиве, затем последние K - N -1 элементов, а затем перевернуть весь массив:
// direction == 2, input.Length == 7
input.AsSpan(0, direction).Reverse();
// [2][1][3][4][5][6][7]
input.AsSpan(direction).Reverse();
// [2][1][7][6][5][4][3]
input.AsSpan().Reverse();// [3][4][5][6][7][1][2]

Получается два прохода по массиву, но зато с читабельностью решения все очень ОК.

вторник, 3 июля 2018 г.

Welcome, так сказать, back:)

Мне вот тут подумалось, что блоггинга мне не хватает. Причем не очень хочется писать чего-то длинное и сильно умное. Для этого, у меня теперь на английском блог есть. Хочется чего-то простого и легковесного, типа журнала живого. Вроде бы есть всякие Г+ и фейсбуки, но их формат мне все равно не нравится. Если захочешь чего-нить своего потом найти там, заморишься.

Так что я решил восстановить блог, но в формате, о чем пишется, о том и буду писать. В основном о технологиях, о книжках читаемых и мыслях при этом в голову приходящих.

Вот и сейчас просто хочется поделиться загадкой, которую вчера решал:

Есть пять нор, расположенных в ряд. В одной из них сидит лиса. Каждую ночь лиса перебирается в соседнюю норму слева или справа. Каждое утро вы можете проверить одну нору на выбор. Какая должна быть стратегия проверки нор, чтобы в конечном итоге лиса была поймана?