alexbuki
@alexbuki
программист js

Насколько правильное решение задачи?

Возможно, кто-то тут решал подобную задачу, возможно просто будет интересно.
Нашёл одну задачку с Яндекс.Контеста, так как сам контест уже прошел и проверить негде, то хочу понять, насколько правильно решил. Буду очень признателен за комментарии.

Текст задачи:

Слишком надежный проект
В Центре разработки тестирующей системы для тестового окружения написания тестов написаны тесты на каждую строчку кода системы. И после каждой правки кода разработчики должны не только написать новые тесты, но и протестировать изменения, чтобы удостовериться в надежности всей системы.
К сожалению, изначально решили запускать вообще все тесты. Последние запуски выполнялись по 42 года каждый, так что руководство центра решило внедрить оптимизации и запускать тесты только для измененных файлов.
Реализуйте функцию, которая будет выводить список запускаемых на правки тестов.

Формат ввода

Декларативное описание документа выглядит следующим образом:
const input = {
  // абсолютный путь до дирректории проекта в файловой системе
  absoluteRepoPath: '/var/www/projects/project1',
  // список алиасов по путям из исходной системы сборки
  aliases: {
    '@': './src',
  },
  // информация обо всех модулях данного проекта
  modules: [
    {
      // относительный от корня путь
      file: './src/pages/1.js',
      deps: [
        // валидная для исходной системы сборки строка, описывающая путь до модуля
        // гарантируется, что такой модуль существует и описан в данной секции
        '/var/www/projects/project1/src/pages/a.js',
        './b.js',
      ],
      // был ли изменен программный код данного модуля
      // ключ может не присутствовать, это означает, что код не был изменен
      hasChanged: true,
    },
    {
      file: './src/pages/a.js',
      deps: ['@/pages/b.js'],
    },
    {
      file: './src/pages/b.js',
      deps: [],
      hasChanged: true,
    },
  ],
  specs: [
    // информация о тестах
    {
      file: './src/specs/1.js',
      deps: ['/var/www/projects/project1/src/pages/a.js'],
    },
  ],
}


Следует понимать, что изменение является транзитивным отношением:

a.js -> b.js -> c.js -> d.js
Если модуль d.js изменен, это означает, что и все модули в цепочке выше тоже изменились: a.js b.js c.js

Формат вывода

Результатом работы алгоритма должен быть упорядоченный лексикографически массив необходимых для запуска тестов, где каждый тест описывается через абсолютный путь в файловой системе:
[
"/var/www/projects/project1/src/specs/1.js"
]

Если тесты запускать не требуется, указывается пустой массив.
[]

Вот мое решение:
module.exports = function (input) {
  const result = new Set()
  let obj

  if (typeof input == 'string') {
    obj = JSON.parse(input)
  } else {
    obj = input
  }

  const { absoluteRepoPath, aliases, modules, specs } = obj
  const allAliases = {
    ...aliases,
    '.': absoluteRepoPath,
  }
  const modulesMap = new Map()

  function pathToAbsolutePath(path, aliases = {}) {
    for (a in aliases) {
      if (path.startsWith(a)) {
        path = path.replace(a, aliases[a])
      }
    }
    return path
  }

  modules.forEach((module) => {
    const path = pathToAbsolutePath(module.file, allAliases)

    const children = module.deps.map((d) => {
      let dpath = pathToAbsolutePath(d, allAliases)
      modulesMap.set(dpath, { parent: path })
      return dpath
    })

    modulesMap.set(path, { deps: children, hasChanged: module.hasChanged })
  })

  specs.forEach((spec) => {
    const path = pathToAbsolutePath(spec.file, allAliases)

    spec.deps.forEach((m) => {
      const absM = pathToAbsolutePath(m, allAliases)
      const module = modulesMap.get(absM) || {}

      if (module.hasChanged) {
        result.add(path)
      }

      module.deps &&
        module.deps.forEach((d) => {
          const dModule = modulesMap.get(d) || {}

          if (dModule.hasChanged) {
            result.add(path)
          }
        })
    })
  })

  return [...result].sort()
}


Вот ссылка на песочницу с тестом -
  • Вопрос задан
  • 639 просмотров
Пригласить эксперта
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы