20
3
Background
Consider a (closed) chain of rods, each of which has integer length. How many distinct hole-free polyominoes can you form with a given chain? Or in other words, how many different non-self-intersecting polygons with axis-aligned sides can you form with a given chain?
Let's look at an example. Consider a particular chain consisting of 8 rods of length 1 and 2, which we can represent as [1, 1, 2, 2, 1, 1, 2, 2]
. Up to rotations and translations, there are only 8 possible polyominoes (we do count different reflections):
This first rod is dark blue, and then we traverse the polygon in a counter-clockwise sense.
The sense of rotation doesn't affect the result in the above example. But let's consider another chain, [3, 1, 1, 1, 2, 1, 1]
, which yields the following 3 polyominoes:
Notice that we do not include a reflection of the last polyomino, because it would require clockwise traversal.
If we had a more flexible chain of the same length, [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
, we would actually be able to form both reflections among some other polyoninoes, totalling 9:
The Challenge
Given a description of a chain, as an array or similar, determine the number of distinct polyominoes you can form (up to rotations and translations) by using the rods in order while going around the perimeter in a counter-clockwise sense.
Please write a full program and include commands to compile (if applicable) and run your code from the command line. Please also include a link to a free compiler/interpreter for your language.
Your program should read the input from STDIN. The first line will contain an integer M. The next M lines will be test cases, each of which will be a space-separated list of rod lengths. Your program should print M lines to STDOUT, each of which consists of a single integer - the number of distinct polyominoes that can be formed.
You must only use a single thread.
Your program must not use more than 1 GB of memory at any time. (This is not a completely strict limit, but I will monitor your executable's memory usage, and kill any process that consistently uses more than 1 GB, or spikes significantly above it.)
To prevent excessive amounts of pre-computation, your code must not be longer than 20,000 bytes, and you must not read any files.
You must also not optimise towards the specific test cases chosen (e.g. by hardcoding their results). If I suspect that you do, I reserve the right to generate new benchmark sets. The test sets are random, so your program's performance on those should be representative for its performance on arbitrary input. The only assumption you're allowed to make is that the sum of the rod lengths is even.
Scoring
I have provided benchmark sets for chains of N = 10, 11, ..., 20 rods. Each test set contains 50 random chains with lengths between 1 and 4 inclusive.
Your primary score is the largest N for which your program completes the entire test set within 5 minutes (on my machine, under Windows 8). The tie breaker will be the actual time taken by your program on that test set.
If anyone beats the largest test set, I will keep adding larger ones.
Test Cases
You can use the following test cases to check the correctness of your implementation.
Input Output
1 1 0
1 1 1 1 1
1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 3
1 1 1 1 1 1 1 1 1 1 9
1 1 1 1 1 1 1 1 1 1 1 1 36
1 1 1 1 1 1 1 1 1 1 1 1 1 1 157
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 758
1 1 2 2 1 1 2 2 8
1 1 2 2 1 1 2 2 1 1 23
1 1 2 2 1 1 2 2 1 1 2 2 69
1 2 1 2 1 2 1 2 3
1 2 1 2 1 2 1 2 1 2 1 2 37
1 2 3 2 1 2 3 2 5
1 2 3 2 1 2 3 2 1 2 3 2 23
3 1 1 1 2 1 1 3
1 2 3 4 5 6 7 1
1 2 3 4 5 6 7 8 3
1 2 3 4 5 6 7 8 9 10 11 5
2 1 5 3 3 2 3 3 4
4 1 6 5 6 3 1 4 2
3 5 3 5 1 4 1 1 3 5
1 4 3 2 2 5 5 4 6 4
4 1 3 2 1 2 3 3 1 4 18
1 1 1 1 1 2 3 3 2 1 24
3 1 4 1 2 2 1 1 2 4 1 2 107
2 4 2 4 2 2 3 4 2 4 2 3 114
You find an input file with these over here.
Leaderboard
User Language Max N Time taken (MM:SS:mmm)
1. feersum C++ 11 19 3:07:430
2. Sp3000 Python 3 18 2:30:181
1
@PeterKagey Did you post this comment on the wrong challenge? Looks like it should have gone on this one.
– Martin Ender – 2019-03-18T09:53:38.250"hole-free" seems superfluous. one contiguous chain can't produce hole'd polyominoes in the first place. – Sparr – 2014-12-04T22:48:46.710
Is multi-threading allowed? And if the threads are in different processes, does each one get to use 1 GB? :P – feersum – 2014-12-04T22:49:26.300
@Sparr It can when the perimeter touches itself at a corner. For instance, see No. 81 here. That one shouldn't be counted.
– Martin Ender – 2014-12-04T22:49:28.613@feersum For simplicity, I'm going to say no to multi-threading (and will edit the challenge). – Martin Ender – 2014-12-04T22:50:44.417
@MartinBüttner ahh, I mistook touching-at-a-corner as self-intersecting. – Sparr – 2014-12-04T22:52:53.777
@Sparr It's also self-intersecting, as far as the bounding polygon is concerned. The two definitions are supposed to be equivalent, and each was supposed to be valid on its own. I just wanted to provide two different viewpoints. – Martin Ender – 2014-12-04T22:53:35.630