파슬리로 AoC#2 난제를 해결하다
11541 단어 ruby
tl;dr(전체 배경 이야기를 읽고 싶지 않은 사람들): 1000줄의 이런 문장을 받을 수 있습니다.
1-3 a: abcde
.이것은 abcde
문자열은 1
부터 3
까지의 자모a
를 포함해야 한다는 뜻이다.너는 세어 보아야 한다. 이것은 정말이다.대부분의 사람들에게 직관적인 해결 방안은 줄마다 정규 표현식(심지어 문자열 분할)을 사용하고 일치/분할 결과에 대해 강제 변환과 검사를 하고 결과에 따라 계수기를 추가하거나 증가하지 않는 것이다.참고로 이것이 바로 내가 첫 번째 교체에서 한 일이다.그러나 나중에 나는 입력을 보고 우리가 실제로 모든 파일을 어떤 외래 언어로 작성된 프로그램으로 볼 수 있다는 것을 깨달았다.따라서, 우리는 이 프로그램을 실행하고 결과를 얻기 위해 해상도와 해석기를 작성하는 도구를 사용할 수 있다.
파슬리로 해결해 주세요.
나는 과거에 그것에 대해 경험이 있기 때문에 Parslet 나의 대체 해결 방안을 작성하는 것을 선택했다.또한 나는 하나의 루비 파일에서 모든 내용을 작성할 수 있기 때문이다. 많은 다른 도구에서, 너는 하나의 단독 파일에서 문법을 정의한 다음에 루비 코드로 컴파일해서 진정한 해석기가 될 수 있다.보통 속도가 더 빠르지만 진입 문턱도 더 높다.
나는 파슬리를 자세히 설명하지 않을 것이다.다른 사람들, 특히 그 작가들은 이미 잘 했으니 적어도 먼저'Getting started'을 읽어야 한다.내가 해야 할 일은 나의 해결 방안과 평론을 제시하는 것이다.
파슬리를 사용하는 데는 두 가지 절차가 포함된다.먼저 입력을 산열과 유사한 내부 표현으로 해석합니다.그리고 우리는 전환 절차를 진행한다.많은 강좌에서 전환의 결과는 실제 해석기가 조작하는AST(추상적 문법 트리)이지만 우리는 이 절차를 생략하고 논리를 전환류에 직접 쓸 수 있다.
구문 분석기/구문
우리가 해석해야 할 프로그램은 많은 줄로 구성되어 있다.각 선에는 다음과 같은 구조가 있습니다.
number -> dash -> number -> space -> letter -> colon -> space -> string -> (optional) new line
(파일의 마지막 줄에 새 줄이 없기 때문에 새 줄은 선택할 수 있습니다.)이것이 바로 파슬리 DSL의 표현 방식입니다.
class Parser < Parslet::Parser
rule(:space) { match('\s') }
rule(:newl?) { match('\n').maybe }
rule(:dash) { str('-') }
rule(:colon) { str(':') }
rule(:num) { match('[0-9]').repeat(1).as(:num) }
rule(:letter) { match('[a-z]').as(:letter) }
rule(:string) { letter.repeat(1) }
rule(:line) { num.as(:min) >> dash >> num.as(:max) >>
space >> letter.as(:target) >>
colon >> space >> string.as(:string) >> newl? }
rule(:lines) { line.repeat(1).as(:lines) }
root :lines
end
보시다시피, 이것은 위에서 작성한 위조 코드와 매우 비슷합니다.이것이 바로 파슬리와 페그 문법의 장점이다. 파슬리가 어떻게 작동하는지 몰라도 머리를 쥐어짜기 쉽다.글의 시작 부분에서 예제에서 파서를 실행하여 인쇄한 경우 결과는 다음과 같습니다.{:lines=>
[{:min=>{:num=>"1"@0},
:max=>{:num=>"3"@2},
:target=>{:letter=>"a"@4},
:string=>
[{:letter=>"a"@7},
{:letter=>"b"@8},
{:letter=>"c"@9},
{:letter=>"d"@10},
{:letter=>"e"@11}]}]}
이것은 내가 너에게 말한 유사한 산열의 표시이다.이제 뭘 좀 할 때가 됐어.바꾸다
전환 절차의 역할은 산열을 가져와 더 좋은 내용으로 바꾸는 것이다.우리의 예에서, 우리는 전력을 다해 그것을 하나의 숫자로 바꿀 것이다. 진실을 말하는 줄 수 (그들이 지정한 조건을 만족시키는 것).
이것은 이렇게 하는 과정이다.
class Transform < Parslet::Transform
rule(:num => simple(:int)) { Integer(int) }
rule(:letter => simple(:char)) { char.to_s }
rule(
:min => simple(:min),
:max => simple(:max),
:target => simple(:target),
:string => sequence(:letters)
) { frequency = letters.tally.fetch(target, 0); frequency >= min && frequency <= max ? 1 : 0 }
rule(:lines => sequence(:lines)) { lines.sum }
end
이것은 컴파일러 해상도처럼 간단하지는 않지만, 기본 규칙은 여전히 간단하다.우리는 해상도 출력의 모든 산열과 같은 부분에 특정한 패턴이 일치하는 규칙을 작성한 다음에 변환을 실행하는 블록을 추가합니다.예를 들어 첫 번째rule(:num => simple(:int)) { Integer(int) }
와 {:num=>"1"@0}
가 동시에 일치한다.이것은 값{:num=>"3"@2}
을 간단한 값으로 간주하고 정수에 강제 변환을 적용한다.여기에는 당연히 하나의 규칙이 매우 두드러진다.이것은 직선과 일치하는 규칙이다.그러나 이것은 이상하지 않다. 왜냐하면 한 줄의 문법도 가장 복잡하기 때문이다.이 규칙은 각 행을 숫자 1(올바른 행의 경우) 또는 0(잘못된 행의 경우)으로 줄입니다.마지막으로
num
규칙은 모든 줄을 더하기만 하면 된다.마무리
이렇게 말해서 미안해요.간단한 해석기와transform-o 해석기를 작성했습니다. 이제 다음 도구로 프로그램을 실행할 수 있습니다.
parsed = Parser.new.parse(File.read('input'))
puts Transform.new.apply(parsed)
결과는 우리가 수수께끼를 풀 수 있는 답이 될 것이다.전체 파일is here.내가 왜 이러는 거야?내장된 정규 표현식의 해결 방안을 사용하면 더욱 익숙하고 빠를 뿐만 아니라, 더욱 빨리 그것을 작성할 수 있다.그럼요.그러나 나는 이런 문제를 해결하는 방식이 새로운 것을 배우는 좋은 방법이라는 것을 발견했다.문법은 상대적으로 간단하기 때문에 귀속 규칙이나 PEG 문법에서 의외로 어려운 일에 빠지지 않는다.그리고 아마도 가장 중요한 것은 다른 사람들처럼 하는 것보다 훨씬 재미있을 것이다.
Reference
이 문제에 관하여(파슬리로 AoC#2 난제를 해결하다), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://dev.to/katafrakt/solving-aoc-2-puzzle-with-parslet-2cbi텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)