通过这篇文章，我们将完成一系列有关2018年Yandex.Blitz竞赛的出版物。 我们希望您有机会参与或至少看到我们建议接近生产的任务。 上一场竞赛专门针对前端中算法的使用。 今天，我们发布了对12个问题的详细分析：在资格赛中提出了前6个问题，在最后一轮中提出了7-12个问题。 我们试图解释条件是如何形成的，我们关注哪些技能。 感谢所有参与者的关注！
任务1
第一个任务是预热20分钟，然后我们决定对其进行设置，以便使用正则表达式轻松解决它。
任务的所有选项都以类似的方式构造-细分为多个点，每个点都可以由最终正则表达式中的组表示。
请考虑以下选项之一：邮局。
条件
在Jopan-14-53星球上，当地人希望互相发送信件，但发送信件的鸽子机器人却对地址感到困惑。 您必须教他们解析字母并检查其有效性。
地址基本部分的结构由收件人的地区，直辖市，姓名和姓氏组成。 直辖市可以分为县和邮局。 所有部分均以逗号分隔。
地区，市镇和地区的名称是单词，每个单词的第一个字母较大，其余的较小。 可以使用两个单词的名称，以空格或减号分隔。 每个字由三到八个字母AZ组成。
居民手中有6个手指，在日常生活中为十二进制系统。 数字0-9照原样使用，而10和11则由符号
~和
≈ 。
组合中的邮局编号连续3位，或4位分为2组，每组2位，带减号。 示例：
44-99 。
有时，居民可应要求向市政当局发送信件。 在这种情况下，没有地址：只有市政当局和收件人的名字。
这很有趣，但地球上的人们仅被称为六个名字和九个姓氏。 名称：Shob，Ryob，Mob，Xian，Ryan，Mans。 姓：Sho，Ryo，Mo，Xia，Rya，Ma，Syu，Ryu，Mu。 这个星球上的居民根本不是梦想家。
解析中
地址基本部分的结构由收件人的地区，直辖市，姓名和姓氏组成。 直辖市可以分为县和邮局。 所有部分均以逗号分隔。
从第一段中，我们学习如何指示地区，城市，地区，邮局，姓名和姓氏，以及在测试行中应遵循的顺序。
地区，市镇和地区的名称是单词，每个单词的第一个字母较大，其余的较小。 可以使用两个单词的名称，以空格或减号分隔。 每个字由三到八个字母AZ组成。
从这一段可以明显看出，该组对应于单词
([-][-]{2,7}) 。 以及名称，分别是
([-][-]{2,7}(?:[- ][-][-]{2,7})) 。
居民手中有6个手指，在日常生活中为十二进制系统。 数字0-9照原样使用，而10和11则由符号~和≈ 。
在这里，我们知道仅使用
\d作为数字是不够的-您需要使用
[0-9~≈] 。
组合中的邮局编号连续3位，或4位分为2组，每组2位，带减号。 示例： 44-99 。
因此，该组对应于邮局编号
([0-9~≈]{3}|[0-9~≈]{2}-[0-9~≈]{2}) 。
有时，居民可应要求向市政当局发送信件。 在这种情况下，没有地址：只有市政当局和收件人的名字。
我们了解，记住并考虑到地区和邮局可能同时缺席的最终职能集会。
这很有趣，但地球上的人们仅被称为六个名字和九个姓氏。 名称：Shob，Ryob，Mob，Xian，Ryan，Mans。 姓：Sho，Ryo，Mo，Xia，Rya，Ma，Syu，Ryu，Mu。 这个星球上的居民根本不是梦想家。
这是条件的最后一部分。 在这里，我们需要另一个简单的小组
(||||||||) (|||||)或更短的
([][]|[]) ([C]|[]||) 。
为简单起见，我们将这些组保存到变量中，并在结果正则表达式中使用它们。
const w = '[-][-]{2,7}';
任务2.出现错误的代码
条件
白天，开发团队做了几个新功能。 但是在准备发布时，发生了合并冲突，解决了这些冲突后，布局便分开了。 迫切需要消除由于代码中的更正次数最少而导致的错误，以使发行版有时间投入生产。
为您提供了样式损坏的HTML页面和PNG格式（具有预期的结果）。 您需要修正错误，以便在Chrome浏览器中查看时的结果与原始屏幕截图相同。 发送更正的页面作为解决问题的方法。
样式损坏的
HTML页面 。 版面：
解析中
在此任务中，我们试图模仿Yandex开发人员经常遇到的情况：在庞大的代码库中，找到很少的简单代码行，对其进行更正可以得到所需的结果。 也就是说，困难不在于编写代码，而在于理解确切地在哪里编写（或删除）代码。
我们采用了真正的搜索引擎代码，并进行了一些修改，破坏了版面。 竞赛的参与者不到一个小时就可以处理大约250 KB的布局，并将代码置于与布局相对应的状态。
很明显，比赛的时间限制不允许阅读全部代码，因此参赛者应在浏览器中使用针对开发人员的工具。
要更正四个任务选项之一，进行以下更改就足够了：
diff --git a / blitz.html b / blitz.html
索引36b9af8..1e30545 100644
---一个/ blitz.html
+++ b / blitz.html
@@ -531.10 +531.6 @@
iframe [src $ ='ext-analytics.html'] { 高度：自动；
}
-.search2__button .suggest2-form__button：nth-child（1）{ -背景：＃ff0！重要；
-}
--
/ * ../../blocks-desktop/input/__control/input__control.styl end * /
/ * ../../node_modules/islands/common.blocks/input/__clear/input__clear.css开始* /
/ *相对于input__box定位。
@@ -744.10 +740.6 @@
iframe [src $ ='ext-analytics.html'] { 背景剪辑：padding-box;
}
.input_theme_websearch .input__clear { 背景图片：url（“ / static / web4 / node_modules / islands / common.blocks / input / _theme / input_theme_websearch.assets / clear.svg”）；
背景尺寸：16px；
@@ -857.6 +849.7 @@
iframe [src $ ='ext-analytics.html'] { 背景颜色：＃f2cf46;
}
.websearch-button__text：{之前 +位置：绝对；
顶部：-6px；
右：-9px；
宽度：0;
@@ -866.8 +859.6 @@
iframe [src $ ='ext-analytics.html'] { 边框样式：实心；
border-color：rgba（255,219,76,0）;
border-left-color：继承;
-职位：相对；
-z-index：-1000；
}
/ * ../../blocks-deskpad/websearch-button/websearch-button.styl结尾* /
@@ -1349.6 +1340.7 @@
iframe [src $ ='ext-analytics.html'] { font-size：14px;
行高：40px;
职位：相对
+显示：内联块；
高度：自动；
填充：0;
垂直对齐：中间；
任务3.具有给定变异性的图片
条件
设计师设计徽标。 它需要在各种条件下使用。 为了使它尽可能方便，请在纯CSS中用一个HTML元素组成它。
您无法使用图片（即使通过数据：uri）。
解析中
由于任务仅使用一个div，因此我们只剩下div本身以及伪元素:: before和:: after。
幸运的是，布局上的图片仅包含三个不同颜色的区域。 我们为每个可访问元素，正确的位置和圆角创建自己的背景。 布局的灰色区域上有阴影-我们使用渐变使其阴影。
div { background: #0C0C0C; border-radius: 10px; position: relative; } div:before { border-radius: 9px 9px 0 0; position: absolute; width: 100%; height: 50%; background: #F8E34B; content: ''; } div:after { content: ''; background: linear-gradient(178deg, #C8C8C8 0px , transparent 7px), #EEEDEF; position: absolute; width: 50%; height: 50%; bottom: 0; border-radius: 0 0 0 9px; }
任务4
条件
Petya是《莫斯科前沿报》（Moscow Frontender）的高级排版员。 在报纸的版面设计中，Petya使用了一堆网络技术。 Petya面临的最困难的任务是报纸文章标题的布局：每期的报纸列宽度不同，标题具有不同的字体和字符数。
Petya需要为每个标题选择自己的字体大小，以便最大字体大小，但同时所有标题文本都适合分配给他的空间。
帮助Petya：实现calcFontSize函数，该函数可让您将传输的文本输入到容器中，以使其适合整个容器并具有最大可能的大小。 如果失败，则解决方案应返回null。 输入行的最大长度为100个字符。 输入字符串不能为空。 您的解决方案应包含整个功能代码，并且不应使用外部依赖关系，以便Petya可以将其复制到他的项目中并在他的代码中调用它。
我们将检查您的解决方案的最佳工作方式，如果产生过多的DOM操作，则会对其进行优化。
解析中
要做的第一件事是学习如何确定文本是否适合容器，因为容器中的文本可能需要多行。 最简单的方法是使用
element.getBoundingClientRect（）函数，该函数可让您获取元素的尺寸。
您可以在容器内使用单独的span元素绘制文本，并检查此元素的宽度或高度是否超过容器的大小。 如果是，则文本不适合容器。
接下来，检查边界条件。 如果即使最小字体也不能容纳该文本，则无法输入。 如果文本以允许的最大尺寸中断，则max将是正确的答案。 在其他情况下，所需的字体大小在间隔[min，max]中。
为了找到一种解决方案，您需要对整个间隙进行排序，并找到一个将文本放置在容器中的字体大小值，但是如果将其增加1-它将不再适合。
您可以使用简单的for循环在[min，max]范围内执行此操作，但是该解决方案将对页面进行大量检查和重绘-对于该范围内检查的每个值至少要执行一次。 这种解决方案的算法复杂度将是线性的。
为了最大程度地减少检查次数并获得适用于O的解决方案（log n），您需要使用二进制搜索算法。 该算法的思想是在每次搜索迭代时，将值的范围分为两半，并且搜索将在解决方案所在的一半中递归地继续。 当范围缩小到单个值时，搜索将结束。
在Wikipedia文章中阅读有关二进制搜索算法的更多信息。
我们使用
MutationObserver检查了解决方案的算法复杂性：我们将其放在页面上，并计算DOM在寻找答案的过程中做出决定的突变次数。 对于某些测试，严格限制了突变的数量，因此只有基于二进制搜索的解决方案才能通过此限制。
要获得任务的总分，还必须仔细检查不同的边界条件（匹配最小和最大，输入处为空行），并提供运行代码的几种环境条件（例如，使用！固定！CSS页面中重要的字体大小） ）
任务5.沟通困难
在每个限定选项中，都有一个任务是提供带有某些界面的HTML页面作为输入。 这些任务有不同的图例，但是它们全都归结为以下事实：必须从页面中提取一些数据，并使用此数据以某种方式与界面进行交互。
让我们分析该系列任务之一的解决方案，即“沟通中的困难”。
条件
Horse Adolf喜欢在电话上和朋友聊天。 不幸的是，这种情况很少见。 每次Adolf想要打电话时，他都要花一个多小时才能拨打朋友的号码。 这是因为他很难用厚实的蹄敲打正确的钥匙。
幸运的是，阿道夫的手机支持JavaScript。 请编写一个程序，通过单击键盘来拨打Adolf的朋友的电话。 所有必要的数字都记录在笔记本中。 不幸的马将非常感谢您！
解析中
这是作为输入提供的页面：
解决方案的第一部分是检索数据电话号码的每个数字都是通过背景图片通过图片设置的。 同时，在验证期间，将动态替换数字。 如果在浏览器中打开调试器并查看页面的DOM树，您将注意到每个DOM元素都使用清晰的类：
<div class="game"> <div class="target"> <div class="line"> <div class="symbol nine"></div> <div class="symbol eight"></div> <div class="symbol five"></div> <div class="symbol separator"></div> <div class="symbol four"></div> <div class="symbol one"></div> <div class="symbol two"></div> <div class="symbol separator"></div> </div> </div> </div>
在这种情况下，仅创建一个字典，提取CSS类并将其转换为带有数字的字符串就足够了，该数字不包含分隔符（CSS类分隔符）。 例如，像这样：
const digits = document.querySelectorAll('.game .target .symbol:not(.separator)'); const dict = { 'one': 1, 'two': 2, 'three': 3, 'four': 4, 'five': 5, 'six': 6, 'seven': 7, 'eight': 8, 'nine': 9, 'zero': 0, }; const phoneNumber = Array.from(digits).reduce((res, elem) => { for (const className of elem.classList) { if (className in dict) { res.push(dict[className]); break; } } return res; }, []);
结果，我们得到以下数组：[9，8，5，4，1，2，8，8，0，9，0]。
解决方案的第二部分是与界面进行交互在这一阶段，我们已经有了一个数组，其中包含该数字的所有数字，并且我们需要了解键盘上的哪个按钮与哪个数字相对应。 如果查看HTML代码，将会看到没有特殊的提示类在键盘上指示数字：
<div class="keys"> <div class="key"></div> <div class="key"></div> </div>
可以简单地通过索引手动创建另一本词典，但是有一种更简单的方法。 如果仔细查看Web检查器中的样式，您会注意到按钮上的数字是通过CSS属性内容为伪元素之前设置的：。 例如，对于“ 3”键，样式如下所示：
.key:nth-child(3):before { content: '3'; }
要获取此属性的值，我们使用window.getComputedStyle方法：
const keys = Array.from(document.querySelectorAll('.game .key')).reduce((res, elem) => { const key = window
结果，我们得到一个对象，其中键文本将是按钮上的文本（数字或“呼叫”），而值将是DOM节点。
剩下的只是从第一个数组（phoneNumber）中获取值，遍历它们，然后使用我们的按键字典单击相应的按钮：
phoneNumber.push('call'); const call = () => { const event = new Event('click'); const next = phoneNumber.shift(); keys[next].dispatchEvent(event); if (phoneNumber.length) { setTimeout(call, 100); } } call();
请注意：在拨号之前，我们将调用值添加到数组的末尾。 这是任务条件所必需的，因为如果您拨打该号码并且不按“呼叫”，则解决方案将无法通过测试。
另一个功能是异步按下键盘按钮。 如果拨号时两次击键之间的时间间隔小于50毫秒，则此解决方案也将无法通过测试。 在出现问题的情况下未明确描述此功能，我们希望参与者通过阅读页面的源代码来查找。 顺便说一句，源代码中的参与者正在等待着一些惊喜。 ;）
任务6
条件
Fedor Rakushkin在他的公司中管理任务管理系统。 系统所在的服务器发生故障（Fedor未执行备份）。
在服务器的内存中，保留了描述任务，执行者和观察者以及这些结构之间的关系的结构缓存。 此外，保留了指向最后更改的结构的缓存链接。
帮助Fedor编写一个函数，该函数可以还原任务和用户之间的所有可能的连接，并将它们保存为Markdown格式的文档，然后Fedor将从该文档中将数据库还原到新服务器。
降价文件应采用以下格式：
## - % 1%, %username1%, : %username2% - % 2%, %username1%, : %username2%, %username3% - % 3%, %username1% // - % 4%, : %username1%, %username2% // - % 5% // - % 6%, : %username1% - % 1%, %username1% // - % 2% - % 3%, : %username1% ## - %username1% * % 1% // , * % 2% * % 3% * % 1% - %username2% * % 3%
任务列表，任务中的执行者列表，任务中的观察者列表，用户列表以及用户执行的任务列表应按字典顺序排序。
缓存中结构的描述
用户以“用户”类型的结构形式存储在缓存中：
type User = { login: string; tasks: Task[]; spectating: Task[]; };
任务以“任务”类型的结构形式存储在缓存中：
type Task = { title: string; assignee: User; spectators: User[]; subtasks: Task[]; parent: Task | null; };
解决方案模板
您的解决方案应包含一个CommonJS模块，该模块导出与以下签名相对应的函数：
module.exports = function (data) {
例子
如果显示指向“ lastEdited”的链接，则会得到以下结构：
{ type: 'task', title: 'Sub task', assignee: null, spectators: [], subtasks: [], parent: { type: 'task', title: 'Something else', assignee: null, spectators: [ { type: 'user', login: 'fedor', tasks: [ { type: 'task', title: 'Do something', assignee: [Circular], spectators: [ { type: 'user', login: 'arkady', tasks: [], spectating: [ [Circular] ] } ], subtasks: [], parent: null } ], spectating: [ [Circular] ] } ], subtasks: [ [Circular] ], parent: null } }
Markdown , :
## - Do something, fedor, : arkady - Something else, : fedor - Sub task ## - arkady - fedor * Do something
, .
, , . , :
function traverse(ctx, handlers) {
. , , …
users.sort((u1, u2) => u1.login < u2.login ? -1 : (u1.login > u2.login ? 1 : 0)); tasks.sort((t1, t2) => t1.title < t2.title ? -1 : (t1.title > t2.title ? 1 : 0));
… — :
7.
条件
, .. :
, . , «».
.
, . , . . . HTML CSS. JavaScript .
, , - . , .
HTML/CSS, , , - .
CSS, , — float, . float , , .
— , . (
jsfiddle.net .)
— padding-top, margin-top ( ). DOM- (). (
.)
8.
条件
HTML-. , . , . .
(pixel perfect). .
. .
, , . , . , : - , , .
, . , , .
, — . — CSS- border ( ), background ( ) box-shadow ( ).
- « » ( ) . , , .
— , 70 70 . : , . CSS- , CSS- , .
— 210 210 , 70 70 .
9.
条件
— , -. JavaScript, . , .
: . , , . .
, — . — . , JavaScript API . , -, , . 10 , HTTP- .
— . , , , .
-.
:
— API npm- @yandex-blitz/phone.
—
API .
— -, :
task.js .
— -
runkit- .
-, .
— GET- return connect.
: - . , , . .
, : , . :
const writeQueue = []; const processQueue = () => { if (writeQueue.length) { const fn = writeQueue.shift(); fn().then(() => { processQueue(); }); } }
, « ».
const writeQueue = []; let isWriteInProgress = false; const processQueue = () => { if (isWriteInProgress) { return; } if (writeQueue.length) { isWriteInProgress = true; const fn = writeQueue.shift(); fn().then(() => { isWriteInProgress = false; processQueue(); }); } }
, POST- . , , .
app.post("/speeddial/:digit/:phonenumber", (req, res) => { writeQueue.push(makeWriteJob(phone, req, res)); processQueue(); });
:
const express = require('express'); const { BEEP_CODES } = require('@yandex-blitz/phone'); const writeQueue = []; let isWriteInProgress = false; const processQueue = () => { if (isWriteInProgress) { return; } if (writeQueue.length) { isWriteInProgress = true; const fn = writeQueue.shift(); fn().then(() => { isWriteInProgress = false; processQueue(); }); } } const makeWriteJob = (phone, req, res) => { return () => { return phone.getData() .then(value => { const speeddialDict = JSON.parse(value); speeddialDict[req.params.digit] = Number(req.params.phonenumber); return phone .setData(JSON.stringify(speeddialDict)) .then(() => phone.beep(BEEP_CODES.SUCCESS)) .then(() => { res.sendStatus(200); }) }) .catch(e => { phone.beep(BEEP_CODES.ERROR).then(() => { res.sendStatus(500); }) }) } }; const createApp = ({ phone }) => { const app = express();
10.
条件
. , «».
:
— , .
— , , .
— , , .
— , : ← ↓ ↑ →.
— — , .
, , , , .
.
.
HTML- ( ).
, window.onMazeReady(). . 2 , .
CSS- map.
click CSS-:
— — control_direction_left,
— — control_direction_down,
— — control_direction_up,
— — control_direction_right.
CSS- :
background: radial-gradient(circle at 5px 5px, #eee, #000);
25 , 500 . 例如：
window.map String. :
# —
。 —
o —
x —
, , , — . .
,
window.map = ` ##### #o#x# #.#.# #...# ##### `;
:
:
<!DOCTYPE html> <html lang=ru/> <head> <style> body { padding: 100px 0 0 100px; } .game-box { perspective: 500px; perspective-origin: center; } .map { transform-style: preserve-3d; } .map__tilt_left { transform: rotateY(-25deg); } .map__tilt_down { transform: rotateX(-25deg); } .map__tilt_up { transform: rotateX(25deg); } .map__tilt_right { transform: rotateY(25deg); } </style> <title></title> </head> <body> <div class="game-box"> <div class="map"> </div> </div> <script> </script> </body> </html>
(HTML, CSS, JS). , «» .
. ( ), , .
, , .
, :
<table class="map map__tilt_none"> <tr> <td class="map__cell map__cell_content_wall"></td> <td class="map__cell map__cell_content_empty"></td> <td class="map__cell map__cell_content_ball"></td> <td class="map__cell map__cell_content_exit"></td> <td class="map__cell map__cell_content_wall"></td> </tr> </table>
:
.map { border: 0; border-spacing: 0; border-collapse: separate; background-color: #ccc; transform-style: preserve-3d; } .map__cell { box-sizing: border-box; border: 1px solid; border-color: #9b9b9b #575757 #575757 #9b9b9b; width: 30px; height: 30px; text-align: center; vertical-align: middle; font-size: 0; line-height: 0; background-color: #707070; } .map__cell_content_ball:after { content: ''; display: inline-block; width: 20px; height: 20px; border-radius: 50%; background: radial-gradient(circle at 5px 5px, #eee, #000); } .map__cell_content_wall { border-width: 4px; } .map__cell_content_exit { background-color: #000; border: 5px solid; border-color: #222 #555 #555 #222; }
— — .
, .
«» , . , . , :
window.map = ` ####### ##.#### #..o..# ##x.#.# ###...# ####### `;
:
function convertMap(mapInput) { return mapInput .trim() .split(/\n\s*/) .map(row => row.split('')); }
, HTML :
const CELL_CONTENT = { '#': 'wall', 'o': 'ball', '.': 'empty', 'x': 'exit' }; function buildGameBoxHtml(map) { return ` <div class="game-box"> <table class="map map__tilt_none"> ${map.map(row => ` <tr> ${row.map(cell => ` <td class="map__cell map__cell_content_${CELL_CONTENT[cell]}"></td> `).join('')} </tr> `).join('')} </table> <!-- --> <div class="controls"> <button class="control control_direction_left">←</button> <button class="control control_direction_down">↓</button> <button class="control control_direction_up">↑</button> <button class="control control_direction_right">→</button> </div> </div> `; }
, :
let gameBox = document.querySelector('.game-box'); let map = gameBox.querySelector('.map');
— callback : window.onMazeReady(). .
, . , , . HTML, CSS JS — , .
, :
— ,
— , ,
— , ,
— , ,
— , ,
— , .
, :
— ,
— ,
— DOM API ,
— .
11.
条件
, , . , . , .
, . , . . .js, :
module.exports = function solveCaptcha(captcha) {
. .
:
captcha = ' TRABWARH THSCAHAW WWBSCWAA CACACHCR '
:
— S — (sign)
— T — (tree)
— R — (road)
—…
:
[ 'TRABWARH THSCAHAW' , 'WWBSCWAA CACACHCR' ]
:
— 1 10.
— .
— , .
— ( ).
— , , .
— , .
Cut the cake codewars.com.
, 10. , . , . :
— ;
— , .
, . : «… , ». . .
. . , . .
. «», .
module.exports = function solveCaptcha(captcha) { const n =
12. -
条件
X . VCS , .
, -. — , .
, . , , . .
, . ( ) .
.
. — 1000, - — 20.
:
type PullRequest = { files: string[], id: string, created: number, }
(created) (id) – .
CommonJS- :
module.exports = function (pullRequests) {
NodeJS v9.11.2. .
function mergeAllPRs(prs) { } console.assert( mergeAllPRs([ { id: '#1', created: 1536077100, files: ['.gitignore', 'README.md'] }, { id: '#2', created: 1536077700, files: ['index.js', 'package-lock.json', 'package.json'] }, { id: '#3', created: 1536077800, files: ['.pnp.js', 'yarn.lock'] } ]) .join(',') === [ "#1", "#2", "#3" ].join(',') ); console.assert( mergeAllPRs([ { id: '#1', created: 1536074100, files: ['README.md'] }, { id: '#2', created: 1536078700, files: ['README.md'] }, { id: '#3', created: 1536097800, files: ['README.md'] } ]).join(',') === [ "#1" ].join(',') ); console.assert( mergeAllPRs([ { id: '#1', created: 1536077100, files: ['.gitignore', 'README.md'] }, { id: '#2', created: 1536077700, files: ['index.js', 'package-lock.json', 'package.json'] }, { id: '#3', created: 1536077800, files: ['.pnp.js', 'package-lock.json', 'yarn.lock'] }, { id: '#4', created: 1536077900, files: ['index.spec.js', 'index.spec.ts', 'index.ts'] } ]) .join(',') === [ "#1", "#2", "#4" ].join(',') );
— ,
.
, « » (, ).
, , , . ( some includes). — O(n
2 ).
, , ( .
). — O(n).
:
function conflicts(a, b) { let i = 0; let j = 0; while (i < a.length && j < b.length) { if (a[i] === b[j]) { return true; } else if (a[i] > b[j]) { j++; } else { i++; } } return false; } function mergeAllPrs (input) { let i = 0; const mergedFiles = []; const mergedPrs = []; while (i < input.length) { const pr = input[i]; if (!conflicts(mergedFiles, pr.files)) { mergedPrs.push(pr); mergedFiles.push(...pr.files); } i++; } return mergedPrs.map(x => x.id); };
, , . , :
console.assert( mergeAllPrs([ { "id": "1", "created": 1538179200, "files": [ "a", "b", "c", "d" ] }, { "id": "2", "created": 1538189200, "files": [ "a", "x" ] }, { "id": "3", "created": 1538199200, "files": [ "b", "g" ] }, { "id": "4", "created": 1538209200, "files": [ "c", "f" ] }, { "id": "5", "created": 1538219200, "files": [ "d", "w" ] } ]) .join(',') === ['2', '3', '4', '5'].join(',') );
, ( , ).
: «» -, «» — ( ). ( ).
:
[ { "id": "#1", "created": 1536077100, "files": [ ".gitignore", "README.md" ] }, { "id": "#2", "created": 1536077700, "files": [ "index.js", "package-lock.json", "package.json" ] }, { "id": "#3", "created": 1536077800, "files": [ "index.js" ] } ]
#2 #3 , ["#1", "#2"]. .
, .
, — O(n
2 ), . .
, , . , , .
conflicts , . :
const conflictMatrix = new Uint8Array(prs.length ** 2); const prToIndex = new WeakMap(); for (let i = 0; i < prs.length; i++) { const pr1 = prs[i]; prToIndex.set(pr1, i); conflictMatrix[i * prs.length + i] = 0; for (let j = i + 1; j < prs.length; j++) { const pr2 = prs[j]; conflictMatrix[i * prs.length + j] = conflictMatrix[j * prs.length + i] = conflicts(pr1.files, pr2.files); } } function doPRsConflict(pr1, pr2) { const i = prToIndex.get(pr1); const j = prToIndex.get(pr2); return conflictMatrix[i * prs.length + j] === 1; }
«» , . ( ) , . , , - .
, , .
function getNonConflictingPRs (prsSet, mergedPrs) { const result = []; const prsToTest = [...prsSet, ...mergedPrs]; prsSet.forEach((pr) => { if (!conflictsWithSomePR(pr, prsToTest)) { result.push(pr); } }); return result; }
.
const fullSearch = (prsSet, mergedPrs = [], mergedFilesCount = 0) => { hits++;
.