사이냅 소프트 입사문제 1번의 간략해

정확한 해는 될 수 없다. 왜냐하면 어떤 형태의 도형이 되었는지 까지는 체크하지않고, 단순히 이것이 몇 점 도형이 되는지 체크하는 것이기때문..
그리고 점의 순서역시 순서대로 찍어야만 되도록 프로그래밍 되었기때문에 예제 입력에 정확히 일치하지 않는 결과만 나온다.

어쨌거나 시작~

해당하는 그리드의 n번째 시작줄은 A(n) = A(n-1) + n 이 된다. 이때 A(0) = 1 이 된다.
또한 같은 밑변인 경우 같은 n번째 항의 값이어야하고,  같은 빗변인 경우 시작줄 첫번호나 끝번호에서 떨어진 길이가 동일해야한다.
따라서 모든 수가 빗변, 밑변을 이룰 수 있어야하고 그리드 안에 이동가능한 모든 수는 단 한번만 나와야 실제로 도형이 나온다.
머.. 빗변과 밑변의 종류와 수를 조합해서 도형을 찾아내는 방법이 있긴한데.. 거기까지는 패쓰.. 아침에 부랴부랴 만들었더니 엉망이네.. =.=

;; n번째 항 찾기..
(defun get-nth (n)
  (cond ((= n 0) 1)
		(t 
		 (+ n (get-nth (- n 1))))))

;; x값이 포함될 n번째 항을 찾기
(defun find-least-n (x)
  (labels ((find-iter (i)
			 (cond ((> (get-nth i) x) i)
				   (t
					(find-iter (+ i 1))))))
	(find-iter 0)))

;; x 값의 수평 위치를 알아오기
(defun find-pos  (x)
  (let ((n (find-least-n x)))
	(- x (get-nth (- n 1) ))))
  
;; x 값의 뒤쪽에서의 위치를 알아오기
(defun find-rev-pos (x)
  (let ((n (find-least-n x)))
	(- x (- (get-nth n) 1))))

;; 같은 Bottom Line 인지 검사
(defun same-bottom (a b)
  (= (find-least-n a) (find-least-n b)))

;; 같은 빗변인지 검사
(defun same-slope (a b)
  (or (slash-slope a b) (backslash-slope a b)))

;; / 빗변인가?
(defun slash-slope (a b)
  ( = (find-pos a) (find-pos b)))

;; \ 빗변인가?
(defun backslash-slope (a b)
  (= (find-rev-pos a) (find-rev-pos b)))

;;밑변의 모든 점
(defun bottom-point (a b)
  (cond ((= a b) (list a))
		(t
		 (cons a (bottom-point (+ a 1) b)))))
;;밑변의 모든 점
(defun bottom-point-rev (a b)
  (reverse (bottom-point b a)))

;; / 모양위의 모든 점
(defun slash-point (a b)
  (cond ((= a b) (list a))
		(t 
		 (cons a (slash-point (+ (find-least-n a) a) b)))))

;; / 모양이지만 a > b 인 경우
(defun slash-point-rev ( a b)
  (reverse (slash-point b a)))

;; \ 모양위의 모든 점
(defun backslash-point (a b)
  (cond ((= a b) (list a))
		(t 
		 (cons a (backslash-point (+ (find-least-n a) a 1) b)))))

;; \ 모양이지만 a > b 인 경우
(defun backslash-point-rev (a b)
  (reverse (backslash-point b a)))


;; 점의 집합을 순환 집합으로 만들기
(defun make-circular (lst)
  (append lst  (list (car lst))))

;; 순환 집합을 각각의 시작점과 끝점의 집합으로 만들기
(defun make-point-set (lst)
  (cond ((> 2 (length lst)) '())
		(t
		 (cons (cons (car lst) (cadr lst))
			   (make-point-set (cdr lst))))))

(defun point-on-line (a b)
  (or (same-bottom a b)
	   (same-slope a b)))

;; 각 점이 모두 라인이 되는지 있는지 검사
(defun all-point-on-line (lst)
  (cond ((null lst) T)
		(t 
		 (and (point-on-line (caar lst) (cdar lst))
			  (all-point-on-line (cdr lst))))))

;; 두 점이 이루는 방식에 따라 중간 수를 가져오는 함수
(defun get-path-between (a b)
  (cond ((= a b) '())
		((> a b)
		 (cond ((same-bottom a b) (bottom-point-rev a b))
			   ((slash-slope a b) (slash-point-rev a b))
			   ((backslash-slope a b) (backslash-point-rev a b))))
		(t
		 (cond ((same-bottom a b) (bottom-point a b))
			   ((slash-slope a b) (slash-point a b))
			   ((backslash-slope a b) (backslash-point a b))))))

(defun tuck (lst)
  (reverse (cdr (reverse lst))))

;; 각 선이 이루는 모든 수를 가져온다.
(defun get-path (lst)
  (cond ((null lst) '())
		(t
		 (append
		  (tuck (get-path-between (caar lst) (cdar lst)))
		  (get-path (cdr lst))))))

(defun get-path-lst (lst)
  (cond ((null lst) '())
		(t
		 (cons
		  (tuck (get-path-between (caar lst) (cdar lst)))
		  (get-path-lst (cdr lst))))))
;; 해당하는 점의 집합이 모두 별개의 수로 되어 있을 것
(defun differ? (n lst)
  (cond ((null lst) t)
		(t
		 (and (not (= n (car lst)))
			  (differ? n (cdr lst))))))

(defun all-differ? (lst)
  (cond ((null lst) t)
		((atom lst) t)
		(t
		 (and (differ? (car lst) (cdr lst))
			  (all-differ? (cdr lst))))))

;; 검사 함수 : 해당하는 점들이 서로 겹치지 않는 도형을 이룰 수 있는지..
(defun avail? (lst)
  (let ((pset (make-point-set (make-circular lst))))
	(and
	 (all-point-on-line pset)
	 (all-differ? (get-path pset)))))

;; 변의 길이가 동일한가?
(defun same-length? (lst)
  (let ((pset (get-path-lst (make-point-set (make-circular lst)))))
	(let ((lenlst (mapcar #'length pset)))
	  (not (differ? (car lenlst) (cdr lenlst))))))

;; 최종 검사 함수 : 해당하는 점들이 도형이며, 변의 길이가 동일한가?
(defun check-shape? (lst)
  (if (and (avail? lst)
		   (same-length? lst))
	  (print-shape lst)
	  (format t "~A is not acceptable shape." lst)))

(defun print-shape (lst)
  (format t "~A is accepable ~A pointed shape." lst (length lst)))