PBT 2021의 도래 - 1일차 - 솔루션

알고리즘은 lastIndexOf였습니다.

가능한 속성 세트가 포함된 CodeSandbox: https://codesandbox.io/s/advent-of-pbt-day-1-solution-kjm25?file=/src/index.spec.ts&previewwindow=tests

속성 1: 하위 문자열이 있을 때 하위 문자열을 감지해야 합니다.

이 첫 번째 속성에 대해 이미 알려진 특성을 가진 맞춤형 입력을 제공합니다. 두 개의 완전히 임의의 문자열을 사용하는 대신 몇 가지 링크가 함께 있는 두 개의 문자열을 만듭니다.

for any a, b and c strings
b should be seen as a sub-string of a+b+c

다시 말해:

for any a, b and c strings
lastIndexOf(b, a+b+c) should be different from -1
as -1 means no match

빠른 확인으로 작성:

it("should detect a substring when there is one", () => {
  fc.assert(
    fc.property(fc.string(), fc.string(), fc.string(), (a, b, c) => {
      const searchString = b;
      const text = `${a}${b}${c}`;
      expect(lastIndexOf(searchString, text)).not.toBe(-1);
    })
  );
});

이 속성에서는 일치하는 항목이 있으면 일치하는 항목이 있다고 말할 수 있다는 사실만 다루었습니다. 그러나 반환된 인덱스가 올바른지 또는 '일치 항목이 없을 때' 알고리즘이 작동하는지 확인하지 않았습니다.

반환된 인덱스에 대해서는 이 속성을 통해 직접 커버할 수 없습니다. lastIndexOf가 a.length 돌아올 것으로 기대하는 것은 유효한 기대가 아닙니다. 실제로 fast-check가 a="", b="abc", c="abc" , lastIndexOf("abc", "abcabc") = 3 (not a.length )로 나온다고 상상해 봅시다.

속성 2: 하위 문자열이 있는 경우 하위 문자열의 시작 인덱스를 반환해야 합니다.

이전 속성에서 볼 수 있듯이 lastIndexOf에서 반환된 값을 다루는 것이 아니라 일치 항목이 있을 때 일치 항목이 있음을 알려줄 수 있습니다. 이미 lastIndexOf 의 중요한 기능입니다. 그러나 우리는 더 나아가고 싶습니다.
lastIndexOf에서 반환된 값은 아직 사용하지 않은 세부 정보로 가득 차 있습니다. 실제로 lastIndexOf("abc", "abcdabcd") = 4 가 있을 때 인덱스 4 에서 시작하여 "abc" 의 것과 동일한 크기를 갖는 하위 문자열을 가져오면 "abc" 를 찾을 수 있음을 의미합니다. 그 사실을 확인하여 우리의 기능이 실제로 작동하는지 확인합시다.

for any a, b and c strings
the string starting at the index returned by lastIndexOf(b, a+b+c)
and having a size of b.length should be equal to b

빠른 확인으로 작성:

it("should return the start index of the substring when there is one", () => {
  fc.assert(
    fc.property(fc.string(), fc.string(), fc.string(), (a, b, c) => {
      const searchString = b;
      const text = `${a}${b}${c}`;
      const index = lastIndexOf(searchString, text);
      expect(text.substr(index, searchString.length)).toBe(searchString);
    })
  );
});

그러나 우리는 여전히 "일치하지 않는"경우를 다루지 않았습니다. 하지만 그 전에 경기와 관련하여 다루어야 할 한 가지 특성이 있습니다. 정말 마지막 경기인가요?

속성 3: 하위 문자열이 있는 경우 하위 문자열의 가능한 마지막 색인을 반환해야 합니다.

일치 항목이 마지막 항목인 경우 반환된 인덱스 +1에서 시작하는 문자열을 가져오면 일치 항목이 없어야 합니다. 즉, 다음 속성이 참일 것으로 기대합니다.

for any a, b and c strings
the string starting at the index lastIndexOf(b, a+b+c) + 1
should not have b as a sub-string

빠른 확인으로 작성:

it("should return the last possible index of the substring when there is one", () => {
  fc.assert(
    fc.property(
      fc.string(),
      fc.string({ minLength: 1 }),
      fc.string(),
      (a, b, c) => {
        const searchString = b;
        const text = `${a}${b}${c}`;
        const textBis = text.substring(lastIndexOf(searchString, text) + 1);
        expect(lastIndexOf(searchString, textBis)).toBe(-1);
      }
    )
  );
});

이 마지막 속성으로 "일치하지 않는"경우도 다루었습니다. 일치하는 항목을 모두 제거하고 일치하지 않는 부분만 유지하는 즉시 이러한 경우에 해당할 것으로 예상했기 때문입니다.


다른 날에 다룬 주제와 그 해결책을 볼 수 있습니다.

또는 해시태그와 함께 이 시리즈에 대해 자세히 알아보세요.