Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
Brute force, smart order solution in Speedy category for Numbered Triangles by macfreek
#!/usr/bin/env python3.3
# -*- coding: utf-8 -*-
from itertools import chain, combinations
def duplicates(iterable):
"""yield all duplicate numbers in iterable, in sorted order.
E.g. [1,1,1,1,1,2,2,3] would yield [1,1,2]."""
prev = None
for item in sorted(iterable):
if item == prev:
yield item
prev = None
else:
prev = item
def other(array, item):
"""Remove item from array and return the remainder.
Leaves original array untouched."""
array = array[:]
array.remove(item)
return array
def has_cycle(inner_sides, chips, start, end):
"""Return True if it is possible to create a cycle chips with inner_sides
as the 'connecting' items."""
# print(inner_sides, chips, start, end)
if len(inner_sides) == 0:
# print("last",chips, start, end)
assert len(chips) == 1
chip = chips[0]
return end in other(chips[0], start)
for chip in chips:
try:
for next in set(other(chip, start)):
try:
other(inner_sides, next) # debug
# print(inner_sides, chips, start, end, "-", chip, next)
if has_cycle(other(inner_sides, next), other(chips, chip), next, end):
return True
except ValueError: # list.remove(x): x not in list
continue
except ValueError: # list.remove(x): x not in list
pass
return False
def checkio(chips):
"""A few observations:
* Since we can both rotate and flip chips, the order of the sides is irrelevant.
* Maximing the outer sides is the same as minimising the inner sides.
* So we have to find a cycle that loops all 6 chips and has the lowest six numbers.
"""
l = len(chips)
all_sides = list(chain(*chips))
# candidates contains sides that can be paired.
# E.g. If side '5' occurs 7 times, the '5' occurs twice in candidates.
candidates = list(duplicates(all_sides))
# loop through all set of 6 sides in candidates, in order of increasing sum
# There are 18 sides, thus as most 9 candidates. This gives at most 9!/6!/3! = 84
# possible numbers for the inner sides. However, since we are looking for the best
# candidate in order, it seems unlikely that this is ever reached.
# list(set(iterable)) removes duplicates in case candidates contains duplicates.
for inner_sides in sorted(list(set(combinations(candidates, l))), key=sum):
# Start the cycle at a random point, in this case inner_side[0].
if has_cycle(list(inner_sides[1:]), chips, inner_sides[0], inner_sides[0]):
return sum(all_sides) - 2 * sum(inner_sides)
return 0
#These "asserts" using only for self-checking and not necessary for auto-testing
April 27, 2014
Comments:
