JOIN
Get Time
forums   
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat (newest first)  | Threaded  | Tree
Previous Thread  |  Next Thread
Post your approach | Reply
It seems that the competition is over, but no one is posting their approach.

I didn't compete, because I couldn't find an effective method for creating loops. Although I did find a decent method for creating long paths. I used simulated annealing with local-level scoring. You get a point if there are two adjacent tiles whose paths match and colours differ. The task is to maximise the total number of points.

Anyway I am very interested in knowing people's approaches. It looks like a few people got almost perfect results, so I suspect that bipartite matching is involved somehow.


P.S. Happy New Year everyone!
Re: Post your approach (response to post by dimkadimon) | Reply
I was going to implement something Beam search-based, but ran out of development time and enthusiasm, so gave up. Also we have a new version release approaching at work.

The idea was to start with topmost row, fill a bunch of patterns into it that "look promising". Then, start building the next layers as usual (much like we did in MM94).

The biggest issue was to match current row (the one appended) to the previous one. Some sort of connecting between the tiles in the currently adding row and already placed tiles was needed. It was clear that a garland can have at most 2 open ends that appear in the current (last added) row. Actually all the other garlands are not interesting, because they are either already closed, or cannot be closed.

So the most interesting part was to join some garlands from the previous rows using some tiles from the current row.
Combined with some semi-greediness for the topmost 30-60% of the board, this approach could beat SA, but as usual I do not have a proof :).
Re: Post your approach (response to post by dimkadimon) | Reply
I haven't submitted either but had some ideas.
You can notice that in any valid solution number of tiles of type 0 equals to number of tiles of type 2. Same for 1 and 3. So if c[i] is the number of tiles of type i then there is obvious upper bound on optimal length:
2*min(c[0], c[2]) + 2*min(c[1], c[3]) + c[4] + c[5] - (c[4]+c[5]) % 2

I was impressed how quickly wleite produced a solution that was very close to this limit and thought the only way to be competitive in this match was to have "perfect" solution.

Maybe there is some nice mathematical construction but I was looking for solutions that would generate a chain of desired length and then try to modify parts of it until we end up using allowed number of tiles for each color/type. We can have scoring function based on how many extra tiles our current solution needs.

Probably the best idea I had there was to split the grid into subrectangles of size 5x5 (or similar) and connect them with a chain. After that you can modify how to traverse each individual subrectangle to improve scoring function. It didn't quite work and I haven't spent enough time to figure out why.
Re: Post your approach (response to post by nika) | Reply
Happy New Year!

My solution looks almost the same as nika's.

I split the field into 3x3 - 5x5 sub-rectangles. The number of sub-rectangles should be even, either vertically or horizontally in order to create a hamilton cycle easily.
https://twitter.com/nico_shindannin/status/946492445335830528

I calculated all the chain patterns for each sub-rectangle size beforehand. Then I used simulated annealing. These two were neighbors ,
(1) Randomly picked up a sub-rectangle and chose a different chain.
(2) Randomly picked up a border of sub-rectangles, moved a position where two chains are connected on the border.

Regarding color, if the number of colors was three or four, the color was trivial. You can use any algorithm to assign them. In the case of two colors, they were assigned to the black or white cell of the checkerboard and they must be the same number. I took it into account during simulated annealing.

Once I reached 976232.19, which seemed the optimal score as Milanin and sdya got. However, in my local test, I failed to reach the optimal, 4 out of 300 cases . So, I re-submitted my solution and my rank went down to the 3rd.

> 2*min(c[0], c[2]) + 2*min(c[1], c[3]) + c[4] + c[5] - (c[4]+c[5]) % 2

At first, I thought it was optimal length. However, I guess it would be length 2 shorter than the above length on the following cases ,
- min(c[0], c[2]) = even, min(c[1], c[3]) = even. c[4] = even. c[5] = odd.
- min(c[0], c[2]) = even, min(c[1], c[3]) = even. c[4] = odd. c[5] = even.
- min(c[0], c[2]) = odd, min(c[1], c[3]) = odd. c[4] = even. c[5] = even.
- min(c[0], c[2]) = odd, min(c[1], c[3]) = odd. c[4] = odd. c[5] = odd.

For example, c[0]=1, c[1]=1, c[2]=1, c[3]=1, c[4]=1, c[5]=1,
2*min(c[0], c[2]) + 2*min(c[1], c[3]) + c[4] + c[5] - (c[4]+c[5]) % 2 = 6
However, I can only create a cycle of length 4 at most. I don't know why, so I hope someone will prove it instead. :)

P.S.
I have just posted my solution for TCO 2017 Announcement Fun Round. I am sorry to late.
https://apps.topcoder.com/forums/?module=Thread&threadID=901996&start=0
RSS