Как на C# написать программу в одно выражение?

в 8:32, , рубрики: оптимизация

Попалась на Stack Overflow интересная задачка: написать программу как можно короче и в одно выражение или с одним оператором (statement) верхнего уровня с точкой с запятой в конце и не использовать блоки кода. Вложенные операторы допускаются.

Написано по (собственным) материалам со Stack Overflow.

Понятно, что это не для любителей стандартного стиля c#. Поэтому чувствительных особ прошу дальше не читать :-).

После решения задачи и получения чувства полного удовлетворения в голове стала вертеться одна мысль: "А что же здесь такого особенного?" В результате анализа захотелось поделиться некоторыми моментами.

  1. Это хороший тест на знание языка. Специфические требования вынуждают использовать стандартные конструкции в несколько других целях.

  2. Одним из самых затруднительных моментов оказалось объявление переменных, что стандартно, кроме некоторых случаев, требует отдельного оператора.

  3. Использование методов "Linq.Enumerable" для организации циклов и преобразования одиночного элемента в коллекцию и наоборот (агрегирование и создание последовательности), а также, совместно с анонимным типом, для выполнения вычислений.

Итак, начну с задачи (авторский текст сохранён).

На вход с консоли пользователь вводит любое число от 0 до что-то около long.Max Это число кладётся на левую чашу весов. Степенями тройки нужно сбалансировать эти весы. Ну то есть если на вход даётся 7, то на левые к 7 кладём 3, а на правые 9 и 1. Веса не могут повторяться. То есть нельзя дважды класть 1. Цель, решить данную задачу в одну, максимально короткую строку. Не важно насколько она будет не читабельной.

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

Приведу программу на Python за авторством @MBo,которая иллюстрирует алгоритм решения задачи.

def TriEqSystem(n):
    lst = []
    p = 1
    while n:
        n, m = divmod(n, 3)
        if m:
            lst.append(p*(3-2*m))  #добавляет p или (-p) для остатков 1 и 2
            n += (m-1)             #увеличить следующий разряд для остатка 2
        p *= 3
    return lst

for i in range(1,101):
    l = TriEqSystem(i)
    print(i, sum(l), l)

...
10 10 [1, 9]
11 11 [-1, 3, 9]
12 12 [3, 9]
13 13 [1, 3, 9]
14 14 [-1, -3, -9, 27]
15 15 [-3, -9, 27]
16 16 [1, -3, -9, 27]
17 17 [-1, -9, 27]
...

Здесь отрицательное число означает, что гирю нужно положить на ту же чашку весов, что и число. В следующих двух решениях наоборот, отрицательное число - гиря на свободную чашку весов.

После нескольких итераций у меня получился следующий код.

using System;
static class Program {
    static void Main() {
        for (
          long i = 1, n = Int64.Parse(Console.ReadLine()), j = n % 3;
          n > 0;
          i += i << 1, n = n / 3 + (j == 0 ? 0 : j - 1), j = n % 3
        )
          if (j > 0) Console.WriteLine(i * ((j << 1) - 3));
    }
}

Для удобства восприятия одна строка с оператором for разбита на несколько, каждая секция оператора в своей строке, тело - в своей.

Здесь я воспользовался стандартными возможностями оператора for, который позволяет в секции инициализации объявлять локальные переменные, а в секции итератора задавать несколько выражений.

Что вызвало затруднения? Нужно было чётко сообразить, что секция итератора выполняется в конце каждого выполнения тела цикла (после тела), и что записанные там выражения, по сути, являются начальными операторами для следующего выполнения тела цикла. Одно выражение из-за этого пришлось повторить в инициализаторе цикла.

Второй вариант решения использует Linq.

using System;
using System.Linq;
static class Program {
    static void Main() {
        foreach (var m in Enumerable.Range(Int64.Parse(Console.ReadLine()!) is long N && 1L is long i? 0 : 0, 40)
            .Select(s => new { x = N = Math.DivRem(N, 3, out long j), Rem = j, y = j == 0 ? N : N += j - 1 })
            .Where(w => w.Rem > 0).Select(s => (i *= 3) / 3 * ((s.Rem << 1) - 3))) Console.WriteLine(m);
    }
}

Прежде всего, нужно ввести исходные данные. В этом нам поможет оператор сравнения типов is, который позволяет объявить переменную. Использовав этот оператор в тернарном операторе, который выдаёт необходимую нам константу вне зависимости от результатов сравнения, мы можем объявить переменную для присвоения ей входного числа. Соединяя is с помощью логических операторов, можно объявить и инициализировать необходимое количество переменных. Таким образом введена переменная i, в которой итерационно вычисляются степени тройки, что позволяет избежать "Math.Pow". Эти две внешние переменные потом захватываются лямбда-выражениями.

Для генерации последовательности, необходимой для организации циклических вычислений, используется метод "Enumerable.Range" как аналог оператора for.

Для проведения вычислений используется метод Select, который позволяет делать практически произвольные преобразования одной последовательности в другую. С помощью создания экземпляра анонимного типа можно производить последовательные вычисления, используя промежуточные переменные.

Ещё один вариант объявления переменных - это метод с параметром out, как, например, DivRem.

Where пропускает значения остатка, равные 0, а финальный Select вычисляет веса "гирь".


Я рассмотрел несколько приёмов, которые в некоторых случаях могут помочь написать более компактный код.

Автор: rotabor

Источник


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js