Skip to main content
Code Golf

Return to Answer

Reworded explanation.
Source Link
xnor
xnor
  • 149.7k
  • 26
  • 287
  • 676

Python 2: 130 bytes

for i in range(4096): G=([0]*6+["\n"])*4;exec"b=i%2;j=G.index(0);G[j]=G[(j+7**b)%28]='-|'[b];i/=2;"*12 if all(G):print"".join(G)

I use a different encoding of tilings than has been posted so far, one that is more efficient timewise in that it needs only 12 bits to represent a valid tiling, though in retrospect perhaps not the golfiest one.

If you "read" through the 4x6 grid from left to right, top to bottom, each domino you encounter in order is either vertical or horizontal. (Of course, you encounter each domino twice, but only the first encounter of the top or left corner matters). This gives a sequence of 12 bits.

For example, the tiling

——|——| |||——| ||||—— ——||——

corresponds to HVHVVVVHVHHH.

Conversely, each sequence of 12 corresponds to a unique tiling, created by repeatedly adding a tile of the specified orientation with it's top or right cell as the first unoccupied cell in reading order. SoSome, though, are not legal tilings because a domino is placed with its other half off the board or overlapping with an existing domino.

The code tries every possible sequence, represented by a 12-bit number 0 to 4095 in bits, reading off bits one at a time with %2 and /2. Zeroes representThe board, initialized with zeroes for empty cells in the initially empty board, which is stored with rows concatenated into a single list. That way, it's easy to find the first zero element to place the domino. The other domino half is either one row or column down, and so found by adding 1 or 6 to the index. These two cells are filled with the proper character - or |. This list could have been a string except that Python strings are immutable.

Rather than checking for a collision, we place the dominoes allowing overlaps, and see at the end whether the board remainsis filled by whether allany zeroes have been filledremain (all). We actually make the board 4x7, filling the right row with \n for two reasons. The first is that the padding lets horizontal dominoes go off the end without cycling over to the left edge (dominoes that go off the bottom edge are wrapped around with %28, but that's fine because they overlap with the the first row which has been filled by then so an overlap occurs). The other reason is so that in a legal configuration, the newlines remain and cause the lines to be printerprinted separately when the characters are joined.

Python 2: 130 bytes

for i in range(4096): G=([0]*6+["\n"])*4;exec"b=i%2;j=G.index(0);G[j]=G[(j+7**b)%28]='-|'[b];i/=2;"*12 if all(G):print"".join(G)

I use a different encoding of tilings than has been posted so far, one that is more efficient timewise in that it needs only 12 bits to represent a valid tiling, though in retrospect perhaps not the golfiest one.

If you "read" through the 4x6 grid from left to right, top to bottom, each domino you encounter in order is either vertical or horizontal. (Of course, you encounter each domino twice, but only the first encounter of the top or left corner matters). This gives a sequence of 12 bits.

For example, the tiling

——|——| |||——| ||||—— ——||——

corresponds to HVHVVVVHVHHH.

Conversely, each sequence of 12 corresponds to a unique tiling, created by repeatedly adding a tile of the specified orientation with it's top or right cell as the first unoccupied cell in reading order. So, though, are not legal tilings because a domino is placed with its other half off the board or overlapping with an existing domino.

The code tries every possible sequence, represented by a number 0 to 4095 in bits, reading off bits one at a time with %2 and /2. Zeroes represent empty cells in the initially empty board, which is stored with rows concatenated into a single list. That way, it's easy to find the first zero element to place the domino. The other half is either one row or column down. These two cells are filled with the proper character. This list could have been a string except that Python strings are immutable.

Rather than checking for a collision, we place the dominoes allowing overlaps, and see at the end whether the board remains by whether all zeroes have been filled. We actually make the board 4x7, filling the right row with \n for two reasons. The first is that the padding lets horizontal dominoes go off the end without cycling over to the left edge (dominoes that go off the bottom edge are wrapped around with %28, but that's fine because the first row has been filled by then so an overlap occurs). The other is so that in a legal configuration, the newlines remain and cause the lines to be printer separately when the characters are joined.

Python 2: 130 bytes

for i in range(4096): G=([0]*6+["\n"])*4;exec"b=i%2;j=G.index(0);G[j]=G[(j+7**b)%28]='-|'[b];i/=2;"*12 if all(G):print"".join(G)

I use a different encoding of tilings than has been posted so far, one that is more efficient timewise in that it needs only 12 bits to represent a valid tiling, though in retrospect perhaps not the golfiest one.

If you "read" through the 4x6 grid from left to right, top to bottom, each domino you encounter in order is either vertical or horizontal. (Of course, you encounter each domino twice, but only the first encounter of the top or left corner matters). This gives a sequence of 12 bits.

For example, the tiling

——|——| |||——| ||||—— ——||——

corresponds to HVHVVVVHVHHH.

Conversely, each sequence of 12 corresponds to a unique tiling, created by repeatedly adding a tile of the specified orientation with it's top or right cell as the first unoccupied cell in reading order. Some, though, are not legal tilings because a domino is placed with its other half off the board or overlapping with an existing domino.

The code tries every possible sequence, represented by a 12-bit number 0 to 4095, reading off bits one at a time with %2 and /2. The board, initialized with zeroes for empty cells, is stored with rows concatenated into a single list. That way, it's easy to find the first zero element to place the domino. The other domino half is either one row or column down, and so found by adding 1 or 6 to the index. These two cells are filled with the proper character - or |. This list could have been a string except that Python strings are immutable.

Rather than checking for a collision, we place the dominoes allowing overlaps, and see at the end whether the board is filled by whether any zeroes remain (all). We actually make the board 4x7, filling the right row with \n for two reasons. The first is that the padding lets horizontal dominoes go off the end without cycling over to the left edge (dominoes that go off the bottom edge are wrapped around with %28, but that's fine because they overlap with the the first row which has been filled by then). The other reason is so that in a legal configuration, the newlines remain and cause the lines to be printed separately when the characters are joined.

edited body
Source Link
xnor
xnor
  • 149.7k
  • 26
  • 287
  • 676

Python 2: 130 bytes

for i in range(4096): G=([0]*6+["\n"])*4;exec"b=i%2;j=G.index(0);G[j]=G[(j+7**b)%28]='-|'[b];i/=2;"*12 if all(G):print"".join(G)

I use a different encoding of tilings thatthan has been posted so far, one that is more efficient timewise in that it needs only 12 bits to represent a valid tiling, though in retrospect perhaps not the golfiest one.

If you "read" through the 4x6 grid from left to right, top to bottom, each domino you encounter in order is either vertical or horizontal. (Of course, you encounter each domino twice, but only the first encounter of the top or left corner matters). This gives a sequence of 12 bits.

For example, the tiling

——|——| |||——| ||||—— ——||——

corresponds to HVHVVVVHVHHH.

Conversely, each sequence of 12 corresponds to a unique tiling, created by repeatedly adding a tile of the specified orientation with it's top or right cell as the first unoccupied cell in reading order. So, though, are not legal tilings because a domino is placed with its other half off the board or overlapping with an existing domino.

The code tries every possible sequence, represented by a number 0 to 4095 in bits, reading off bits one at a time with %2 and /2. Zeroes represent empty cells in the initially empty board, which is stored with rows concatenated into a single list. That way, it's easy to find the first zero element to place the domino. The other half is either one row or column down. These two cells are filled with the proper character. This list could have been a string except that Python strings are immutable.

Rather than checking for a collision, we place the dominoes allowing overlaps, and see at the end whether the board remains by whether all zeroes have been filled. We actually make the board 4x7, filling the right row with \n for two reasons. The first is that the padding lets horizontal dominoes go off the end without cycling over to the left edge (dominoes that go off the bottom edge are wrapped around with %28, but that's fine because the first row has been filled by then so an overlap occurs). The other is so that in a legal configuration, the newlines remain and cause the lines to be printer separately when the characters are joined.

Python 2: 130 bytes

for i in range(4096): G=([0]*6+["\n"])*4;exec"b=i%2;j=G.index(0);G[j]=G[(j+7**b)%28]='-|'[b];i/=2;"*12 if all(G):print"".join(G)

I use a different encoding of tilings that has been posted so far, one that is more efficient timewise in that it needs only 12 bits to represent a valid tiling, though in retrospect perhaps not the golfiest one.

If you "read" through the 4x6 grid from left to right, top to bottom, each domino you encounter in order is either vertical or horizontal. (Of course, you encounter each domino twice, but only the first encounter of the top or left corner matters). This gives a sequence of 12 bits.

For example, the tiling

——|——| |||——| ||||—— ——||——

corresponds to HVHVVVVHVHHH.

Conversely, each sequence of 12 corresponds to a unique tiling, created by repeatedly adding a tile of the specified orientation with it's top or right cell as the first unoccupied cell in reading order. So, though, are not legal tilings because a domino is placed with its other half off the board or overlapping with an existing domino.

The code tries every possible sequence, represented by a number 0 to 4095 in bits, reading off bits one at a time with %2 and /2. Zeroes represent empty cells in the initially empty board, which is stored with rows concatenated into a single list. That way, it's easy to find the first zero element to place the domino. The other half is either one row or column down. These two cells are filled with the proper character. This list could have been a string except that Python strings are immutable.

Rather than checking for a collision, we place the dominoes allowing overlaps, and see at the end whether the board remains by whether all zeroes have been filled. We actually make the board 4x7, filling the right row with \n for two reasons. The first is that the padding lets horizontal dominoes go off the end without cycling over to the left edge (dominoes that go off the bottom edge are wrapped around with %28, but that's fine because the first row has been filled by then so an overlap occurs). The other is so that in a legal configuration, the newlines remain and cause the lines to be printer separately when the characters are joined.

Python 2: 130 bytes

for i in range(4096): G=([0]*6+["\n"])*4;exec"b=i%2;j=G.index(0);G[j]=G[(j+7**b)%28]='-|'[b];i/=2;"*12 if all(G):print"".join(G)

I use a different encoding of tilings than has been posted so far, one that is more efficient timewise in that it needs only 12 bits to represent a valid tiling, though in retrospect perhaps not the golfiest one.

If you "read" through the 4x6 grid from left to right, top to bottom, each domino you encounter in order is either vertical or horizontal. (Of course, you encounter each domino twice, but only the first encounter of the top or left corner matters). This gives a sequence of 12 bits.

For example, the tiling

——|——| |||——| ||||—— ——||——

corresponds to HVHVVVVHVHHH.

Conversely, each sequence of 12 corresponds to a unique tiling, created by repeatedly adding a tile of the specified orientation with it's top or right cell as the first unoccupied cell in reading order. So, though, are not legal tilings because a domino is placed with its other half off the board or overlapping with an existing domino.

The code tries every possible sequence, represented by a number 0 to 4095 in bits, reading off bits one at a time with %2 and /2. Zeroes represent empty cells in the initially empty board, which is stored with rows concatenated into a single list. That way, it's easy to find the first zero element to place the domino. The other half is either one row or column down. These two cells are filled with the proper character. This list could have been a string except that Python strings are immutable.

Rather than checking for a collision, we place the dominoes allowing overlaps, and see at the end whether the board remains by whether all zeroes have been filled. We actually make the board 4x7, filling the right row with \n for two reasons. The first is that the padding lets horizontal dominoes go off the end without cycling over to the left edge (dominoes that go off the bottom edge are wrapped around with %28, but that's fine because the first row has been filled by then so an overlap occurs). The other is so that in a legal configuration, the newlines remain and cause the lines to be printer separately when the characters are joined.

Source Link
xnor
xnor
  • 149.7k
  • 26
  • 287
  • 676

Python 2: 130 bytes

for i in range(4096): G=([0]*6+["\n"])*4;exec"b=i%2;j=G.index(0);G[j]=G[(j+7**b)%28]='-|'[b];i/=2;"*12 if all(G):print"".join(G)

I use a different encoding of tilings that has been posted so far, one that is more efficient timewise in that it needs only 12 bits to represent a valid tiling, though in retrospect perhaps not the golfiest one.

If you "read" through the 4x6 grid from left to right, top to bottom, each domino you encounter in order is either vertical or horizontal. (Of course, you encounter each domino twice, but only the first encounter of the top or left corner matters). This gives a sequence of 12 bits.

For example, the tiling

——|——| |||——| ||||—— ——||——

corresponds to HVHVVVVHVHHH.

Conversely, each sequence of 12 corresponds to a unique tiling, created by repeatedly adding a tile of the specified orientation with it's top or right cell as the first unoccupied cell in reading order. So, though, are not legal tilings because a domino is placed with its other half off the board or overlapping with an existing domino.

The code tries every possible sequence, represented by a number 0 to 4095 in bits, reading off bits one at a time with %2 and /2. Zeroes represent empty cells in the initially empty board, which is stored with rows concatenated into a single list. That way, it's easy to find the first zero element to place the domino. The other half is either one row or column down. These two cells are filled with the proper character. This list could have been a string except that Python strings are immutable.

Rather than checking for a collision, we place the dominoes allowing overlaps, and see at the end whether the board remains by whether all zeroes have been filled. We actually make the board 4x7, filling the right row with \n for two reasons. The first is that the padding lets horizontal dominoes go off the end without cycling over to the left edge (dominoes that go off the bottom edge are wrapped around with %28, but that's fine because the first row has been filled by then so an overlap occurs). The other is so that in a legal configuration, the newlines remain and cause the lines to be printer separately when the characters are joined.