timeit

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

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

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

Краен срок
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 неуспешни тест(а)
Теодор Тошков
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
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 неуспешни тест(а)
Десислава Цветкова
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
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 неуспешни тест(а)
Илия Жечев
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
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 неуспешни тест(а)
Ивета Чампоева
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
49
50
51
52
53
54
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]:
                sum += 1
    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 неуспешни тест(а)
Мартин Стоев
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
49
50
51
52
53
54
55
56
57
58
59
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 неуспешни тест(а)
Христо Хърсев
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
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 неуспешни тест(а)
Тодор Димов
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
from itertools import permutations


def solvable_tiles(size=3):
    def valid(data):
        def inversions(data):
            ind, count = 0, 0
            for num1 in data:
                ind += 1
                for num2 in data[ind::]:
                    if(num1 != 0 and num2 != 0 and num1 > num2):
                        count += 1
            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 неуспешни тест(а)
Стилиян Стоянов
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
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 неуспешни тест(а)
Борис Алтънов
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
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:
                if i % 2 == 0:
                    return True
                else:
                    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 неуспешни тест(а)
Георги Данков
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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
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:
            i += 1
        elif right[j] == 0:
            j += 1
        elif left[i] <= right[j]:
            sorted_array.append(left[i])
            i += 1
        elif left[i] > right[j]:
            sorted_array.append(right[j])
            count += left_length - i
            j += 1

    sorted_array += left[i:]
    sorted_array += right[j:]

    return sorted_array, count
......
----------------------------------------------------------------------
Ran 6 tests in 0.242s

OK
Алекс Николов
  • Коректно
  • 6 успешни тест(а)
  • 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
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 неуспешни тест(а)
Александрина Ламбова
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
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 неуспешни тест(а)
Николай Желязков
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
49
50
51
52
53
54
55
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 неуспешни тест(а)
Кристина Христакиева
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
49
50
51
52
53
54
55
56
57
58
59
60
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 неуспешни тест(а)
Димитър Керезов
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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
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 неуспешни тест(а)
Кристофър Митов
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
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 неуспешни тест(а)
Георги Иванов
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
49
50
51
52
53
54
55
56
57
58
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 неуспешни тест(а)
Хризантема Станчева
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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
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:
            pass

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

OK
Данислав Киров
  • Коректно
  • 6 успешни тест(а)
  • 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
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 неуспешни тест(а)
Николай Мантаров
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
49
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 неуспешни тест(а)
Ивелина Христова
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
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 неуспешни тест(а)
Даниел Делчев
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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
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
    i = 0
    while i < length and not found:
        for j in range(0, length):
            if rev[i*length+j] == 0:
                index = i
                found = True
        i += 1
    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 неуспешни тест(а)
Илиан Стаменов
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
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 неуспешни тест(а)
Андрей Иванов
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
49
50
51
52
53
54
55
56
57
58
59
60
61
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 = []
        k = 0
        for i in range(0, self.size):
            helper = []
            for j in range(0, self.size):
                helper.append(l[k])
                k = k + 1
            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 неуспешни тест(а)
Николай Бабулков
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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:
                inv += 1

    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 неуспешни тест(а)
Светомир Стоименов
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
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 неуспешни тест(а)
Веселин Иванов
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
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)