99 lisp problems

Here is the solutions to 99 lisp problems so far. I am Problem 11.

;P01 (*) Find the last box of a list.
;Example:
;* (my-last '(a b c d))
;(D)

to my.last :list 
 ifelse emptyp butfirst :list 
  [output first :list]
  [output my.last butfirst :list]
end 

to my.last2 :list 
 output last :list
end 


;P02 (*) Find the last but one box of a list.
;Example:
;* (my-but-last '(a b c d))
;(C D)

to my.but.last :list 
 ifelse emptyp butfirst butfirst :list 
  [output :list]
  [output my.but.last butfirst :list]
end 

;P03 (*) Find the K'th element of a list.
;The first element in the list is number 1.
;Example:
;* (element-at '(a b c d e) 3)
;C

to element.at :list :index  
 ifelse emptyp :list
  [output :list]
  [ifelse equalp :index 1 
   [output first :list]
   [output element.at butfirst :list (:index - 1)]]
end

to element.at2 :list :index 
 output item :index :list 
end 

;P04 (*) Find the number of elements of a list.

to number.of.elements :list 
 ifelse emptyp :list 
  [output 0]
  [output 1 + number.of.elements butfirst :list]
end 

to number.of.elements2 :list 
 output count :list
end

;P05 (*) Reverse a list.

to my.reverse :list 
 ifelse emptyp :list  
  [output :list]
  [output sentence (my.reverse butfirst :list) first :list]
end


;P06 (*) Find out whether a list is a palindrome.
;A palindrome can be read forward or backward; e.g. (x a m a x).

to palindrome :list
 output equalp :list (my.reverse :list)
end 

;P07 (**) Flatten a nested list structure.
;Transform a list, possibly holding lists as elements into a `flat' list 
;by replacing each list with its elements (recursively).

;Example:
;* (my-flatten '(a (b (c d) e)))
;(A B C D E)

;Hint: Use the predefined functions list and append.

to my.flatten :list 
 ifelse emptyp :list 
  [output :list]
  [ifelse listp first :list 
   [output sentence (my.flatten first :list) (my.flatten butfirst :list)]
   [output sentence first :list my.flatten butfirst :list]]
end 


;show my.flatten [a [b [c d] e]]

;P08 (**) Eliminate consecutive duplicates of list elements.
;If a list contains repeated elements they should be replaced 
;with a single copy of the element. The order of the elements should not be changed.

;Example:
;* (compress '(a a a a b c c a a d e e e e))
;(A B C A D E)

to compress :list 
 ;show :list 
 ifelse emptyp butfirst :list  
  [output :list]
  [ifelse equalp (first :list) (first butfirst :list) 
   [output compress butfirst :list]
   [output sentence first :list compress butfirst :list]]
end 

to compress.2.run :list :item 
 ifelse emptyp :list  
  [output :list]
  [ifelse equalp :item first :list
   [output compress.2.run butfirst :list :item]
   [output sentence first :list compress.2.run butfirst :list first :list]]
end 

to compress.2 :list 
 output compress.2.run :list []
end 

;show compress.2 [a a a a b c c a a d d e e e e]



;P09 (**) Pack consecutive duplicates of list elements into sublists.
;If a list contains repeated elements they should be placed in separate sublists.

;Example:
;* (pack '(a a a a b c c a a d e e e e))
;((A A A A) (B) (C C) (A A) (D) (E E E E))

to pack.run :list :item :group 
 ;show :group 
 ifelse emptyp :list  
  [output fput fput :item :group []]
  [ifelse equalp first :list :item 
   [output pack.run (butfirst :list) :item (fput :item :group )]
   [output fput (fput :item :group) pack.run butfirst :list first :list [] ]]
end 

to pack :list
 output pack.run :list [] []
end 

;show pack [a a a a b c c a a d e e e e]

;P10 (*) Run-length encoding of a list.
;Use the result of problem P09 to implement the so-called run-length encoding data compression method. Consecutive duplicates of elements are encoded as lists (N E) where N is the number of duplicates of the element E.

;Example:
;* (encode '(a a a a b c c a a d e e e e))
;((4 A) (1 B) (2 C) (2 A) (1 D)(4 E))


to encode :list 
 ifelse emptyp :list  
  [output :list]
  [output fput fput count first :list fput first first :list [] encode butfirst :list]
end 

;show encode butfirst pack [a a a a b c c a a d e e e e]

;P11 (*) Modified run-length encoding.
;Modify the result of problem P10 in such a way that if an element has no duplicates it is simply copied into the result list. Only elements with duplicates are transferred as (N E) lists.

;Example:
;* (encode-modified '(a a a a b c c a a d e e e e))
;((4 A) B (2 C) (2 A) D (4 E))

to encode.modified :list 
 ifelse emptyp :list 
  [output :list]
  [ifelse (count first :list) = 1  
   [output fput first first :list encode.modified butfirst :list ]
   [output fput fput count first :list fput first first :list [] ~
           encode.modified butfirst :list]]
end 

show encode.modified butfirst pack [a a a a b c c a a d e e e e]

Comments

Post a Comment

Popular posts from this blog

Recursion Part 1

Recursion is art of making programs call themselves. It is my opinion, recursion is the main idea in computer programming. In fact early computer theorist where recursion theorist( eg. church, curry, ackermann,etc). Recursion theory inspired functional programming in the 70s. Functional programming is prefered by these mathematically oriented programmers not only by its elagence but by it suitability to be reasoned with mathematically. Lisp was invented by John Mccathy in 1958. It was also based in recursive theory paradigm. The language in my opinion possesess the beauty of the mathematics it inherited from. It has simple syntax(core language i mean). eg. only 5 primitive operations are defined: car,cdr,cons,eq, and null. Knowing these together with statements for creating functions(lamda or defun) and conditional statements(if, cond) one can derive everything else using the language. I am set to master lisp, not necessary to use as a language in my programming task, but you thi...
Read more

Back to programming competitons

I am coming back to programming competitions. and as preparation I am back at a study of recursion. I have bought books and read websites on this topics over the years. Only lately have I thought I made progress. Firstly I must thank God for getting to know lisp. And getting to understand its power. List makes you look at programs in a different way. I never knew a programming language could make a person see the programs different. Also the idea of list forces you to program using data. Very smart. And data is static. You generate output as the program progress. All you should be worried about the final list and the list you consume. It is highly recommended for anyone who wants to do serious programming. A key advantage of engaging in programming competitions is it will boost your programming skills. In my opinion, this is how far it can go. I don't think a good algorithms programmer automatically can make a good software developer. Development in my opinion is another skill,...
Read more

Debugging Part 3

I am debugging the following program, and I started realising the disadvatanges of blind debugging. I had solved the problem before. And I solved it through debugging. So now faced with the same problem I seem not to remember how I solved it. So here i is the disadvatanges of blind debugging. It is adhoc and prone to blind programming. The other way I like to say it, is it is "hacky". Not hack of breaking computers but that of prototyping something quickly without following principles. I am still in the process of solving the problem below. When I am done, I will let you know how I did it. ;P09 (**) Pack consecutive duplicates of list elements into sublists. ;If a list contains repeated elements they should be placed in separate sublists. ;Example: ;* (pack '(a a a a b c c a a d e e e e)) ;((A A A A) (B) (C C) (A A) (D) (E E E E)) to pack.run :list :item ifelse emptyp :list [output :list] [ifelse equalp first :list :item [output sentence first :list pa...
Read more