Одно поколение генетического алгоритма

Генетический алгоритм улучшает популяцию решений-кандидатов так же, как эволюция: отбирает приспособленных родителей, скрещивает их и добавляет случайные мутации. Здесь кандидаты — битовые строки, а приспособленность — число единиц (задача OneMax).

Чтобы алгоритм можно было проверить, все случайные выборы передаются на вход. Из N строк (N чётно) постройте N потомков парами. Для пары k = 0, 1, …, N/2 - 1:

Отбор: parent1 — победитель турнира tournaments[2k], а parent2 — победитель tournaments[2k + 1]. Турнир [i, j] выигрывает та из строк population[i] и population[j], в которой больше единиц; при равенстве выигрывает population[i].
Скрещивание в точке c = crossover_points[k]: потомок 2k = parent1[0:c] + parent2[c:] и потомок 2k + 1 = parent2[0:c] + parent1[c:].

Затем примените каждую мутацию [child, position] по порядку, инвертируя этот бит этого потомка.

Реализуйте ga_generation(population, tournaments, crossover_points, mutations).

Входные данные

population: N битовых строк одинаковой длины L.

tournaments: N пар индексов популяции.

crossover_points: N/2 точек разреза, каждая от 1 до L - 1.

mutations: Пары [child, position] (могут отсутствовать).

Выходные данные

Верните N потомков по порядку.

Ограничения

2 ≤ N ≤ 200 (N чётно), 2 ≤ L ≤ 64

0 ≤ число мутаций ≤ 1 000

Примеры

Пример 1

Ввод:
population = ["0000", "1111", "1100", "0011"]
tournaments = [
    [0, 1],
    [2, 3],
    [1, 2],
    [0, 3]
]
crossover_points = [2, 1]
mutations = [
    [0, 0]
]

Ожидаемый вывод:
["0100", "1111", "1011", "0111"]

Пояснение

Пара 0: "1111" побеждает "0000", а у "1100" и "0011" поровну единиц, поэтому побеждает первая. Разрез после 2 битов даёт "1100" и "1111". Пара 1: родители "1111" и "0011", разрез после 1 бита: "1011" и "0111". Наконец у потомка 0 инвертируется бит 0: "0100".

Пример 2

Ввод:
population = ["10", "01"]
tournaments = [
    [0, 1],
    [1, 0]
]
crossover_points = [1]
mutations = []

Ожидаемый вывод:
["11", "00"]

Пояснение

В обеих строках по одной единице, поэтому каждый турнир выигрывает первый индекс: parent1 = "10" и parent2 = "01". Разрез после 1 бита даёт "11" и "00".

Ссылки

Запустите примерные тесты, чтобы проверить код без отправки.

Пример 1 Не запущено

Ввод:

population = ["0000", "1111", "1100", "0011"]
tournaments = [
    [0, 1],
    [2, 3],
    [1, 2],
    [0, 3]
]
crossover_points = [2, 1]
mutations = [
    [0, 0]
]

Ожидаемый вывод:

["0100", "1111", "1011", "0111"]

Ваш вывод

Пример 2 Не запущено

Ввод:

population = ["10", "01"]
tournaments = [
    [0, 1],
    [1, 0]
]
crossover_points = [1]
mutations = []

Ожидаемый вывод:

["11", "00"]

Ваш вывод

При отправке также выполняются ещё 4 скрытых теста. Если код не пройдёт один из них, вы увидите этот тест. Решите задачу, чтобы увидеть все.

Онлайн-компилятор Kotlin (Котлин)

Write, compile, run, and debug Kotlin code online in a full-featured browser IDE. Work with multiple files, save your workspace, and collaborate in real time.

Версия

Предустановленные библиотеки

🚀 71,457 всего выполнений (576 в этом месяце)

Вывод

Практикуйте Kotlin на задачах

Решайте задачи прямо в редакторе: запускайте тесты, отправляйте решение и получайте AI-рецензию.

Все задачи на Kotlin

Легко

Rectangle Perimeter

Compute the perimeter of a rectangle from its sides.

Вы освоите АрифметикаВозвращаемые значения

BeginnerLearning-pathVariables

Посмотреть решения (12)

Легко

Distance Between Points

Compute the straight-line distance between two points.

Вы освоите Теорема ПифагораКвадратные корни

BeginnerFunctionsLearning-pathmath

Посмотреть решения (7)

Легко

Days in a Month

Return how many days a month has, including leap years.

Вы освоите Правила календаряВспомогательные функции

BeginnerConditionsFunctionsLearning-path

Посмотреть решения (6)

Легко

Среднее из трёх

Вычислите среднее трёх целых чисел.

Вы освоите АрифметикаДеление

BeginnerLearning-pathVariables

Посмотреть решения (6)

Легко

Скалярное произведение двух векторов

Перемножьте два вектора поэлементно и сложите результаты — это основная операция любого нейрона.

Вы освоите ВекторыСкалярное произведение

Нейронные сетиискусственный интеллектмашинное обучение

Посмотреть решения (4)

Легко

Largest of Three

Pick the largest of three numbers without a built-in max.

Вы освоите СравненияСочетание условий

BeginnerConditionsLearning-path

Посмотреть решения (4)

Легко

Проверка на простое число

Определите, является ли число простым.

Вы освоите ДелимостьОптимизация циклов

BeginnerLoopsNumbersStudent-beginner

Посмотреть решения (3)

Легко

Number Triangle

Build a triangle of increasing numbers.

Вы освоите Растущие строкиСчётчик между строками

BeginnerLearning-pathNested-loopsPatterns

Посмотреть решения (3)

Легко

Число Армстронга

Проверьте, равно ли число сумме его цифр, возведённых в степень, равную количеству цифр.

Вы освоите Выделение цифрСтепени

BeginnerNumbersStudent-beginner

Посмотреть решения (3)

Легко

Row Sums

Add up every row of a grid.

Вы освоите Двумерные спискиВложенные циклы

BeginnerGridsLearning-path

Посмотреть решения (3)

Легко

Min and Max Together

Find the smallest and largest value in one pass.

Вы освоите Один проходНесколько возвращаемых значений

ArraysBeginnerFunctionsLearning-path

Посмотреть решения (3)

Легко

Подсчёт пар с заданной суммой

Посчитайте количество пар позиций, значения которых в сумме дают целевое число.

Вы освоите Пары индексовБез двойного счёта

ArraysBeginnerLearning-pathNested-loops

Посмотреть решения (3)

🧩 Об этом онлайн-исполнителе Kotlin

Исполнитель Kotlin CodeUtility позволяет писать, компилировать и запускать код Kotlin прямо в браузере - без установки, IDE или настройки SDK. Он использует реальные компиляторы Kotlin, работающие в изолированных песочницах, обеспечивая безопасный и достоверный опыт выполнения.

Этот инструмент поддерживает несколько версий Kotlin - 1.6, 1.9 и 2.1 - так что вы можете изучать изменения синтаксиса, проверять совместимость кода и экспериментировать с современными возможностями языка, такими как корутины, data-классы и sealed-интерфейсы.

Он идеально подходит для студентов, изучающих основы Kotlin, Android‑разработчиков, экспериментирующих с фрагментами кода, или бэкенд‑инженеров, проверяющих логику в среде JVM, не покидая браузер.

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

Больше, чем просто запуск кода

В одном редакторе есть всё для работы: несколько файлов, изолированный терминал, библиотеки для выбранной версии, сохранение проектов, общий доступ по ссылке и совместная работа в реальном времени.

Как пользоваться редактором

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

Выберите версию и отредактируйте текущий файл или откройте другой файл рабочего пространства.
Запустите код, при необходимости введите данные в терминале и просмотрите сохранённую историю запусков.
Используйте библиотеки, инструменты рабочего пространства, общий доступ и чат, когда для задачи требуется несколько фрагментов кода.

Начать кодирование

ВерсияПеред запуском выберите среду выполнения. Установленные библиотеки относятся к выбранной версии языка.
В списке открытых файлов показаны текстовые файлы рабочей области. Выберите файл, чтобы открыть его во вкладке редактора.
Кнопка «Запустить» выполняет активный файл и предоставляет программе доступ к рабочей области.
Кнопка «Остановить» завершает выполнение программы до истечения лимита времени.
Расширенный режим открывает IDE с файловым проводником и терминалом с изменяемым размером.

Рабочее пространство и библиотеки

Команда «Новый файл» создаёт файл в выбранном каталоге и открывает его в редакторе.
Команда «Новая папка» создаёт каталог в рабочей области.
Команда «Загрузить файлы» добавляет в каталог один или несколько безопасных файлов.
Команда «Скачать» сохраняет файл или архив каталога на вашем устройстве.
Команда «Копировать» создаёт копию файла или каталога рабочей области.
Команда «Переименовать» изменяет имя файла и обновляет его открытую вкладку и историю.
Команда «Переместить» переносит элемент; файлы и каталоги также можно перетаскивать.
Команда «Удалить» удаляет элемент после подтверждения и закрывает открытую вкладку редактора.
Раздел «Предустановленные библиотеки» показывает пакеты, включённые в выбранную среду выполнения.
Кнопка «Добавить библиотеку» устанавливает личный пакет для вашей учётной записи и выбранной среды выполнения.

Терминал и помощь

История выполнения открывает предыдущие и следующие сохраненные результаты.
Кнопка «Копировать вывод» помещает текст терминала в буфер обмена.
Команда «Очистить вывод» после подтверждения удаляет сохранённые результаты выполнения.
Функция «Объяснить» анализирует активный код и кратко описывает его работу.
Раздел «Недавние» показывает последние объяснения и результаты.
В настройках можно изменить шрифты, темы и набор кнопок панели инструментов.

Обмен и сотрудничество

Функция «Поделиться» публикует текущий файл, каталог или всю рабочую область как снимок либо живую рабочую область. Вы управляете доступом по ссылке и правами на сохранение изменений.
Журнал показывает сохранённые действия соавторов в общей рабочей области.
Общий чат позволяет вошедшим в систему участникам отправлять сообщения, упоминать людей, делиться блоками кода и видеть участников, находящихся в сети или печатающих сообщения.
Совместная работа в реальном времени показывает курсоры соавторов и сохранённые обновления файлов. Пользователи с доступом только для просмотра могут загрузить последнюю версию или сохранить временные изменения у себя.

Квоты и лимиты

Один запуск на сервере может длиться не более 20 секунд. Чтобы завершить его раньше, нажмите «Остановить».
Для каждой рабочей области и языка доступно до 100 файлов, 100 каталогов и 10 МБ хранилища.
Размер одного файла ограничен 1 МБ, а глубина каталогов - пятью уровнями. Эти ограничения распространяются и на файлы, созданные программой.
Для каждой учётной записи и среды выполнения можно установить до 10 личных пакетов.
Снимки общих ресурсов могут содержать до 100 файлов, 1 МБ каждый файл и общий размер 2 МБ.
К одной общей рабочей области можно пригласить до 25 человек; права доступа и сохранения настраиваются отдельно.
В общем чате сообщение может содержать до 2000 символов, а история - до 10 000 сообщений.
Ограничения действуют и во время выполнения кода. Операции, превышающие лимит количества файлов, размера, хранилища или глубины вложенности, безопасно отклоняются.

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

💡 Справочник по основам Kotlin для начинающих

1. Объявление переменных и констант

В Kotlin val используется для неизменяемых переменных, а var - для изменяемых.

val name: String = "Alice"
var age: Int = 30
val pi = 3.14  // тип выводится автоматически

// Константы
const val MAX_USERS = 100

2. Условия (if / when)

Используйте выражения if или when для нескольких веток.

val x = 2
if (x == 1) {
    println("Один")
} else if (x == 2) {
    println("Два")
} else {
    println("Другое")
}

when (x) {
    1 -> println("Один")
    2 -> println("Два")
    else -> println("Другое")
}

3. Циклы

Используйте for, while и do-while для итераций.

for (i in 0..2) {
    println(i)
}

var n = 3
while (n > 0) {
    println(n)
    n--
}

4. Массивы

Kotlin поддерживает массивы через функцию arrayOf().

val numbers = arrayOf(10, 20, 30)
println(numbers[1])

5. Работа со списками

Используйте mutableListOf для динамических списков.

val nums = mutableListOf(1, 2, 3)
nums.add(4)
nums.removeAt(0)

for (n in nums) {
    print("$n ")
}

6. Ввод/вывод в консоль

Используйте readLine() для ввода и println() для вывода.

print("Введите ваше имя: ")
val name = readLine()
println("Привет, $name")

7. Функции

Функции объявляются ключевым словом fun с необязательным возвращаемым типом.

fun add(a: Int, b: Int): Int {
    return a + b
}

println(add(3, 4))

8. Отображения (Map)

mutableMapOf хранит пары ключ-значение.

val ages = mutableMapOf("Alice" to 30)
println(ages["Alice"])

9. Обработка исключений

Используйте try, catch и finally для обработки ошибок.

try {
    val result = 10 / 0
} catch (e: ArithmeticException) {
    println("Ошибка: ${e.message}")
}

10. Работа с файлами

Используйте File из java.io для операций с файлами.

import java.io.File

File("file.txt").writeText("Привет, файл")
val text = File("file.txt").readText()
println(text)

11. Работа со строками

Строки в Kotlin поддерживают множество методов и интерполяцию.

val text = "Привет, мир"
println(text.length)
println(text.substring(0, 5))
println(text.contains("World"))

12. Классы и объекты

Классы в Kotlin лаконичны и поддерживают конструкторы по умолчанию.

class Person(val name: String) {
    fun greet() = println("Привет, я $name")
}

val p = Person("Alice")
p.greet()

13. Безопасность null

Kotlin различает типы, допускающие null, и не допускающие. Используйте ? и ?: для безопасности.

val name: String? = null
println(name?.length ?: 0)