사이냅소프트 막대자르기 문제

얼핏 본바로는 소인수분해를 해서 그 리스트를 나누어진 조각중 가장 큰 것보다 큰 것중 가장 작은것을 가져오면 될듯하다

;; 길이가 같은 여러 개의 막대를 잘라 다양한 길이로 만들었다.
;; 원래대로 막대를 돌려놓을 때 가능한 길이중 가장 작은 값을 찾아라..


;; 해당하는 문제는 소인수 분해를 해서, 그 중에 잘라놓은 막대보다 큰 것중 가장 작은 수를 구하면 된다.
;; 소인수 분해를 하자.. 소인수 분해의 수는 소수만 가능.. 1은 제외하고 2부터..

(defun sum (lst)
  (cond ((null lst) 0)
		(t (+ (car lst)
			  (sum (cdr lst))))))

(defun max-lst (lst)
  (cond ((= (length lst) 1) (car lst))
		((null lst) '())
		(t (max (car lst)
				(max-lst (cdr lst))))))

(defun min-lst (lst)
  (cond ((= (length lst) 1) (car lst))
		((null lst) '())
		(t (min (car lst)
				(max-lst (cdr lst))))))

(defun digest-num (n)
  (labels ((iter (s n)
			 (cond ((>= s n) '())
				   (t
					(cond ((= (mod n s) 0) 
						   (cons s (iter (+ s 1) n)))
						  (t
						   (iter (+ s 1) n)))))))
	(iter 2 n)))

(defun bar-check (lst)
  (let ((wholebar (sum lst))
		(max-ele (max-lst lst)))
	(let ((dnum (digest-num wholebar)))
	  (let ((least-max  (find-at-least dnum max-ele)))
		(cond
		  ((null least-max) -1)
		  ((= wholebar least-max) -1)
		  (t
		   least-max))))))

;; 리스트 내역을 필터링하기
(defun filter (lst proc)
  (cond ((null lst) '())
		(t
		 (if (funcall proc (car lst))
			 (cons (car lst) (filter (cdr lst) proc))
			 (filter (cdr lst) proc)))))
			 
;; 리스트중 v보다 큰 요소중 가장 작은 것을 구하기..
(defun find-at-least (lst v)
  (min-lst (filter lst
				   #'(lambda (c)
					   (> c v)))))

사이냅소프트 입사문제 2진수 계산기(곱셈)

엄청 지저분해졌지만 그런대로. 답 나옴..
2진수의 곱을 이쁘게 출력하는 함수..

;; 이쁘게 찍기
(defun pretty-print-mul (a b)
  (let ((ans (binary-mul a b))
		(lst (reverse (binary-bit-calculate a b))))
	(let ((digits (length ans)))
	  (format t "~A~%" (fill-spacer a digits))
	  (format t "~A~%" (fill-spacer b digits))
	  (format t "~A~%" (fill-spacer (dashes (max (length a) (length b))) digits))
	  (dolist (ele lst)
		(format t "~A~%" (fill-spacer ele digits)))
	  (format t "~A~%" (fill-spacer (dashes (length ans)) digits))
	  (format t "~A~%" (fill-spacer ans digits)))))

(defun dashes (n)
  (cond ((= n 0) "")
		(t (string-concat "-" 
		                  (dashes (- n 1))))))

(defun binary-mul (a b)
  (trim-left-zero (sumup (binary-bit-calculate a b))))


;; 2진수 문자열을 풀어서 각 자리수별로 연산 결과를 만들기...
;; 자리수가 증가할 수록 뒷부분에 문자열도 따라서 증가해야한다.
(defun binary-bit-calculate (a b)
  (cond ((= (length b) 0) '())
		(t
		 (cons 
		  (string-concat (binary-and a (char b 0)) (spacer (- (length b) 1)))
		  (binary-bit-calculate a (subseq b 1 (length b)))))))

(defun sumup (lst)
  (cond ((null lst) "")
		(t (binary-bit-add (car lst)
						   (sumup (cdr lst))))))

;; 앞쪽의 0 지우기..
(defun trim-left-zero (str)
  (cond ((not (char= (char str 0) #\0)) str)
		(t
		 (trim-left-zero (subseq str 1 (length str))))))
;; 2진수 문자열의 합
(defun binary-bit-add (a b)
  (let ((la (length a))
		(lb (length b)))
	(let ((ll (max la lb)))
	  (let ((ra (fill-spacer a ll))
			(rb (fill-spacer b ll)))
		(binary-add ra rb)))))

(defun fill-spacer (s n)
  (cond ((= (length s) n) s)
		(t
		 (string-concat (string " ")
						(fill-spacer s (- n 1))))))

;; 2진수의 합 계산하기..
; 각 항의 값을 더하고 캐리가 발생하면 다음 자리로 올린다.
; Reverse 가 된 것이라고 가정

(defun rev-binary-add (a b)
  (labels ((adds (a b)
			 (cond ((and (char= a #\1) (or (char= b #\0) (char= b #\Space))) "1")
				   ((and (or (char= a #\0) (char= a #\Space)) (char= b #\1)) "1")
				   (t "0")))
		   (cadds (a b)
			 (cond ((and (char= b #\1) (char= a #\1)) "1")
				   (t "0")))
		   (binary-iter (c a b)
			 (cond ((= (length a) 0) c)
				   (t
					(let ((fa (char a 0))
						  (fb (char b 0))
						  (ans (string "0"))
						  (carry (string "0")))
					  (progn
						(setf ans (adds fa fb))
						(setf carry (cadds fa fb))
						(cond ((string= c "1")
							   (if (string= ans "1")
								   (progn
									 (setf ans (string "0"))
									 (setf carry (string "1")))
								   (setf ans (string "1")))))
						(string-concat ans 
									   (binary-iter carry
													(subseq a 1 (length a))
													(subseq b 1 (length b))))))))))
  (binary-iter (string "0")
			   a
			   b)))
			
(defun binary-add (a b)
  (reverse (rev-binary-add (reverse a)
						   (reverse b))))

(defun stringloop (a)
  (cond ((= (length a) 0) (string ""))
		(t
		 (stringloop 
		  (subseq a 1 (length a))))))
						 

;; 어떤 이진수 A와 0, 1의 곱 결과를 돌려주기.
(defun binary-and (a b)
  (cond ((char= b #\0)
		 (zeros (length a)))
		(t a)))

;; 특정 길이만큼 0로 찬 결과를 돌려주기..
(defun zeros (n)
  (cond ((= n 0) (string ""))
		(t
		 (string-concat (string "0")
						(zeros (- n 1))))))

;; 특정 길이만큼 스페이스 
(defun spacer (n)
  (cond ((= n 0) (string ""))
		(t
		 (string-concat (string " ")
						(spacer (- n 1))))))

사이냅 소프트 입사문제 Triple

주어진 양수의 리스트에서 다음과 같은 조건을 만족하는 조합의 수를 출력하기..

x + y = z

리스트 상의 모든 내역을 조사해서 해당하는 내역에 맞는 값의 조합을 구해내야한다.

(defun findout_triple (lst)
  (let ((n (length lst))
		(total 0))
	(do ((i 0 (+ i 1)))
		((eq n i) nil)
	  (let ((lst-i (nth i lst)))
		(do ((j 0 (+ j 1)))
			((or (eq n j) (eq i j)) nil)
		  (let ((lst-j (nth j lst)))
			(do ((k 0 (+ k 1)))
				((or (eq n k) (eq i k) (eq j k)) nil)
			  (let ((lst-k (nth k lst)))
				(if (or (eq (+ lst-i lst-j) lst-k)
						(eq (+ lst-i lst-k) lst-j)
						(eq (+ lst-j lst-k) lst-i))
					(progn
					  (format t "~A ~A ~A ~%" lst-i lst-j lst-k)
					  (setf total (+ total 1))))))))))
	total))

조금 헤멨던게 do 문에서 반복의 첨자로 루프가 돌 때, 해당 첨자에 문제가 있을 때까지도 해당식이 평가되기 때문에, 에러가 발생할 수 있다는 것..

지저분하게 풀렸다.. -_-;;;

사이냅 소프트 입사문제 3번

어떤 자연수가 세 개의 자연수의 제곱합으로 나타낼 수 있는지를 보여주기..

n^2 = a^2 + b^2 + c^2

원래는 하나만 보여줘야하지만 그냥 다 보여주는 루틴 만들어놨음
LISP의 루프 구조하나는 확실히 쓰게됐다...

(defun square (n)
  (* n n))

(defun find3num (n)
  (let ((sq (floor (sqrt n))))
	(dotimes (i (+ sq 1))
	  (let ((sq1 (floor (sqrt (- n (square i))))))
		(dotimes (j (+ sq1 1))
		  (let ((sq2 (floor (sqrt (- n (square i) (square j))))))
			(dotimes (k (+ sq2 1))
			  (cond ((= (+ (square i) (square j) (square k)) n)
					 (format t "~A ~A ~A ~%" i j k))))))))))

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

머.. 각 문자별로 입력하는 키 코드 값을 생성한 후에 전체 길이를 구하면 끝~~

;; Get char and return keypad list
;; ex) (mobilepad #\c) -> (2 2 2)
(defun mobilepad (ch)
  (cond 
	((char= ch #\a) '(2))
	((char= ch #\b) '(2 2))
	((char= ch #\c) '(2 2 2))
	((char= ch #\d) '(3))
	((char= ch #\e) '(3 3))
	((char= ch #\f) '(3 3 3))
	((char= ch #\g) '(4))
	((char= ch #\h) '(4 4))
	((char= ch #\i) '(4 4 4))
	((char= ch #\j) '(5))
	((char= ch #\k) '(5 5))
	((char= ch #\l) '(5 5 5))
	((char= ch #\m) '(6))
	((char= ch #\n) '(6 6))
	((char= ch #\o) '(6 6 6))
	((char= ch #\p) '(7))
	((char= ch #\q) '(7 7))
	((char= ch #\r) '(7 7 7))
	((char= ch #\s) '(7 7 7 7))
	((char= ch #\t) '(8))
	((char= ch #\u) '(8 8))
	((char= ch #\v) '(8 8 8))
	((char= ch #\w) '(9))
	((char= ch #\x) '(9 9))
	((char= ch #\y) '(9 9 9))
	((char= ch #\z) '(9 9 9 9))
	((char= ch #\Space) '(0))
	(t
	 (error "Incorrect Charater"))))


(defun str2pad (str)
  (cond ((= (length str) 0) '())
		(t
		 (append
		  (mobilepad (char str 0))
		  (str2pad (subseq str 1 (length str)))))))

;; 코드 길이 구하기
(defun padlength (str)
  (length (str2pad str)))

사이냅 소프트 입사문제 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)))

Twitter, 성능상의 문제로 Scala를 부분 도입..

근래에 Twitter 에 대해 많은 관심이 집중되는 모양이다. 구글이 인수하려고 한다는 얘기도 들리고 있고, 계속해서 접속량도 늘어나고 있다.

Twitter 는 ROR(Ruby on Rails)의 가장 대표적인 레퍼런스 사이트 중 하나이다. 루비야 그동안 알려진대로 유연성에, 깔끔함에.. 암튼 예쁜 언어임에는 틀림없다. 문제는 사이트가 거대해지면서 생기는 스크립트 언어 특유의 문제점이 곳곳에서 나타나고 있다는 점.

먼저 장기간에 걸쳐 안정적인 서비스를 하는데 있어서, 어느 정도 약점을 보이는 모양이다. Twitter 개발진에서도 이 점을 우려하고 있는 바... JVM의 최적화정도나 안정성에 상당히 긍정적인 시선을 보이는 것 같다.
결국 Twitter에서는 기존의 Rails 프레임 웍을 운영하면서, 적절한 서버쪽 부분의 재구성을 필요로하고 있었는데, Scala가 잘 맞아떨어진 모양이다. 자세한 사항은 Twitter on Scala를 참조하기 바란다.

작년부터 Scala나 Clojure에 대한 인기가 조금씩 나타나는 모양이다.
몇 년간 Perl, Python, Ruby 같은 언어 자체의 뛰어남을 보이는 분야가 강세였다면, 앞으로는 안정된 VM위에서 잘 운영될 수 있는 함수형 언어가 기존의 스크립트와 잘 어울리면서 성능을 보장해줄 수 있는 시스템이 많이 각광을 받을 것으로 생각한다.

C/C++로 엄청난 퍼포먼스를 내는 것이 필요로 할 수도 있고, 반면에 유연함과 안정성을 겸비한 VM위에서 동작하는 모델이 우위를 차지하는 부분이 앞으로 지속적으로 모습을 드러낼 것 같다. 개인적으로는 현재 1.0이 나온 Parrot 기반으로 C/C++과 Perl, 그리고 다른 많은 언어들의 조화로 JVM못지않은 훌륭한 시스템이 나와줬으면 하는 바램이다.

그런 의미로. Perl 만세~~ Long Live C/C++~~
마지막으로 함수형 언어는 꼭 공부해둡시다~~