ç«¶æããã°ã©ãã³ã° Advent Calendar 2020 3æ¥ç®ã®èšäºã§ãã æ
è¡ãã©ãããã©ãŒã éšãšã³ãžãã¢ã®è°·äºã§ãã æ®æ®µã®æ¥åã§ã¯äž»ã«TypeScript + PostgreSQLã§éçºãè¡ã£ãŠããŸããä»åã¯ãå人çãªèª²é¡ãJavaScriptã§è§£æ±ºããŠã¿ãããç«¶ããã®äžçã«è¶³ãèžã¿å
¥ããŠãããè©±ãæžããŸãã æ¥åžžç掻ã®ã¡ãã£ãšããå°ãããšãèªåã®ã³ãŒãã§è§£æ±ºã§ããã®ã¯ãšã³ãžãã¢ã®åœ¹åŸã§ããïŒ ä»åã¯ã¢ããªã®æ§æãUIã¯ã¹ã³ãŒãå€ãšããããžãã¯ã®éšåã ããåãåºããŠæ±ãã®ã§ããJavaScriptã®æžãæ¹ã¯äžéãåŠãã ããè€éãªã¢ããªã¯äœã£ãããšããªãããšããæ¹ãããã²ããºã«ã®ã€ããã§èããªããèªãã§ã¿ãŠãã ããïŒ è§£æ±ºãããèª²é¡ ã飿Šã®å°ãªãç·åœããã®å¯ŸæŠé ãæ±ºãããã ãã®èšäºãèªãã§ããã¿ãªããããã飿Šã®å°ãªãç·åœããã®å¯ŸæŠé ãæ¥œã«æ±ãããïŒããšæã£ãããšã¯ãã£ãšäžåºŠãäºåºŠã§ã¯ãªãã§ãããã ç§ã¯å€§åŠãã躰éãšããæŠéããã£ãŠãããå°åºã®éžèäŒéå¶ãªã©ã§å¯ŸæŠé ãæ±ºããæ©äŒããããŸããïŒèº°éã«ã€ããŠã¯ãã®èšäºã§ã¯å°åºèªãå°œãããªãã®ã§ãã²åç»ãæ€çŽ¢ããŠã¿ãŠãã ããïŒã éžèäŒã§ã¯å¯Ÿè±¡éžæã®ç·åœããæŠãé çªã«è¡ãã®ã§ãããé£ç¶ããŠè©Šåã«åºãããšã¯éžæã«ãšã£ãŠãè² è·ã倧ããã飿Šãæ¥µåæžãããçµã¿åãããæ±ããããŸãã ãŸããäºåã®å€§äŒã§å®æœãã察æŠã«ãŒãã¯ãã®çµæãæµçšããããã äžéšã®çµã¿åããã察æŠé ããé€å€ãã å¿
èŠããããŸããã åœç¶ã詊åé ãäºåã«èããŠãããã°æ¥œãªã®ã§ãããå¯Ÿè±¡éžæã人æ°ãåœæ¥ç¢ºå®ããããšãããããã®å Žã§æ¥ãã§å¯ŸæŠé ãèããªããã°ãããŸããã ä»åã¯ãããŸã§ã¯çŽãšãã³ã§ãã£ãŠããå°å³ã«å€§å€ãªãã®äœæ¥ããèªååããŠãããããšæããŸãã å®çŸãããå
容ã¯äžèšã®å³ã®ãããªã€ã¡ãŒãžã§ãã ãéžæãç»é²ãããã§ã«å®æœæžã¿ã®è©Šåãéžæãããšãç·åœããã«å¿
èŠãªæ®ãã®è©ŠåãïŒé£æŠã®å°ãªã圢ã§ïŒèªåã§æç€ºããŠãããããšããæµãã§ãã ãã®èšäºã§ã¯ã(ii)â(iii)ã®çµã¿åããæé©åã«ã€ããŠèããŸãã n人(~10çšåºŠ)ã®ç·åœããæŠã®å¯ŸæŠé ãæ±ºãã åæã«è¡ã詊åã®æ°ã¯1詊åãšãã äžéšã®çµã¿åãããé€å€ããäžã§ã飿п°ãæå°ã«ãã ããã§ã®ã飿п°ããšã¯ãåã®è©Šåã«åºãéžæãšåãéžæãåºã詊åã®æ°ãã®ããš ããšãã°"A-B", "B-C", "A-C", "D-E"ã®é ã§å®æœããå Žåã1,2詊åç®ã®Bãš2,3詊åç®ã®Cã飿Šãšãªãããã飿п°ã¯2 æ¹é éžæã®ãªã¹ããäœã ãªã¹ãããçµã¿åãããåæãã åæããçµã¿åãããäžŠã¹æ¿ããè©äŸ¡é¢æ°ãéããŠã³ã¹ãïŒé£æŠæ°ïŒãæå°ã®ãã®ãåãåºã ããã©ãŒãã³ã¹ãå®è£
ã®æè»œããèæ
®ãããšä»ã®èšèªã«è»é
ãäžããããã§ãããä»åã¯TypeScriptã§äœã£ãŠããWebã¢ããªã«ä¹ããããšãæ³å®ããŠãããããäžæŠJSã§å®è£
ããŠã¿ãããšæããŸãã æ¬æäžã®ãµã³ãã«ã³ãŒãã¯Node.js 12.19.0ã§åäœç¢ºèªããŠããŸãã å®è£
ã¯ããã«ãéžæã®çµã¿åããã®è¡šçŸæ¹æ³ãèããŸãã A, B, C...ãšéžæãäžãããããšããA察Bã®è©Šåã "AB" ã®ããã«æååã§äžããŠãè¯ãã®ã§ããã飿Šå€å®ãããã·ã³ãã«ã«è¡ãããã«ãåéžæã«ããããå²ãåœãŠãŠè¡šçŸããŠã¿ãããšæããŸãã ããªãã¡ãéžæA, B, C, D...ã«å¯Ÿã㊠1, 2, 4, 8... ãšæ°å€ãå²ãåœãŠãŠãããéžæå士ã®å¯ŸæŠçµã¿åããã¯ãã®åã«ãã£ãŠè¡šçŸããããšã«ããŸãã ããšãã°"A-D"ã®è©Šå㯠9 ãšããŠäžæã«è¡šçŸã§ããŸããã 衚1: n=5ã®å Žåã®å詊åã®è¡šçŸ ç¶ããŠãå®éã«ã³ãŒããæžããŠãããŸãããã 1. éžæã衚ããªã¹ããäœã åå 人æ°nãäžãããããšããåéžæã«å²ãåœãŠããããããã«1ãç«ãŠãæ°å€ã®é
åãäœã£ãŠãããŸãã nåã®èŠçŽ ã®é
åãäœããmap颿°ã§åèŠçŽ ãindexåã ãã·ãããããæ°å€ã«å€æããŸãã ãªãã Array(n) ã§ã¯ç©ºé
åãçæãããã®ã§ãäžåºŠã¹ãã¬ããæŒç®åã§å±éããŠããŸãã const createList = n => [...Array(n)].map((_, i) => 1 2. çµã¿åãããå
šãŠåæãã äºéã®ã«ãŒããéããŠäºéžæã®æ°å€ã®åãé
åã«å ããŠãããŸãã "A-B"ãš"B-A"ã¯åºå¥ããå¿
èŠããªããããå
åŽã®ã«ãŒãã®ã«ãŠã³ã¿ãå€åŽã®ãããè¶
ããªãç¯å²ã§ããããšã«æ³šæããŸãã åŒæ°ã«ã¯å
ã»ã©ã®createListã§äœã£ãéžæã衚ãé
åãæž¡ããŸãã const combination = list => { let combinationList = []; for (let i = 0; i äžã€ç®ã®äŸã¯ ["A-B", "A-C", "B-C"] ã衚ãé
åãåŸãããããšã«ãªããŸãã 3. ãã§ã«çµæããã詊åãé€å€ãã ä»åã¯ã宿œæžã¿ã®è©Šåãè¡šãæ°å€ã®é
å excludeList ãäžããããŠãããã®ãšããŸãã ããšãã°ã"A-C", "C-D"ã®è©Šåã宿œæžã¿ã®å Žå㯠excludeList 㯠[5, 12] ãšãªããŸãã Array.filter() ã䜿ã£ãŠãããããé€å€ãããããããè¡ã詊åã®ãªã¹ãããäœæããŸãã const combinationList = combination(createList(5)); const excludeList = [5, 12]; const filteredList = combinationList.filter(elm => !excludeList.includes(elm)); 4. 飿п°ãèšç®ãã颿°ïŒè©äŸ¡é¢æ°ïŒãäœã ããŠãäžŠã¹æ¿ããŠå¯ŸæŠé ã®æ¢çŽ¢ãããåã«ã飿п°ãæ±ãã颿°ãäœã£ãŠãããŸãã åèŠçŽ ããé ã«ãã1ã€åã®èŠçŽ ãšæ¯èŒããŠåãéžæãå«ãŸããå Žåã¯ã³ã¹ãã«1å ç®ãããæäœãè¡ããŸãã ãåãéžæãå«ãŸãããã©ãããã®å€å®ã¯ããããè«çç©ã«ãã£ãŠå€å®ããããšãã§ããŸãã åãéžæãå«ãŸããŠããå Žåã¯åãäœçœ®ã«1ãç«ã£ãŠãããããè«çç©ãåããš0ã«ãªããŸããã 衚2: 飿Šãšãªãå Žåããªããªãå Žåã®2詊åã®è«çç©ã®çµæ ãããé ç¹°ãã«å€å®ãã飿Šã®å Žåã¯ã³ã¹ããå ç®ããŠãããŸãã foræã§æžããŠãè¯ãã®ã§ãããé
åãç³ã¿èŸŒãã§ãã£ãŠããå€ãåŸãããšãã¯ããã®æå³ãæç€ºããããã«ã Array.reduce() 颿°ããã䜿ããŸãã const evaluationFunc = list => list.reduce((cost, _, idx, src) => src[idx] & src[idx - 1] ? ++cost : cost, 0); // example const listA = [3, 5, 6, 9, 10, 12]; const listB = [3, 12, 5, 10, 6, 9]; evaluationFunc(listA); // 4 evaluationFunc(listB); // 2 idxã0ã®ãšãã src[idx - 1] = undefined ãšãªããŸãããè«çç©ãåããš0ã«ãªãã®ã§åå²ã¯çç¥ããŸãã src[idx] ã¯ç¬¬äºåŒæ°ã§è¡šããŸããããã¡ãã®æ¹ãæäœãçŽæçã«çè§£ããããããªãããã®ããã«æžããŠããŸãã 5. äžŠã¹æ¿ããŠè©äŸ¡ãã é çªãå
¥ãæ¿ãããããé åãæ±ãã颿°ãå®è£
ããŸãã const permutation = (list, k) => { let ans = []; if (list.length [i]); } else { for (let i = 0; i å
šéšäžŠã¹æ¿ããŠããè©äŸ¡ããŠãè¯ãã®ã§ããã飿Šãªãã®è§£ãèŠã€ãã£ãæç¹ã§æã¡åããããããååž°ã®äžçªæµ
ãéå±€ã§è©äŸ¡ããªããforæãåããŸãã const search = (filteredList) => { let ans = []; let cost = undefined; for (let i = 0; i ããã§ã飿п° cost ã®å¯ŸæŠé ans ãåŸãããšãã§ããŸãã 詊ãã«åå 人æ°ã6åã宿œæžã¿ã®è©Šåã"A-C", "C-D", "B-E", "B-F"ãšããŠå¯ŸæŠé ãæ±ããŠã¿ãŸãã const list = createList(6); const excludeList = [5, 12, 18, 34]; const filteredList = combination(list).filter(elm => !excludeList.includes(elm)); search(filteredList); // { // ans: [ 3, 20, 9, 6, 40, 17, 36, 24, 33, 10, 48 ], // cost: 0 // } ããã埩å
ãããšã ãšãªãã確ãã«æå®ãã詊åãé€ããã飿Šã®ãªã察æŠé ãæ±ããããšãã§ããŸããã äžèšã®äŸã§ã¯è©Šãã«æå
ã§10åèšæž¬ãããšãããå®è¡æéã¯å¹³å10.8ç§ã§ããã æ¹å ããŠãäžå¿çããæ±ããããšã¯ã§ããŸããããã©ãã«ãæçŽã«ãããããŠããæ°ãããŠãªããŸããã ãã®èåããåéã®éãå
šæ¢çŽ¢ããããšã¯èšããŸããããããå°ãå¹çããæ¢ãããšã¯ã§ããªãã§ããããã ããããåä»ããŠããŸããããããã«ãç«¶ããããã¯ãªåé¡ã§ããã ç«¶ããã©çŽ äººã®ç§ã§ã¯èª¿ã¹ããã«ãå¹çãæªããšæãã瀟å
ã®ç«¶ããæŽæŠã®çè
éã«ã¬ãã¥ãŒããé¡ããããšããã以äžã®ãããªå瀺ãè³ãããšãã§ããŸããã 飿Šã«ãªããªã詊åå士ãã³ã¹ã0ã®èŸºã飿Šã«ãªã詊åå士ãã³ã¹ã1ã®èŸºã§ã€ãªãã ç¡åã°ã©ããèãããšã飿п°ãæå°åããåé¡ã¯ãããã®ã°ã©ãã®ãã¹ãŠã®é ç¹ã1床ãã€éããã£ãšãåèšã³ã¹ãã®å°ããçµè·¯ã¯ã©ããïŒããšããåé¡ã«åž°çãããã㯠巡åã»ãŒã«ã¹ãã³åé¡ ãšåŒã°ãã ããã¯èšç®é O(2^n n^2) (n: é ç¹æ°=è©Šåæ°)ã§æ±ºå®çã«æ±ããã¢ã«ãŽãªãºã ãç¥ãããŠãã ãã ãå·¡åã»ãŒã«ã¹ãã³åé¡ã«ã€ããŠã¯è¿äŒŒçã«ããè§£ãæ±ããæ¹æ³ãèæ¡ãããŠãã(2-optãªã©)ãä»åã®ã±ãŒã¹ã§ã¯ååãªè§£ãåŸãããå¯èœæ§ãé«ã ã¢ã«ãŽãªãºã ãåé¡ã®åç§°ãç¥ãããšã§ãæ€çŽ¢ããããšããææ®µãæã«å
¥ããã®ã§ã調ã¹ãªããæ¹è¯ããŠã¿ãããšæããŸãã 2-optæ³ æ¬¡ã®ãŽãŒã«ã§ãããå¹çããæ¢ããæ¹æ³ã®ã²ãšã€ãšããŠã屿æ¢çŽ¢æ³ããããŸãã ããã¯ãçŸåšã®çµã¿åããã«å°ãã ãå€åãå ããã³ã¹ããäžããã°æ¡çšããããšããæäœããã³ã¹ããäžãããªããªããŸã§ç¹°ãè¿ããã®ã§ãã ãã®äžã§ãå·¡åã»ãŒã«ã¹ãã³åé¡ã«ãã䜿ããã2-optæ³ã¯ãã°ã©ãä»»æã®2ã€ã®èŸºãéžã³ããããã€ãªãå€ããããšã§ãçµã¿åãããå€åãããŠãããŸãã ã€ãŸãã ...-a-b-...-c-d-... ã®ãããªã°ã©ãã«å¯ŸããŠã ...-a-c-...-b-d-... ã®ããã« b-...-c ã®ãããã¯ãå転ãããŠã€ãªãæ¿ãããããªæäœã詊ããŠããããšã«ãªããŸãã åå®è£
1ãã3ãŸã§ã®æé ã«ã€ããŠã¯æ¢ã«äœæãã颿°ãæµçšããè¿åæ¢çŽ¢éšåã远å ã§å®è£
ããŠãããŸãã ãŸã蟺ãå
¥ãæ¿ããéã®é£æŠæ°ã®å€åã«ã€ããŠèããŸãã æåã®å®è£
åæ§ã«å
šäœã®é£æŠæ°ãæ°ããè©äŸ¡é¢æ°ãéãããšãã§ããŸãããå
¥ãæ¿ãååŸã§ã³ã¹ããå€ããåŸãã®ã¯äº€æãã蟺ã®éšåã®ã¿ã®ãããå·®åã ããèšç®ããããšã§èšç®éãæžãããŸãã const getSwapCost = (list, i, j) => { const getLocalCost = (x, y) => list[x] & list[y] ? 1 : 0; const costBefore = getLocalCost(i, i + 1) + getLocalCost(j, j + 1); const costAfter = getLocalCost(i, j) + getLocalCost(i + 1, j + 1); return costAfter - costBefore; } ïŒä»åããé
åé·ãè¶
ããŠåç
§ããå Žåã³ã¹ãã¯0ãšèšç®ãããã®ã§ã i , j ãé
åæ«å°Ÿã ã£ãå ŽåãäŸå€åŠçã¯äžèŠã§ããïŒ ç¶ããŠãã³ã¹ããäžããããšãããã£ãå Žåã«ã2ã€ã®èŸºãã€ãªãæ¿ãã颿°ãäœæããŸãã const swapEdges = (list, i, j) => { const head = list.slice(0, i + 1); const reverseTarget = list.slice(i + 1, j + 1); const tail = list.slice(j + 1); return [...head, ...reverseTarget.reverse(), ...tail]; } // example const list = [0, 1, 2, 3, 4, 5, 6]; swapEdges(list, 2, 5); // [0, 1, 2, 5, 4, 3, 6] ããã«ãå
¥ãæ¿ããéã«ã³ã¹ããæãäžãã蟺ã®çµã¿åãããæ¢ããæ°ãã察æŠé ãè¿ã颿°ãäœããŸãã ä»»æã®2蟺ã«ã€ããŠè©ŠããŸããã i ãš j ãé£ç¶ããŠãããšå
¥ãæ¿ãæäœãããŠãé
åãå€ãããªãïŒ2ã€ã®èŸºãåã1ã€ã®é ç¹ã«ã€ãªãã£ãŠããŠã€ãªãæ¿ãããããªãïŒãããå
åŽã®ã«ãŠã³ã¿ j 㯠i+2 ããå§ãŸãããã«ããŸãã ãŸãè¿ãå€ã¯ãã³ã¹ããäžãã£ãå Žåã«ã¯æ¡çšãããæ°ãã䞊ã³é ããã³ã¹ããå€ãããªãã£ãå Žå㯠null ãè¿ãããã«ããŠãããŸãã const improve = list => { let iBest, jBest; let diffBest = 0; for (let i = 0; i æåŸã«ã improve ã®çµæã null ã«ãªããŸã§ç¹°ãè¿ãæ¢çŽ¢ããã¡ã€ã³ã®é¢æ°ãå®è£
ããŸãã const localSearch = list => { const totalCost = evaluationFunc(list); if (totalCost !== 0) { while (true) { let improvedList = improve(list); if (!improvedList) break; list = improvedList; } } return { ans: list, cost: evaluationFunc(list) } }; å®è¡ããéã¯ãåæ§ã®æé ã§ filter ããé
åãæž¡ããŸãã localSearch(filteredList); // { // ans: [ 3, 36, 9, 6, 24, 33, 20, 40, 17, 10, 48 ], // cost: 0 // } æåã®å®è£
ãšåæ§ã®é
åãæž¡ããšãå¥ã®è§£ã§ãã飿Š0ã®äžŠã³é ãåŸãããšãã§ããŸããã ããããå®è¡æéã¯å
šæ¢çŽ¢ã®å¹³å10.8sã«æ¯ã¹ãŠå¹³å1.2msãšã倧å¹
ã«ççž®ããããšãã§ããŸããïŒ åæè§£ã«ã€ã㊠2-optæ³ã®æ¢çŽ¢ã§ã¯ãäžããããè§£ããå€åãããŠæ¢çŽ¢ãããããåæè§£ã®è¯ããæçµçãªè§£ã®è¯ãã«åœ±é¿ãäžããŸãã ç¹ã«ãä»åã¯çµã¿åãããäœæããããžãã¯äžã飿Šãçžåœæ°ç¶ã䞊ã³ãåæè§£ãšãªãããã filteredList ãã©ã³ãã ã«äžŠã¹æ¿ããŠããå®è¡ããæ¹ãè¯ããããããŸããã ããã«ããã°ãè€æ°ã®ã©ã³ãã åæè§£ãããããã2-optã§æ¢çŽ¢ãããšãæé©è§£ãåŸããã確床ãäžããããã§ããã ã©ã³ãã ã«äžŠã¹æ¿ãã颿°ãå®è£
ããŠè©Šãããšããã100ã»ããã®æ¢çŽ¢äžã9åã¯é£æŠæ°1ã®è§£ããã以å€ã®91åã¯é£æŠ0ã®è§£ãå°åºãããŠããŸããã const shuffle = list => { for (let i = list.length - 1; i >= 0; i--) { const j = Math.floor(Math.random() * (i + 1)); [list[i], list[j]] = [list[j], list[i]]; } return list; } ãããã« æåŸãŸã§èªãã§ããã ããããããšãããããŸããïŒ ä»åã¯èº«è¿ãªïŒãšãŠãå人çãªïŒèª²é¡ãJavaScriptã䜿ã£ãŠè§£æ±ºããŸããã ãŸãã2-optæ³ãçšããããšã§ãå®è¡æéãåçã«ççž®ããããšãã§ããŸããã ãããªãæ¡åŒµãçŸå®çã«ãªã£ãã®ã§ãä»åŸã®å±æãšããŠã¯ åäžéžæã3飿Šããå Žåãè©äŸ¡ã«çµã¿èŸŒã éžè詊åã2ã³ãŒãåæäžŠè¡ã§è¡ã éžææ°ãããå¢ããã±ãŒã¹ ãªã©ã察å¿ã»å®èšŒããŠãããããšæããŸãã ãããŸã§ç«¶ããããã£ãŠã¿ãããšã¯æããªãããæãåºããŠããŸããã§ããããæããããŠãã®å¥¥æ·±ãã®äžç«¯ã«è§Šããããšãã§ããŸããã äžããããåé¡ãããã§ãªãçŸå®ã§å¿
èŠãªåé¡èšå®ãèªãèããããšã§ãããèå³ãšå®æãæã£ãŠåŠã¶ããšãã§ããããã«æããŸãã çŸå®çãªèª²é¡ãããã«æ¢ç¥ã®åé¡ã«èœãšã蟌ããããŸãèœãšã蟌ãã åé¡ã«å¯ŸããŠå¹çããè§£ããåŒãåºããã©ãã ãæã£ãŠãããããšããéšåã¯ã»ã³ã¹ãçµéšãåãããããšãçæããã®ã§ããããããæ®æ®µã®æ¥åã§äœ¿ãæè¡é åã«ãšãããããå¹
åºãåŠãã§æè¡ã磚ããŠãããããšæ¹ããŠæããŸããã