出一个leetcode hard编程题
版主: verdelite, TheMatrix
-
- 论坛支柱
2024年度优秀版主
TheMatrix 的博客 - 帖子互动: 279
- 帖子: 13710
- 注册时间: 2022年 7月 26日 00:35
#1 出一个leetcode hard编程题
在二维的方格上画类似俄罗斯方块的block,每个block由小方块组成,每个小方块有坐标。block必须是联通的。联通的意思是小方块之间两两连接。两个小方块之间连接,定义为其坐标x相等y相差1,或者y相等x相差1。
写一个程序,给定block中小方块个数,输出全部不同的block的数量,要求满足平移旋转不变性,也就是两个block如果平移或旋转之后重合,那么认为是同一个block。
可以用AI。但是如果不知道答案的话,也不能判定AI的结果是否正确。我让ChatGPT做了几次都是错的,最后才做对。
写一个程序,给定block中小方块个数,输出全部不同的block的数量,要求满足平移旋转不变性,也就是两个block如果平移或旋转之后重合,那么认为是同一个block。
可以用AI。但是如果不知道答案的话,也不能判定AI的结果是否正确。我让ChatGPT做了几次都是错的,最后才做对。
-
- 论坛支柱
2024年度优秀版主
TheMatrix 的博客 - 帖子互动: 279
- 帖子: 13710
- 注册时间: 2022年 7月 26日 00:35
#2 Re: 出一个leetcode hard编程题
我的版本:TheMatrix 写了: 2025年 3月 4日 20:12 在二维的方格上画类似俄罗斯方块的block,每个block由小方块组成,每个小方块有坐标。block必须是联通的。联通的意思是小方块之间两两连接。两个小方块之间连接,定义为其坐标x相等y相差1,或者y相等x相差1。
写一个程序,给定block中小方块个数,输出全部不同的block的数量,要求满足平移旋转不变性,也就是两个block如果平移或旋转之后重合,那么认为是同一个block。
可以用AI。但是如果不知道答案的话,也不能判定AI的结果是否正确。我让ChatGPT做了几次都是错的,最后才做对。
代码: 全选
#a block is a list of positions, e.g. [(0,1), (1,1), (2,1), (2,0)].
def normalize(block):
"""
normalize the block to start from (0,0) corner
"""
min_x = min(x for x,y in block)
min_y = min(y for x,y in block)
block = [(x-min_x, y-min_y) for x,y in block]
return sorted(block)
def rotation_set(block):
"""
generate the set of 4 rotations of a block
return tuple of sorted to use as keys of a dictionary
"""
rotations = [tuple(block)]
for i in range(3):
block = [(-y,x) for x,y in block]
rotations.append(tuple(normalize(block)))
return tuple(sorted(rotations))
def unique_blocks(n):
nblocks = [[(0,0)]]
for i in range(n-1):
#grow at one cell of a block in 4 directions
nblocks =[
block+[(x+dx, y+dy)]
for block in nblocks
for x,y in block
for dx,dy in [[0,1],[0,-1],[1,0],[-1,0]]
]
#remove invalid grows
nblocks = [block for block in nblocks if len(block) == len(set(block))]
#remove duplicates
nblocks = {tuple(normalize(block)) for block in nblocks}
nblocks = [list(block) for block in nblocks]
#group by rotation_set
nblocks_rotation = {rotation_set(block): block for block in nblocks}
nblocks = nblocks_rotation.values()
return len(nblocks)
if __name__ == "__main__":
nblocks = unique_blocks(5)
print(nblocks)
-
- 论坛支柱
2024年度优秀版主
TheMatrix 的博客 - 帖子互动: 279
- 帖子: 13710
- 注册时间: 2022年 7月 26日 00:35
#3 Re: 出一个leetcode hard编程题
functools/itertools 版本 - no loop:
这应该算completely functional programming吧?
这应该算completely functional programming吧?

代码: 全选
import functools
import itertools
def normalize(block):
min_x = min(x for x,y in block)
min_y = min(y for x,y in block)
block = [(x-min_x, y-min_y) for x,y in block]
return sorted(block)
def rotation(block, _):
return [(-y,x) for x,y in block]
def rotation_set(block):
rotations = itertools.accumulate(range(3), rotation, initial=block)
rotations = [tuple(normalize(block)) for block in rotations]
return tuple(sorted(rotations))
def next_level(pblocks, _):
#grow at one cell of a block in 4 directions
nblocks =[
block+[(x+dx, y+dy)]
for block in pblocks
for x,y in block
for dx,dy in [[0,1],[0,-1],[1,0],[-1,0]]
]
#remove invalid grows
nblocks = [block for block in nblocks if len(block) == len(set(block))]
#remove duplicates
nblocks = {tuple(normalize(block)) for block in nblocks}
nblocks = [list(block) for block in nblocks]
#group by rotation_set
nblocks_rotation = {rotation_set(block): block for block in nblocks}
nblocks = nblocks_rotation.values()
return nblocks
def unique_blocks(n):
nblocks = functools.reduce(next_level, range(n-1), [[(0,0)]])
return len(nblocks)
if __name__ == "__main__":
nblocks = unique_blocks(5)
print(nblocks)
上次由 TheMatrix 在 2025年 3月 5日 21:29 修改。
原因: 未提供修改原因
原因: 未提供修改原因
-
- 论坛支柱
2024年度优秀版主
TheMatrix 的博客 - 帖子互动: 279
- 帖子: 13710
- 注册时间: 2022年 7月 26日 00:35
#5 Re: 出一个leetcode hard编程题
那就这样:
代码: 全选
nblocks =[
block+[(x+dx, y+dy)]
for dx,dy in [[0,1],[0,-1],[1,0],[-1,0]]
for block in pblocks
for x,y in block
]
-
- 论坛支柱
2024年度优秀版主
TheMatrix 的博客 - 帖子互动: 279
- 帖子: 13710
- 注册时间: 2022年 7月 26日 00:35
-
- 论坛支柱
2024年度优秀版主
TheMatrix 的博客 - 帖子互动: 279
- 帖子: 13710
- 注册时间: 2022年 7月 26日 00:35
#9 Re: 出一个leetcode hard编程题
7个方块的block,去除旋转和镜像对称性,总共108个。5X5之内的有102个:TheMatrix 写了: 2025年 3月 4日 20:12 在二维的方格上画类似俄罗斯方块的block,每个block由小方块组成,每个小方块有坐标。block必须是联通的。联通的意思是小方块之间两两连接。两个小方块之间连接,定义为其坐标x相等y相差1,或者y相等x相差1。
写一个程序,给定block中小方块个数,输出全部不同的block的数量,要求满足平移旋转不变性,也就是两个block如果平移或旋转之后重合,那么认为是同一个block。
可以用AI。但是如果不知道答案的话,也不能判定AI的结果是否正确。我让ChatGPT做了几次都是错的,最后才做对。

x1

-
- 论坛支柱
2024年度优秀版主
TheMatrix 的博客 - 帖子互动: 279
- 帖子: 13710
- 注册时间: 2022年 7月 26日 00:35
-
- 论坛支柱
2024年度优秀版主
TheMatrix 的博客 - 帖子互动: 279
- 帖子: 13710
- 注册时间: 2022年 7月 26日 00:35
#15 Re: 出一个leetcode hard编程题
明白,5个块有12种,可以拼成一个长方形,叫亚特兰蒂斯方块TheMatrix 写了: 2025年 3月 4日 20:12 在二维的方格上画类似俄罗斯方块的block,每个block由小方块组成,每个小方块有坐标。block必须是联通的。联通的意思是小方块之间两两连接。两个小方块之间连接,定义为其坐标x相等y相差1,或者y相等x相差1。
写一个程序,给定block中小方块个数,输出全部不同的block的数量,要求满足平移旋转不变性,也就是两个block如果平移或旋转之后重合,那么认为是同一个block。
可以用AI。但是如果不知道答案的话,也不能判定AI的结果是否正确。我让ChatGPT做了几次都是错的,最后才做对。
-
- 论坛支柱
2024年度优秀版主
TheMatrix 的博客 - 帖子互动: 279
- 帖子: 13710
- 注册时间: 2022年 7月 26日 00:35
-
- 论坛支柱
2024年度优秀版主
TheMatrix 的博客 - 帖子互动: 279
- 帖子: 13710
- 注册时间: 2022年 7月 26日 00:35
-
- 论坛支柱
2024年度优秀版主
TheMatrix 的博客 - 帖子互动: 279
- 帖子: 13710
- 注册时间: 2022年 7月 26日 00:35
-
- 论坛支柱
2024年度优秀版主
TheMatrix 的博客 - 帖子互动: 279
- 帖子: 13710
- 注册时间: 2022年 7月 26日 00:35
-
- 论坛支柱
2024年度优秀版主
TheMatrix 的博客 - 帖子互动: 279
- 帖子: 13710
- 注册时间: 2022年 7月 26日 00:35
#20 Re: 出一个leetcode hard编程题
不对。它给的程序输入有一个重复的block,把那个重复的换掉就正确了。TheMatrix 写了: 2025年 3月 8日 21:42 哦。5-block排长方形的游戏好像不是用全部的12个不同的,而且每个只能用一次。好像是可以重复使用的,而且不一定全要用到。
chatgpt给了一个python程序生成了一个答案,就是这个情况。

这是它的程序。我改了它的W-block:
代码: 全选
def normalize(shape):
min_r = min(r for r, c in shape)
min_c = min(c for r, c in shape)
return tuple(sorted(((r - min_r, c - min_c) for r, c in shape)))
def rotate(shape):
return [(c, -r) for r, c in shape]
def all_orientations(shape):
orientations = set()
current = shape
for _ in range(4):
current = normalize(current)
orientations.add(current)
reflected = normalize([(r, -c) for r, c in current])
orientations.add(reflected)
current = rotate(current)
return [list(orientation) for orientation in orientations]
pieces = {
'F': [(0,1), (1,0), (1,1), (1,2), (2,2)],
'I': [(0,0), (1,0), (2,0), (3,0), (4,0)],
'L': [(0,0), (1,0), (2,0), (3,0), (3,1)],
'N': [(0,1), (1,1), (2,1), (2,0), (3,0)],
'P': [(0,0), (0,1), (1,0), (1,1), (2,0)],
'T': [(0,0), (0,1), (0,2), (1,1), (2,1)],
'U': [(0,0), (0,2), (1,0), (1,1), (1,2)],
'V': [(0,0), (1,0), (2,0), (2,1), (2,2)],
#'W': [(0,0), (1,0), (1,1), (2,1), (2,2)],
'W': [(0,0), (1,0), (1,1), (1,2), (2,2)],
'X': [(0,1), (1,0), (1,1), (1,2), (2,1)],
'Y': [(0,1), (1,1), (2,1), (3,1), (2,0)],
'Z': [(0,0), (0,1), (1,1), (1,2), (2,2)]
}
piece_orientations = {letter: all_orientations(shape) for letter, shape in pieces.items()}
BOARD_ROWS = 6
BOARD_COLS = 10
def print_board(board):
for row in board:
print(''.join(row))
print()
def find_next_empty(board):
for r in range(BOARD_ROWS):
for c in range(BOARD_COLS):
if board[r][c] == '.':
return r, c
return None, None
def can_place(board, shape, top, left):
positions = []
for dr, dc in shape:
r, c = top + dr, left + dc
if r < 0 or r >= BOARD_ROWS or c < 0 or c >= BOARD_COLS:
return None
if board[r][c] != '.':
return None
positions.append((r, c))
return positions
def solve(board, remaining, solutions):
pos = find_next_empty(board)
if pos == (None, None):
solutions.append([row[:] for row in board])
return True
r, c = pos
for letter in list(remaining):
for orientation in piece_orientations[letter]:
for (dr, dc) in orientation:
top = r - dr
left = c - dc
positions = can_place(board, orientation, top, left)
if positions is not None:
for pr, pc in positions:
board[pr][pc] = letter
remaining.remove(letter)
if solve(board, remaining, solutions):
return True
remaining.add(letter)
for pr, pc in positions:
board[pr][pc] = '.'
return False
def main():
board = [['.' for _ in range(BOARD_COLS)] for _ in range(BOARD_ROWS)]
remaining = set(pieces.keys())
solutions = []
if solve(board, remaining, solutions):
print("found")
print_board(solutions[0])
else:
print("not found")
if __name__ == '__main__':
main()
这种“布局”问题是很难编程的。我想不出来怎么编。而它这个程序只有不到100行。烈害!