?

Log in

No account? Create an account
программирование во вьетнаме - Поклонник деепричастий [entries|archive|friends|userinfo]
Anatoly Vorobey

[ website | Website ]
[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

Links
[Links:| English-language weblog ]

программирование во вьетнаме [мар. 21, 2013|09:57 am]
Anatoly Vorobey
Очень интересный рассказ Нила Фрейзера о том, как преподают компьютеры во вьетнамских школах. Не буду пытаться пересказывать - но советую прочитать. И игра его Blockly Maze для объяснения детям основных понятий программирования - тоже интересная штука.

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

Comments:
[User Picture]From: tat_ti
2013-03-21 08:29 am
Расширяем ли набор задач? Если да, то
1) хочу мазу и задачи в классы студентам
2) готова делать задачи (т.е. перевести часть задач классических задач cs на эту мазу забесплатно и придумать новые на разные разделы; я это могу и могу много)

Причина: даже если человек олимпиадник-международник по математике, то это еще не значит, что он прекрасно начинает писать программы на формальном языке (а если не олимпиадник-международник, а просто умный мальчик, то еще менее значит).
Я готова согласиться, что часть народа в студенческие годы, как и среднюю школу, нужно учить через "программирование в картинках". Особенно, если это первый язык программирования.
3-5% на математических специальностях обучаются либо туго, либо очень туго.
(Ответить) (Thread)
[User Picture]From: francis_drake
2013-03-21 09:54 am
Запись не грузится :(
(Ответить) (Thread)
From: ztarlitz
2013-03-21 10:11 am
Программирование, как написано в заголовке лучшего учебника по программированию это алгоритмы + структуры данных.
Где в этой игре данные? Возможно эта игра развивает алгоритмическое мышление, но это не программирование.
(Ответить) (Thread)
[User Picture]From: vika_1_2
2013-03-21 10:18 am
Данные используются в 10 уровне.
(Ответить) (Parent) (Thread)
[User Picture]From: migmit
2013-03-21 10:36 am
Нафиг только они там - непонятно.
(Ответить) (Parent) (Thread)
[User Picture]From: vika_1_2
2013-03-21 10:53 am
Наверно потому, что финиш не всегда достижим обходом по правой или левой руке.
(Ответить) (Parent) (Thread)
[User Picture]From: migmit
2013-03-21 11:26 am
Учитывая, что количество команд там не ограничено, никто не мешает просто захардкодить правильный маршрут.
(Ответить) (Parent) (Thread)
From: kapla55
2013-03-21 11:46 am
Там в каждом уровне есть кнопка "рандомизировать лабиринт". По идее написанная программа должна решать любой случайный лабиринт уровня.
(Ответить) (Parent) (Thread)
[User Picture]From: migmit
2013-03-21 11:54 am
Блин, я и не заметил.
(Ответить) (Parent) (Thread)
From: ztarlitz
2013-03-21 10:47 am
да в 10 уровне данные есть. Но как ниже написали, не понятно зачем.
(Ответить) (Parent) (Thread)
(Удалённый комментарий)
[User Picture]From: alpas
2013-03-21 11:41 am
да, очень интересно.
в конце автор рассуждает о том, что в США проблема с компетентными учителями CS, при этом умалчивает о том, откуда они взялись во Вьетнаме. что удивительно, учитывая его же слова о том, что в тамошних университетах не так всё впечатляет, т.к. CS пришли в страну недавно.

ну и по поводу нёрдов, по-моему, у него устаревшая информация. с тех пор как супергерои и звёздные войны завоевали попкультуру (последние 7-10 лет), ботаны вышли из подполья. сам этот факт уже вполне обыгрывается в фильмах, см. к примеру 21 Jump Street (2012).
(Ответить) (Thread)
[User Picture]From: alenaroo
2013-03-21 01:27 pm
Очень интересно, спасибо. По забавному совпадению я сейчас во Вьетнаме отдыхаю, а один из моих коллег-разработчиков в сиднейской компании, где я работаю, - вьетнамец и один из лучших программистов в компании. Правда, акцент его ну очень сложно бывает понимать.
(Ответить) (Thread)
[User Picture]From: sorcerer_
2013-03-21 01:36 pm
Во Вьетнаме были одни из самых лучших аутсорс программистов, которых мы нанимали.
(Ответить) (Thread)
[User Picture]From: prosto_tak
2013-03-21 01:54 pm
Интересно, что эта его игра сделана на базе Scratch (http://scratch.mit.edu/). Мы с Юлей с ним как раз последние пару недель играем. С одной стороны, язык для детей, но с другой, вполне мощный и интересный. Можно делать мультики и игры. Это не то же самое, как в детстве Фортран учить...
(Ответить) (Thread)
From: huzhepidarasa
2013-03-21 07:31 pm
Задача непростая, да — не сразу понятно, что же обозначают единицы и нули в данных.
(Ответить) (Thread)
[User Picture]From: avva
2013-03-21 09:09 pm
Это сарказм, или не вполне понятный мне смысл?
(Ответить) (Parent) (Thread)
From: huzhepidarasa
2013-03-21 09:41 pm
Но это действительно не сразу понятно. Понятно, что единицы как-то обозначают диагональные отрезки, но одна единица не соответствует одному отрезку, а ноль не соответствует клетке без отрезка. Ну то есть идентифицировать области можно и без этого, а посчитать площадь уже труднее, надо понять, что именно считать.

Edited at 2013-03-21 21:45 (UTC)
(Ответить) (Parent) (Thread)
[User Picture]From: avva
2013-03-21 10:45 pm
Да, в такой формулировке я согласен - посчитать площадь чуть ли не самое сложное в задаче.
(Ответить) (Parent) (Thread)
From: huzhepidarasa
2013-03-21 11:20 pm
Вы как считали, кстати?
(Ответить) (Parent) (Thread)
[User Picture]From: avva
2013-03-22 09:21 am
Я решил, что могу считать данным размер лабиринта в клетках (6x4). Исходя из этого, я вычислил координаты точек, лежащих в середине вертикальных границ клеток. Например, если вершины клеток (0,0), (0,4), (0,8), (4,0), (4,8) итд., я говорю о точках (0,2), (4,2), (0,6), (4,6) итд., только из них еще выбрасываются те, что лежат на левой и правой границе. Оставшиеся точки обладают тем свойством, что если одна из них лежит внутри связной компоненты, она "отвечает" за два треугольника, касающихся ее, каждый площадью 1/2, лежащих внутри этой компоненты, и из этих пар треугольников все состоит.
(Ответить) (Parent) (Thread)
From: huzhepidarasa
2013-03-22 03:06 pm
Я наоборот. Выбрасываются все клетки, у которых хотя бы одна из координат кратна 4 (они лежат на границах квадратов), и все клетки, у которых сумма координат четная (эти лежат на диагоналях). Оставшиеся лежат внутри треугольных четвертушек квадратов. То есть их количество внутри связной компоненты надо делить на 4.
(Ответить) (Parent) (Thread)
[User Picture]From: avva
2013-03-22 04:58 pm
Остроумно!
(Ответить) (Parent) (Thread)
[User Picture]From: kobak
2013-03-22 09:21 am
Честно говоря, я до сих пор не могу понять. Сначала подумал, что нолики -- это пустые клетки, а единички -- клетки с диагональными отрезками, но это не может быть верно, т.к. в data.txt есть структуры вроде

00100
01010
10001

где верхняя единичка по идее должна быть уголком (??). Еще была мысль, что нолики и единички означают не клетки, а узлы решетки, но и в такой интерпретации в таком формате невозможно закодировать конфигурацию, которая приведена тут http://i.imgur.com/qTFiXAW.jpg как иллюстрация.
(Ответить) (Parent) (Thread)
[User Picture]From: avva
2013-03-22 09:40 am
Может, вы не поняли, что файл data.txt в точности кодирует конфигурацию, которая на иллюстрации?

Это дискретизированная плоскость. Единички - "точки", из которых состоят диагональные отрезки, нолики - "точки", соответствующие пустым местам. Если дан файл данных, то учитывая условие, что отрезки всегда диагональные, понятно, как соединить единички, чтобы получить представление в виде картинки. Картинка получится очень грубой, потому что в файле единичный квадрат размером всего 4x4. Если бы он был размером 400x400 "точек", то вышла бы даже более "точная" картинка, чем на иллюстрации.
(Ответить) (Parent) (Thread)
[User Picture]From: kobak
2013-03-22 09:58 am
ой. действительно. спасибо!
(Ответить) (Parent) (Thread)
[User Picture]From: migmit
2013-03-22 01:20 pm
О господи.

Я, грешным делом, вообще подумал, что единички - это клетки, где диагональ проведена одним способом, а нолики - другим.
(Ответить) (Parent) (Thread)
[User Picture]From: aivean
2013-03-21 08:23 pm

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

Правильно ли я понимаю, что вся «сложность» заключается в поиске в ширину? Вначале он запускается при проходе по периметру, затем при проходе за N*M по всей площади лабиринта. Ассимптотическая сложность O(N*M).
(Ответить) (Thread)
[User Picture]From: avva
2013-03-21 09:33 pm

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

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

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


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

Для алгоритмической задачи эта слишком проста. Для задачи на написание кода она в самый раз или даже сложнее средней.
(Ответить) (Parent) (Thread)
[User Picture]From: malaya_zemlya
2013-03-22 01:34 am

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

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

ЗЫ: Я б решал задачу построчным сканированием и модификацией списков связных регионов. В компьютерной графике есть похожий алгоритм заполнения 2х-мерных областей, не помню чьего имени.
(Ответить) (Parent) (Thread)
[User Picture]From: a_bronx
2013-03-22 07:11 am
Не определено, как считать площадь для областей с дырками -- включать дырки или вычитать?
(Ответить) (Parent) (Thread)
[User Picture]From: dvornikstepanof
2013-03-22 09:10 am
Вряд ли предполагается наличие дырок. Т.е. "дырка" - это тоже область, которую нужно учесть и подсчитать ее площадь.
(Ответить) (Parent) (Thread)
[User Picture]From: a_bronx
2013-03-22 09:21 am
Если внутри большой области есть несколько маленьких то чему равна площадь бОльшей? Считать ли её всю целиком со вложенными областями, или же исключить площадь внутренних областей?
(Ответить) (Parent) (Thread)
From: huzhepidarasa
2013-03-22 03:39 pm
Первый вариант будет трудноват для школьников, даже и вьетнамских.
(Ответить) (Parent) (Thread)
[User Picture]From: dvornikstepanof
2013-03-23 08:02 pm
Алгоритмически, наверное, не намного труднее, но программирования будет существенно больше.
Я, кажется, понял, почему вообще возник вопрос о "дырках": если обрабатывать область идя вдоль границы, то внутренние области ("дырки") не видны. Но если рассматривать внутренность каждой связной области, то "дырки" не мешают. А данное в задаче представление в виде матрицы позволяет легко идентифицировать связную (многосвязную) внутренность области через граничащие друг с другом нули.


Edited at 2013-03-23 20:16 (UTC)
(Ответить) (Parent) (Thread)
From: huzhepidarasa
2013-03-25 08:05 pm
Я тут подумал, это на самом деле нетрудно тем же поиском в глубину. Но с педагогической точки зрения это не имеет большого смысла, новых идей здесь не требуется. Еще раз или два применить тот же поиск, и все.
(Ответить) (Parent) (Thread)
[User Picture]From: dvornikstepanof
2013-03-22 08:48 am
В школьном тесте я бы решал задачу в лоб, не заботясь об эффективности и общности:
1. Заменить в матрице все «висячие» единицы (т.е. граничащие с не более чем одной единицей) на 0. Итерировать, пока таковых не останется.
2. Удалить из матрицы (скажем, заменить на «-1») все пограничные нули. (Ноль – пограничный, если с одной из 4 сторон касается границы матрицы или ранее удаленного нуля). Итерировать, пока пограничных нулей не останется.
3. (общий шаг) Выбрать какой нибудь «0» и удалить из матрицы. Затем итеративно удалить все другие нули, граничащие с ранее удаленными. При удалении накапливать суммарную площадь по правилу: если не граничит с единицами, добавить 1; если граничит с одной единицей, добавить ½; если с двумя – добавить ¼. Когда не остается нулей для удаления, накопленная сумма есть (16-кратная) площадь соответствующей области.
Продолжаем процесс, считая области и сравнивая их площади, до тех пор пока остаются нули.

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

Но на интервью я бы, наверное, решал иначе, сведя к более общей задаче. Какие-то усилия заняло бы написание процедуры перевода матрицы в плоский граф (вершины с координатами и ребра), но зато потом решать легче и приятнее. Достаточно трех-четырех операторов, чтобы удалить все висячие ребра; при обходе контура элементарно считается площадь многоугольника через координаты вершин, и т.п.
(Ответить) (Thread)
[User Picture]From: meshko
2013-03-22 07:47 pm
А нельзя просто сжульничать с казать,, что площадть -- это floor(s/12), где s -- это площадь в единицах измерения файла?
(Ответить) (Parent) (Thread)
[User Picture]From: dvornikstepanof
2013-03-22 11:02 pm
Откуда взялось 12?
Одна квадратная единица площади соответсвует 4х4=16 элементам матрицы. Нолик внутри области представлает 1\16 кв. единицы; нолик на границе - вдвое меньше; нолик в углу - вчетверо меньше.
Жульничество или аппроксимация (если даже дадут правильный результат) ничего не облегчают -- простой подсчет нуликов достаточно прост..
(Ответить) (Parent) (Thread)
[User Picture]From: meshko
2013-03-23 01:53 pm
Да, 12 это наверное неправильно. Но откуда берутся ваши дроби я тоже не понимаю. И по-моему они неправильные. Посмотрите на вторую закрытую область, которая в форме ромба. У нее площадь 2, а по-вашему выходит:
4 угловых - 1
8 пограничных - 4
13 внутренних - 13
Итого 18.
(Ответить) (Parent) (Thread)
[User Picture]From: dvornikstepanof
2013-03-23 07:29 pm
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.


Edited at 2013-03-23 20:36 (UTC)
(Ответить) (Parent) (Thread)
[User Picture]From: meshko
2013-03-23 09:17 pm
Но будет ли это работать с большими областями? Если бы например ромб был в два раза больше с площадью 8?
(Ответить) (Parent) (Thread)
[User Picture]From: meshko
2013-03-23 09:28 pm
Например такая фигура:

............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. То есть тоже приближение.

Edited at 2013-03-23 21:29 (UTC)
(Ответить) (Parent) (Thread)
[User Picture]From: meshko
2013-03-23 09:44 pm
аа, я не прав, таки 96!
Как это работает можете объяснить?
(Ответить) (Parent) (Thread)
[User Picture]From: dvornikstepanof
2013-03-24 11:07 am
Если Вам интересно глянуть на С++ программу и результаты ее работы, можете посмотреть в моем журнале здесь .
(Первоначальную наспех написанную программу я причесал, вставил комментарии и добавил печать промежутожных результатов в наглядном виде).
Если у Вас есть вопросы по коду, пишите мне. Неудобно засорять журнал Аввы посторонними вещами.


Edited at 2013-03-24 11:16 (UTC)
(Ответить) (Parent) (Thread)
From: lanceupper
2013-03-25 05:47 pm
Когда речь идет об обучении детей программированию, понятно, что могут представлять ценность разнообразные надумано-искуственные задачи с заранее заказанными надуманно-искуственными способами решения. Но за пределами этой области надуманость и искуственность никакого смысла не имеют.

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

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

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

Edited at 2013-03-25 17:48 (UTC)
(Ответить) (Thread)
[User Picture]From: dvornikstepanof
2013-03-25 11:22 pm
Поскольку я один в этой дискуссии упомянул 40 минут ( Avva решил за 35), то Ваши слова -
Садиться же тихо строчить растровое решение "за 40 минут" в такой ситуации является ярко выраженным признаком непрофессионализма -
очевидно, относятся ко мне.

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

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


Edited at 2013-03-25 23:25 (UTC)
(Ответить) (Parent) (Thread)