교량 수리

Mary-Kate Olsen
Mary-Kate Olsen원래의
2024-12-22 04:17:09130검색

Bridge Repair

2024 코드의 출현 7일차

1부

올해의 첫 재귀

적어도 오늘은 그렇게 해서 금별 하나를 따고 싶습니다.

  • 전체 목록으로 시작
  • 덧셈과 곱셈을 모두 확인하세요
  • 각 결과에 대해 목록의 나머지 부분을 계속 진행하세요
  • 총액을 초과하거나 일치할 때까지

어려움은 디테일에 있습니다.

해보자!

내 알고리즘 만들기

먼저 각 줄을 숫자 목록으로 구문 분석해야 합니다.

let eqs = input.split('\n').map(line => {
  return [...line.matchAll(/\d+/g)].map(el => +el[0])
})

첫 번째 요소는 원하는 합계입니다.

나머지는 방정식의 순서가 지정된 피연산자입니다.

재귀 함수에서 이 점을 고려해야 합니다.

내 재귀 함수는 다음과 같습니다.

function eqChecker(operands, amount, test) {
  if (amount > test) {
    return false
  } else if (amount == test && operands.length == 0) {
    return true
  } else if (operands.length) {
    let copy = operands.slice()
    let first = copy.shift()
    return eqChecker(copy, amount + first, test) || eqChecker(copy, amount * first, test)
  }
}

이를 사용하는 축소는 다음과 같습니다.

let part1 = eqs.reduce((count, eq) => {
  if (eqChecker(eq.slice(2), eq[1], eq[0])) {
    count += eq[0]
  }
  return count
}, 0)

기대했지만 결코 예상하지 못했던 예시 입력에 대한 정답이 생성됩니다!

퍼즐 입력 처리가 완료되나요?

그렇다면 정답이 나올까요?

솔직히 잘 모르겠어요...

해냈습니다!!!

와!!!

다음 부분에서 더 많은 연산자를 추가하거나 재귀를 더 이상 실행 가능한 솔루션으로 만들지 않기 위해 일부 고급 CS가 필요할 것 같아 걱정됩니다.

2부

전혀 예상치 못한 일입니다! 그리고 훨씬 더 어려워요

이걸 어떻게 할 수 있나요?

...

며칠 후...

내 사고 과정 요약:

  • 반품 조건에 세 번째 조항을 추가하는 것만큼 간단합니까? 아니요
  • 제 1부 재귀 기능이 성공을 위해 올바르게 구성되었나요? 아니요
  • 아니요, 이전 작업의 결과로 금액이 적립되는 것이 가능할까요? 아니요
  • 정말 새로운 전략으로 접근해야 할까요? 그렇습니다

모든 새로운 변형을 고려

이 방정식의 경우:

292: 11 6 16 20

다음은 세 연산자가 주어지면 가능한 모든 방정식입니다.

11 
11+6 
11+6+16 
11+6+16+20 
11+6+16*20 
11+6+1620 
11+6*16 
11+6*16+20 
11+6*16*20 
11+6*1620 
11+616 
11*6 
11*6+16 
11*6+16+20 
11*6+16*20 
11*6+1620 
11*6*16 
11*616 
116 
116+16 
116+16+20 
116+16*20 
116+1620 
116*16 
11616 

각 방정식의 문자열을 작성하고 재귀 함수 내에서 수동으로 평가할 수도 있습니다.

예:
가장 바깥쪽 함수 호출에서 빈 문자열로 시작합니다.

""

여기에서 다음 숫자를 사용하여 세 가지 변형을 만듭니다.

"" + "+N"
"" + "*N"
"" + "N"

흠, 하지만 첫 번째 숫자에는 작동하지 않습니다.

빈 문자열이 아닌 첫 번째 숫자로 첫 번째 함수 호출을 시작해야 합니다.

"N"

거기서 같은 내용:

"N" + "+N"
"N" + "*N"
"N" + "N"

네, 그러면 되겠군요.

마지막에는 다음과 같은 샘플 변형을 모두 평가할 수 있게 됩니다.

let eqs = input.split('\n').map(line => {
  return [...line.matchAll(/\d+/g)].map(el => +el[0])
})

건너뛰기: 코딩했는데...더 큰 문제를 발견했습니다.

모든 변형 방정식을 성공적으로 생성하는 코드를 작성했습니다.

function eqChecker(operands, amount, test) {
  if (amount > test) {
    return false
  } else if (amount == test && operands.length == 0) {
    return true
  } else if (operands.length) {
    let copy = operands.slice()
    let first = copy.shift()
    return eqChecker(copy, amount + first, test) || eqChecker(copy, amount * first, test)
  }
}
  • 나는 숫자 목록을 따라가는 데 익숙합니다
  • 마지막 절은 i가 마지막에서 두 번째 인덱스 이전 또는 그 인덱스에 있는 경우에만 진행됩니다

이 함수는 다음 네 가지 값을 얻습니다.

  1. 예상 합계를 뺀 숫자 목록의 사본
  2. 다음지수
  3. 세 문자열 중 하나가 연결된 방정식 문자열
  4. 동일한 시험번호

1부에서와 거의 동일한 시그니처를 사용하여 함수를 호출합니다.

let part1 = eqs.reduce((count, eq) => {
  if (eqChecker(eq.slice(2), eq[1], eq[0])) {
    count += eq[0]
  }
  return count
}, 0)

차이점은 인수로 전달하는 내용입니다.

  1. 예상총액이 없는 목록
  2. 인덱스 0에서 시작
  3. 첫 번째 숫자가 포함된 문자열
  4. 예상총액

좋은 소식:

  • 모든 방정식 변형을 생성합니다

나쁜 소식:

  • 왼쪽에서 오른쪽이 아닌 PEMDAS를 사용하여 모든 방정식을 평가합니다

내장된 JavaScript 평가기가 기본적으로 왼쪽에서 오른쪽이 아닌 올바른 작업 순서를 따른다는 것을 더 잘 알았어야 했습니다.

이것은 내 알고리즘에 훨씬 더 큰 렌치를 던집니다.

  • 각 방정식을 분해하여 부분별로 평가해야 합니다

우우우우우우.

다행히 저는 그 방법을 잘 알고 있는 것 같아요.

수학을 수동으로 수행

다음과 같은 방정식을 평가하려면 JavaScript가 필요합니다.

292: 11 6 16 20

순서는 다음과 같습니다.

11 
11+6 
11+6+16 
11+6+16+20 
11+6+16*20 
11+6+1620 
11+6*16 
11+6*16+20 
11+6*16*20 
11+6*1620 
11+616 
11*6 
11*6+16 
11*6+16+20 
11*6+16*20 
11*6+1620 
11*6*16 
11*616 
116 
116+16 
116+16+20 
116+16*20 
116+1620 
116*16 
11616 

이 방정식을 여러 부분으로 나누고 싶습니다.

""

내가 알 수 있는 유일한 방법은 삼중 연결 표현을 사용하는 것입니다.

"" + "+N"
"" + "*N"
"" + "N"

각 연산자를 구분 기호로만 사용하기 위해 공백으로 채웁니다.

이 방정식 부분 목록에 대한 사실:

  • 항상 3개 이상의 홀수 개수의 항목이 포함됩니다

각 피연산자-연산자-피연산자 쌍을 반복하는 루프에서 이 사실을 어떻게 활용할 수 있나요?

내 생각은 다음과 같습니다.

  • 처음 세 항목 제거
  • 문자열로 결합하여 수학 표현식으로 평가합니다
  • 수식 목록 시작 부분에 결과를 다시 첨부
  • 등식 목록이 빌 때까지 반복

효과가 있기를 바랍니다!

JavaScript로 작업하는 수학 시뮬레이터:

"N"

좋은 소식:

  • 예상 계산값이 표시됩니다

나쁜 소식:

  • 예제 입력에서 하나의 방정식에 대한 정답을 아직 얻지 못했습니다

예시 답변은 틀릴 수 없습니다...그렇죠??

계속 생성되는 답변이 예상 답변보다 7k 정도 부족합니다.

내 알고리즘이 이 방정식을 올바른 것으로 식별하지 못하는 것 같습니다.

let eqs = input.split('\n').map(line => {
  return [...line.matchAll(/\d+/g)].map(el => +el[0])
})

입력 예시 설명 중 승리 방정식은 다음과 같습니다.

function eqChecker(operands, amount, test) {
  if (amount > test) {
    return false
  } else if (amount == test && operands.length == 0) {
    return true
  } else if (operands.length) {
    let copy = operands.slice()
    let first = copy.shift()
    return eqChecker(copy, amount + first, test) || eqChecker(copy, amount * first, test)
  }
}

내 알고리즘은 해당 방정식을 평가하고 다음 결과를 생성합니다.

let part1 = eqs.reduce((count, eq) => {
  if (eqChecker(eq.slice(2), eq[1], eq[0])) {
    count += eq[0]
  }
  return count
}, 0)

그 이유는 내 알고리즘이 다음과 같이 실행되기 때문입니다.

292: 11 6 16 20

어떻게 다른 숫자일 수 있는지 모르겠습니다.

그래서...Google에 검색해 봤습니다.

그리고 늘 그렇듯 일반 사이트에 숨어 있던 답을 설명에서 찾았습니다.

모든 연산자는 여전히 왼쪽에서 오른쪽으로 평가됩니다.

각 재귀 함수 호출에 값을 미리 연결했습니다.

대신 내 알고리즘은 다음을 수행해야 합니다.

11 
11+6 
11+6+16 
11+6+16+20 
11+6+16*20 
11+6+1620 
11+6*16 
11+6*16+20 
11+6*16*20 
11+6*1620 
11+616 
11*6 
11*6+16 
11*6+16+20 
11*6+16*20 
11*6+1620 
11*6*16 
11*616 
116 
116+16 
116+16+20 
116+16*20 
116+1620 
116*16 
11616 

이제 무슨 일이 일어날지 이해했으니 해당 처리 동작에 맞게 알고리즘을 조정할 수 있나요?

왼쪽에서 오른쪽으로...이번엔 진짜

다행히도 알고리즘 조정은 비교적 쉬웠습니다.

||를 설명하기 위해 replacementAll() 절을 추가했습니다.

세 항목마다 처리하는 새로운 while 루프는 다음과 같습니다.

""

그리고 반환문의 || 두 숫자를 즉시 ​​연결하는 대신 해당 문자를 포함하도록 절을 사용하세요.

테스트 및 재테스트

예제 입력에 대해 알고리즘을 실행했습니다.

드디어 정답이 나왔습니다!!

정말 다행이네요!!

실행이 완료되고 내 퍼즐 입력에 정답이 생성될지 궁금합니다.

실행을 누르면...

...

...

답변을 얻었습니다!

규모가 크니 좋은 징조일지도 모르겠습니다.

정답인가요?

...

아니요. 너무 높습니다.

버머.

엣지 케이스가 누락되었나요?

승리 방정식의 조건은 단순히 처리된 수학이 테스트 금액과 일치한다는 것입니다.

그러나 변형 방정식 중 하나가 숫자의 하위 집합을 통해 정답을 생성할 수 있다면 어떻게 될까요?

이 시나리오를 파악하고 제외하기 위해 if 조건에 절을 하나 더 포함하도록 업데이트했습니다.

"" + "+N"
"" + "*N"
"" + "N"

이렇게 하면 모든 숫자가 처리되고 결과 금액이 테스트 숫자와 동일한 경우에만 방정식이 계산됩니다.

큰 질문:

  • 이렇게 하면 제가 받는 답변이 바뀌나요?

다시 실행을 누르세요...

...

흠, 여전히 같은 대답인 것 같네요.

아 잠깐만요, 끝 부분에 다른 두 자리 숫자가 있어요!

새 답변은 이전보다 정확히 80이 적습니다.

예상량이 80인 방정식이 있나요?

그렇습니다!

"N"

숫자를 다 쓰지 않고 80을 만드는 방법이 있나요?

그렇습니다!

"N" + "+N"
"N" + "*N"
"N" + "N"

이것이 제가 제외해야 했던 유일한 극단적인 경우였나요?

새 답변을 제출하는 중...

맞습니다!!!

우후!!!

해냈어요!!!

그거요. 였다. 지친다. 그리고 신난다. 그리고 정말로 달리세요. 그리고 도전적입니다.

내가 이 퍼즐을 좋아하는 모든 이유

다음으로!

위 내용은 교량 수리의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!

성명:
본 글의 내용은 네티즌들의 자발적인 기여로 작성되었으며, 저작권은 원저작자에게 있습니다. 본 사이트는 이에 상응하는 법적 책임을 지지 않습니다. 표절이나 침해가 의심되는 콘텐츠를 발견한 경우 admin@php.cn으로 문의하세요.