программирование во вьетнаме

[avva]

Очень интересный рассказ Нила Фрейзера о том, как преподают компьютеры во вьетнамских школах. Не буду пытаться пересказывать - но советую прочитать. И игра его Blockly Maze для объяснения детям основных понятий программирования - тоже интересная штука.

Что касается задачи про лабиринт для старшеклассников, которую он описывает ближе к концу записи, меня это весьма впечатлило (и даже подзуживает скепсис несколько). Это действительно непростая задача, и автор не преувеличивает, когда пишет, что ее вполне можно задавать на интервью в Гугле. Любопытства ради я решил ее на Питоне, сидя за компьютером, и засек время: от начала работы до вывода всех требуемых результатов, включая отладку и все остальное, у меня заняло 35 минут.

Comments

[tat-ti.livejournal.com]

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

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

[francis-drake.livejournal.com]

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

[ztarlitz.livejournal.com]

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

[vika-1-2.livejournal.com]

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

[migmit.livejournal.com]

Нафиг только они там - непонятно.

[vika-1-2.livejournal.com]

Наверно потому, что финиш не всегда достижим обходом по правой или левой руке.

[migmit.livejournal.com]

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

[kapla55.livejournal.com]

Там в каждом уровне есть кнопка "рандомизировать лабиринт". По идее написанная программа должна решать любой случайный лабиринт уровня.

[migmit.livejournal.com]

Блин, я и не заметил.

[ztarlitz.livejournal.com]

да в 10 уровне данные есть. Но как ниже написали, не понятно зачем.

[arhip.livejournal.com]

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

[alpas.livejournal.com]

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

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

[alenaroo.livejournal.com]

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

[http://users.livejournal.com/sorcerer_/]

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

[prosto-tak.livejournal.com]

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

[huzhepidarasa.livejournal.com]

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

[avva.livejournal.com]

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

[huzhepidarasa.livejournal.com]

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

[avva.livejournal.com]

Да, в такой формулировке я согласен - посчитать площадь чуть ли не самое сложное в задаче.

[huzhepidarasa.livejournal.com]

Вы как считали, кстати?

[avva.livejournal.com]

Я решил, что могу считать данным размер лабиринта в клетках (6x4). Исходя из этого, я вычислил координаты точек, лежащих в середине вертикальных границ клеток. Например, если вершины клеток (0,0), (0,4), (0,8), (4,0), (4,8) итд., я говорю о точках (0,2), (4,2), (0,6), (4,6) итд., только из них еще выбрасываются те, что лежат на левой и правой границе. Оставшиеся точки обладают тем свойством, что если одна из них лежит внутри связной компоненты, она "отвечает" за два треугольника, касающихся ее, каждый площадью 1/2, лежащих внутри этой компоненты, и из этих пар треугольников все состоит.

[huzhepidarasa.livejournal.com]

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

[avva.livejournal.com]

Остроумно!

[obiwanus.livejournal.com]

Долго ломал голову, никак не мог понять как такое можно решить за 45 минут, но только потом понял что не рассматриваются варианты когда ширина коридоров не корень из двух.

Пошел учиться, чтоб быть не хуже вьетнамских школьников.

Вот пример решения на питоне, если кому интересно
https://gist.github.com/obiwanus/8036251

[kobak.livejournal.com]

Честно говоря, я до сих пор не могу понять. Сначала подумал, что нолики -- это пустые клетки, а единички -- клетки с диагональными отрезками, но это не может быть верно, т.к. в data.txt есть структуры вроде

00100
01010
10001

где верхняя единичка по идее должна быть уголком (??). Еще была мысль, что нолики и единички означают не клетки, а узлы решетки, но и в такой интерпретации в таком формате невозможно закодировать конфигурацию, которая приведена тут http://i.imgur.com/qTFiXAW.jpg как иллюстрация.

[avva.livejournal.com]

Может, вы не поняли, что файл data.txt в точности кодирует конфигурацию, которая на иллюстрации?

Это дискретизированная плоскость. Единички - "точки", из которых состоят диагональные отрезки, нолики - "точки", соответствующие пустым местам. Если дан файл данных, то учитывая условие, что отрезки всегда диагональные, понятно, как соединить единички, чтобы получить представление в виде картинки. Картинка получится очень грубой, потому что в файле единичный квадрат размером всего 4x4. Если бы он был размером 400x400 "точек", то вышла бы даже более "точная" картинка, чем на иллюстрации.

[kobak.livejournal.com]

ой. действительно. спасибо!

[migmit.livejournal.com]

О господи.

Я, грешным делом, вообще подумал, что единички - это клетки, где диагональ проведена одним способом, а нолики - другим.

в чем сложность задачи?

[aivean.livejournal.com]

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

Re: в чем сложность задачи?

[avva.livejournal.com]

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

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


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

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

Re: в чем сложность задачи?

[malaya-zemlya.livejournal.com]

Одно интервью занимает 45 минут на все про все, поэтому имхо задача несколько длинновата для кодинга.

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

[a-bronx.livejournal.com]

Не определено, как считать площадь для областей с дырками -- включать дырки или вычитать?

[dvornikstepanof.livejournal.com]

Вряд ли предполагается наличие дырок. Т.е. "дырка" - это тоже область, которую нужно учесть и подсчитать ее площадь.

[a-bronx.livejournal.com]

Если внутри большой области есть несколько маленьких то чему равна площадь бОльшей? Считать ли её всю целиком со вложенными областями, или же исключить площадь внутренних областей?

[huzhepidarasa.livejournal.com]

Первый вариант будет трудноват для школьников, даже и вьетнамских.

[dvornikstepanof.livejournal.com]

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

[huzhepidarasa.livejournal.com]

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

[dvornikstepanof.livejournal.com]

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

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

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

[meshko.livejournal.com]

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

[dvornikstepanof.livejournal.com]

Откуда взялось 12?
Одна квадратная единица площади соответсвует 4х4=16 элементам матрицы. Нолик внутри области представлает 1\16 кв. единицы; нолик на границе - вдвое меньше; нолик в углу - вчетверо меньше.
Жульничество или аппроксимация (если даже дадут правильный результат) ничего не облегчают -- простой подсчет нуликов достаточно прост..

[meshko.livejournal.com]

Да, 12 это наверное неправильно. Но откуда берутся ваши дроби я тоже не понимаю. И по-моему они неправильные. Посмотрите на вторую закрытую область, которая в форме ромба. У нее площадь 2, а по-вашему выходит:
4 угловых - 1
8 пограничных - 4
13 внутренних - 13
Итого 18.

[dvornikstepanof.livejournal.com]

Sorry, у меня там оговорка. Полный вклад вносят нулики, а половинный и четвертной - ЕДИНИЧКИ на границе. В матрице указанной области соответствуют строки 5-12, колонки 13-21 (начиная счет с 1):

____1
___101
__10001
_1000001
100000001
_1000001
__10001
___101
____1

4 угловых единичек - 1
12 пограничных единичек - 6
25 внутренних ноликов - 25
Итого 32.

Площадь области: 32/16 = 2.

[meshko.livejournal.com]

Но будет ли это работать с большими областями? Если бы например ромб был в два раза больше с площадью 8?

[meshko.livejournal.com]

Например такая фигура:

............1
...........1.1
..........1...1
.........1.....1
........1.......1
.......1.......1
......1.......1
.....1.......1
....1.......1
...1.......1
..1.......1
.1.......1
1.......1
.1.....1
..1...1
...1.1
....1


Площадь 6, а по вашей формуле выходит, по-моему, 97. То есть тоже приближение.

[meshko.livejournal.com]

аа, я не прав, таки 96!
Как это работает можете объяснить?

[dvornikstepanof.livejournal.com]

Если Вам интересно глянуть на С++ программу и результаты ее работы, можете посмотреть в моем журнале здесь (http://dvornikstepanof.livejournal.com/4366.html).
(Первоначальную наспех написанную программу я причесал, вставил комментарии и добавил печать промежутожных результатов в наглядном виде).
Если у Вас есть вопросы по коду, пишите мне. Неудобно засорять журнал Аввы посторонними вещами.

[lanceupper.livejournal.com]

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

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

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

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

[dvornikstepanof.livejournal.com]

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

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

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