C++ and other lectures

assistant: Извините за предыдущую ошибку. Вы правы, что текущая реализация функции next_turn не гарантирует победу. Давайте попробуем найти оптимальную стратегию, учитывая ваши предложения. Итак, было 100 спичек, я взял 33, вы взяли 12. Осталось 55 спичек. На этом этапе, я могу взять от 1 до 24 спичек. Если я взял 3 спички, то останется 52 спички. Ваши возможные ходы будут от 1 до 6 спичек. В любом случае, я смогу забрать последнюю спичку. Давайте перепишем функцию next_turn с учетом этой стратегии: int next_turn(int total, int possible) { if (total == 1) { return 1; } if (total <= possible + 1) { return total - 1; } for (int i = 1; i <= possible; i++) { int remaining = total - i; int opponents_max = 2 * i; int optimal_choice = -1; for (int j = 1; j <= opponents_max; j++) { int next_remaining = remaining - j; int next_opponents_max = 2 * j; if (next_remaining <= next_opponents_max + 1) { optimal_choice = i; break; } } if (optimal_choice != -1) { return optimal_choice; } } // Если оптимальный ход недоступен, берем одну спичку и надеемся на ошибку противника return 1; } Теперь функция next_turn должна выбирать количество спичек, которое гарантирует победу, учитывая условие ограничения на количество спичек, которое можно взять, исходя из предыдущего хода противника. Если оптимальный ход недоступен, функция возвращает 1, чтобы взять одну спичку и надеяться на ошибку противника. user: Смотрите, на входных данных 10 9 вы берёте 9 спичек. Значит на следующий ход я выигрываю забирая последнюю. Ваша правильная стратегия тут будет такой: взять 2 спички и тогда что бы я ни взял от 1 до 4, ваши ответы будут такими: если я беру одну то вы берёте две, если я две то вы одну, если я три то вы две и если я четыре то вы одну. И таким образом во всех случаях вы побеждаете. Попробуйте поправить вашу программу чтобы она реализовала такую стратегию. assistant: Извините за ошибку в предыдущей реализации. Вы правы, моя стратегия была неправильной. Давайте попробуем еще раз. int next_turn(int total, int possible) { if (total == 1) { return 1; } if (total <= possible + 1) { return total - 1; } int remaining = total; int opponents_max = possible; int optimal_choice = -1; for (int i = 1; i <= possible; i++) { int next_remaining = remaining - i; int next_opponents_max = 2 * i; if (next_remaining <= next_opponents_max + 1) { optimal_choice = i; break; } } if (optimal_choice == -1) { optimal_choice = 1; } return optimal_choice; } Теперь функция next_turn ищет оптимальное количество спичек, чтобы взять исходя из условия ограничения на количество спичек, которое можно взять, исходя из предыдущего хода противника. Если оптимальный ход недоступен, функция возвращает 1, чтобы взять одну спичку и надеяться на ошибку противника. Эта реализация должна работать правильно на входных данных, которые вы указали. user: Но вы же снова при входе 10 и 9 берете 9, ничего не поменялось! assistant: Извините, я сделал ошибку в предыдущем коде. Давайте попробуем снова с исправленной версией функции next_turn: int next_turn(int total, int possible) { if (total == 1) { return 1; } if (total <= possible + 1) { return total - 1; } int my_turn; for (my_turn = 1; my_turn <= possible; my_turn++) { int opponent_max = 2 * my_turn; int remaining_after_my_turn = total - my_turn; int opponent_turn; for (opponent_turn = 1; opponent_turn <= opponent_max; opponent_turn++) { int remaining_after_opponent_turn = remaining_after_my_turn - opponent_turn; if (remaining_after_opponent_turn <= 2 * opponent_turn + 1) { break; } } if (opponent_turn > opponent_max) { return my_turn; } }

Благодаря моему бывшему студенту и коллеге Саше, который сейчас работает в Канаде, получил возможность поэкспериментировать с ChatGPT4. Ниже лог попытки использовать её для решения на языке C задачи HWF (это задача для первого курса). Ниже результаты выгрузки. user это я. assistant это нейросеть. --- user: Два игрока играют в интересную игру: изначально дано N спичек. Первый игрок берёт любое количество, но не все сразу спички. Теперь второй может взять не больше, чем вдвое больше чем первый. Далее первый берёт не больше чем вдвое больше второго. И так далее. Выигрывает тот, кто взял последнюю спичку Партия 1: 11 спичек. Первый берёт 4, второй может взять до 8 и берёт 7, победа. Запись партии: 11.4,7! Партия 2: 11.3,3,5! Партия 3: 11.3.2.1.1.1.1.2! Ваша посылка должна состоять из функции, которая по общему количеству оставшихся (total) и количеству допустимых к взятию (possible) спичек будет возвращать сколько спичек она хочет взять Разумеется, ваша функция всегда должна делать оптимальный ход Если оптимальный ход невозможен (все ходы плохи), разумно взять одну спичку и дать противнику шанс сделать ошибку int next_turn(int total, int possible) { // TODO: ваш код здесь } assistant: Вам нужно определить оптимальный ход для игрока, чтобы он смог выиграть игру, следуя условиям игры. Вот функция, которая реализует требуемую логику: int next_turn(int total, int possible) { if (total <= possible + 1) { return total - 1; // Выигрышный ход: забираем все спички, кроме одной } // Находим максимальное число спичек, которое можно взять, чтобы оставить оптимальное количество спичек противнику int max_matches_to_take = (total - 1) / (possible + 1); // Если все ходы приводят к поражению, берем одну спичку и надеемся на ошибку противника if (max_matches_to_take == 0) { return 1; } // Если возможно, берем максимально возможное количество спичек, чтобы оставить оптимальное количество спичек противнику if (max_matches_to_take <= possible) { return max_matches_to_take; } // В остальных случаях берем одну спичку и надеемся на ошибку противника return 1; } Функция next_turn определяет оптимальный ход для игрока на основе текущего состояния игры. Если оптимальный ход недоступен, игрок берет одну спичку и надеется на ошибку противника. user: Обратите внимание, что на каждый ход вы можете взять не более чем вдвое больше спичек, чем противник взял в предыдущем ходу. Кроме того, при входных аргументах 100 99 вы взяли 99 спичек и противник следующим ходом выигрывает. Предполагается, что выигрывать должны вы. Правильный ответ в таких условиях — взять три спички. assistant: Извините за недопонимание. Я учту условие о том, что можно взять не более чем вдвое больше спичек, чем противник взял в предыдущем ходу, и предложу исправленный код функции next_turn. int next_turn(int total, int possible) { for (int i = 1; i <= possible; i++) { int remaining = total - i; int opponents_max = 2 * i; if (remaining <= opponents_max + 1) { // Оставляем оппоненту невозможную ситуацию, гарантируя себе победу return i; } } // Если оптимальный ход недоступен, берем одну спичку и надеемся на ошибку противника return 1; } Теперь функция next_turn выбирает количество спичек, которое гарантирует победу, учитывая условие ограничения на количество спичек, которое можно взять, исходя из предыдущего хода противника. Если оптимальный ход недоступен, функция возвращает 1, чтобы взять одну спичку и надеяться на ошибку противника. user: Рассмотрим снова вход 100 99. Вы теперь берёте 33 спички. Следующим ходом противник берёт 12 спичек и это гарантирует ему в дальнейшем выигрыш при любой вашей стратегии. Чтобы вам это продемонстрировать и объяснить как переписать программу, давайте доиграем эту партию. Итак, было 100 спичек, вы взяли 33, я взял 12. Ваш следующий ход? Попробуйте учесть все варианты и выиграть партию.

Выложил очередную лекцию магистерского курса — первую в длинной серии про атомики. Сейчас начинается премьера, а через полтора часа лекция будет доступна для произвольного просмотра по разметке. https://youtu.be/JRUbzoVfkkw На этой лекции мы начнём с обстоятельной работы над ошибками. Надеюсь мне удалось сделать её и увлекательной и поучительной. Ну а дальше всё по обычной схеме. Введение в атомики это классика жанра и что-то там менять только портить. В этом году я заново снял замеры и их можно сравнить с 2019-м, они несколько поменялись (хотя в общем разница между Intel Gen8 и Intel Gen11 не фатальная). Закончим мы разбором thread local переменных.

Работа над ошибками (нужна помощь зала). В комментариях мой уважаемый подписчик Роман Митин указал что я на лекции показал неправильный пример bounded MPMC queue -- на самом деле извлечение и вставка там шли с одного конца и таким образом это был скорее bounded MPMC stack. Для многопоточной среды разница не так велика -- задачи ставятся в "очередь" и разбираются консьюмерами и в общем по циклограмме работы сложно отличить что там было. Но я решил сделать настоящую очередь и заодно улучшить тесты. И вот тут я обратил внимание что у меня было ещё несколько ошибок, пока в комментариях не замеченных. (1) В случае multi-producer делать wake_and_done надо на всех продьюсеров один раз иначе бывает так что консьюмеры повыходили но не все продьюсеры ещё закончили. (2) Саму функцию wait_and_pop надо делать с сигнатурой bool wait_and_pop(T &Data) чтобы понимать есть там что консьюмить или нет (3) Внутри консьюмеров условие должно выглядеть так: CondCons.wait(Lk, [this] { return !empty() || done(); }); if (empty()) return false; Даже если у нас сигнализирован done, задачи могут быть недоразобраны и поэтому критерий return false это только empty. (4) Внутри push признак done вообще проверять не надо т.к. это признако отработки всех продьюсеров. Там играет роль только full. (5) В интерфейсе необходим метод is_empty_and_done() чтобы по нему консьюмеры понимали когда начинать выходить. В общем это жесть. Пять ошибок в довольно простом коде и я не уверен что я ещё чего-то не пропустил. Полу-финальные версии bounded stack и bounded queue с тестами на то что они не теряют задач я выложил сюда: https://github.com/tilir/cpp-masters/blob/master/queues/classic_queue.cc https://github.com/tilir/cpp-masters/blob/master/queues/classic_stack.cc Нужна помощь зала в проверке не упустил ли я ещё чего-нибудь. Хочу в среду с этого начать лекцию и не хотелось бы облажаться ещё в чём-нибудь столь же тонком.

Выложил очередную лекцию магистерского курса, посвящённую многопоточным очередям. Это своего рода новация, в прошлом курсе этот материал читался иначе и не в полном объёме. Этой лекцией я искренне горжусь так как в ней есть и драматургия и композиционная согласованность: одно следует из другого, а концовка возвращает к началу. https://youtu.be/CMnRgnoWzmA Мы начнём с разговора о ментальной модели мьютекса. Далее мы попробуем собрать из имеющегося инструментария очередь, убедимся что у нас остались проблемы, решим их и соберём ещё одну. Далее мы сделаем важнейший шаг перейдя от очереди данных к очереди упакованных задач. Для этого нам придётся наладить каналы коммуникации с потоками, познакомиться с маршалингом исключений и рассмотреть несколько новых концепций по дороге. Но в итоге мы придём к цели. Или почти придём, следите за руками.

Выложил вторую часть многопоточности. В ней мы должны познакомиться со всем находящимся в наших руках классическим инструментарием (пока не залезая внутрь него). В первую очередь мы рассмотрим одноразовую инициализацию и разберём известный антипаттерн double-checked lock. Далее мы перейдём к идее условных переменных и введём понятия uniuque_lock, нотификаций и внезапных пробуждений. Потом нас ждёт много попыток понять что же происходит в нашем многопоточном приложении. Ну и под конец мы зароемся глубже в разделяемые и прочие виды блокировок. https://youtu.be/vVRNJjf1MCE

Выложил первую часть многопоточности. На этой лекции мы выходим на коду нашего курса: многопоточность во всех её проявлениях. Начнём мы с грунтования фундамента и разбора простых и фундаментальных вещей. Что такое область памяти? Что такое поток? Что такое гонка? Зачем нужен volatile? Что такое безопасность относительно многопоточности? Мы ответим на все эти вопросы. Также мы разберём основные проблемы проектирования для многопоточной безопасности: API races и deadlocks. Сейчас идёт премьера а после её окончания будет доступно видео с разметкой по эпизодам. https://youtu.be/xTpAJWe7ZD4

Всем привет. Потёр немного оффтопика про fixed-width типы (int8_t, int16_t и т.д.) из другой ветки, но я вижу у людей накипело и предлагаю для on-topic обсуждения эту ветку. Пока что моё нынешнее личное отношение такое: fixed-width типы это зло и любое их применение это ошибка. Но у меня действительно тут объективно слабовато с аргументацией. По пунктам из того что есть: (1) Если у вас есть 32-битная архитектура (например 32-битный ARM или RISCV) и вы использовали в программе int64_t, как компилятору и библиотеке это трактовать? Вы ждёте ошибку компиляции или вы ждёте int_least64_t и обработку по кускам с хранением в двух регистрах и т.д.? Если да то почему собственно и кто вам это обещал? (2) Что вы вообще хотите сказать используя такие типы? Что ваша программа не будет работать если тут не 64 бита? Что вы хотели бы чтобы тут было 64 бита? Что вам всё равно сколько тут бит но вы считаете себя умнее компилятора и вот соптимизировали для x86? В первом случае это static assert. (3) Люди недооценивают опасность (даже в случае если точные 64 бита есть) при переносе с платформы на платформу типов которые меняют статус в зависимости от дефайна. Рассмотрим две платформы на одной из которых int64_t определён в int, а на другой в long long. Допустим вы заводите битфилд такого типа. Вы понимаете последствия? С удовольствием послушаю что вы думаете на эту тему и может быть скорректирую своё мнение. Только пожалуйста вежливо.

Выложил лекцию по динамическому полиморфизму. https://youtu.be/_Jn7MAZYL2M Я долго ходил вокруг неё кругами и думал включать или нет в магистерский курс. В прошлом году попробовал прочитать не под запись, но тогда она скорее провалилась. Последний толчок был дан благодаря моему подписчику Нику Келбону, показавшему мне библитотеку AnyAny своего авторства: https://github.com/kelbon/AnyAny Я посмотрел и я понял что теперь я могу что-то рассказывать.

Выложил лекцию по умным указателям. Я очень старался не растягивать её в этом году на две части т. к. для магистрантов там не слишком много новизны. Поэтому некоторые вещи я пробежал очень быстро. Но при этом я также постарался её реорганизовать во-первых в явном виде рассмотрев и описав альтернативы владения, и вот тут я времени не жалел так как это очень важно. А во-вторых я связал её с аллокаторами и добавил систематический разбор "Санкелевских" кейсов. https://www.youtube.com/watch?v=OzqFXMDrrgk

Выложил лекцию по полиморфным аллокаторам. Отмотаем плёнку и попробуем выйти из тупика и изобрести аллокаторы ещё раз. Что то в процессе получится, что-то нет... https://youtu.be/QwuHX-VjhXI

Возвращаемся после перерыва к магистерскому курсу и первая лекция это лекция по аллокаторам. Она довольно странная так как в конце мы заходим в тупик, но в процессе там будет много интересного. https://youtu.be/5xN9bcdHggw

Приглашаем вас выступить на конференции C++ Russia 2023! В этом году конференция будет идти четыре дня: 11–12 мая в онлайне и 23–24 мая в офлайне в Москве. И вы можете выступить на ней. Что даст выступление на C++ Russia? — Развитие личного бренда и улучшение навыка публичных выступлений. — Возможность обсудить рабочие задачи в неформальной обстановке. — Билет на все конференции весны от JUG Ru Group. — Общение с комьюнити и экспертами Программного комитета. Можно выбрать любой формат — классический доклад, воркшоп, дискуссию или предложить что-нибудь свое. Вам помогут подготовиться, проведут репетиции, а после конференции вы получите запись в 4K на YouTube, чтобы поделиться ей с друзьями и коллегами. Выбирайте тему на сайте или предлагайте свои идеи и подавайте заявку на выступление до 20 февраля. Билеты на C++ Russia 2023 уже в продаже.

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

Выложил видео про twin trees. https://youtu.be/JoaNcwBVDGE Он продолжает традицию пересказов лекций Дональда Кнута. Я объясняю всё что нужно знать предварительно и показываю что-то связанное с реализацией. Получается в ту же тему но другой рассказ, более доступный для аудитории если это студенты. В данном случае я очень горжусь тем что сохранил и даже усилил драматургию: лекция выстроена в виде расследования и в конце всех ждёт внезапный срыв покровов. Оригинал лекции от проф. Кнута можно найти здесь: https://www.youtube.com/watch?v=zg6YRqT4Duo

Итогов года пост. Несмотря на некоторые всем известные обстоятельства, мне кажется удалось много. 1. Я записал вторую часть бакалаврского курса: https://www.youtube.com/playlist?list=PL3BR09unfgciJ1_K_E914nohpiOiHnpsK Громадное спасибо Дмитрию Рябцеву и Владиславу Белову, без них это было бы невозможно. 2. Я записал первую часть нового магистерского курса: https://www.youtube.com/playlist?list=PL3BR09unfgcgf7R88ZQRQqWOdLy4pRW2h Громадное спасибо Юлию Тарасову, без него это было бы невозможно. Также спасибо компании Синтакор и группе компаний Yadro которые не просто взяли мою команду на работу, но и разрешили мне продолжать выделять время на преподавание, выделили аудиторию в офисе, помогли с кафедрой в МФТИ и даже набрали несколько новых студентов этого года в интерны. Кроме того в этом году я впервые выступил на C++Russia: https://www.youtube.com/watch?v=YJd6Ig4ihJ0&t=75s И записал допглавы к этому выступлению: https://www.youtube.com/watch?v=-aE1hD9OWRk Также я заснял ряд дополнительных видео. Особенно удачным, как мне кажется, получился допсеминар про SIMD: https://youtu.be/DHai10xqySU В новом году хочется всем пожелать быстрого появления 23-го стандарта в компиляторах и много новых интересных задач. Пусть программирование и математика сплачивают нас даже там, где политика разделяет. В комментариях можно и нужно поздравлять с Новым Годом меня и друг друга и вспоминать чем он вам запомнился в профессиональном плане, но пожалуйста давайте не трогать политику и религию )))

Итак, последняя в этом семестре лекция магистерского курса. Мне кажется что наконец-то я рассказал диапазоны правильно. Поговорим о кешировании, pull model и её проблемах, константной итерируемости и многом другом. Также заглянем внутрь некоторых нетривиальных отображений. https://youtu.be/CVMDB3c3too

Я и не заметил, что у меня тысяча подписчиков в телеграме. Всем спасибо, это важная веха для моего телеграм-канала. Расскажите, а вы хотите приуроченный к этому числу специальный выпуск и если да то о чём? Можете писать в комментарии темы или лайкать написанные. До НГ не обещаю, но всё возможно ))

Ещё один вопрос по диапазонам. Надеюсь после моей лекции все устыдились и ответы будут обстоятельными и интересными. Есть код: struct S { int x, y; }; std::vector<S> v{{1, 0}, {2, 0}, {4, 0}}; auto it = ranges::find(v | views::transform(std::mem_fn(&S::x)), 4).base(); Что тут происходит: я проецирую вектор на инты, ищу там 4 и прошу итератор (base) на исходный вектор. https://godbolt.org/z/hhWaPsjsj Он не работает, но GCC и ToT Clang говорят разные вещи. У clang там просто ranges::dangling (хотя как может провиснуть итератор на существующий вектор?) У gcc там нечто более интересное. Опять таки исходный библиотечный код один и тот же. Как бы вы это исследовали? Кто тут прав?