{ "nbformat": 4, "nbformat_minor": 0, "metadata": { "colab": { "provenance": [] }, "kernelspec": { "name": "python3", "display_name": "Python 3" }, "language_info": { "name": "python" } }, "cells": [ { "cell_type": "code", "execution_count": null, "metadata": { "id": "oB5W0LdeIBrs" }, "outputs": [], "source": [ "from utils import (\n", " to_tuple_set, to_list, is_connected, is_move_connected, build_response, make_step_info\n", ")\n", "\n", "# ============================================================\n", "# 1. HÀM THẾ NĂNG CHÍNH XÁC THEO BÀI BÁO (Strict Potential)\n", "# ============================================================\n", "def calculate_weight(c_y, c_z):\n", " \"\"\"Tính trọng số w_c dựa trên tọa độ y và z theo đúng định nghĩa bài báo.\"\"\"\n", " if c_z > 1:\n", " return 17\n", " if c_z == 1:\n", " return 16\n", " # Nếu c_z == 0\n", " if c_y > 1:\n", " return 3\n", " if c_y == 1:\n", " return 2\n", " return 1 # c_z = 0 và c_y = 0\n", "\n", "def exact_potential(blocks_set):\n", " \"\"\"\n", " Tính tổng thế năng dựa trên công thức: \\Pi_C = \\sum w_c(x + 2y + 4z)\n", " \"\"\"\n", " total = 0\n", " for x, y, z in blocks_set:\n", " w_c = calculate_weight(y, z)\n", " total += w_c * (x + 2 * y + 4 * z)\n", " return total\n", "\n", "# ============================================================\n", "# 2. BỘ THỰC THI MACRO-MOVE (Macro-Move Engine)\n", "# ============================================================\n", "def apply_macro_move(blocks_set, move_sequence, get_move_type_func):\n", " \"\"\"\n", " Thực thi một kịch bản chuỗi các bước đi.\n", " Bỏ qua việc kiểm tra thế năng trung gian, chỉ cần đảm bảo cuối cùng\n", " chuỗi này là \"safe\" (tổng thế năng giảm) và không làm đứt gãy hệ thống.\n", " \"\"\"\n", " curr_blocks = set(blocks_set)\n", " steps_taken = []\n", "\n", " for c, e in move_sequence:\n", " move_type = get_move_type_func(c, e, curr_blocks)\n", " # Bắt buộc phải là move hợp lệ và duy trì liên thông\n", " if not move_type or not is_move_connected(curr_blocks, c, e, 3):\n", " return None, False\n", "\n", " next_blocks = set(curr_blocks)\n", " next_blocks.remove(c)\n", " next_blocks.add(e)\n", "\n", " steps_taken.append((c, e, move_type, next_blocks))\n", " curr_blocks = next_blocks\n", "\n", " return curr_blocks, steps_taken\n", "\n", "# ============================================================\n", "# 3. MÔ HÌNH HÓA SUBPILLAR VÀ CÁC OPERATION [a]-[d] TRONG 3D\n", "# ============================================================\n", "def get_subpillars_3d(blocks_set):\n", " \"\"\"Tìm tất cả các cột P = \"\"\"\n", " columns = {}\n", " for x, y, z in blocks_set:\n", " columns.setdefault((x, y), []).append(z)\n", "\n", " subpillars = []\n", " for (x, y), zs in columns.items():\n", " zs = sorted(zs)\n", " start = prev = zs[0]\n", " for z in zs[1:]:\n", " if z == prev + 1:\n", " prev = z\n", " else:\n", " subpillars.append({'x': x, 'y': y, 'z_b': start, 'z_t': prev})\n", " start = prev = z\n", " subpillars.append({'x': x, 'y': y, 'z_b': start, 'z_t': prev})\n", " return subpillars\n", "\n", "def operation_local_z_reduction(blocks_set):\n", " \"\"\"\n", " Tương đương Operation [a], [b], [c], [d].\n", " Nhắm vào việc giảm z của các non-cut subpillar.\n", " \"\"\"\n", " subpillars = get_subpillars_3d(blocks_set)\n", "\n", " for P in subpillars:\n", " x, y, z_b, z_t = P['x'], P['y'], P['z_b'], P['z_t']\n", "\n", " # Bỏ qua nếu P là cut-subpillar (gỡ ra làm đứt hệ thống)\n", " # Giả định có hàm is_non_cut_subpillar_3d\n", " if not is_non_cut_subpillar_3d(blocks_set, x, y, z_b, z_t):\n", " continue\n", "\n", " # Duyệt 4 mặt bên (sides) của P trong 3D: (x-1,y), (x+1,y), (x,y-1), (x,y+1)\n", " sides = [(x-1, y), (x+1, y), (x, y-1), (x, y+1)]\n", " for s_x, s_y in sides:\n", " # Lấy cột kề (P') cao nhất hoặc thấp nhất ở mặt này\n", " P_prime = get_adjacent_pillar(blocks_set, s_x, s_y)\n", " if not P_prime: continue\n", "\n", " p_z_b, p_z_t = P_prime['z_b'], P_prime['z_t']\n", "\n", " # [Operation A] Ném đỉnh cột xuống nếu cột kề đủ thấp\n", " if p_z_t <= z_t - 2:\n", " c = (x, y, z_t)\n", " e = (s_x, s_y, z_t - 1) # Rơi chéo qua (convex)\n", " return \"op_a\", [(c, e)]\n", "\n", " # [Operation B] Cột kề có đáy cao hơn đáy P (z_b' > z_b)\n", " if p_z_b > z_b:\n", " c_under = (x, y, p_z_b - 1)\n", " c_base = (x, y, p_z_b)\n", "\n", " if is_non_cut(blocks_set, c_under) and is_non_cut(blocks_set, c_base):\n", " return \"op_b_normal\", [\n", " (c_under, (s_x, s_y, p_z_b - 1)),\n", " (c_base, c_under)\n", " ]\n", " # Nếu bị vướng đỉnh (locked), mở khóa đỉnh trước rồi trượt\n", " elif not is_non_cut(blocks_set, c_base) and p_z_b == z_t - 1:\n", " return \"op_b_unlock\", [\n", " ((x, y, z_t), (s_x, s_y, z_t)), # Unlock (làm tăng thế năng tạm thời)\n", " (c_under, (s_x, s_y, p_z_b - 1)),\n", " (c_base, c_under)\n", " ]\n", "\n", " is_based = (x, y, z_b - 1) not in blocks_set\n", "\n", " # [Operation C] Cột chạm đáy, đáy kề lún sâu hơn\n", " if is_based and p_z_b < z_b:\n", " seq = []\n", " if is_locked(blocks_set, x, y, z_t):\n", " seq.append(((x, y, z_t), (s_x, s_y, z_t))) # Unlock\n", " seq.append(((x, y, z_b), (x, y, z_b - 1))) # Tụt xuống\n", " return \"op_c\", seq\n", "\n", " # [Operation D] Cột chạm đáy, đáy kề bằng nhau\n", " if is_based and p_z_b == z_b and z_b > 0:\n", " seq = []\n", " if is_locked(blocks_set, x, y, z_t):\n", " seq.append(((x, y, z_t), (s_x, s_y, z_t))) # Unlock\n", " seq.append(((x, y, z_b), (s_x, s_y, p_z_b - 1))) # Lật qua góc\n", " return \"op_d\", seq\n", "\n", " return None, []\n", "\n", "# ============================================================\n", "# 4. LUỒNG THỰC THI CHÍNH (Exact Pipeline)\n", "# ============================================================\n", "def compact_3d_exact(blocks, max_steps):\n", " blocks_set = to_tuple_set(blocks)\n", " steps = []\n", "\n", " # 1. Trạng thái khởi tạo\n", " pot_initial = exact_potential(blocks_set)\n", " # ... (Lưu info tương tự mã cũ)\n", "\n", " while len(steps) < max_steps:\n", " if is_finished_3d(blocks_set):\n", " break\n", "\n", " # Thử chuỗi Local z-reduction [a-d]\n", " op_name, move_seq = operation_local_z_reduction(blocks_set)\n", "\n", " if move_seq:\n", " # Thực thi chuỗi vĩ mô thay vì 1 bước\n", " blocks_set, detailed_steps = apply_macro_move(blocks_set, move_seq, get_move_type_3d)\n", " if detailed_steps:\n", " steps.extend(detailed_steps)\n", " continue\n", "\n", " # Thử Pillar Shove [e]\n", " # op_name, move_seq = operation_pillar_shove(blocks_set)\n", " # ...\n", "\n", " # Thử High Components Reduction [f]\n", " # ...\n", "\n", " # Nếu duyệt hết các Operation [a]-[j] mà không có move nào -> Bị kẹt\n", " break\n", "\n", " # Đóng gói Response...\n", " return build_response(...)" ] } ] }