배고픈 사람들을 위한 과학

코드 출현 2015 15일차



1 부


  • 연속 콤보
  • 101, 4번?
  • regex를 사용하여 양
  • 추출
  • 작동 알고리즘 애니메이션 및 작성

  • 콤보 계속하기



    올해에는 몇 가지 조합 테마 퍼즐이 등장했습니다.
  • Day 24: It Hangs in the Balance
  • Day 22: Wizard Simulator 20XX
  • Day 21: RPG Simulator 20XX
  • Day 17: No Such Thing as Too Much

  • 오늘이 내가 만나는 마지막 날도 아니라는 느낌이 듭니다.

    101, 4번?


  • 가장 높은 점수를 받은 쿠키를 찾으려면 가능한 모든 쿠키의 점수를 찾은 다음 가장 높은 점수를 결정해야 합니다.
  • 내 입력에는 네 가지 성분이 있습니다
  • .
  • 레시피에는 모든 재료 조합의 100티스푼이 포함되어야 합니다
  • .

    가능한 조합은 다음과 같습니다.

    Ingr.  1   2   3   4
           100 0   0   0
           0   25  26  49
           1   1   1   97
           5   95  2   3
    


    내 순진하고 무차별적인 접근 방식은 4개의 중첩 루프를 사용하여 합이 100이 되는 4개의 숫자를 포함하는 배열 목록을 작성하는 것입니다.

    Set combos to an empty list
    For a from 0 up to and including 100
      For b from 0 up to and including 100
        For c from 0 up to and including 100
          For d from 0 up to and including 100
            If a + b + c + d equals 100
              Add [a, b, c, d] to combos
    


  • 해당 루프는 101 * 101 * 101 * 101번 실행됩니다
  • .
  • 1000만 번 이상입니다
  • 하지만 컴퓨터는 빠르다
  • 1초밖에 걸리지 않습니다
  • 그리고 약 175,000개의 조합 목록을 생성합니다
  • .

    정규식을 사용하여 금액 추출



    이 입력에서:

    Butterscotch: capacity -1, durability -2, flavor 6, texture 3, calories 8
    Cinnamon: capacity 2, durability 3, flavor -2, texture -1, calories 3
    


    다음 목록이 필요합니다.

    [-1, -2,  6,  3]
    [ 2,  3, -2, -1]
    


    간단한 정규 표현식이 필요합니다.

    /-*\d+/g
    


  • -*는 0개 이상의 대시와 일치합니다
  • .
  • \d+는 1개 이상의 숫자와 일치합니다
  • .

    JavaScript에서 문자열에서 숫자 목록으로 이동하는 것은 다음과 같습니다.

    [...ingredient.matchAll(/-*\d+/g)].map(i => +i[0])
    


  • ingredient.matchAll(/-*\d+/g) 각 매치의 세부 정보로 채워진 반복 가능한 목록을 생성합니다
  • .
  • [...] 각 목록 항목을 하나 이상의 배열로 확산
  • .map(i => +i[0]) 각 목록 항목 배열을 첫 번째 항목의 숫자 강제 값인 일치하는 하위 문자열로 변경합니다
  • .

    작동하는 알고리즘 애니메이션 및 작성


  • 이것은 어떤 이유로 인해 일시적으로 '내 머리를 망가뜨렸습니다'
  • 조합 배열에서 시작할지 성분 목록에서 시작할지 고민했습니다
  • .
  • 음수 값을 고려해야 하는 경우

  • 머리를 긁적 거리는 문제 해결 후 마침내 알아 냈습니다.

    그리고 그것은 정답을 생성했습니다!

    의사 코드 내 알고리즘:

    For each 100-teaspoon recipe as a combination of four numbers
      Accumulate a number that represents the highest one among all those encountered, starting at 0
        Create a 4-element array
        For each item in that array
          Start with a copy of the amounts of each ingredient
          Keep only the amount from each ingredient in the same position as the current iteration of this loop
          Multiply the amount by the number of teaspoons in the same position
          Add each item together to get a sum
        Multiply each amount together, replacing any negative amounts with 0
      Compare the resulting product with the current highest number
      Return the highest number
    


    내 알고리즘, 애니메이션:


    자바스크립트 내 알고리즘:

    100_Teaspoon_Recipes.reduce(
      (highest, recipe) => Math.max(
        highest, 
        new Array(4)
          .fill(null)
          .map(
            (_, index) => 
              ingredients
                .map(el => el[index])
                .map((el, index) => el * recipe[index])
                .reduce((sum, num) => sum + num)
          )
          .reduce(
            (product, num) => product *= num < 0 ? 0 : num
          , 1)
      ), 0)
    


  • 3 map() 에스
  • 3 reduce() ers
  • 와우!

  • 파트 2에서 음수 금액과 calories 를 활용하는지 여부와 방법을 확인하게 되어 기쁩니다!

    2 부


  • 칼로리를 올려라!
  • 내 알고리즘 업데이트 중

  • 칼로리를 가져와!


  • 동일한 작업이지만 이전 레시피의 하위 집합만 고려합니다: 500칼로리
  • 이렇게 하려면 내 알고리즘을 약간만 조정하면 됩니다
  • .

    내 알고리즘 업데이트


  • 방정식에 칼로리를 포함해야 하므로 배열에 4개가 아닌 5개의 슬롯이 있어야 합니다
  • .
  • 최고 점수와 현재 점수를 비교하기 전에 모든 계산 후 마지막 슬롯의 숫자가 500인지 확인해야 합니다.
  • 그렇다면 곱셈 단계를 진행할 수 있습니다
  • 그렇지 않은 경우 최고 점수
  • 를 업데이트할 위험이 없도록 점수를 0으로 간주해야 합니다.

    의사 코드 내 알고리즘:

    For each 100-teaspoon recipe as a combination of four numbers
      Accumulate a number that represents the highest one among all those encountered, starting at 0
        Create a 5-element array
        For each item in that array
          Start with a copy of the amounts of each ingredient
          Keep only the amount from each ingredient in the same position as the current iteration of this loop
          Multiply the amount by the number of teaspoons in the same position
          Add each item together to get a sum
        If the last item in the array equals 500
          Remove the last item, as it's not needed to calculate the score
          Multiply each amount together, replacing any negative amounts with 0
      Compare the resulting product - or 0, if there were not 500 calories - with the current highest number
      Return the highest number
    


    자바스크립트 내 알고리즘:

    combos.reduce(
      (highest, recipe) => { 
        let totals = new Array(5)
          .fill(null)
          .map(
            (_, index) => 
              ingredients
                .map(el => el[index])
                .map((el, index) => el * recipe[index])
                .reduce((sum, num) => sum + num)
          )
        let score = 0
        if (totals[4] == 500) {
          score = totals.slice(0,4).reduce(
            (product, num) => product *= num < 0 ? 0 : num
          , 1)
        }
        return Math.max(highest, score)
      }, 0
    )
    


    정답을 생성했습니다!

    해냈어!!


  • 두 부분 모두 해결했습니다!
  • 내 계획된 접근 방식에 대해 당황한 후!
  • 소수의 map()reduce() 방법 사용!

  • 이 퍼즐은 조합 생성 및 배열 조작에 대한 더 많은 훌륭한 연습을 제공했습니다.

    좋은 웹페이지 즐겨찾기