Tile Polygons with Dominoes

Submit

Your name:
File:
Open code-statistics:

Language is selected by the extension of the file. See the list of supported languages to know the extension of your language.

Problem

Draw tilings of simple polygons with dominoes, in particular the maximal height tilings as defined by William P. Thurston in his paper "Conway's Tiling Groups".

Side lengths are given starting from the bottom left corner and proceeding clockwise. Negative numbers indicate left (counterclockwise) turns. The bottom left cell is colored white.

Brief description of algorithm: The region is colored black and white as on a chessboard. Define the direction of edges on the lattice as being clockwise around white cells. Define a height function such that for an edge (u,v) we have h(v) = h(u) + 1 if the edge lies on the boundary of a domino, otherwise h(v) = h(u) - 3. Arbitrarily assign a height to a vertex on the boundary, which determines all other boundary heights. Then for each height k starting with the lowest and working up, for all edges (u,v) such that v is unlabelled and h(u) = k, set h(v) = k + 1, until all vertices are labelled.

-- mitchs

Options

exec is denied

no deadline, the server will not save your submission

Sample input:_

4 8 4 8
1 6 1 6
8 8 8 8
1 2 1 2
2 1 2 1
2 8 2 8
6 2 6 2
4 3 4 3
4 7 4 7
1 -1 1 -1 1 -1 1 -1 2 1 -1 1 -1 1 -1 1 -1 2 1 -1 1 -1 1 -1 1 -1 2 1 -1 1 -1 1 -1 1 -1 2
1 1 -2 -1 3 2 2 -2 -2 2 2 -2 -5 1 5 -2 -5 3 1 2 -1 -2 1 2 -3 10 -3 2
1 -2 7 8 8 6
2 -1 6 8 8 7
1 7 -7 -6 -5 -4 -3 -2 -1 -1 1 2 3 4 5 6 7 8 9 8
9 8 7 6 5 4 3 2 1 1 -1 -2 -3 -4 -5 -6 -7 -7 1 8

Sample output:

 _______________________________
|       |       |       |       |
|_______|_______|_______|_______|
|   |       |       |       |   |
|   |_______|_______|_______|   |
|   |       |       |       |   |
|___|_______|_______|_______|___|
|       |       |       |       |
|_______|_______|_______|_______|

 _______________________
|       |       |       |
|_______|_______|_______|

 _______________________________
|       |       |       |       |
|_______|_______|_______|_______|
|   |       |       |       |   |
|   |_______|_______|_______|   |
|   |   |       |       |   |   |
|___|   |_______|_______|   |___|
|   |   |   |       |   |   |   |
|   |___|   |_______|   |___|   |
|   |   |   |       |   |   |   |
|___|   |___|_______|___|   |___|
|   |   |       |       |   |   |
|   |___|_______|_______|___|   |
|   |       |       |       |   |
|___|_______|_______|_______|___|
|       |       |       |       |
|_______|_______|_______|_______|

 _______
|       |
|_______|

 ___
|   |
|   |
|   |
|___|

 _______________________________
|       |       |       |       |
|_______|_______|_______|_______|
|       |       |       |       |
|_______|_______|_______|_______|

 _______
|       |
|_______|
|   |   |
|   |   |
|   |   |
|___|___|
|   |   |
|   |   |
|   |   |
|___|___|
|       |
|_______|

 ___________
|       |   |
|_______|   |
|   |   |   |
|   |   |___|
|   |   |   |
|___|___|   |
|       |   |
|_______|___|

 ___________________________
|       |       |       |   |
|_______|_______|_______|   |
|   |       |       |   |   |
|   |_______|_______|   |___|
|   |       |       |   |   |
|___|_______|_______|___|   |
|       |       |       |   |
|_______|_______|_______|___|

                 _______
                |       |
             ___|_______|___
            |       |       |
         ___|_______|_______|___
        |       |       |       |
     ___|_______|_______|_______|___
    |       |       |       |       |
 ___|_______|_______|_______|_______|___
|       |       |       |       |       |
|_______|_______|_______|_______|_______|
|       |       |       |       |       |
|_______|_______|_______|_______|_______|
    |       |       |       |       |
    |_______|_______|_______|_______|
        |       |       |       |
        |_______|_______|_______|
            |       |       |
            |_______|_______|
                |       |
                |_______|

                                 ___         ___________
                                |   |       |   |       |
                                |   |       |   |_______|
                                |   |       |   |
                                |___|       |___|_______
                                |   |       |   |       |
 _______         _______        |   |       |   |_______|
|       |       |       |       |   |       |   |
|_______|       |_______|       |___|       |___|
|   |   |       |   |   |       |   |       |   |
|   |   |_______|   |   |_______|   |_______|   |
|   |   |       |   |   |       |   |       |   |
|___|___|_______|___|___|_______|___|_______|___|
    |   |
    |   |
    |   |
 ___|___|
|       |
|_______|

 _______________________________
|       |       |       |       |
|_______|_______|_______|_______|
|   |       |       |       |   |
|   |_______|_______|_______|   |
|   |   |       |       |   |   |
|___|   |_______|_______|   |___|
|   |   |   |       |   |   |   |
|   |___|   |_______|   |___|   |
|   |   |   |       |   |   |   |
|___|   |___|_______|___|   |___|
|   |   |       |       |   |   |
|   |___|_______|_______|___|   |
|   |       |       |       |   |
|___|_______|_______|_______|___|
        |       |       |       |
        |_______|_______|_______|

 _______________________________
|   |       |       |       |   |
|   |_______|_______|_______|   |
|   |   |       |       |   |   |
|___|   |_______|_______|   |___|
|   |   |   |       |   |   |   |
|   |___|   |_______|   |___|   |
|   |   |   |   |   |   |   |   |
|___|   |___|   |   |___|   |___|
|   |   |   |   |   |   |   |   |
|   |___|   |___|___|   |___|   |
|   |   |   |       |   |   |   |
|___|   |___|_______|___|   |___|
    |   |       |       |   |   |
    |___|_______|_______|___|   |
    |       |       |       |   |
    |_______|_______|_______|___|

 _______________________________
|   |       |       |       |   |
|   |_______|_______|_______|   |
|   |                       |   |
|___|    _______________    |___|
|   |   |   |       |   |   |   |
|   |   |   |_______|   |   |   |
|   |   |   |       |   |   |   |
|___|   |___|___    |___|   |___|
|   |   |       |   |   |   |   |
|   |   |_______|   |   |   |   |
|   |               |   |   |   |
|___|_______________|___|   |___|
|       |       |       |   |   |
|_______|_______|_______|   |   |
                            |   |
 ___________________________|___|
|       |       |       |       |
|_______|_______|_______|_______|

 _______________________________
|   |       |       |       |   |
|   |_______|_______|_______|   |
|   |                       |   |
|___|    _______________    |___|
|   |   |   |       |   |   |   |
|   |   |   |_______|   |   |   |
|   |   |   |       |   |   |   |
|___|   |___|    ___|___|   |___|
|   |   |   |   |       |   |   |
|   |   |   |   |_______|   |   |
|   |   |   |               |   |
|___|   |___|_______________|___|
|   |   |       |       |       |
|   |   |_______|_______|_______|
|   |
|___|___________________________
|       |       |       |       |
|_______|_______|_______|_______|

Sample input:_

1 1 -2 -1 -1 2 1 1 -1 1 -1 -1 1 -2 -2 1 2 -2 1 1 -1 -2 1 3 2 -4 1 -1 -1 2 2 1 -1 -3 1 -1 2 2 2 -2 -3 2
1 2 -1 1 2 3
4 -3 5 2 -2 -1 -1 2 -2 1 2 -2 1 2 -1 -1 1 2 1 -2 -2 -3 2 1 1 -1 -2 2 2 -1 -1 1 1 -2 1 -2 2 -1 1 2 2 -1 -2 1 2 -1 -1 1 -1 -1 1 -2 1 1 -2 2 -1 -3 -2 2 3 4 -1 -1 2 -1 1 2 -1 1
2 1 -3 -1 -1 1 -1 2 1 1 -1 -2 -1 1 -1 -1 2 2 2 -1 1 1 -2 1 -1 2 1 -3 -1 -1 3 2 -1 1 2 -1 2 1 -2 -2 2 1 -2 2 -1 1
1 1 -2 -1 -1 2 1 1 -1 1 -1 -1 1 -2 -2 1 2 -2 1 1 -1 -2 1 3 2 -4 1 -1 -1 2 2 1 -1 -3 1 -1 2 2 2 -2 -3 2
1 -2 1 -2 3 1 -2 -1 -1 1 -2 1 -2 1 4 -1 1 -2 -1 1 2 1 -1 1 -3 1 -1 1 2 -2 -2 -1 1 2 5 2 -1 -3 -1 1 -1 -1 5 2 1 1 -2 -1 -1 1 1 -2 1 -1 2 2 -1 3 -1 -5 1 -1 2 1 1 -1 -1 1 -4 1

Sample output:

 ___________
|       |   |
|_______|   |
        |   |
     ___|___|_______________     _______
    |       |       |       |   |       |
    |_______|_______|_______|___|_______|
            |   |       |       |       |
            |   |       |_______|_______|
            |   |           |       |
            |___|        ___|_______|___________
                        |       |       |       |
                     ___|_______|_______|_______|___
                    |       |   |   |       |   |   |
                    |_______|   |   |       |   |   |
                                |   |       |   |   |
                             ___|___|       |___|___|
                            |       |
                            |_______|

         ___
        |   |
 _______|   |
|       |   |
|_______|___|

                 _______
                |       |
         ___    |_______|    ___
        |   |   |       |   |   |
        |   |___|_______|___|   |_______
        |   |       |   |   |   |       |
        |___|_______|   |   |___|_______|_______
                    |   |   |       |       |   |
     _______        |___|___|_______|_______|   |
    |       |       |   |       |   |   |   |   |
    |_______|_______|   |_______|   |   |   |___|___
        |   |       |   |   |       |   |   |       |
 _______|   |_______|___|   |___    |___|   |_______|
|       |   |       |   |   |   |
|_______|___|_______|   |___|   |_______
        |   |           |   |   |       |
        |   |    _______|   |___|_______|
        |   |   |       |   |   |   |
        |___|   |_______|___|   |   |    _______
                |   |       |   |   |   |   |   |
                |   |_______|___|___|   |   |   |
                |   |   |   |           |   |   |
                |___|   |   |___________|___|___|
                |   |   |   |   |       |       |
                |   |___|___|   |_______|_______|
                |   |       |   |
                |___|_______|___|___
                            |       |
                            |_______|
                            |       |
                            |_______|___
                            |   |       |
                            |   |_______|
                            |   |
                            |___|

                                 ___
                                |   |
                         _______|   |
                        |   |   |   |
                        |   |   |___|___
                        |   |   |       |
                        |___|___|_______|
                        |       |       |
         _______        |_______|_______|
        |       |           |   |   |
     ___|_______|___________|   |   |
    |       |       |       |   |   |
    |_______|_______|_______|___|___|_______
    |       |       |       |   |       |   |
 ___|_______|    ___|_______|   |_______|   |
|       |       |       |       |   |   |   |
|_______|___    |_______|       |   |   |___|
    |   |   |                   |   |   |
    |   |   |                ___|___|___|
    |   |   |               |   |       |
    |___|___|               |   |_______|
                            |   |
                            |___|

 ___________
|       |   |
|_______|   |
        |   |
     ___|___|_______________     _______
    |       |       |       |   |       |
    |_______|_______|_______|___|_______|
            |   |       |       |       |
            |   |       |_______|_______|
            |   |           |       |
            |___|        ___|_______|___________
                        |       |       |       |
                     ___|_______|_______|_______|___
                    |       |   |   |       |   |   |
                    |_______|   |   |       |   |   |
                                |   |       |   |   |
                             ___|___|       |___|___|
                            |       |
                            |_______|

                                 _______
                                |       |
                     _______    |_______|
                    |       |   |   |
             ___    |_______|   |   |    ___
            |   |       |   |   |   |   |   |
         ___|   |       |   |   |___|___|   |_______
        |   |   |       |   |   |   |   |   |       |
        |   |___|_______|___|   |   |   |___|_______|___
        |   |   |       |   |   |   |   |       |       |
        |___|   |_______|   |   |___|___|_______|_______|
        |   |   |       |   |       |       |   |       |
     ___|   |___|_______|___|    ___|_______|   |_______|
    |   |   |       |           |   |       |   |
 ___|   |___|_______|___________|   |_______|___|
|   |   |       |       |       |   |
|   |___|_______|_______|_______|___|___________________
|   |       |       |       |   |       |       |       |
|___|       |_______|_______|   |_______|_______|_______|___
                |   |   |       |   |   |       |       |   |
                |   |   |    ___|   |   |_______|_______|   |
                |   |   |   |   |   |   |   |       |   |   |
                |___|___|   |   |___|___|   |_______|   |___|
                |   |       |   |       |   |   |
                |   |       |___|_______|___|   |
                |   |       |       |   |   |   |
                |___|       |_______|   |   |___|
                                    |   |   |   |
                                    |___|___|   |
                                            |   |
                                            |___|

Ranking

Perl _

RankUserSizeTimeDateStatistics
1tails4350.76432015/05/28 18:13:120B / 142B / 286B

Python _

RankUserSizeTimeDateStatistics
1mitchs5541.92202016/02/01 09:04:150B / 249B / 277B
2rolf11550.31962015/05/27 03:26:280B / 514B / 435B

Language Ranking_

RankLangUserSizeScore
1Perltails43510000
2Pythonmitchs5547851

return top