master

分支 (1)

管理

管理

master

ThreePlusOneGame
/
loop clusts 2nd.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 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 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 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;

    // 压缩与解压缩
    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;
      }

      if (rtn.length < B_LEN) {
        rtn = new Array(B_LEN - rtn.length).fill(0).concat(rtn);
      }

      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");
    });

    // 在数据量大时 Map 的查找更快些

    // 位轮环标识
    const CIRCLE = {};
    CIRCLE.hit = new Map(); // 击中集合
    CIRCLE.index = new Map(); // 反向索引
    CIRCLE.debug = () => {
      let str = "\n\n CIRCLE.Map: \n";
      str += `\n hit size:${CIRCLE.hit.size} \n\n`;
      let count = 0;
      for (const [idx, { circle }] of CIRCLE.index) {
        str +=
          `i: ${count} ,{hash: ${idx} ,` +
          `nums: ${circle.map((nums) => nums.join("")).join(",")} },\n`;
        count++;
        if (count === DEBUG_LINES) break;
      }
      str += "\n.........\n\n";
      str += "\n index size:" + CIRCLE.index.size + "\n";
      return str;
    };

    // 生成环标识
    const LOOP = {};
    LOOP.hit = new Set();
    LOOP.index = new Map();
    LOOP.debug = () => {
      let str = "\n\n LOOPS.Map: \n\n";
      str += `\n index size:${LOOP.index.size} \n\n`;
      let count = 0;
      for (const [idx, loop] of LOOP.index) {
        str += `i: ${count} ,{hash: ${idx} ,`;
        str += `size: ${loop.size} },\n`;
        count++;
        if (count === DEBUG_LINES) break;
      }
      str += "\n.........\n\n";
      str += "\n index size:" + LOOP.index.size + "\n";
      return str;
    };

    // 获取当前序列所有的轮环形式
    const doCircle = (mh) => {
      const nums = decompressHex(mh);
      const hash = [];
      const circle = [];
      for (let i = 0; i < nums.length; i++) {
        const numsi = nums.slice(i).concat(nums.slice(0, i));
        const hashi = compressHex(numsi);
        // if(hash.includes(hashi)) continue;
        hash.push(hashi);
        circle.push(numsi);
      }

      const minHash = Math.min(...hash);

      // const minNums = decompressHex(minHash);
      CIRCLE.index.set(minHash, { hash, circle });
      hash.forEach((hashi) => {
        CIRCLE.hit.set(hashi, minHash);
      });

      return null;
    };

    /**
     * 00000 重复了 B_LEN - 1 次
     *  forPP(...BIT_LIM)((i)=>{
     *    const idx = compressHex(new Array(B_LEN).fill(i));
     *    const {hash,circle} = CIRCLE.index.get(idx);
     *    CIRCLE.index.set(idx,{hash:hash.slice(0,1),circle:circle.slice(0,1)});
     *  })
     **/

    forWraper(
      B_LEN,
      ...BIT_LIM
    )((...nums) => {
      const hash = compressHex(nums);
      if (!CIRCLE.hit.has(hash)) doCircle(hash);
    });

    console.debug(CIRCLE.index, CIRCLE.debug());

    // 创建环形链表
    const doLoop = (mh) => {
      let nextHash = mh;
      let minHash = Number.POSITIVE_INFINITY;
      // const loop = new Map();
      const loop = new Set();
      while (!loop.has(nextHash)) {
        const prevHash = CIRCLE.hit.get(nextHash);
        nextHash = compressHex(getNext(decompressHex(prevHash)));
        minHash = minHash >= nextHash ? nextHash : minHash;
        // loop.set(prevHash, nextHash);
        loop.add(prevHash);
        LOOP.hit.add(prevHash);
      }
      LOOP.index.set(minHash, loop);

      return null;
    };

    for (const [idx] of CIRCLE.index) {
      if (!LOOP.hit.has(idx)) doLoop(idx);
    }

    console.debug(LOOP.index, LOOP.debug());

    // 结果梳理
    const CLUSTOR = {};
    for (const [clust, loop] of LOOP.index) {
      if (!CLUSTOR[clust]) CLUSTOR[clust] = [];
      for (const hash of loop) {
        CLUSTOR[clust].push(...CIRCLE.index.get(hash).circle);
      }
    }

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

    debugger;
    // 网页输出应该用异步加载
    // 数据量太大，显示不出来

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