Guest User

Untitled

a guest
Feb 2nd, 2021
76
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. (function (root, factory) {
  2.     if (typeof exports === 'object') {
  3.         module.exports = factory(root);
  4.     } else if (typeof define === "function" && define.amd) {
  5.         define([], factory);
  6.     } else {
  7.         root.IdiomSolitaire = factory(root);
  8.     }
  9. })(typeof global !== 'undefined' ? global : this.window || this.global, function (root) {
  10.  
  11. class IdiomSolitaire {
  12.     constructor() {
  13.         this.idioms = null;
  14.     }
  15.  
  16.     load() {
  17.         return this.idioms ? Promise.resolve(this) : fetch('https://cdn.jsdelivr.net/gh/pwxcoo/chinese-xinhua/data/idiom.json')
  18.             .then(res => res.json())
  19.             .then(res => {
  20.                 this.idioms = Object.freeze(res.map(e => {
  21.                     const pinyin = e.pinyin.replace(/[ ,?]/, '').split(' ');
  22.                     e.start = pinyin[0];
  23.                     e.end = pinyin[pinyin.length - 1];
  24.                     return Object.freeze(e);
  25.                 }));
  26.                 return this;
  27.             });
  28.     }
  29.  
  30.     solve(start, end) {
  31.         if (!this.idioms) {
  32.             throw new Error('Idioms not ready');
  33.         }
  34.  
  35.         console.time('Solve');
  36.  
  37.         const startIdiom = this.idioms.find(e => e.word === start);
  38.         const endIdiom = this.idioms.find(e => e.word === end);
  39.         if (!startIdiom || !endIdiom) {
  40.             throw new Error('Invalid idiom');
  41.         }
  42.  
  43.         const set = new Set;
  44.         const queue = [{
  45.             parent: null,
  46.             idiom: startIdiom,
  47.         }];
  48.         let found;
  49.         let nodeCount = 0;
  50.         while (queue.length) {
  51.             const node = queue.shift();
  52.             nodeCount++;
  53.             const children = this.idioms
  54.                 .filter((e, i) => e.start === node.idiom.end && !set.has(i) && set.add(i))
  55.                 .map(e => ({
  56.                     parent: node,
  57.                     idiom: e,
  58.                 }));
  59.                 if (found = children.find(e => e.idiom.end === endIdiom.start)) {
  60.                     break;
  61.                 }
  62.             children.forEach(e => queue.push(e));
  63.         }
  64.  
  65.         console.info('Node count:', nodeCount);
  66.         console.timeEnd('Solve');
  67.  
  68.         if (found) {
  69.             const result = [endIdiom];
  70.             while (found) {
  71.                 result.unshift(found.idiom);
  72.                 found = found.parent;
  73.             }
  74.             return result;
  75.         } else {
  76.             throw new Error('No solution');
  77.         }
  78.     }
  79. }
  80.  
  81. return IdiomSolitaire;
  82.  
  83. });
  84.  
  85. // 使用例:
  86. const solitaire = new IdiomSolitaire;
  87. solitaire.load().then(solitaire => console.log(solitaire.solve('身经百战', '谈笑风生').map(e => e.word).join(' -> ')));
RAW Paste Data