赛题名称：Santa 2023 - The Polytope Permutation Puzzle 赛题类型：优化算法 赛题任务：确定所有谜题解决方案中的移动总数，其目标是最小化这个数字
https://www.kaggle.com/competitions/santa-2023
比赛任务
任务类型： 优化算法 任务描述： 确定所有谜题解决方案中的移动总数，目标是最小化这个数字。谜题是通过对颜色符号排列进行置换来解决的，其中包括通配符的概念。
评测指标
评测过程： 通过确定所有谜题解决方案中的移动总数来评估性能。 评价指标： 总体得分，即所有谜题解决方案中的移动总数。目标是在尽量少的移动中解决所有给定的谜题。
数据集介绍
文件列表： id：对应于puzzles.csv中的谜题。 moves：一个初始的、未经优化的解决方案。 id：每个谜题的唯一标识符。 puzzle_type：对应于puzzle_info.csv中的谜题类型。 solution_state：描述谜题解决状态的颜色排列。 initial_state：描述谜题初始状态的颜色排列。 num_wildcards：解决方案的最终状态中允许的通配符数量。 puzzle_type：标识谜题类型。 allowed_moves：描述谜题类型解决方案中允许的移动。 puzzle_info.csv： 包含谜题类型和允许移动的信息。 puzzle.csv： 包含每个谜题的唯一标识符、谜题类型、解决状态、初始状态和通配符数量。 sample_submission.csv： 包含谜题标识符和初始解决方案的信息。
解题思路
使用puzzle_info.csv中的信息了解每个谜题类型和允许的移动。 在puzzle.csv中找到每个谜题的唯一标识符、初始状态和解决状态。 使用allowed_moves中的移动规则，通过对初始状态应用适当的移动顺序，将其转换为解决状态。 通过最小化移动总数，优化解决方案。考虑到通配符的概念，可能需要重新排列贴纸而不仅仅是应用标准移动。 提交结果，包括每个谜题的最终移动序列。
高分baseline
https://www.kaggle.com/code/shitovvladimir/optimize-any-solution-with-group-theory-approach/notebook
假设你有一系列移动导致了一个解决方案。我们能否在不改变解决方案的情况下使这个序列更短？是的，我们可以！存在一些移动是可以相互取消的，或者可以被更短地表示。
取消移动
如果你先移动一侧，然后再将其反向移动，这不会改变任何东西。'r1.-r1.r0' 等同于 'r0'。这对于任何类型的拼图都是成立的。
魔方的同一移动的4次重复
如果你将魔方的同一面移动4次，那么什么都不会改变。因此，'r1.r1..r1.r1.r0' 等同于 'r0'。
魔方的同一移动的3次重复等同于1次逆向移动
我们可以通过将3次相同面的移动替换为1次逆向移动来使序列变短。例如，'r1.r1.r1.r0' 等同于 '-r1.r0'。
其中一个明显的例子，就是这个笔记本中使用的相同面的移动。每次移动不会影响其他移动的轴，它们是“平行”的。以3x3魔方为例：你可以按任何顺序移动左侧和右侧的面，结果都不会改变。因此，'r1.r0' == 'r0.r1'
。对于应用于相同面的任何长度的序列都是成立的。'r1.r0.r1.r1.r0.-r1' == 'r1.r1.r1.r0.r0.-r1'
。
现在优化序列变得更容易了！我们只需找到移动相同面的子序列，并对每个子序列应用上面描述的优化。以下是算法的示例：
初始解决方案： 'r1.r0.r1.r1.-r0.r1.r1.f1.f0.-f1.r1.r0.r1.r1'分组相同面的子序列： ['r1.r0.r1.r1.-r0.r1.r1', 'f1.f0.-f1', 'r1.r0.r1.r1']对每个子序列应用上述描述的变换进行优化： ['r1', 'f0', '-r1.r0']从第一个序列中删除了4次 'r1'
，并取消了'r0'
和'-r0'从第二个序列中删除了取消对 'f1'
和'-f1'在第三个序列中用 '-r1'
替换了3次'r1'获取优化后的解决方案： 'r1.f0.-r1.r0'
完整的魔方旋转
在https://www.kaggle.com/code/ryanholbrook/getting-started-with-santa-2023/notebook中，对2x2魔方提出了以下优化：
f0 * f1 * r0 * (f1 ** -1) * (f0 ** -1) == d0
这意味着如果你完全旋转了魔方（对于2x2，是 f0 * f1
），然后旋转了一个面（在这个例子中是 r0
），那么结果与仅仅旋转另一个面（d0
）是相同的。想象一下实际的魔方：如果你旋转了它的所有面，你并没有改变它们之间的对应关系。你只是完全旋转了魔方！但因为我们的解决方案需要魔方特定的方向，你需要使用 (f1 ** -1) * (f0 ** -1)
将其完全旋转回来。
基于这一点，我们可以进行以下优化：
如果魔方被完全旋转，舍弃所有这些移动，它们不会改变任何东西。只需在此旋转后仔细更改所有移动的名称。 如果超过半数的魔方面被连续旋转，你可以通过以相反方向旋转其他面来得到相同的结果。例如，对于3x3魔方， f0 * f1
等同于-f2
。这可以为我们节省一个移动！将上述优化应用于所有可交换的群组。最后，正确地将魔方旋转回来。利用一些群论知识，我可以向你保证，3次完整的面旋转总是足够的！因此，对于边长为 n
的魔方，您最多需要3*n
次旋转来正确地将魔方旋转回来。如果您可以通过优化获得更多移动，您将获得更好的分数！
部分代码如下：
def optimize_solution(moves, puzzle="cube"):
"""
在移动序列长度减小的同时应用优化。
Parameters:
- moves (str): 移动序列，表示为字符串。
- puzzle (str): 指定谜题类型，默认为 "cube"。支持的类型包括 "cube" 和 "wreath"。
Returns:
- str: 优化后的移动序列。
"""
groups = group_cube_moves(moves) # 将移动分组，以便进行优化
previous_length = len(moves) # 记录优化前的移动序列长度
keep_optimizing = True # 标志是否继续优化
while keep_optimizing:
if puzzle == "cube":
# 首先尝试尽可能多地删除无意义的移动
groups = [remove_multiples_of_four(group) for group in groups]
groups = regroup(groups) # 如果某些组变为空，其他组可能出现，因此需要重新分组
if puzzle in ("cube", "wreath"):
# 尝试通过取消移动来进一步减少元素数量
groups = [remove_cancelling_pairs(group) for group in groups]
groups = regroup(groups)
if puzzle == "cube":
# 最后，尝试通过替换三重循环来稍微减少序列长度。这不需要重新分组
groups = [substitute_three_for_inverse(group) for group in groups]
moves = groups_to_solution(groups)
keep_optimizing = (len(moves) != previous_length)
previous_length = len(moves)
return moves
