재고 관리 시스템

코드 출현 2018 2일 차

과제: X에 대해 풀기 여기서...

1 부

X = the checksum for my list of box IDs

2 부

X = the letters that are common between the two correct box IDs

예시 입력

abcdef
bababc
abbcde
abcccd
aabcdd
abcdee
ababab

다음을 나타냅니다.

상자 ID 목록

1 부

해야 할 일

단방향 풀기: 각 문자 수 합산

다른 방법으로 해결 시도: 정규 표현식

해야 할 일

다음과 같은 ID를 별도로 식별해야 합니다.

임의의 문자

중 정확히 두 개

모든 문자

중 정확히 3개

주의 사항:

하나의 ID로 두 범주를 모두 충족할 수 있습니다. 그렇다면 둘 다에서 한 번 계산하십시오.

ID는 하나의 범주를 여러 번 수행할 수 있습니다. 그렇다면 해당 범주에 대해 한 번 계산하십시오.

한 가지 방법으로 풀기: 각 문자 수 합산

Create a 2-element tracker array to store the number of two- and three-letter IDs
  Initialize both values to 0
Create a dictionary to sum up each letter count

For each ID
  For each letter
    If the letter is not a key in the dictionary, make it one and initialize it to 1
    Increment the letter's associated integer value by 1

  Generate a list of the values from the dictionary
    If there are any 2s, increment the first element in the tracker array
    If there are any 3s, increment the second element in the tracker array

Return the product of both elements in the tracker array

단일 ID에 대한 알고리즘의 모습:


정답을 생성하기 위해 작성한 JavaScript는 다음과 같습니다.

input.split('\n')
  .reduce((a,c) => {
    let tallies = Object.values(c.split('').reduce((a,c) => {
      (!(c in a)) ? a[c] = 1 : a[c] += 1
      return a
    }, {}))
    a[0] += tallies.includes(2) ? 1 : 0
    a[1] += tallies.includes(3) ? 1 : 0
    return a
  }, [0,0])
  .reduce((a,c) => a * c)

조금split()s

쓰리reduce()s

쓰리 ternaries

그리고 둘includes()

얼마나 간결한지 자랑스럽습니다.

그러나 퍼즐의 이 부분을 해결하는 데 더 효과적인 방법이 있다고 생각합니다.

다른 방법으로 해결하기: 정규 표현식

For each box ID string
  Match exactly two of any letter
  Match exactly three of any letter

이것은 정규 표현식에 완벽하게 적합하다고 느낍니다.

작동하는 것을 쓸 수 있습니까?

문자 중 정확히 두 개를 일치시키려면

일부 문자를 일치시키는 것으로 시작하겠습니다

일치하는 문자와 다음 인스턴스 사이에 0개 이상의 문자가 있을 수 있습니다

.

그런 다음 동일한 문자의 두 번째 인스턴스를 일치시켜야 합니다

.

그런 다음 동일한 문자

의 추가 인스턴스가 없는지 확인해야 합니다.

정규 표현식의 의사 코드는 다음과 같을 수 있습니다.

/ (LETTER), other letters?, LETTER, no more LETTERs/g

처음 세 부분은 저에게 쉽습니다.

/(\w)\w*\1/g

임의의 문자 일치

0개 이상의 문자 일치

같은 문자 일치

문제는 처음에 일치된 문자의 더 이상 존재하지 않는 인스턴스를 일치시키려고 시도할 때 발생합니다.

집합을 사용하여 역참조를 무효화할 수 있습니까? [^\1]

부정 예측을 사용할 수 있습니까? (?!\1)

인터넷 검색 후 a commenter's answer on Stack Overflow에서 해결책처럼 보이는 것을 찾았습니다.

((?!\1).)*

정규 표현식에 통합했습니다.

/(\w)\w*\1((?!\1).)*/g

그러나 내가 원하는 결과를 얻지 못했다는 것을 알았습니다.

정규식을 사용하여 파트 1을 어떻게 해결할 수 있을지 아직도 난감합니다.

가능할 것 같은 느낌이 듭니다.

하지만 탐색을 마쳤습니다.

2 부

한 가지 방법으로 풀기: 모든 문자열 비교

한 가지 방법으로 풀기: 모든 문자열 비교

내가 찾아야 할 것:

IDs which differ by exactly one character at the same position in both strings

내가 제안한 알고리즘:

Set the matching box ID as null
For each box ID string except the last
  Do until all other strings have been compared, or a match was found
    Set the tally of different characters as 0
    Set the character as null
    Do until two characters are different
      Compare the current character in the current string with the current character in the next string
        If they are different
          Increment the tally
          Set the current character as the new different character
    Set the matching box ID as the current box ID string with the single differing character replaced with an empty string
    Escape the loops

Return the matching box ID with the differing character removed

작동 방식을 보여주는 애니메이션:


내 알고리즘에서 while 루프를 사용하려고 했습니다.

내 목표는 두 문자가 달라지는 즉시 각while 루프를 중단하여 마이크로 수준에서 성능을 향상시키는 것이었습니다.

나는 단일for 문이 있는 끝에 조건이 있는 break 루프를 작성했습니다...일치하는 항목이 있는지 확인했습니다.

따라서 큰 성능 향상은 없습니다.

그러나 알고리즘은 여전히 ​​거의 즉각적으로 실행되어 정답을 생성합니다!

해냈어!!

두 부분 모두 해결했습니다!

내 알고리즘이 어떻게 작동하는지 보여주는 몇 개의 GIF를 만들었습니다!

파트 1

을 어떻게 해결했는지 자랑스럽습니다.

버머:

정규 표현식으로 파트 1을 풀지 못해 실망했습니다

.

파트 2: 필요하지 않았을 가능성이 있는 모든 루프 및 비교

를 해결한 방식이 마음에 들지 않습니다.

개인적으로 낮은 점수인 34점에 맞추려면 최소한 1일 차의 파트 1을 풀어야 합니다.

지금까지 Day 1을 해결하는 데 문제가 없었기 때문에 그렇게 할 수 있다고 확신합니다.

갑시다!