Commits

Anonymous committed 0eedf38

Yaaaawn. Finito.

Comments (0)

Files changed (1)

+"""
+Develer's Sequence Challenge.
+"""
+
+class Game(object):
+
+    def __init__(self, sequence):
+        self.sequence = list(sequence)
+        self.solution = sorted(sequence)
+        self.moves = 0
+        self.length = len(self.sequence)
+
+    def _move(self, x, pos):
+        if not self.sequence.index(x) == pos:
+            self.sequence.remove(x)
+            self.moves += 1
+            self.sequence.insert(pos, x)
+
+    def move_top(self, x):
+        self._move(x, 0)
+
+    def move_bottom(self, x):
+        self._move(x, self.length)
+
+    @property
+    def solved(self):
+        return self.sequence == self.solution
+
+    def __repr__(self):
+        return 'Game({0.sequence}) solved={0.solved}'.format(self)
+
+
+def ordered_groups(sequence):
+    """
+    Extract all the groups of ordered numbers in the sequence.
+    For each group yields:
+        smaller_nums, group, larger_nums.
+    smaller_nums are the numbers, not in the ordered group, smaller than the
+    first element of the group.
+    larger_nums are the numbers, not in the ordered group, larger than the last
+    element of the group.
+
+    For example, having the sequence
+        [3, 2, 1, 4, 7, 5, 9]
+    the first group of ordered numbers would be
+        [3, 4, 5]
+    smaller_nums would then be
+        [2, 1]
+    and larger_nums:
+        [7, 9]
+    """
+    solution = sorted(sequence)
+    
+    def subsequent_of(x):
+        try:
+            return solution[solution.index(x)+1]
+        except IndexError:
+            return
+
+    starts = sequence[:]
+    for start in sequence:
+        if not start in starts:
+            continue
+        next_expected = start
+        smaller_nums = []
+        larger_nums = sequence[:]
+        result = []
+        for x in sequence:
+            if x == next_expected:
+                starts.remove(x)
+                larger_nums.remove(x)
+                result.append(x)
+                next_expected = subsequent_of(x)
+            elif x < start:
+                larger_nums.remove(x)
+                smaller_nums.append(x)
+        yield smaller_nums, result, larger_nums
+
+
+def larger_group(s1, s2):
+    # reduce(larger_set, ordered_groups(sequence))
+    return (s2, s1)[len(s1[1]) > len(s2[1])]
+
+
+def tyrion_solve(game):
+    (smaller_nums, ordered,
+    larger_nums) = reduce(larger_group, ordered_groups(game.sequence))
+
+    for n in sorted(smaller_nums, reverse=True):
+        game.move_top(n)
+
+    for n in sorted(larger_nums):
+        game.move_bottom(n)
+
+    return game
+
+
+
+if __name__ == '__main__':
+    sequence = [58, 29, 97, 12, 70, 30, 16, 99, 24, 33, 69, 98, 35, 47, 52]
+    game = Game(sequence)
+    print tyrion_solve(game)