Добрый день.
Принимал участие в чемпионате по программированию.
Хочу понять как решить одну задачку. Не прошу писать решение, но хотелось бы получить рекомендации. Какие алгоритмы используются для решения подобного рода задач?
Может быть ссылки на ресурсы, где есть похожие задания. Буду очень благодарен.
Ниже условия:
В 2158 году всемирная организация ООПН (Организация Объединенных Программирующих Наций) приняла закон об амнистии. В его рамках заключения могли избежать осуждённые по не особо тяжким преступлениям, способные исправить важные для всего мира программы. Один из тех, кому выпала такая возможность, Джекки, на самом деле осуждён ошибочно, поэтому ему разрешили выйти на контакт, но только с одним случайным человеком. По воле случая таким человеком оказались вы.
Потратив несколько часов на исследование доставшейся ему проблемы, Джекки дошел до причины ошибки. Все дело оказалось в некорректном использовании экземпляров, порождаемых фабрикой объектов ‘Q‘. Фабрика возвращает один экзмепляр, если в ‘Q‘ передать строку, и массив, если в ‘Q‘ передать массив строк. В тех экземплярах, которые были возвращены в массиве, нет метода ‘r‘, а, следовательно, его использование в них невозможно, то есть ‘Q([’a’])[0].r()‘ является ошибкой.
Предоставленный ему код достаточно большой, а времени мало, да и метод ‘r‘ вызывается очень часто. Джекки необходимо находить необходимые места кода автоматически. Помогите написать проверку, которая находила бы в коде запрещённые использования метода ‘r‘ (то есть в тех экземплярах, которые были порождены фабрикой ‘Q‘, вызванной с массивом строк).
Про код, переданный Джекки, известно, что:
он написан на es3,
переменные получают свои значения при декларации и не переписываются, т.е. в коде не будет подобного ‘var a = x; a = y;‘ и ‘var a = b = 1;‘,
обращение к свойствам объекта возможно как через точку, так и через скобки (‘a.b‘ и ‘a[’b’]‘),
часть выражения может быть сохранена в переменной, но никогда не передаётся в функцию параметром (‘a(x)‘ — запрещено),
нет функций, которые возвращают часть искомого выражения,
нет свойств объектов или элементов массивов, которые содержат часть выражения,
при обращении к свойству объекта, название свойства может быть взято из переменной (‘a[x]‘, x — переменная).
Проверка должна быть оформлена в виде CommonJS-модуля, который экспортирует функцию, принимающую на вход абстрактное синтаксическое дерево (ast) проверяемого кода.
Функция должна вернуть массив из ast-узлов, которые соответствуют местам вызова метода ‘r‘. Порядок элементов в массиве не важен, дубли не допускаются.
Код, который можно взять за основу для обхода дерева:
ссылка:
https://codepen.io/alex-buki/pen/xxxgzbJ
Данные на ввод:
{
"type": "File",
"start": 0,
"end": 53,
"program": {
"type": "Program",
"start": 0,
"end": 53,
"sourceType": "script",
"interpreter": null,
"body": [
{
"type": "ExpressionStatement",
"start": 0,
"end": 25,
"expression": {
"type": "CallExpression",
"start": 0,
"end": 24,
"callee": {
"type": "MemberExpression",
"start": 0,
"end": 22,
"object": {
"type": "MemberExpression",
"start": 0,
"end": 10,
"object": {
"type": "CallExpression",
"start": 0,
"end": 7,
"callee": {
"type": "Identifier",
"start": 0,
"end": 1,
"name": "Q"
},
"arguments": [
{
"type": "ArrayExpression",
"start": 2,
"end": 6,
"elements": [
{
"type": "StringLiteral",
"start": 3,
"end": 5,
"extra": {
"rawValue": "",
"raw": "''"
},
"value": ""
}
]
}
]
},
"property": {
"type": "NumericLiteral",
"start": 8,
"end": 9,
"extra": {
"rawValue": 0,
"raw": "0"
},
"value": 0
},
"computed": true
},
"property": {
"type": "Identifier",
"start": 21,
"end": 22,
"name": "r"
},
"computed": false
},
"arguments": []
}
},
{
"type": "ExpressionStatement",
"start": 27,
"end": 52,
"expression": {
"type": "CallExpression",
"start": 27,
"end": 51,
"callee": {
"type": "MemberExpression",
"start": 27,
"end": 49,
"object": {
"type": "MemberExpression",
"start": 27,
"end": 37,
"object": {
"type": "CallExpression",
"start": 27,
"end": 34,
"callee": {
"type": "Identifier",
"start": 27,
"end": 28,
"name": "Q"
},
"arguments": [
{
"type": "ArrayExpression",
"start": 29,
"end": 33,
"elements": [
{
"type": "StringLiteral",
"start": 30,
"end": 32,
"extra": {
"rawValue": "",
"raw": "''"
},
"value": ""
}
]
}
]
},
"property": {
"type": "NumericLiteral",
"start": 35,
"end": 36,
"extra": {
"rawValue": 0,
"raw": "0"
},
"value": 0
},
"computed": true
},
"property": {
"type": "Identifier",
"start": 48,
"end": 49,
"name": "m"
},
"computed": false
},
"arguments": []
}
}
],
"directives": []
}
}
На выходе получаем:
[
{
"type": "Identifier",
"start": 21,
"end": 22,
"name": "r"
}
]
