Головоломка Арнольда ★

Постоянные читатели помнят, что мы с коллегами по учебе лет 10 назад занимались задачей Арнольда. В ней остались открытые вопросы, и я недавно решил к ним вернуться. Дописал одну из программ, отрисовывающих и распрямляющих конфигурации, и понял, что получилась хорошая игровая механика для головоломки. Переписал код визуализации и моделирования на js, и получилась браузерная головоломка.

Правила

В этой игре выполняются простые правила:

1. На плоскости проведены несколько линий, каждая пара линий пересекается в одной точке.
2. Линии разбивают плоскость на области, раскрашенные в шахматном порядке.
3. Вы можете перестраивать разбиение, «схлопывая» и «выворачивая» треугольники.
4. Ваша цель — получить максимально возможное количество темных областей.

В простейшем случае 5 линий процесс игры выглядит так:

Пользовательский опыт

При небольшом количестве линий решить головоломку можно случайным перебором. Нужно помнить, что иногда надо «пожертвовать» счетом (количеством темных областей), так как не всегда есть «прямая дорога» к цели, на которой счет только увеличивается.

Я довольно быстро «прошел» все уровни до 19 линий. 21 линию (на скриншоте в начале) собрал часа за полтора. Правда, я знал, что существует вращательно-симметричная конфигурация (поворот на 120° переводит ее в себя), и специально делал ее симметричной. 23 линии пытался собрать дважды, и оба раза не получилось набрать последнее очко.

С увеличением уровня сложность игры растет не только количественно (нужно дольше идти к цели), но и качественно: приходится придумывать новые приемы и подходы, так как старых становится недостаточно.

По ощущениям игра похожа на паззл, каждый кусочек которого подходит к любому другому кусочку, но общая картина из них всё никак не складывается.

Игра полностью отвлекает от происходящего вокруг, подходит для убивания времени в метро.

Математическая основа

Напомню формулировку задачи Арнольда:

На плоскости проведены N прямых. Найти максимальную разность между числом черных и белых областей шахматной раскраски дополнения.

Это открытая математическая проблема. Она является частным случаем 16-й проблемы Гильберта для многочленов специального вида — произведения линейных сомножителей ax+by+c.

Таким образом, переворачивая треугольники в головоломке, вы на самом деле решаете в частном случае 16-ю проблему Гильберта! :)

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

Также задача Арнольда тесно связана с задачей о треугольниках Кобона.

Вместе со мной Денис Уткин и Сергей Белёв потратили немало времени на попытки решения, результаты которого есть во многостраничном pdf-отчете. Я хочу выразить благодарность Денису и Сергею за совместный интерес, без которого в конечном итоге не появилась бы эта головоломка. Бонус для внимательных читателей: в отчете есть примеры конфигураций, на которых достигается цель головоломки.

Вычислительная модель игры

В основе визуализации — математическое моделирование некоторой «механической» системы. В этой системе массивные точки соединены ломаными линиями, отталкиваются друг от друга, испытывают сопротивление среды. В узлах ломаных — распрямляющие «пружинки». Концы ломаных прибиты внешними зафиксированными точками. Для расчетов движения точек по законам механики применяется метод Рунге — Кутты четвертого порядка с оценкой ошибок и плавающим шагом. Преподаватели вычматов были бы довольны :) Код, как обычно, открыт на гитхабе.

Рубаков

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

Не совсем интервью, правда. Из видео вопросы вырезали, добавили текст при монтаже. Но всё равно тут главное послушать Рубакова.

Понятие формата в дизайне интерфейсов — В кресле препода №5

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

Когда формулировал, почему моим словам стоит доверять, осознал, что у меня уже почти 13 лет опыта в коммерческой веб-разработке. Незаметно время летит :)

00:11 Почему моим словам стоит доверять: 13 лет опыта
00:42 Собирался рассказать о понятии формата давно
01:11 Для затравки: чем плохи выпадайки в вебе, пример личного кабинета интернет-банка
03:28 Понятие формата
04:56 Пример 1: формат веба и формат окон настройки старых операционных систем (сравнение из старой статьи на хабре)
08:03 Комментарий к статье, обращающийся к понятию формата
10:42 OS/2 умер
12:09 Окно настройки — почему такое? Ограничение 1: физический размер экранов
14:24 Ограничение 2: размер видеопамяти
15:26 Ограничение 3: частота обновления
18:53 Ограничение 4: работа без драйверов
19:54 640*480 — естественное ограничение в конце 90-х
20:58 Особенности формата веба
22:47 Сравнивать надо функциональность
25:28 Бессмысленность претензий к вебу
26:52 Эволюция интерфейса настройки Windows
32:28 Пример 2: Одностраничные приложения
33:54 Админка моего движка как пример одностраничного приложения
37:25 Как бы сейчас спроектировал интерфейс админки
41:42 Обсуждаем извлеченные уроки и дизайн выпадайки из личного кабинета интернет-банка
46:17 Итог

Главное правило подготовки докладов

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

Доклад нужно разделить на три примерно равные части. Первую часть доклада должны понять все присутствующие. Вторую часть — около половины. Третью часть должны понимать всего несколько человек.

Вы вольны выбирать структуру доклада самостоятельно. Пример: вы придумали решение какой-либо проблемы. Вариант структуры:

1. Описание проблемы, обзор существующих методов решения.
2. Поиск решения: предпосылки, логические построения, гипотезы, неудачные варианты.
3. Технические детали решения.

Недавно со мной советовались, как подготовить доклад. Я вспомнил это правило и посоветовал его. Доклад получился замечательным.

Уборка улиц, отрицательная польза и коррупция

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

Смысла от его действий нет никакого. Ветер сдует и дождь смоет грязь опять на асфальт. Результат работы дворника — не чистый двор, а фотографии чистого асфальта. Он продает эти фотографии, а управляющая компания их покупает.

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

Латынина об этом говорила не один раз:

У нас до сих пор через железнодорожные переезды вокруг Москвы не построены нормальные автомобильные переезды, у нас автомобили стоят в пробке по несколько часов. При этом рядом как всегда таджики косят траву, нанятые, видимо, Железной дорогой.

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

Яндекс-рай

Гендерная нейтральность

Сфотографировал социальную рекламу в метро.

Как вы считаете, это сексистская реклама? Нарушена ли в ней гендерная нейтральность?

Добавлено: Вот какой вариант сфотографировал в декабре. Те же вопросы и к нему.

Воспринимайте слова в переписке буквально

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

В устном общении есть возможность задать уточняющий вопрос, и проблема часто снимается. В переписке с этим сложнее, поэтому особенно важно следить за словами: проверять, правильно ли слова передают смысл, и воспринимать слова буквально.

Смотрите, что получается, если кто-то в переписке не придерживается таких правил. Мне написал посетитель сервиса для генерации картинок с формулами. В письме с темой «Про отсутствие https в адресах картинок на tex.s2cms.ru/» он сформулировал мысль так:

Во всех адресах и примерах использования «https:» почему-то исчезло. Так что адреса формально неправильные.

Чтобы не отправлять вас по ссылкам, поясню, что сервис предлагает УРЛы картинок в виде //i.upmath.me/svg/f(x) и код встраивания скрипта <script src="//i.upmath.me/latex.js"></script>.

Дело в том, что схема (http или https для веба) — необязательная часть адреса, его можно опустить (см. network-path reference в RFC). Тогда подразумевается, что используется текущая схема. Независимо от того, включен ли на сайте https или нет, картинки и скрипт загрузятся по соответствующей схеме.

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

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

Это вопрос или предложение? Почему вы считаете, что «https:» исчезло?

Первая часть — отсылка к технике продуктивной переписки «общаться вопросами и предложениями». Непонятно, интересовался ли посетитель, почему так сделано, или предлагал сделать по-другому. Эту часть вопроса он проигнорировал. На вторую часть он ответил «Смотрите сами» и приложил скриншоты с подчеркнутыми УРЛами без схемы. Разумеется, схемы в них нет, я сделал это специально. Вопроса в сообщении опять не было. Как и задачи у меня кого-либо переубедить. Поэтому переписка не продолжилась.

Закрепим рекомендации:

1. Когда вы пишете сообщение в мессенджере или почте, перечитайте перед отправкой и проверьте, что сообщение отражает вашу мысль.
2. Когда вы получили сообщение, воспринимайте его буквально, не додумывайте за автора. Если автору нужно было другое, он переспросит.
3. Отвечайте на явно сформулированные вопросы. Прокомментируйте предложения: будем ли мы делать то, что предлагается, и если нет, то почему.
4. Если ни вопросов, ни предложений нет, а от вас требуется реакция, и вы не знаете, что ответить, так и напишите: «Я не понимаю, в чем твой вопрос и что ты предлагаешь».

О тестовых заданиях на собеседованиях программистов — В кресле препода №4

Я провел много собеседований. Несколько десятков, или даже около сотни. К сожалению, с самого начала подсчитывать не догадался. Точное число было бы интересным.

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

Кстати, видео снимал по методу Ильи Бирмана.

Редактор математических текстов Mathcha

Искал онлайн-инструменты для редактирования картинок TikZ и наткнулся на редактор Mathcha.

Этот редактор — визуальный: вы сразу редактируете документ вместе с форматированием. В отличие от моего редактора Upmath, в котором вы редактируете исходник на маркдауне и латехе, хотя и сразу видите результат.

Вот рисунок, который я сделал с помощью Mathcha. Накидал основу в нем, экспортировал в TikZ и подправил исходный код уже в UpMath.

$$ \tikzset{every picture/.style={line width=0.75pt}} %set default line width to 0.75pt \begin{tikzpicture}[x=0.75pt,y=0.75pt,yscale=-1,xscale=1] %uncomment if require: \path (0,300); %set diagram left start at 0, and has height of 300 %Shape: Boxed Line [id:dp7642567693966007] \draw (130,80) -- (130,140) ; %Shape: Boxed Line [id:dp02318954146147889] \draw (130,150) -- (130,180) ; %Shape: Boxed Line [id:dp4638027067588357] \draw (130,190) -- (130,250) ; %Shape: Wave [id:dp03622557580885122] \draw [color={rgb, 255:red, 74; green, 144; blue, 226 } ,draw opacity=1 ] (215,80) .. controls (202.19,83.1) and (190,86.06) .. (190,89.5) .. controls (190,92.94) and (202.19,95.9) .. (215,99) .. controls (227.81,102.1) and (240,105.06) .. (240,108.5) .. controls (240,111.94) and (227.81,114.9) .. (215,118) .. controls (202.19,121.1) and (190,124.06) .. (190,127.5) .. controls (190,130.94) and (202.19,133.9) .. (215,137) .. controls (227.81,140.1) and (240,143.06) .. (240,146.5) .. controls (240,149.94) and (227.81,152.9) .. (215,156) .. controls (202.19,159.1) and (190,162.06) .. (190,165.5) .. controls (190,168.94) and (202.19,171.9) .. (215,175) .. controls (227.81,178.1) and (240,181.06) .. (240,184.5) .. controls (240,187.94) and (227.81,190.9) .. (215,194) .. controls (202.19,197.1) and (190,200.06) .. (190,203.5) .. controls (190,206.94) and (202.19,209.9) .. (215,213) .. controls (227.81,216.1) and (240,219.06) .. (240,222.5) .. controls (240,225.94) and (227.81,228.9) .. (215,232) .. controls (202.19,235.1) and (190,238.06) .. (190,241.5) .. controls (190,244.57) and (199.7,247.26) .. (210.89,250) ; %Straight Lines [id:da008457960885399407] \draw (190,80) -- (190,250) ; %Flowchart: Summing Junction [id:dp09695643217509597] \draw (135,132.75) .. controls (135,128.75) and (138.36,125.5) .. (142.5,125.5) .. controls (146.64,125.5) and (150,128.75) .. (150,132.75) .. controls (150,136.75) and (146.64,140) .. (142.5,140) .. controls (138.36,140) and (135,136.75) .. (135,132.75) -- cycle ; \draw (137.2,127.62) -- (147.8,137.88) ; \draw (147.8,127.62) -- (137.2,137.88) ; %Shape: Inductor [id:dp3454355331692156] \draw (35,155) -- (42.06,155) .. controls (43.68,155) and (45,156.12) .. (45,157.5) .. controls (45,158.88) and (43.68,160) .. (42.06,160) .. controls (43.68,160) and (45,161.12) .. (45,162.5) .. controls (45,163.88) and (43.68,165) .. (42.06,165) .. controls (43.68,165) and (45,166.12) .. (45,167.5) .. controls (45,168.88) and (43.68,170) .. (42.06,170) .. controls (43.68,170) and (45,171.12) .. (45,172.5) .. controls (45,173.88) and (43.68,175) .. (42.06,175) -- (35,175) ; %Straight Lines [id:da4690178114375858] \draw [dash pattern={on 0.84pt off 2.51pt}] (45,165.5) -- (130,185) -- (190,165) ; %Straight Lines [id:da10916309009890135] \draw [dash pattern={on 0.84pt off 2.51pt}] (45,164.5) -- (130,145) -- (190,165) ; % Text Node \draw (112,127) node [anchor=north west][inner sep=0.75pt] [align=left] {A}; % Text Node \draw (112,191) node [anchor=north west][inner sep=0.75pt] [align=left] {B}; \end{tikzpicture} $$

← сюда туда →