tag:blogger.com,1999:blog-16250439945727107002024-02-19T06:57:27.347+02:00On The HighwaySergey Kishchenkohttp://www.blogger.com/profile/13451038740185023562noreply@blogger.comBlogger44125tag:blogger.com,1999:blog-1625043994572710700.post-86706963248293504922012-12-16T06:34:00.002+02:002012-12-16T06:48:44.139+02:00Отчёт о Dee Mon Winter Contest<div dir="ltr" style="text-align: left;" trbidi="on">
<br /></div>
По традиции участвовал в <a href="http://thedeemon.livejournal.com/56856.html">этом контесте</a> в составе команды THIRTEEN. Отчёт(осторожно, там СПОЙЛЕРЫ-СПОЙЛЕРЫ-СПОЙЛЕРЫ), написанный san'ом и brox'ом с моими небольшими дополнениями можно прочитать <a href="https://docs.google.com/document/pub?id=1phO7T882D5ZFdO8sjBe6mYVswkFdB_1DKE5ORxeXv1c">здесь</a>.
Контест выдался замечательный, вполне в духе, автору браво и аплодисменты.Sergey Kishchenkohttp://www.blogger.com/profile/13451038740185023562noreply@blogger.com2tag:blogger.com,1999:blog-1625043994572710700.post-44391945151752264512012-10-11T17:48:00.000+03:002012-10-11T17:57:28.895+03:00Talk: What every programmer should know about merging branches in MercurialUsing named branches in <a href="http://mercurial.selenic.com">Mercurial</a> can be rather difficult especially when it gets to merging these branches. There are several useful techniques and process improvements that simplify the development/release loop. You can find some of them in the talk slides I did on Oct 11, 2012 here at Quickoffice(aka DoctorMobile). It doesn't restrain any development flow and can be useful for any Mercurial (or even non-Mercurial) user. For those who are not familiar with Mercurial at all I recommend to read some <a href="http://mercurial.selenic.com/guide/">guides</a> before looking at the slides.
<a title="View What every programmer should know about merging branches in Mercurial on Scribd" href="http://www.scribd.com/doc/109713593/What-every-programmer-should-know-about-merging-branches-in-Mercurial" style="margin: 12px auto 6px auto; font-family: Helvetica,Arial,Sans-serif; font-style: normal; font-variant: normal; font-weight: normal; font-size: 14px; line-height: normal; font-size-adjust: none; font-stretch: normal; -x-system-font: none; display: block; text-decoration: underline;">What every programmer should know about merging branches in Mercurial</a><iframe class="scribd_iframe_embed" src="http://www.scribd.com/embeds/109713593/content?start_page=1&view_mode=scroll&access_key=key-2lwv40elr40eqvu32nbm" data-auto-height="true" data-aspect-ratio="1.33115468409586" scrolling="no" id="doc_54983" width="100%" height="600" frameborder="0"></iframe>
Sources for the slides can be found <a href="https://github.com/tilarids/code-quality-talk">here</a>
Sergey Kishchenkohttp://www.blogger.com/profile/13451038740185023562noreply@blogger.com0Харьков, Харьковская область, Украина49.9935 36.23038349.830175499999996 35.914526 50.1568245 36.546240000000004tag:blogger.com,1999:blog-1625043994572710700.post-56170316964910872532012-05-27T21:11:00.000+03:002012-05-27T21:24:31.994+03:00Counting bits<div dir="ltr" style="text-align: left;" trbidi="on">How would you count the number of bits set in a 32-bit integer? This question is amongst the favorite interviewing questions. The naïve approach is to loop through the bits aggregating the sum in a variable. It's already fast enough but you can make the interviewer happy with a much better "lookup table" solution: just use a static 256-entry table that contains pre-evaluated bits count for any 8-bit integer. With such table you need only 4 lookups and 4 summations to get the answer. "Lookup table" algorithm is even implemented as a GCC builtin function. Take a look at the code:
<br/><br/>
<div style="background: #ffffff; overflow:auto;width:auto;color:black;background:white;border:solid gray;border-width:.1em .1em .1em .8em;padding:.2em .6em;"><pre style="margin: 0; line-height: 125%"><span style="color: #507090">#include <stdint.h></span>
<span style="color: #008000; font-weight: bold">const</span> <span style="color: #303090; font-weight: bold">uint32_t</span> tbl[] <span style="color: #303030">=</span> {
<span style="color: #0000D0; font-weight: bold">4181239173</span><span style="color: #808080">/*,lots of random data, I used 16384 integers for tests*/</span>,<span style="color: #0000D0; font-weight: bold">2866015773</span> } ;
<span style="color: #507090">#define TEST_COUNT 100000</span>
<span style="color: #008000; font-weight: bold">static</span> <span style="color: #008000; font-weight: bold">const</span> <span style="color: #303090; font-weight: bold">uint32_t</span> ARRAY_SIZE <span style="color: #303030">=</span> <span style="color: #008000; font-weight: bold">sizeof</span>(tbl)<span style="color: #303030">/</span><span style="color: #008000; font-weight: bold">sizeof</span>(tbl[<span style="color: #0000D0; font-weight: bold">0</span>]);
<span style="color: #303090; font-weight: bold">int</span> <span style="color: #0060B0; font-weight: bold">main</span>()
{
<span style="color: #303090; font-weight: bold">uint32_t</span> i <span style="color: #303030">=</span> <span style="color: #0000D0; font-weight: bold">0</span>;
<span style="color: #008000; font-weight: bold">volatile</span> <span style="color: #008000; font-weight: bold">register</span> <span style="color: #303090; font-weight: bold">uint32_t</span> c;
<span style="color: #008000; font-weight: bold">for</span> (; i<span style="color: #303030"><</span> TEST_COUNT; <span style="color: #303030">++</span>i)
{
<span style="color: #303090; font-weight: bold">uint32_t</span> j <span style="color: #303030">=</span> <span style="color: #0000D0; font-weight: bold">0</span>;
<span style="color: #008000; font-weight: bold">for</span> (; j <span style="color: #303030"><</span> ARRAY_SIZE; <span style="color: #303030">++</span>j)
{
c <span style="color: #303030">=</span> __builtin_popcount(tbl[j]);
}
}
}
</pre></div>
<br/>
Here <i>__builtin_popcount</i> is a function that calculates the population count. If compiled with <pre>gcc -O3 t.c -o bitcount</pre> one can get such results:
<pre>$ time ./bitcount
real 0m17.465s
user 0m17.425s
sys 0m0.000s
</pre>
Not too fast, huh? Some of the time is wasted calling the function and inlining it can speed up things. But! There is even a better way. Compiling it with <pre>gcc -O3 -mpopcnt t.c -o bitcount</pre> results in:
<pre>$ time ./bitcount
real 0m1.738s
user 0m1.728s
sys 0m0.004s
</pre>
That's simply because modern processors have POPCNT instruction that can be used to count the number of bits and GCC is nice enough to support it. As you can see, in this case hardware optimization beats smart algorithm design with ease.
<h2>Resume</h2>
Algorithms are designed on paper but executed on a real hardware. Knowing what your hardware is capable of is a must for a software engineer. And please don't tell me about all these patterns and object-oriented stuff: unless you invent a machine that can run concepts instead of machine instructions, you <b>must</b> be aware of all the low-level stuff <strike>because it will save lives</strike>
because I don't want to buy a new laptop capable of running new version of nano/Notepad.<br/><br/>
I also highly recommend an awesome article <a href="http://www.strchr.com/crc32_popcnt">"Benchmarking CRC32 and PopCnt instructions"</a> for further reading.
<br /></div>Sergey Kishchenkohttp://www.blogger.com/profile/13451038740185023562noreply@blogger.com2Харьков, Харьковская область, Украина, 6100049.9935 36.23038349.830175499999996 35.914526 50.1568245 36.546240000000004tag:blogger.com,1999:blog-1625043994572710700.post-3839017574418499662012-03-29T22:09:00.004+03:002012-03-29T22:49:46.973+03:00Ruby-like blocks and yield "keyword" in CToday I want to show you some of the plain old C black magic. This is the magic of direct user context manipulating. You can use this low-level feature to implement some high-level language abstractions such as generators and ruby-like blocks. Let's start with an example(<i>test1.c</i>):<br /><!-- HTML generated using hilite.me --><div style="background: #ffffff; overflow:auto;width:auto;color:black;background:white;border:solid gray;border-width:.1em .1em .1em .8em;padding:.2em .6em;"><pre style="margin: 0; line-height: 125%"><span style="color: #507090">#include <stdio.h></span><br /><span style="color: #507090">#include <string.h></span><br /><span style="color: #507090">#include "gens.h"</span><br /><span style="color: #507090">#include "cblocks.h"</span><br /><br /><br /><span style="color: #303090; font-weight: bold">int</span> <span style="color: #0060B0; font-weight: bold">main</span>(<span style="color: #303090; font-weight: bold">int</span> argc, <span style="color: #303090; font-weight: bold">char</span><span style="color: #303030">**</span> argv)<br />{<br /> EXECUTE_BLOCK(enumerate, (<span style="color: #0000D0; font-weight: bold">1</span>, <span style="color: #0000D0; font-weight: bold">10</span>), <span style="color: #303090; font-weight: bold">int</span>, x)<br /> printf(<span style="background-color: #fff0f0">"Got %d</span><span style="color: #606060; font-weight: bold; background-color: #fff0f0">\n</span><span style="background-color: #fff0f0">"</span>, <span style="color: #303030">*</span>x);<br /> END_BLOCK<br /> <span style="color: #303090; font-weight: bold">char</span><span style="color: #303030">*</span> buf <span style="color: #303030">=</span> <span style="background-color: #fff0f0">"Hello, world!"</span>;<br /> EXECUTE_BLOCK(enumerate, (<span style="color: #0000D0; font-weight: bold">1</span>, <span style="color: #0000D0; font-weight: bold">4</span>), <span style="color: #303090; font-weight: bold">int</span>, z)<br /> printf(<span style="background-color: #fff0f0">"Saying it %d time</span><span style="color: #606060; font-weight: bold; background-color: #fff0f0">\n</span><span style="background-color: #fff0f0">"</span>, <span style="color: #303030">*</span>z);<br /> EXECUTE_BLOCK(for_each, (buf, buf <span style="color: #303030">+</span> strlen(buf)), <span style="color: #303090; font-weight: bold">char</span>, c)<br /> printf(<span style="background-color: #fff0f0">"%c."</span>, <span style="color: #303030">*</span>c);<br /> END_BLOCK<br /> printf(<span style="background-color: #fff0f0">"</span><span style="color: #606060; font-weight: bold; background-color: #fff0f0">\n</span><span style="background-color: #fff0f0">"</span>);<br /> END_BLOCK<br /><br /> <span style="color: #008000; font-weight: bold">return</span> <span style="color: #0000D0; font-weight: bold">0</span>;<br />}<br /></pre></div><br />The code above is a valid C code. It produces such output:<br /><!-- HTML generated using hilite.me --><div style="background: #ffffff; overflow:auto;width:auto;color:black;background:white;border:solid gray;border-width:.1em .1em .1em .8em;padding:.2em .6em;"><pre style="margin: 0; line-height: 125%">Yielding 1<br />Got 1<br />Yielding 2<br />Got 2<br />Yielding 3<br />Got 3<br />Yielding 4<br />Got 4<br />Yielding 5<br />Got 5<br />Yielding 6<br />Got 6<br />Yielding 7<br />Got 7<br />Yielding 8<br />Got 8<br />Yielding 9<br />Got 9<br />Yielding 1<br />Saying it 1 time<br />H.H.e.e.l.l.l.l.o.o.,.,. . .w.w.o.o.r.r.l.l.d.d.!.!.<br />Yielding 2<br />Saying it 2 time<br />H.H.e.e.l.l.l.l.o.o.,.,. . .w.w.o.o.r.r.l.l.d.d.!.!.<br />Yielding 3<br />Saying it 3 time<br />H.H.e.e.l.l.l.l.o.o.,.,. . .w.w.o.o.r.r.l.l.d.d.!.!.<br /></pre></div><br />Let's take a look on the implementation of used generators (<b>enumerate</b>, <b>for_each</b> in <i>gens.c</i>):<br /><!-- HTML generated using hilite.me --><div style="background: #ffffff; overflow:auto;width:auto;color:black;background:white;border:solid gray;border-width:.1em .1em .1em .8em;padding:.2em .6em;"><pre style="margin: 0; line-height: 125%"><span style="color: #507090">#include "gens.h"</span><br /><span style="color: #507090">#include <stdio.h></span><br /><br />START_GENERATOR(<span style="color: #303090; font-weight: bold">int</span>, enumerate, (<span style="color: #303090; font-weight: bold">int</span> start, <span style="color: #303090; font-weight: bold">int</span> end))<br /> <span style="color: #303090; font-weight: bold">int</span> i <span style="color: #303030">=</span> start;<br /> <span style="color: #008000; font-weight: bold">for</span>(; i<span style="color: #303030"><</span>end; <span style="color: #303030">++</span>i)<br /> {<br /> printf(<span style="background-color: #fff0f0">"Yielding %d</span><span style="color: #606060; font-weight: bold; background-color: #fff0f0">\n</span><span style="background-color: #fff0f0">"</span>, i);<br /> YIELD(i);<br /> }<br />END_GENERATOR<br /><br />START_GENERATOR(<span style="color: #303090; font-weight: bold">char</span>, for_each, (<span style="color: #303090; font-weight: bold">char</span><span style="color: #303030">*</span> start, <span style="color: #303090; font-weight: bold">char</span><span style="color: #303030">*</span> end))<br /> <span style="color: #008000; font-weight: bold">while</span> (start <span style="color: #303030">!=</span> end)<br /> {<br /> YIELD(<span style="color: #303030">*</span>start);<br /> YIELD(<span style="color: #303030">*</span>start); <span style="color: #808080">// intentionally</span><br /> <span style="color: #303030">++</span>start;<br /> }<br />END_GENERATOR<br /></pre></div><br />As you can see, the implementation of generators is pretty straightforward. All the magic is done in <i>cblocks.h</i>:<br /><!-- HTML generated using hilite.me --><div style="background: #ffffff; overflow:auto;width:auto;color:black;background:white;border:solid gray;border-width:.1em .1em .1em .8em;padding:.2em .6em;"><pre style="margin: 0; line-height: 125%"><span style="color: #507090">#include <stdlib.h></span><br /><span style="color: #507090">#include <ucontext.h></span><br /><br /><span style="color: #507090">#define DECLARE_GENERATOR(type, name, params) extern ucontext_t name ## _context__; \</span><br /><span style="color: #507090">extern ucontext_t name ## _out_context__; \</span><br /><span style="color: #507090">extern int name ## _finished__; \</span><br /><span style="color: #507090">extern type name ## _out_var__; \</span><br /><span style="color: #507090">extern void name ## _fun__ params</span><br /><br /><span style="color: #507090">#define START_GENERATOR(type, name, params) ucontext_t name ## _context__; \</span><br /><span style="color: #507090">ucontext_t name ## _out_context__; \</span><br /><span style="color: #507090">int name ## _finished__ = 0; \</span><br /><span style="color: #507090">type name ## _out_var__; \</span><br /><span style="color: #507090">void name ## _fun__ params \</span><br /><span style="color: #507090">{ \</span><br /><span style="color: #507090">name ## _finished__ = 0; \</span><br /><span style="color: #507090">int* current_finished = & name ## _finished__; \</span><br /><span style="color: #507090">ucontext_t* current_context = & name ## _context__; \</span><br /><span style="color: #507090">ucontext_t* current_out_context = & name ## _out_context__; \</span><br /><span style="color: #507090">type* current_var = & name ## _out_var__;</span><br /><br /><span style="color: #507090">#define END_GENERATOR *current_finished = 1; \</span><br /><span style="color: #507090">}</span><br /><br /><span style="color: #507090">#define YIELD(x) *current_var = x; swapcontext(current_context, current_out_context);</span><br /><span style="color: #507090">#define EXECUTE_BLOCK(gen, params, type, varname) do{ type* varname = & gen ## _out_var__; \</span><br /><span style="color: #507090">ucontext_t* current_context = & gen ## _context__; \</span><br /><span style="color: #507090">ucontext_t* current_out_context = & gen ## _out_context__; \</span><br /><span style="color: #507090">volatile int gen ## _temp_var__ = 0; \</span><br /><span style="color: #507090">getcontext(& gen ## _out_context__); \</span><br /><span style="color: #507090">if (gen ## _temp_var__ == 0) \</span><br /><span style="color: #507090">{ \</span><br /><span style="color: #507090"> gen ## _temp_var__ = 1; \</span><br /><span style="color: #507090"> gen ## _fun__ params; \</span><br /><span style="color: #507090">}\</span><br /><span style="color: #507090">else \</span><br /><span style="color: #507090">{ \</span><br /><span style="color: #507090"> while (! gen ## _finished__) { </span><br /><span style="color: #507090"> </span><br /><span style="color: #507090">#define END_BLOCK swapcontext(current_out_context, current_context); } \</span><br /><span style="color: #507090">} \</span><br /><span style="color: #507090">} while(0);</span><br /></pre></div><br />Manual pages for <b>swapcontext</b> and <b>getcontext</b> can help in understanding what's going on here.<br /><h3>Resume</h3><ul><li>It's possible to implement nifty language features in C using its low-level features. The generators described above can be even used to build cooperative multitasking systems.</li><li>It doesn't mean that you should do it just because you can ;). Beware that context manipulating doesn't work on all platforms.</li><li>You can find the source code <a href="https://github.com/tilarids/cblocks">on github</a>. The code should be considered just a playground so please forgive me its untidiness. If you want something mature(e.g., you're seeking for coroutines support in C), check out the <a href="http://swtch.com/libtask/">libtask</a>, <a href="https://github.com/dankamongmen/libtorque">libtorque</a> or <a href="http://software.schmorp.de/pkg/libcoro.html">libcoro</a></li></ul><br />As always I will be happy to accept any criticism on the code above. Feel free to contact me in any way you can imagine.Sergey Kishchenkohttp://www.blogger.com/profile/13451038740185023562noreply@blogger.com2tag:blogger.com,1999:blog-1625043994572710700.post-18965286521699802602011-08-03T11:55:00.004+03:002012-08-30T13:24:22.667+03:00Kharkov DOU Hackathon - отчёт об участии<blockquote>A hackathon, a hacker neologism, is an event when programmers meet to do collaborative computer programming(c) wiki</blockquote>Вышеобозначеный хакатон проходил в Харькове 30-31 августа в соревновательном виде. За сутки нужно было написать что-нибудь интересное и команда Von Neumann Architecture в составе двух человек приняла вызов. В качестве задачи мы выбрали портирование Pascal игрушки 1994-го года на HTML5/JS посредством написания Haskell транслятора. Исходники <a href="https://github.com/tilarids/pascal2js">здесь</a>. Полноценный отчёт можно почитать <a href="http://von-neumann-architecture.blogspot.com/2011/08/blog-post.html">здесь</a>. Также можно посмотреть онлайн демку, демка доделывалась уже после Хакатона. Цитата:<blockquote>Повторяю, вы видите как работает интерпретатор многопоточного (yield) Javascript, сконвертированного (via Haskell) из Turbo Pascal, сам интерпретатор Javascript-а "Rhino" написан на Java, портирован (via gwt + ножницы) в Javascript.<br />Внизу работающая программа, проверено под Chrome, Mozilla. Если в опере загрузить ее отладчик DragonFly, то там отчего-то тоже начинает работать.</blockquote><iframe width="900PX" height="700px" src="http://kishchenko.info/static/pascal2js/RhinoGWT.html"></iframe>Sergey Kishchenkohttp://www.blogger.com/profile/13451038740185023562noreply@blogger.com0tag:blogger.com,1999:blog-1625043994572710700.post-32073140176559882562011-06-22T00:30:00.001+03:002011-06-22T01:30:54.282+03:00ICFPC 2011<blockquote>(((S (K (S ((S (K S)) ((S (K (S I))) K))))) ((S (K K)) K)) awesome! was ICFPC)</blockquote><br />ICFP Contest 2011 точно войдет в список лучших ICFP контестов всех времен. Причина тому - интересное непутанное задание, которое при этом довольно сложное и хорошо продуманное. Я, как и в прошлом году, принимал участие в составе команды THIRTEEN. Отчёты от команды можно найти на сайте <a href="http://thirteen.kharkov.ru">http://thirteen.kharkov.ru</a>(сейчас там только один <a href="http://thirteen.kharkov.ru/2011/06/20/icfp-contest-2011-otchet-writeup-san/">отчёт</a>). Здесь постараюсь дать описание контеста со своей точки зрения.<br />Для меня контест начинался вдали от команды(я находился в командировке в Лондоне). Прочтение задания вызвало бурную радость(я как раз готовился к контесту написанием парсера и эвалуатора для лямбда-калькулюса). Из-за удаленности от команды я решил код не писать, а сосредоточиться на изучении того, что мы можем сделать с помощью карт. Это оказалось правильным решением - мои коллеги написали всё намного быстрее и лучше, чем с моим участием :) Первая ночь прошла в попытках использовать Y комбинатор для создания рекурсивных функций. К сожалению, strict evaluation не давал этого сделать. И даже Y комбинаторы для applicative order не работали. Также не получалось и организовать рекурсию через SII. Утром пятницы я отправился на работу, но потратил большую часть рабочего времени на исследование системы. Результатом этого стала "недорекурсия" через get ячейки. А по окончанию рабочего дня пришло лучшее понимание того, как работает вычисление в предложенной системе, и это дало возможность вывести настоящую рекурсию по аналогии с выводом Y комбинатора. Это позволило писать рекурсивные функции, пробегающие по всем ячейкам. К счастью, организаторы ограничили количество аппликаций одной тысячей(к счастью - потому что увеличение количества аппликаций до 3839 позволило бы уничтожать противника где-то на 85 ходу). И из-за этого ограничения рекурсивные функции пробегались только по нескольким ячейкам и самоуничтожались после применения.<br />К этому моменту в Харькове был написан конвертер из лямбда выражений в SKI выражения и конвертер из SKI выражений в программы. В ночь с пятницы на субботу я пытался оптимизировать конвертер и генерировать с его помощью выражения, вызывающие рекурсивный обход ячеек. Результат: больше 89 ячеек за один запуск для односложных команд при помощи настоящей рекурсии не обойти. Ночью же вылетел в Харьков(и наконец выспался в самолете). По прилету обнаружил, что коллеги вовсю думают над однотактными и двухтактными пушками. Идея была в том, чтобы создать пушку, которая будет уничтожать вражескую ячейку и восстанавливать после этого vitality. Двухтактная пушка перенаправлялась на следующую ячейку двумя тактами, однотактная(гениальное изобретение Sas/Rst) - одним. К вечеру пришло осознание того, что нам нужно писать хитрого стратега, который будет решать, какие выражения применять. San создал инфраструктуру для написания ботов-стратегов, и к этому моменту был написан язык для описания действий(by San/Dzhulgakov). Я продолжал в душе лелеять надежду на использование рекурсивных выражений и начал создавать ботов и стравливать их в турнире. Конечным результатом этого процесса к 10 утра воскресенья стал SuicideBot(убийца-камикадзе) и, главное, ZombaBot - бот, который за ~150 ходов уничтожал ~40 ячеек противника, а еще за ~90 ходов стирал всю информацию из них. Начальная стратегия использовала настоящую рекурсию(синтаксис языка не приводится):<br /><pre><code>power@0 = 8192;<br />@1 = (S (attack 0 0) (attack 1 0) (get 0));<br />pois@2 = ^x. (help x x @power);<br />part@3 = ^n.^f. (f (S @pois succ n) f);<br />part_func@4 = ^y. (@part (y 0) ) @part;<br />@5 = (dec 0) (zombie 0 @part_func);<br />newpois@6 = ^xx. (zombie xx I);<br />newpart@7 = ^nn.^ff. (ff (S @newpois succ nn) ff);<br />newpart_func@8 = (@newpart 219) @newpart;</code></pre><br />Также в это время формируется SanBot(by San) - консервативный бот, который умеет защищаться, уничтожая "горячие" ячейки противника. В свободное время он собирает более быстрые атакующие программы и переключается на них. San постоянно развивал своего бота, тренируясь на кошках - на SuicideBot и ZombaBot. В схватках с ZombaBot он научился закрывать порталы для зомби, а по дороге научился воскрешаться, восстанавливать команды из кеша, красть константы. ZombaBot тоже не стоял на месте. Sas подхватил идею с использованием copy для организации рекурсии и придумал, как с ее помощью сделать обход ячеек. В конечном итоге, этот способ и оказался самым эффективным способом обхода. Он дал возможность ZombaBotу полностью уничтожать противника за 4 запуска рекурсивного зомби, за 198 тактов. К этому времени submissionы SanBotа показали, что он слишком консервативен, и поэтому не столь эффективен. Воспользовавшись наработками, я добавил еще и UndeadRiseBotа - бота, который пытался уничтожить противника за 198 ходов, а после этого переключался на SanBotа. Этот бот оказался весьма эффективным - он крошил противников на неофициальном сервере и даже побеждал самого SanBotа, потому что использовал его же механизмы лечения. Мы продолжали развивать эту идею и оптимизировать код. Результат(язык получился довольно мощный и выразительный, а к концу контеста Dzhulgakov добавил в него и средства для ручной оптимизации):<br /><pre><code>power@0 = 8192;<br />@24 = (attack 0 0) (get 0);<br />@24 = (attack 1 0) (get 0);<br />pois@1 = ^x. (help x x @power);<br />!clear @0;<br />part@0 = \x. ((@pois x) (copy (K 0 x)) (succ x));<br />!clear @1;<br />part_func@1 = ^z.^y. ((get 0) (y z));<br />@128 = (S zombie @part_func);<br />// optional dec 0; here is done by UndeadRiseBot <br />@128 += @@ 0;<br />address@2 = 66;<br />@129 ~ zombie1 = (zombie 0 (@part_func @address));<br />// optional dec 0; here is done by UndeadRiseBot <br />!continue zombie1;<br />@2 += dbl @@;<br />@130 ~ zombie2 = (zombie 0 (@part_func @address));<br />// optional dec 0; here is done by UndeadRiseBot <br />!continue zombie2;<br />!clear @2;<br />@2 = 198;<br />@131 ~ zombie3 = (zombie 0 (@part_func @address));<br />// optional dec 0; here is done by UndeadRiseBot <br />!continue zombie3;<br /></pre></code><br />Этот вариант уничтожал противника за 177 ходов. В копилке наших знаний есть еще парочка оптимизаций, которые должны уменьшить код до 171-172 ходов. Хочется верить, что это минимальная программа, которая уничтожает безвольного противника. <br />Всё это время Sas собирал своего бота - SasBot, который использовал супероружие - зомбопушку (убить+стереть). Он добился того, что своей пушкой уничтожал и SanBotа, и UndeadRiseBotа. Но, к сожалению, он был готов слишком поздно и не очень хорошо справлялся с реальными противниками на официальном сервере, поэтому в последний момент было решено сабмитить UndeadRiseBota, который в душе - SanBot. <br /><br />Выводы по окончанию контеста: по результатам битв на неофициальном сервере видно, что наш бот неплох, но далеко не лучший. Что особенно интересно - есть сильные боты, которые используют сходную с нами тактику, но при этом побеждают нас. Это значит, что мы просто не отладили бота окончательно. Еще стоит пожалеть о судьбе SasBotа. Он был готов слишком поздно, чтобы его достижения использовать в SanBot/UndeadRiseBot, и не был готов к submission самостоятельно. Основной вывод - нужно было начинать создавать ботов и описывать стратегии раньше. Тогда к концу контеста у нас бы было лучшее понимание того, какая тактика оптимальна.<br /><br />Как я уже говорил выше - один из лучших ICFP contests за всё время, что я о нём знаю. Спасибо организаторам - великолепное задание и отличная организация. Спасибо каждому из команды THIRTEEN. Мне кажется, мы отлично сыгрались и можем и будем таким составом выигрывать :)Sergey Kishchenkohttp://www.blogger.com/profile/13451038740185023562noreply@blogger.com1tag:blogger.com,1999:blog-1625043994572710700.post-48990875744409771602011-04-01T19:00:00.001+03:002011-04-01T19:12:22.615+03:00Talk: (Non) Comprehensive Guide to C/C++ Source Code QualityI did a talk on C/C++ source code quality tools here at Quickoffice. I believe it could be helpful for the C/C++/ObjC developers(especially for those who care about quality). Here goes the list of the tools mentioned: <ul><li>CPD</li><li>gcc</li><li>clang</li><li>Valgrind</li><li>cppcheck</li><li>EDoc++</li><li>GCOV</li><li>gcovr</li><li>LCOV</li><li>avalanche</li><li>frama-c</li></ul><a title="View (Non) Comprehensive Guide to C/C++ Source Code Quality on Scribd" href="http://www.scribd.com/doc/52077820/Non-Comprehensive-Guide-to-C-C-Source-Code-Quality" style="margin: 12px auto 6px auto; font-family: Helvetica,Arial,Sans-serif; font-style: normal; font-variant: normal; font-weight: normal; font-size: 14px; line-height: normal; font-size-adjust: none; font-stretch: normal; -x-system-font: none; display: block; text-decoration: underline;">(Non) Comprehensive Guide to C/C++ Source Code Quality</a> <object id="doc_4897" name="doc_4897" height="600" width="100%" type="application/x-shockwave-flash" data="http://d1.scribdassets.com/ScribdViewer.swf" style="outline:none;" > <param name="movie" value="http://d1.scribdassets.com/ScribdViewer.swf"> <param name="wmode" value="opaque"> <param name="bgcolor" value="#ffffff"> <param name="allowFullScreen" value="true"> <param name="allowScriptAccess" value="always"> <param name="FlashVars" value="document_id=52077820&access_key=key-2crxaf7sx057hq5y54m4&page=1&viewMode=slideshow"> <embed id="doc_4897" name="doc_4897" src="http://d1.scribdassets.com/ScribdViewer.swf?document_id=52077820&access_key=key-2crxaf7sx057hq5y54m4&page=1&viewMode=slideshow" type="application/x-shockwave-flash" allowscriptaccess="always" allowfullscreen="true" height="600" width="100%" wmode="opaque" bgcolor="#ffffff"></embed> </object><br />You can find LaTeX source and .cpp source files <a href="https://github.com/tilarids/code-quality-talk">at github</a>Sergey Kishchenkohttp://www.blogger.com/profile/13451038740185023562noreply@blogger.com0tag:blogger.com,1999:blog-1625043994572710700.post-50709003292594088642010-06-23T18:45:00.001+03:002010-07-30T12:57:35.462+03:00Отчёт об ICFPC-2010<blockquote>До чего дошёл прогресс -<br />До невиданных чудес!<br />Опустился на глубины<br />И поднялся до небес.<br /><br />Позабыты хлопоты, остановлен бег -<br />Вкалывают роботы, а не человек.</blockquote><h2>Введение</h2>ICFPC-2010 закончился еще в понедельник, но он оказался настолько емким, что полтора дня я только и мог, что кататься на велосипеде и проветривать мозги. Да и сейчас на подробный отчёт меня не хватит, так что ограничусь только кратким описанием того, что происходило со мной во время ICFPC-2010.<br />Итак, начнём с того, что в этом году меня пригласили поучаствовать вживую в харьковской команде THIRTEEN. Команда сыгранная и довольно сильная, до этого я с ними сталкивался на Sapka и ICFPC-2009. <br />На время прохождения контеста мы все собрались в квартире-офисе одного из членов команды. Отсюда первое и самое сильное впечатление: общение с живыми людьми, участие действительно в реальном времени(без перерывов на сон в собственной постели) - это нечто невообразимое. Представьте, что вы провалились в кроличью нору и попали в страну, где жители решают странные задачки, где сон и еда - досадные раздражители, а производительность труда взлетает до небес.<br />Второе впечатление - для участия в таком конкурсе нужна не команда из программистов, каждый из которых будет писать код. Нужны математики, физики, спецы по схемотехнике и прочие головастики. А программить могут 2-3 человека, не более того.<h2>Кратко о происходившем</h2>Задание повторять не буду, вы можете найти его краткое описание в <a href="http://users.livejournal.com/_adept_/106759.html">отчете Futamura Rejection</a>. В первую очередь, все бросились разбирать формат фабрики. Довольно быстро я написал парсер на Python, который генерил картинки в graphviz. Однако красивыми картинки сделать не получилось и в итоге все фабрики рисовались на бумаге. Как только с форматом более-менее разобрались, начали подбирать функцию гейтов. Мудрым решением здесь было предположить, что Undefined сигнала не существует и он заменяется 0. Я сделал простейший эмулятор на Python и с его помощью пытался подобрать функцию гейта(в виде матрицы). Но где-то в коде закрался баг и пока я его искал, sannysanoff на Java реализовал такой же симулятор без багов и нашел эту самую функцию. <br /><br />А дальше пошло самое интересное: нужно было придумать генератор, который будет генерить фабрики в соответствии с нужной выходной последовательностью. При этом на входную последовательность завязываться было нельзя. Пока я крутил в голове всякие мысли со стейтами, переходами между ними и применением алгоритмов из теории графов для построения таблицы переходов между стейтами, Rst7 и SAS мозговым штурмом предложили довольно простой и естественный способ генерации фабрик из таких макроэлементов, как "генератор 0", "генератор 1", "генератор 2", "задержка", "задержка с вычитанием", "вычитатель". sannysanoff его быстро закодил(кстати, я впервые видел применение настоящего ООП в спортивном программировании. До этого я считал, что ООП слишком затратно, чтобы его применять при жестких временных рамках). Фабрики получались довольно большими, но работали. <br /><br />Это был вечер пятницы. Начиная с этого момента начинается хмурая и безрадостная эпопея разгадывания внутреннего кода машин и топлива. Одна из причин этой хмурости (и один из основных лучей ненависти к организаторам) - в том, что попытки работать из под одного IP на нескольких машинах заканчивались провалом. Видимо, организаторы сделали привязку по IP и, соответственно, если заходить всем под разными аккаунтами, то аккаунты шарились между машинами, а при заходе по одному аккаунту высвечивался Internal Error. В итоге, я и sannysanoff зарегистрировали два фейковых аккаунта (fake001 и fake002) и использовали их через собственные туннели. Аккаунт THIRTEEN был под управлением brox и через его машину мы сабмитили официальные решения. Таким образом, несмотря на то, что участников было довольно много, разбираться с форматом данных могли только два, максимум три человека: ведь для того, чтобы понять формат, нужен был доступ к серверу.<br /><br />Суббота прошла туманно. С утра я написал на Python скрипты, которые позволяли заливать тривиальные решения для тривиальных машин. Это дало ощутимый прирост к очкам. Всё остальное время было посвящено разгадыванию кода. Почему-то это шло очень медленно и к вечеру субботы полного понимания даже структуры топлива еще не было. Более-менее был ясен только способ кодирования чисел. Где-то в это же время я написал command-line интерфейс к парсеру на сервере, открыл к своей машине терминальный доступ и за разгадывание формата взялся Rst7. После нескольких часов, он предложил вариант формата, который мы успешно(!) использовали до утра понедельника. После этого Rst7 и SAS увлеклись идеей оптимального генератора фабрик. Они его разработали, хотя я до сих пор лучше понимаю, как работает первый вариант генератора. <br /><br />Таким образом, к началу воскресенья у нас не было еще формата описания машин и не было никаких наработок по алгоритмам их решения. Я не помню точного времени, но где-то в этот момент, руководствуясь подсказками из чатов, до меня начал доходить формат описания машин. Однако полностью это понимание сформировалось позже. Читая отчёты других команд, я завидовал тем людям, которые выписав колонки чисел, сразу догадались, что два формата чисел отличаются сдвигом и отбрасыванием двойки. Я к этому сдвигу шел долгие часы, а 22 вообще долгое время считал признаком начала списка. Всё же, совместно с sannysanoff мы разобрали этот формат, я написал простенький енкодер машин. Еще ранее был написан интеллектуальный посылатель тривиальных машин. Он проработал совсем немного - до момента падения сервера. После поднятия сервера организаторы отключили нужные для работы ссылки на список всех машин, но оставили рабочей скрытую в недрах ссылку на список всех машин с принадлежностью к командам. Переписать скрипт, чтобы он использовал эту ссылку - дело 3-х минут. Как я понимаю, к моменту, когда мой бот снова начал работать, остальные участники еще не успели модифицировать собственные скрипты - скорость работы сервера была великолепна!<br /><br />Также где-то в ночи появился переборный решатель от sannysanoff и dshoot. К нему так же был написан скрипт на Python, который запускал программу на Java для нахождения решений и отсылал результаты на сервер. Так решались небольшие нетривиальные машины. В это же время стало очевидно, что мы многое теряем, н придумывая свои машины. Этим занимались SAS и brox. В это же время действовало ограничение на 100 символов на машину. Поэтому почти все наши машинки - небольшие и поддаются перебором. К сожалению, мы пропустили момент, когда ограничение на 100 символов было снято.<br /><br />Утром в понедельник вовсю работали скрипты, мы постили шаблонные машинки, а sannysanoff обнаружил, что топливо у нас кодируется неправильно. Часов за 7 до окончания контеста. Однако проблему удалось решить, хотя это нам и не сильно помогло. Последние участники разбрелись за час до окончания.<h2>Итог</h2>30 место, 69 машинок, около 700 топлив. Великолепное задание, отвратные кодировки. Я успел покодить на Python, C и Java. Кстати, этот ICFPC-2010 - наглядное доказательство того, что скриптовые языки вроде Python - очень нужны в таких контестах. Без Python не было бы ботов, написанных в считанные минуты, без Python не было бы быстрого прототипирования.<h2>Заключение</h2>В голове у меня эти дни отпечатались размыто. Действительно, как сон Алисы о Стране Чудес. Я мог перепутать время, потому что не помню, когда заканчивался один день и начинался другой. Я ничего не упомянул о том, как brox пытался на С подобрать очень короткие макроэлементы а я писал ему алгоритм пермутаций, как я оптимизировал генераторы 1 с задержкой, как вместе с Rst7 мы пытались решить машины аналитически с помощью Matlab, как я пытался реализовать рекурсивный энкодер чисел и как у меня ничего не вышло.<br /><br /><a href="http://thirteen.kharkov.ru/2010/06/21/team-thirteen-otchet-icfpc-2010/">Немного сумбурный отчёт от sannysanoff</a>. Если чей-то ник или какие-то события я указал неправильно - поправляйте.<br /><a href="http://br0x.livejournal.com/2545.html"> ICFPC 2010 - кулаками после боя (by brox)</a>Sergey Kishchenkohttp://www.blogger.com/profile/13451038740185023562noreply@blogger.com1tag:blogger.com,1999:blog-1625043994572710700.post-45921654092016091072010-03-17T17:00:00.002+02:002010-07-05T17:15:14.547+03:00Некоторые трюки при использовании GDBНебольшое собрание трюков, которые могут помочь при отладке с использованием GDB. Не претендует на сенсационность, но должно быть полезно для тех, кто только начинает знакомиться с этим замечательным инструментом. Итак, начнём:<br /><h2>Печать содержимого STL контейнеров</h2>Основные способы собраны <a href="http://sourceware.org/gdb/wiki/STLSupport">здесь</a>, но я бы хотел остановиться на наиоболее универсальном способе - <a href="http://sourceware.org/gdb/wiki/STLSupport?action=AttachFile&do=view&target=stl-views-1.0.3.gdb">gdb-stl-views</a>(нужно добавить в ~/.gdbinit). Он будет работать не только в самых новых версиях, а и в уже устаревших (это является важным фактором для тех, кто не может обновиться). Примеры использования:<br /><pre>(gdb) plist some_list<br />List size = list_size<br />List type = std::list<element_type, std::allocator<element_type> ></pre>Соответственно, для того, чтобы распечатать весь список нужно использовать:<br /><pre>(gdb) plist some_list element_type<br />elem[0]: $i = ...<br />...<br />elem[list_size - 1]: $i = ...<br />List size = list_size </pre>А теперь интересные моменты: <ul><li>Если внутри контейнера хранится умный указатель, то часто для упрощения вывода можно в качестве element_type указать просто указатель (зависит от того, какой умный указатель вы используете. Большая часть из них при reinterpret_cast к указателю даст осмысленный результат). Например, вместо <pre>plist some_list smart_ptr<elem_type></pre> использовать <pre>plist some_list elem_type*</pre></li><li>Если вы активно используете пространства имён, element_type скорее всего будет доступен только с полным указанием пространств имён, например NS1::NS2::element_type. Интересной особенностью GDB является то, что он не воспринимает NS1::NS2::element_type* как тип. Обойти эту проблему можно заключив имя типа в одинарные кавычки: 'NS1::NS2::element_type'* </li><li>GDB иногда игнорирует using namespace. Поэтому лучше просто полностью указывать имя типа со всеми пространствами имён</li><li>Чем новее у вас версия GDB, тем лучше он работает с пространствами имён. Если есть возможность - поставьте GDB 7.0 и выше</li></ul><h2>Вывод строк</h2>Если вы активно работаете с разными типами строк, с разным размером символов, то вам пригодится следующий совет. Чтобы вывести строку, которую не желает выводить print, можно использовать:<ul><li>Команду просмотра памяти x. Например, <pre>(gdb) x/16s some_char_ptr</pre> для вывода 16 первых символов в символьном виде</li><li>Можно добавить вот такую функцию в .gdbinit:<br /><pre>define wchar_print<br /> echo "<br /><br /> set $i = 0<br /> while (1 == 1)<br /> set $c = (char)(($arg0)[$i++])<br /> if ($c == '\0')<br /> loop_break<br /> end<br /> printf "%c", $c<br /> end<br /><br /> echo "<br /><br />end</pre>Использовать так: <pre>(gdb) wchar_print some_char_ptr</pre>Однообразно выводит std::string, std::wstring, различные двухбайтные строки. Естественно, конвертация к ASCII строке приводит к потере информации, однако в большинстве случаев это не так важно</li></ul><h2>Step Out</h2>Самый короткий совет. Step Out делается командой fin или finish. Это почему-то один из самых распространённых вопросов.<br /><br /><br /><i>И the last but not the least: в последнее время я довольно редко пишу в этот блог. Одна из причин тому - для небольших спонтанных записей я веду <a href="http://juick.com/tilarids/">микроблог</a>. Вторая - банальная нехватка времени. Однако не спешите отписываться: в записной книжке скопилось множество интересных статей, советов и идей. Постараюсь возобновить более-менее равномерное наполнение этого блога.</i><br /><br />P.S. Для вывода на экран Qt строк можно использовать вот такое:<br /><pre>define printqstring<br /> printf "(QString)0x%x (length=%i): \"",&$arg0,$arg0.d->size<br /> set $i=0<br /> while $i < $arg0.d->size<br /> set $c=$arg0.d->data[$i++]<br /> if $c < 32 || $c > 127<br /> printf "\\u0x%04x", $c<br /> else<br /> printf "%c", (char)$c<br /> end<br /> end<br /> printf "\"\n"<br />end</pre>Sergey Kishchenkohttp://www.blogger.com/profile/13451038740185023562noreply@blogger.com1tag:blogger.com,1999:blog-1625043994572710700.post-32293317675552998842010-02-01T18:15:00.000+02:002010-02-01T18:21:31.337+02:00Краткий отчёт о PyCampНе далее как в прошлую субботу, 30 января 2010, в Киеве состоялась конференция <a href="http://pycamp.org.ua/">PyCamp Kyiv</a>, основной темой которой был язык Python и сопутствующие технологии. Мне повезло там побывать, и я получил <b>огромное</b> удовольствие от конференции.<h2>Доклады</h2>В основном, доклады были довольно интересными. Ниже представлены некоторые претензии/отзывы по докладам, а также оценка качества повествования/слайдов:<br /><ul><li><i>Александр Шигин "Почему Python - тормоз и как заставить его меньше тормозить"</i> - неплохой доклад о том, какие конструкции в Python тормозят сильнее, чем другие. Для многих информация из доклада может показаться очевидной, но для меня она оказалась довольно полезной - позволила кое-как классифицировать разрознённые знания по этой теме. Качество повествования-3+, качество слайдов-5.</li><li><i>Юрий Юревич "Рецепты декораторов"</i> - очень короткий и довольно малоинформативный доклад о том, что такое декораторы в Python. Несмотря на хорошие слайды(на 5) и доклад(на 4+)</li><li><i>Дмитрий Кожевин "Программирование на нервах"</i> - отличный развлекательный доклад на тему управления проектами. Он небольшой и веселый, поэтому смотреть в видеозаписи обязательно. Качество доклада - 5, качество слайдов - 3.</li><li><i>Михаил Кашкин "Работа с хранилищем данных в Google App Engine, отличия от реляционной модели"</i> - доклад сочетает в себе общий обзор Datastore и описание некоторых особенностей. Доклад, в принципе, неплохой, но неполный. После него осталось очень много вопросов. Качество слайдов - 5, качество повествования - 4.</li><li><i>Александр Соловьев "Redis: Дикий Запад баз данных"</i> - хороший доклад про сверх-быструю key-value db. Удачно выбранная тема в данном случае на 80% определила успех доклада. Качество повествования - 5, качество слайдов - 5</li><li><i>Андрей Светлов "Безопасная разработка ПО. Результат длинного пути и множества набитых шишек"</i> - доклад о том, как важно использовать тесты, системы автоматической сборки и прочие вспомогательные тулзы. Довольно длинно, в основном по местам давно обглоданным. К тому же для многих тема "Тестировать или не тестировать" уже далеко не так остра, как была пару лет назад. Качество повествования - 4, качество слайдов - 4.</li><li><i>Владимир Пузанов, Владимир Кириллов "Расширение и встраивание Python"</i> - обзорный доклад об интерпретаторах Python, методах расширения стандартной функциональности и связывание с другими ЯП. Было весьма интересно, а продемонстрированный в конце хак нахожу очень приятным и довольно юзабельным. Качество повествования - 4+, качество слайдов - 3.</li><li><i>Андрей Мишковский "Использование Python в ГИС"</i> - неплохой обзорный доклад о средствах и библиотеках для создания ГИС на Python. Хотя я бы с большим удовольствием послушал о том, <i>как</i> создаются ГИС, а не с помощью чего(эту информацию можно получить и в Google). Качество повествования - 5, качество слайдов - 5.</li><li><i>Сергей Кириллов "WebSockets в Twisted"</i> - неплохой вводный доклад на тему "Что такое WebSockets?". Тема не очень сложная и была полностью раскрыта. Качество повествования - 5, качество слайдов - 5.</li><li><i>Александр Бельченко "Интернационализация и локализация Python-приложений с использованием gettext"</i> - подробный доклад об использовании gettext для локализации GUI приложений на Python. Большую часть информации из доклада можно получить при чтении документации, но докладчик также обозначил множество интересных и полезных моментов. Качество повествования - 4+, качество слайдов - 5.</li><li><i>Иван Моргун "Работа с платежными системами в Django (PayPal, WebMoney)"</i> - излишне подробный доклад, практически пересказ документации. Доклад можно было существенно порезать и он от этого стал бы более привлекательным. Качество повествования - 3+, качество слайдов - 3+.</li><li><i>Дмитрий Жемеров "PyCharm – новая python IDE от JetBrains"</i> - весьма любопытная презентация новой коммерческой IDE для Python. Выглядит весьма многообещающе, но то, что оно написано на Java, а также будет в будущем стоить $100, слегка портит впечатление. Качество повествования - 5, качество слайдов :) - 5</li></ul><h2>Организация</h2>Организована конференция была просто восхитительно: с онлайн-трансляцией, вкусными бутербродами, с вайфаем, с прямой трансляцией на большой экран сообщений из твиттера (<a href="http://search.twitter.com/search?q=%23pykyiv+tilarids">мои сообщения</a>). И всё это практически бесплатно. Выражаю благодарность организаторам - <a href="http://maxua.posterous.com/">Максу Ищенко</a> и <a href="http://hotsyk.com/">Владимиру Гоцику</a>.<h4>Заключение</h4>Жду видео. Побольше бы таких конференций, хороших и разных!Sergey Kishchenkohttp://www.blogger.com/profile/13451038740185023562noreply@blogger.com0tag:blogger.com,1999:blog-1625043994572710700.post-59037065644188398702009-09-27T00:45:00.001+03:002009-09-27T00:54:06.710+03:00Мини-отчёт об участии в GCJ<a href="http://code.google.com/codejam">GCJ(Google Code Jam)</a> - контест по спортивному программированию, который проводит всем известная компания Google. Контест не командный, международный, проводится в онлайн.<br />В этому году участвовал в первый раз, основные результаты таковы: остановился на втором раунде, в третий не прошёл.<h2>Впечатления</h2>Сумбурные. Участие в <a href="http://tilarids.blogspot.com/2009/06/icfp-contest-2009.html">ICFPC</a> и в <a href="http://tilarids.blogspot.com/2009/03/sapka-contest.html">Sapka</a> рождает совсем другие эмоции. GCJ более напряженный, задачи значительно меньше по объему, но труднее, временные рамки куда жестче. Однако задачи GCJ отличаются и от тех, что встречаются на ACMовских олимпиадах. Большинство задач действительно имеют очень короткие и очень красивые решения, каждую из них действительно можно решить за отведенное время, если уловить какую-то важную мысль. <h2>Выводы</h2><ul><li>Неожиданно для себя обнаружил доказательство тезиса "Разные ЯП - для разных задач". Решал задачи на Python(основной язык), Haskell и С++ - действительно, иногда тот или иной язык куда лучше подходил для решения определенной задачи</li><li>Фан можно получать и от простых задачек, не обязательно рулить спутниками или писать AI для bombermanа. Зря я почти забросил теорию - теперь сыплюсь на стандартных алгоритмах и мне очень стыдно</li><li>Нужно обязательно участвовать в следующих GCJ. Он совсем не напрягает и занимает куда меньше времени, чем многодневные командные состязания</li></ul><h3>Интересная ссылкa</h3>Недавно мне подбросили ссылку на еще один контест - <a href="http://www.hugi.scene.org/compo/">Hugi Size Coding Competition Series(hugi-compo)</a>, который кардинально отличается от всех, в которых я доселе участвовал. Именно этим он и привлекателен, хоть я и не обладаю достаточной квалификацией для удачных выступлений(контест посвящен ассемблерной оптимизации). Возможно, кого-нибудь заинтересует такое нестандартное соревнование. Спасибо за внимание!Sergey Kishchenkohttp://www.blogger.com/profile/13451038740185023562noreply@blogger.com0tag:blogger.com,1999:blog-1625043994572710700.post-53717722150388489882009-07-11T01:30:00.002+03:002009-07-11T17:26:20.718+03:00Сказ о том, как Python С++ обогналЯ всегда защищаю С++, когда приверженцы других языков ругают его за невыразительный синтаксис, чрезмерную сложность или раздутость, потому что, по-моему мнению, на С++ можно писать красиво, и особенно в этом помогают различные высокоуровневые конструкции из стандартной библиотеки. <br />В одном из споров в c_plus_plus@c.j.r речь зашла о том, какой же из языков лучше - простой С или всё же С++? В качестве одного из аргументов я предложил провести эксперимент - сколько времени понадобится для решения простой задачи: из stdin считываются строки текста, и после этого в обратном порядке записываются в stdout, т.е., первая строка в stdin становится последней в stdout. Длина строк не ограничена, поэтому для решения ее на С понадобится выделять и перевыделять память, от этого код на С разбухнет, что станет наглядной демонстрацией превосходства высокоуровневых конструкций С++. Более того, я предположил, что код на С++ может быть даже производительней кода на С, написанного без дополнительного профилирования - ведь контейнеры С++ выделяют память так, чтобы reallocate происходил реже. Пример кода на С++, написан за пару минут для демонстрации:<br /><div class="highlight"><pre><span style="color: #BC7A00">#include <iostream></span><br /><span style="color: #BC7A00">#include <string></span><br /><span style="color: #BC7A00">#include <vector></span><br /><br /><span style="color: #B00040">int</span> main() {<br /> std<span style="color: #666666">::</span>vector<span style="color: #666666"><</span>std<span style="color: #666666">::</span>string<span style="color: #666666">></span> v;<br /> <span style="color: #008000; font-weight: bold">while</span>(std<span style="color: #666666">::</span>cin)<br /> {<br /> std<span style="color: #666666">::</span>string s;<br /> std<span style="color: #666666">::</span>getline(std<span style="color: #666666">::</span>cin,s);<br /> v.push_back(s);<br /> }<br /> <span style="color: #008000; font-weight: bold">for</span> (std<span style="color: #666666">::</span>vector<span style="color: #666666"><</span>std<span style="color: #666666">::</span>string<span style="color: #666666">>::</span>reverse_iterator it <span style="color: #666666">=</span> v.rbegin();it<span style="color: #666666">!=</span>v.rend();<span style="color: #666666">++</span>it)<br /> {<br /> std<span style="color: #666666">::</span>cout<span style="color: #666666"><<*</span>it<span style="color: #666666"><<</span><span style="color: #BA2121">"</span><span style="color: #BB6622; font-weight: bold">\n</span><span style="color: #BA2121">"</span>;<br /> }<br />}<br /></pre></div>Как видите, код далеко не оптимален, однако мне хотелось показать, что даже такое решение лучше, чем код на С. <br />Тут же захотелось проверить, а как другие языки справятся с этой задачей. Например,однострочник на Ruby:<br /><pre>$stdin.readlines.reverse.join.display</pre>Когда я протестировал его на небольших файлах, С++ решение оказалось быстрее решения на Ruby в десятки раз, что меня нисколько не удивило. Однако для чистоты эксперимента я решил увеличить размер файла. Я сгенерировал файл в 100 строк общим размером ~600mb(исходник на Python):<br /><pre>open("/tmp/z.txt",'w').write((''.join(map(str,xrange(1000000)))+'\n')*100</pre>Результаты тестирования на нём были просто поразительны:<br /><pre>ruby 1.8.6 (2009-06-08 patchlevel 369) [i686-linux]:<br />real 0m9.841s<br />user 0m0.849s<br />sys 0m7.206s<br /><br />gcc (GCC) 4.1.2 (Gentoo 4.1.2 p1.3):<br />real 0m51.902s<br />user 0m48.682s<br />sys 0m1.429s</pre>Я тут же решил проверить решение на Python:<br /><pre>import sys<br />sys.stdout.write('\n'.join(reversed(sys.stdin.readlines())))</pre>Результаты:<br /><pre>Python 2.6.2<br />real 0m4.855s<br />user 0m0.913s<br />sys 0m1.233s</pre>Т.е., еще быстрее, чем ruby (что уже не удивительно ;) ). Просмотрев код на С++, я добавил простейшую оптимизацию, которую изначально добавлять не хотел, чтобы код совсем не был похож на С. Я добавил хранение в векторе указателей, а не строк, что должно было убрать ненужное копирование:<br /><div class="highlight"><pre><span style="color: #BC7A00">#include <iostream></span><br /><span style="color: #BC7A00">#include <string></span><br /><span style="color: #BC7A00">#include <vector></span><br /><br /><span style="color: #B00040">int</span> main() {<br /> std<span style="color: #666666">::</span>vector<span style="color: #666666"><</span>std<span style="color: #666666">::</span>string<span style="color: #666666">*></span> v;<br /> <span style="color: #008000; font-weight: bold">while</span>(std<span style="color: #666666">::</span>cin)<br /> {<br /> std<span style="color: #666666">::</span>string <span style="color: #666666">*</span> s <span style="color: #666666">=</span> <span style="color: #008000; font-weight: bold">new</span> std<span style="color: #666666">::</span>string();<br /> std<span style="color: #666666">::</span>getline(std<span style="color: #666666">::</span>cin,<span style="color: #666666">*</span>s);<br /> v.push_back(s);<br /> }<br /> <span style="color: #008000; font-weight: bold">for</span> (std<span style="color: #666666">::</span>vector<span style="color: #666666"><</span>std<span style="color: #666666">::</span>string<span style="color: #666666">*>::</span>reverse_iterator it <span style="color: #666666">=</span> v.rbegin();it<span style="color: #666666">!=</span>v.rend();<span style="color: #666666">++</span>it)<br /> {<br /> std<span style="color: #666666">::</span>cout<span style="color: #666666"><<*</span>(<span style="color: #666666">*</span>it)<span style="color: #666666"><<</span><span style="color: #BA2121">"</span><span style="color: #BB6622; font-weight: bold">\n</span><span style="color: #BA2121">"</span>;<br /> <span style="color: #008000; font-weight: bold">delete</span> <span style="color: #666666">*</span>it;<br /> }<br />}<br /></pre></div>Но результат всё так же не вдохновляет:<br /><pre>real 0m46.444s<br />user 0m43.462s<br />sys 0m1.379s</pre>Назначив ответственным за тормоза std::string, я попытался переписать всё на QString из Qt, которые, по слухам, умеют copy-on-write и вообще быстрые. Наивный код:<br /><div class="highlight"><pre><span style="color: #BC7A00">#include <iostream></span><br /><span style="color: #BC7A00">#include <QtCore/qstring.h></span><br /><span style="color: #BC7A00">#include <QtCore/qlist.h></span><br /><span style="color: #BC7A00">#include <QtCore/qtextstream.h></span><br /><span style="color: #BC7A00">#include <vector></span><br /><br /><span style="color: #B00040">int</span> main() {<br /> QList<span style="color: #666666"><</span>QString<span style="color: #666666">></span> v;<br /> QTextStream st (stdin);<br /> QTextStream sto (stdout);<br /> <span style="color: #008000; font-weight: bold">while</span>(<span style="color: #666666">!</span>st.atEnd())<br /> {<br /> v.push_back(st.readLine());<br /> }<br /> QListIterator<span style="color: #666666"><</span>QString<span style="color: #666666">></span> it(v);<br /> it.toBack ();<br /> <span style="color: #008000; font-weight: bold">while</span> (it.hasPrevious ())<br /> sto<span style="color: #666666"><<</span>it.previous()<span style="color: #666666"><<</span><span style="color: #BA2121">"</span><span style="color: #BB6622; font-weight: bold">\n</span><span style="color: #BA2121">"</span>;<br />}<br /></pre></div>Однако это решение пожрало все 2 гигабайта моей оперативной памяти и я его остановил, попросив Qt-шников с c_plus_plus@c.j.r помочь с оптимизацией. После нескольких минут получился вот такой код, который использовал уже 1.4 гигабайта оперативки:<br /><div class="highlight"><pre><span style="color: #BC7A00">#include <iostream></span><br /><span style="color: #BC7A00">#include <QtCore/qstring.h></span><br /><span style="color: #BC7A00">#include <QtCore/qlist.h></span><br /><span style="color: #BC7A00">#include <QtCore/qtextstream.h></span><br /><br /><span style="color: #B00040">int</span> main ()<br />{<br /> QList<span style="color: #666666"><</span>QByteArray<span style="color: #666666">></span> v;<br /> QTextStream st (stdin);<br /> QTextStream sto (stdout);<br /> <span style="color: #B00040">int</span> line <span style="color: #666666">=</span> <span style="color: #666666">0</span>;<br /> <span style="color: #008000; font-weight: bold">while</span> (<span style="color: #666666">!</span>st.atEnd ())<br /> { <br /> std<span style="color: #666666">::</span>cerr <span style="color: #666666"><<</span> <span style="color: #BA2121">"Reading line... "</span> <span style="color: #666666"><<</span> line<span style="color: #666666">++</span> <span style="color: #666666"><<</span> std<span style="color: #666666">::</span>endl;<br /> v.push_back (qCompress (st.readLine ().toUtf8 (), <span style="color: #666666">9</span>));<br /> }<br /> QListIterator<span style="color: #666666"><</span>QByteArray<span style="color: #666666">></span> it (v);<br /> it.toBack ();<br /> <span style="color: #008000; font-weight: bold">while</span> (it.hasPrevious ())<br /> { <br /> std<span style="color: #666666">::</span>cerr <span style="color: #666666"><<</span> <span style="color: #BA2121">"Writing line... "</span> <span style="color: #666666"><<</span> std<span style="color: #666666">::</span>endl;<br /> sto <span style="color: #666666"><<</span> qUncompress (it.previous ()) <span style="color: #666666"><<</span> <span style="color: #BA2121">"</span><span style="color: #BB6622; font-weight: bold">\n</span><span style="color: #BA2121">"</span>;<br /> sto.flush ();<br /> }<br />}<br /></pre></div>Однако он работал еще медленнее, чем на стандартных строках - более двух минут. Для чистоты эксперимента я также написал вариант на Python, который не использовал стандартные join и reversed, а был более похож на код на С++:<br /><div class="highlight"><pre><span style="color: #008000; font-weight: bold">import</span> <span style="color: #0000FF; font-weight: bold">sys</span><br />s <span style="color: #666666">=</span> sys<span style="color: #666666">.</span>stdin<span style="color: #666666">.</span>readlines()<br /><span style="color: #008000; font-weight: bold">for</span> x <span style="color: #AA22FF; font-weight: bold">in</span> <span style="color: #008000">xrange</span>(<span style="color: #008000">len</span>(s)<span style="color: #666666">-1</span>,<span style="color: #666666">-1</span>,<span style="color: #666666">-1</span>):<br /> sys<span style="color: #666666">.</span>stdout<span style="color: #666666">.</span>write(s[x]<span style="color: #666666">+</span><span style="color: #BA2121">'</span><span style="color: #BB6622; font-weight: bold">\n</span><span style="color: #BA2121">'</span>)<br /></pre></div>Его результаты:<br /><pre>real 0m2.198s<br />user 0m0.884s<br />sys 0m1.190s</pre><h2>Выводы</h2>Если не учитывать опыты с Qt(всё равно ведь хороших результатов добиться не удалось), ни в одном из языков не было использовано каких-либо особых оптимизаций, напротив, были использованы те конструкции высокого уровня, которые предлагает сам язык. И удивительно, что программы на Python и Ruby смогли с большим отрывом обогнать аналогичную программу на С++. Я сам еще не знаю причину этого, и я был бы очень рад, если бы кто-то смог прогнать аналогичные тесты у себя на машине. Однако вне зависимости от причины, такой результат явственно говорит одно - нельзя безоговорочно верить в то, что С++ быстрее интерпретируемых языков, особенно если простейшие высокоуровневые конструкции в них, такие как строки, работают лучше.<h2>P.S.</h2>Я не старался создать идеальные условия для тестирования и не прогонял тесты сотни раз, чтобы получить идеальный результат. Достаточно всего-лишь заметить, что в этом синтетическом тесте Python был в 2-5 раз быстрее Ruby, а Ruby была в 4-5 раз быстрее С++. Спасибо за внимание!<h2>Частичная реабилитация<b>(update)</b></h2><div class="highlight"><pre><span style="color: #BC7A00">#include <iostream></span><br /><span style="color: #BC7A00">#include <fstream></span><br /><span style="color: #BC7A00">#include <string></span><br /><span style="color: #BC7A00">#include <vector></span><br /><br /><span style="color: #B00040">int</span> main() {<br /> std<span style="color: #666666">::</span>ifstream fin(<span style="color: #BA2121">"/dev/stdin"</span>);<br /> std<span style="color: #666666">::</span>vector<span style="color: #666666"><</span>std<span style="color: #666666">::</span>string<span style="color: #666666">*></span> v;<br /> <span style="color: #008000; font-weight: bold">while</span>(fin)<br /> {<br /> std<span style="color: #666666">::</span>string <span style="color: #666666">*</span> s <span style="color: #666666">=</span> <span style="color: #008000; font-weight: bold">new</span> std<span style="color: #666666">::</span>string();<br /> std<span style="color: #666666">::</span>getline(fin,<span style="color: #666666">*</span>s);<br /> v.push_back(s);<br /> }<br /> <span style="color: #008000; font-weight: bold">for</span> (std<span style="color: #666666">::</span>vector<span style="color: #666666"><</span>std<span style="color: #666666">::</span>string<span style="color: #666666">*>::</span>reverse_iterator it <span style="color: #666666">=</span> v.rbegin();it<span style="color: #666666">!=</span>v.rend();<span style="color: #666666">++</span>it)<br /> {<br /> std<span style="color: #666666">::</span>cout<span style="color: #666666"><<*</span>(<span style="color: #666666">*</span>it)<span style="color: #666666"><<</span><span style="color: #BA2121">"</span><span style="color: #BB6622; font-weight: bold">\n</span><span style="color: #BA2121">"</span>;<br /> <span style="color: #008000; font-weight: bold">delete</span> <span style="color: #666666">*</span>it;<br /> }<br />}<br /><br />real <span style="color: #666666">0</span>m1<span style="color: #666666">.783</span>s<br />user <span style="color: #666666">0</span>m0<span style="color: #666666">.656</span>s<br />sys <span style="color: #666666">0</span>m1<span style="color: #666666">.070</span>s<br /></pre></div><br />Т.е., тормозил std::cin. Естественно, это не оправдание, поэтому реабилитация только частичная. Вывод: tools don't kill software. people kill software.Sergey Kishchenkohttp://www.blogger.com/profile/13451038740185023562noreply@blogger.com37tag:blogger.com,1999:blog-1625043994572710700.post-90708841192044673682009-06-30T15:30:00.005+03:002009-06-30T19:32:04.628+03:00ICFP contest 2009Продолжая добрую традицию подробно описывать контесты, <a href="http://tilarids.blogspot.com/2009/03/sapka-contest.html">начатую</a> с Sapka contest, предлагаю вашему вниманию отчёт о <b>ICFPC 09</b><h2>Введение</h2><a href="http://icfpcontest.org/">ICFP Contest</a> - командный контест, который проводится один раз в году. Количество участников в команде не ограничено. Задание одно, на весь контест отводится 72 часа(3 суток). Контест делится на lightning round(оцениваются решения, полученные в первые 24 часа) и main round(оцениваются все отосланные решения).<h2>Команда</h2>Страницу команды <b>Concrete mixers</b> можно найти <a href="http://cm.xa4a.org.ua/">здесь</a>. Т.е., 4 человека, но после lightning A2K отошел от дел. С одним из оставшихся участников - <a href="http://undefined.org.ua/">xa4a</a> - я уже участвовал в Sapka, и мы там даже взяли призовое место на Lightning. Со вторым из оставшихся - <a href="http://murkt.org.ua/blog/">Murkt</a> - до этого работать вместе не приходилось, но мы вроде неплохо сработались.<h2>Инструменты</h2>Основной язык - Python. В качестве системы контроля версий использовали Mercurial, в качестве хостинга - <a href="http://bitbucket.org/">bitbucket</a>. Для визуализации был использован pygame(также были попытки использовать Qt, но в итоге остался вариант с pygame). Для общения использовали конференцию в jabber.<h2>Задание</h2>Оригинальное задание (последнюю версию) можно скачать <a href="http://icfpcontest.org/task-1.9.pdf">здесь</a>. Кратко - нужно было писать управляющие программы для спутника для выполнения разных задач. Поведение спутника и окружающей его вселенной эмулировалось в бинарниках, которые предоставляли организаторы. Бинарники можно было запустить на виртуальной машине, спецификации которой были также предоставлены. Список маневров, которые нужно было выполнять со спутником:<br /><ul><li>Перевод спутника с одной круговой орбиты на другую</li><li>Рандеву с другим спутником, двигающимся по круговой орбите</li><li>Аналогичное рандеву, но начальная орбита и конечная могут быть эллиптическими</li><li>Упрощенное рандеву с 11-ю спутниками на произвольных орбитах. Также здесь присутствует Луна и заправочная станция</li></ul>Таким образом, большая часть задания связана с орбитальными маневрами - сплошная математика и физика.<h2>Ночь первая (26.06-27.06)</h2>Получили задание, прочитали, пообсуждали, устранили непонимания, распределили задания. Где-то через два часа у нас наконец появился парсер бинарников, еще через час было две VM, из которых мы выбрали лучшую. Еще через два часа я сделал первый тестовый солвер с визуализатором, а к этому моменту xa4a уже залил нужные формулы для hohmann transfer, A2K доделывал логгер, который был нужен для формирования сабмишенов. <br />Т.о., через 5 часов после начала я приступил к прикручиванию формул к солверу, однако это оказалось не так просто. Murkt с чувством выполненного долга(написанная им VM работала, хоть и медленно) пошел спать, а мы с xa4a и A2K еще часа два пытались починить логгер и формулы, A2K писал визуализатор на Qt. Результат первой ночи - готова VM, визуализатор, основная инфраструктура, однако очков всё еще 0<h2>День первый (27.06)</h2>С утра Murkt и xa4a подхимичили формулы и у нас в нашем симуляторе появились первые очки. Однако при попытке сабмита тут же стало понятно, что написанный ночью логгер ошибочен и я взялся его переделывать. В 14:20 был "EPIC WIN!!!!!"(с)Murkt - первые очки, полученные после исправления логгера. Задачи 1001-1004 в этот момент времени перешли в статус решенных. И пока xa4a и Murkt продолжали изыскания с задачами 2001-2004, я в течение часа многократно ускорил VM путем генерации и последующей интерпретации кода на Python. Также скриншот, сохранившийся с этого временного участка:<br /><a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEj_6D7N020zNRSyOMsZjIqxi4_2mZy45ODHwLRldAJ4V0Y9iajWZSZgVnvRgV_YGvMznmLN6Qv7auqNpEElD3GSBK-ZbEP2RGMLvTzFaTA0gbkTwQ60X4Kyfz6vEpH8wuBwihLAzyAH9Ic/s1600-h/screen1.png"><img style="display:block; margin:0px auto 10px; text-align:center;cursor:pointer; cursor:hand;width: 320px; height: 320px;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEj_6D7N020zNRSyOMsZjIqxi4_2mZy45ODHwLRldAJ4V0Y9iajWZSZgVnvRgV_YGvMznmLN6Qv7auqNpEElD3GSBK-ZbEP2RGMLvTzFaTA0gbkTwQ60X4Kyfz6vEpH8wuBwihLAzyAH9Ic/s320/screen1.png" border="0" alt=""id="BLOGGER_PHOTO_ID_5353092115112020642" /></a>В дальнейшем мы все вместе пытались побороть задачи 2001-2004. Напомню, в этих задачах нужно было не просто перелететь на другую орбиту, как в 1001-1004, а и попасть еще и в ту же точку этой орбиты, что и другой спутник. Для того, чтобы этого добиться, мы ввели понятие hohmann delay - время ожидания, нужное, чтобы после него при hohmann transfer попасть в нужную точку. В 18:40 Murkt получил первые очки этим методом. Однако метод оказался совсем не стабильным - решение он давал, но давал и большие погрешности. Поэтому оставшееся до окончания lightning время мы работали в двух направлениях - устранение погрешности и 3001-3004. Ничего существенно добиться мы не успели и lightning закончили с результатом где-то 945 баллов. В top lightning'a мы,естественно не попали, и место в lightning на данном этапе узнать невозможно, хотя и очень интересно.<br />Ниже - визуализатор, который писал A2K, но который так и не был использован:<br /><a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhJEzNFtBrEy7tJQemFqAPSWAulNchozvybJUpGqMzre7qdAsqki2lOs36a27Pu8JLB6y5Vmomo4VXqSwsfpNLqVxoBWST9686oFgHVT5ahqvhhJy2abPhmTlA1htrxQHp9GC70rqMgzQg/s1600-h/scrj.png"><img style="display:block; margin:0px auto 10px; text-align:center;cursor:pointer; cursor:hand;width: 302px; height: 320px;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhJEzNFtBrEy7tJQemFqAPSWAulNchozvybJUpGqMzre7qdAsqki2lOs36a27Pu8JLB6y5Vmomo4VXqSwsfpNLqVxoBWST9686oFgHVT5ahqvhhJy2abPhmTlA1htrxQHp9GC70rqMgzQg/s320/scrj.png" border="0" alt=""id="BLOGGER_PHOTO_ID_5353093022916441330" /></a><h2>Ночь вторая (27.06-28.06)</h2>Появилась Луна и задачи 4001-4004. Часа через четыре усилиями Murkt и xa4a были существенно проапгрейджены решения наших 8 задач и получено 1127.44746 очков. Приблизительно этого хотелось добиться в lightning, но не успели, а жаль. Также xa4a очень красиво переделал солверы (стало чем-то похоже на twisted). С 3х до 6 утра я сделал алгоритм подгазовки через phasing - он работал идеально и позволял проходить 2001-2004 даже без hohmann delay.<h2>День второй (28.06)</h2>Murkt почистил код, а мы с xa4a пытались найти параметры эллиптических орбит и у нас никак не получалось вывести формулу, которая бы работала для всех задач 3001-3004. В поисках решения были привлечены ЧМ и придумано несколько странных методов определения. Однако это ни к чему не привело, а уравнение орбиты было выведено xa4a чуть позже, когда я отсутствовал.<h2>Ночь третья (28.06-29.06)</h2>Murkt сделал naive chase - подгазовку, которая плевала на всю астрофизику и просто заставляла суптник лететь к цели, сжигая при этом топливо(занятный пример представлен ниже).<br /><a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiT-v5ba9dTWgvG0XBT8mAd5WUdgu8r68joF-N98sBQFAVBgQHCPS_XXToAyROWbJRFx1W-prU958WQH_QrL3tGHdJ1-qZFcBeL6tSNUaCgNI0a13GRRdc64qDJXQ0Lf2xGsj09KNakXHw/s1600-h/screenshot-2009-06-29--21-14-17.png"><img style="display:block; margin:0px auto 10px; text-align:center;cursor:pointer; cursor:hand;width: 320px; height: 200px;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiT-v5ba9dTWgvG0XBT8mAd5WUdgu8r68joF-N98sBQFAVBgQHCPS_XXToAyROWbJRFx1W-prU958WQH_QrL3tGHdJ1-qZFcBeL6tSNUaCgNI0a13GRRdc64qDJXQ0Lf2xGsj09KNakXHw/s320/screenshot-2009-06-29--21-14-17.png" border="0" alt=""id="BLOGGER_PHOTO_ID_5353094148370739378" /></a> Этот naive chase отлично работал на небольших расстояниях. Совместив его с hohmann elliptic transfer, который к этому моменту я докрутил до состояния бета, у нас получилось решить все задачи из 3001-3004. Также я пытался сделать phasing для эллиптических орбит, однако из-за каких-то погрешностей точность phasingа оказалась меньше, чем нужно. Тем не менее, применение одной итерации phasing, а потом naive chase привело к увеличению очков.<h2>День третий (29.06)</h2>Весь день был проведен в попытках улучшить переходы по эллиптическим орбитам для 3001-3004, чтобы затем использовать в 4001-4004. Я попытался еще ускорить виртуальную машину посредством psyco (работало отлично, но только на 32-битных системах) и cython(работало везде, но компиляция была слишком долгой, кеширование скомпилированного нужно было делать, а профит был <u>меньше</u>, чем с psyco, т.о. в итоге от него отказались). В 13:04 был эпический "OMFG", когда мы заметили, что в Orbital Mechanics (описание ее смотрите ниже) есть матлабовский код, в котором есть готовые нужные нам формулы и алгоритмы - только копируй, исправляй и пользуйся. По этому коду xa4a переделал определение параметров орбиты, а я пытался сделать smart chase - через уравнение Ламберта. Однако, по-моему мнению, это было лишним - код нормально работать отказывался, а определение параметров орбиты вообще стало работать хуже, чем было. Smart chase также работал хуже, чем naive chase. Я попытался вывести hohmann elliptic delay - аналог hohmann delay но для произвольных эллиптических орбит, однако и этот алгоритм нам не очень пригодился. В этот момент - оставалось часа 3 до конца контеста - мы решили, что нужно хотя бы какие-нибудь Score получить на задачах 4001-4004. Murkt сделал простой солвер, который работал также, как 3001-3004(hohmann elliptic transfer+naive chase), однако ему не хватало топлива. Остальные три часа мы пытались подстроить naive chase, так чтобы он экономил топливо. Итог - пойманы три спутника в 4001(третий спутник был пойман мной за 7 минут до окончания, скриншот смотрите ниже) и два спутника в 4002. <br /><a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEi-dTGWAlni3_w5EZucBN155SEzYtRWNXCPsuv8FLpHNm983D6WdQgtuG0wMZl_YwuBu51A_AMkXSXrdiFO0b69bw6JJTwjPNbk9CJ0uPn5jmaD26TfiVUSiA6vIMXhj_AU-vwyYeANCWU/s1600-h/screen.png"><img style="display:block; margin:0px auto 10px; text-align:center;cursor:pointer; cursor:hand;width: 320px; height: 320px;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEi-dTGWAlni3_w5EZucBN155SEzYtRWNXCPsuv8FLpHNm983D6WdQgtuG0wMZl_YwuBu51A_AMkXSXrdiFO0b69bw6JJTwjPNbk9CJ0uPn5jmaD26TfiVUSiA6vIMXhj_AU-vwyYeANCWU/s320/screen.png" border="0" alt=""id="BLOGGER_PHOTO_ID_5353095308735524338" /></a>Итог контеста - Weighted Total Score 2852.2285 (14 problems solved), 21 место, если последние 4 часа контеста все участники прохлаждались :)<h2>О разном</h2><ul><li>Репозиторий с исходниками можно найти <a href="http://bitbucket.org/xa4a/icfpc09/">здесь</a></li><li>Orbital mechanics - кодовое название книги Howard Curtis "Orbital mechanics for engineering students" - для нас она стала Библией астрофизики</li><li><a href="http://murkt.org.ua/blog/2009/06/30/icfpc09-space-opera/">Отчёт от Murkt</a></li><li><a href="http://undefined.org.ua/blog/2009/06/30/icfpc09/?lang=ru">Отчёт от xa4a</a></li></ul><h2>Организаторам</h2><ul><li>Слишком много версий заданий. Последние я даже не читал - надоело</li><li>Математика - это круто, и я не жалею, что участвовал в контесте, но всё же хотелось увидеть programming contest</li></ul><h2>Выводы</h2>Как ни странно, текущий раздел не последний в этом отчёте. Тех, кто интересуется математикой, могут также прочитать и следующий раздел. Здесь же хотелось отметить, что фана от ICFPC 09 было всё же меньше, чем от Sapka (возможно потому, что Sapka была первым моим подобным контестом), однако море удовольствия от решения математических задачек я всё же получил. Будем надеяться, что в следующем году я тоже смогу поучаствовать.<h2>О математике</h2>За время контеста я получил(вывел сам, подсмотрел в Orbital Mechanics) множество формул. Здесь небольшой список, что было проделано(список не включает достижения остальных участников соревнования):<table><tr><th>Кодовое имя</th><th>Описание</th></tr><br /><tr><td>hohmann delay</td><td>Позволял найти время, которое нужно подождать на текущей орбите, чтобы при hohmann transfer на целевую орбиту попасть в нужную точку. Я выводил из равенства конечных углов, где конечные углы - функции времени. Этот hohmann delay не был использован в решении</td></tr><br /><tr><td>phasing</td><td>Был подсмотрен в Orbital Mechanics и немного подправлен, чтобы была возможность совершать подстройку из любой точки орбиты, а не только из перигея. Вывод можно посмотреть в Orbital Mechanics</td></tr><br /><tr><td>orbital equation v.1</td><td>Позволял находить уравнение орбиты по двум точкам. Был выведен из системы двух уравнений орбиты в разных точках. Работал идеально на орбитах, apse line которых совпадала с осью абсцисс</td></tr><br /><tr><td>orbital equation v.2</td><td>К v.1 был добавлен еще один параметр - угол поворота орбиты. Параметры должны были находиться теперь уже по трём точкам. Решение искалось численно, потому что косинусы. Довести до ума так и не получилось, возможно, в моих предположениях была какая-то ошибка</td></tr><br /><tr><td>orbital equation v.3</td><td>Было использовано уравнение орбиты в векторах. Также должно было определять по трём точкам и находить угловой момент и вектор эксцентриситета. Не был доведен до ума, потому что см. ниже</td></tr><br /><tr><td>orbital equation v.4</td><td>Был подсмотрен в википедии в статье про кеплеровские орбиты. Вероятно, я где-то ошибся, но и эта формула выдавала неправильные результаты, хотя по этой же статье xa4a смог сделать рабочую версию</td></tr><br /><tr><td>hohmann elliptic transfer</td><td>Почти то же самое, что и hohmann transfer, только без упрощений, возможных для круговых орбит. Вывод можно посмотреть в Orbital Mechanics. Было использовано для 3001-3004</td></tr><br /><tr><td>elliptic phasing</td><td>То же самое, что и phasing, но для эллиптических орбит. Работало хуже, чем phasing, но работало для некоторых задач из 3001-3004. Вывод можно посмотреть в Orbital Mechanics</td></tr><br /><tr><td>Smart chase</td><td>Chasing maneuver по Orbital Mechanics. Работал не очень, использован не был</td></tr><br /></table>Sergey Kishchenkohttp://www.blogger.com/profile/13451038740185023562noreply@blogger.com0tag:blogger.com,1999:blog-1625043994572710700.post-62791740976020499542009-06-24T19:00:00.001+03:002009-06-24T19:01:43.969+03:00Django CouchDB backend 0.1Не так давно стараниями <a href="http://42coffeecups.com/">42cc</a> была выпущена версия 0.1 бэкенда к CouchDB для Django ORM. Доступ к нему можно получить<a href="http://github.com/42/42-django-couchdb/tree/master">на github</a>, также есть <a href="http://trac.khavr.com/project/django-couchdb">трак</a>. Так как я принимал в этом проекте весьма деятельное участие, то мне бы хотелось рассказать про него поподробнее.<br />Я не буду останавливаться на том, нужна или не нужна CouchDB. Вы можете прочитать об этом <a href="http://books.couchdb.org/relax/why-couchdb">здесь</a> или в google. Мне бы хотелось отметить один из недостатков CouchDB - он непривычен для людей, привыкших к реляционным базам данных, а следовательно, может показаться неудобным. Это и стало одной из причин разработки django-couchdb.<br />Основная цель разработки - позволить описывать взаимодействие приложений на Django с CouchDB на знакомом "языке" - на языке Django ORM. Для поверхностного использования не понадобится даже знания о том, что такое CouchDB - достаточно прописать backend в DATABASE_ENGINE и использовать его. Простейшие примеры того, что умеет django-couchdb(в виде теста):<pre><code class="prettyprint">class Boo(models.Model):<br /> title = models.CharField(max_length=20)<br /> slug = models.SlugField()<br /> class Meta:<br /> unique_together = ('title', 'slug')<br /><br />class Foo(models.Model):<br /> boo = models.ForeignKey(Boo)<br /> boo2 = models.ForeignKey(Boo, related_name="foo2_set")<br /><br />b1 = Boo(title="1", slug="1")<br />b1.save()<br />b11 = Boo(title="11", slug="1")<br />b11.save()<br />b2 = Boo(title="2", slug="2")<br />b2.save()<br />f1 = Foo(boo=b1)<br />f1.save()<br />f2 = Foo(boo=b2)<br />f2.save()<br />f3 = Foo(boo=b1,boo2=b2)<br />f3.save()<br />assert_equal(Foo.objects.filter(boo__title="1").count(), 2)<br />assert_equal(Foo.objects.filter(boo__title="11").count(), 0)<br />assert_equal(Foo.objects.filter(Q(boo__title="1") | Q(boo__slug="2")).count(), 3)<br /><br />assert_equal(Foo.objects.filter(Q(boo__title="1") & Q(boo2__title="2")).count(), 1)<br />assert_equal(Foo.objects.filter(Q(boo__title="1") & Q(boo2__title="11")).count(), 0)<br /></code></pre><br />А именно: работает генерация "схемы" из моделей, insert, update, delete, select, joins(не все). Не работает - ManyToManyField, aggregates. Поэтому django.contrib(например, admin) работает, но не полностью.<h3>Перспективы развития</h3>Дальнейшее развитие будет вестись в нескольких направлениях:<ol><li>Исправление недостатков, поддержка других возможностей ORM</li><li>Развитие backend для использования сильных сторон CouchDB</li><li>Увеличение производительности</li></ol><h3>Выводы</h3>Получился очень удобный инструмент, скрывающий особенности реализации (JS, HTTP запросы). Спасибо за внимание, ожидайте новые версии и новые возможности :)Sergey Kishchenkohttp://www.blogger.com/profile/13451038740185023562noreply@blogger.com7tag:blogger.com,1999:blog-1625043994572710700.post-51324837490928661912009-06-12T01:30:00.000+03:002009-06-12T01:42:25.873+03:00Bachelor Thesis in Computer Science. Part 1Finally, my bachelor thesis has come to an end! And now I am going to publish the most interesting stuff I've done. Let me introduce you CamTrack, a simple OpenCV based tool that can be used to control your desktop using webcam. There is nothing breaking new in there (it is only a bachelor thesis and in Ukraine it is not something difficult). But I think, it can be a strong open source competitor to the <a href="http://www.camspace.com/">CamSpace</a> software.<br /><br /><object width="425" height="344"><param name="movie" value="http://www.youtube.com/v/bhxp_4KCf0c&hl=en&fs=1&"></param><param name="allowFullScreen" value="true"></param><param name="allowscriptaccess" value="always"></param><embed src="http://www.youtube.com/v/bhxp_4KCf0c&hl=en&fs=1&" type="application/x-shockwave-flash" allowscriptaccess="always" allowfullscreen="true" width="425" height="344"></embed></object><br /><br /><object width="425" height="344"><param name="movie" value="http://www.youtube.com/v/gLVrx-Ggjy4&hl=en&fs=1&"></param><param name="allowFullScreen" value="true"></param><param name="allowscriptaccess" value="always"></param><embed src="http://www.youtube.com/v/gLVrx-Ggjy4&hl=en&fs=1&" type="application/x-shockwave-flash" allowscriptaccess="always" allowfullscreen="true" width="425" height="344"></embed></object><br /><br />You can find the source code on <a href="http://bitbucket.org/tilarids/camtrack/">bitbucket</a>. Or use <a href="http://bitbucket.org/tilarids/camtrack/get/tip.zip">direct link</a> to download latest version. Don't hesitate to ask if you have any problems with installation. <br /><br />If you're interested in this software or if you want to take part in it - please contact me.<br /><br />Announcement for russian readers: I am also going to publish my thesis papers and give some suggestions about writing thesis using LaTeX. Stay tuned.Sergey Kishchenkohttp://www.blogger.com/profile/13451038740185023562noreply@blogger.com4tag:blogger.com,1999:blog-1625043994572710700.post-29747441944080814072009-05-13T23:30:00.000+03:002009-05-13T23:31:48.196+03:00О замыканиях в Python и С++<a href="http://tilarids.blogspot.com/2009/05/c-0x.html">Предыдущий пост</a> вызвал множество споров в pythonua@c.j.r на тему сложности синтаксиса С++ и сложности синтаксиса лямбд в частности. Действительно, в С++ 0x лямбды - это не one-line expressions, а полноценные анонимные функции. Именно поэтому синтаксис и так сложен.<br />Например, возьмём Python и его лямбды. Так как синтаксис Python изначально минималистичен, то и лямбды в нём выглядят аккуратно и понятно. Однако, с другой стороны такая минималистичность может сыграть и злую шутку. Вот пример - не так давно <a href="http://curvedbrain.org/2009/05/07/o-zamykaniyah-v-python/">поднимался</a> вопрос о замыканиях в Python. Речь в этой статье шла о таком небольшом сниппете:<br /><pre style='color:#000000;background:#ffffff;'>l <span style='color:#808030; '>=</span> <span style='color:#808030; '>[</span><span style='color:#808030; '>]</span><br /><span style='color:#800000; font-weight:bold; '>for</span> i <span style='color:#800000; font-weight:bold; '>in</span> <span style='color:#e34adc; '>range</span><span style='color:#808030; '>(</span><span style='color:#008c00; '>2</span><span style='color:#808030; '>)</span><span style='color:#808030; '>:</span><br /> <span style='color:#800000; font-weight:bold; '>for</span> j <span style='color:#800000; font-weight:bold; '>in</span> <span style='color:#e34adc; '>range</span><span style='color:#808030; '>(</span><span style='color:#008c00; '>2</span><span style='color:#808030; '>)</span><span style='color:#808030; '>:</span><br /> l<span style='color:#808030; '>.</span>append<span style='color:#808030; '>(</span><span style='color:#e34adc; '>lambda</span><span style='color:#808030; '>:</span> i <span style='color:#808030; '>+</span> j<span style='color:#808030; '>)</span><br /></pre>При такой реализации замыкания не происходит - в l мы получим абсолютно одинаковые функции. Основной вывод вышеприведенной статьи - правильная реализация замыканий в Python - это:<br /><pre style='color:#000000;background:#ffffff;'><span style='color:#800000; font-weight:bold; '>def</span> lsum<span style='color:#808030; '>(</span>n<span style='color:#808030; '>,</span> m<span style='color:#808030; '>)</span><span style='color:#808030; '>:</span><br /> <span style='color:#800000; font-weight:bold; '>return</span> <span style='color:#e34adc; '>lambda</span><span style='color:#808030; '>:</span> n <span style='color:#808030; '>+</span> m<br /><br />l <span style='color:#808030; '>=</span> <span style='color:#808030; '>[</span><span style='color:#808030; '>]</span><br /><span style='color:#800000; font-weight:bold; '>for</span> i <span style='color:#800000; font-weight:bold; '>in</span> <span style='color:#e34adc; '>range</span><span style='color:#808030; '>(</span><span style='color:#008c00; '>2</span><span style='color:#808030; '>)</span><span style='color:#808030; '>:</span><br /> <span style='color:#800000; font-weight:bold; '>for</span> j <span style='color:#800000; font-weight:bold; '>in</span> <span style='color:#e34adc; '>range</span><span style='color:#808030; '>(</span><span style='color:#008c00; '>2</span><span style='color:#808030; '>)</span><span style='color:#808030; '>:</span><br /> l<span style='color:#808030; '>.</span>append<span style='color:#808030; '>(</span>lsum<span style='color:#808030; '>(</span>i<span style='color:#808030; '>,</span> j<span style='color:#808030; '>)</span><span style='color:#808030; '>)</span><br /></pre>Но что мы видим в этом коде? Вместо удобного inline использования - отдельная функция, которая отвлекает внимание и всё портит.<br />Теперь вернёмся к С++ и посмотрим как в игру вступает один из синтаксических наворотов - capture list: <br /><pre style='color:#000000;background:#ffffff;'><span style='color:#004a43; '>#</span><span style='color:#004a43; '>include </span><span style='color:#800000; '><</span><span style='color:#40015a; '>iostream</span><span style='color:#800000; '>></span><br /><span style='color:#004a43; '>#</span><span style='color:#004a43; '>include </span><span style='color:#800000; '><</span><span style='color:#40015a; '>vector</span><span style='color:#800000; '>></span><br /><span style='color:#004a43; '>#</span><span style='color:#004a43; '>include </span><span style='color:#800000; '><</span><span style='color:#40015a; '>algorithm</span><span style='color:#800000; '>></span><br /><span style='color:#004a43; '>#</span><span style='color:#004a43; '>include </span><span style='color:#800000; '><</span><span style='color:#40015a; '>boost/function.hpp</span><span style='color:#800000; '>></span><br /><br /><span style='color:#800000; font-weight:bold; '>int</span> <span style='color:#400000; '>main</span><span style='color:#808030; '>(</span><span style='color:#808030; '>)</span><br /><span style='color:#800080; '>{</span><br /> <span style='color:#666616; '>std</span><span style='color:#800080; '>::</span><span style='color:#603000; '>vector</span><span style='color:#808030; '><</span>boost<span style='color:#800080; '>::</span>function <span style='color:#808030; '><</span><span style='color:#800000; font-weight:bold; '>int</span><span style='color:#808030; '>(</span><span style='color:#808030; '>)</span><span style='color:#808030; '>></span><span style='color:#808030; '>></span> l<span style='color:#800080; '>;</span><br /> <span style='color:#800000; font-weight:bold; '>for</span> <span style='color:#808030; '>(</span><span style='color:#800000; font-weight:bold; '>int</span> i<span style='color:#808030; '>=</span><span style='color:#008c00; '>0</span><span style='color:#800080; '>;</span>i<span style='color:#808030; '><</span><span style='color:#008c00; '>2</span><span style='color:#800080; '>;</span><span style='color:#808030; '>+</span><span style='color:#808030; '>+</span>i<span style='color:#808030; '>)</span><br /> <span style='color:#800000; font-weight:bold; '>for</span> <span style='color:#808030; '>(</span><span style='color:#800000; font-weight:bold; '>int</span> j<span style='color:#808030; '>=</span><span style='color:#008c00; '>0</span><span style='color:#800080; '>;</span>j<span style='color:#808030; '><</span><span style='color:#008c00; '>2</span><span style='color:#800080; '>;</span><span style='color:#808030; '>+</span><span style='color:#808030; '>+</span>j<span style='color:#808030; '>)</span><br /> l<span style='color:#808030; '>.</span>push_back<span style='color:#808030; '>(</span><span style='color:#808030; '>[</span>i<span style='color:#808030; '>,</span>j<span style='color:#808030; '>]</span><span style='color:#ffffff; background:#dd0000; font-weight:bold; font-style:italic; '>{</span> <span style='color:#800000; font-weight:bold; '>return</span> i <span style='color:#808030; '>+</span> j<span style='color:#800080; '>;</span> <span style='color:#ffffff; background:#dd0000; font-weight:bold; font-style:italic; '>}</span><span style='color:#808030; '>)</span><span style='color:#800080; '>;</span><br /> <span style='color:#603000; '>for_each</span><span style='color:#808030; '>(</span>l<span style='color:#808030; '>.</span>begin<span style='color:#808030; '>(</span><span style='color:#808030; '>)</span><span style='color:#808030; '>,</span><br /> l<span style='color:#808030; '>.</span>end<span style='color:#808030; '>(</span><span style='color:#808030; '>)</span><span style='color:#808030; '>,</span><br /> <span style='color:#808030; '>[</span><span style='color:#808030; '>]</span><span style='color:#808030; '>(</span>boost<span style='color:#800080; '>::</span>function <span style='color:#800080; '><</span><span style='color:#800000; font-weight:bold; '>int</span><span style='color:#808030; '>(</span><span style='color:#808030; '>)</span><span style='color:#800080; '>></span> f<span style='color:#808030; '>)</span><span style='color:#ffffff; background:#dd0000; font-weight:bold; font-style:italic; '>{</span> <span style='color:#666616; '>std</span><span style='color:#800080; '>::</span><span style='color:#603000; '>cout</span> <span style='color:#808030; '><</span><span style='color:#808030; '><</span> f<span style='color:#808030; '>(</span><span style='color:#808030; '>)</span> <span style='color:#808030; '><</span><span style='color:#808030; '><</span> <span style='color:#800000; '>"</span><span style='color:#0f69ff; '>\n</span><span style='color:#800000; '>"</span><span style='color:#800080; '>;</span> <span style='color:#ffffff; background:#dd0000; font-weight:bold; font-style:italic; '>}</span><span style='color:#808030; '>)</span><span style='color:#800080; '>;</span><br /><span style='color:#800080; '>}</span><br /></pre>Данная программа выводит:<br /><pre>0<br />1<br />1<br />2</pre>Как и ожидалось. Таким образом, "синтаксический мусор" в С++ 0x - это по большей части нужные и полезные вещи. Спасибо за внимание!Sergey Kishchenkohttp://www.blogger.com/profile/13451038740185023562noreply@blogger.com7tag:blogger.com,1999:blog-1625043994572710700.post-13946411944746178022009-05-13T01:15:00.001+03:002009-05-13T01:23:14.185+03:00C++ 0x уже сегодня?<h2>Вступление</h2>С++ 0x - кодовое имя грядущего стандарта С++, который несет в себе огромное количество изменений. Если и до этого язык С++ был одним из самых нагруженных и сложных, то с приходом нового стандарта он может вообще быть погребен под собственной массой. Но случится ли это? Ответу на этот вопрос и посвящен данный пост.<h2>Основная часть</h2>На <a href="http://www.boostcon.com/home">BoostCon</a> было точно подмечено, что "С++ 0x" нужно читать как "C++ 0A","C++0B", etc, однако многое можно попробовать уже сейчас.<br />Для этого я собрал gcc из cxx0x-lambdas-branch, который, по-моему, сейчас максимально близок к C++0x (бранч периодически мержится с основной веткой, но в этом бранче полностью отстутствуют Concepts). О том, как собирать - смотрите ссылки ниже.<br />Итак, имеем:<br /><pre>$ bin/gcc --version<br />gcc (GCC) 4.5.0 20090421 (experimental)<br />Copyright (C) 2009 Free Software Foundation, Inc.<br />This is free software; see the source for copying conditions. There is NO<br />warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.</pre>Попробуем что-нибудь написать:<br /><pre style='color:#000000;background:#ffffff;'><span style='color:#004a43; '>#</span><span style='color:#004a43; '>include </span><span style='color:#800000; '><</span><span style='color:#40015a; '>iostream</span><span style='color:#800000; '>></span><br /><span style='color:#004a43; '>#</span><span style='color:#004a43; '>include </span><span style='color:#800000; '><</span><span style='color:#40015a; '>vector</span><span style='color:#800000; '>></span><br /><span style='color:#004a43; '>#</span><span style='color:#004a43; '>include </span><span style='color:#800000; '><</span><span style='color:#40015a; '>algorithm</span><span style='color:#800000; '>></span><br /><br /><br /><span style='color:#800000; font-weight:bold; '>int</span> <span style='color:#400000; '>main</span><span style='color:#808030; '>(</span><span style='color:#808030; '>)</span><br /><span style='color:#800080; '>{</span><br /> <span style='color:#666616; '>std</span><span style='color:#800080; '>::</span><span style='color:#603000; '>vector</span><span style='color:#800080; '><</span><span style='color:#800000; font-weight:bold; '>int</span><span style='color:#800080; '>></span> v <span style='color:#808030; '>=</span> <span style='color:#800080; '>{</span><span style='color:#008c00; '>1</span><span style='color:#808030; '>,</span><span style='color:#008c00; '>2</span><span style='color:#808030; '>,</span><span style='color:#008c00; '>3</span><span style='color:#808030; '>,</span><span style='color:#008c00; '>4</span><span style='color:#808030; '>,</span><span style='color:#008c00; '>5</span><span style='color:#800080; '>}</span><span style='color:#800080; '>;</span><br /> <span style='color:#666616; '>std</span><span style='color:#800080; '>::</span><span style='color:#603000; '>vector</span><span style='color:#808030; '><</span><span style='color:#666616; '>std</span><span style='color:#800080; '>::</span><span style='color:#603000; '>pair</span><span style='color:#808030; '><</span><span style='color:#800000; font-weight:bold; '>int</span><span style='color:#808030; '>,</span><span style='color:#800000; font-weight:bold; '>int</span><span style='color:#808030; '>></span><span style='color:#808030; '>></span> v2<span style='color:#800080; '>;</span><br /> <span style='color:#666616; '>std</span><span style='color:#800080; '>::</span><span style='color:#603000; '>transform</span><span style='color:#808030; '>(</span>v<span style='color:#808030; '>.</span>begin<span style='color:#808030; '>(</span><span style='color:#808030; '>)</span><span style='color:#808030; '>,</span><br /> v<span style='color:#808030; '>.</span>end<span style='color:#808030; '>(</span><span style='color:#808030; '>)</span><span style='color:#808030; '>,</span><br /> <span style='color:#666616; '>std</span><span style='color:#800080; '>::</span>back_inserter<span style='color:#808030; '>(</span>v2<span style='color:#808030; '>)</span><span style='color:#808030; '>,</span><br /> <span style='color:#808030; '>[</span><span style='color:#808030; '>]</span><span style='color:#808030; '>(</span><span style='color:#800000; font-weight:bold; '>int</span> x<span style='color:#808030; '>)</span><span style='color:#ffffff; background:#dd0000; font-weight:bold; font-style:italic; '>{</span><span style='color:#800000; font-weight:bold; '>return</span> <span style='color:#666616; '>std</span><span style='color:#800080; '>::</span><span style='color:#603000; '>pair</span><span style='color:#800080; '><</span><span style='color:#800000; font-weight:bold; '>int</span><span style='color:#808030; '>,</span><span style='color:#800000; font-weight:bold; '>int</span><span style='color:#800080; '>></span><span style='color:#808030; '>(</span>x<span style='color:#808030; '>,</span> x<span style='color:#808030; '>*</span>x<span style='color:#808030; '>)</span><span style='color:#800080; '>;</span><span style='color:#ffffff; background:#dd0000; font-weight:bold; font-style:italic; '>}</span><span style='color:#808030; '>)</span><span style='color:#800080; '>;</span><br /> <span style='color:#603000; '>for_each</span><span style='color:#808030; '>(</span>v2<span style='color:#808030; '>.</span>begin<span style='color:#808030; '>(</span><span style='color:#808030; '>)</span><span style='color:#808030; '>,</span>v2<span style='color:#808030; '>.</span>end<span style='color:#808030; '>(</span><span style='color:#808030; '>)</span><span style='color:#808030; '>,</span><span style='color:#808030; '>[</span><span style='color:#808030; '>]</span><span style='color:#808030; '>(</span><span style='color:#666616; '>std</span><span style='color:#800080; '>::</span><span style='color:#603000; '>pair</span><span style='color:#800080; '><</span><span style='color:#800000; font-weight:bold; '>int</span><span style='color:#808030; '>,</span><span style='color:#800000; font-weight:bold; '>int</span><span style='color:#800080; '>></span> x<span style='color:#808030; '>)</span><span style='color:#ffffff; background:#dd0000; font-weight:bold; font-style:italic; '>{</span><span style='color:#666616; '>std</span><span style='color:#800080; '>::</span><span style='color:#603000; '>cout</span><span style='color:#808030; '><</span><span style='color:#808030; '><</span><span style='color:#800000; '>"</span><span style='color:#0000e6; '>(</span><span style='color:#800000; '>"</span><span style='color:#808030; '><</span><span style='color:#808030; '><</span>x<span style='color:#808030; '>.</span>first<span style='color:#808030; '><</span><span style='color:#808030; '><</span><span style='color:#800000; '>"</span><span style='color:#0000e6; '>,</span><span style='color:#800000; '>"</span><span style='color:#808030; '><</span><span style='color:#808030; '><</span>x<span style='color:#808030; '>.</span>second<span style='color:#808030; '><</span><span style='color:#808030; '><</span><span style='color:#800000; '>"</span><span style='color:#0000e6; '>)</span><span style='color:#800000; '>"</span><span style='color:#800080; '>;</span><span style='color:#ffffff; background:#dd0000; font-weight:bold; font-style:italic; '>}</span><span style='color:#808030; '>)</span><span style='color:#800080; '>;</span><br /> <span style='color:#800000; font-weight:bold; '>int</span> s <span style='color:#808030; '>=</span> <span style='color:#008c00; '>0</span><span style='color:#800080; '>;</span><br /> <span style='color:#603000; '>for_each</span><span style='color:#808030; '>(</span>v<span style='color:#808030; '>.</span>begin<span style='color:#808030; '>(</span><span style='color:#808030; '>)</span><span style='color:#808030; '>,</span>v<span style='color:#808030; '>.</span>end<span style='color:#808030; '>(</span><span style='color:#808030; '>)</span><span style='color:#808030; '>,</span><span style='color:#808030; '>[</span><span style='color:#808030; '>&</span>s<span style='color:#808030; '>]</span><span style='color:#808030; '>(</span><span style='color:#800000; font-weight:bold; '>int</span> x<span style='color:#808030; '>)</span><span style='color:#ffffff; background:#dd0000; font-weight:bold; font-style:italic; '>{</span>s<span style='color:#808030; '>+</span><span style='color:#808030; '>=</span>x<span style='color:#800080; '>;</span><span style='color:#ffffff; background:#dd0000; font-weight:bold; font-style:italic; '>}</span><span style='color:#808030; '>)</span><span style='color:#800080; '>;</span><br /> <span style='color:#666616; '>std</span><span style='color:#800080; '>::</span><span style='color:#603000; '>cout</span><span style='color:#808030; '><</span><span style='color:#808030; '><</span><span style='color:#800000; '>"</span><span style='color:#0f69ff; '>\n</span><span style='color:#0000e6; '>Result:</span><span style='color:#800000; '>"</span><span style='color:#808030; '><</span><span style='color:#808030; '><</span>s<span style='color:#808030; '><</span><span style='color:#808030; '><</span><span style='color:#800000; '>"</span><span style='color:#0f69ff; '>\n</span><span style='color:#800000; '>"</span><span style='color:#800080; '>;</span><br /><span style='color:#696969; '>// static_assert(false, "Dummy assertion!");</span><br /> <span style='color:#800000; font-weight:bold; '>auto</span> is_42 <span style='color:#808030; '>=</span> <span style='color:#808030; '>[</span><span style='color:#808030; '>]</span><span style='color:#808030; '>(</span><span style='color:#800000; font-weight:bold; '>int</span> x<span style='color:#808030; '>)</span> <span style='color:#800080; '>{</span><span style='color:#800000; font-weight:bold; '>return</span> x <span style='color:#808030; '>=</span><span style='color:#808030; '>=</span> <span style='color:#008c00; '>42</span><span style='color:#800080; '>;</span><span style='color:#800080; '>}</span><span style='color:#800080; '>;</span><br /> <span style='color:#800000; font-weight:bold; '>auto</span> answer <span style='color:#808030; '>=</span> <span style='color:#008c00; '>42</span><span style='color:#800080; '>;</span><br /> <span style='color:#800000; font-weight:bold; '>if</span> <span style='color:#808030; '>(</span>is_42<span style='color:#808030; '>(</span>answer<span style='color:#808030; '>)</span><span style='color:#808030; '>)</span><br /> <span style='color:#800080; '>{</span><br /> <span style='color:#666616; '>std</span><span style='color:#800080; '>::</span><span style='color:#603000; '>cout</span><span style='color:#808030; '><</span><span style='color:#808030; '><</span><span style='color:#800000; '>"</span><span style='color:#0000e6; '>Yes, it is!</span><span style='color:#0f69ff; '>\n</span><span style='color:#800000; '>"</span><span style='color:#800080; '>;</span><br /> <span style='color:#800080; '>}</span><br /> decltype<span style='color:#808030; '>(</span>answer <span style='color:#808030; '>+</span> <span style='color:#008c00; '>42</span><span style='color:#808030; '>)</span> new_answer <span style='color:#808030; '>=</span> <span style='color:#008c00; '>43</span><span style='color:#800080; '>;</span><span style='color:#696969; '>//?</span><br /> <span style='color:#666616; '>std</span><span style='color:#800080; '>::</span><span style='color:#603000; '>cout</span><span style='color:#808030; '><</span><span style='color:#808030; '><</span><span style='color:#800000; '>"</span><span style='color:#0000e6; '>New Answer:</span><span style='color:#800000; '>"</span><span style='color:#808030; '><</span><span style='color:#808030; '><</span>new_answer<span style='color:#808030; '><</span><span style='color:#808030; '><</span><span style='color:#800000; '>"</span><span style='color:#0f69ff; '>\n</span><span style='color:#800000; '>"</span><span style='color:#800080; '>;</span><br /><span style='color:#800080; '>}</span></pre>Впечатляет? Присмотритесь внимательней, в этом примере: initializer lists(список инициализации для v), right angle brackets (две правые угловые скобки в определении v2), lambda(с захватом переменных и без), static_assert (закомментирован), auto (для простых случаев и для лямбда-выражений), decltype(для определения типов). Меня очень впечатлило. Несмотря на то, что в язык добавлены новые элементы, язык стал только выразительней, а никак не сложнее. <br />Таким образом, С++ вбирает в себя всё новые и новые идеи. Несложно заметить, что С++ 0x - огромный шаг поближе к Haskell. Кто считает, что это чепуха - присмотритесь к Variadic Templates:<br /><pre style='color:#000000;background:#ffffff;'><span style='color:#800000; font-weight:bold; '>template</span><span style='color:#800080; '><</span><span style='color:#800000; font-weight:bold; '>unsigned</span><span style='color:#808030; '>.</span><span style='color:#808030; '>.</span><span style='color:#808030; '>.</span> Args<span style='color:#800080; '>></span> <span style='color:#800000; font-weight:bold; '>struct</span> mysum<span style='color:#800080; '>;</span><br /><span style='color:#800000; font-weight:bold; '>template</span><span style='color:#800080; '><</span><span style='color:#800080; '>></span><br /><span style='color:#800000; font-weight:bold; '>struct</span> mysum<span style='color:#800080; '><</span><span style='color:#800080; '>></span> <span style='color:#800080; '>{</span><br /> <span style='color:#800000; font-weight:bold; '>static</span> <span style='color:#800000; font-weight:bold; '>const</span> <span style='color:#800000; font-weight:bold; '>int</span> value <span style='color:#808030; '>=</span> <span style='color:#008c00; '>0</span><span style='color:#800080; '>;</span><br /><span style='color:#800080; '>}</span><span style='color:#800080; '>;</span><br /><br /><span style='color:#800000; font-weight:bold; '>template</span><span style='color:#800080; '><</span><span style='color:#800000; font-weight:bold; '>unsigned</span> x<span style='color:#808030; '>,</span> <span style='color:#800000; font-weight:bold; '>unsigned</span><span style='color:#808030; '>.</span><span style='color:#808030; '>.</span><span style='color:#808030; '>.</span> Args<span style='color:#800080; '>></span><br /><span style='color:#800000; font-weight:bold; '>struct</span> mysum<span style='color:#808030; '><</span>x<span style='color:#808030; '>,</span> Args<span style='color:#808030; '>.</span><span style='color:#808030; '>.</span><span style='color:#808030; '>.</span><span style='color:#808030; '>></span> <span style='color:#800080; '>{</span><br /> <span style='color:#800000; font-weight:bold; '>static</span> <span style='color:#800000; font-weight:bold; '>const</span> <span style='color:#800000; font-weight:bold; '>int</span> value <span style='color:#808030; '>=</span> x <span style='color:#808030; '>+</span> mysum<span style='color:#808030; '><</span>Args<span style='color:#808030; '>.</span><span style='color:#808030; '>.</span><span style='color:#808030; '>.</span><span style='color:#808030; '>></span><span style='color:#800080; '>::</span>value<span style='color:#800080; '>;</span><br /><span style='color:#800080; '>}</span><span style='color:#800080; '>;</span><br /><br /><span style='color:#800000; font-weight:bold; '>int</span> <span style='color:#400000; '>main</span><span style='color:#808030; '>(</span><span style='color:#808030; '>)</span><br /><span style='color:#800080; '>{</span><br /> static_assert<span style='color:#808030; '>(</span>mysum<span style='color:#800080; '><</span><span style='color:#008c00; '>10</span><span style='color:#808030; '>,</span><span style='color:#008c00; '>20</span><span style='color:#808030; '>,</span><span style='color:#008c00; '>11</span><span style='color:#808030; '>,</span><span style='color:#008c00; '>1</span><span style='color:#800080; '>></span><span style='color:#800080; '>::</span>value<span style='color:#808030; '>=</span><span style='color:#808030; '>=</span><span style='color:#008c00; '>42</span><span style='color:#808030; '>,</span> <span style='color:#800000; '>"</span><span style='color:#0000e6; '>Wow!</span><span style='color:#800000; '>"</span><span style='color:#808030; '>)</span><span style='color:#800080; '>;</span><br /><span style='color:#800080; '>}</span></pre>Variadic Templates уже доступны, однако работают не полностью.<h2>Выводы</h2>С++ 0x - попытка скачкообразно осовременить С++. И, как мне кажется, эта попытка вполне может оказаться удачной.<h2>Ссылки</h2><ul><li><a href="http://parasol.tamu.edu/groups/pttlgroup/lambda/">Про установку cxx0x-lambdas-branch</a></li><li><a href="http://www.boostcon.com/site-media/var/sphene/sphwiki/attachment/2009/05/02/C0xoverview.pdf">Обзор C++0x c BoostCon</a></li><li><a href="http://gcc.gnu.org/projects/cxx0x.html">Степень готовности GCC</a></li><li><a href="http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2009/n2857.pdf">Working Draft</a></li><li>Для пользователей Visual Studio: <a href="http://www.boostcon.com/site-media/var/sphene/sphwiki/attachment/2009/05/01/vc10.pdf">Доклад с BoostCon</a>, а также посты с VCBlog: <a href="http://blogs.msdn.com/vcblog/archive/2008/10/28/lambdas-auto-and-static-assert-c-0x-features-in-vc10-part-1.aspx">Часть 1</a>,<a href="http://blogs.msdn.com/vcblog/archive/2009/02/03/rvalue-references-c-0x-features-in-vc10-part-2.aspx">Часть 2</a>,<a href="http://blogs.msdn.com/vcblog/archive/2009/04/22/decltype-c-0x-features-in-vc10-part-3.aspx">Часть 3</a></li><li><a href="http://www.osl.iu.edu/~dgregor/cpp/variadic-templates.pdf">Про Variadic Templates</a></li></ul>Спасибо за внимание!Sergey Kishchenkohttp://www.blogger.com/profile/13451038740185023562noreply@blogger.com9tag:blogger.com,1999:blog-1625043994572710700.post-2593969244515071472009-04-01T03:30:00.001+03:002009-04-01T03:38:25.806+03:00Links: tddspry, ItQuest.ru<h2>Link 1. tddspry</h2>Что такое <a href="http://github.com/playpauseandstop/tddspry/tree/master">tddspry</a>? Это небольшой набор утилит для тестирования django-приложений с помощью nosetests. Если по какой-то причине Вы не можете воспользоваться Django Test-execution Framework или джанговские тесты просто Вас раздражают, то обязательно обратите внимание на этот небольшой проект. На данный момент в состав tddspry включены хэлперы для написания тестов, а также моки для БД и twill. В дальнейшем возможно включение поддержки Windmill, etc. Проект открыт для предложений. :)<br />Пример использования:<br /><pre style='color:#000000;background:#ffffff;'><span style='color:#800000; font-weight:bold; '>class</span> TestUI<span style='color:#808030; '>(</span>TwillMock<span style='color:#808030; '>,</span> DbMock<span style='color:#808030; '>)</span><span style='color:#808030; '>:</span><br /> <span style='color:#800000; font-weight:bold; '>def</span> setup<span style='color:#808030; '>(</span>self<span style='color:#808030; '>)</span><span style='color:#808030; '>:</span><br /> <span style='color:#e34adc; '>super</span><span style='color:#808030; '>(</span>TestUI<span style='color:#808030; '>,</span>self<span style='color:#808030; '>)</span><span style='color:#808030; '>.</span>setup<span style='color:#808030; '>(</span><span style='color:#808030; '>)</span><br /> login_to_admin<span style='color:#808030; '>(</span>username<span style='color:#808030; '>=</span><span style='color:#0000e6; '>'admin'</span><span style='color:#808030; '>,</span> password<span style='color:#808030; '>=</span><span style='color:#0000e6; '>'admin'</span><span style='color:#808030; '>)</span><br /><br /> @show_on_error<br /> <span style='color:#800000; font-weight:bold; '>def</span> test_order_add_no_transport<span style='color:#808030; '>(</span>self<span style='color:#808030; '>)</span><span style='color:#808030; '>:</span> <span style='color:#696969; '># ticket:9</span><br /> go<span style='color:#808030; '>(</span>SITE <span style='color:#808030; '>+</span> <span style='color:#0000e6; '>'/shop/order/add/'</span><span style='color:#808030; '>)</span><br /> code<span style='color:#808030; '>(</span><span style='color:#008c00; '>200</span><span style='color:#808030; '>)</span><br /> <span style='color:#800000; font-weight:bold; '>assert</span> <span style='color:#800000; font-weight:bold; '>not</span> <span style='color:#0000e6; '>"Transport"</span> <span style='color:#800000; font-weight:bold; '>in</span> show<span style='color:#808030; '>(</span><span style='color:#808030; '>)</span><span style='color:#808030; '>,</span> show<span style='color:#808030; '>(</span><span style='color:#808030; '>)</span></pre><h2>Link 2. ItQuest.ru</h2>Возможно, многие из читателей уже слышали о таком сервисе, как <a href="http://itquest.ru/">ItQuest.ru</a>. А если не слышали - обязательно обратите на него внимание. Ресурс идейно схож с <a href="http://stackoverflow.com/">StackOverflow</a> - большая база вопросов и ответов на IT тематику. Так что если у Вас есть вопрос, ответ на который не знает даже Google, попробуйте задать его здесь.<br />P.S. Сайт написан на Django. Еще один повод присмотреться.Sergey Kishchenkohttp://www.blogger.com/profile/13451038740185023562noreply@blogger.com3tag:blogger.com,1999:blog-1625043994572710700.post-49021167353789182672009-03-23T23:45:00.000+02:002009-03-23T23:56:09.617+02:00Sapka contestНе так давно закончился контест <a href="http://stanfy.com.ua/contest/">Sapka</a>, который проходил с 13-го по 20-е марта 2009 года. Я принимал в этом контесте участие и не могу не поделиться впечатлениями, ведь их было очень-очень-очень много. <h2>Введение</h2>Sapka - контест, больше похожий на <a href="http://www.icfpcontest.org/">ICFPC</a>, чем на контесты, проводимые <a href="http://www.acm.org/">ACM</a>. А именно - задание здесь одно, марафонного типа, которое может решить практически любой хороший программист, но только в ситуации, когда у него в распоряжении будет неограниченное количество времени. К тому же задания как в ICFPC, так и в Sapka обычно намного интересней, подаются в игровой форме и больше требуют не знания алгоритмов, а умения напрягать мозг, концентрировать усилия и бороться. Для меня контест <i>Sapka</i> стал первым контестом подобного типа.<h2>Команда</h2><i>Sapka</i> и <i>ICFPC</i> - командные соревнования. Естественно, участвовать можно и одному, но для одного человека объем работы очень велик, да и вместе веселее. Поэтому очень важным является выбор команды, настройка средств коммуникации, распределение ролей и т.д.<br />Я до самого конца не был уверен, буду ли я участвовать в <i>Sapka</i>, поэтому команду я нашел лишь за день до соревнований, да и за день мы никак не готовились к участию. Как ни странно, но ничего страшного из-за этого не случилось, были и покрупней просчёты :) Итак, команда под названием "<b>a</b>" изначально состояла из трёх человек - Вашего покорного слуги, <a href="http://undefined.org.ua/blog/">xa4a</a> и <i>A2K</i>. Но у последнего участника под конец соревнования были завалы с учебой, поэтому написанием самого решения занимались всего два человека. <h2>Начало соревнования</h2>Оригинальное задание можно прочитать <a href="http://stanfy.com.ua/contest/">на сайте Sapka</a>. Фан начинается уже здесь. Если кратко - то нам даётся некий сервер некой игры, в которую надо стучаться по телнету. Нужно написать клиента для этой игры. Всё! Никакого точного ТЗ, только упоминание о том, что сначала сервер нужно сконфигурировать. И вот с таким багажом знаний все участники и вступают в игру.<br />Лично для себя я всё время участия могу поделить на 3 этапа:<h2>Этап 1. Хак сервера :)</h2>То, что сервер написан на Java, и то, что защита там игрушечная, впоследствии позволило многим командам получить все нужные для конфигурации данные в течение первых 1-2х часов соревнования. Это также вызвало бурные дискуссии и недовольство тех, кто не смог сервер хакнуть. В <a href="http://groups.google.com.ua/group/sapka-contest">гугл-группе</a> даже <a href="http://groups.google.com.ua/group/sapka-contest/browse_thread/thread/573262de84547fc3">жаловались</a>, что из-за того, что в команде не было ни одного джависта, у них не получилось похачить сервер и поэтому они не смогли "заняться собственно программированием"(с). Для тех, кто все еще считает, что для взлома сервера обязательно нужны знания Java - следующий абзац.<br />Обладая минимальными знаниями Java и обладая к Java большой нелюбовью, я пересилил себя и приступил к "взлому" сервера. Вся процедура взлома заключалась вот в чём: разархивировать jar; увидеть, что там есть какой-то loader; натравить на него jad (найден в google по словам Java Decompiler); открыть Eclipse; запихать туда расшифрованный код; пройтись по коду и найти место, где происходит дешифрация; добавить запись в файл прямо там(код записи в файл был также найден в google ;));скомпилировать и использовать получившийся код для дешифрации файлов; после этого натравливать jad на дешифрованные файлы. Чтобы долго не лазить по обфусцированному коду, я взял и банально расшифровал самые большие файлы, которые были в архиве. И тут же налетел на нужные файлы - на описания логики игр. Чуть погодя(почему погодя - смотрите ниже) был написан и генератор конфигурационных токенов(простым копированием существующего кода). Вы всё еще считаете, что для взлома сервера нужно было знание Java? ;)<br />На самом деле, я занимался исследованием сервера намного дольше, чем это могло показаться. Во-первых, я вначале пытался достать конфигурационные токены прямо из памяти, но успеха не добился. Во-вторых, команда активно ковыряла квестовую часть Сапки, и я также принимал в этом участие.<h2>Этап 2. Квест</h2>Все конфигурационные токены можно было достать, пройдя текстовый квест, общаясь по telnet с сервером. Это было очень увлекательно, поэтому даже когда я уже достаточно продвинулся в процессе взлома, мы всё равно продолжали решать задачки. Так были найдены практически все токены, кроме DNA (сгенерировать токен оказалось намного проще, чем решить эту задачу). Также были подсмотрены в коде сервера секретные пароли, так что токены, которые они дают, также были получены путём хака.<br />В общем, описать квестовую часть практически невозможно - это было незабываемо! :) Внутри был Брейнфак, Forth-подобный язык, "шашки"(за них отдельное спасибо, я был просто поражен, когда обыграл его) + несколько задачек на преобразование текста. Я постарался не выдавать никаких секретов в описании, поэтому если вы не видели квеста - it's worth to try it out! Даже несмотря на то, что игра завершена, удовольствие вам гарантировано.<h2>Этап 3. Программирование бота</h2>После прохождения квеста стало ясно, что нам нужно написать клиент к <a href="http://en.wikipedia.org/wiki/Bomberman">bomberman</a>-like игре. В качестве основного инструмента был выбран язык Python. Краткое описание процесса:<br /><i>xa4a</i> - написание парсера для сообщений от сервера<br /><i>xa4a</i> - создание визуализатора (на pygame)<br /><i>tilarids(/me)</i> - улучшение визуализатора<br /><i>xa4a</i> - создание keyboard controller<br /><i>xa4a</i> - рефакторинг, фикс багов, random AI<br /><i>tilarids(/me)</i> - добавлено избегание опасных мест<br /><i>tilarids(/me)</i> - добавление уничтожителя стен<br /><hr>Здесь небольшая врезка - кончился lightning раунд. На lightning раунд был отправлен бот, который не ставил бомб, а только убегал от опасностей. Причина - за убийство себя давали -1000 очков, а бот был страшен в своей наглости и часто себя убивал. <br />Дальнейшая разработка заключалась практически в улучшении, рефакторингом и пофиксах существующих алгоритмов. <hr><i>xa4a</i> - большой рефакторинг, добавлен нормальный механизм переключения состояний<br /><i>tilarids(/me)</i> - добавлен учёт времени взрыва бомб, простейшее начисление очков(в соответствии с идеей A2K), пофикс багов<br /><i>xa4a</i> - добавление охоты за бонусами, пофикс багов, рефакторинг бомб<br /><i>tilarids(/me)</i> - добавление охоты за противником<br /><i>xa4a</i> - завершение рефакторинга бомб, добавление учета подрыва бомбами друг друга, пофикс багов<br /><i>tilarids(/me)</i> - пофикс багов, пофикс учета коллапса мира, сабмит<br /><hr>На этом уже подошел к концу сам контест. Мы засабмитили бота, который умеет всё, что нужно для победы, но, к сожалению, он всё же не бессмертен и частенько умирает.<br />Краткое описание алгоритмов. Бот - простейший автомат, с такими состояниями как "беги", "ищи, куда поставить", "ставь", "охоться за бонусами", etc. Переход из одного состояния в другое был жестко зашит - никакой сложно логики выбора состояния не было - она была просто лишней. Для нахождения путей был применен волновой алгоритм, который учитывал опасности на пути. Для нахождения места, куда ставить, также использовался волновой алгоритм, на котором помечались цели с указанием очков за эти цели. После того, как алгоритм отрабатывал, выбиралась цель с набольшим количеством очков, такая, что если рядом с целью поставить бомбу, то мы сможем оттуда убежать(для проверки, можем ли мы убежать, также использовался волновой алгоритм). В случае, когда бомбу поставить не было возможности, включалась охота за бонусами.<br />Для тех, кто хочет посмотреть, как это выглядело:<br /><object width="425" height="344"><param name="movie" value="http://www.youtube.com/v/3Cva5coK2rE&hl=en&fs=1"></param><param name="allowFullScreen" value="true"></param><param name="allowscriptaccess" value="always"></param><embed src="http://www.youtube.com/v/3Cva5coK2rE&hl=en&fs=1" type="application/x-shockwave-flash" allowscriptaccess="always" allowfullscreen="true" width="425" height="344"></embed></object><br />Репозиторий с исходниками находится <a href="http://bitbucket.org/xa4a/bomber/">в публичном доступе</a>. Также есть <a href="http://bitbucket.org/xa4a/sapka-player/overview/">просмотрщик риплеев</a>.<h2>Благодарности</h2> Хотелось бы выразить огромнейшую благодарность организаторам. Sapka - это было потрясающе! Такого количества фана я не получал уже очень давно. Спасибо вам за то, что вы сделали!<br />Также хотелось поблагодарить команду - мне показалось, что работали мы достаточно слаженно, и я очень рад, что мне довелось участвовать в Sapka в команде именно с таким составом.<h2>Организаторам</h2><ul><li>Всё же сервер надо защищать лучше. Чтобы взлом сервера был отдельной трудной задачей, а не заменял прохождение квеста. Например, можно было бы некоторые задания составить так, чтобы понадобилось их решать программно в момент запуска клиента</li><li>Побольше бы заданий наподобие fifth. Задачки на преобразование текста были занятные, но по количеству фана намного менее содержательные</li><li>Я буду очень рад поучаствовать в Sapka 2010 ;)</li></ul><h2>Себе на заметку</h2><ul><li>Если желаешь выиграть, нужно пользоваться даже относительно нечестными методами. Если бы мы не тратили время на квест, когда уже были почти все токены, на лайтнинг можно было бы успеть отправить уже активного бота</li><li>Количество участников в подобных соревнованиях - не главное. Но хорошо, если есть участники, которые могут потратить время на поиск и исправление багов</li><li>Возможно, стоило попробовать переписать всё вообще без состояний, чтобы получить простого, как пробка, но зато бессмертного/безбажного бота. Но после драки кулаками не машут :) </li><li>Pygame - отличная платформа для визуализации чего-либо</li></ul>Sergey Kishchenkohttp://www.blogger.com/profile/13451038740185023562noreply@blogger.com9tag:blogger.com,1999:blog-1625043994572710700.post-37635418734345304432009-03-02T13:15:00.004+02:002009-03-05T18:44:50.711+02:00Reia - скриптовый язык для виртуальной машины Erlang`аЛично я считаю Erlang одним из самых простых яызков программирования, а среди знакомых мне функциональных языков - самым простым. К тому же на Erlang благодаря его направленности на создание конкурентных приложений написано уже множество проектов, таких как <a href="http://yaws.hyber.org/">Yaws</a>, <a href="http://couchdb.apache.org/">CouchDB</a>, <a href="http://www.ejabberd.im/">ejabberd</a>, которые являются для него наилучшей рекламой. <br />Таким образом, Erlang - функциональный язык с простым и понятным синтаксисом, который нашёл свою нишу, и если вы интересуетесь созданием масштабируемых конкурентных систем - вам стоит выучить его. Однако из-за того, что Erlang - функциональный, его синтаксис и стиль понятен не всем - он слишком отличается от императивных языков(таких как С и подобные) и даже от Ruby/Python, которые включают в себя частицы функционального подхода. <br />Если Вы столкнулись с такой проблемой - обратите внимание на <a href="http://wiki.reia-lang.org/wiki/Reia_Programming_Language">Reia</a> - скриптовый Ruby/Python like язык для виртуальной машины BEAM(эта виртуальная машина используется также и в Erlang). Язык Reia совместим с Erlang и может использоваться для создания конкурентых приложений, однако используя при этом скриптовый синтаксис. Вот простейший пример:<br /><pre>module Foo<br /> def bar<br /> receive<br /> when msg<br /> ["Received ",msg].join().puts()<br /> bar()<br />pid = Process.spawn(fun {Foo.bar()})<br />pid ! "Hello"<br />pid ! "World"</pre>Результат:<br /><pre>Received Hello<br />Received World</pre>В язык заложено очень много возможностей(как по мне - слишком много :) ): отсылка сообщений процессам и объектам, встроенные регулярные выражения, pattern matching, асинхронные вызовы функции, лямбда функции, а также многое-многое другое. Многое из этого не реализовано(например, циклы), но часть функциональности уже существует и работает, как можно увидеть из примера.<h2>Выводы</h2><ol><li>Reia - многообещающий ЯП, которому, однако, не хватает разработчиков. Возможно, если реализации будет уделяться больше времени, то этот ЯП станет мостиком, по которому толпы приверженцев императивного подхода ринутся в страну Erlang</li><li>Как по мне, синтаксис Reia перегружен. Этот вывод только подкрепляет моё убеждение, что Erlang - отлично спроектирован и очень элегантен</li></ol>Sergey Kishchenkohttp://www.blogger.com/profile/13451038740185023562noreply@blogger.com2tag:blogger.com,1999:blog-1625043994572710700.post-2911158761957085192009-02-25T13:25:00.001+02:002009-02-25T13:33:59.934+02:00app-engine-patch 1.0 is out!Не далее как 24-го февраля сего года увидела свет новая версия одной незаменимой вещи для разработки под <a href="http://code.google.com/intl/ru/appengine/">Google AppEngine</a>, а именно <a href="http://code.google.com/p/app-engine-patch/">app-engine-patch</a>.<br /><a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjGXxwbtTvzApQ08AmgdT0GDf_TsPdI2BcbBcNkfhkWfIVkxs5CO_zOnMw6k947l0mUaHg7PG1CkH5bJv3yHwWPZSKjYR7gOO3RcxQbCtFCiHBqlolyxUaWEvrq-WPkZDcRB-eWkL9h8Xo/s1600-h/Screenshot-%D0%90%D0%B4%D0%BC%D0%B8%D0%BD%D0%B8%D1%81%D1%82%D1%80%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5+%D1%81%D0%B0%D0%B9%D1%82%D0%B0+%7C+%D0%90%D0%B4%D0%BC%D0%B8%D0%BD%D0%B8%D1%81%D1%82%D1%80%D0%B0%D1%82%D0%B8%D0%B2%D0%BD%D1%8B%D0%B9+%D1%81%D0%B0%D0%B9%D1%82+Django+-+Mozilla+Firefox.png"><img style="display:block; margin:0px auto 10px; text-align:center;cursor:pointer; cursor:hand;width: 320px; height: 187px;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjGXxwbtTvzApQ08AmgdT0GDf_TsPdI2BcbBcNkfhkWfIVkxs5CO_zOnMw6k947l0mUaHg7PG1CkH5bJv3yHwWPZSKjYR7gOO3RcxQbCtFCiHBqlolyxUaWEvrq-WPkZDcRB-eWkL9h8Xo/s320/Screenshot-%D0%90%D0%B4%D0%BC%D0%B8%D0%BD%D0%B8%D1%81%D1%82%D1%80%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5+%D1%81%D0%B0%D0%B9%D1%82%D0%B0+%7C+%D0%90%D0%B4%D0%BC%D0%B8%D0%BD%D0%B8%D1%81%D1%82%D1%80%D0%B0%D1%82%D0%B8%D0%B2%D0%BD%D1%8B%D0%B9+%D1%81%D0%B0%D0%B9%D1%82+Django+-+Mozilla+Firefox.png" border="0" alt=""id="BLOGGER_PHOTO_ID_5306692319428296658" /></a><br />Кажется, ничего особенного на этом скриншоте нет - всего лишь Django admin интерфейс. Однако, я не зря запостил этот скриншот - это админка Django запущенная под app-engine-patch! Теперь и под GAE можно получить эту "killer" feature Django. Об остальных нововведениях можно прочитать <a href="http://code.google.com/p/app-engine-patch/wiki/ReleaseNotes">здесь</a>. Меня особенно радует, что портировано <i>django.contrib.sites</i>, однако пока я не могу заставить <i>django.contrib.sitemaps</i> работать.<br /><br />P.S. Еще два поинта, на которые я хотел бы указать. Во-первых, планы на будущее - "Native Django support (including Model class)."(с). Во-вторых, появилась некая тулза, которая пытается проверять импорты на правильность(кто сталкивался со страшными ошибками при случайных рекурсивных импортах - поймёт, насколько это хорошо :) )Sergey Kishchenkohttp://www.blogger.com/profile/13451038740185023562noreply@blogger.com0tag:blogger.com,1999:blog-1625043994572710700.post-85400404617815767412009-02-24T23:45:00.002+02:002009-02-25T10:30:10.891+02:00TDD's revengeПопробовал себя в "рисовании" комиксов. То, что получилось - ниже:<br /><a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEi45u0wUUU7fHfMssU-95cvPVrMOGa0hksP_311RJ_d4JnNF8dG3eRpSVFxQPs23T_tP231qZi9LCaz6xV-Jfjyw-YlPe94Ex_Z-41c74JLWJ1H9xGMH0CXopidsYs3RCYvH1qx6mExIEM/s1600-h/tdd_revenge.png"><img style="display:block; margin:0px auto 10px; text-align:center;cursor:pointer; cursor:hand;width: 160px; height: 320px;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEi45u0wUUU7fHfMssU-95cvPVrMOGa0hksP_311RJ_d4JnNF8dG3eRpSVFxQPs23T_tP231qZi9LCaz6xV-Jfjyw-YlPe94Ex_Z-41c74JLWJ1H9xGMH0CXopidsYs3RCYvH1qx6mExIEM/s320/tdd_revenge.png" border="0" alt=""id="BLOGGER_PHOTO_ID_5306482657535333714" /></a><br />А теперь о серьёзном. Я сейчас собираюсь перевести RSS на <a href="http://feedburner.google.com">feedburner.google.com</a>. Надеюсь, проблем не возникнет и все подписчики просто ничего не почувствуют. Однако, если вы за своим RSS-агрегатором замечали проблемы с обработкой редиректов или неперевариванием feedburner - пишите, будем разбираться :)Sergey Kishchenkohttp://www.blogger.com/profile/13451038740185023562noreply@blogger.com3tag:blogger.com,1999:blog-1625043994572710700.post-77701405665487350952009-02-10T22:45:00.001+02:002009-02-10T22:48:23.241+02:00Знакомьтесь: Geany!<h2>Введение</h2>Я уже <a href="http://tilarids.blogspot.com/2008/12/scite-incremental-autocompletion.html">писал</a>, что мне очень нравится редактор <a href="http://www.scintilla.org/">SciTE</a> и поэтому я его постоянно использую, например, при программировании на Python. Однако в GTK версии есть несколько недостатков:<ul><li>Открытие большого числа вкладок невозможно - не работает прокрутка и multiline</li><li>Глюки с юникодом - если написать <i>\что-то</i> при редактировании TeX документа, получим несуразные символы. Эти же несуразные неудаляемые символы также иногда появляются в строке поиска</li><li>Нет нормальной интеграции с shell. В итоге для простейшей проверки конструкции в <i>ipython</i> приходится переключаться на терминал</li></ul>Естественно, можно было бы подправить это в самом SciTE, но зачем, если всё уже сделано? Представляю вам <a href="http://www.geany.org/">Geany</a> - простейший редактор с замашками IDE(которые, в принципе, не мешают :) ) основанный на том же движке, что и SciTE - на <a href="http://www.scintilla.org/">Scintilla</a>.<br /><a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgn47W91wr3PpxB3mbLb5S9Z1wprlcC7NsKcTjUS2ST5xpSM3DVmSQkFRmoB6XkUX-QikH2cHwBrdRwgnplR-iWGxff2Ht7WV_oRk_76dO9Lqp7i2BDVo2BAyb0fGoAs5MPadHqlhwOBGY/s1600-h/Screenshot-middleware.py+-+-home-sergey-dev-w-djtesttask-django_authopenid+-+Geany.png"><img style="display:block; margin:0px auto 10px; text-align:center;cursor:pointer; cursor:hand;width: 320px; height: 187px;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgn47W91wr3PpxB3mbLb5S9Z1wprlcC7NsKcTjUS2ST5xpSM3DVmSQkFRmoB6XkUX-QikH2cHwBrdRwgnplR-iWGxff2Ht7WV_oRk_76dO9Lqp7i2BDVo2BAyb0fGoAs5MPadHqlhwOBGY/s320/Screenshot-middleware.py+-+-home-sergey-dev-w-djtesttask-django_authopenid+-+Geany.png" border="0" alt=""id="BLOGGER_PHOTO_ID_5301271201518552802" /></a><br />На этом скриншоте он уже немного подконфигурирован для моего удобства. Возможности Geany:<ul><li>Подсветка, фолдинг - аналогично SciTE</li><li><b>Нормальные табы</b></li><li><b>Поддержка VTE</b></li><li>Symbol explorer</li><li>Плагины(в числе встроенных FileBrowser, SplitWindow и т.д.)</li><li>Автодополнение по символам(неплохое, но для Python хотелось бы лучше. Geany - Open Source, так что возможно это желание будет реализовано)</li><li>Автозакрытие тегов</li><li>Сессии</li></ul>Более подробно хотелось бы остановится на поддержке VTE. Благодаря ей в Geany есть полноценный терминал! Насколько это удобно можно понять, прочитав следующий раздел.<h2>Конфигурирование</h2>В этом разделе я хочу дать описание моего рабочего окружения в Geany. Оно не блещет уникальностью, но весьма удобно. Конечный внешний вид - на скриншоте выше. По пунктам: <ol><li>Ставим. Я просто выполнил "<i>emerge -av geany</i>". Думаю, в остальных Linux дистрибутивах его можно поставить сходным же образом. Для Windows пользователей - <a href="http://www.geany.org/Download/Releases">есть инсталляторы</a></li><li>Убираем Sidebar, дабы сэкономить площадь</li><li>Задаем комбинации клавиш для удобного перемещения по табам</li><li>Настраиваем терминал - самая интересная часть. Я выбрал себе темную темку и запустил внутри <i>screen</i> - в итоге я могу переключаться между логами сервера, <i>ipython</i> и дополнительными консолями. Для меня терминал в Geany - самый важный инструмент. В нём я работаю с <i>git</i> и <i>hg</i>, в нём я отлаживаю приложение, в нём же я и лажу по файлам("<i>geany file_name</i>" открывает файл в новой вкладке). Таким образом, терминал мне заменяет File Browser, Debugger и VCS Inegration</li><li>Настраиваем шрифт, остальные комбинации клавиш и интерфейс по вкусу</li></ol>У меня в <i>screen</i> не заработала клавиша Backspace, пришлось биндить. Ниже - кусок конфигурационного файла <i>screen</i> (.screenrc), который делает screen юзабльным:<pre>bindkey -d ^@ stuff ^? # пофикс backspace<br />hardstatus on<br />hardstatus alwayslastline<br />hardstatus string "%{Gk}| %-w%{+u}%n %t%{-}%+w |%=(%l) %d/%m %c"</pre>До сих пор нормально не работает скролл на мышке, прокрутка вверх генерит "^[[A". Если у кого-то есть уже решение - поделитесь :) Если разберусь сам - проапдейчу.<h2>Выводы</h2>Geany - отличный редактор, полностью покрывающий мои запросы. На данный момент я использую его для Python разработки и редактирования TeX файлов. Для С++ же я предпочитаю IDE <a href="http://anjuta.sourceforge.net/">Anjuta</a>, хоть Geany можно использовать и здесь.Sergey Kishchenkohttp://www.blogger.com/profile/13451038740185023562noreply@blogger.com9tag:blogger.com,1999:blog-1625043994572710700.post-70361310384212094952009-01-28T23:23:00.003+02:002009-01-28T23:50:41.370+02:00Debugging with app-engine-patch and pdbIf you ever tried to use pdb in application written using app-engine-patch, you should notice, that pdb is not working here at all. All pdb output is shown directly in browser. Thanks to <span style="font-weight:bold;">Antonin Hildebrand</span> from <a href="http://groups.google.com/group/google-appengine/browse_thread/thread/9f226a46a0de3188/c08269e8da190452?show_docid=c08269e8da190452">this</a> thread now we have a way to use pdb for debugging GAE applications. Use following code to put trace in your app: <br /><pre style='color:#000000;background:#ffffff;'><span style='color:#800000; font-weight:bold; '>def</span> b<span style='color:#808030; '>(</span><span style='color:#808030; '>)</span><span style='color:#808030; '>:</span><br /> <span style='color:#800000; font-weight:bold; '>import</span> pdb<span style='color:#808030; '>,</span> sys<br /> sys<span style='color:#808030; '>.</span>__stdout__<span style='color:#808030; '>.</span>write<span style='color:#808030; '>(</span><span style='color:#0000e6; '>'\a'</span><span style='color:#808030; '>)</span><br /> sys<span style='color:#808030; '>.</span>__stdout__<span style='color:#808030; '>.</span>flush<span style='color:#808030; '>(</span><span style='color:#808030; '>)</span><br /> debugger <span style='color:#808030; '>=</span> pdb<span style='color:#808030; '>.</span>Pdb<span style='color:#808030; '>(</span>stdin<span style='color:#808030; '>=</span>sys<span style='color:#808030; '>.</span>__stdin__<span style='color:#808030; '>,</span> stdout<span style='color:#808030; '>=</span>sys<span style='color:#808030; '>.</span>__stdout__<span style='color:#808030; '>)</span><br /> debugger<span style='color:#808030; '>.</span>set_trace<span style='color:#808030; '>(</span>sys<span style='color:#808030; '>.</span>_getframe<span style='color:#808030; '>(</span><span style='color:#808030; '>)</span><span style='color:#808030; '>.</span>f_back<span style='color:#808030; '>)</span><br /><span style='color:#696969; '>#...</span><br /><span style='color:#696969; '>#...</span><br /><span style='color:#696969; '>##########################</span><br />b<span style='color:#808030; '>(</span><span style='color:#808030; '>)</span><span style='color:#696969; '>#here I want to start tracing</span></pre>For me it worked without any <span style="font-style:italic;">dev_appserver.py</span> patches. Try it out!Sergey Kishchenkohttp://www.blogger.com/profile/13451038740185023562noreply@blogger.com0tag:blogger.com,1999:blog-1625043994572710700.post-62669035958237850872009-01-28T11:00:00.000+02:002009-01-28T11:08:27.866+02:00Write in CНе так давно я довольно круто поменял направление деятельности, чем практически вытеснил язык С++ из своей коммерческой практики. Несмотря на это, я продолжаю его любить и продолжаю использовать в некоторых некоммерческих проектах. Так что, надеюсь, в последующих постах будет как Python, так и С++(не считая всего остального). И как доказательство моей преданности семье С языков, ниже отличный ролик. Улыбнитесь!<br /><object width="425" height="344"><param name="movie" value="http://www.youtube.com/v/XHosLhPEN3k&hl=en&fs=1"></param><param name="allowFullScreen" value="true"></param><param name="allowscriptaccess" value="always"></param><embed src="http://www.youtube.com/v/XHosLhPEN3k&hl=en&fs=1" type="application/x-shockwave-flash" allowscriptaccess="always" allowfullscreen="true" width="425" height="344"></embed></object><br />Если вы даже после этого не не соглашаетесь, что иногда стоит писать на C, а не, например, Python, предлагаю посмотреть вот <a href="http://spreadsheets.google.com/pub?key=pbqSxQEo4UXwPlifXmvPHGQ">сюда</a>Sergey Kishchenkohttp://www.blogger.com/profile/13451038740185023562noreply@blogger.com0