master

分支 (1)

管理

管理

master

ThreePlusOneGame
/
loop clusts 1st.html

<!DOCTYPE html>
<html lang="en">
  <head>
    <!-- <meta http-equiv="Content-Type" content="text/html" /> -->
    <meta charset="utf-8" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>Show All circle in 3n+1 Hex Matrix</title>
  </head>

  <body>
    <header>
      <p>When B_LEN = 7 :</p>
      <div>
        <p>Clust: 0000000, size: 1</p>
        <p>Clust: 5555555, size: 1</p>
        <p>Clust: 3333333, size: 4</p>
        <p>Clust: 0000014, size: 55986</p>
        <p>Clust: 0000030, size: 111972</p>
        <p>Clust: 0000304, size: 111972</p>
      </div>
    </header>
    <button>Close All</button>
    <main></main>
  </body>

  <style>
    :root {
      --FONT-SIZE: 18px;
      --C-WHITE: #f3f3f3;
      --C-BLACK: #333;
      --C-RED: #f99;
      --C-GREEN: #9f9;
      --C-BLUE: #99f;
      --C-GRAY: #666;
    }

    body {
      overflow: scroll;
      background-color: var(--C-BLACK);
      color: var(--C-WHITE);
      font-family: Consolas, "Courier New", monospace;
    }

    header div{
      text-indent: 2em;
    }

    details {
      margin: 1em auto;
      padding: 0.5em 0.5em 0;
      border: 1px solid var(--C-WHITE);
      border-radius: 4px;
      overflow-wrap: break-word; /* 允许在单词内部换行 */
      white-space: pre-wrap; /* 保留空白符，但允许换行 */
      text-overflow: ellipsis; /* 溢出时显示省略号 */
      hyphens: auto; /* 自动添加连字符 */
    }

    summary {
      font-weight: bold;
      margin: -0.5em -0.5em 0;
      padding: 0.5em;
    }

    details[open] {
      padding: 0.5em;
    }

    details[open] summary {
      border-bottom: 1px solid var(--C-WHITE);
      margin-bottom: 0.5em;
    }
  </style>

  <script type="module" src="./tpo2n.mjs"></script>
  <script type="module">
    "use strict";
    // import { next2 } from "./tpo2n.mjs";
    import { nx } from "./tpo2n.mjs";

    // 轮环形检测
    const unitCircle = (nums, target) => {
      if (nums.length !== target.length) return { nums: nums, bool: false };
      let b, i, x;
      for (b = 0; b < target.length; b++) {
        if (nums[b] !== target[0]) continue;
        for (i = 1; i < target.length; i++) {
          x = (i + b) % nums.length;
          // console.log(`b ${b},i ${i},x ${x},nums[${x}]:${nums[x]},target[${i}]:${target[i]}`);
          if (nums[x] !== target[i]) break;
        }
        if (i === target.length) return { nums: target, bool: true };
      }
      return { nums: nums, bool: false };
    };
    // 测试数据集合1
    const testUnits1 = [
      { nums: [1, 1, 1, 1], target: [1, 1, 1, 1, 1], bool: false },
      { nums: [1, 1, 1, 1, 1], target: [1, 1, 1, 1, 1], bool: true },
      { nums: [0, 1, 1, 1, 1], target: [1, 1, 1, 1, 0], bool: true },
      { nums: [1, 1, 0, 1, 1], target: [1, 1, 1, 0, 1], bool: true },
      { nums: [0, 1, 0, 1, 1], target: [1, 0, 1, 1, 0], bool: true },
      { nums: [1, 2, 3, 4, 5], target: [5, 1, 2, 3, 4], bool: true },
      { nums: [2, 3, 4, 5, 1], target: [4, 5, 1, 2, 3], bool: true },
      { nums: [0, 0, 1, 1, 1], target: [1, 1, 1, 1, 0], bool: false },
      { nums: [1, 2, 3, 4, 5], target: [1, 2, 4, 3, 5], bool: false },
      { nums: [1, 2, 3, 4, 5], target: [5, 1, 2, 4, 3], bool: false },
    ];
    // 校验测试测试数据集合1
    testUnits1.forEach((tu) => {
      const isCircle = unitCircle(tu.nums, tu.target);
      if (isCircle.bool !== tu.bool) {
        alert("test faild!!!");
        const p = document.createElement("p");
        p.textContent =
          `test faild!!! n1:${n1.join("")},n2:${n2.join("")}` +
          `,want:${tu.bool},got:${isCircle.bool}`;
        p.style.color = "red";
        document.body.appendChild(p);
      }
    });

    // =================================================================
    const B_WID = 3; // 一个字字长 2^3
    const B_LEN = 5; // 数字串长，也是循环数
    const BIT_LIM = [0, 5]; // 3n + 1 的取值
    const MASK = 7; // 掩码 2^3 - 1
    const DEBUG_LINES = 10;
    // 在数据量大时 Map 的查找更快些

    // 聚类标识
    const CLUST_MAP = new Map();
    /*
        CLUST_MAP.count = 0;
        // 加计数器，以免迭代超额
        CLUST_MAP.addCount = (cnt) => {
          if (cnt <= CLUST_MAP.count) return CLUST_MAP.count;
          return ++CLUST_MAP.count;
        };
        // 测试 CLUST_MAP.addCount
        for (let idx = 0; idx < 10; idx++) {
          // 不会超过 5
          console.log("CLUST_MAP.addCount()", CLUST_MAP.addCount(5));
        }
        */
    CLUST_MAP.debug = () => {
      let str = "\n\n CLUST_MAP: \n\n";
      let count = 0;
      for (const [hash, { nums, clust }] of CLUST_MAP) {
        str +=
          `i: ${count} ,{hash: ${hash} ,` +
          `nums: ${nums.join("")} ,clust: ${clust} },\n`;
        count++;
        if (count === DEBUG_LINES) break;
      }
      return str + ".........\n\n";
    };

    // 位轮环标识
    const CIRCLE_MAP = new Map();
    CIRCLE_MAP.targets = () =>
      new Set(CIRCLE_MAP.values().map(({ target }) => target));
    CIRCLE_MAP.debug = () => {
      let str = "\n\n CIRCLE_MAP: \n\n";
      let count = 0;
      for (const [hash, { nums, target }] of CIRCLE_MAP) {
        str +=
          `i: ${count} ,{hash: ${hash} ,` +
          `nums: ${nums.join("")} ,target: ${target} },\n`;
        count++;
        if (count === DEBUG_LINES) break;
      }
      str += "\n.........\n\n";
      str += "\n target size:" + CIRCLE_MAP.targets().size + "\n";
      return str;
    };

    // 生成环标识
    const LOOPS_MAP = new Map();
    LOOPS_MAP.targets = () =>
      new Set(LOOPS_MAP.values().map(({ target }) => target));
    LOOPS_MAP.debug = () => {
      let str = "\n\n LOOPS_MAP: \n\n";
      let count = 0;
      for (const [hash, { nums, next }] of LOOPS_MAP) {
        str +=
          `i: ${count} ,{hash: ${hash} ,` +
          `nums: ${nums.join("")} ,next: ${next} },\n`;
        count++;
        if (count === DEBUG_LINES) break;
      }
      str += "\n.........\n\n";
      str += "\n target size:" + LOOPS_MAP.targets().size + "\n";
      return str;
    };

    // 压缩与解压缩
    const compressHex = (nums) => {
      let rtn = 0;
      for (let i = 0; i < nums.length; i++) {
        rtn = (rtn << B_WID) | nums[i];
      }
      return rtn;
    };
    const decompressHex = (num) => {
      let rtn = [];
      while (num > 0) {
        rtn.unshift(num & MASK);
        num = num >> B_WID;
      }
      return rtn;
    };

    // 测试数据压缩解压
    [
      [1, 2, 3, 4],
      [6, 4, 3, 2],
      [5, 0, 2, 1],
    ].forEach((nums) => {
      const n = compressHex(nums);
      const n2 = decompressHex(n);
      if (n === compressHex(n2)) return null;
      console.log("========com/de press test==========");
      console.log(`${nums} -> ${n}`);
      console.log(`${n} -> ${n2}`);
      alert("compressHex / decompress error");
    });

    /**
     *  用于测试
     */
    const clsi = (...args) => {
      console.log(...args);
      console.count("clsi times");
    };

    /**
     *  for循环用函数式外包一层
     *  (s, t) 循环限制次数 strat terminal
     *  返回一个执行函数的函数
     *  (fn, ...args) =>  {fn: CallBack函数, args:参数集合}
     */
    const forPP =
      (s, t) =>
      (fn, ...args) => {
        for (let i = s; i <= t; i++) {
          fn(...args.concat(i));
        }
      };

    // forPP(1, 6)(clsi);
    // forPP(1, 6)((idx) => forPP(1, 6)(clsi, idx));
    // forPP(1, 6)((jdx) => forPP(1, 6)((idx) => forPP(1, 6)(clsi, idx, jdx)));

    /**
     * forPP函数的递归包裹函数
     * w 包裹的层数
     * s t forPP的start terminal
     * 返回值与forPP返回值格式相同，返回一个执行函数的函数
     * (fn, ...args) =>  {fn: CallBack函数, args:参数集合}
     */
    const forWraper = (w, s, t) => {
      // 层数为0
      if (w === 0)
        return (fn, ...args) => {
          fn(...args);
        };

      return (fn, ...args) =>
        // 层数递减 w - 1
        forPP(s, t)((i) => forWraper(w - 1, s, t)(fn, ...args.concat(i)));
    };

    // forWraper(3, 1, 3)(clsi);
    // forWraper(5, 1, 6)(clsi);

    // 获取当前序列所有的轮环形式
    const initCircleMap = (nums) => {
      if (CIRCLE_MAP.has(compressHex(nums))) return null;

      let minHash = Number.POSITIVE_INFINITY;
      const circle = [];
      for (let i = 0; i < nums.length; i++) {
        const numsi = nums.slice(i).concat(nums.slice(0, i));
        const hashi = compressHex(numsi);
        minHash = Math.min(hashi, minHash);
        circle.push({ hash: hashi, nums: numsi });
      }

      for (let i = 0; i < circle.length; i++) {
        CIRCLE_MAP.set(circle[i].hash, {
          nums: circle[i].nums,
          target: minHash,
        });
      }
    };

    forWraper(B_LEN, ...BIT_LIM)((...nums) => initCircleMap(nums));

    console.debug(
      `\n CIRCLE_MAP size:${CIRCLE_MAP.size}`,
      CIRCLE_MAP,
      CIRCLE_MAP.debug(),
      CIRCLE_MAP.targets()
    );

    const getNext = (nums) => {
      const next = [];
      for (let i = 0; i <= nums.length - 2; i++) {
        next.push(nx(nums[i], nums[i + 1]));
      }
      next.push(nx(nums[nums.length - 1], nums[0]));
      return next;
    };

    // 测试数据
    [
      [0, 0, 0],
      [0, 0, 1],
      [0, 1, 0],
      [1, 0, 0],
    ].forEach((nums) => console.log("\n  test getNext", nums, getNext(nums)));

    // 创建环形链表
    const createLoopsMap = (nums) => {
      let nextHash = compressHex(nums);
      let prevNums = nums;
      let nextNums;
      let minHash = Number.POSITIVE_INFINITY;
      const loop = new Map();
      while (!loop.has(nextHash)) {
        // debugger;
        let hash = nextHash;
        nextNums = getNext(prevNums);
        nextHash = compressHex(nextNums);
        minHash = Math.min(hash, minHash);
        loop.set(hash, { nums: nextNums, next: nextHash });
        prevNums = nextNums;
      }

      for (const [key, val] of loop) {
        LOOPS_MAP.set(key, {
          nums: val.nums,
          next: val.next,
          target: minHash,
        });
      }

      loop.clear();
    };

    for (const [hash, { nums }] of CIRCLE_MAP) {
      if (!LOOPS_MAP.has(hash)) createLoopsMap(nums);
    }

    console.debug(
      `\n LOOPS_MAP size:${LOOPS_MAP.size}`,
      LOOPS_MAP,
      LOOPS_MAP.debug(),
      LOOPS_MAP.targets()
    );

    // 获取环形链表所属的集群
    const mathClustMap = (hash) => {
      if (CLUST_MAP.has(hash)) return null;

      const tgC = CIRCLE_MAP.get(hash).target;
      const tgLs = Array.from(CIRCLE_MAP)
        .filter(([_, { target }]) => target === tgC)
        .map(([hash]) => LOOPS_MAP.get(hash).target);

      const minTg = Math.min(...tgLs);

      Array.from(LOOPS_MAP)
        .filter(([_, { target }]) => tgLs.includes(target))
        .forEach(([hash, { nums }]) =>
          CLUST_MAP.set(hash, { nums: nums, clust: minTg })
        );
    };

    for (const [hash] of LOOPS_MAP) {
      mathClustMap(hash);
    }

    console.debug(
      `\n CLUST_MAP size:${CLUST_MAP.size}`,
      CLUST_MAP,
      CLUST_MAP.debug()
    );

    // 集群结果梳理
    const CLUSTORS = {};
    for (const [hash, { nums, clust }] of CLUST_MAP) {
      if (!CLUSTORS[clust]) CLUSTORS[clust] = [];
      CLUSTORS[clust].push({ hash, nums: nums.join("") });
    }
    // 按hash排序
    for (const arr of Object.values(CLUSTORS)) {
      arr.sort((a, b) => a.hash - b.hash);
    }
    console.debug(`\n CLUSTORS size:${Object.keys(CLUSTORS).length}`, CLUSTORS);

    // 网页输出
    const c_arr = Object.entries(CLUSTORS);
    // 集群按元素所含个数大小排序
    c_arr.sort((a, b) => a[1].length - b[1].length);

    const mainTag = document.getElementsByTagName("main")[0];
    for (const [key, val] of c_arr) {
      let str = "";
      str += `<details open><summary>Clust: ${val[0].nums}, `;
      str += `size: ${val.length}</summary>`;
      str += val.map((e) => e.nums).join(",");
      str += "</details>";
      mainTag.innerHTML += str;
    }

    // details 全控制按钮
    const btn = document.getElementsByTagName("button")[0];
    const details = Array.from(document.getElementsByTagName("details"));

    const cls_a = "Close All";
    const opn_a = "Open All";
    btn.addEventListener("click", (e) => {
      if (btn.textContent === cls_a) {
        details.forEach((e) => (e.open = false));
        btn.textContent = opn_a;
      } else if (btn.textContent === opn_a) {
        details.forEach((e) => (e.open = true));
        btn.textContent = cls_a;
      }
    });
  </script>
</html>