July 28, 2017 at 14:02ICFP Contest 2017 - Strength Test for Real Developers
ICFPC is an annual competition for programmers. It takes place online and lasts 72 hours. ICFPC 2017 will begin on Friday August 4 at 12:00 (UTC) and end on Monday.
I will tell you why ICFPC should not be missed and give a series of tips. Free the next weekend, gather a team and participate!
ICFPC - team competition. There are many competitions for singles: for example, Facebook Hacker Cup and Google Code Jam . If you like AI for games, then codingame.com holds great challenges once every 2-3 months. In singles competitions, the top is usually clogged by some geniuses, and in teams you can perform well due to perseverance and good organization.
The team can be of any size. Typically, ICFPC tasks can be accomplished 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 the lack of hands.
Competition for the thoughtful.The competition lasts three days, so you do not need to be as fast as the Olympiad programmer. There is time to think about the task, understand and implement any algorithm.
Tasks are not trivial. The organizer of the competition changes every year. Usually this is a university, so they add references to scientific problems and the classics of computer science to tasks (say, in 2014, there was a reference to SECD machines ). In addition, ICFPC is dedicated to the scientific conference on functional programming of ICFP , and this affects the tasks. Once you have to read the descriptions in a functional pseudo-language (do not be afraid, understandable for the layman!), And then program the virtual machines and compilers.
There is one task!In 72 hours a team of unlimited size should solve only one problem. But multifaceted and difficult. It cannot be solved optimally, but it can be solved better than other teams. The most unusual and striking tasks are those of 2006 and 2007, in which virtual machines inside virtual machines ruled the ball and also reverse engineering of virtual machines.
I, xoposhiy , participated in the ICFPC 9 times. And every time there was something new:
In recent years, our team has been consistently ranked in the top ten:
Interestingly, the third place in 2013 was won by a team of 8 people. And last year, the 6th place was taken by a team of as many as 12 people. Here a normal person should be surprised how we are capable of such a crowd of three days to work productively on just one task? I tell you!
Frederick Brooks law: “If the project does not meet the deadlines, the addition of labor will delay it even more”.
I will tell you about the problem from last year’s ICFPC 2016. The
silhouette of a flat origami assembled from a square sheet of 1 × 1 paper is given. It is necessary to restore the origami scan, that is, mark the fold lines on the sheet and describe for each vertex on the scan where it goes on the silhouette. At the beginning there are 100 silhouettes from the organizers. In a day, participants will be able to submit their tasks for rivals.
How to decide?
Use the duality of the task. You have to decide origami. And you also need to come up with origami that rivals will not be able to solve. This is the first opportunity for parallel work. Dual tasks are common at ICFPC. In 2010 and 2014 there were similar tasks.
Solve problems in different ways. We immediately came up with two ways to solve origami: to collect a 1 × 1 square from the polygons visible on the silhouette, and vice versa, to expand the silhouette so that a 1 × 1 square is obtained. It was not clear which of these methods is better, so we split up and started doing them in parallel.
Then they noticed that many silhouettes are convex figures. But they are solved trivially - by bending the edges of the square. Therefore, we wrote another solver for convex origami.
Then we noticed some difficult tasks from the team WILD BASHKORT MAGES (hello, ripatti ), which 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 that helped to cope with dozens of origami manually. As a result, we had 5 different solvers for one problem.
In 2013, we also took third place due to the fact that we had two different solvers for different types of tasks. At ICFPC, specialization and duplication of solutions help.
Start with the helper code. Before programming solvers, you need to encode data structures that describe the subject area. Program I / O. To test. Profile 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's ours:
And this is how the visualization in the solver of the Unagi winning team looks like:
Invest in infrastructure. Once the initial chaos and rush is over, automate routine tasks. We made automatic downloading of new tasks. They put together the decided 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 a solution in order to experiment and understand whether our improvements are useful or harmful.
Test it out. It's easy to add a lot of code. It is harder to get it to work correctly. There are always errors, so be sure to write tests, especially for the low-level code that the whole team uses. If you do not write tests, then two out of three days will be spent on debugging. We have gone through this lesson many times. However, talking about tests is easy, more difficult in the heat of competition is 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, and each participant will be well versed in the common code. For example, you can start making a visualizer in a couple, lay the right architecture, and then plan features and disperse to do them in parallel. Even a couple more fun to code, but that's not accurate.
Avoid merge conflicts. The story in the repository of a large team turns out to be branchy. With any inaccurate movement, merge conflicts occur that spoil the nerves and take time. Therefore, taking care of change history is very useful at ICFPC. Agree on the design of the code, add the IDE settings file to the repository, use autoformatting.
Assemble a dream team.The task is not known in advance; it will need to be decomposed on the fly. Therefore, people who can quickly navigate the situation, generate ideas and sell them to other team members, invest in the most useful task, read a bunch of other people's code and not break it with their own edits are useful at ICFPC.
Organize a science department. Part of the team can read scientific articles, look for ready-made tools, decode clues 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 awaits you, and fresh heads will be worth its weight in gold.
This year, our team [so far] has 14 people. We will try to follow all our tips and show the best game.
During the competition, we will try to write interesting in our channel in Telegram. Subscribe and cheer for us.
t.me/KonturTech
Real Jedi can't just watch, right? Moreover, playing ICFPC is interesting and exciting, regardless of the final result. So put together a team and get involved. And may the force be with you :)
I will tell you why ICFPC should not be missed and give a series of tips. Free the next weekend, gather a team and participate!
Competition for thoughtful hackers
ICFPC - team competition. There are many competitions for singles: for example, Facebook Hacker Cup and Google Code Jam . If you like AI for games, then codingame.com holds great challenges once every 2-3 months. In singles competitions, the top is usually clogged by some geniuses, and in teams you can perform well due to perseverance and good organization.
The team can be of any size. Typically, ICFPC tasks can be accomplished 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 the lack of hands.
Competition for the thoughtful.The competition lasts three days, so you do not need to be as fast as the Olympiad programmer. There is time to think about the task, understand and implement any algorithm.
Tasks are not trivial. The organizer of the competition changes every year. Usually this is a university, so they add references to scientific problems and the classics of computer science to tasks (say, in 2014, there was a reference to SECD machines ). In addition, ICFPC is dedicated to the scientific conference on functional programming of ICFP , and this affects the tasks. Once you have to read the descriptions in a functional pseudo-language (do not be afraid, understandable for the layman!), And then program the virtual machines and compilers.
There is one task!In 72 hours a team of unlimited size should solve only one problem. But multifaceted and difficult. It cannot be solved optimally, but it can be solved better than other teams. The most unusual and striking tasks are those of 2006 and 2007, in which virtual machines inside virtual machines ruled the ball and also reverse engineering of virtual machines.
I have an anniversary)
I, xoposhiy , participated in the ICFPC 9 times. And every time there was something new:
- in 2007 there was the task of editing the alien DNA and the rope string data structure ,
- in 2009 - launching satellites into orbit using a program for a virtual machine simulator,
- in 2010 - a completely different task about cars and fuel,
- in 2011 - the card game Lambda the Gathering about SKI-combinators,
- in 2012 - a bot for Boulder Dash with changing requirements during the game,
- in 2013 - selection of arithmetic functions by examples of inputs and outputs,
- in 2014 - bots for Pac-Man on two virtual machines,
- in 2015 - hexagonal tetris with spells,
- in 2016 - solving and compiling difficult origami.
In recent years, our team has been consistently ranked in the top ten:
- in 2016 - 6th place,
- in 2015 - 7th and 13th place (there were two teams),
- in 2014 - 7th place,
- in 2013 - 3rd place,
- in 2012 - 13th place,
- in 2011 - did not reach the final round,
- in 2010 - 22nd place.
Interestingly, the third place in 2013 was won by a team of 8 people. And last year, the 6th place was taken by a team of as many as 12 people. Here a normal person should be surprised how we are capable of such a crowd of three days to work productively on just one task? I tell you!
How We Fight Mythical Man-Month
Frederick Brooks law: “If the project does not meet the deadlines, the addition of labor will delay it even more”.
I will tell you about the problem from last year’s ICFPC 2016. The
silhouette of a flat origami assembled from a square sheet of 1 × 1 paper is given. It is necessary to restore the origami scan, that is, mark the fold lines on the sheet and describe for each vertex on the scan where it goes on the silhouette. At the beginning there are 100 silhouettes from the organizers. In a day, participants will be able to submit their tasks for rivals.
How to decide?
Use the duality of the task. You have to decide origami. And you also need to come up with origami that rivals will not be able to solve. This is the first opportunity for parallel work. Dual tasks are common at ICFPC. In 2010 and 2014 there were similar tasks.
Solve problems in different ways. We immediately came up with two ways to solve origami: to collect a 1 × 1 square from the polygons visible on the silhouette, and vice versa, to expand the silhouette so that a 1 × 1 square is obtained. It was not clear which of these methods is better, so we split up and started doing them in parallel.
Then they noticed that many silhouettes are convex figures. But they are solved trivially - by bending the edges of the square. Therefore, we wrote another solver for convex origami.
Then we noticed some difficult tasks from the team WILD BASHKORT MAGES (hello, ripatti ), which 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 that helped to cope with dozens of origami manually. As a result, we had 5 different solvers for one problem.
In 2013, we also took third place due to the fact that we had two different solvers for different types of tasks. At ICFPC, specialization and duplication of solutions help.
Start with the helper code. Before programming solvers, you need to encode data structures that describe the subject area. Program I / O. To test. Profile 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's ours:
And this is how the visualization in the solver of the Unagi winning team looks like:
Invest in infrastructure. Once the initial chaos and rush is over, automate routine tasks. We made automatic downloading of new tasks. They put together the decided 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 a solution in order to experiment and understand whether our improvements are useful or harmful.
Test it out. It's easy to add a lot of code. It is harder to get it to work correctly. There are always errors, so be sure to write tests, especially for the low-level code that the whole team uses. If you do not write tests, then two out of three days will be spent on debugging. We have gone through this lesson many times. However, talking about tests is easy, more difficult in the heat of competition is 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, and each participant will be well versed in the common code. For example, you can start making a visualizer in a couple, lay the right architecture, and then plan features and disperse to do them in parallel. Even a couple more fun to code, but that's not accurate.
Avoid merge conflicts. The story in the repository of a large team turns out to be branchy. With any inaccurate movement, merge conflicts occur that spoil the nerves and take time. Therefore, taking care of change history is very useful at ICFPC. Agree on the design of the code, add the IDE settings file to the repository, use autoformatting.
Assemble a dream team.The task is not known in advance; it will need to be decomposed on the fly. Therefore, people who can quickly navigate the situation, generate ideas and sell them to other team members, invest in the most useful task, read a bunch of other people's code and not break it with their own edits are useful at ICFPC.
Organize a science department. Part of the team can read scientific articles, look for ready-made tools, decode clues 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 awaits you, and fresh heads will be worth its weight in gold.
Kontur.ru team
This year, our team [so far] has 14 people. We will try to follow all our tips and show the best game.
During the competition, we will try to write interesting in our channel in Telegram. Subscribe and cheer for us.
t.me/KonturTech
Real Jedi can't just watch, right? Moreover, playing ICFPC is interesting and exciting, regardless of the final result. So put together a team and get involved. And may the force be with you :)
- Competition site (there is traditionally a minimum of information before the start!)
- Organizers twitter