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.