[코드 2020의 등장] 16일차 튜토리얼(타자 스크립트)

이 글은 최초로 발표되었다kais.blog.코드 2020 이벤트에 대한 일련의 단계별 자습서의 일부입니다.
만약 당신이 나의 내용을 좋아한다면, 당신은 더 많은 것을 보고 싶을 것이다.
질문, 피드백, 아니면 그냥 얘기하고 싶어요?가입해 주세요Discord!

선결 조건
나는 퍼즐을 lines 라는 그룹에 입력했다고 가정합니다. 그 중 모든 항목은 텍스트 파일을 입력하는 한 줄입니다.텍스트 파일을 직접 해석하거나 수동으로 그룹을 만들 수 있습니다.

const lines = [
  "departure location: 28-787 or 804-964",
  "departure station: 41-578 or 594-962",
  "departure platform: 50-718 or 733-949",
  …
];

솔루션

전언
10일째부터 나는 이 두 부분의 해결 방안을 발표할 것이며, 매 단계를 설명하지 않을 것이다.불행하게도, 나는 매일 완전한 단계별 강좌를 제공할 수 없다.사용하는 개념은 나날이 어려워진다.그래서 내가 얻은 결론은 앞으로 이런 개념에 대해 단독 블로그 댓글을 쓰는 것이 좋다는 것이다.
그리고 지금은 휴가철이다.이것은 심사숙고한 강좌를 만드는 것을 더욱 어렵게 만들었다.단, 나는 나의 코드 예시에 대해 약간의 주석을 달려고 시도할 것이다.이렇게 하면 너는 내가 무엇을 했는지 이해할 수 있다.
현재, 나는 계속해서 정기적으로 웹 개발자에게 유용한 힌트를 공유할 것이다.이것들은 당신이 더 좋은 개발자가 되는 것을 도울 것이다.또한 공유된 힌트는 우리가 코드가 나타날 때 겪는 문제를 해결하는 데 도움이 될 것이다.다음은 제 첫 번째 게시물입니다.

수수께끼
내가 무슨 말을 하는지 알기 위해 오늘의 수수께끼를 봐라.
Day 16: Ticket Translation

제1부
오늘, 우리는 필드 목록과 유효한 값 범위를 얻었다.이 밖에 우리는 또 약간의 가치 있는 표를 받았다.그러나, 우리는 어느 값이 어느 필드를 인용하는지 모른다.
첫 번째 부분에서, 우리의 임무는 부근의 모든 어음에서 모든 무효 값을 찾는 것입니다. (퍼즐 입력 참조)그럼 어떻게 할까요?우선, 퍼즐 입력에서 모든 필드를 검색합시다.이를 위해 parseFields 함수를 만들었습니다.해석한 후에, 우리는 맵을 받았는데, 그 중 필드 이름은 키였다.상응하는 값은 함수(이곳은 validateFns라고 부른다)로 어음을 검증하는 데 쓰인다.이 함수들을 만들기 위해서, 나는 작은 조수 함수 isBetween 를 만들었다.이 함수는 각 필드의 값을 검증할 수 있는 함수를 만드는 데 사용됩니다.
완료되면 모든 잘못된 값을 찾을 수 있습니다.우리는 퍼즐 입력에서 nearbyTickets 을 추출하고 어떤 값이 영원히 무효인지 검사합니다.따라서 우리는 validateFns 중의 모든 함수의 값이 유효한지 테스트해야 한다.
이제 우리는 모두 알았다invalidValues.마지막 단계는 그것들을 한데 합치는 것이다.다음은 완벽한 솔루션입니다.

// Parse fields into a map.
// Then, we have all field names with their corresponding validate function.
const fields = parseFields(lines);

// Get all validate functions from our map.
const validateFns = [...fields.values()];

const invalidValues: number[] = [];

const nearbyTickets = lines.slice(lines.indexOf("nearby tickets:") + 1);

// For each nearby ticket, check if any value is invalid.
// Add invalid values to the `invalidValues` array.
nearbyTickets.forEach((nearbyTicket) => {
  const values = nearbyTicket.split(",").map(Number);

  invalidValues.push(
    ...values.filter(
      (value) => !validateFns.some((validate) => validate(value))
    )
  );
});

// Sum up all invalid values.
return invalidValues.reduce((previous, current) => previous + current);

// Type definition for a validate function.
type ValidateFn = (value: number) => boolean;

// Helper function for creating validate functions.
const isBetween = (min: number, max: number) => (value: number) =>
  value >= min && value <= max;

function parseFields(lines: string[]): Map<string, ValidateFn> {
  const fields = new Map<string, ValidateFn>();

  // Extract name and the rules from a field definition.
  const regex = /^([a-z ]+): (\d+-\d+) or (\d+-\d+)/;

  let i = 0;
  let match = regex.exec(lines[i]);

  // Extract all fields.
  while (match) {
    const [, name, ...rules] = match;

    // Create validate functions for the field.
    const validateFns = rules.map((rule) => {
      const [ruleMin, ruleMax] = rule.split("-").map(Number);
      return isBetween(ruleMin, ruleMax);
    });

    // Create a validate function for the field.
    // If validate function returns `true`, then `value` is valid.
    const validateFn = (value: number) =>
      validateFns.some((validate) => validate(value));

    // Add our field to the map.
    fields.set(name, validateFn);

    i++;
    match = regex.exec(lines[i]);
  }

  return fields;
}

제2부분
두 번째 부분은 우리에게 어느 어음의 가치가 어느 필드에 속하는지 찾아내도록 요구한다.따라서 필드를 다시 해석해 봅시다.그래서 우리는 필드 이름이 있는 맵과 그것들의 검증 함수를 가지고 있다.
우선 1부와 유사한 방법을 사용하겠습니다.우리는 모든 무효치의 표를 버릴 수 있다.다음에, 우리는 어떤 방식으로 어느 값이 어느 필드에 속하는지 확인해야 한다.어음을 더욱 편리하게 사용하기 위해서, 나는 우리의 validNearbyTickets 를 다른 columns 이라는 수조로 바꾸었다.현재, 우리 columns 그룹의 모든 요소는 하나의 필드의 모든 값을 포함하는 다른 그룹입니다.
이 columns 수조는 어떤 필드가 어떤 값에 사용할 수 있는지 검사할 수 있도록 합니다.내가 쓴 reducePossibilities 함수를 사용하면, 우리는 어떤 값이 어느 필드에 속하는지 확실히 알 때까지 가능성을 줄일 수 있다.
이제 * 로 시작하는 필드의 값만 티켓에서 찾을 수 있습니다. 이 모든 값을 곱하는 것이 수수께끼 해결 방안입니다. 다음은 완전한 해결 방안입니다.

// Parse fields into a map.
// Then, we have all field names with their corresponding validate function.
const fields = parseFields(lines);

// Get all validate functions from our map.
const validateFns = [...fields.values()];

const nearbyTickets = lines.slice(lines.indexOf("nearby tickets:") + 1);

// For each nearby ticket, check if any value is invalid.
// If the nearby ticket contains invalid values, throw it away.
const validNearbyTickets = nearbyTickets
  .map((nearbyTicket) => nearbyTicket.split(",").map(Number))
  .filter(
    (values) =>
      !values.some(
        (value) => !validateFns.some((validate) => validate(value))
      )
  );

// Use transposition. Thus, each element contains all values for a single field.
const columns = validNearbyTickets[0].map((x, i) =>
  validNearbyTickets.map((x) => x[i])
);

const columnsWithPossibleFields = new Map<number, Set<string>>();

// Check which fields these values could belong to.
columns.forEach((values, i) => {
  const possibleFields = new Set<string>();

  for (const [name, validateFn] of fields.entries()) {
    const valid = values.every((value) => validateFn(value));

    if (valid) {
      possibleFields.add(name);
    }
  }

  columnsWithPossibleFields.set(i, possibleFields);
});

// Reduce possiblities until it's clear to which fields the values belong.
reducePossibilities([...columnsWithPossibleFields.values()]);

// Map a column (with its values) to a single field.
const columnToField = new Map<number, string>();
for (const [column, possibleFields] of columnsWithPossibleFields.entries()) {
  columnToField.set(column, [...possibleFields.values()][0]);
}

const myTicket = lines[lines.indexOf("your ticket:") + 1]
  .split(",")
  .map(Number);

const result: number[] = [];

// Get all values from our ticket where field name starts with `"departure"`.
for (const [column, field] of columnToField.entries()) {
  if (!field.startsWith("departure")) continue;
  result.push(myTicket[column]);
}

// Return the product of those values.
return result.reduce((previous, current) => previous * current);

function reducePossibilities(sets: Set<string>[]): void {
  // Sort sets so the smallest set comes first.
  sets.sort((a, b) => a.size - b.size);

  const smallestSet = sets.shift();

  if (!smallestSet) {
    return;
  }

  if (smallestSet.size > 1) {
    throw new Error();
  }

  const value = [...smallestSet.values()][0];

  // Delete the value from this set from all other sets.
  sets.forEach((set) => {
    set.delete(value);
  });

  // Keep on reducing until we can't continue anymore.
  reducePossibilities(sets);
}

// Type definition for a validate function.
type ValidateFn = (value: number) => boolean;

// Helper function for creating validate functions.
const isBetween = (min: number, max: number) => (value: number) =>
  value >= min && value <= max;

function parseFields(lines: string[]): Map<string, ValidateFn> {
  const fields = new Map<string, ValidateFn>();

  // Extract name and the rules from a field definition.
  const regex = /^([a-z ]+): (\d+-\d+) or (\d+-\d+)/;

  let i = 0;
  let match = regex.exec(lines[i]);

  // Extract all fields.
  while (match) {
    const [, name, ...rules] = match;

    // Create validate functions for the field.
    const validateFns = rules.map((rule) => {
      const [ruleMin, ruleMax] = rule.split("-").map(Number);
      return isBetween(ruleMin, ruleMax);
    });

    // Create a validate function for the field.
    // If validate function returns `true`, then `value` is valid.
    const validateFn = (value: number) =>
      validateFns.some((validate) => validate(value));

    // Add our field to the map.
    fields.set(name, validateFn);

    i++;
    match = regex.exec(lines[i]);
  }

  return fields;
}

결론
오늘의 퍼즐은 다음날에 대한 사람들의 추억을 불러일으켰다.검증하다.그러나 이번에는 크게 다르다.가장 어려운 부분은 필드 값을 찾을 수 있는 모든 가능성을 줄이는 것이다.그럼에도 불구하고 우리는 해냈다.
이 글을 읽어 주셔서 대단히 감사합니다.친구나 동료와 공유하는 것을 고려해 주십시오.내일 만나요!
만약 당신이 나의 내용을 좋아한다면, 당신은 더 많은 것을 보고 싶을 것이다.
질문, 피드백, 아니면 그냥 얘기하고 싶어요?가입해 주세요Discord!
이 글은 최초로 발표되었다kais.blog.