PA5 - Tiling Dino

We would like to use dominoes (\(2\)-by-\(1\) rectangles) to tile a pixel-art image, such as the dinosaur above. Unfortunately, not every such image can be tiled with dominoes. Write an algorithm that takes as input a black-and-white pixel-art image (with \(r\) rows and \(c\) columns) and determines whether or not that image’s black pixels can be exactly tiled using \(2\)-by-\(1\) dominoes. The running time of your algorithm should be a polynomial in \(c\) and \(r\). (Hint: Think about max flow and how we could use that to solve this problem. How could we turn our input into an appropriate graph for max flow, such that finding a max flow will find a tiling?)

Details

Input

Your algorithm will be given (as input) a string representation of the image as a list of Strings, which represents a \(c \times r\) grid of characters defining the pixel art image you must cover. The first character in the first string will be the top-left pixel \((0,0)\) in the image. The last character in the last string will be the bottom-right pixel \((c-1, r-1)\) in the image. Each line will contain a string where each character is either a . or a #. Any cell with # is “black” and must be covered by a domino, any cell with a . is “white” and must not be.

Output

Your algorithm should determine whether the image can be tiled with dominoes. If it cannot be tiled, your algorithm should return the string impossible as the first string in its return array. However, if it can be tiled, your algorithm should return any one valid tiling as a list/array of strings each containing four space-separated integers. Each string represents the placement of a tile by giving the coordinates (column then row, i.e. \((x,y)\)) of the cells that domino will cover. Your dominoes may be listed in any order.

Runtime

Examples

For each of the examples below, we’ve included a text file in the zip file. The solutions are provided below.

Diamond

...#...
..###..
..###..
...#...

Tiling:

3 0 3 1
2 1 2 2
4 1 4 2
3 2 3 3

UVA ASCII Art 1

.#...#.#...#..#####.
.#...#.#...#..#...#.
.#...#.#...#..#...#.
.#...#.#...#..#####.
.#...#..#.#...#...#.
.#...#..###...#...#.
..###....#....#...#.

Tiling: impossible

UVA ASCII Art 2

.#...#.#...#..####..
.#...#.#...#..##.##.
.#...#.#...#..#...#.
.#...#.#...#..#.###.
.#...#..#.#...#...#.
.#####..###...#...#.
..###....#..........

Tiling:

1 0 1 1
5 0 5 1
7 0 7 1
11 0 11 1
15 0 15 1
17 0 16 0
14 1 14 0
18 1 17 1
1 2 1 3
5 2 5 3
7 2 7 3
11 2 11 3
14 3 14 2
16 3 17 3
18 3 18 2
1 4 1 5
5 4 5 5
2 5 2 6
4 5 4 6
8 5 8 4
10 5 10 4
14 5 14 4
18 5 18 4
3 6 3 5
9 6 9 5

Implementation

Your program should have the following properties:

• Your algorithm must be written in Python 3.10.6 or Java 19.0.2 (OpenJDK)
• You must download the appropriate wrapper code based on the language you choose: Main.py and TilingDino.py for Python, Main.java and TilingDino.java for Java.
  • Java package: pa5-java.zip
  • Python package: pa5-python.zip
• The compute() method in TilingDino receives as input the body of the input file as a list of strings. You must have compute() return the results described above.
• You may modify the Main files to test your algorithm, but they will not be used during grading.
• You must submit your TilingDino file to Gradescope. Do not submit Main.java, Main.py, or any test files.
• You may submit your code a maximum of 15 times to Gradescope. After the 15th submission, Gradescope will not run your code.
• A few other notes:
  • Your code will be run as:
    python3 Main.py for Python, or javac *.java && java Main for Java.
  • You may use the networkx package for Python or the JGraphT package for Java
    • Networkx: https://networkx.org/
      pip3 install networkx has v3.1 for python 3
    • JGraphT: https://jgrapht.org/
      We will use version 1.5.2
  • You may upload multiple files if you need additional classes for Java, but do not assign packages to the files.
  • You may write additional methods in the TilingDino class as needed to support your algorithm.
  • You may use any editor or IDE you prefer as long as the code can be executed as stated above.
  • We strongly encourage you to practice good development as you write code: use meaningful variable names, break your code into functions, “code a little then test a little”, use the debugger, etc.

Rules on Collaboration and Outside Sources

You may discuss the problem and the overall strategy with up to 4 other students, but you must list those people in your submission under collaborators. You may not share code, look at others’ code, or help others debug their code. You must write your own code. Not just type it (though you need to do that too): compose it yourself, as your own original work. Please read the syllabus carefully around coding. Do not seek published or online solutions for any assignments. If you use any published or online resources (which may not include solutions) when completing this assignment, be sure to cite them. Do not submit a solution that you are unable to explain orally to a member of the course staff.

Use of Generative AI

For PA4, you are not allowed to use generative AI tools to help you solve this problem.