While I was playing around with a particular problem this week, a
small discovery led me to a major design fix for the solution I had
developed. Here I will tell you this story because it is not only
about coding, but about inspiration, and its many sources.
The problem was the following:
You will have to trace the steps of a robot to determine its final
commands in the following language:
L - turn 90 degrees left
R - turn 90 degrees right
M - move forward
T - transport to a given location
The commands will be given as such:
10 10 # board size
2 5 N # initial location and the direction the robot is facing
LLRRMMMRLRMMM # series of moves
T 1 3 # transport to position x=1 y=3
LLRRMMRMMRM # another series of moves
Summing up, it is a small textual logo.
My approach to the problem was basically to draft the structures I
would need, in a semi object oriented approach (old-habits). Much like
the following(the first version is in portuguese):
;; tabuleiro é uma estrutura contendo um par de inteiros (define-struct tabuleiro (x y) #:transparent) (define-struct robo (x y direção) #:transparent) ;; constrói-tabuleiro : string -> tabuleiro (define (constrói-tabuleiro dados) (let ([dados-do-tabuleiro (string-tokenize dados)]) (make-tabuleiro (string->number (first dados-do-tabuleiro)) (string->number (second dados-do-tabuleiro))))) ;; constrói-tabuleiro : string -> tabuleiro (define (constrói-robo dados) (let ([dados-do-robo (string-tokenize dados)]) (make-robo (string->number (first dados-do-robo)) (string->number (second dados-do-robo)) (string-ref (third dados-do-robo) 0))))
All was going pretty smooth. I had defined some structures, later
the functions that mapped to the commands in the mini logo:
(define DIREÇÕES-POSSIVEIS (list '(#\N (#\W #\E)) '(#\W (#\S #\N)) '(#\S (#\E #\W)) '(#\E (#\N #\S)))) (define RESULTADO-DO-PASSO-A-FRENTE (list (list #\N (list (λ (n) n) add1)) (list #\W (list sub1 (λ (n) n))) (list #\S (list (λ (n) n) sub1)) (list #\E (list add1 (λ (n) n))))) ;; muda-direção : robo char -> robo (define (muda-direção o-robo virar-para) (let ([possíveis-direções (second (findf (λ (uma-possibilidade) (equal? (first uma-possibilidade) (robo-direção o-robo))) DIREÇÕES-POSSIVEIS))]) (struct-copy robo o-robo (direção (if (equal? virar-para #\L) (first possíveis-direções) (second possíveis-direções)))))) ;; muda-posição : robo number number -> robo (define (muda-posição o-robo x y) (struct-copy robo o-robo (x x) (y y))) ;; passo-a-frente : robo -> robo (define (passo-a-frente o-robo) (let ([possíveis-funções (second (findf (λ (um-resultado-de-uma-posição) (equal? (first um-resultado-de-uma-posição) (robo-direção o-robo))) RESULTADO-DO-PASSO-A-FRENTE))]) (muda-posição o-robo ((first possíveis-funções) (robo-x o-robo)) ((second possíveis-funções) (robo-y o-robo)))))
That also went ok. But the problem was parsing the language. I did
my own ad-hoc parser, but as I was building it, the felling of
suspicion was growing and my faith in my approach diminishing. Take
a look at the final product:
;; ler-movimentos-do-robo : input-port robo tabuleiro -> robo ;; le e modifica a posição do robo a partir de uma lista de movimentos (define (ler-movimentos-do-robo arquivo (o-robo #f) (o-tabuleiro #f)) (let* ([linha-de-comandos (read-line arquivo 'any)]) (if (eof-object? linha-de-comandos) o-robo (let ([elementos-da-linha (string-tokenize linha-de-comandos)]) (case (length elementos-da-linha) [(3) (if (equal? (first elementos-da-linha) "T") (ler-movimentos-do-robo arquivo (muda-posição o-robo (string->number (second elementos-da-linha)) (string->number (third elementos-da-linha))) o-tabuleiro) (ler-movimentos-do-robo arquivo (constrói-robo linha-de-comandos) o-tabuleiro))] [(2) (ler-movimentos-do-robo arquivo o-robo (constrói-tabuleiro linha-de-comandos))] [else (ler-movimentos-do-robo arquivo ; cria um novo robo pra cada comando da linha (string-fold (lambda (comando velho-robo) (if (equal? comando #\M) (passo-a-frente velho-robo) (muda-direção velho-robo comando))) o-robo linha-de-comandos) o-tabuleiro)])))))
Big, butt-ugly, hard to read and maintain. Something was wrong
and I wasn't really sure what. Then serendipity struck me in the
form of
this message. Lex
and YACC, of course! It took me a couple of hours to learn Racket's
syntax for it, but I ended up with a lexer and a parser for the
mini logo, in a version that was much more friendly and elegant.
(define-tokens value-tokens (NUMBER
DIRECTION
FUNCTION
COMMANDS))
(define-empty-tokens op-tokens (EOF NEWLINE))
(define-lex-abbrevs
(teleport #\T)
(turn-left #\L)
(turn-right #\R)
(move-forward #\M)
(directions (:or #\N
#\S
#\E
#\W))
(digit (:/ #\0 #\9)))
(define mech-lexer
(lexer
[(eof) 'EOF]
[#\newline (token-NEWLINE)]
;; recursively call the lexer on the remaining input after a tab or space.
;; Returning the result of that operation.
;; This effectively skips all whitespace.
[#\space (mech-lexer input-port)]
[directions (token-DIRECTION (string-ref lexeme 0))]
[(:+ (:or turn-right turn-left move-forward))
(token-COMMANDS
(map (λ (command)
(get-consequences COMMAND-LOOKUP-TABLE command))
(string->list lexeme)))]
[teleport (token-FUNCTION (string-ref lexeme 0))]
[(:+ digit) (token-NUMBER (string->number lexeme))]))
;; mech-parser : (X -> token) board mech -> mech
(define (mech-parser gen
(board #f)
(mech #f))
((parser
(start start)
(end EOF NEWLINE)
(tokens value-tokens op-tokens)
(error (λ (tok-ok? tok-name tok-value)
(error 'lexer
(format
(if (false? tok-ok?)
"the token ~a with value ~a was invalid."
"unknow error with token ~a with value ~a")
tok-name
tok-value))))
(grammar
(start [() mech] ;; end our parsing, return the mech structure
[(exp) $1])
(exp [(NUMBER NUMBER)
(mech-parser gen
(make-board $1 $2)
mech)]
[(NUMBER NUMBER DIRECTION)
(mech-parser gen
board
(make-mech $1 $2 $3))]
[(FUNCTION NUMBER NUMBER)
(with-handlers ((string? (λ (message)
(display message)
(mech-parser gen
board
mech))))
(mech-parser gen
board
(jump board mech $2 $3)))]
[(COMMANDS)
(mech-parser gen
board
(foldl
(λ (command old-mech)
(with-handlers ((string? (λ (message)
(display message)
old-mech)))
(command board old-mech)))
mech $1))])))
gen))
(define (process-mech ip)
(mech-parser (λ () (mech-lexer ip))))
If you want to compare the full versions, take a look at the
github repository. The
version with the cleaner Lexer/Parser are called 'mech' instead of
'robo'.
Until next time!
Nenhum comentário:
Postar um comentário