ICFP Contest 2017 - strength test for real developers
ICFPC is an annual competition for programmers. It runs online and lasts 72 hours. ICFPC 2017 will start on Friday, August 4th at 12:00 (UTC) and end on Monday.
I'll tell you why you can not miss ICFPC and give a series of tips. Free up the next weekend, gather a team and take part!
ICFPC - team competition. Competitions for singles are many: for example, Facebook Hacker Cup and Google Code Jam . If you like AI for games, then codingame.com has great challenges every 2-3 months. In single competitions, the top is usually crammed with some kind of geniuses, and in team ones you can perform well due to persistence and good organization.
')
A team can be any size. Usually tasks on ICFPC can be solved in several ways. Trying all the ways and choosing the best is a big job. In 2011, I played in a team of two people. We had no lack of ideas, but we acutely felt a lack of hands.
Competition for thoughtful. The competition lasts for three days, so you do not need to be fast, like an olympiad programmer. There is time to think about the task, to understand and implement any algorithm.
Tasks are not banal. The organizer of the competition changes every year. This is usually a university, so they add reference to computer science to problems and classics (for example, in 2014 there was a reference to SECD machines ). In addition, ICFPC is dedicated to the ICFP functional programming research conference, and this affects the objectives. Once you have to read the descriptions on the functional pseudo-language (do not be afraid, understandable for the average man!), And then program the virtual machines and compilers.
One problem! For 72 hours, a team of unlimited size should solve only one task. But multifaceted and difficult. It cannot be solved optimally, but it can be solved better than other teams. The most unusual and bright tasks are the tasks of 2006 and 2007, in which virtual machines inside virtual machines and also reverse engineering of virtual machines ruled the show.
I, xoposhiy , participated in the ICFPC 9 times. And every time there was something new:
In recent years, our team consistently ranks in the top ten:
Interestingly, the third place in 2013 was won by a team of 8 people. And last year the team took the 6th place from as many as 12 people. Here, a normal person should be surprised how we are capable of such a crowd for three days working productively on just one task? I'm telling!
Frederick Brooks Act: "If the project does not fit the deadline, then adding labor will delay it even more"
I'll tell you on the example of the problem from last year's ICFPC 2016.
Given the silhouette of a flat origami, assembled from a square sheet of paper 1 × 1. You need to restore the origami scan, that is, mark the lines of the folds on the sheet and describe for each vertex on the scan where it goes to the silhouette. In the beginning there are 100 silhouettes from the organizers. In 24 hours, the participants will be able to submit their tasks for rivals.
How to solve?
Use task duality. Need to solve origami. And you need to come up with origami, which rivals cannot solve. This is the first opportunity for parallel work. Dual tasks are common in ICFPC. In 2010 and 2014 there were similar tasks.
Solve problems in different ways. We immediately came up with two ways to solve origami: collect a 1 × 1 square from the polygons visible on the silhouette, and vice versa, extend the silhouette so that it turns out to be 1 × 1 square. It was not clear which of these methods is better, so we split up and started making them in parallel.
Then he noticed that a lot of silhouettes - bulging figures. And they are solved trivially - by bending the edges of the square. Therefore, we wrote another convex origami solver.
Then we noticed some difficult tasks from the WILD BASHKORT MAGES team (hello, ripatti ) that would bring a lot of points, and wrote a solver for them. (In the end, we learned that MAGES also wrote a specialized solver for our origami)
Then we wrote a visual solver, which helped to cope with several dozens of origami manually. As a result, we had 5 different solvers for one problem.
In 2013, we also took the third place due to the fact that we had two different solvers for different types of problems. In ICFPC, specialization and duplication of solutions help.
Start with an auxiliary code. Before programming solvers, you need to encode data structures that describe the subject area. Program I / O. To test File and optimize. While one group is engaged in these tasks, the rest are thinking about algorithms.
Visualize. Origami were described by numbers, but we wanted to look at them, so we immediately took up the visualizer. In each ICFPC, you need to do some kind of visualizer or visual debugger. Here is our:
And this is how the visualization in the Unagi winning team solver looks like:
Invest in infrastructure. As soon as the initial chaos and haste end, automate routine tasks. We made automatic downloading of new problems. We put the solved origami in Git so that they are available to the whole team. In other ICFPCs, they wrote a system for testing the final quality of the solution, in order to experiment and understand whether our refinements are useful or harmful.
Test it. It's easy to get a lot of code. Harder to get it to work correctly. There are always bugs, so be sure to write tests, especially to the low-level code used by the whole team. If you do not write tests, then two out of three days will be spent on debugging. We passed this lesson many times. However, it is easy to talk about tests, it is more difficult in the heat of competition not to score on them.
Divide by two. 12 people turn into 6 if they work in pairs. A couple gives a better solution. A couple can split up at any time, with each participant being well versed in the general code. For example, you can start to make a visualizer in a pair, lay the right architecture, and then plan the features and go to separate them in parallel. More in a couple more fun to code, but this is not accurate.
Avoid merge conflicts. The story in the repository of a large team turns branching. With any inaccurate movement occur merge-conflicts that spoil the nerves and take time. Therefore, the skill of respect for change history is very useful on the ICFPC. Agree on the design of the code, add the file with the IDE settings in the repository, use auto-formatting.
Gather a dream team. The task is not known in advance, it will need to be decomposed "on the fly." Therefore, ICFPC is useful for people who are able to quickly navigate the environment, generate ideas and sell them to other team members, invest their strengths in the most useful task, read a bunch of other people's code and not break it with their own edits.
Organize a science department. A part of the team can read scientific articles, search for ready-made tools, decipher prompts from organizers and other participants. Like any science, it does not give instant exhaust. But last year we thus found a couple of useful thoughts.
Do not forget to sleep. A 72-hour marathon is waiting for you, and fresh heads will be worth its weight in gold.
This year there are 14 people in our team [for now]. We will try to follow all our tips and show the best game.
During the competition we will try to write something interesting in our channel in Telegram. Subscribe and support us.
t.me/KonturTech
Real Jedi can't just watch, right? Moreover, playing ICFPC is interesting and exciting, regardless of the final result. So gather a team and participate. And may the force be with you :)
I'll tell you why you can not miss ICFPC and give a series of tips. Free up the next weekend, gather a team and take part!
Competition for thoughtful hackers
ICFPC - team competition. Competitions for singles are many: for example, Facebook Hacker Cup and Google Code Jam . If you like AI for games, then codingame.com has great challenges every 2-3 months. In single competitions, the top is usually crammed with some kind of geniuses, and in team ones you can perform well due to persistence and good organization.
')
A team can be any size. Usually tasks on ICFPC can be solved in several ways. Trying all the ways and choosing the best is a big job. In 2011, I played in a team of two people. We had no lack of ideas, but we acutely felt a lack of hands.
Competition for thoughtful. The competition lasts for three days, so you do not need to be fast, like an olympiad programmer. There is time to think about the task, to understand and implement any algorithm.
Tasks are not banal. The organizer of the competition changes every year. This is usually a university, so they add reference to computer science to problems and classics (for example, in 2014 there was a reference to SECD machines ). In addition, ICFPC is dedicated to the ICFP functional programming research conference, and this affects the objectives. Once you have to read the descriptions on the functional pseudo-language (do not be afraid, understandable for the average man!), And then program the virtual machines and compilers.
One problem! For 72 hours, a team of unlimited size should solve only one task. But multifaceted and difficult. It cannot be solved optimally, but it can be solved better than other teams. The most unusual and bright tasks are the tasks of 2006 and 2007, in which virtual machines inside virtual machines and also reverse engineering of virtual machines ruled the show.
I have an anniversary)
I, xoposhiy , participated in the ICFPC 9 times. And every time there was something new:
- in 2007 there was a task to edit the alien DNA and the data structure of the rope string ,
- in 2009 - putting satellites into orbit using the program for a virtual machine simulator,
- in 2010 - a similar task about cars and fuel,
- in 2011 - Lambda the Gathering card game about SKI-combinators,
- in 2012 - a bot for Boulder Dash with requirements changing during the game,
- in 2013 - the selection of the arithmetic function for examples of inputs and outputs,
- in 2014 - Pac-Man bots on two virtual machines,
- in 2015 - hexagonal tetris with spells,
- in 2016 - solving and compiling difficult origami.
In recent years, our team consistently ranks in the top ten:
- in 2016 - 6th place
- in 2015 - 7th and 13th place (there were two teams)
- in 2014 - 7th place
- in 2013 - 3 place
- in 2012 - 13th place
- in 2011 - did not reach the final round,
- in 2010 - 22 place.
Interestingly, the third place in 2013 was won by a team of 8 people. And last year the team took the 6th place from as many as 12 people. Here, a normal person should be surprised how we are capable of such a crowd for three days working productively on just one task? I'm telling!
How do we fight the mythical man month
Frederick Brooks Act: "If the project does not fit the deadline, then adding labor will delay it even more"
I'll tell you on the example of the problem from last year's ICFPC 2016.
Given the silhouette of a flat origami, assembled from a square sheet of paper 1 × 1. You need to restore the origami scan, that is, mark the lines of the folds on the sheet and describe for each vertex on the scan where it goes to the silhouette. In the beginning there are 100 silhouettes from the organizers. In 24 hours, the participants will be able to submit their tasks for rivals.
How to solve?
Use task duality. Need to solve origami. And you need to come up with origami, which rivals cannot solve. This is the first opportunity for parallel work. Dual tasks are common in ICFPC. In 2010 and 2014 there were similar tasks.
Solve problems in different ways. We immediately came up with two ways to solve origami: collect a 1 × 1 square from the polygons visible on the silhouette, and vice versa, extend the silhouette so that it turns out to be 1 × 1 square. It was not clear which of these methods is better, so we split up and started making them in parallel.
Then he noticed that a lot of silhouettes - bulging figures. And they are solved trivially - by bending the edges of the square. Therefore, we wrote another convex origami solver.
Then we noticed some difficult tasks from the WILD BASHKORT MAGES team (hello, ripatti ) that would bring a lot of points, and wrote a solver for them. (In the end, we learned that MAGES also wrote a specialized solver for our origami)
Then we wrote a visual solver, which helped to cope with several dozens of origami manually. As a result, we had 5 different solvers for one problem.
In 2013, we also took the third place due to the fact that we had two different solvers for different types of problems. In ICFPC, specialization and duplication of solutions help.
Start with an auxiliary code. Before programming solvers, you need to encode data structures that describe the subject area. Program I / O. To test File and optimize. While one group is engaged in these tasks, the rest are thinking about algorithms.
Visualize. Origami were described by numbers, but we wanted to look at them, so we immediately took up the visualizer. In each ICFPC, you need to do some kind of visualizer or visual debugger. Here is our:
And this is how the visualization in the Unagi winning team solver looks like:
Invest in infrastructure. As soon as the initial chaos and haste end, automate routine tasks. We made automatic downloading of new problems. We put the solved origami in Git so that they are available to the whole team. In other ICFPCs, they wrote a system for testing the final quality of the solution, in order to experiment and understand whether our refinements are useful or harmful.
Test it. It's easy to get a lot of code. Harder to get it to work correctly. There are always bugs, so be sure to write tests, especially to the low-level code used by the whole team. If you do not write tests, then two out of three days will be spent on debugging. We passed this lesson many times. However, it is easy to talk about tests, it is more difficult in the heat of competition not to score on them.
Divide by two. 12 people turn into 6 if they work in pairs. A couple gives a better solution. A couple can split up at any time, with each participant being well versed in the general code. For example, you can start to make a visualizer in a pair, lay the right architecture, and then plan the features and go to separate them in parallel. More in a couple more fun to code, but this is not accurate.
Avoid merge conflicts. The story in the repository of a large team turns branching. With any inaccurate movement occur merge-conflicts that spoil the nerves and take time. Therefore, the skill of respect for change history is very useful on the ICFPC. Agree on the design of the code, add the file with the IDE settings in the repository, use auto-formatting.
Gather a dream team. The task is not known in advance, it will need to be decomposed "on the fly." Therefore, ICFPC is useful for people who are able to quickly navigate the environment, generate ideas and sell them to other team members, invest their strengths in the most useful task, read a bunch of other people's code and not break it with their own edits.
Organize a science department. A part of the team can read scientific articles, search for ready-made tools, decipher prompts from organizers and other participants. Like any science, it does not give instant exhaust. But last year we thus found a couple of useful thoughts.
Do not forget to sleep. A 72-hour marathon is waiting for you, and fresh heads will be worth its weight in gold.
Team kontur.ru
This year there are 14 people in our team [for now]. We will try to follow all our tips and show the best game.
During the competition we will try to write something interesting in our channel in Telegram. Subscribe and support us.
t.me/KonturTech
Real Jedi can't just watch, right? Moreover, playing ICFPC is interesting and exciting, regardless of the final result. So gather a team and participate. And may the force be with you :)
- Competition site (there is traditionally a minimum of information before the start!)
- Twitter organizers
Source: https://habr.com/ru/post/334324/
All Articles