出一个leetcode hard编程题

[TheMatrix]

在二维的方格上画类似俄罗斯方块的block，每个block由小方块组成，每个小方块有坐标。block必须是联通的。联通的意思是小方块之间两两连接。两个小方块之间连接，定义为其坐标x相等y相差1，或者y相等x相差1。

写一个程序，给定block中小方块个数，输出全部不同的block的数量，要求满足平移旋转不变性，也就是两个block如果平移或旋转之后重合，那么认为是同一个block。

可以用AI。但是如果不知道答案的话，也不能判定AI的结果是否正确。我让ChatGPT做了几次都是错的，最后才做对。

[TheMatrix]

在二维的方格上画类似俄罗斯方块的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)

[TheMatrix]

functools/itertools 版本 - no loop：

这应该算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)

[ɓuoɥɔɓuɐnɥ]

5层tab，代码审查直接被咔嚓

[TheMatrix]

5层tab，代码审查直接被咔嚓

那就这样：

代码： 全选

    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
    ]

[baba]

直接问chatgpt不香吗？

[TheMatrix]

直接问chatgpt不香吗？

也可以。但是它可能会给出错的答案。你也不知道对不对。

[baba]

哦

也可以。但是它可能会给出错的答案。你也不知道对不对。

[TheMatrix]

在二维的方格上画类似俄罗斯方块的block，每个block由小方块组成，每个小方块有坐标。block必须是联通的。联通的意思是小方块之间两两连接。两个小方块之间连接，定义为其坐标x相等y相差1，或者y相等x相差1。

写一个程序，给定block中小方块个数，输出全部不同的block的数量，要求满足平移旋转不变性，也就是两个block如果平移或旋转之后重合，那么认为是同一个block。

可以用AI。但是如果不知道答案的话，也不能判定AI的结果是否正确。我让ChatGPT做了几次都是错的，最后才做对。

7个方块的block，去除旋转和镜像对称性，总共108个。5X5之内的有102个：

[Rabboni]

孤最烦这种对称旋转群了。

[TheMatrix]

[wdong]

7个方块的block，去除旋转和镜像对称性，总共108个。5X5之内的有102个：

妙！送到stable diffusion里diffuse一下肯定更妙！

[lq558]

孤最烦这种对称旋转群了。

婲媌8964:“LOL！包叔一晚双飞萧美琴和蔡英文LOL！！让这俩台独不停旋转LOL！！！”

[TheMatrix]

有很多动物图标：

[bihai]

在二维的方格上画类似俄罗斯方块的block，每个block由小方块组成，每个小方块有坐标。block必须是联通的。联通的意思是小方块之间两两连接。两个小方块之间连接，定义为其坐标x相等y相差1，或者y相等x相差1。

写一个程序，给定block中小方块个数，输出全部不同的block的数量，要求满足平移旋转不变性，也就是两个block如果平移或旋转之后重合，那么认为是同一个block。

可以用AI。但是如果不知道答案的话，也不能判定AI的结果是否正确。我让ChatGPT做了几次都是错的，最后才做对。

明白，5个块有12种，可以拼成一个长方形，叫亚特兰蒂斯方块

[TheMatrix]

明白，5个块有12种，可以拼成一个长方形，叫亚特兰蒂斯方块

这12个5-block能拼成一个长方形？有意思。

[TheMatrix]

这12个5-block能拼成一个长方形？有意思。

很难拼出长方形：

[TheMatrix]

[TheMatrix]

哦。5-block排长方形的游戏好像不是用全部的12个不同的，而且每个只能用一次。好像是可以重复使用的，而且不一定全要用到。

chatgpt给了一个python程序生成了一个答案，就是这个情况。

[TheMatrix]

哦。5-block排长方形的游戏好像不是用全部的12个不同的，而且每个只能用一次。好像是可以重复使用的，而且不一定全要用到。

chatgpt给了一个python程序生成了一个答案，就是这个情况。

不对。它给的程序输入有一个重复的block，把那个重复的换掉就正确了。



这是它的程序。我改了它的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行。烈害！