Недавно прошёл конкурс красоты кода от Сбера. Участие по направлению Android в этом конкурсе было интересным опытом, которым я поделюсь в статье.

Содержание:

• О конкурсе

• Задание по направлению Android

• Моё решение

• Решение chatGPT

• Звонок другу

• Комментарий победителя в номинации «Изящный код» и его решение

О конкурсе

Компьютерный код может написать любой разработчик. Красивый код пишут лишь единицы. Чистый, изящный, лаконичный, читаемый и понятный код, который работает без багов — это настоящее произведение искусства в сфере разработки.

Для участников стояла задача написать красивый код по одному из пяти направлений (Python, Java, Data Science, Front-end, Android).

Каждое направление предусматривало 3 номинации:

• Краса кода — решение, признанное максимально эффективным по мнению жюри;

• Изящный код — самое лаконичное решение, соответствующее поставленной задаче;

• Звезда кода — самое неординарное решение по общей оценке жюри.

Призы конкурса: iPhone 14, колонка SberBoom Mini и приглашение на вечеринку в честь дня программиста.

Задание по направлению Android

По направлению Android задание было следующим:

Имея вводные данные, написать функцию, получающую список категорий (List Category), список характеристик (List Feature), и преобразующую их в один List элементов, и возвращающую его.
Правила формирования результирующего списка:
- Первый элемент связан с категорией (Category). Хранит в себе всю информацию о категории.
- Далее идут все элементы, связанные с характеристикой (Feature) относящиеся к данной категории.
- После последней характеристики, относящийся к открытой категории, идет элемент, сигнализирующий о том, что категория закончилась. Хранит в себе только CategoryId.
Количество элементов не ограничено.

Вводные данные:

// Класс категории
data class Category(
    val categoryId: Int,
    val name: String)

// Класс характеристики
data class Feature(
    val featureId: Int,
    val categoryId: Int,
    val title: String,
    var value: Int)

// Список всех доступных категорий можем получить методом
fun getCategories(): List<Category>

// Список характеристик для отображения можем получить методом
fun getFeatures(): List<Feature>

// Получаемые данными методами элементы не отсортированы

// Характеристика и категория связаны между собой полем
// val categoryId: Int

Моё решение

Итак, нам нужно вывести список категорий и характеристик. При этом элементы в списке должны находиться разные типы элементов: категория, характеристика, концевик категории (её ID).

Первое, что пришло на ум — List<Any>. Это плохое решение, ведь так в этот список можно положить вообще всё, что угодно.

Я посмотрел, что объединяет входные дата-классы. Воспользовавшись nullable-свойствами, я создал общий дата-класс. В названии его я буквально написал, что он содержит.

data class CategoryOrFeatureOrEndElement(
    val categoryId: Int,
    val categoryName: String? = null,
    val featureId: Int? = null,
    val featureTitle: String? = null,
    var featureValue: Int? = null
)

Объекты этого класса будут наполнять результирующий список.
Дальше ничего не интересного: я просто воспользовался вложенными циклами.

fun getCategoriesWithFeatures(categories: List<Category>, features: List<Feature>):
        MutableList<CategoryOrFeatureOrEndElement> {
    val categoriesWithFeatures = mutableListOf<CategoryOrFeatureOrEndElement>()

    for (category in categories) {
        categoriesWithFeatures.add(
            CategoryOrFeatureOrEndElement(categoryId = category.categoryId, categoryName = category.name)
        )

        for (feature in features) {
            if (feature.categoryId == category.categoryId) {
                categoriesWithFeatures.add(
                    CategoryOrFeatureOrEndElement(
                        featureId = feature.featureId,
                        categoryId = category.categoryId,
                        featureTitle = feature.title,
                        featureValue = feature.value
                    )
                )
            }
        }

        categoriesWithFeatures.add(
            CategoryOrFeatureOrEndElement(categoryId = category.categoryId)
        )
    }

    return categoriesWithFeatures
}

С помощью именованных аргументов конструктора класса, в список сначала добавляется категория, потом все соответствующие характеристики, затем ID категории. Такое довольно простое решение.

Небольшая оптимизация:

fun getCategoriesWithFeaturesOptimized(categories: List<Category>, features: List<Feature>):
        MutableList<CategoryOrFeatureOrEndElement> {
    val categoriesWithFeatures = mutableListOf<CategoryOrFeatureOrEndElement>()

    val mutableFeatures = features.toMutableList()

    for (category in categories) {
        categoriesWithFeatures.add(
            CategoryOrFeatureOrEndElement(categoryId = category.categoryId, categoryName = category.name)
        )

        val iterator = mutableFeatures.iterator()
        while (iterator.hasNext()) {
            val feature = iterator.next()
            if (feature.categoryId == category.categoryId) {
                categoriesWithFeatures.add(
                    CategoryOrFeatureOrEndElement(
                        featureId = feature.featureId,
                        categoryId = category.categoryId,
                        featureTitle = feature.title,
                        featureValue = feature.value
                    )
                )
                iterator.remove()
            }
        }

        categoriesWithFeatures.add(
            CategoryOrFeatureOrEndElement(categoryId = category.categoryId)
        )
    }

    return categoriesWithFeatures
}

В данном случае после добавления характеристики (feature) в итоговый список (categoriesWithFeatures), она удаляется из списка характеристик (mutableFeatures), поэтому следующая итерация цикла пройдёт быстрее, так как в списке будет меньше элементов.
Однако в данном случае необходимо создавать mutableFeatures (изменяемый дупликат списка features), что может быть неэффективно по памяти, если начальный список достаточно большой.
Эта оптимизация подходила бы, если входная функция возвращала изменяемый список:

fun getFeatures(): MutableList<Feature>

После участия в конкурсе я нашёл конструкции языка и методы, которые позволяют улучшить код. Например, вместо моего дата-класса больше подошёл бы Sealed Class с тремя потомками: Категорией, Характеристикой и ID категории.

Решение chatGPT

Я попросил chatGPT решить поставленную задачу, и вот что он написал:

data class CategoryWithFeatures(
    val categoryId: Int,
    val categoryName: String,
    val features: List<Feature>
)

fun combineCategoriesAndFeatures(categories: List<Category>, features: List<Feature>): List<CategoryWithFeatures> {
    val categoryMap = categories.associateBy { it.categoryId }

    val result = mutableListOf<CategoryWithFeatures>()
    var currentCategory: CategoryWithFeatures? = null

    for (feature in features) {
        if (currentCategory == null || feature.categoryId != currentCategory.categoryId) {
            // Создаем новую категорию, когда текущая категория закончена или еще не начата
            val category = categoryMap[feature.categoryId]
            if (category != null) {
                currentCategory = CategoryWithFeatures(category.categoryId, category.name, mutableListOf())
                result.add(currentCategory)
            }
        }

        // Добавляем характеристику к текущей категории
        currentCategory?.features?.add(feature)
    }

    return result
}

Моё решение лучше этого, потому что оно, как минимум, работает. Ура, моё решение лучше решения chatGPT, плюс самооценка !

Что же делает наш умный товарищ:

• пытается добавить элемент к неизменяемому списку (строка 24);

• пишет комментарии в решении, которое должно читаться без комментариев.

Хорошо, давайте закроем на это глаза. Закрыли, но решение всё ещё плохое: оно не соответствует поставленной задаче:

• Основная функция в итоге возвращает список объектов CategoryWithFeatures. Этот класс содержит данные категории и список характеристик. Всё это он запихал в один класс. Теперь нет отдельных элементов категории, характеристики и ID категории, которые должны быть в результирующем списке по условию задачи.

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

Вот, что мы в итоге получаем:

// Код всё ещё от chatGPT
fun main() {
    val categories = getCategories()
    val features = getFeatures()

    val combinedList = combineCategoriesAndFeatures(categories, features)

    // Выводим результат
    for (categoryWithFeatures in combinedList) {
        println("Category: ${categoryWithFeatures.categoryName} (ID: ${categoryWithFeatures.categoryId})")
        for (feature in categoryWithFeatures.features) {
            println(" - Feature: ${feature.title} (ID: ${feature.featureId}), Value: ${feature.value}")
        }
    }
}

Я также показал своё решение chatGPT и попросил его улучшить. Вот его версия моего решения:

data class CategoryOrFeatureOrEndElement(
    val categoryId: Int,
    val categoryName: String? = null,
    val featureId: Int? = null,
    val featureTitle: String? = null,
    var featureValue: Int? = null
)

fun groupCategoriesWithFeatures(categories: List<Category>, features: List<Feature>):
        List<CategoryOrFeatureOrEndElement> {
    val groupedFeatures = features.groupBy { it.categoryId }

    val result = mutableListOf<CategoryOrFeatureOrEndElement>()

    for (category in categories) {
        result.add(CategoryOrFeatureOrEndElement(category.categoryId, category.name))

        groupedFeatures[category.categoryId]?.forEach { feature ->
            result.add(CategoryOrFeatureOrEndElement(
                featureId = feature.featureId,
                categoryId = category.categoryId,
                featureTitle = feature.title,
                featureValue = feature.value
            ))
        }

        result.add(CategoryOrFeatureOrEndElement(category.categoryId))
    }

    return result
}

Мой дата-класс он оставил без изменений и поменял саму функцию. Теперь сначала с помощью функции groupBy создаётся Map<Int, List<Feature>>, где ключи — ID категории, значения — списки характеристик. Потом всё те же вложенные циклы, только теперь нужные характеристики не нужно искать, а просто брать из созданного Map.

В итоге:

• результат работы такой же;

• вложенные циклы остались;

• перед вложенными циклами появились: ещё один цикл от функции groupBy и дополнительная переменная;

• код стал короче, но, как по мне, его читаемость не изменилась.

Звонок другу

Не получив фидбека от организаторов конкурса, я попросил его у друга. Вместе с фидбеком я получил ещё один вариант решения:

// Возврат объекта с несколькими нуллабельными полями в качестве метки — это не очень хорошо
data class CategoryOrFeatureOrEndElement(
    val categoryId: Int,
    val categoryName: String? = null,
    val featureId: Int? = null,
    val featureTitle: String? = null,
    var featureValue: Int? = null
)

// Зачем возвращать MutableList, если можно вернуть просто List?
fun getCategoriesWithFeatures(categories: List<Category>, features: List<Feature>):
        List<CategoryOrFeatureOrEndElement> {
    val categoriesWithFeatures = mutableListOf<CategoryOrFeatureOrEndElement>()

    val featureMap = mutableMapOf<Int, List<CategoryOrFeatureOrEndElement>>()

    for (feature in features) {
        var mutableCategoryFeatures: MutableList<CategoryOrFeatureOrEndElement>? = null
        val categoryFeatures = featureMap[feature.categoryId]
        if (categoryFeatures != null) {
            mutableCategoryFeatures = categoryFeatures.toMutableList()
            mutableCategoryFeatures.add(CategoryOrFeatureOrEndElement(
                categoryId = feature.categoryId,
                featureId = feature.featureId,
                featureTitle = feature.title,
                featureValue = feature.value
            ))
            featureMap[feature.categoryId] = mutableCategoryFeatures
            continue
        }
        mutableCategoryFeatures = mutableListOf()
        mutableCategoryFeatures.add(CategoryOrFeatureOrEndElement(
            categoryId = feature.categoryId,
            featureId = feature.featureId,
            featureTitle = feature.title,
            featureValue = feature.value
        ))
        featureMap[feature.categoryId] = mutableCategoryFeatures
    }

    for (category in categories) {
        categoriesWithFeatures.add(
            CategoryOrFeatureOrEndElement(categoryId = category.categoryId, categoryName = category.name)
        )

        val featuresFromMap = featureMap[category.categoryId]

        categoriesWithFeatures.addAll(featuresFromMap!!)
        
        categoriesWithFeatures.add(
            CategoryOrFeatureOrEndElement(categoryId = category.categoryId)
        )
    }

    return categoriesWithFeatures
}

Я попытался переписать код, но в итоге сложность по времени получилась такая же. Пока что не придумал другого варианта.

Действительно, во втором цикле из-за функции addAll (которая циклически добавляет все элементы списка featuresFromMap) у нас снова получаются вложенные циклы. При этом читаемость кода снизилась.

К слову, весь первый цикл делает почти то же самое, что и функция groupBy. Разница в том, что groupBy вернёт Map<Int, List<Feature>>, а цикл — MutableMap<Int, List<CategoryOrFeatureOrEndElement>>.

Мне не нравится моя мапа на самом деле. Я добавил список не фичей, а этого класса только из-за того, что не хотел дополнительно забивать память потом. Хотя я, может быть, неправильно посчитал, и такой вариант ничем не отличается. Короче, в промышленном коде так делать не стоит.

Комментарий победителя конкурса и его решение

Давид Жубрёв, победитель в номинации «Изящный код», разрешил опубликовать его решение*:

fun getResultList() =
    getCategories().flatMap { category ->
        listOf(
            category,
            *getFeatures().filter { it.categoryId == category.categoryId }.toTypedArray(),
            category.categoryId
        )
    }

Рассмотрим, что здесь происходит. Метод flatMap в соответствии с лямбда-функцией преобразует каждый элемент списка категорий в List, где первый элемент — объект категории. Список характеристик фильтруется по ID категории и преобразовывается в массив. С помощью оператора * каждый элемент массива вкладывается в упомянутый List. Последний элемент List — ID категории.
После этого flatMap избавляется от вложенных списков и возвращает одномерный список всех элементов.

Хоть в результате и получается List<Any>, решение очень лаконичное и понятное, что идеально соответствует номинации. По временной сложности всё остаётся так же, но выглядит лучше. Если добавить сюда другую структуру данных, например, тот же Sealed Class, то будет, возможно, лучшее решение поставленной задачи.

Победитель прокомментировал конкурс и своё участие в нём:

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

Я очень люблю работать с коллекциями, поэтому решение быстро пришло в голову, минут 20-30 ушло на всё, включая миллион запусков кода, чтобы ну точно все работало)

В целом, было довольно интересно участвовать, да и конкурс весьма необычный оказался, на мой взгляд)

— Давид Жубрёв, Санкт-Петербург.

Спасибо за прочтение данной статьи! Буду рад узнать ваше мнение о конкурсе и представленных решениях :)