/* eslint-disable no-console */
/* eslint-disable padding-line-between-statements */
/* eslint-disable prettier/prettier */
const generationSize = 100

const getRandomNumber = max => Math.round(Math.random() * Math.floor(max)) / 10

const getRandomInteger = max => Math.floor(Math.random() * (max + 1))

const generatePoints = N => {
  const points = []
  const currentPointsMap = {}

  while (points.length < N) {
    const point = { x: getRandomNumber(20), y: getRandomNumber(20) }
    const stringifiedPoint = JSON.stringify(point)

    if (!currentPointsMap[stringifiedPoint]) {
      currentPointsMap[stringifiedPoint] = true
      points.push(point)
    }
  }

  return points
}

const shuffle = a => {
  for (let i = a.length - 1; i > 0; i--) {
    const j = Math.floor(Math.random() * (i + 1))
    ;[a[i], a[j]] = [a[j], a[i]]
  }
  return a
}

const generatePopulation = N => {
  const population = []
  for (let i = 0; i < generationSize; i++) {
    const chromosome = shuffle(Array.from({ length: N }, (_, ind) => ind))
    population.push(chromosome)
  }
  return population
}

const getEuclideanDistance = (a, b) =>
  Math.sqrt((a.x - b.x) ** 2 + (a.y - b.y) ** 2)

const calcTotalDistance = points =>
  points.reduce((totalDistance, point, ind, arr) => {
    if (ind === 0) {
      return totalDistance
    }

    const prevPoint = arr[ind - 1]
    const distanceToPrev = getEuclideanDistance(point, prevPoint)

    return totalDistance + distanceToPrev
  }, 0)

const difference = (a, b) => b.filter(el => !a.includes(el))

// const select = (N, initialPopulation) => {
//   const sortedInitialPop = [...initialPopulation].sort(
//     (a, b) =>
//       calcTotalDistance(a.map(ind => points[ind])) -
//       calcTotalDistance(b.map(ind => points[ind]))
//   )

//   return sortedInitialPop.slice(0, N)
// }

const crossOver = (parent1, parent2) => {
  const length = parent1.length
  const [randomInd1, randomInd2] = [
    getRandomInteger(length - 1),
    getRandomInteger(length - 1)
  ]
  const i = Math.min(randomInd1, randomInd2)
  const j = Math.max(randomInd1, randomInd2)
  const p1substr = parent1.slice(i, j + 1)
  const p2substr = parent2.slice(i, j + 1)

  let ch1 = new Array(length).fill(-1)
  let ch2 = new Array(length).fill(-1)

  ch1 = ch1
    .slice(0, i)
    .concat(p1substr)
    .concat(ch1.slice(j + 1))
  ch2 = ch2
    .slice(0, i)
    .concat(p2substr)
    .concat(ch2.slice(j + 1))

  const mapping = {}
  const diff = difference(p1substr, p2substr)

  diff.forEach(missingFromP1 => {
    let ind = parent2.indexOf(missingFromP1)
    let currParent = 0
    const parents = [parent1, parent2]

    while (ind === -1 || (i <= ind && ind <= j)) {
      const el = parents[currParent][ind]
      currParent = (currParent + 1) % 2
      ind = parents[currParent].indexOf(el)
      currParent = (currParent + 1) % 2
    }

    mapping[missingFromP1] = parents[(currParent + 1) % 2][ind]
  })

  Object.entries(mapping).forEach(entry => {
    const [fromP1, fromP2] = entry
    const fromP1ind = parent1.indexOf(Number(fromP1))
    const fromP2ind = parent2.indexOf(Number(fromP2))

    ch1[fromP2ind] = Number(fromP1)
    ch2[fromP1ind] = Number(fromP2)
  })

  ch1 = ch1.map((el, ind) => (el === -1 ? parent2[ind] : el))
  ch2 = ch2.map((el, ind) => (el === -1 ? parent1[ind] : el))

  return [ch1, ch2]
}

const mutateChromosome = chromosome => {
  const i = getRandomInteger(chromosome.length - 1)
  const j = getRandomInteger(chromosome.length - 1)

  const temp = chromosome[i]
  chromosome[i] = chromosome[j]
  chromosome[j] = temp

  return chromosome
}

const getNextGeneration = currGen => {
  let children = []

  const sortedCurrGen = [...currGen].sort(
    (a, b) =>
      calcTotalDistance(a.map(ind => points[ind])) -
      calcTotalDistance(b.map(ind => points[ind]))
  )

  const best20percent = sortedCurrGen.slice(0, 20)
  const worst6percent = sortedCurrGen.slice(94)

  children = children.concat(best20percent)

  for (let i = 0; i < (currGen.length - 20 - 6) / 2; i++) {
    const [ch1, ch2] = crossOver(currGen[i], currGen[currGen.length - 1 - i])
    children.push(ch1)
    children.push(ch2)
  }

  const mutatedWorst6percent = worst6percent.map(mutateChromosome)

  children = children.concat(mutatedWorst6percent)

  return children
}

// main
const N = 50
const MAX_GENERATIONS = 300
const points = generatePoints(N)
const initialPopulation = generatePopulation(N)

let prevGeneration = initialPopulation
for (let i = 0; i < MAX_GENERATIONS; i++) {
  const newGeneration = getNextGeneration(prevGeneration)
  if ([10, 35, 99, ~~(MAX_GENERATIONS / 2), MAX_GENERATIONS - 1].includes(i)) {
    const min = Math.min(
      ...newGeneration.map(chromosome =>
        calcTotalDistance(chromosome.map(ind => points[ind]))
      )
    )
    console.log("min", min)
  }
  prevGeneration = newGeneration
}