Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
First solution in Clear category for Domino Chain by colinmcnicholl
def get_suitable_tiles(tiles, my_tile):
"""Input: 'tiles' as a list of tiles as two-tuples of integers,
each integer representing the value on the tile and 'my_tile' as
a two-tuple of integers.
Output: A list of tiles that have a left number that matches with
the right number on the given tile. Maybe an empty list.
"""
num_1, num_2 = my_tile
copy_tiles = tiles[:]
copy_tiles.remove(my_tile)
matches = []
for tile in copy_tiles:
num_x, num_y = tile
if tile != turn(my_tile) and num_x == num_2:
matches.append((num_x, num_y))
return matches
def turn(tile):
"""Input: a two-tuple, e.g., (3, 5) representing a tile.
Function turns the tile around so first (left) number on tile is
now on the right.
Output: a two-tuple.
"""
return (tile[1], tile[0])
def try_compile(chain, end_tile, tiles_count):
count = 0
candidates = tiles_dict[end_tile]
candidates_copy = candidates[:]
while len(candidates_copy) > 0:
link_tile = candidates_copy.pop()
if link_tile not in chain and turn(link_tile) not in chain:
if len(chain) + 1 == tiles_count:
count += 1
else:
count += try_compile(chain + [link_tile], link_tile,
tiles_count)
return count
def domino_chain(tiles: str) -> int:
"""Input: String with the description of the domino tiles.
Like this one: "5-4, 4-3, 3-2, 2-1".
Function counts how many complete chains you can make using all of the
given tiles.
Note. Chains must be unique. An inverted chain is not considered as
unique: "1-2, 2-3, 3-4, 4-5" and "5-4, 4-3, 3-2, 2-1" are the same chain.
Output: Integer. The maximum number of complete chains that you can
build using all of the given tiles.
"""
tiles = {elem.strip() for elem in tiles.split(',')}
tiles_count = len(tiles)
tiles = {(int(tile[0]), int(tile[2])) for tile in tiles}
turn_tiles = {turn(tile) for tile in tiles}
tiles.update(turn_tiles)
tiles = list(tiles)
copy_tiles = tiles[:]
global tiles_dict
tiles_dict = {}
for tile in tiles:
tiles_dict[tile] = get_suitable_tiles(tiles, tile)
result = 0
while len(tiles) > 0:
a_tile = tiles.pop()
count = try_compile([a_tile], a_tile, tiles_count)
result += count
return result // 2
if __name__ == '__main__':
#These "asserts" using only for self-checking and not necessary for auto-testing
assert domino_chain("0-2, 0-5, 1-5, 1-3, 5-5") == 1
assert domino_chain("1-5, 2-5, 3-5, 4-5, 3-4") == 2
assert domino_chain("0-5, 1-5, 2-5, 3-5, 4-5, 3-4") == 0
assert domino_chain("0-1, 0-2, 1-3, 1-2, 3-4, 2-4") == 6
assert domino_chain("0-1, 0-2, 1-3, 1-2, 3-4, 2-4, 3-0, 0-4") == 0
assert domino_chain("1-2, 2-2, 2-3, 3-3, 3-1") == 5
assert domino_chain("1-4, 3-4, 0-4, 0-5, 4-5, 2-4, 2-5") == 0
assert domino_chain("1-4, 1-5, 0-2, 1-6, 4-6, 4-5, 5-6") == 0
assert domino_chain("1-2, 2-3, 2-4, 3-4, 2-5, 2-6, 5-6") == 8
assert domino_chain("1-2, 2-3, 3-1, 4-5, 5-6, 6-4") == 0
assert domino_chain("1-2, 1-4, 1-5, 1-6, 1-1, 2-5, 4-6") == 28
print("Basic tests passed.")
Feb. 15, 2019
Comments:
