Devdays Весна 2017

Материал из CSC Wiki
Перейти к:навигация, поиск

Результаты

Valgrind для CLion 227.17
Чит-программа 206.40
Стилизация текста 198.40
Фурье-термометр 189.70
Сartoon Faces 180.11

Темы проектов

Чтобы править эту страницу, нужно залогиниться в Sewiki. Тогда сверху будет кнопочка "править". Если у вас нет учётной записи - напишите Мише Кольцову желаемый логин.

Редактировать wiki одновременно нескольким людям стоит осторожно: после внесения правки проверьте, что она действительно сохранилась.

Проекты нумеруются автоматически. Можно вписывать свои идеи проектов в порядке, отличном от "первый вписал - меньше номер".

Сделаем чит-программу или бота для старой компьютерной игры

Для популярных компьютерных игр энтузиасты делают всякие программы:

-ботов, которые играют за тебя;

-примочки, которые помогают в игре, типа дополнительных кнопок;

-альтернативные игровые клиенты, которые позволяют игрокам подключаться к альтернативным серверам;

-читерские программы, которые позволяют получать преимущество в игре (стрелять точно во врагов, видеть всю карту, ...);

-crack-и, которые подбирают серийные номера для бесплатной игры.

Все эти программы запускаются отдельно от игры, но каким-то образом влияют на происходящее в игре. Мне интересно понять, как это вообще происходит.

Идея такая: давайте возьмём какую-нибудь старую игру. Скажем, года до 2003, а то в современных играх античит системы накручивают сильно. Плюс, некоторые старые игры имеют открытый исходный код движка.

И сделаем для этой игры какую-нибудь программу, которая позволяет получить преимущество в игре (например: wallhack\speedhack для counter-strike 1.6, maphack для warcraft 3, бот для diablo 2).

Предложил: Михаил Кольцов

Анализ данных применительно к игре Dota 2

Недавно на kaggle я наткнулся на датасет с матчами многопользовательской игры Dota 2. В нём для каждого матча есть информация об игроках, о ходе игры, чат и всякое разное. Можно попробовать поанализировать, какие факторы влияют на успех\неуспех игрока.

Или посмотреть, как соотносятся фразы игрока в чате с его реальной пользой в игре: верно ли, что человек, который всех кроет матом, на самом деле играет лучше других?

Ожидаемый результат работы: какая-то новая информация про поведение игроков. Год назад меня поразила статья Masters of Control: Behavioral Patterns of Simultaneous Unit Group Manipulation in StarCraft 2, которая указывает на факторы, отделяющие хороших игроков от плохих. Я уверен, что тут море возможностей.

Замечу, что уже есть сайт, собирающий статистику по играм: dotabuff.

Предложил: Михаил Кольцов

WebAssembly 2027

Сейчас разрабатывается стандарт WebAssembly, который позволит (как многие надеятся) достичь скорости native-кода (считай, ассемблер) прямо в браузере. Недавно был достигнут консенсус между разработчиками популярных браузеров насчёт того, как будет выглядеть этот стандарт.

Выглядит это многообещающе. Я считаю, что в будущем очень много сервисов, которыми мы пользуемся с помощью desktop-приложений, перейдут в браузер. Браузер станет новой операционной системой для обычных людей.

Давайте подумаем, что можно сделать с помощью этой новой технологии. Посмотрим незашоренным взглядом в будущее, в 2027 год: что нас ждёт?

Ожидаемый результат: проект сервиса или сервисов, которые будут функционировать в 2027 году, и которые станут возможными благодаря скорости WebAssembly.

Предложил: Михаил Кольцов

GitHub security assessment

Есть такой сайт - HackerOne. На нём компании размещают свои страницы, а пользователи могут туда посылать security-related баги в продуктах этих компаний. Компании платят деньги пользователям, которые нашли крутые баги.

Там же есть страница у GitHub. На странице указано, за какие баги можно получить награду. Например, DDoS и social engineering запрещены.

Давайте посидим и за хакатон найдём какой-нибудь баг в гитхабе. Получим долларов пачку. Почему именно гитхаб? Я думаю, это близкий для каждого разработчика продукт. От его работоспособности зависят многие люди. Например, если будет какая-то уязвимость, позволяющая удалять из чужого репозитория что-нибудь -- это очень серьёзно. Чем серьёзнее проблема, тем больше денег дают.

Хочется подойти к проблеме с программистской стороны. Многие начинающие хакеры используют существующие утилиты для проведения экспериментов (например, для автоматического сканирования сайта). Более продвинутые хакеры пишут скрипты на python. А мы с вами можем написать всё что угодно на том же python!

Ожидаемый результат: найденный баг в github, одобренный представителями компании.

Предложил: Михаил Кольцов

Derived class debugging

Solving YoYo problem. Предлагается взять код из некоторой иерархии наследования, где логика разнесена по разным уровням наследования. Разработать некоторый фреймворк (на крайний случай, пара скриптов на модификацию исходников и пара на то, как как их встроить в популярные IDE) который позволяет видеть весь код на одном экране, без прыгания по уровням иерархии наследования.

Предложил: Кравцун Андрей

Templates overhead in C++ STL

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

  • во-первых, итераторы по стандартным контейнерам в ошибках компиляции почти полностью выдают детали своей реализации.
  • во-вторых, CRTP не делало жизнь проще.

Предлагается парсить ошибки компилятора, приводя реальные типы к человечным описаниям этих типов в коде.

Предложил: Кравцун Андрей.

Генерация сложных тестов к олимпиадным задачам

Берём из какого-нибудь официального соревнования по программированию какую-нибудь задачу с тестами, чекером и подходами участников. Пытаемся сгенерировать тест, на котором упадёт как можно больше решений. Будет круто, если какое-то AC решение упадёт. Ещё круче, если авторское решение упадёт.

Генерировать генетическими алгоритмами. Нужно будет написать всё для запуска решений участников.

Предложил: Антон Гардер

Бронирование места на ближайшей платной парковке

Просто много покодить.

Хотим сделать сеть платных парковок. Через веб-интерфейс владелец парковки может добавлять-удалять свои парковки, менять им параметры. В мобильном приложении предлагаются ближайшие парковки с свободными местами, можно оплатить и забронировать место.

Java/Python, Android

Предложил: Антон Гардер

Some considerations about NUMA & HPC

Non-uniform memory access (NUMA/ccNUMA) - интересная архитектура, значительно облегчающая масштабирование. Однако, когда дело доходит до высокопроизводительных вычислений, она может стать узким местом.

Хотелось бы иметь библиотеку, позволяющую абстрактно

  • 1. определять положение устройства и памяти
  • 2. производить аллокации и явные трансферы памяти на указанных узлах
  • 3. облегчающие менеджмент потоков (миграции потоков между узлами нарушает локальность памяти)
  • 4. (опционально) довести этот же функционал на уровень устройств в OpenCL

tags: c/c++, PCIe topology, linux api, processor affinity, (+OpenCL)

P.S. необходимо найти сервер с NUMA/эмулятор для тестирования.

Автор: Павел Бегунков

Yet another OpenCL memory optimizations & architecture features

OpenCL для NVidia является прямым конкурентом (e.g. CUDA), поэтому NVidia придерживает различные архитектурные фичи для CUDA. Хотялось бы протянуть некоторые возможности видеокарт NVidia для использования в OpenCL. На повестке:

tags: Cuda, OpenCL, c/c++

P.S. По поводу (1) слышал, что можно внедрить их IL в OpenCL с помошью inline asm. Понятия не имею реализуемо ли (2).

Автор: Павел Бегунков

compiler improvements

Как-то давно заметил, что мейнстримовые c/c++ компиляторы не умеют оптимизировать записи по out-dependency даже в самых простых случаях. Можно было бы законтрибутить (точнее попробовать) в один из них (i.e. gcc or clang) подобную фичу. Также можно обратить внимание на некоторые оптимизации техник rvo/nrvo.

tags: с/с++, compiler, clang/gcc

Автор: Павел Бегунков

Фильтрация заполненных пауз в видеозаписях

Существует множество статей, посвященных задаче распознавания заполненных (хезитационных?) пауз в речи. Хотелось бы найти и приспособить одно из существующих решений для фильтрации видеозаписей, воспроизводимых из браузера.

Что конкретно хочется сделать:

  • Либо найти готовую библиотеку, которая умеет распознавать звуки-паразиты в аудиодорожке, либо самому построить "распознаватель" по материалам из статей. Найти что-то готовое у меня почему-то не вышло, но зато в каждой второй статье по данной теме указывается, на каком из открытых корпусов обучались авторы.
  • Реализовать сервер, который бы принимал ссылку на видео с того же ютуба, кусками скачивал его аудиодорожку (при помощи этого, например), размечал её и отправлял разметку пользователю. Результаты запросов кешируются, а разметки, относящиеся к разным кускам одного и того же видео склеваются.
  • Небольшой плагин для хрома, который бы общался с сервером и скипал раздражающие куски видео, эксплуатируя api ютуба.

Предложил: Миша Чернявский


Фурье - термометр

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

Реализовать предлагается в виде приложеньки на андроиде.

Предложил: Симиютин Борис

Game Network Engine

Есть ряд статей на тему реал тайма, физики + мультиплеер http://gafferongames.com/. Предлагается на основе этих статей написать собственную библиотеку и провести сравнительный анализ с уже существующими библиотеками.

tags: c/c++, multithreadings, network, os

Предложил: Доронин Олег

Textbook to TeX

Уверена, что среди нас остались люди, кто по прежнему домашку в тетради может написать быстрее, чем в ТеХе. Но условия часто требуют именно ТеХ формат. Для таких людей, оказавшихся в такой ситуации, подойдёт конвертатор из фотографии решения в исходник теха (чтобы можно было вставить в свой ТеХ файл, что-то подправить и т.д.). Знаю, что я не первопроходец в этой теме, и существует много решений (например https://github.com/falvaro/seshat ), распознающих математический язык -- но хорошего приложения по сути нет. Или можно даже сделать телеграм-бота. Ты ему фото домашки по матлогике - он тебе код в ТеХе!

Предложила: Лапицкая Людмила

Литературный Питер

Мы живем в городе, который был много раз описан в произведениях великих классиков; проходим мимо зданий, мостов и парков, увековеченных поэтами; гуляем по улицам, по которым гуляли герои произведений Пушкина, Гоголя, Достоевского и прочих. Проблема в том, что среднестатистический обыватель об этом может не знать. Идея такая: написать приложение, которое в зависимости от вашего местоположения будет выдавать на карте метки, связанные с "литературным" прошлом города: может быть эта местность была описана в каком-то произведении, или где-то жил или работал кто-то из классиков, и т. п. Все эти метки хотелось бы уметь автоматически объединять в маршруты (вдохновлена я была маршрутом от Яндекса https://tjournal.ru/37074-yandeks-nanyos-na-kartu-peterburga-mesta-deistviya-romana-prestuplenie-i-nakazanie), а так же учитывать предпочтения пользователя, подкидывать ему "интересные" маршруты. Хотелось бы как-то автоматизировать процесс поиска и нанесения на карту маршрутных меток (например поиск в текстах произведения ключевых слов, пример: Летний сад А.Ахматовой), а так же поддерживать ручное редактирование и добавление их (так как не из всех литературных произведений можно автоматически выявить точные географические места).

Java, Android (для мобильного приложения, но можно и десктопную версию, тогда JavaScript)

Предложила: Тищенко Олеся

Программирование - детям

Все мы знаем, что без программирования - никуда, более того, даже совсем маленькие дети это знают. Пройдет десяток лет, и программировать люди будут учиться примерно тогда же, когда читать(если не раньше). Однако, объяснить детям какие-то сложные парадигмы ЯП - задача довольно трудная (наверное, многие школьные учителя с ней сталкиваются). Предполагается, что дети лучше усваивают информацию в виде игры. Идея: придумать игру для обучения детей программированию.

Вдохновлена я была LegoMindstorms(https://www.lego.com/ru-ru/mindstorms), где написание команд для робота предполагает по сути комбинацию прямоугольников, стрелочек и прочих примитивов и не требует умения программировать вообще. Но, конечно, не каждый учитель сможет притащить на урок лего-робота, да и к основной цели (понимать код) это не приведет. Поэтому это должно быть визуальное приложение - легкая игра, в которой ребенок задает героя, задает ему навыки, и так далее визуально или на командами на естественном языке: а результаты его действий в виде кода на заранее заданном ЯП отображаются в окошке рядом (тут я имела ввиду что-то вроде RoboCode http://robocode.sourceforge.net/ по оформлению, только адаптированного специально для образовательных целей). Для учителя должна быть возможность добавлять к приложению уроки: задания, тесты, и так далее. Начать предлагается с какого-то одного ЯП - на ваш выбор.

Предложила: Тищенко Олеся

Больше рефакторинга к трону C++

Во время работы над дз по C++ я столкнулась с багами в автоматически сгенерированном QtCreator'ом коде. Например, QtCreator не умеет по-человечески выносить определение метода за пределы класса (генерируется некорректный код). У Clion, насколько я поняла, в принципе нет такого типа рефакторинга. Предлагается написать плагин, реализующий адекватный рефакторинг для этого и/или каких-нибудь других use case'ов.

Автор: Аня Явейн

Автоматическая векторизация кода на Python или R

Автоматическая векторизация кода -- оптимизация, применяемая в компиляторах, например, в Clang (http://llvm.org/devmtg/2014-02/slides/golin-AutoVectorizationLLVM.pdf). R и Python обладают большими возможностями, связанными с векторизованными вычислениями. Некоторый код можно бесплатно и безболезненно векторизовать, тем самым улучшив его производительность. Задача состоит в статической обработке кода и поиске мест (циклов), к которым можно было бы применить данную оптимизацию.

Автор: Святослав Грязнов (делегировано Ане Явейн)

Агрегатор рецептов

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

Предложила: Мухина Анжелика


Kaggle Competitions

Сейчас многие HR в компаниях отбирают кандидатов по ключевым словам типа ШАД, ACM ( и другое олимпиадное) и Kaggle (https://www.kaggle.com/competitions). Скоро нам придется искать себе работу, поэтому предлагаю начать заботиться об этом сейчас.

Предполагается взять какой-нибудь компетишен и попробовать его зарешать. Понятно дело, что надо будет очень хорошо подумать, прежде чем делать. Но зато, решая такую задачу можно будет видеть свой прогресс на лидерборде. Единственный минус - всего 5 сабмишенов в сутки(.

tags: Python

Предложила: Малютина Екатерина

Cartoon faces

Сейчас очень бысто набирают популярность приложения, которые как-то изменяют твое лицо. Либо это состаренность/молодость, либо это пририсовка к тебе ушей/усов и прочего. Хотелось бы сделать, что-то похожее на это.

tags: Python

Предложила: Малютина Екатерина


Valgrind Memory Analyzer for CLion

Довольно часто мне приходится переключатся между CLion и QtCreator, т.к в CLion до сих пор не добавили Valgrind Memory Analyzer (как можно без нее писать C++ код без утечки памяти?!). Судя по ответу на запросы пользователей (https://youtrack.jetbrains.com/issue/CPP-548) не скоро появится такая фича. Давайте напишем свою реализацию. Понимаю, что за 3 дня написать свой valgrind уж очень непростая задача. Если тоже так считаете, то можно для начала написать хотя бы обертку над обычным valgrind'ом (но не такую https://github.com/montao/clion-valgrind), с форматированием вывода (сортировка по ошибкам и warning'ам и т.д.), т.к слишком много лишнего выводится (действительно это лишняя информация начинающему программисту).

tags: C++, bash

Предложил: Ёров Собир

Стилизация текста

В прошлом семестре в одном из НИРов решалась задача "Определение авторства по тексту" при помощи метода word2vec. Давайте попробуем сделать обратное. Возьмем несколько очень колоритных героев, н-р: Онегин, Каренина, Конфуций, Аристотель, (Маяковский ?) и обучим на соответсвующих текстах модельки. А теперь мы можем конвертировать произвольные тексты в стиль конкретного персонажа. И зачем это надо?

Вы только представьте! Представьте, что вы не можете грамотно выразить свои мысли, например вы всю жизнь со всеми общались как "Хай братан че по чем?", а теперь появился научный руководитель и ему время от времени надо писать отчеты... Вы отправляете такое письмо, а конвертер берет и транслирует: "Здравствуйте достопочтенный господин, что у Вас нового?".

Предложил: Кручинин Дмитрий


Магазинная оптимизация

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

Идея минимум. Давайте сделаем приложение: задаем товары, количество и прочее, решаем задачку линейного программирования, выдаем координаты -- все счастливы.

Если хочется что-то большего: идея максимум. Давайте прикрутим рецепты к нашей приложухе, оно в оффлайне ищет самые дешёвые товары подходящие под рецепт, а потом скидывает уведомления, например, на телефон. Еще? Давайте прикрутим учитывание местоположения, далеко ехать не хочется. Еще? Добавляем ползунок уровня жизни, что-то вроде: Поесть только не умереть, Студент, Богатый Студент, ..., Сегодня шикую, Олигарх. Теперь подбираем уже не самое дешевое, а по ползунку.

Предложил: Кручинин Дмитрий


Exercise book from StackOverflow

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

Давайте сделаем "книжку" из живых примеров со stackoverflow. Для начала просто бьем по тегам и сортируем по релевантности. Хочешь изучать bash? -- пожалуйста, выдаем одну за другой задачки (конечно, только вопрос из треда со stackoverflow), а решение уже после (жаль только решение очень просто гуглится =( ).

Предложил: Кручинин Дмитрий


Картинка в ноты

Есть гипотеза, что почти любой НЕслучайный набор нот звучит или почти звучит как музыка. Например, есть видосики на ютубе, где ноты, выстроенные в контур чего либо, забавно звучат. Хочу проверить гипотезу, написать автоматическое конвертирование картинки в ноты, посмотреть, что получится.

Гоша.


Tap Tap resurrection

Хочется сделать игру в стиле guitar hero, по типу ушедшей в историю Tap Tap. Анализируем музыкальную коллекцию пользователя, извлекаем ритм из музыки на телефоне и стараемся сделать это хорошо.

В итоге хочется получить android приложение.

Предложил Симиютин Борис