Ракетка - Найти списки, которые имеют одинаковый элемент в 2D-списке - PullRequest
Новая
       6

Ракетка - Найти списки, которые имеют одинаковый элемент в 2D-списке

0 голосов
/ 29 октября 2019

Я новичок в ракетке, и мне нужно написать функцию (код аэропортов той же страны), которая использует список аэропортов (аэропортов) и трехбуквенный код, который представляет аэропорт. Функция выдает список всех кодов аэропортов, имеющих ту же страну, что и данный аэропорт, отсортированных по возрастанию в алфавитном порядке.

Например: 

(define alist (list (list "YYZ" (list "Toronto" "Canada"))
                    (list "YWG" (list "Winnipeg" "Canada"))
                    (list "BGO" (list "Bergen" "Norway"))
                    (list "TRF" (list "Sandefjord" "Norway"))
                    (list "YUL" (list "Montreal" "Canada"))
                    (list "LHR" (list "London" "England"))
                    (list "YVR" (list "Vancouver" "Canada"))))

Тогда 

(same-country alist "YUL") => (list "YUL" "YVR" "YWG" "YYZ")

Может кто-нибудь показать мне, как решить эту проблему / дать мне шаблон? Мне не разрешено использовать карту, лямбду или любые другие дополнительные встроенные функции, только список

1 Ответ

0 голосов
/ 29 октября 2019

Сначала извлеките страну, связанную с входной строкой: 

(define (get-country l s)
  (cond [(empty? (rest l)) (second (second (first l)))]
        [else (if (equal? s (first (first l)))
                  (second (second (first l)))
                  (get-country (rest l) s))]))

Затем извлеките все строки, с которыми связана эта страна: 

(define (get-countries l s)
  (cond [(empty? l) '()]
        [else (if (equal? s (second (second (first l))))
                  (cons (first (first l)) (get-countries (rest l) s))
                  (get-countries (rest l) s))]))

Затем сложите их вместе: 

(define (same-country l s)
  (get-countries l (get-country l s)))

Когда мы оцениваем, мы получаем результат, отличный от (list "YUL" "YVR" "YWG" "YYZ"): 

> (same-country alist "YUL")
(list "YYZ" "YWG" "YUL" "YVR")

Поэтому мы проверяем, является ли результат перестановкой нужного списка. Сначала мы делаем is-permutation: 

(define (is-permutation l1 l2)
  (and (not (and (cons? l1) (empty? l2)))
       (not (and (empty? l1) (cons? l2)))
       (or (and (empty? l1) (empty? l2))
           (and (is-member (first l1) l2)
                (is-permutation (rest l1)
                                (remove-one (first l1) l2))))))

(define (is-member e l)
  (and (not (empty? l))
       (or (equal? (first l) e)
           (is-member e (rest l)))))

(define (remove-one e nel)
  (cond [(empty? (rest nel)) '()]
        [else (if (equal? (first nel) e)
                  (rest nel)
                  (cons (first nel) (remove-one e (rest nel))))]))

Затем мы можем проверить: 

> (is-permutation (same-country alist "YUL")
                  (list "YUL" "YVR" "YWG" "YYZ"))
#true
...