Hatena::Groupcadr

わだばLisperになる このページをアンテナに追加 RSSフィード

2004 | 12 |
2005 | 01 | 02 | 07 | 10 | 11 |
2006 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2007 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2008 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2009 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2010 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2011 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 11 |

2007-05-14

L-99 (80) (2)

| 21:50 | L-99 (80) (2) - わだばLisperになる を含むブックマーク はてなブックマーク - L-99 (80) (2) - わだばLisperになる

L-99 P80に挑戦 - L-99:Ninety-Nine Lisp Problems

P80の続き。だいぶ重複も多い気がするし、まとめるべ

きなんだろうけども、まとめる気力がないので、とりあ

えず、このままで(ノ´∀`*)

今回は、Common Lisp版の有向グラフ版と、名札付き有

向グラフ版。

Lisp Machine LispとScheme版は、また後で。

解答
;; Common Lisp
(load ./flatten)

;; -----------------------------------------------------------------------------
;; DIRECTED
;; graph-term <=> arc-clause
(defun graph-term->arc-clause/directed (expr)
  (cadr expr))

(defun arc-clause->graph-term/directed (expr)
  `(,(sort
      (delete-duplicates
       (reduce #'xappend
               expr :initial-value '() ))
      #'(lambda(a b) (string< (string a) (string b))))
    ,expr))

(defun xappend (lst1 lst2)
  (append lst2 lst1))

;; -----------------------------------------------------------------------------
;; adjacency-list <=> graph-term
(defun adjacency-list->graph-term/directed (expr)
  `(,(mapcar #'car expr)
    ,(reduce #'(lambda (retlst item)
                 (if item
                     `(,@retlst ,@(mapcar #'(lambda (i) `(,(car item) ,i)) 
                                          (cadr item)))
                   retlst))
             expr :initial-value '() )))

(defun graph-term->adjacency-list/directed (expr)
  (mapcar #'(lambda (item) `(,item ,(get-direction item (cadr expr))))
          (car expr)))

(defun get-direction (from dist-lst)
  (reduce #'(lambda (retlst item)
              (if (eql from (car item))
                  `(,@retlst ,(cadr item))
                retlst))
          dist-lst :initial-value '() ))

;; -----------------------------------------------------------------------------
;; directed-graph-term <=> human-friendly
(defun graph-term->human-friendly/directed (expr)
  (sort `(,@(mapcar #'(lambda (item) 
                        (format nil "~A>~A" (car item) (cadr item)))
		    (cadr expr))
          ,@(mapcar #'string
                    (set-difference (car expr) (flatten (cadr expr)))))
	#'string<))

(defun human-friendly->graph-term/directed (expr)
  (flet ((splitter (strlst)
           (mapcar #'(lambda (item)
                       (let ((pos (position #\> (coerce item 'list))))
                         (if pos
                             `(,(subseq item 0 pos)
                               ,(subseq item (1+ pos)))
                           item)))
                   strlst)))
    (let ((item-list (mapcar #'(lambda (item)
                                 (if (listp item)
                                     (mapcar #'read-from-string item)
                                   (read-from-string item)))
                             (splitter expr))))
      `(,(delete-duplicates (flatten item-list)) 
        ,(delete-if-not #'listp item-list)))))

;; -----------------------------------------------------------------------------
;; LABELLED
;; graph-term <=>arc-clause
(defun graph-term->arc-clause/labelled (expr)
  (cadr expr))

(defun arc-clause->graph-term/labelled (expr)
  `(,(sort 
      (delete-duplicates
       (reduce #'(lambda (ret item) `(,@(butlast item) ,@ret))
               expr :initial-value '() ))
      #'(lambda(a b) (string< (string a) (string b))))
    ,expr))

;; -----------------------------------------------------------------------------
;; adjacency-list <=> graph-term/labelled
(defun adjacency-list->graph-term/labelled (expr)
  `(,(mapcar #'car expr)
    ,(reduce #'(lambda (retlst item)
                 `(,@retlst ,@(reduce #'(lambda (ret num)
                                          (if num
                                              `(,@ret (,(car item) ,@num))
                                            ret))
                                      (cadr item) :initial-value '() )))
             expr :initial-value '() )))

(defun graph-term->adjacency-list/labelled (expr)
  (mapcar #'(lambda (item)
              `(,item ,(get-direction/labelled item (cadr expr))))
          (car expr)))
                       
(defun get-direction/labelled (from dist-lst)
  (reduce #'(lambda (retlst item)
              (if (eql from (car item))
                  `(,@retlst (,(cadr item) ,(caddr item)))
                retlst))
          dist-lst :initial-value '() ))

;; -----------------------------------------------------------------------------
;; graph-term <=> human-friendly
(defun graph-term->human-friendly/labelled (expr)
  (sort `(,@(mapcar #'(lambda (item) (format nil "~{~A>~A/~A~}" item))
		    (cadr expr))
          ,@(mapcar #'string
                    (set-difference (car expr) (flatten (cadr expr)))))
	#'string<))

(defun human-friendly->graph-term/labelled (expr)
  (labels ((splitter (strlst)
             (mapcar #'(lambda (item)
                         (let ((>pos (position #\> (coerce item 'list)))
                               (/pos (position #\/ (coerce item 'list))))
                           (if >pos 
                               `(,(subseq item 0 >pos)
                                 ,(subseq item (1+ >pos) /pos)
                                 ,(subseq item (1+ /pos)))
                             item)))
                     strlst)))
    (let ((item-list (mapcar #'(lambda (item)
                                 (if (listp item)
                                     (mapcar #'read-from-string item)
                                   (read-from-string item)))
                             (splitter expr))))
      `(,(delete-duplicates 
          (reduce #'(lambda (retlst item)
                      `(,@retlst ,@(if (listp item) (butlast item) `(,item))))
                  item-list :initial-value '() )) 
        ,(delete-if-not #'listp item-list)))))