고소 이모

코드 출현 2015 16일차

1 부

500개 중 1개 - 충분히 쉬워 보입니다

작업 알고리즘 작성

500개 중 1개 - 충분히 쉬워 보입니다.

내 가정:

실제 선물의 일부와 모두 일치하는 속성 및 값에 대한 각 이모의 선물 속성 확인을 마치면...

...한 개만 있을 것입니다

옵션이 둘 이상인 경우 옵션을 추가로 제거하려면 어떻게 해야 합니까?

작동하는 알고리즘 작성

먼저 실제 선물을 개체로 저장합니다.

const gift = {
  children: 3,
  cats: 7,
  samoyeds: 2,
  pomeranians: 3,
  akitas: 0,
  vizslas: 0,
  goldfish: 5,
  trees: 3,
  cars: 2,
  perfumes: 1
}

각 입력 라인은 다음 패턴을 따릅니다.

Sue (1-500): (compound: [0-10],?){3}

다음을 추출해야 합니다.

ID:1-500

세 가지 화합물

세 가지 금액: 0-10

이regex가 작업을 처리해야 합니다.

/\d+|\w+/g

\d+는 임의의 연속 숫자

와 일치합니다.

\w+는 임의의 연속 문자

와 일치합니다.

| 왼쪽 비트 또는 오른쪽 비트

와 일치합니다.

이 예에서 이를 사용regex:

Sue 234: goldfish: 9, cats: 4, cars: 7

다음과 같은 배열을 반환해야 합니다.

['Sue', '234', 'goldfish', '9', 'cats', '4', 'cars', '7']

다음으로 이를 다음과 같은 객체로 변환해야 합니다.

{
  id: 234,
  goldfish: 9,
  cats: 4,
  cars: 7
}

그리고 그것을 Sue 이모 모두를 나타내는 객체를 포함하는 배열에 추가합니다.

JavaScript의 알고리즘은 다음과 같습니다.

const Sues = input.reduce(
  (list, gift) => {
    let [,id,c1,a1,c2,a2,c3,a3] = 
      [...gift.matchAll(/\d+|\w+/g)].map(match => match[0])
    let obj = {}
    obj[id] = +id
    obj[c1] = +a1
    obj[c2] = +a2
    obj[c3] = +a3
    list.push(obj)
    return list
  }, []
)

마지막으로 진짜 수 이모를 찾아야 합니다.

의사 코드로서의 내 알고리즘 :

For each gift from a Sue
  Generate a nested array of each compound and its value
  Check whether the gift contains that exact value for each compound
  Keep the gift only if each compound and its value match those in the actual gift

Return the ID of the only gift that matched

내 알고리즘을 JavaScript로:

return sues.filter(
  sue => Object.entries(sue)
    .slice(1)
    .map(el => gift[el[0]] == el[1])
    .every(el => el == true)
)[0].id

정답을 생성했습니다!

2 부

더 어려운 범위

도전에 대한 오해

작업 알고리즘 작성

더 빠른 알고리즘 작성

더 어려운 범위

cats 및 trees : >

pomeranians 및 goldfish : <

이것이 내 알고리즘에 어떤 영향을 미칩니까?

도전에 대한 오해

실제 선물에 있는 숫자가 고소이모 각각의 선물의 복리로 정해진 범위 안에 있는지 확인을 해봐야 겠다는 생각이 들었습니다

하지만 그 반대입니다. 수 이모의 선물에 있는 각 화합물의 가치에 있는 숫자가 실제 선물에 지정된 범위 내에 있는지 확인해야 합니다

.

작동하는 알고리즘 작성

내 업데이트된 선물 개체는 이제 다음 범위를 설명합니다.

const gift = {
  children: 3,
  cats: [8,9,10],
  samoyeds: 2,
  pomeranians: [0,1,2],
  akitas: 0,
  vizslas: 0,
  goldfish: [0,1,2,3,4],
  trees: [4,5,6,7,8,9,10],
  cars: 2,
  perfumes: 1
}

화합물의 값이 switch 문으로 시작된 일치 여부를 결정하기 위한 제어 흐름:

switch (compound) {
  case 'cats':
    // is value in the range?
    break;
  case 'trees':
    // is value in the range?
    break;
  case 'pomeranians':
    // is value in the range?
    break;
  case 'goldfish':
    // is value in the range?
    break;
  default:
    // is value equivalent?
}

그런 다음 ternary operator 구문을 사용하면 훨씬 더 간결해질 수 있다는 것을 깨달았습니다.

['cats','trees','pomeranians','goldfish']
  .includes(compound) ? 
  gift[compound].includes(value) : 
  gift[compound] == value

내 파트 1 알고리즘의 다른 모든 것은 변경되지 않았습니다.

정답을 생성했습니다!

더 빠른 알고리즘 작성

reduce() 및 filter를 사용하면 선물 500개의 전체 입력 목록을 두 번 반복합니다

.

1000회 반복은 별거 아닙니다. 물론입니다

하지만 하나의 결과만 찾고 있습니다

일치 항목을 찾을 때까지 필요한 만큼의 입력 라인에 대해서만 이 모든 작업을 수행할 수 없습니까?

대신에:

Generate an array of objects from the input list
Check each object for a match of every compound and value
Return the only object that matched

find()를 사용하여 불필요한 작업을 많이 줄일 수 있습니다.

Search the input list of strings for the first - and only - match where:
  After extracting the values using regex
  And creating an object
  And comparing that object's compound's values to the actual gift
  All are a match

나는 같은 작업을 수행하지만 일치 항목을 찾는 데 필요한 만큼의 목록 항목에 대해서만 수행합니다!

JavaScript에서 내 빠른 알고리즘:

input.find(gift => {
  let [,id,c1,a1,c2,a2,c3,a3] = 
    [...gift.matchAll(/\d+|\w+/g)].map(match => match[0])
  let obj = {}
  obj.id = +id
  obj[c1] = +a1
  obj[c2] = +a2
  obj[c3] = +a3
  return Object.entries(obj)
    .slice(1)
    .map(pair => 
      ['cats','trees','pomeranians','goldfish']
        .includes(el[0]) ? 
        gift[pair[0]].includes(pair[1]) : 
        gift[pair[0]] == pair[1]
    )
    .every(bool => bool == true)
})

느린 알고리즘과 빠른 알고리즘 비교:

해냈어!!

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

regex , Array , reduce() , filter() 및 map() 와 같은 includes() 및 find() 메서드 사용

알고리즘을 더 빠르게 만들 수 있는 기회를 인식하고 구현했습니다!

화합물의 값이 어떻게 작용하는지 오해하여 엑스트라 하드 모드에서 파트 2를 풀었습니다!

이 퍼즐이 생각보다 비교적 쉬워서 다행입니다.

커브볼보다 로브를 선호하는 경우도 있습니다.