TeardownTree update

The TeardownTree project is coming along nicely. It is now feature-complete: both the basic and the interval tree have been implemented, thoroughly tested and benchmarked. The interfaces provided are Map and Set with all the familiar BST operations (with the notable exception of insert): find, query_range (basic tree) / query_overlap (interval tree), delete, delete_range / delete_overlap with optional filtering, iter, into_iter.

As to the insert operation, I initially assumed it was simply impossible to implement in a satisfactory manner. But I have now arrived at the idea that it's doable by borrowing from the awesome data structure called Scapegoat Tree. Indeed, the Scapegoat Tree is perfectly suited for my use case: it rebalances itself by rebuilding entire subtrees as opposed to by tree rotations (which are basically impossible in the implicit representation) and requires no extra data in the nodes. It also does not affect the delete_* operations, which I want to keep as they are, or perhaps allow enabling full conformance to the Scapegoat Tree with a flag if the user is interested in guaranteed O(log N) amortized complexity at the expense of having to rebuild the whole tree every once in a while.

Anyway, my immediate plans are to publish a full and proper set of benchmarks (the currently published benchmarks are, as I learned, only valid for Windows, where Rust uses the inferior system allocator - as opposed to jemalloc on Linux, - with a huge effect on data structures that allocate their nodes individually): first, comparing the flagship TeardownTree::delete_range, as well as delete, query and query_range operations with the competition; second, showing how various features affect the performance of delete_range: basic delete_range vs filter_range vs IntervalTree::delete_overlap vs IntervalTree::filter_overlap.

HOWTO: Ivacy VPN & QBittorrent on Windows

Goal: configure Ivacy VPN service on Windows in such way that only select few applications (QBittorrent in my case) would use it.

After several hours of bashing my head against the wall, here is what I found.

1) There is a guide describing how to achieve this with OpenVPN; however, I found that, for some reason, with Ivacy this yields a much worse performance than when connecting with Ivacy's proprietary client. Namely, QBittorrent is able to connect to much fewer peers. Ivacy's support has (so far) been unable to solve this.
2) QBittorrent allows one to configure the network interface through which to connect, but the drop-down list does not include "Ivacy" - the name of the VPN interface created by Ivacy's proprietary client.

1) Set up the Windows Firewall rules to block all communication for QBittorrent, except through the VPN interfaces. This is a safety measure, not required for the rest to work.
2) Download and install ForceBindIP.
3) Connect to the VPN. Find out the GUID of the VPN network interface: open regedit and browse to HKEY_LOCAL_MACHINE\SYSTEM\CurrentControlSet\Services\Tcpip\Parameters\Interfaces.
4) Modify QBittorrent's shortcut as follows: <path/to/ForceBindIp.exe> -i <GUID> <path/to/qbittorrent.exe>

P.S. Of all Torrent clients I tried, only Vuze was able to handle this properly. However, its GUI is extraordinarily repulsive and inconvenient, not to mention the ads.

Bulk delete for BST (binary search trees)

Hmm, it seems Google doesn't know of an algorithm to bulk delete all nodes in [from, to] range from a binary search tree in O(k+log n) time (where k is the number of nodes in that range). Can I be the first to invent one? Granted, the implementation is involved with lots of cases, but quite straightforward conceptually.

Briefly, it is a recursive algorithm (duh!) based on the standard BST delete operation (refresh your memory on that before reading further). The recursive function accepts 4 parameters aside from the node itself: two stacks of items (replacements_min and replacements_max) and two integers (min_reqs, max_reqs).

- min_reqs contains the number of minimum items that were requested to replace items above in the call stack
- replacements_min contains the stack of items in increasing order (biggest on top) that have been accumulated in response to min-reqs. Thus its size is always <= min_reqs.

(max_reqs and replacements_max are the same for max items)

What we are supposed to do in our current subtree is:
- for every item that is inside the search range, move it to an output list; then attempt to retrieve a replacement for it from either the left subtree (by passing max_reqs+1) or the right subtree (by passing min_reqs+1). To be more specific: after a recursive call on the left subtree with (max_reqs+1), we check whether max_reqs+1==replacements_max.len() and, if so, pop an item from replacements_max and put it in place of our removed item. Otherwise we proceed to recursive call on the right subtree with (min_reqs+1), etc.
- remove (min_reqs-replacements_min.len()) smallest items that have not been consumed and add them to replacements_min
- mirror for replacements_max and max_reqs

See my implementation below for details. It has been exhaustively tested on all trees up to size 10 with no errors (the test is found in

Предание о Хакинтоше

Сказ о том, как я собрал себе Хакинтош.

I) Дано
1. Железо: GA-Z97-D3H, i5 4690k, карта WiFi TL-WN881ND, NVidia GTX 260, KVM из Китая (CKL-92D).

II) Создаем виртуальную машину с Mac OS X. Это нужно для того, чтобы создать образ инсталляции Хакинтоша. Такой вот bootstrapping.
2. Качаем VMWare Player и готовый образ под него. Следуем инструкции по установке. Если сеть перестает работать (как это случилось у меня), переводим в настройках виртуальной машины сеть в режим Bridged, нажимаем на кнопку Configure Adapters, выставляем там флажок только напротив реальной сетевой карты.
3. Вставляем флешку или USB Hard Disk. Говорим VMWare подключить его к виртуальной машине.
4. Форматируем так, чтобы первый партишн был пустым, имел обычную файловую систему мака (HFS+) и размер от 8 до 16Гб (важно!).

III) Создаем образ инсталляции Хакинтоша:
5. Следуем гайду по установке Хакинтоша. В программе Unibeast включаем галочку "Inject NVidia". Везде, где есть выбор между EFI и Legacy, выбираем EFI.
6. Качаем Multibeast, записываем его на наш USB drive.
7. Качаем Clover Configurator, записываем его на USB drive.

8. Подключаем все проводки к KVM.
9. Открываем Device Manager в Windows. Идем в Universal Serial Bus Controllers. Открываем все девайсы со словом "Hub", идем в таб Power Management, отключаем галочку "Allow the computer to turn off this device to save power". Это нужно потому, что со включенным флажком при переключении KVM в Windows часто отключаются клавиатура и мышь. (Возможно, это проблема только с этим конкретным девайсом KVM.)
10. У всех нормальных KVM есть комбинация горячих клавиш для переключения между девайсами. У моего она явно нигде не указана, но методом научного тыка выявлены две: два нажатия на Scroll Lock и два нажатия на Num Lock. Самое интересное - как выяснилось, девайс отлавливает не сами нажатия, а изменение состояния лампочки (мы к этому еще вернемся).

V) Инсталлируем Хакинтош и конфигурируем его:
11. Продолжаем следовать гайду по установке Хакинтоша.
12. Настройки BIOS для Z97-D3H берем отсюда.
13. После окончания установки загружаем Хакинтош используя тот же диск USB (в boot menu будет соответствующая опция). Это важно потому, что его собственный boot loader может быть еще не создан или иметь неправильные настройки.
14. Запускаем Multibeast с нашего диска USB. В нем выбираем опции: Audio->ALC1150, Misc->FakeSMC*, Misc->NullCpuPowerManagement, Network->Intel->AppleIntelE1000e v3.3.3, Bootloaders->Clover v2.3k r3423 UEFI Boot Mode, Customize->Inject NVIDIA, Customize->System Definitions->Mac Pro->Mac Pro 3,1
15. Открываем таб Build в MultiBeast, выбираем правильный Install Drive (важно!), запускаем Install. Отключаем наш USB drive, перезагружаемся. Комп должен теперь загружаться со своего хард диска.
16. Запускаем Clover Configurator с диска USB.
17. В разделе Boot выставляем: Rootless=0, -XCPM, Darkwake=no, как советуют здесь.

VI) Чиним драйвер для карты WiFi:
18. Копируем файл /System/Library/Extensions/IO80211Family.kext на десктоп. Сразу же создаем его бекап на десктопе.
19. Жмем на файл правой кнопкой -> Show package contents.
20. Открываем Contents -> Plugins.
21. Жмем правой кнопкой на файл AirportAtheros40.kext -> Show package contents
22. Открываем файл Contents -> Info.plist в текстовом редакторе
23. Находим первую строку вида <string>pci168c,XX</string> и меняем в ней XX на "2e", где "e" - маленькая
24. Сохраняем Info.plist
25. С помощью утилиты KextBeast инсталлируем IO80211Family.kext в директорию /System/Library/Extensions/
26. Перезагружаемся, теперь WiFi должен работать.

VII) Устанавливаем программы, облегчающие жизнь:
27. "MouseFixer" - программа от TeamLiquid, отключающая ускорение мыши. Рекомендуется в сочетании с программой, устанавливающей нужный DPI (т.к. скорость мыши в контрольной панели Мака перестает работать), - например, драйвером производителя мыши.
28. TeamViwer - иногда удобнее использовать программу такого рода, чем KVM (для filesharing, clipboard sharing, если надо часто переключаться туда-сюда, etc)

VIII) Проблема с переключением KVM и ее решение:
29. Как я писал выше, мой KVM отлавливает не нажатия на клавиши Scroll Lock и Num Lock, а изменение состояния лампочек. Когда он обнаруживает, что лампочка мигнула, срабатывает переключение на другой компьютер.
30. Проблема в том, что клавиатура Маков в принципе не имеет ни этих клавиш, ни лампочек. При нажатии на Scroll и Num Lock генерируются какие-то события, но лампочка не переключается. Соответственно, hotkey в Маке не работает.
31. Как пофиксить:
  а) скачать этот файл и положить его в /Users/MYUSER/bin/. Это программа, скомпилированная под Intel/x64 (не проверял, для какого точно instruction set).
  б) Установить системный хотки как описано здесь. В качестве команды выбираем Shell Script с текстом "/Users/MYUSER/bin/setleds" (без кавычек). В качестве комбинации клавиш я выбрал Cmd+Scroll Lock, т.к. просто Scroll Lock не работает.
  в) теперь двойное нажатие на Scroll Lock через полсекунды переключит компьютер
32. Что это за программа:
  а) Это код, взятый из этой репозитории
  б) ... переделанный так, что он вместо заданных пользователем операций всегда делает следующее: выключает лампочку Num Lock; спит полсекунды; включает лампочку Num Lock; спит полсекунды; выключает лампочку Num Lock
  в) почему Num Lock, а не Scroll Lock? Потому что лампочка Scroll Lock почему-то не включается (хотя должна).
  г) почему требуется двойное нажатие на Scroll Lock, а не одинарное? Потому что одинарное не всегда работает. Whatever!

развитие идеи про клетки и вкусняшки

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

Итак, модифицируем дизайн.
1) На каждой вкусняшке написана ее "пищевая ценность", то есть сколько клеток из нее вырастет. Игрок в начале получает определенное число вкусняшек с разной пищевой ценностью, и его задача - расставить их по уровню таким образом, чтобы в итоге организм добрался до Главной Вкусняшки (она зафиксирована где-то на уровне) и сожрал ее.
2) Клетки будут не только размножаться, но и умирать. Но не по таким правилам, как в Game of Life: умирать они будут от старости. Организм жрет вкусняшку, возникают новые клетки, после этого каждая из этих клеток живет N тиков и умирает. В результате наш монолитный организм может разделиться на несколько отдельных, и каждый будет жить дальше своей жизнью. В моем воображении это выглядит уже более интересно и забавно. И не так угрожающе, как всепоглощающая протоплазма (мама!). Похоже на жизнь.
3) После поглощения вкусняшки новые клетки вырастают не все сразу, а с течением времени. После тика k вырастет слой клеток на расстоянии k от вкусняшки.
4) Как вариант - когда вкусняшка исчерпана, все клетки, которые находятся по одну сторону от этой вкусняшки, "по инерции" продолжают двигаться в ту же сторону, в которую они росли, отрываясь от остального организма. Не уверен, что это хорошая идея.
5) Открытый вопрос - что происходит, когда два организма сталкиваются. Самый простой вариант - просто соединяются в один, но есть и другие.

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

еще идея для игры

Буду рад услышать комментарии - насколько интересно это звучит, как можно улучшить, итп.

У нас есть сетка определенного размера, причем между некоторыми ячейками расположены стенки. Где-то на поле находится целевая ячейка, в которую надо добраться. Игрок получает клетку (как в биологии) и N вкусняшек. Он должен расставить вкусняшки по полю, поставить клетку на край поля и нажать на Start. После этого происходит автоматическая симуляция: клетка начинает делиться. Каждый раз при делении новая клетка попадает в соседнюю ячейку (подробнее дальше). Изначально у нее есть потенциал создать 10 новых клеток. Каждая съеденная вкусняшка увеличивает потенциал еще на 10. Наконец, как происходит выбор ячейки, в которой будет создана новая клетка: мы всегда выбираем ту ячейку, которая находится на минимальном расстоянии от ячейки, в которой находилась вкусняшка. Если таких ячеек больше, чем одна, то выбираем первую такую ячейку против часовой стрелке (от направления "вверх").


Возникла вот такая идея для игры с паззлами (или, скорее, набора игр). По мотивам Legend of Grimrock и иже с нею.

Есть поле фиксированного размера, скажем, 10x10. Для простоты скажем, что все клетки либо черные, либо белые (если развивать идею, то хочется еще вариантов: скажем, есть активные/неактивные, а также помеченные символами). При нажатии на каждую клетку, паттерн как-то изменится (или не изменится). Правила, по которым меняется паттерн, устанавливаются для каждого паззла отдельно. Цель - получить на поле определенный паттерн (в зависимости от задумки автора, игрок может знать или не знать целевой паттерн заранее). Дополнительно есть подсказки, которые могут появляться при достижении определенного паттерна, а также игрок может просить о подсказке, если застрял. В общем, автор паззла задает набор правил, общее описание, подсказки и целевой паттерн.

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

Основной вопрос - в том, как построить удобную и гибкую систему правил. Наверное, она не должна быть Turing-complete, иначе возможен абьюз (с другой стороны, можно постараться и сделать песочницу). Хотелось бы, чтобы ей могли довольно успешно пользоваться непрограммисты, но непонятно насколько это реалистично.

Кто-нибудь слышал о похожей системе? Мысли/идеи приветствуются.

Про Rust

Это своего рода summary моего текущего опыта работы с новым интересным языком Rust. Давно собирался написать на эту тему, но вот подвернулся удобный случай - avva просил прокомментировать опыт использования этого языка.

Мой бекграунд: много лет программирования под JVM (Java, Groovy, Kotlin, чуть-чуть Scala), само собой JS, кое-что на Objective-C, лоу-левел C+OpenGL, игрушечные проекты на OCaml. Интересуюсь ЯП.

Collapse )