ICFP Contest '08 Final results

На официальной странице ICFP Contest выложены результаты, которые так долго ждали большевики. Было проведено 11 заездов, в результате которых был определен один победитель (Team Smartass) и 297 неудачников, которым не так повезло. К сожалению финальные карты еще не выложены, поэтому трудно сказать что пошло не так, но финалисты предыдущего чекпойнта "вылетели за ограждение". Как в прошлый раз, я подготовил таблицу с суммарными результатами. Команды отсортированы по количеству раундов, в которых они приняли участие независимо от результата. Команды, прошедшие одинаковое число раундов отсортированы по рейтингу. Напоминаю, чем меньше рейтинг, тем круче. Для каждой команды приведена статистика исходов по всем пяти заездам каждого раунда. В общем, можно меряться. Get it and use it well.

Моя команда называется Mosquito. Каким чудом она попала на 11 место, оставив позади страшных монстров, сам не понимаю. Видимо, новичкам везет.

#	Team	Rounds	Score	Home	Martian	Crater	Timeout	Error
1	Team Smartass	11	512510	50	5
2	shinh	11	515370	49	5	1
3	Error 404	11	541960	50	3	2
4	UBE	11	546000	48	7
5	LazyBear	11	556870	51	2	2
6	SzM	11	608630	40	5	5	5
7	souris aveugle	11	611620	40	12	3
8	frank324	11	643610	39	6	5	5
9	kstm.org	11	674530	40	13	2
10	fireinthedisco2	11	689400	45	8	2
11	Mosquito	11	730040	41	8	5	1
12	Om Nom Nom Nom	11	743140	37	15	3
13	Giantslalom	11	748550	38	16	1
14	epriestley	11	765090	33	17		5
15	intelliarts	10	609050	37	8	1	4
16	cw	10	617070	40	10
17	The B-Team: 25/26ths as good as the A-Team	10	619280	40	1	4	5
18	Blue Iris	10	626860	37	13
19	Spore Sept 7th, only $49.99! Play Bejeweled @ popcap.com!	10	631580	38	10	1	1
20	team_bruno	10	649780	41	9
21	Hands Solo	10	652200	40	8	2
22	jabber.ru	10	654310	37	13
23	Celestial Dire Badger	10	659590	44	6
24	Side Effects May Include...	10	660740	38	12
25	Apathy Kings	10	665890	36	12	1	1
26	CNaml	10	672810	37	13
27	Cup<'t>	10	695250	36	13		1
28	TC2	10	703310	40	10
29	Team Meh	10	710430	38	12
30	Yeahbut	10	712870	43	7
31	td	10	716950	42	7	1
32	Purple Pointer Eaters	10	719560	35	15
33	TeamDJ	10	721200	36	13	1
34	ur 67P	10	723350	32	17	1
35	NMSU	10	732770	39	11
36	Actua	10	739020	34	16
37	Eger a Marson	10	739540	35	13	2
38	EdFred	10	742580	38	10	2
39	Arekuma	10	748030	35	13	2
40	little lemon	10	784960	34	14	2
41	Order of the Fridge	10	805310	33	17
42	HackerDom_1	9	442150	35	10
43	ais523	9	442380	38	7
44	ILL martians	9	448300	34	11
45	Sir Bedevere the Wise	9	450780	34	9	2
46	Kee	9	455360	36	9
47	Urxae	9	465070	34	10	1
48	Heklers	9	465790	33	8	4
49	Malfunctional Programmer	9	470250	35	10
50	42	9	477900	33	11	1
51	Slow	9	478020	36	9
52	LUHPI	9	484290	36	7	2
53	tidder	9	486570	34	10	1
54	elbereth@utmc	9	487230	37	8
55	Wile E.	9	492300	35	9		1
56	12a0	9	494180	31	14
57	PurelyFunctionalInfrastructure	9	501520	34	11
58	RHZ	9	501570	36	7	2
59	m1-speedygonzalez	9	515180	34	11
60	Five of Six	9	516800	30	7	6	2
61	Bobry	9	543260	29	4	11	1
62	a1k0n	9	553370	28	13	4
63	Team Sampou	9	572500	30	14	1
64	taxi driver	8	398800	29	10	1
65	BugbearR	8	411060	34	5	1
66	Dee Mon	8	428540	34	6
67	ayatuki	8	433350	26	9	5
68	HackerDom	8	434210	28	12
69	Too Simplicity and Beyond!	8	438920	26	9	4	1
70	I-cons-a-lot	8	448770	29	9	2
71	The Dibbies	8	448860	23	11	6
72	Hacking in the Rain	8	454330	24	7	8	1
73	Altair	8	462550	29	9	2
74	lazymonkeys	8	468020	30	6	3	1
75	'a infvec	8	471290	28	7	5
76	protocolocon	8	472150	31	4	1		4
77	Kharkiv MIND	8	479810	27	8	5
78	Begot	8	501070	25	15
79	Lazy elf	8	509630	23	10	6	1
80	astsmtl	7	313950	27	8
81	shitamachi no ue	7	319560	27	7	1
82	kounoike	7	323950	28	7
83	Java Jones and the Kingdom of the Crystal Crater	7	331520	26	7	2
84	TBD	7	331980	25	10
85	lepidum	7	333640	27	8
86	ktkr-cpp	7	339090	26	6	2	1
87	miyu	7	341220	30	4	1
88	Gcup	7	341560	26	8	1
89	Epsilon	7	353250	29	4	2
90	nanndemoiidesu	7	355670	25	9		1
91	pirapira	7	357200	25	10
92	barry, our driver, is reckless	7	366510	25	9	1
93	NAU ACM	7	372490	21	9	5
94	TheRoverers	7	373210	24	11
95	DotWeb	7	403330	20	9	6
96	SwtPl	7	403430	21	10	4
97	7-15	7	416680	22	12		1
98	Beer:Thirty	6	263510	24	3	2		1
99	Team DumbAss	6	278530	21	8	1
100	inforfun	6	278540	24	6
101	Team Lolemnity	6	284370	21	5	2	2
102	ntua 67P	6	285500	23	4	3
103	jan nasa	6	295270	23	5	2
104	Pear Programmers	6	295850	24	4	2
105	Christoph Breitkopf	6	297470	24	6
106	spotrover	6	297980	21	3	5	1
107	cashto	6	298450	22	5	3
108	The Weyburn Expatriates	6	299910	22	3	5
109	ORBIT	6	301320	24	2	4
110	Rhope Burn	6	301820	23	2	5
111	aruhimorinonaka	6	302020	22	7	1
112	green_tea	6	303570	24	4	2
113	Bob's Store	6	305870	22	2	6
114	WindowMakers	6	307600	22	7	1
115	The Blind Hen	6	307990	22	6	2
116	bmm team	6	309570	24	2	4
117	Grasshoppers	6	309860	21	6	3
118	The Tcler	6	320610	20	3	6	1
119	ksk	6	321500	21	2	7
120	MIMUW 4060	6	325260	22	6		2
121	Florida Institute of Technology	6	325410	22	5	3
122	D&D	6	327400	18	3	7	2
123	wjdogs	6	328260	17	5	8
124	Kerochan	6	329180	20	7	3
125	The Unchecked Exceptions	6	329930	20	1	9
126	In dumb we trust	6	335040	19	7	4
127	Curry On!	6	335190	17	3	6	4
128	KFL	6	335540	21	2	5	2
129	hibi@utmc.or.jp	6	336640	21	3	5	1
130	YBuzz	6	338630	20	3	6	1
131	Dragons	6	339210	18	3	8	1
132	Q42/Xopus	6	341840	18	4	7	1
133	Team Guyford	6	342030	18	12
134	Arsbit	6	351210	18	5	7
135	one canuck	6	354510	17	7	6
136	Chouser	6	355910	18	3	7	2
137	uguu.org	6	356690	18	4	8
138	midoj	6	367820	19	6	4	1
139	The Tweezer Minstrels	6	370960	15	7	8
140	bens	6	373000	17	8	5
141	apple2gs	6	378790	21	5	4
142	yarunee	6	381880	16	3	8	3
143	The Usual Suspects	6	382080	21	3	6
144	Ramen Holiday	6	383550	19	4	6	1
145	The Code Alchemists	6	384790	21	8	1
146	Team Rocket	6	389320	19	4	7
147	nekoneko	6	393150	17	5	7	1
148	The Inmates	6	393770	20	7	3
149	camping gaz international	6	397790	22	2	6
150	solo r6	6	402650	20	8	1	1
151	GRoboCode	6	403340	19	3	8
152	ktkr-ocaml	6	411990	18	5	7
153	LazyBottoms	6	445710	16	6	7	1
154	spbsunt	5	176870	21		4
155	It's all about the Pentiums.	5	183290	19	3	3
156	Emory PChem	5	184270	19	5		1
157	Toasted Monkeys	5	186140	19	2	2	2
158	Le club des 5	5	188750	19	4	2
159	suihan_jar	5	193440	17	4	3	1
160	Wobbla Team	5	193980	20	4	1
161	__ufo42	5	205480	13	2	6	4
162	Dis Functional	5	209550	15	4	6
163	POSTECH-PL	5	210090	16	5	4
164	The Higher Order Of Zeuxis	5	212910	17	3	3	2
165	Unary Operator	5	214170	18	4	3
166	POSCAT@POSTECH	5	222830	14	2	5	4
167	suzumiyaharuhiko	5	224050	11	7	4	3
168	Hidden Agenda	4	147770	14	6
169	Incompetent Design	4	148210	11	5	3	1
170	OCamlCore	4	153050	12	5	3
171	Knights of Cydonia	4	159050	12	5	3
172	Marcin Simonides	4	160540	12	8
173	td2	4	160620	13	3	4
174	efg	4	161220	13	3	3	1
175	AntiCylonDefenseTeamImpersonator	4	161650	12	6	2
176	ikon	4	162730	10	3	4	3
177	o(ry	4	164470	14	5	1
178	bucchigiri	4	165230	13	2	5
179	Dylan Hackers	4	165310	13	5	2
180	Team Gales	4	165700	11	2	5	2
181	The Rover Routers	4	166900	13	5	1	1
182	Anairiats	4	167190	14	3	2	1
183	Tigerfunk	4	170840	6	2	8	4
184	dot-emacs	4	173780	7	2	8	3
185	Fly (Yaroslavl)	4	175800	12	7	1
186	K&R	4	175840	13	3	4
187	Mostly Harmless	4	178490	12	7	1
188	AyaCFP	4	178530	13	7
189	putzen along	4	178740	12	7	1
190	Enoch Root	4	179780	11	5	3	1
191	futurelabs	4	180990	12	4	4
192	Molotov Mocktail	4	186430	9	7	2	2
193	Servants of Barsoom	4	187290	12	8
194	NetHack	4	187550	12	6	2
195	Ruby Team	4	187930	12	8
196	Almaya	4	188130	12	5	2	1
197	gassa & toxa	4	193000	11	7	2
198	(defun friends)	3	107180	10	3	2
199	The Lone TeXnician	3	107700	8	2	3	2
200	hogelog	3	108370	6		6	3
201	Insane Closure Posse	3	111800	11		4
202	Macrott	3	113310	9	3	2	1
203	Blazing Saddles	3	115370	9	3	1	2
204	yet another team	3	115550	7	4	1	3
205	honey_rooibos	3	116140	9	6
206	Evil Geniuses For a Better Tomorrow	3	117360	10	4	1
207	TeamNewshamBros	3	117630	9	2	4
208	Illudium Q-36 Explosive Space Modulator	3	118060	9	4	1	1
209	Giver	3	118500	9	2	4
210	rmathew	3	119120	5	2	5	3
211	SIMAP	3	119570	9	3	2	1
212	eugene_jeff	3	122240	6	4	2	3
213	polka	3	124300	8	4	2	1
214	Func-n-stein	3	125140	7	2	4	2
215	EddieHasNoPreferenceForName	3	126480	8	5	2
216	Xebia	3	128110	8	3	3	1
217	Bad Science	3	129430	8	6		1
218	Stern Types	3	130400	7	3	2	3
219	siti	3	132470	7	6	1	1
220	panard_groumpf	3	134380	5	3	3	4
221	SugarSun	3	134660	8	6	1
222	mfp	3	135860	4	5	1	5
223	NCSU ARC Alums	3	136960	9	3	3
224	The Bobcat Hackers	3	138980	6	5	2	2
225	Knights of the Crescent Moon	3	140250	5	4	2	4
226	isobe	3	140660	7	4	3	1
227	EarthFusion	3	144310	8	5	1	1
228	Epic Fail	3	146750	6	5	2	2
229	plai	3	147620	5	6	2	2
230	ozy4dm	3	157370	7	8
231	wheezards	2	57930	8	1			1
232	Soul Trader	2	77580	4	2	1	3
233	404 NOT FOUND	2	78470	3		1	5	1
234	WE NEED A TEAM NAME	2	78540	6	2	1	1
235	Not a Number	2	78910	5	2	1	2
236	Stanfy	2	79440	7	1	2
237	Bloody Camls	2	79500	7	3
238	Team Sparrow	2	79740	6	3		1
239	Too much free time	2	80430	6	2	2
240	Linkage Failure	2	80660	7	3
241	kt3k	2	81230	7				3
242	Suzumiya Haruhiko wo Ooini Shizumeru Fullbocco-dan	2	81960	6	3	1
243	University of Western Australia	2	83980	6	2	2
244	Littlechina	2	84830	5	3	1	1
245	Drifter's Revenge	2	85150	5	2	1	2
246	Erraen	2	85860	6	3	1
247	cthulhuivore	2	86940	2	1	3	4
248	ktkr-java	2	89390	4	2	1	3
249	Ocamlman	2	89500	5	2	2	1
250	Team Cow	2	90130	6	2	2
251	Rhinos	2	90200	1	1		8
252	Cup<T>	2	92040	6	3	1
253	The Chun Council	2	92340	6	4
254	FUN	2	92460	4	5		1
255	ICSkies of Blue and F(P)	2	92550	4	2	3	1
256	Felspar	2	92560	6	3	1
257	Happy Camels	2	92670	6	3	1
258	The Teddyborg	2	92850	2	3	1	4
259	drunken ants	2	92860	5	2	2	1
260	foognostic	2	92950	1	2		7
261	Marti	2	93070	6	3	1
262	StreetMagic	2	94650	6	2	2
263	Cal Poly Pomona Computer Science Society	2	97530	6	4
264	nishiohirokazu	2	98510	6	4
265	United Coding Team	2	98880	5	5
266	KuntbucketsAndKuntrags	2	100630	1	3		6
267	Turn Right Left	2	100670	5	5
268	mazeSolver@UTMC	2	102330	3	4		3
269	Schwarzschild	2	107120	5	3	2
270	gpfault id-alex	2	107250	2	4		4
271	aalto high school	2	115320	1	5	1	3
272	The Dudes	2	115510	3	5		2
273	Engineers Without Boulders	2	116710	4	4	1	1
274	The Al-Gore-Rhythms AKA The Doug Boat	2	117700	1	3	1	5
275	Team_XIII	2	119200	5	5
276	The Armstrongs	2	124310	5	1			4
277	casillero del diablo	2	125570	1	5		4
278	gzoluble	2	130690	5				5
279	Chvex Stucture	2	148470	1			4	5
280	SATiriker	1	36160	1			3	1
281	The unmoving notogawa	1	42300				5
282	Monkeyget	1	42300				5
283	Sim	1	42300				5
284	P Squared	1	42300				5
285	gb	1	42300				5
286	mokehehe	1	42300				5
287	ocaml users anonymous	1	42300				5
288	LISA~HackLab-FI	1	42300				5
289	zetafish	1	42300				5
290	Puddingforce	1	42300				5
291	Chicago Blubs	1	42300				5
292	Nodal Asymmetry	1	84000					5
293	incognito	1	84000					5
294	Monadic Cows	1	84000					5
295	Late Ocamler	1	84000					5
296	Rufus2	1	84000					5
297	greedy	1	84000					5
298	The Shiniest of Heisenbugs	1	84000					5

Закон больших чисел

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

На большой выборке даже маловероятные события становятся наблюдаемыми.

На практике этот закон означает полную неприменимость «наивной» аналитики и, как следствие, «наивного» тестирования при проектировании информационных систем. Если не предусмотреть редкие случаи ещё при проектировании они больно стукнут на стадии эксплуатации, причем далеко не сразу, а лишь по прошествии некоторого инкубационного периода. Это чревато хотя бы тем, что багфиксинг на внедренной системе, в которой уже накоплен значительный объем данных — отдельное развлечение.

Ещё одно проявление Закона больших чисел в том, что невозможно построить информационную систему гарантированно не содержащую ошибок в данных. Простой пример: Оператор вводит данные вручную. Оператор не идеален, поэтому он делает одну ошибку на 100 записей. Это означает, что на 1 000 000 введенных записей будет порядка 10 000 ошибок. Поскольку такое количество ошибок нас не устраивает, мы садим поверх оператора контроллера, который будет проверять правильность ввода. Пусть контроллер более внимателен и продуктивен, однако и он не идеален, поэтому допускает одну ошибку на 1000 записей. Тогда вероятность ошибки снижается до 10^-5 на запись. Однако, на миллионе записей это даст примерно 10 ошибок. Если количество данных неограниченно растет, а так бывает почти всегда, никаким контролем не добиться гарантированного отсутствия ошибок. Даже оценить вероятность ошибки и то не всегда возможно. Люди не механические приборы, к ним паспортов точности не полагается.

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

• Признают, что качество данных не имеет значения для бизнеса;
• Контролируют качество собственными силами;
• Выбирают один из наборов данных и признают его эталонным.

Это всего лишь частные эффекты. На практике достаточно хорошо осознавать, что чем больше данных, тем сильнее проявляется Закон больших чисел, влияние которого нужно учитывать при проектировании, в разработке и в тестировании.