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

Краен срок
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]:
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 неуспешни тест(а)
Мартин Стоев
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:
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 неуспешни тест(а)
Стилиян Стоянов
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:
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 неуспешни тест(а)
Георги Данков
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 неуспешни тест(а)
Алекс Николов
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:
pass
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
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 неуспешни тест(а)
Илиан Стаменов
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 = []
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 неуспешни тест(а)
Николай Бабулков
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 неуспешни тест(а)
Светомир Стоименов
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)