Skip to main content
added 1431 characters in body
Source Link
Jakube
  • 21.9k
  • 3
  • 27
  • 108

In my code I'll define a recursive function y. The function y takes a list of 2D-coordinates and returns the number of different domino tilings using these coordinates. E.g. y([[0,0], [0,1]]) = 1 (one horizontal domino), y([[0,0], [1,1]]) = 0 (coordinates are not adjacent) and y([[0,0], [0,1], [1,0], [1,1]]) = 2 (either two horizontal or two vertical dominoes). After defining the function I'll call it with all coordinates [x,y] with x in [0, 1, m-1], y in [0, 1, n-1].

How does the recursive function work? It's quite simple. If the list of coords is empty, there is exactly one valid tiling and y returns 1.

Otherwise I take the first coordinate in the list b[0], and search the remaining coordinates for a neighbors. If there is no neighbor to b[0], then there is no tiling possible, therefore I return 0. If there is one or more neighbors, then the number of tilings is (the number of tilings where I connect b[0] with the first neighbor via a domina, plus the number of tilings where I connect b[0] with the second neighbor, plus ...) So I call the function recursively for each neighbor with the shortened list (by removing the two coords b[0] and neighbor). Afterwards I sum up all results and return them.

Because of the order of the coords there are always only two neighbors possible, the one on the right side and the one below. But my algorithm doesn't care about that.

In my code I'll define a recursive function y. The function y takes a list of 2D-coordinates and returns the number of different domino tilings using these coordinates. E.g. y([[0,0], [0,1]]) = 1 (one horizontal domino), y([[0,0], [1,1]]) = 0 (coordinates are not adjacent) and y([[0,0], [0,1], [1,0], [1,1]]) = 2 (either two horizontal or two vertical dominoes). After defining the function I'll call it with all coordinates [x,y] with x in [0, 1, m-1], y in [0, 1, n-1].

How does the recursive function work? It's quite simple. If the list of coords is empty, there is exactly one valid tiling and y returns 1.

Otherwise I take the first coordinate in the list b[0], and search the remaining coordinates for a neighbors. If there is no neighbor to b[0], then there is no tiling possible, therefore I return 0. If there is one or more neighbors, then the number of tilings is (the number of tilings where I connect b[0] with the first neighbor via a domina, plus the number of tilings where I connect b[0] with the second neighbor, plus ...) So I call the function recursively for each neighbor with the shortened list (by removing the two coords b[0] and neighbor). Afterwards I sum up all results and return them.

Because of the order of the coords there are always only two neighbors possible, the one on the right side and the one below. But my algorithm doesn't care about that.

deleted 7 characters in body
Source Link
Jakube
  • 21.9k
  • 3
  • 27
  • 108

Pyth, 3030 29 bytes

L?bsmy-tb]dfq1.a-VThbtb1y*FUMQVThbb1y*FUMQ

Try it online: DemonstrationDemonstration / Test SuiteTest Suite

All example inputs run in the online compiler. The last one takes a few seconds though.

Explanation:

                           UMQ  convert the input numbers into ranges
                         *F     Cartesian product (coords of each square)
L                               define a function y(b):
 ?b                               if len(b) > 0:
           f         tbb             filter b[1:]b for squares T, which satisfy:
              .a-VThb                 Euclidean distance between T and b[0]
            q1                        is equal to 1 (direct neighbors)
    m                               map each neighbor d to:
      -tb]d                           remove d from b[1]
     y                                and call recursively y with the rest
   s                                sum all those values and return them
                                  else:
                       1            return 1 (valid domino tiling found)
                        y*FUMQ  Call y with all coords and print the result  

Pyth, 30 bytes

L?bsmy-tb]dfq1.a-VThbtb1y*FUMQ

Try it online: Demonstration / Test Suite

All example inputs run in the online compiler. The last one takes a few seconds though.

Explanation:

                           UMQ  convert the input numbers into ranges
                         *F     Cartesian product (coords of each square)
L                               define a function y(b):
 ?b                               if len(b) > 0:
           f         tb             filter b[1:] for squares T, which satisfy:
              .a-VThb                 Euclidean distance between T and b[0]
            q1                        is equal to 1 (direct neighbors)
    m                               map each neighbor d to:
      -tb]d                           remove d from b[1]
     y                                and call recursively y with the rest
   s                                sum all those values and return them
                                  else:
                       1            return 1 (valid domino tiling found)
                        y*FUMQ  Call y with all coords and print the result  

Pyth, 30 29 bytes

L?bsmy-tb]dfq1.a-VThbb1y*FUMQ

Try it online: Demonstration / Test Suite

All example inputs run in the online compiler. The last one takes a few seconds though.

Explanation:

                          UMQ  convert the input numbers into ranges
                        *F     Cartesian product (coords of each square)
L                              define a function y(b):
 ?b                              if len(b) > 0:
           f         b             filter b for squares T, which satisfy:
              .a-VThb                Euclidean distance between T and b[0]
            q1                       is equal to 1 (direct neighbors)
    m                              map each neighbor d to:
      -tb]d                          remove d from b[1]
     y                               and call recursively y with the rest
   s                               sum all those values and return them
                                 else:
                      1            return 1 (valid domino tiling found)
                       y*FUMQ  Call y with all coords and print the result  
Source Link
Jakube
  • 21.9k
  • 3
  • 27
  • 108

Pyth, 30 bytes

L?bsmy-tb]dfq1.a-VThbtb1y*FUMQ

Try it online: Demonstration / Test Suite

All example inputs run in the online compiler. The last one takes a few seconds though.

Explanation:

                           UMQ  convert the input numbers into ranges
                         *F     Cartesian product (coords of each square)
L                               define a function y(b):
 ?b                               if len(b) > 0:
           f         tb             filter b[1:] for squares T, which satisfy:
              .a-VThb                 Euclidean distance between T and b[0]
            q1                        is equal to 1 (direct neighbors)
    m                               map each neighbor d to:
      -tb]d                           remove d from b[1]
     y                                and call recursively y with the rest
   s                                sum all those values and return them
                                  else:
                       1            return 1 (valid domino tiling found)
                        y*FUMQ  Call y with all coords and print the result