Расширяем ли набор задач? Если да, то
1) хочу мазу и задачи в классы студентам
2) готова делать задачи (т.е. перевести часть задач классических задач cs на эту мазу забесплатно и придумать новые на разные разделы; я это могу и могу много)

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

Запись не грузится :(

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

Данные используются в 10 уровне.

Надо будет сегодня же на сыне опробовать.. ;)

да, очень интересно.
в конце автор рассуждает о том, что в США проблема с компетентными учителями CS, при этом умалчивает о том, откуда они взялись во Вьетнаме. что удивительно, учитывая его же слова о том, что в тамошних университетах не так всё впечатляет, т.к. CS пришли в страну недавно.

ну и по поводу нёрдов, по-моему, у него устаревшая информация. с тех пор как супергерои и звёздные войны завоевали попкультуру (последние 7-10 лет), ботаны вышли из подполья. сам этот факт уже вполне обыгрывается в фильмах, см. к примеру 21 Jump Street (2012).

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

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

Интересно, что эта его игра сделана на базе Scratch (http://scratch.mit.edu/). Мы с Юлей с ним как раз последние пару недель играем. С одной стороны, язык для детей, но с другой, вполне мощный и интересный. Можно делать мультики и игры. Это не то же самое, как в детстве Фортран учить...

Задача непростая, да — не сразу понятно, что же обозначают единицы и нули в данных.

Это сарказм, или не вполне понятный мне смысл?

Правильно ли я понимаю, что вся «сложность» заключается в поиске в ширину? Вначале он запускается при проходе по периметру, затем при проходе за N*M по всей площади лабиринта. Ассимптотическая сложность O(N*M).

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

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


В Гугле на интервью задают в принципе три разных вида задач:
1. algo
2. coding
3. system design

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

В школьном тесте я бы решал задачу в лоб, не заботясь об эффективности и общности:
1. Заменить в матрице все «висячие» единицы (т.е. граничащие с не более чем одной единицей) на 0. Итерировать, пока таковых не останется.
2. Удалить из матрицы (скажем, заменить на «-1») все пограничные нули. (Ноль – пограничный, если с одной из 4 сторон касается границы матрицы или ранее удаленного нуля). Итерировать, пока пограничных нулей не останется.
3. (общий шаг) Выбрать какой нибудь «0» и удалить из матрицы. Затем итеративно удалить все другие нули, граничащие с ранее удаленными. При удалении накапливать суммарную площадь по правилу: если не граничит с единицами, добавить 1; если граничит с одной единицей, добавить ½; если с двумя – добавить ¼. Когда не остается нулей для удаления, накопленная сумма есть (16-кратная) площадь соответствующей области.
Продолжаем процесс, считая области и сравнивая их площади, до тех пор пока остаются нули.

У меня чистое программирование с отладкой в С++ заняло около 40 мин, но перед этим я потратил некоторое время на обдумывние алгоритма и структуры программы. Это время я не засек; это могло быть от 5 до 20 мин.

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

А нельзя просто сжульничать с казать,, что площадть -- это floor(s/12), где s -- это площадь в единицах измерения файла?

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

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

Готовый программист же, будучи ознакомлен с исходной абстрактной постановкой задачи, должен сделать большие глаза, увидев, что входные данные вдруг с какого-то бодуна представлены растром. Для любого job interview (если интервьюирующий не идиот) в такой ситуации правильным ответом является: ткнуть пальцем во входные данные и сказать "вы что, с дуба ляснулись?!". Садиться же тихо строчить растровое решение "за 40 минут" в такой ситуации является ярко выраженным признаком непрофессионализма.

Если же "заказчик" таки настаивает на растровом задании входа, то правильным решением будет все таки разработать собственный векторный формат входа и решение именно для векторной задачи. А затем просто написать "преобразовалку" растрового входа к вектороному, т.е. свести решение растровой задачи к уже решенной векторной задаче. Да, это может занять больше, чем 40 минут. Но это продемонтирует тот факт, что программист умеет разделять поствленную задачу на осмысленое ядро и малозначительную интерфейсную шелуху. Последеняя существует лишь потому, что "заказчик" еще сам не понял, что ему нужно.

Edited at 2013-03-25 17:48 (UTC)

Поскольку я один в этой дискуссии упомянул 40 минут ( Avva решил за 35), то Ваши слова -
Садиться же тихо строчить растровое решение "за 40 минут" в такой ситуации является ярко выраженным признаком непрофессионализма -
очевидно, относятся ко мне.

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

Но говорить на интервью "вы что, с дуба ляснулись?!" я бы все-таки воздержался.


Edited at 2013-03-25 23:25 (UTC)