Judge's source codes have been published

The source codes of the judge system and the traditional origami silhouettes from the Kojiki have been published on GitHub:

https://github.com/icfpc2016/icfpc2016-judge

We will keep the post-mortem server running for a while, but we may shut it down in the future without any prior notification.

Contest results are up!

Thank you very much for your patience. We have announced the final result of the contest in ICFP:

1st place

Unagi

2nd place

天羽々斬 (ame-no-habakiri)

Lightning division winner

jabber.ru

Judges' prize

TBD

The team TBD is evaluated by the fact that the team submitted a problem solved by no other team.

All the final standings are as follows.

Rank	Score	Team Name	Programming Languages
1	700327	Unagi	Java,C++,C#,PHP,Haskell
2	268752	天羽々斬	C++, Ruby, Python, Haskell, Java, JavaScript
3	243456	Cult of the Bound Variable	C++, Standard ML, Python
4	211020	WILD BASHKORT MAGES	Python, OCaml, C++
5	201776	Frictionless Bananas	C++
6	192501	kontur.ru	C#
7	185202	Tsuru	C++, JavaScript, Go
8	146270	negainoido	Ruby, Python, PHP, Bash, Haskell, SQL
9	138789	nerunerunerune	C++, Python, JavaScript, Ruby, ShellScript
10	117388	DiamondPrincess	Haxe,Python,C++,shell
11	112182	jabber.ru	OCaml
12	99701	kstm.org	Scissors, Pen, Ruby
13	97359	モダン焼 フジ	C++,Python
14	96320	Lens d'Ulm
15	93680	yowa	Ruby
16	93159	fixstars	C++, Java, Python, JavaScript
17	83936	TBD	Python3
18	83710	typo	Python
19	81972	THIRTEEN	Java, Kotlin, Python, JavaScript, C++
20	77145	The $oun𝅗𝅥 0f λ	ruby, python
21	62895	Olympia	c++, c#, javascript, asp.net
22	60550	unfold	OCaml, Unix shell, gnuplot
23	57690	Deramer	python, bash
24	57292	Invisible Imp	Scala, jq
25	54727	😼̯__,	Common Lisp,Ruby
26	53636	Snakes vs Lambdas	python, c++, bash, javascript
27	52884	TheWildLobsters	Common Lisp
28	52752	lilik	Rust, Python, Javascript, Macaulay2
29	46223	powder	Haskell,bash
30	45368	The Cat is #1!!	JavaScript,C#,python,go,html,brainfuck
31	44446	Temporary OCaml Team Name	OCaml
32	44437	cashto	C#
33	36371	big.Rat	go, shell script
34	35565	Raging Mushrooms	Ocaml problem generator, lisp solver, js/php glue and visualizers
35	34341	GD and Alumni	Scala
36	33441	Barbarella	OCaml
37	33122	Zebra Infused Hamsters	C, C++, Python, bash, Ruby, CMake
38	31659	MIPT Lambda	Haskell
39	29655	Stanfy+	kotlin, bash, java, javascript
40	28710	Henchman #24	Python,Haskell
41	28457	Buy Ascension VR on Steam, $9.99	C++ for the solver, javascipt to make problems, C# for the rest API
42	27499	Eger a Marson	Haskell, (+Python for the API access only)
43	26327	NCPLUG	Haskell
44	25838	Hydralisk eats taco	OCaml, JavaScript
45	25452	A Storm of Minds	Java, groovy, bash
46	25184	301	Kotlin
47	24407	Zygohistomorphic Preproxenomorph	Haskell, Python, Bash
48	24284	CubeClub	python
49	24262	uguu.org	C++
50	24180	codingteam	Haskell
51	23416	Small Opulent Shelducks 💨	Scala, Python, Bash
52	22604	sdb	Java,Python
53	20554	sonna*baka*na	Our brain and Excel
54	20200	Coding Monkeys	Kotlin
55	20104	kittykoala	C#
56	19489	Möbius Swan	Ruby, Elm, Python
57	19286	code-o-matic	Python
58	18717	Piggybank Software	C++, Java, C#, windows bat files
59	18467	Omega men
60	18128	why-five-aye	NFlat, C#
61	16831	Sunspear	Haskell, C++
62	16702	びア部🍺	JavaScript, C++, Python, Haskell
63	16561	Skobochka	Haskell, PHP, Bash
64	15804	TeamDev
65	15726	Team Awesome	Haskell,Python,JavaScript
66	15309	bystander.js	JavaScript
67	14947	I'ZOO	C++ language
68	14929	Team Sampou	Haskell, shell, jq
69	13941	xyz	Python
70	13259	trup16	Python
71	12038	udfew
72	11822	IKS	python, minizinc, c++, bash, sql
73	11666	yarunee	Ruby
74	11072	lambda-llama	OCaml,Python,JavaScript
75	10712	R22b	Python, C++
76	10703	Le doux cri du yak des cimes	python,OCaml
77	10632	Team K&R	Python
78	10246	fotocopia-al-150	Python
79	10176	ALAMBDA	Clojure, Python
80	10017	Goto11	C++, Mathematica, Lisp,JavaScript
81	9941	Xeniac	Python
82	9851	peria	C++,python
83	9769	Bears ate our brains	C++, bash
84	9523	Dao of the fold	OCaml
85	9299	Not bad team at all	C#
86	8900	The team formally known as	Haskell
87	8600	AZALEA
88	8186	Junk Food	Haskell,Shell
89	7807	InforFun	Java
90	7390	ImaginaryCF
91	6905	Gassa & The Family	D, bash
92	5835	COBOL_lovers	COBOL,Java,Python,C++
93	5746	Scala Ballas 🏀	Scala
94	5377	Leaf Pie	Bash
95	4973	👸💕 We Love Chiiia 💕👸
96	4930	CTDElite
97	4918	🐍 String Invaders 👾
98	4909	Task Manager (Not Responding)	D
99	4765	Wagner-sama	C++, Python, ...
100	4676	Leonardone @ NEETSDKASU	F#
101	4658	This is an albatrocity!	python
102	4246	kstm	Python,PHP,JavaScript
103	3924	taxidriver
104	3908	lass1e	ruby
105	3322	WOMBAT	Python
106	3237	paiv	C++, Python
107	3019	The Higher Order Of Zeuxis	Haskell, Java
108	2954	foldCrane	scala, R, python
109	2741	Errol's Robots
110	2677	Wintermute	Java, Kotlin, Python
111	2336	loop the hack
112	2235	試運転	C++
113	2207	prolab
114	1598	ParseError	f#, c#, Z3
115	1442	d4o	Haskell, Python
116	1438	Canivsar
117	1261	Falt mal kurz	Python
118	1221	Team SSL	Haskell,pen and paper
119	1176	Team Super Legit	Rust
120	832	nobu
121	820	SteelRaven
122	567	The Pragmatic Russians
123	546	🌟 kirakira 🌟	Rust
124	484	kmc
125	464	public static void main	Ruby
126	278	O Caml, My Caml	Haskell
127	259	cauchym	JavaScript, Ruby
128	231	Taupiqueur	ocaml, python
129	211	Wowbagger6809	Tcl
130	180	Movio	JavaScript,Haskell,Go
131	150	Standard ML/Yeah!	Haskell,Python
132	136	gzoluble	Ruby
133	85	abcde
134	75	Team Aerokraft	python
135	66	ha2ne2	Clojure
136	64	Belle Area	Haskell,Python
137	54	chiiia12
138	51	Folding Functor
139	44	診断人
140	41	Folds R Us	Haskell
141	35	Team Wolfie
142	32	Solo 399
143	25	Sedentary Mollusc
144	23	epriestley	PHP
145	18	ricknmorty	Racket
146	15	xsd	OCaml
147	13	cw	Java
148	12	2ManGroup	Java
149	11	wheezards	golang
150	11	NaruseJun	Haskell, JavaScript
151	11	PartialOrder	C++
152	11	Limbo
153	8	tcybe
154	8	rover
155	7	Wombatman	F#
155	7	kludgefactory	Ruby
155	7	LoneRanger
158	7	YOLOswag	American
159	7	Aecium
159	7	O
159	7	perpetuum mobile	Scala
159	7	framus	english
159	7	ghost
159	7	cereal
159	7	read & write
166	5	Cactus	C++
167	2	dumbojet
168	2	Marooned Combiners
168	2	Room 641a	Go, JQ, Shell
168	2	豆腐祭り
171	2	ヒッキープログラミングするスレ	Ruby
172	2	Powershop is hiring
173	2	Olakka
173	2	アリクイ㌠	C++
173	2	r152	C++
173	2	naoys
177	2	Paper Tiger
178	1	phantomancy
179	1	vsapsai
180	1	Jackstone
181	0	Gyutan
182	0	Celestial Dire Badger
182	0	pro.elixir
182	0	Leg of Lambda
182	0	tanzaku
182	0	CDT
182	0	Princess Molestia
188	0	uint32_t
189	0	Samurai Helmet of Origami	C++,Python
189	0	GFlat	F#
189	0	side effect
192	0	Dis Functional
192	0	AtnNn
192	0	TusanHomichi
192	0	begot
192	0	Rarest Pepe	Perl, Javascript, Snobol
192	0	Wrong Endians	Scala
192	0	pibe
192	0	D3but	RU
192	0	Wile E.
192	0	112	Russian
192	0	Biorigamics
203	0	Wandering Hobos	julia
203	0	NULL
203	0	yowa
203	0	pk
203	0	Hemisphere
203	0	Slow
203	0	Too lazy to think of a name....	Haskell
203	0	Riaqn
203	0	botrevenge
203	0	Pokebowl
203	0	teofr
203	0	Team Mugit
203	0	Oklahoma FC	Haskell
203	0	Byker Dave	English
203	0	ATS
203	0	kami-waza
203	0	Pastillage Research
203	0	moray	C++
203	0	Blue Iris
203	0	Lazy Owl
203	0	framus	english
203	0	LonelyNerd
203	0	Little Bippy & Big Growler
203	0	Flexible Demeanour
203	0	OrigamiRaven	Go
203	0	Hemisphere	Scala
203	0	AllIWantIsToSeeTheProblems
203	0	Occupational Face Plant
203	0	Church of the Least Fixed Point
203	0	TIML6574
203	0	Team Aerokraft
203	0	Team Aerokraft
203	0	Son of a Lambda!	Python
203	0	notogawa	Haskell
203	0	LoLi Saikou	Common Lisp
203	0	貴方、「怠惰」ですねえ	Common Lisp
203	0	suikkee
203	0	mekajfire
203	0	lopihuta
203	0	sergeif	J, C
203	0	Fly On The Wall
203	0	Pelmeshki
203	0	rocco66_team
203	0	KOLOBOLOK
203	0	Flying Teriyaki Monster	Haskell
203	0	Lilik
203	0	Menschenkindlein
203	0	Peeing Turtle
203	0	*ptr	Haskell
203	0	アヒル㌠	C++
203	0	Deterministic Market Ride
203	0	Midorimushi	Haskell, Scala, Java
203	0	TaupeGoons
203	0	¯\_(ツ)_/¯
203	0	covax	Haskell, C#
203	0	nbu
203	0	DNIWE :: a	Turbo Pascal 6.0
203	0	Freeball
203	0	Lyrical Tokarev
203	0	ggg
203	0	Codermal	C++
203	0	Not There Yet
203	0	JavaScriptFullCompilation	JavaScript
203	0	orzr
203	0	FooBar
203	0	Thommi
203	0	yohmike
203	0	BC	C++
203	0	Team007	PHP
203	0	診断人
203	0	診断人
203	0	drop_table_users
203	0	radupeca
203	0	lopihuta
203	0	pecaradu
203	0	Test team
203	0	Hekul
203	0	iFold
203	0	test
203	0	kamikaze
203	0	UPA
203	0	vodka_bear_balalaika
203	0	cata	Scala
203	0	hakomo
203	0	The seekers of curiosity
203	0	keizo
203	0	chiiia12
203	0	on vacation
203	0	Far away from Gallifrey
203	0	Lightning	Python
203	0	Mischa

We started accepting T-shirt orders!

We are soon announcing contest winners in ICFP 2016, but meanwhile, here's an update for T-shirts!

Thank you for answering the questionnaires about T-shirts. According to the responses, design A was very popular compared to design B, so we are making design A only. Also we will produce slim-cut (womens) T-shirts too.

So, now, we are ready to accept orders!

We prepared two editions of T-shirts: Screenprint Edition and DTG Edition. While the design is the same, all others (garment, printing method, price, logistics, ...) are totally different. Please read carefully the explanations below before placing orders.

1. Screenprint Edition

This edition uses screenprinting as T-shirt printing method. We expect it to have higher quality and durability than DTG Edition, while price is lower.

Price is 1,500 JPY. Items are sold and shipped by BOOTH, a Japan-based company. Since BOOTH does not support international shipping by itself, if you live outside Japan, you need to use some international forwarding service to ship items overseas. BOOTH recommends tenso.com (see links below for details).

Order deadline of Screenprint Edition is Sep 30 23:59 UTC. Estimated shipping date is October or December.

2. DTG Edition

DTG stands for Direct-To-Garment, and this edition prints T-shirts on demand by ink-jet printers. One good point about this method is that items can be produced on-demand, any time.

Price is 32.99 USD. Items are sold and shipped by CafePress, a US-based company. It supports international shipping by itself.

We set no deadline for this edition, so you can buy one whenever you like.

Summary

The table below summarizes the differences of two editions:

Order Links

Finally, here are links to the shops!

Screenprinting Edition, Mens:
https://icfpc2016-tshirt.booth.pm/items/327165
Screenprinting Editions, Womens:
https://icfpc2016-tshirt.booth.pm/items/328441
(You can change the display language by the dropdown box at the bottom of the page)
(Tenso.com http://www.tenso.com/en/static/lp_shop_booth is recommended by BOOTH for international shipping)

DTG Edition, Mens:
http://www.cafepress.com/cp/customize/product2.aspx?from=CustomDesigner&number=1941085036
DTG Edition, Womens:
http://www.cafepress.com/cp/customize/product2.aspx?from=CustomDesigner&number=1941085496

We hope you like them!

Winners have been notified.

We have sent the notification of all prizes to the winners. The emails were sent from the address icfp-contest _at_ researchr _dot_ org on 17 and 29 August. Please check your mail box whether the notification is buried under spam messages.

We are making T-shirts!

We are planning to make ICFP Programming Contest 2016 T-shirts. If you are interested, please fill in this questionnaire so we can estimate the total number of orders.

ICFP Programming Contest 2016 T-shirts Questionnaire

Note that submitting this form does NOT place an order. We will later announce the details on how to order them on this blog.

This activity is approved by our sponsors, ACM and ICFP.

You've done a great job!

We have been receiving a lot of heartwarming messages, and are already learning that many of the solutions had been generated by karate humans or computer-aided humans. You have shown another class of problems computers alone cannot solve well, and have shown the importance of human-computer collaboration. All the efforts you have put in are the live evidences that make the vision beyond The Singularity substantially brighter, than any predictions and spells found in the Kojiki.

The purpose of the contest has been fulfilled.

The contest is over!

The contest is over! You may not submit solutions anymore.

We would like to remind you once again to submit your source code. See the source code submission instructions for details. You can still update your team profile on the server for the next 24 hours.

Meanwhile, we have set up a postmortem server, where we have put all the submitted problems. If you want to continue playing, please use the postmortem server.

We hope you have enjoyed this year's ICFP programming contest. We love you all and are deeply grateful for your participation. Please look forward to the announcement of the final results at ICFP 2016. Good game, everyone!

The last hour of the contest!

Less than an hour to the end! While you put forth your final effort, please be reminded to prepare your source code for submission. Please see the source code submission instructions for details.

Announcing the leaderboard freeze

Our fridge have been repaired! The leaderboard is now frozen as planned. All submissions from now on will not be reflected in the leaderboard. However, other pages of the contest server, especially the “Solution Ranking” section in the “Problem Details” pages, will remain up to date until the end of the contest. Good luck!

Notification of the system change

We have detected a subtle glitch in our system, however, this will not affect any of the contest activity including problem submissions, solution submissions, and evaluations. We are now working on a fix.

(12:00 UTC, 7 Aug) Update: The glitch was that our fridge have failed, so we cannot freeze the leaderboard for the moment.　We also have little choice but to give out all the sushi and sukiyaki we have kept in the fridge. It’s a little bit earlier than we’ve planned, but please accept these rewards and hang on for remaining hours.

Appologies on icfpcontest2016@googlegroup.org icfpcontest2016@googlegroups.com

We have found out that our contact e-mail address has been rejecting posts from non-members. Those who have tried to contact us via e-mail may have received following messages. We have now fixed our configuration.

We're writing to let you know that the group you tried to contact (icfpcontest2016) may not exist, or you may not have permission to post messages to the group. A few more details on why you weren't able to post: ...
 
Our sincere appologies for the inconvenience.

Also note that some file types are blocked for this e-mail address. Again, if you have any problem, please do not hesitate to contact us, so that we can make our best effort to retrieve your valued source codes.

Source code submission and how to win Judges' prize

Sixteen hours left till the end of the contest! We would like to ask you to review your team information (http://2016sv.icfpcontest.org/profile) before the contest ends, especially:

•  Contact email address 
•  Team member names
•  Languages
•  Source code URL

You need to submit source codes within 24 hours from the end of the contest. The easiest way is to upload your source code on a web server (e.g. your own web server, Dropbox or Google Drive, etc.). If you cannot provide a public URL, please leave it blank and send your source files into icfpcontest2016@googlegroups.com by the end of the contest. Please contact us if your source code is too large to send it via email.

Preferably, the source code URL should point to a single .tar.gz archive file. Judges will make our best effort to handle other formats. Put README.txt in the root directory of the submitted archive to nominate yourself for the Judges’ prize. Let us know how you have survived the contest!

How to solve origami 101 (crane) in 8 seconds

Our server solves origami 101 in 8 seconds by simulated annealing. It should not be so hard!

The idea behind the rate limits

Dear contestants,

You might have been feeling uncomfortable with the rate limits on the APIs. Well, we would like to support your efforts till the very end of the contest. We don't prefer to promise you optimistic rates and betray your expectations at the last moment of the contest, when you are in the final rush and need the server stability the most. We have prepared computer resources that are able to serve at these rates under any foreseeable circumstances in the future. Of course, unexpected things happen, but we have recovered from one of such cases.

We will do our best in keeping up the servers, so please enjoy the contest, and please find out the most blessed origami possible!

Meanwhile, here are some tips:

• Cache your blob lookup results.
• Take record of the best solution you have submitted and its resemblance to each problem, and postpone new submissions until you have made improvements.

More informative server responses for invalid submissions

It is our pity that you might have suffered from too many of the blunt invalid solution  messages. In fact, each of those invalid origami had contained weak but certain portion of prayer for better error message so that the contest server have accumulated the enough enchantment to return more informative error diagnostics:



We wish this update help you as you are going to face harder problems.

Notification of the change of the leaderboard system

Previously, the score values in the learderboard at HH:00 included the problem scores of those published at HH:00. We are now working on the change, so that the score values at HH:00 include the problem scores of those published before HH:00 but not of those published at HH:00.

Consequently, the result of the lightning round might differ from the leaderboard published at 00:00 UTC, 6 Aug. Also note that all the submissions are subject to investigation and re-evaluation after the contest, and any evaluation published during the contest are just for your reference, and are not final.

(01:35 UTC, 6 Aug) Update: The mentioned change on the leaderboard have been implemented. The leaderboard at 02:00 UTC and thereafter will not include the scores from those problems just have been published.

Let the full round begin!

The first set of user-generated problems have been published. 

Thank you all for your participation.

Never forget to post your own problems!

Submitting your own problems is an important way to increase your team scores, and you must do so before the deadlines.

Reserve problems publication schedules from this url: http://2016sv.icfpcontest.org/problem/submit. Never miss your important opportunities to submit your problems.

Publication of contestant-generated problems starts from 24 hours after the start of the contest (0:00 (UTC) 6 August, 2016), and one problem per hour is published for each team. You cannot submit a problem to a timestamp after that time has passed! So we strongly recommend submitting several problems before going to bed (if you ever do). You can update your problem submission reservations anytime before their publication. See Problem Submission specification for the details.

Notification on the contest system

We've found a bug in the contest scoring system. We are now working to fix this problem. All related submission will be re-evaluated after the bug is fixed.

Update: We believe that the scoring bug mentioned above has been fixed (09:55 UTC, Aug 5).  The leaderboards will be fixed accordingly.  The leaderboards remain incorrect at the moment, although the solutions submitted after the fix have been evaluated correctly. Please wait until we re-evaluate all the solutions to fix the leaderboards.

Update: The bug has caused some valid solutions to be rejected. In case of any doubt please just re-submit those solutions. Sorry for the inconvenience.

Update: We have fixed the scores and the leaderboards (11:04 UTC, Aug 5). Also the leaderboards at 11:00 UTC are correct. The scores for the following solutions have been modified:

• Team 21 (Standard ML/Yeah!), Problem IDs: 24 29 52 59 60 61 63 65 66 75 82 89 91 94 100
• Team 92 (gzoluble), Problem ID: 67
• Team 103 (Hydralisk eats taco), Problem ID: 8

If you would like to know the correct resemblance, please just re-submit your solutions.

Sorry for the inconvenience.

Questions and Answers

Q. Where is a PDF?

A. PDF for Task Description is found at http://icfpc2016.blogspot.jp/2016/08/pdf-for-task-description.html

Q. Black writing on brown background is really bad.

A. Please reload the Web page in your browser.

Q. Is it ok to register the team with incomplete list of members for now?

A. Yes, as long as you keep the conditions that one person is member of only a single team, and that teams do not divide or collaborate, you can complete the list of members after your initialization. You can edit your team profile from the contest server interface.

Q. Is the example solution specification correct? The second facet listed, 4 1 2 6 5 I believe should instead read 5 1 2 6 5.

A. Please read the facets part specification carefully.

Q. How do I use the playground tool?

A. Drag from point A to point B, and you can fold the paper at the perpendicular bisector of the two points.

Q. The playground tool does not work.

A. Please use one of the latest browsers on your computers with mouse devices. We also have (limited) touchscreen support. In any case, operation or consistency with the task description is not guaranteed.

Q. Are polygons from an input silhouette guaranteed to be simple? Or they can be of arbitrary shape even with self-intersections?

A. The boundary of a silhouette polygons does not intersect with itself. Also, it does not share a fixed-length segment with itself. However, it may touch itself at finite numbers of points.

Q. Is there guarantee that holes in an input silhouette are within some polygon from the silhouette with positive area?

A. All holes in an impute silhouette are always within other positive-area polygons.

Q. Blob Lookup API doesn't work.

A. Your access to our server might be failing because of your network configuration. Note that the blob lookup API returns a redirect (303 See other) to storage.googleapis.com. In order to access the blob lookup API you need to be able to connect to 2016sv.icfpcontest.org and storage.googleapis.com. Please check if you can connect to them. If this is not your case, please post your question with the details (the name of the hash you can't access, the IP address you are connecting from, the error message, etc.)

Q. When a solution has to be normalized?

A. Normalized solutions are only required for problem submissions. Solutions to existing problems are not necessarily normalized, and just have to be valid.

Q. Can you increase the submission rate limit of at 1000 / hour?

A. No, this is the hard limit from our server capability and the numbers of already registered teams. In fact, we might be forced to decrease the rate limits, as precautioned in the terms and conditions.

Q. How can I possibly solve all the problems, given that already thousands of problems are submitted in a few hours?

A. Don't worry. The problem IDs you see are numbered in the order of their submissions. Some of them never get published because they are overwritten by later submissions. Since each team publish at most one problem per hour, and the number of teams is smaller than the number of submissions you can make per second, you will have enough time to solve all the problems. Also note that problem publication is closed 3 hours before the end of the contest. Plan wisely and have some good luck.

Q. What happens when I submit multiple problems to be published at the same time?

A. If you submit multiple problems with the same timestamp, the latest submission will be used. This behavior is described only in REST API Documentation, but the same applies to web interface too.

Q. Are the 1000/hour rate limits rolling 1-hour windows?

A. No, the rate limits are counters reset every hour on the hour (HH:00). See the Rate Limits and Leaderboard Freeze section of the task description for the detail.

PDF for Task Description

Task Description in PDF format is now available here. This PDF is just for reference. The judges offer no guarantee of its consistency with the task description. Refer http://icfpc2016.blogspot.jp/2016/08/task-description.html for the official task description.

Task Description

---

Back Story

General Remark

Problem Specification

Solution Specification

• The source positions part
• The facets part
• The destination positions part
• Valid solution, Normalized solution

Contest Structure

• Team Registration and Solution/Problem Submission
• Solution Evaluation
• Scoring
• Rate Limits and Leaderboard Freeze

Terms and Conditions

---

Back Story

Origamis are artistic objects created by folding square papers into shapes, without cutting or glueing. Origami also refers to the act of creating such objects.

    Origami has been practiced for a long, long time in Japan, and is now popular worldwide. But few are aware of spiritual powers of origami. They offer protection from disasters such as earthquakes, plagues and server failures. Now, we want to enhance the Big Buddha Statue of Nara, by offering enchanted origamis to the Buddha. Origami silhouettes of special meanings are described in the Kojiki, an ancient scroll, but how to fold them is lost knowledge.

    As we are now in the 21st century of industry 4.0, big data, and artificial intelligence, we employ drone geishas to fold origamis. Your task is to recover the folds, each in form of a mapping from a square of paper to a special silhouette, so that the drone geishas can be programmed to fold the ancient origamis described in the Kojiki.

    To make matters worse, the very act of folding origamis using drone geishas draws The Singularity near, that clouds everything (also known as IoT) and makes it impossible to see the future. In preparation for this, we need to find out more powerful origami shapes that were not even predicted in the Kojiki. We need help from all of you here; you are all hardworking programmers, so those origami shapes that are insoluble by most of you must hold the strongest power.

    We live in a two-dimensional world, so only planar origamis are considered. As long as the origami is a valid two-dimensional mapping, it is allowed to specify impossible folds, that require papers to penetrate each other. Never mind, one of geisha's jobs is to warp the reality into fourth dimension.

Sushi and sukiyaki will be rewarded. Wasshoi!

General Remark

In our coordinate system, the x axis points to the right, y to the up. A two-dimensional point is specified in the form a/b,c/d, where the numerators a, c are integers and the denominators b, d are positive integers. The / and the denominator may be abbreviated when the denominator is equal to 1. Fractions may be reducible.

    Often we treat polygons and edges as sets of points. In such cases the boundaries are inclusive. That is, a polygon seen as a set of points includes its edges and vertices; an edge as a set includes its two vertices.

The size of a problem file or a solution file is defined by the number of non-whitespace ASCII characters in it. This is to avoid the issue of newline-code differences among operating systems, of newline characters at the end of file, etc.

    An interactive tool to help you understand the idea of the task is provided at http://2016sv.icfpcontest.org/play . This tool is provided just for reference; it supports only simple valley folds, so you may not be able to create some complex silhouettes with this tool. The interactive tool is not part of the task description, and the judges offer no guarantee of its consistency with the task description. The judges will not use this tool to evaluate your solutions. 

Problem Specification

Figure 1. An origami silhouette with its skeleton.

Each problem is specified by a silhouette of the origami, which is a two-dimensional figure, in ASCII text format. Additionally, a skeleton of the origami is given as a hint. For the exact definitions of silhouette and skeleton, see the “Solution Evaluation” section.

    A silhouette consists of one or more polygons. In silhouette specifications, counterclockwise polygons refer to polygons with positive area; clockwise polygons are treated as holes in the silhouette.

    A silhouette specification consists of the following items, each in one line.

• the number of polygons

• for each polygon, the number of vertices

• for each vertex, its coordinates

A skeleton is a set of edges and folding line segments of the origami. A skeleton is specified by the following items, each in one line:

• the number of line segments

• for each line segment, the coordinates of its two vertices, separated by a space

The skeleton specification must employ the least number of line segments; any two line segments that lie on a same line must be disjoint.

Here is a sample problem specification which corresponds to Figure 1:

1
4
0,0
1,0
1/2,1/2
0,1/2
5
0,0 1,0
1,0 1/2,1/2
1/2,1/2 0,1/2
0,1/2 0,0
0,0 1/2,1/2

For a problem to be a valid one, there must exist a valid and normalized solution that produces the silhouette and the skeleton exactly. The definitions for valid / normalized solutions are given in the following sections.

(21:00 UTC, Aug 5) Update: Problem submissions must be valid and normalized. On the other hand, solution submissions must be valid but not necessarily normalized.

Solution Specification

Figure 2. Visualization of facets of an origami at their source (left) and destination (right) positions. The alphabet labels represent the mapping of the vertices. This mapping constitutes a solution to the origami problem in Figure 1.

A solution to a problem is a mapping that produces the given silhouette. An origami consists of facet polygons created as results of folding the square paper. All the components of origami such as the facet polygons, their edges and vertices have two positions, one at source and the other at destination. The source position is where the paper is a square located at  (0,0), (1,0), (1,1), (0,1), and the destination position is where the paper is folded to form the silhouette.

    A solution specification consists of three parts:

• the source positions part
• the facets part
• the destination positions part

The source positions part

The vertices of an origami are indexed by integers starting from 0.

The source positions part consists of the following items, each in one line:

• the number of vertices

• for each vertex, its coordinate

The facets part

The facets part consists of the list of facet polygons. Each polygon is specified by the indices of the vertices. For facet polygons, the vertices can either be listed in clockwise or counterclockwise order. In both cases, facet polygons are treated as polygons with positive areas.

The facets part consists of the following items, each in one line:

• the number of facets

• for each facet, the number of vertices, followed by the list of its vertex indices, separated by single space characters.

The destination positions part

In this part, destination coordinates of the vertices are listed, in the ascending order of the vertex index.

As an example, here is a solution that corresponds to the above example problem.

7
0,0
1,0
1,1
0,1
0,1/2
1/2,1/2
1/2,1
4
4 0 1 5 4
4 1 2 6 5
3 4 5 3
3 5 6 3
0,0
1,0
0,0
0,0
0,1/2
1/2,1/2
0,1/2

Valid solution and Normalized solution

A solution is valid if and only if it satisfies all of the following conditions:

• All the source positions of the vertices are within the initial square spanned by the four vertices (0,0), (1,0), (1,1), (0,1).
• No coordinate appears more than once in the source positions part.
• Any edge of any facet has length greater than zero.
• At source positions, if two different edges share a point, the point should always be one of the endpoints for both the edges. That is, an edge touching another edge, or edges crossing each other are prohibited.
• All facet polygons are simple; a facet polygon’s perimeter must not intersect itself.
• Every facet at source position maps to its destination position, by a congruent transformation that maps its source vertices to corresponding destination vertices.
• At source position, the intersection set of any two different facets has zero area.
• At source position, the union set of all facets exactly matches the initial square.
• The size of the solution is no larger than Bs = 5000 Bytes.

Note that all facets are defined to have positive areas, regardless of their perimeters being clockwise/counterclockwise, as described in “The facets part” section.

    A solution is normalized if and only if it satisfies all of the following conditions:

• It is valid.
• At source position, if two different facets share an edge for a length greater than 0, then the intersection set of those two facets at destination positions must have an area greater than 0. In other words, if an edge separates two facets, you should always fold the origami at that edge.

Conversely, the following properties of an origami are irrelevant to its validity and normality:

• The skeleton of the origami.
• Whether its destination silhouette fits within the source position (0,0), (1,0), (1,1), (0,1) or not.
• Whether the destination position can be reached just by folding the paper, or it requires parallel transformation and/or rotation of the paper to be reached.
• Whether the paper is not folded at all.

Contest Structure

Team Registration and Solution/Problem Submission

In this section we explain the structure and schedule of the contest. We use the Contest Clock to refer to the timings of various events in the contest. The Contest Clock is set to 00:00 (CC) at the start of the contest, which is 00:00 (UTC) 5 August, 2016. The contest ends at 72:00 (CC).

    At 00:00 (CC) you can start team registration on http://2016sv.icfpcontest.org/. You need to register your team to view problems and submit solutions.

    The contest consists of two rounds. The first 24 hours (00:00 (CC) - 24:00 (CC)) is the Lightning Round where contestants can only submit solutions to those problems that are described in the Kojiki. You don’t need to submit your source code at the end of the Lightning Round.

    The following 48 hours (24:00 (CC) - 72:00 (CC)) is the Full Round where contestants can also view and solve problems created by other contestants. At the end of the Full Round, you will be asked to submit your source code.

Every one hour, the contest server reveals one problem per each team, starting at 24:00 (CC) and till 69:00 (CC). Therefore, each team can publish a maximum of 46 problems. You can pre-register the problems you want to publish, and the contest server automatically publishes them in the order you specified. Pre-registration of the problems starts at 00:00 (CC). Remember, you must submit a valid and normalized solution that produces the problem for your problem submission to be accepted. The problem specification will be automatically generated from the solution you have submitted.

    A team cannot submit a solution to a problem submitted by itself.

Solution Evaluation

(21:00 UTC, Aug 5) Update: Solution submissions must be valid, but not necessarily be normalized. Any invalid solution submissions are not accepted. 
For an origami solution, its silhouette is the union set of all its facets at the destination position. The skeleton of a solution is the union set of all the facet edges at the destination positions.

    Our goal is to approximate, and if possible, reproduce the problem silhouette using your solutions. The skeleton in the problem specification is just a hint, therefore the skeleton of a solution is irrelevant for scoring.

    Solutions submitted for a problem are ranked by resemblance of their silhouette to the problem silhouette. The resemblance of a valid solution is calculated by the following formula:

resemblance = area_and / area_or

• area_and is the area of the intersection set of the solution silhouette and the problem silhouette.
• area_or is the area of the union set of the solution silhouette and the problem silhouette.

Resemblance of each solution is rounded down to six decimal places. Therefore, the highest resemblance attainable by an approximate solution is 0.999999 .

Scoring

Teams are ranked by team score. Teams can increase their scores both by submitting problems and solutions. The team score is the sum of the problem score and the solution score the team receives, calculated as following.

    Submitting a perfect solution, that is, a solution with resemblance = 1.0, is important in making high scores. For a problem, let s be the size of the problem(21:15 UTC, Aug 5) Update: let s be the size of the solution that produced the problem and n be the number of the teams that submitted a perfect solution, plus 1. The problem-setting team receives (5000 - s) / n points, and each team that submitted a perfect solution gets s / n points. The scores for the teams with imperfect solutions are calculated such that the total points earned by all the imperfect solution teams is s / n, and each team's share is proportional to the resemblance of its solution. Remember, you cannot submit a solution to your own problems.

    For example: when 39 teams submitted a perfect solution to a 1000-bytes problem, the problem-setting team will earn (5000 - 1000) / (39 + 1) = 100.0 points. Each team that submitted a perfect solution will earn 1000 / (39 + 1) = 25.0 points, and each team that submitted an imperfect solution will share the total of 1000 / (39 + 1) = 25.0 points.

    If you submit multiple solutions to one problem, only the best one is used for scoring. That is, the solution with the highest resemblance, and in case of a tie, the solution with the smallest size.

   The team with the highest team score is the winner of the contest. In case of a tie, the sum of the sizes of the scoring solutions is calculated for each team. The team with smaller total size will win.

Rate Limits and Leaderboard Freeze

A team may not make more than 1000 submissions per hour (both the problem and the solution submissions count.) That is, a team can make up to 1000 submissions during 00:00 (CC) - 01:00 (CC), 1000 submissions during 01:00 (CC) - 02:00 (CC), and so on. Also, the period between two consecutive submissions must be greater than 1 second. The judges will update the problem list and the ranking every hour, so kindly refrain from refreshing too frequently. The leaderboard will be updated till 66:00 (CC); after that the leaderboard will be frozen, and the final results will be published at ICFP 2016. The statistics for each problem will be updated till the end of the contest.

Clarifications and Questions

Please submit your clarifications and questions as comments to this blog article. In order to provide consistent answers to all contestants, and to make the questions and answers easier to find, we kindly wish your cooperation in using this method of asking questions.

Terms and Conditions

By registration, ICFP programming contest (ICFPC) participants understand and agree to the following terms and conditions.

    Contest participants retain ownership of all intellectual property rights in and to any submitted solutions, source codes, custom tools, and related materials ("submissions") that participants had before submission. As a condition of entry, participants grant ICFPC judges a non-exclusive, perpetual, irrevocable, worldwide, royalty-free license to use, reproduce, publish, distribute, publicly perform, and publicly display the submissions for the purposes of allowing ICFPC judges to test and evaluate the submissions for purposes of the contest.

    One person may only be member of a single team, and teams may not divide or collaborate with each other once the contest has begun. As long as contest participants follow these terms and conditions, and applicable laws, there is no limitation to the number of members in a single team, and contest participants may use whatever programming languages and computer resources.

    Although the judges take the best effort to keep the contest server running, the server is not guaranteed to be available all time throughout the contest. In particular, the server may be temporarily unavailable, or available at lowered submission rate limits, due to server maintenance, server resource constraints or other reasons. Judges are not obliged to take any compensation measures in such cases.

    The judges retain the right to monitor, record, and investigate the submissions, other contest-related activities, or lack thereof, of participants. The records are used for the sole purpose of judgement and are discarded once the contest-related events are over. Violations of these terms and conditions, any attempts to compromise the integrity of the contest infrastructure, attempts to interfere with other participants, attempts to spoil the joy and spirit of the contest will lead to disqualification of the involved participants and revocation of the related scores and prizes. The decisions of the judges on these matters are final. There is no right of appeal. In case of dispute, the judges retain the right to send ninjas to you to “resolve” the issue.

Less than 1 week away until the days!

Are you ready for the upcoming programming contest? Call For Participation is available here. There is additional but important information for all participants.

Contest participants retain ownership of all intellectual property rights in and to any submitted source codes, custom tools, and related materials ("submissions") that participants had before submission. As a condition of entry, participants grant ICFPC judges a non-exclusive, perpetual, irrevocable, worldwide, royalty-free license to use, reproduce, publish, distribute, publicly perform, and publicly display the submissions for the purposes of allowing ICFPC judges to test and evaluate the submissions for purposes of the contest.

One person may only be member of a single team, and teams may not divide or collaborate with each other once the contest has begun. As long as contest participants follow these terms and conditions, and applicable laws, there is no limitation to the number of members in a single team, and contest participants may use whatever programming languages and computer resources.

Everything of these conditions is for enjoying the programming contest. We hope you'll be looking forward to it and do your best on the days.

Welcome!

   This is the official Web site for the ACM SIGPLAN ICFP programming contest 2016, the 19th instance of the annual programming contest series sponsored by the ACM SIGPLAN International Conference on Functional Programming. The official twitter account is @ICFPContest2016.
   The contest will be held for 72 hours, starting from 0:00 (UTC) 5 August, 2016, and ending at 0:00 (UTC) 8 August, 2016. There will be a lightning division, ending at 0:00 (UTC) 6 August, 2016. The task description will be posted here at the beginning of the contest.
   This contest is open to everyone. Neither advance registration nor entry fee is required. Any programming languages may be used.
   There will be prizes for the first (US$1,000) and second ($500) place teams as well as a discretionary judges' prize ($500) and a lightning division ($500). The winners will be announced at ICFP 2016 in Nara, Japan, on 19-21 September, 2016.