Алгоритмы и структуры данных

4.7. Демонстрация - Примерная реализация

Шаг 1

Начнём реализацию нашей задачи с самого простого случая: если матрица пуста, то и возвращать мы будем null. А вот если она не пуста, то нам, как и полагается в алгоритмах «Разделяй и властвуй», нужно упрощать её до тех пор, пока она не будет простейшей. То есть состоящей из одного единственного элемента. Будем разделять задачи поиска на три подзадачи. Разделим нашу матрицу посередине на четыре части. В двух из них (верхняя правая и левая нижняя) мы будем запускать этот же алгоритм рекурсивно всегда, так как в обеих может оказаться искомый элемент. В нижнюю правую будем идти, только если искомый элемент больше середины, а в верхнюю левую — если меньше. Ничего страшного, если вы не дошли до этого разбиения самостоятельно. И ничего страшного, если вам не кажется это разбиение очевидным. Всё приходит с опытом и насмотренностью! Чтобы интуитивно понять суть такого разбиения, можете самостоятельно составить матрицу из чисел, отсортированных подобным образом, и поискать там случайные числа. Уверены, как только вы начнёте искать, всё сразу станет ясно!


import {log} from "./logger";

/*
searchScore(data, 4) => {
  "guild": "seabass",
  "placement": 4,
}
searchScore(data, 14) => null
*/

function searchScore(leaderboard, leaguePoints) {
  if (!(leaderboard.length && leaderboard[0].length)) {
    return null;
  }

  return null;
}


const data = [
  [
    {
      "login": "stypeano",
      "leaguePoints": 4,
      "guild": "seabass",
    },
    {
      "login": "rstrazir",
      "leaguePoints": 356,
      "guild": "seabass",
    },
    {
      "login": "cathead",
      "leaguePoints": 930,
      "guild": "seabass",
    },
    {
      "login": "cavernous",
      "leaguePoints": 1056,
      "guild": "seabass",
    }
  ],
  [
    {
      "login": "ConspiracyLil",
      "leaguePoints": 18,
      "guild": "goldfish",
    },
    {
      "login": "CzarStories",
      "leaguePoints": 568,
      "guild": "goldfish",
    },
    {
      "login": "GottaSaiyan",
      "leaguePoints": 931,
      "guild": "goldfish",
    },
    {
      "login": "Mountaintrid",
      "leaguePoints": 1130,
      "guild": "goldfish",
    }
  ],
  [
    {
      "login": "Rectionom",
      "leaguePoints": 42,
      "guild": "catfish",
    },
    {
      "login": "JoshChase",
      "leaguePoints": 931,
      "guild": "catfish",
    },
    {
      "login": "DreamLess",
      "leaguePoints": 956,
      "guild": "catfish",
    },
    {
      "login": "BlondiePlanet",
      "leaguePoints": 1045,
      "guild": "catfish",
    }
  ],
  [
    {
      "login": "Breakingbing",
      "leaguePoints": 64,
      "guild": "bream",
    },
    {
      "login": "Goldenelox",
      "leaguePoints": 932,
      "guild": "bream",
    },
    {
      "login": "SaiyanBroadway",
      "leaguePoints": 1432,
      "guild": "bream",
    },
    {
      "login": "BoostScooby",
      "leaguePoints": 1476,
      "guild": "bream",
    }
  ]
]

log(4, searchScore(data, 4));
log(14, searchScore(data, 14));

Шаг 2

Осталось только аккуратно реализовать нашу задумку. Напишем функцию-помощника для нашей задачи. Она будет принимать больше аргументов, чем исходная задача: таблицу лидеров, искомое и 4 границы поиска (ведь нам нужно как-то понимать внутри подзадач, где именно нужно искать). В ней же и будем создавать по три подзадачи, а в исходной задаче будем вызывать новую функцию, передавая ей границами всю нашу матрицу.


import {log} from "./logger";

/*
searchScore(data, 4) => {
  "guild": "seabass",
  "placement": 4,
}
searchScore(data, 14) => null
*/

function searchSubtask(leaderboard, leaguePoints, topBorder, leftBorder, bottomBorder, rightBorder) {
  return null;
}

function searchScore(leaderboard, leaguePoints) {
  if (!(leaderboard.length && leaderboard[0].length)) {
    return null;
  }

  const bottomBorder = leaderboard.length - 1;
  const rightBorder = leaderboard[0].length - 1;

  return searchSubtask(leaderboard, leaguePoints, 0, 0, bottomBorder, rightBorder);
}


const data = [
  [
    {
      "login": "stypeano",
      "leaguePoints": 4,
      "guild": "seabass",
    },
    {
      "login": "rstrazir",
      "leaguePoints": 356,
      "guild": "seabass",
    },
    {
      "login": "cathead",
      "leaguePoints": 930,
      "guild": "seabass",
    },
    {
      "login": "cavernous",
      "leaguePoints": 1056,
      "guild": "seabass",
    }
  ],
  [
    {
      "login": "ConspiracyLil",
      "leaguePoints": 18,
      "guild": "goldfish",
    },
    {
      "login": "CzarStories",
      "leaguePoints": 568,
      "guild": "goldfish",
    },
    {
      "login": "GottaSaiyan",
      "leaguePoints": 931,
      "guild": "goldfish",
    },
    {
      "login": "Mountaintrid",
      "leaguePoints": 1130,
      "guild": "goldfish",
    }
  ],
  [
    {
      "login": "Rectionom",
      "leaguePoints": 42,
      "guild": "catfish",
    },
    {
      "login": "JoshChase",
      "leaguePoints": 931,
      "guild": "catfish",
    },
    {
      "login": "DreamLess",
      "leaguePoints": 956,
      "guild": "catfish",
    },
    {
      "login": "BlondiePlanet",
      "leaguePoints": 1045,
      "guild": "catfish",
    }
  ],
  [
    {
      "login": "Breakingbing",
      "leaguePoints": 64,
      "guild": "bream",
    },
    {
      "login": "Goldenelox",
      "leaguePoints": 932,
      "guild": "bream",
    },
    {
      "login": "SaiyanBroadway",
      "leaguePoints": 1432,
      "guild": "bream",
    },
    {
      "login": "BoostScooby",
      "leaguePoints": 1476,
      "guild": "bream",
    }
  ]
]

log(4, searchScore(data, 4));
log(14, searchScore(data, 14));

Шаг 3

Условия окончания поиска у нас будут похожи на бинарный поиск. Если границы поиска пересеклись и верхняя граница стала ниже нижней (или правая левее левой), значит, поиск в этих границах точно ничего не даст, там мы всё уже просмотрели. А если левая и правая, нижняя и верхняя границы равны между собой, то мы как раз находимся в матрице из одного элемента, и нам нужно вернуть результат, если этот элемент и есть наше искомое!


import {log} from "./logger";

/*
searchScore(data, 4) => {
  "guild": "seabass",
  "placement": 4,
}
searchScore(data, 14) => null
*/

function searchSubtask(leaderboard, leaguePoints, topBorder, leftBorder, bottomBorder, rightBorder) {
  if (leftBorder > rightBorder || topBorder > bottomBorder) {
    return null;
  }

  if (leftBorder === rightBorder && topBorder === bottomBorder) {
    const candidate = leaderboard[topBorder][leftBorder];

    return candidate.leaguePoints === leaguePoints
      ? {
        guild: candidate.guild,
        placement: leaderboard[topBorder].length - leftBorder,
      }
      : null
  }

  return null;
}

function searchScore(leaderboard, leaguePoints) {
  if (!(leaderboard.length && leaderboard[0].length)) {
    return null;
  }

  const bottomBorder = leaderboard.length - 1;
  const rightBorder = leaderboard[0].length - 1;

  return searchSubtask(leaderboard, leaguePoints, 0, 0, bottomBorder, rightBorder);
}


const data = [
  [
    {
      "login": "stypeano",
      "leaguePoints": 4,
      "guild": "seabass",
    },
    {
      "login": "rstrazir",
      "leaguePoints": 356,
      "guild": "seabass",
    },
    {
      "login": "cathead",
      "leaguePoints": 930,
      "guild": "seabass",
    },
    {
      "login": "cavernous",
      "leaguePoints": 1056,
      "guild": "seabass",
    }
  ],
  [
    {
      "login": "ConspiracyLil",
      "leaguePoints": 18,
      "guild": "goldfish",
    },
    {
      "login": "CzarStories",
      "leaguePoints": 568,
      "guild": "goldfish",
    },
    {
      "login": "GottaSaiyan",
      "leaguePoints": 931,
      "guild": "goldfish",
    },
    {
      "login": "Mountaintrid",
      "leaguePoints": 1130,
      "guild": "goldfish",
    }
  ],
  [
    {
      "login": "Rectionom",
      "leaguePoints": 42,
      "guild": "catfish",
    },
    {
      "login": "JoshChase",
      "leaguePoints": 931,
      "guild": "catfish",
    },
    {
      "login": "DreamLess",
      "leaguePoints": 956,
      "guild": "catfish",
    },
    {
      "login": "BlondiePlanet",
      "leaguePoints": 1045,
      "guild": "catfish",
    }
  ],
  [
    {
      "login": "Breakingbing",
      "leaguePoints": 64,
      "guild": "bream",
    },
    {
      "login": "Goldenelox",
      "leaguePoints": 932,
      "guild": "bream",
    },
    {
      "login": "SaiyanBroadway",
      "leaguePoints": 1432,
      "guild": "bream",
    },
    {
      "login": "BoostScooby",
      "leaguePoints": 1476,
      "guild": "bream",
    }
  ]
]

log(4, searchScore(data, 4));
log(14, searchScore(data, 14));

Шаг 4

Ну, а если мы не пришли к базовому случаю, делим нашу задачу на подзадачи, как придумали это в первом шаге!


  import {log} from "./logger";

/*
searchScore(data, 4) => {
  "guild": "seabass",
  "placement": 4,
}
searchScore(data, 14) => null
*/

function searchSubtask(leaderboard, leaguePoints, topBorder, leftBorder, bottomBorder, rightBorder) {
  // Если границы сошлись — ничего не нашлось
  if (leftBorder > rightBorder || topBorder > bottomBorder) {
    return null;
  }

  // Если границы сошлись до единственного элемента, то проверяем, подходит ли он нам
  if (leftBorder === rightBorder && topBorder === bottomBorder) {
    const candidate = leaderboard[topBorder][leftBorder];

    return candidate.leaguePoints === leaguePoints
      ? {
        guild: candidate.guild,
        placement: leaderboard[topBorder].length - leftBorder,
      }
      : null
  }

  const middleY = Math.floor((topBorder + bottomBorder) / 2);
  const middleX = Math.floor((leftBorder + rightBorder) / 2);
  const {leaguePoints: candidateLeaguePoints} = leaderboard[middleY][middleX];

  // Если нам нужно найти части, где количество очков больше, чем по середине, то это...
  if (candidateLeaguePoints < leaguePoints) {
    return searchSubtask(leaderboard, leaguePoints, topBorder, middleX + 1, middleY, rightBorder) // верхняя правая
      || searchSubtask(leaderboard, leaguePoints, middleY + 1, leftBorder, bottomBorder, middleX) // нижняя левая
      || searchSubtask(leaderboard, leaguePoints, middleY + 1, middleX + 1, bottomBorder, rightBorder) // нижняя правая
  // а если меньше, то...
  } else {
    return searchSubtask(leaderboard, leaguePoints, topBorder, middleX + 1, middleY, rightBorder) // верхняя правая
      || searchSubtask(leaderboard, leaguePoints, middleY + 1, leftBorder, bottomBorder, middleX) // нижняя левая
      || searchSubtask(leaderboard, leaguePoints, topBorder, leftBorder, middleY, middleX) // верхняя левая
  }
}

function searchScore(leaderboard, leaguePoints) {
  if (!(leaderboard.length && leaderboard[0].length)) {
    return null;
  }

  const bottomBorder = leaderboard.length - 1;
  const rightBorder = leaderboard[0].length - 1;

  return searchSubtask(leaderboard, leaguePoints, 0, 0, bottomBorder, rightBorder);
}


const data = [
  [
    {
      "login": "stypeano",
      "leaguePoints": 4,
      "guild": "seabass",
    },
    {
      "login": "rstrazir",
      "leaguePoints": 356,
      "guild": "seabass",
    },
    {
      "login": "cathead",
      "leaguePoints": 930,
      "guild": "seabass",
    },
    {
      "login": "cavernous",
      "leaguePoints": 1056,
      "guild": "seabass",
    }
  ],
  [
    {
      "login": "ConspiracyLil",
      "leaguePoints": 18,
      "guild": "goldfish",
    },
    {
      "login": "CzarStories",
      "leaguePoints": 568,
      "guild": "goldfish",
    },
    {
      "login": "GottaSaiyan",
      "leaguePoints": 931,
      "guild": "goldfish",
    },
    {
      "login": "Mountaintrid",
      "leaguePoints": 1130,
      "guild": "goldfish",
    }
  ],
  [
    {
      "login": "Rectionom",
      "leaguePoints": 42,
      "guild": "catfish",
    },
    {
      "login": "JoshChase",
      "leaguePoints": 931,
      "guild": "catfish",
    },
    {
      "login": "DreamLess",
      "leaguePoints": 956,
      "guild": "catfish",
    },
    {
      "login": "BlondiePlanet",
      "leaguePoints": 1045,
      "guild": "catfish",
    }
  ],
  [
    {
      "login": "Breakingbing",
      "leaguePoints": 64,
      "guild": "bream",
    },
    {
      "login": "Goldenelox",
      "leaguePoints": 932,
      "guild": "bream",
    },
    {
      "login": "SaiyanBroadway",
      "leaguePoints": 1432,
      "guild": "bream",
    },
    {
      "login": "BoostScooby",
      "leaguePoints": 1476,
      "guild": "bream",
    }
  ]
]

log(4, searchScore(data, 4));
log(14, searchScore(data, 14));

File logger.js


const results = document.getElementById('results')

export function log(points, placement) {
  const result = document.createElement('li');

  if (!placement) {
    result.innerHTML = `Вы — единствнный игрок со счетом ${points}`;
  } else {
    result.innerHTML = `Ваш счет — ${points}. Вы могли бы играть в гильдии ${placement.guild} и занять там ${placement.placement} место`;
  }

  results.appendChild(result);
}