Tile Polygons with Dominoes

Submit

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 _

Python _

Language Ranking_

return to the top page