Генератор на тухлички

Краен срок: 29.03.2016 13:00

Срокът за предаване на решения е отминал

Генератор на тухлички

Чували ли сте вица за тухличка? Ако не сте, питайте. Обратно към задачата.

Повечето от вас са играли в някакъв период от своите посттийн години това:

Puzzle

Ако не сте, или пък сте забравили, може да се позабавлявате!

Целта е да упражним генератори. Напишете функция def solvable_tiles(size=3), която връща по мързеливия начин итеруем обект, на който като се извика next(), връща подредба на дъска (съответно с размер size x size).

Подредбите трябва да са различни и да са възможни за изпълнение. Връщането на дъски продължава до изчерпвне на количествата.

Дъската се представя като кортеж от кортежи отразяващи съответно редовете. С 0 се означава празно квадратче.

Например дъската от картинката по-горе се представя като:

(
    (1, 2, 3, 4),
    (5, 6, 7, 8),
    (9, 10, 11, 12),
    (13, 14, 15, 0)
)

Как се разбира, че една конкретна подредба има решение, може да прочете тук. Да се пробвате да измислите сами формула, да питате във форума или нещо друго.

Решения

Коректно
6 успешни тест(а)
0 неуспешни тест(а)

Теодор Тошков

import itertools

def inversion(ls):

    length = len(ls)

    counter = 0

    for i in range(0, length-1):

        for j in range(i+1, length):

            counter = counter + (ls[i] > ls[j])

    return counter

def even(num):

    return num % 2 == 0

def odd(num):

    return num % 2 != 0

def valid(game):

    size = len(game)

    zeroless = [item for sublist in game for item in sublist]

    empty_pos = zeroless.index(0)

    empty_pos_row = empty_pos // size

    del zeroless[empty_pos]

    inversions = inversion(zeroless)

    return (odd(size) and even(inversions)) or \

           (even(size) and (even(empty_pos_row) != even(inversions)))

def solvable_tiles(size=3):

    for game in filter(valid,

                       map(lambda x: tuple(zip(*[iter(x)]*size)),

                           itertools.permutations(range(0, size ** 2)))):

        yield game

......
----------------------------------------------------------------------
Ran 6 tests in 0.157s

OK

Некоректно
1 успешни тест(а)
5 неуспешни тест(а)

Десислава Цветкова

def chunkify(xs, size):

    return tuple(tuple(xs[i:i + size]) for i in range(0, len(xs), size))

def inversion_number(xs):

    without_zero = list(xs)

    without_zero.remove(0)

    return sum(1 for x, y in combinations(range(len(without_zero)), 2)

               if without_zero[x] > without_zero[y])

def make_combinations(size):

    return groupby(map(lambda xs: [inversion_number(xs) % 2, xs],

                       permutations(range(size))), key=lambda xs: xs[0])

def filter_zero(matrix, begin):

    searched_lines = [matrix[i] for i in range(begin, len(matrix), 2)]

    return any(map(lambda line: 0 in line, searched_lines))

def solvable_tiles(size=3):

    combs = make_combinations(size ** 2)

    for key, group in combs:

        # odd grid, even inversions

        if size % 2 == 1 and key == 0:

            for element in group:

                yield(chunkify(element[1], size))

        # even grid, odd inversions

        elif size % 2 == 0 and key == 1:

            for element in group:

                matrix = chunkify(element[1], size)

                if filter_zero(matrix, 0):

                    yield(matrix)

        # even grid, even inversions

        elif size % 2 == 0 and key == 0:

            for element in group:

                matrix = chunkify(element[1], size)

                if filter_zero(matrix, 1):

                    yield(matrix)

E.EEEE
======================================================================
ERROR: test_board_rows_are_correct_size (test.TestSolvableTiles)
----------------------------------------------------------------------
Traceback (most recent call last):
  File "/data/rails/pyfmi-2016/releases/20160307095126/lib/language/python/runner.py", line 67, in thread
    raise result
NameError: name 'groupby' is not defined

======================================================================
ERROR: test_solvable_tiles_actually_returns_solvable_tiles (test.TestSolvableTiles)
----------------------------------------------------------------------
Traceback (most recent call last):
  File "/data/rails/pyfmi-2016/releases/20160307095126/lib/language/python/runner.py", line 67, in thread
    raise result
NameError: name 'groupby' is not defined

======================================================================
ERROR: test_solvable_tiles_returns_tuple_of_tuples (test.TestSolvableTiles)
----------------------------------------------------------------------
Traceback (most recent call last):
  File "/data/rails/pyfmi-2016/releases/20160307095126/lib/language/python/runner.py", line 67, in thread
    raise result
NameError: name 'groupby' is not defined

======================================================================
ERROR: test_stopiteration_error_is_raised (test.TestSolvableTiles)
----------------------------------------------------------------------
Traceback (most recent call last):
  File "/data/rails/pyfmi-2016/releases/20160307095126/lib/language/python/runner.py", line 67, in thread
    raise result
NameError: name 'groupby' is not defined

======================================================================
ERROR: test_tiles_generated_uniqueness (test.TestSolvableTiles)
----------------------------------------------------------------------
Traceback (most recent call last):
  File "/data/rails/pyfmi-2016/releases/20160307095126/lib/language/python/runner.py", line 67, in thread
    raise result
NameError: name 'groupby' is not defined

----------------------------------------------------------------------
Ran 6 tests in 0.116s

FAILED (errors=5)

Некоректно
0 успешни тест(а)
0 неуспешни тест(а)

Илия Жечев

from itertools import permutations

import numpy as np

import math

def even(number):

    return number % 2 == 0

def odd(number):

    return not even(number)

def count_inversions(board):

    return sum(sum(piece > current and bool(piece and current)

                   for current in board[id + 1:])

               for id, piece in enumerate(board[:-1]))

def valid_move(board):

    inversions = count_inversions(board)

    grid_width = int(math.sqrt(len(board)))

    blank_pos = grid_width - math.ceil((board.index(0) + 1) / grid_width) + 1

    return (odd(grid_width) and even(inversions)) or (

        even(grid_width) and odd(blank_pos) == even(inversions))

def solvable_tiles(size=3):

    return (tuple(board[i: i + size] for i in np.arange(0, size ** 2, size))

            for board in filter(valid_move, permutations(range(size ** 2))))

No module named 'numpy'
  File "/data/rails/pyfmi-2016/releases/20160307095126/lib/language/python/runner.py", line 114, in main
    loaded_test = imp.load_source('test', test_module)
  File "/usr/local/lib/python3.5/imp.py", line 172, in load_source
    module = _load(spec)
  File "<frozen importlib._bootstrap>", line 693, in _load
  File "<frozen importlib._bootstrap>", line 673, in _load_unlocked
  File "<frozen importlib._bootstrap_external>", line 662, in exec_module
  File "<frozen importlib._bootstrap>", line 222, in _call_with_frames_removed
  File "/tmp/d20160330-2514-169viji/test.py", line 3, in <module>
    import solution
  File "/tmp/d20160330-2514-169viji/solution.py", line 2, in <module>
    import numpy as np

Коректно
6 успешни тест(а)
0 неуспешни тест(а)

Ивета Чампоева

import math

import random

def number_of_inversions(row):

    sum = 0

    for i in range(0, len(row) - 1):

        for j in range(i + 1, len(row)):

            if row[i] > row[j] and row[j]:

    return sum

def tuple_of_tuples(row):

    size = int(math.sqrt(len(row)))

    return tuple([tuple([row[j] for j in range(i, i+size)])

                 for i in range(0, len(row), size)])

def blank_on_even_row(row):

    size = int(math.sqrt(len(row)))

    tiles = tuple_of_tuples(row)

    for line in range(size - 2, -1, 2):

        if 0 in tiles[line]:

            return True

    return False

def legal(row):

    size = int(math.sqrt(len(row)))

    if size % 2 != 0 and number_of_inversions(row) % 2 == 0:

        return True

    elif size % 2 == 0 and blank_on_even_row(row) and\

            number_of_inversions(row) % 2 != 0:

        return True

    elif size % 2 == 0 and not blank_on_even_row(row) and\

            number_of_inversions(row) % 2 == 0:

        return True

    else:

        return False

def solvable_tiles(size=3):

    row = random.sample(range(size ** 2), size ** 2)

    solutions = []

    count = 0

    while count < math.factorial(size ** 2)/2:

        if legal(row) and row not in solutions:

            yield tuple_of_tuples(row)

            count += 1

            solutions.append(row)

        else:

            row = random.sample(range(size ** 2), size ** 2)

    raise StopIteration

......
----------------------------------------------------------------------
Ran 6 tests in 0.365s

OK

Коректно
6 успешни тест(а)
0 неуспешни тест(а)

Мартин Стоев

import random

import math

from itertools import accumulate

def Merge(A, B):

    count = 0

    M = []

    while A and B:

        if A[0] <= B[0]:

            M.append(A.pop(0))

        else:

            count += len(A)

            M.append(B.pop(0))

    M += A + B

    return M, count

def count_inversions(A):

    l = len(A)

    if l > 1:

        n = l // 2

        C = A[:n]

        D = A[n:]

        C, c = count_inversions(A[:n])

        D, d = count_inversions(A[n:])

        B, b = Merge(C, D)

        return B, b + c + d

    else:

        return A, 0

def solvable(sample, size):

    odd = size % 2

    inversions = count_inversions(sample)[1] % 2

    zero = sample.index(0)

    state1 = (odd and inversions != 1)

    state2 = (not odd)

    state3 = (size - math.ceil(zero % size) + 1) % 2 == inversions

    solvable = state1 or (state2 and state3)

    return solvable

def solvable_tiles(size):

    cells = size * size

    factorial = list(accumulate(range(1, cells + 1), lambda a, b: a * b))[-1]

    past = set()

    while True:

        sample = random.sample(range(0, cells), cells)

        iterations = 0

        while tuple(sample) in past or not solvable(sample, size):

            sample = random.sample(range(0, cells), cells)

            iterations += 1

            if iterations > factorial:

                raise StopIteration

        past.add(tuple(sample))

        result = tuple([tuple(sample[(x * size):((x + 1) * size)])

                        for x in range(size)])

        yield result

......
----------------------------------------------------------------------
Ran 6 tests in 0.392s

OK

Коректно
6 успешни тест(а)
0 неуспешни тест(а)

Христо Хърсев

from itertools import permutations

def inversions(tile, tiles):

    return [

        tile > following_tile and following_tile != 0

        for following_tile in tiles[tiles.index(tile)+1:]

    ].count(True)

def is_solvable(tiles, size):

    inversions_count = sum(inversions(x, tiles) for x in tiles)

    blank_tile_row = tiles.index(0) // size

    if size % 2 == 1 and inversions_count % 2 == 0:

        return True

    if size % 2 == 0 and inversions_count % 2 != blank_tile_row % 2:

        return True

    return False

def solvable_tiles(size=3):

    tiles = permutations(range(size * size), size * size)

    return (

        tuple((tile[i * size: i * size + size]) for i in range(size))

        for tile in tiles

        if is_solvable(tile, size)

......
----------------------------------------------------------------------
Ran 6 tests in 0.598s

OK

Коректно
6 успешни тест(а)
0 неуспешни тест(а)

Тодор Димов

from itertools import permutations

def solvable_tiles(size=3):

    def valid(data):

        def inversions(data):

            ind, count = 0, 0

            for num1 in data:

                for num2 in data[ind::]:

                    if(num1 != 0 and num2 != 0 and num1 > num2):

            return count

        def blank(data):

            return tuple(reversed(data)).index(0) // size + 1

        inv = not inversions(data) % 2

        return size % 2 and inv or not size % 2 and blank(data) % 2 == inv

    def make_board(data):

        result = ()

        for ind in range(size):

            result += (data[ind * size:(ind + 1) * size],)

        return result

    boards = permutations(range(size ** 2))

    for board in boards:

        if(valid(board)):

            yield make_board(board)

......
----------------------------------------------------------------------
Ran 6 tests in 0.137s

OK

Коректно
6 успешни тест(а)
0 неуспешни тест(а)

Стилиян Стоянов

from itertools import permutations

def count_inversions(tile):

    inversions = 0

    for index, item in enumerate(tile):

        for j in range(index, len(tile)):

            if item > tile[j]:

                inversions += 1

    return inversions

def is_solvable(tile, size):

    inversions_count = count_inversions(tile)

    blank_row = int(tile[::-1].index(0)/size)

    A, B, C = size % 2, blank_row % 2, inversions_count % 2

    # B==C

    # (even_blank_row(0..size-1) == even_inversions) or

    # (odd_blank_row_number(0..size-1) == odd_inversions)]

    if (A and not(C)) or (not(A) and (B == C)):

        return True

    else:

        return False

def solvable_tiles(size=3):

    all_tiles = permutations(range(size * size))

    for tile in all_tiles:

        if is_solvable(tile, size):

            tile = [tile[x:x+size] for x in range(0, size * size, size)]

            yield tuple(tile)

......
----------------------------------------------------------------------
Ran 6 tests in 0.152s

OK

Коректно
6 успешни тест(а)
0 неуспешни тест(а)

Борис Алтънов

import itertools

def count_inversions(arr):

    count = 0

    for i in range(len(arr)):

        for n in arr[i + 1:]:

            if n < arr[i] and n != 0:

                count = count + 1

    return count

def check_zero(arr):

    for i in range(len(arr)):

        for j in range(len(arr[0])):

            if arr[i][j] == 0:

                    return True

                    return False

def to_table(arr, size):

    table = tuple(arr[n:n + size] for n in range(0, len(arr), size))

    return table

def solvable_tiles(size=3):

    tiles_perm = itertools.permutations(range(size**2))

    if size % 2 == 1:

        for elem in tiles_perm:

            if count_inversions(elem) % 2 == 0:

                yield to_table(elem, size)

    elif size % 2 == 0:

        for elem in tiles_perm:

            if check_zero(to_table(elem, size)) and \

                    count_inversions(elem) % 2 == 1:

                yield to_table(elem, size)

            if not check_zero(to_table(elem, size)) and \

                    count_inversions(elem) % 2 == 0:

                yield to_table(elem, size)

......
----------------------------------------------------------------------
Ran 6 tests in 0.126s

OK

Коректно
6 успешни тест(а)
0 неуспешни тест(а)

Георги Данков

from itertools import permutations

def solvable_tiles(size=3):

    perms = permutations(range(size ** 2))

    for perm in perms:

        if is_solvable(perm, size):

            yield to_tile(perm, size)

def is_solvable(x, size):

    even_inversions = count_inversions(x) % 2 == 0

    if(size % 2 != 0 and even_inversions or

       size % 2 == 0 and blank_on_even_row(x, size) is not even_inversions):

        return True

    else:

        return False

def blank_on_even_row(permutation, size):

    row_counter = 1

    for i in range(len(permutation) - size, -1, -size):

        if(0 in permutation[i:i+size]):

            return row_counter % 2 == 0

        else:

            row_counter += 1

def to_tile(permutation, size):

    result = tuple(tuple(permutation[i:i+size])

                   for i in range(0, len(permutation), size))

    return result

def count_inversions(array):

    return merge(array)[1]

def merge(array):

    if (len(array) < 2):

        return array, 0

    middle_index = int(len(array) / 2)

    left = merge(array[:middle_index])

    right = merge(array[middle_index:])

    count = left[1] + right[1]

    return merge_helper(left[0], right[0], count)

def merge_helper(left, right, count):

    left_length = len(left)

    right_length = len(right)

    sorted_array = []

    i, j = 0, 0

    while i < left_length and j < right_length:

        if left[i] == 0:

        elif right[j] == 0:

        elif left[i] <= right[j]:

            sorted_array.append(left[i])

        elif left[i] > right[j]:

            sorted_array.append(right[j])

            count += left_length - i

    sorted_array += left[i:]

    sorted_array += right[j:]

    return sorted_array, count

......
----------------------------------------------------------------------
Ran 6 tests in 0.242s

OK

Коректно
6 успешни тест(а)
0 неуспешни тест(а)

Алекс Николов

import itertools

import math

def solvable_tiles(size=3):

    all_tile_permutations = itertools.permutations(range(size * size))

    return (create_board(permutation) for permutation in all_tile_permutations

            if is_tile_solution(permutation))

def inversions(perm):

    inversion_number = 0

    for i in range(len(perm) - 1, -1, -1):

        for j in range(len(perm) - 1, i, -1):

            if 0 not in [perm[i], perm[j]] and perm[i] > perm[j]:

                inversion_number += 1

    return inversion_number

def is_tile_solution(permutation):

    grid_width = math.sqrt(len(permutation))

    inversion_number_even = inversions(permutation) % 2 == 0

    grid_width_even = grid_width % 2 == 0

    row_with_blank = grid_width - permutation.index(0) // grid_width

    blank_on_even_row_from_bottom = row_with_blank % 2 == 0

    first_condition = not grid_width_even and inversion_number_even

    second_condition = blank_on_even_row_from_bottom == inversion_number_even

    return first_condition or (grid_width_even and second_condition)

def create_board(flattened_board):

    board = []

    board_width = int(math.sqrt(len(flattened_board)))

    row = []

    for index, element in enumerate(flattened_board):

        row.append(element)

        if index % board_width == board_width - 1:

            board.append(tuple(row))

            row = []

    return tuple(board)

......
----------------------------------------------------------------------
Ran 6 tests in 0.248s

OK

Коректно
6 успешни тест(а)
0 неуспешни тест(а)

Александрина Ламбова

from itertools import permutations

from math import sqrt

def even(num):

    return num % 2 == 0

def countRows(grid):

    count = 0

    for i in range(len(grid)):

        if grid[i] == 0:

            count = i

    return len(grid) - count/sqrt(len(grid))

def countInversions(grid):

    count = 0

    for i in range(1, len(grid)):

        for j in range(i):

            if(grid[j] > grid[i]):

                count += 1

    return count

def slice(grid):

    l = int(sqrt(len(grid)))

    new = []

    for i in range(l):

        new.append(tuple(grid[i*l:(i+1)*l]))

    return tuple(new)

def solvable(grid):

    if even(len(grid)):

        return even(countInversions(grid)) != even(countRows(grid))

    else:

        return even(countInversions(grid))

def solvable_tiles(size=3):

    if(size <= 0):

        raise ValueError

    return map(slice, filter(solvable, permutations(range(size*size))))

......
----------------------------------------------------------------------
Ran 6 tests in 0.142s

OK

Коректно
6 успешни тест(а)
0 неуспешни тест(а)

Николай Желязков

from itertools import permutations

import random

def count_inversions(a):

    length = len(a)

    if length > 1:

        mid = length // 2

        left, left_inversions = count_inversions(a[:mid])

        right, right_inversions = count_inversions(a[mid:])

        merge, inversions = merge_count(left, right)

        return merge, left_inversions + right_inversions + inversions

    else:

        return a, 0

def merge_count(a, b):

    count = 0

    merge = []

    while a and b:

        if a[0] <= b[0]:

            merge.append(a.pop(0))

        else:

            count += len(a)

            merge.append(b.pop(0))

    merge.extend(a + b)

    return merge, count

def get_blank_row(grid):

    for index, row in enumerate(reversed(grid)):

        if 0 in row:

            return index + 1

def is_grid_solvable(grid, grid_width):

    elements = [elem for row in grid for elem in row]

    elements.remove(0)

    inversions_count = count_inversions(elements)[1]

    blank_row = get_blank_row(grid)

    if grid_width % 2 == 0 and blank_row % 2 == 0:

        return inversions_count % 2 == 1

    else:

        return inversions_count % 2 == 0

def solvable_tiles(size=3):

    count = size * size

    numbers = list(range(0, count))

    random.shuffle(numbers)

    numbers = permutations(numbers)

    for current in numbers:

        grid = tuple([tuple(current[x:x+size]) for x in range(0, count, size)])

        if is_grid_solvable(grid, size):

            yield grid

......
----------------------------------------------------------------------
Ran 6 tests in 0.204s

OK

Некоректно
5 успешни тест(а)
1 неуспешни тест(а)

Кристина Христакиева

import itertools

def list_to_grid(l, size):

    grid = [l[i:i + size] for i in range(0, len(l), size)]

    return tuple(tuple(row) for row in grid)

def number_of_inversions(grid_list):

    new_list = [x for x in grid_list if x != 0]

    counter = 0

    for i in range(len(new_list)):

        for j in range(i + 1, len(new_list)):

            if new_list[i] > new_list[j]:

                counter += 1

    return counter

def blank_row(grid_list, size):

    new_list = list_to_grid(grid_list, size)

    for i in range(len(new_list)):

        if 0 in new_list[i]:

            return i

            break

def is_solvable(grid_list, size):

    inversions = number_of_inversions(grid_list)

    blank = blank_row(grid_list, size)

    return ((size % 2) & (not(inversions % 2))) | ((not(size % 2))

                    & (blank % 2)) == (not(inversions % 2))

class Grid:

    def __init__(self, size=3):

        self.size = size

        grid = list(range(0, self.size**2))

        self.tables = itertools.permutations(grid)

        self.listgrid = next(self.tables)

        while not is_solvable(self.listgrid, self.size):

            self.listgrid = next(self.tables)

    def __next__(self):

        try:

            while True:

                self.listgrid = next(self.tables)

                if is_solvable(self.listgrid, self.size):

                    return list_to_grid(self.listgrid, self.size)

        except StopIteration:

            raise StopIteration

def solvable_tiles(size=3):

    grid = Grid(size)

    while True:

        yield next(grid)

..F...
======================================================================
FAIL: test_solvable_tiles_actually_returns_solvable_tiles (test.TestSolvableTiles)
----------------------------------------------------------------------
Traceback (most recent call last):
  File "/data/rails/pyfmi-2016/releases/20160307095126/lib/language/python/runner.py", line 67, in thread
    raise result
AssertionError: False is not true

----------------------------------------------------------------------
Ran 6 tests in 0.146s

FAILED (failures=1)

Коректно
6 успешни тест(а)
0 неуспешни тест(а)

Димитър Керезов

from math import factorial

from itertools import permutations

def is_even(num):

    return num % 2 == 0

def get_inversions(arr, left, right):

    left_index = 0

    right_index = 0

    arr_next_index = 0

    inversions_count = 0

    left_len = len(left)

    right_len = len(right)

    while left_index < left_len or right_index < right_len:

        arr_next_index = left_index+right_index

        if left_index == left_len:

            arr[arr_next_index] = right[right_index]

            right_index += 1

        elif right_index == right_len:

            arr[arr_next_index] = left[left_index]

            left_index += 1

        elif left[left_index] <= right[right_index]:

            arr[arr_next_index] = left[left_index]

            left_index += 1

        else:

            arr[arr_next_index] = right[right_index]

            if not right[right_index] == 0:

                inversions_count += left_len - left_index

            right_index += 1

    return inversions_count

def inversions_count(arr):

    arr_len = len(arr)

    if arr_len < 2:

        return 0

    middle = (arr_len + 1) // 2

    left = arr[:middle]

    right = arr[middle:arr_len]

    return (inversions_count(left) +

            inversions_count(right) +

            get_inversions(arr, left, right))

def is_solvable(game_board, board_width):

    blank_tile_row = game_board.index(0) // board_width

    board_inversions = inversions_count(game_board)

    board_width_even = is_even(board_width)

    board_inversions_even = is_even(board_inversions)

    blank_tile_on_odd_row = not is_even(blank_tile_row % board_width)

    return ((not board_width_even and board_inversions_even) or

            (board_width_even and

                (blank_tile_on_odd_row == board_inversions_even)))

def solvable_tiles(size=3):

    if size <= 0:

        raise ValueError("Game board size cannot be less than 1")

    board_size = size * size

    numbers = list(range(board_size))

    max_number_of_boards = factorial(board_size)

    used_boards = []

    for permutation in permutations(numbers):

        if is_solvable(list(permutation), size):

            yield tuple(

                [permutation[i:i+size] for i in range(0, board_size, size)]

    raise StopIteration

......
----------------------------------------------------------------------
Ran 6 tests in 0.184s

OK

Коректно
6 успешни тест(а)
0 неуспешни тест(а)

Кристофър Митов

from functools import reduce

from math import sqrt

from itertools import permutations

def inv_count(arr):

    return reduce(lambda x, y: x + y,

                  [1 for i in range(len(arr)-1)

                   for j in range(i+1, len(arr)) if arr[i] > arr[j]], 0)

def even(n):

    return n % 2 == 0

def odd(n):

    return n % 2 == 1

def is_solvable(board):

    board = list(board)

    size = int(sqrt(len(board)))

    zero_index = (board.index(0) // size, board.index(0) % size)

    board.remove(0)

    zero_row = size - zero_index[0]

    inversions = inv_count(board)

    return any([odd(size) and even(inversions),

                (even(size) and

                ((odd(inversions) and even(zero_row)) or

                 (even(inversions) and odd(zero_row))))])

def solvable_tiles(size=3):

    game = list(range(size*size))

    solvables = filter(is_solvable, permutations(game))

    while True:

        current = next(solvables)

        result = [tuple([current[j] for j in range(i*size, size*(i + 1))])

                  for i in range(size)]

        yield tuple(result)

......
----------------------------------------------------------------------
Ran 6 tests in 0.160s

OK

Коректно
6 успешни тест(а)
0 неуспешни тест(а)

Георги Иванов

import itertools

def solvable_tiles(size):

    return Board(size)

class Board:

    def __init__(self, size):

        self.__size = size

        self.__max_number = size * size

        self.__permutations = itertools.permutations(

            list(range(0, self.__max_number)))

    def __iter__(self):

        return self

    def __next__(self):

        for permutation in self.__permutations:

            if self.__check_if_solvable(permutation):

                board = self.__convert_to_board(permutation)

                return board

            else:

                continue

        raise StopIteration()

    def __check_if_solvable(self, permutation):

        cnt_inversions = 0

        for i in range(self.__max_number):

            if permutation[i] == 0:

                blank_on_row = i / self.__size

            for j in range(i, self.__max_number):

                if permutation[i] > permutation[j]:

                    cnt_inversions += 1

        if blank_on_row % 2 == 2:

            blank_on_odd = False

        else:

            blank_on_odd = True

        if self.__size % 2 != 0 and cnt_inversions % 2 == 0:

            return True

        elif self.__size % 2 == 0 and \

                not blank_on_odd and \

                cnt_inversions % 2 == 0:

            return True

        elif self.__size % 2 == 0 and blank_on_odd and cnt_inversions % 2 != 0:

            return True

        return False

    def __convert_to_board(self, permutation):

        splitted = [permutation[i:i + self.__size]

                    for i in range(0, self.__max_number, self.__size)]

        return tuple(tuple(row) for row in splitted)

......
----------------------------------------------------------------------
Ran 6 tests in 0.160s

OK

Коректно
6 успешни тест(а)
0 неуспешни тест(а)

Хризантема Станчева

from itertools import chain, repeat

from itertools import permutations

def number_of_inversions(iterable):

    tmp = list(iterable)

    length = len(tmp)

    count = 0

    for i in range(0, length - 1):

        for j in range(i + 1, length):

            if tmp[j] < tmp[i]:

                count += 1

    return count

class ZipExhausted(Exception):

    pass

def izip_longest(*args, **kwds):

    fillvalue = kwds.get('fillvalue')

    counter = [len(args) - 1]

    def sentinel():

        if not counter[0]:

            raise ZipExhausted

        counter[0] -= 1

        yield fillvalue

    fillers = repeat(fillvalue)

    iterators = [chain(it, sentinel(), fillers) for it in args]

    try:

        while iterators:

            yield tuple(map(next, iterators))

    except ZipExhausted:

        pass

def grouper(iterable, n, fillvalue=None):

    args = [iter(iterable)] * n

    return izip_longest(fillvalue=fillvalue, *args)

def zero_position(grid, size):

    tmp = list(grid)

    for i in range(0, size):

        if 0 in set(tmp[i]):

            return i

def solvable_tiles(size=3):

    length = size ** 2

    tmp = permutations(range(0, length))

    for perm in tmp:

        num_inv = number_of_inversions(perm)

        grid = tuple(grouper(perm, size))

        zero_pos = zero_position(grid, size)

        if any([((size % 2 != 0) and (num_inv % 2 == 0)),

                (size % 2 == 0 and num_inv % 2 == 0 and zero_pos % 2 != 0),

                (size % 2 == 0 and num_inv % 2 != 0 and zero_pos % 2 == 0)]):

            yield grid

        else:

    raise StopIteration

......
----------------------------------------------------------------------
Ran 6 tests in 0.208s

OK

Коректно
6 успешни тест(а)
0 неуспешни тест(а)

Данислав Киров

from itertools import permutations

class TilesGame:

    def __init__(self, size):

        self.__size = size

        self.__permutations = permutations(range(self.__size ** 2))

    def __iter__(self):

        return self

    def __find_number_of_inversions(self, perm):

        inversions = 0

        checked_tiles = [0] * (self.__size ** 2 - 1)

        for tile in perm:

            if tile:

                checked_tiles[tile - 1] = 1

                inversions += checked_tiles[:tile].count(0)

        return inversions

    def __is_solvable(self, perm):

        inversions = self.__find_number_of_inversions(perm)

        blank_el_row = self.__size - perm.index(0) // self.__size

        cases = [

            all([self.__size % 2, not inversions % 2]),

            all([not self.__size % 2, not blank_el_row % 2, inversions % 2]),

            all([not self.__size % 2, blank_el_row % 2, not inversions % 2])

        return any(cases)

    def __next__(self):

        while True:

            perm = next(self.__permutations)

            if self.__is_solvable(perm):

                return tuple(tuple(perm[i:i + self.__size]) for i in range(

                                                    0, len(perm), self.__size))

def solvable_tiles(size=3):

    return TilesGame(size)

......
----------------------------------------------------------------------
Ran 6 tests in 0.110s

OK

Коректно
6 успешни тест(а)
0 неуспешни тест(а)

Николай Мантаров

from itertools import permutations

def inversion_count(board):

    inversions = 0

    for this in board:

        for other in board:

            if this > other and board.index(this) < board.index(other):

                if other != 0:

                    inversions += 1

    return inversions

def find_empty(board):

    length = len(board) ** (1/2)

    return int(board.index(0) / length)

def solvable(board):

    inversions = inversion_count(board)

    zero_pos = find_empty(board)

    if len(board) % 2 == 1 and inversions % 2 == 0:

        return True

    elif len(board) % 2 == 0 and zero_pos % 2 == 1 and inversions % 2 == 0:

        return True

    elif len(board) % 2 == 0 and zero_pos % 2 == 0 and inversions % 2 == 1:

        return True

    return False

def to_tuple(board, size):

    nested_lst = []

    for row in range(size):

        helper = []

        for col in range(size):

            helper.append(board[row*size+col])

        nested_lst.append(helper)

    nested_tuple_of_tuples = tuple(tuple(l) for l in nested_lst)

    return nested_tuple_of_tuples

def solvable_tiles(size=3):

    chances = permutations(range(size*size))

    while True:

        grid = next(chances)

        if solvable(list(grid)):

            solvable_grid = to_tuple(grid, size)

            yield solvable_grid

    raise StopIteration

......
----------------------------------------------------------------------
Ran 6 tests in 0.805s

OK

Коректно
6 успешни тест(а)
0 неуспешни тест(а)

Ивелина Христова

import itertools

class BoardGenerator:

    def __init__(self, size):

        self.size = size

        numbers = range(size * size)

        self.boards = itertools.permutations(numbers)

        self.solvable_boards = (board for board in self.boards if self.is_solvable(board))

    def __iter__(self):

        return self

    def __next__(self):

        row = next(self.solvable_boards)

        chunks=[row[x:x + self.size] for x in range(0, len(row), self.size)]

        return tuple(chunks)

    def is_solvable(self, board):

        inversions = len([board[index] for index in range(len(board)) 

            for x in board[index:] if board[index] > x])

        blank_on = round((len(board) - board.index(0)) / self.size)

        if self.size % 2 == 0:

            return (inversions % 2 == 0) == (blank_on % 2 != 0)

        else:

            return inversions % 2 == 0

def solvable_tiles(size=3):

    board_generator = BoardGenerator(size)

    return board_generator

......
----------------------------------------------------------------------
Ran 6 tests in 0.135s

OK

Коректно
6 успешни тест(а)
0 неуспешни тест(а)

Даниел Делчев

import itertools

def bubble_sort_count(board):

    array = board

    array = list(array)

    swaps_counter = 0

    swap_executed = True

    while swap_executed:

        swap_executed = False

        for i in range(0, len(array) - 1):

            if array[i+1] < array[i]:

                array[i+1], array[i] = array[i], array[i+1]

                swap_executed = True

                if array[i+1] != 0 and array[i] != 0:

                    swaps_counter += 1

    return swaps_counter

def find_line_of_blank(board):

    rev = list(reversed(board))

    length = int(len(rev)**0.5)

    found = False

    index = 0

    while i < length and not found:

        for j in range(0, length):

            if rev[i*length+j] == 0:

                index = i

                found = True

    return index

def solvability(board):

    even_count = bubble_sort_count(board) % 2 == 0

    even_size = (len(board)**0.5) % 2 == 0

    even_blank = (find_line_of_blank(board) + 1) % 2 == 0

    if ((not even_size) and even_count) or \

            (even_size and ((not even_blank) == even_count)):

        return True

    return False

def tupify(tup):

    l = int(len(tup)**0.5)

    return tuple([tup[i:i+l] for i in range(0, len(tup), l)])

class Tiles:

    def __init__(self, generator):

        self.iterator = generator

    def __next__(self):

        return tupify(next(self.iterator))

    def __iter__(self):

        return self

def solvable_tiles(size=3):

    gen = filter(solvability, itertools.permutations(range(0, size*size)))

    return Tiles(gen)

......
----------------------------------------------------------------------
Ran 6 tests in 0.139s

OK

Некоректно
3 успешни тест(а)
3 неуспешни тест(а)

Илиан Стаменов

from itertools import permutations

def t(size):

    def f(x):

        count = 0

        for i in range(size * size):

            for j in range(i, size * size):

                if x[i] > x[j] and x[i] != 0 and x[j] != 0:

                    count = count + 1

        print(count)

        if size % 2 == 1 and count % 2 == 0:

            return True

        if size % 2 == 0 and count % 2 != (size - int(x.index(0) / size)) % 2:

            return True

        return False

    return f

def group(n):

    def f(iterable):

        res = []

        iter = iterable.__iter__()

        for i in range(n):

            tempList = []

            for i in range(n):

                tempList.append(next(iter))

            res.append(tempList)

        return res

    return f

def solvable_tiles(size=3):

    return map(group(size), filter(t(size), permutations(range(size * size))))

..EF.E
======================================================================
ERROR: test_solvable_tiles_actually_returns_solvable_tiles (test.TestSolvableTiles)
----------------------------------------------------------------------
Traceback (most recent call last):
  File "/data/rails/pyfmi-2016/releases/20160307095126/lib/language/python/runner.py", line 67, in thread
    raise result
TypeError: can only concatenate tuple (not "list") to tuple

======================================================================
ERROR: test_tiles_generated_uniqueness (test.TestSolvableTiles)
----------------------------------------------------------------------
Traceback (most recent call last):
  File "/data/rails/pyfmi-2016/releases/20160307095126/lib/language/python/runner.py", line 67, in thread
    raise result
TypeError: unhashable type: 'list'

======================================================================
FAIL: test_solvable_tiles_returns_tuple_of_tuples (test.TestSolvableTiles)
----------------------------------------------------------------------
Traceback (most recent call last):
  File "/data/rails/pyfmi-2016/releases/20160307095126/lib/language/python/runner.py", line 67, in thread
    raise result
AssertionError: [[0, 1, 2, 3, 4, 5, 6], [7, 8, 9, 10, 11, 12, 13], [14, 15, 16, 17, 18, 19, 20], [21, 22, 23, 24, 25, 26, 27], [28, 29, 30, 31, 32, 33, 34], [35, 36, 37, 38, 39, 40, 41], [42, 43, 44, 45, 46, 47, 48]] is not an instance of <class 'tuple'>

----------------------------------------------------------------------
Ran 6 tests in 0.085s

FAILED (failures=1, errors=2)

Коректно
6 успешни тест(а)
0 неуспешни тест(а)

Андрей Иванов

import itertools

def count_inversions_helper(list_help, position):

    x = list_help[position]

    count = 0

    for i in range(position, len(list_help)):

        if x > list_help[i] and list_help[i] != 0:

            count = count + 1

    return count

def count_inversions(list_help):

    count = 0

    for i in range(0, len(list_help)):

        count = count + count_inversions_helper(list_help, i)

    return count

def zero_row_bottom(list_help, size):

    for i in range(len(list_help) - 1, -1, -1):

        if list_help[i] == 0:

            position = i

            break

    return size - int(position/size) - 1

class generator:

    def __init__(self, size):

        self.iterable = itertools.permutations(range(0, size * size))

        self.size = size

    def __iter__(self):

        return self

    def __next__(self):

        l = list(next(self.iterable))

        list_of_lists = []

        for i in range(0, self.size):

            helper = []

            for j in range(0, self.size):

                helper.append(l[k])

            list_of_lists.append(helper)

        result = tuple(tuple(x) for x in list_of_lists)

        zero_place = zero_row_bottom(l, self.size)

        count_inv = count_inversions(l)

        condition1 = self.size % 2 == 1 and count_inv % 2 == 0

        condition2 = self.size % 2 == 0 and zero_place % 2 == 1 and \

            count_inv % 2 == 1

        condition3 = self.size % 2 == 0 and zero_place % 2 == 0 and \

            count_inv % 2 == 0

        if condition1 or condition2 or condition3:

            return result

        else:

            return next(self)

def solvable_tiles(size=3):

    return generator(size)

......
----------------------------------------------------------------------
Ran 6 tests in 0.179s

OK

Коректно
6 успешни тест(а)
0 неуспешни тест(а)

Николай Бабулков

from itertools import permutations

def grid_solvable(flat_grid, width):

    size = len(flat_grid)

    inv = 0

    for i in range(size):

        if flat_grid[i] == 0:

            blank = i

        for j in range(i + 1, size):

            if flat_grid[i] > flat_grid[j] and flat_grid[j] != 0:

    blank_row_rev = width - blank//width

    return not(inv % 2) if width % 2 else blank_row_rev % 2 == (not(inv % 2))

def split_grid(flat_grid, size):

    return tuple([flat_grid[i:i+size] for i in range(0, len(flat_grid), size)])

def solvable_tiles(size=3):

    perms = permutations(range(size*size))

    return (split_grid(p, size) for p in perms if grid_solvable(p, size))

......
----------------------------------------------------------------------
Ran 6 tests in 0.150s

OK

Коректно
6 успешни тест(а)
0 неуспешни тест(а)

Светомир Стоименов

from itertools import permutations

def even(permutation):

    invertions = 0

    for i in range(0, len(permutation) - 1):

        invertions += sum(x < permutation[i] for x in permutation[i:])

    return invertions % 2 == 0

def solvable(permutation, size):

    odd_row = (size - permutation.index(0) // size) % 2 == 1

    return ((size % 2 == 1 and even(permutation)) or

            (size % 2 == 0 and odd_row == even(permutation)))

def split(tile, size):

    args = [iter(tile)] * size

    return tuple(zip(*args))

def solvable_tiles(size=3):

    for tile in permutations(range(size**2)):

        if solvable(tile, size):

            yield split(tile, size)

......
----------------------------------------------------------------------
Ran 6 tests in 0.181s

OK

Некоректно
4 успешни тест(а)
2 неуспешни тест(а)

Веселин Иванов

from itertools import permutations

from itertools import islice

def solvable(perm, size):

    inversions = 0

    for i in range(size**2 - 1):

        for j in range(i + 1, size**2):

            if perm[i] > perm[j]:

                inversions += 1

    if size % 2 == 1 and inversions % 2 == 0:

        return True

    return False

def pack(perm, size):

    return tuple(tuple(islice(perm, i * size, (i + 1) * size))

                 for i in range(size))

def solvable_tiles(size=3):

    perm_length = size**2

    perms = permutations(range(perm_length), perm_length)

    for p in perms:

        if solvable(p, size):

            yield pack(p, size)

E....E
======================================================================
ERROR: test_board_rows_are_correct_size (test.TestSolvableTiles)
----------------------------------------------------------------------
Traceback (most recent call last):
  File "/data/rails/pyfmi-2016/releases/20160307095126/lib/language/python/runner.py", line 63, in thread
    raise TimeoutError
TimeoutError

======================================================================
ERROR: test_tiles_generated_uniqueness (test.TestSolvableTiles)
----------------------------------------------------------------------
Traceback (most recent call last):
  File "/data/rails/pyfmi-2016/releases/20160307095126/lib/language/python/runner.py", line 63, in thread
    raise TimeoutError
TimeoutError

----------------------------------------------------------------------
Ran 6 tests in 4.130s

FAILED (errors=2)

Програмиране с Python

Курс във Факултета по Математика и Информатика към СУ

Генератор на тухлички

Генератор на тухлички

Решения