Поиск всех возможных значений с помощью if в схеме

Question

Я пытаюсь делать домашнее задание, но у меня проблемы с этим .. Есть несколько фактов об автобусах и путешественниках:

Я пытаюсь написать код, который дает альтернативные пути (это может быть прямой путь или максимум одна передача) к пункту назначения voyager. Например:

>(findways 'john)
(list (list 'b002))
>(findways 'merry)
(list (list 'b005) (list 'b001 'b002))
>(findways 'lerry)
(list (list 'b006) (list 'b004 'b003) (list 'b007 'b008))

Итак ... сначала найдите способ без необходимости перевода, после этого найдите способ или способы, требующие только одного перевода ...

после этого мне нужно найти кратчайший путь с другой функцией:

>(findshort 'jhon)
(list 'b002)  ; this is because the only way is
>(findshort 'merry) 
(list 'b005)  ; this because b005 travel time is 8, b001+b002 is 15
>(findshort 'lerry)
(list 'b004 'b003) ; this is because b006 is 18, b007+b008 is 16 but b004+b003 is 13

Большое спасибо

p.s .: я не могу использовать ! и let

Answer 1

Это не полное решение, но оно должно помочь вам начать работу. Попробуйте разбить проблему на более мелкие и простые функции, например:

;; (define buses ...)
;; (define voyagers ....)

(define findways
   (lambda (voyager)
     (find_bus_routes (lookup_voyager_route voyager voyagers) buses)))

(define lookup_voyager_route
  (lambda (voyager voyager_lst)
    (if (null? voyager_lst)
        '()
        (if (equal? voyager (caar voyager_lst))
            (cdar voyager_lst)
            (lookup_voyager_route voyager (cdr voyager_lst))))))

(define find_bus_routes
  (lambda (sd_lst bus_routes)
    (if (or (null? sd_lst) (null? bus_routes))
        '()
        (if (equal? (car sd_lst) (cadar bus_routes))
            ;; perfect match
            (if (equal? (cadr sd_lst) (caddar bus_routes)) 
                (cons (caar bus_routes) ;; keep bus number
                      (find_bus_routes sd_lst (cdr bus_routes)))
                ;; partial match could be improved
                (cons (list (caar bus_routes) 
                            (match_route (caddar bus_routes)
                                         (cadr sd_lst) buses))
                      (find_bus_routes sd_lst (cdr bus_routes))))
            (find_bus_routes sd_lst (cdr bus_routes))))))

(define match_route
   (lambda (start dest routes)
     (if (null? routes)
         routes
         (if (and (equal? start (cadar routes))
                  (equal? dest (caddar routes)))
             (caar routes)
             (match_route start dest (cdr routes))))))

Как только у вас есть список возможных маршрутов, легко определить кратчайшее расстояние.