Hi All
First i thought that this group is only for guru
Lispers and i avoid it because i couldn't understand
anything but afterwards i read thread about breaking
numbers and i think is awesome for newbies like me
small interesthing problem and a lot of different solutions
from different people ,i'm working on my own today.
See there is no much exercises in the books
or not at all so i really don't know how to gain
experience with Lisp.
And most code is or trivial or too advanced for me.
So could somebody post some other task like this?
Presumably from some contest , or anything alike/
Just joking , here's one form the contest i participated several years
ago:
Hidden Words
Write a code findins presence of a words in a 8-way M x N"crossword" :
the "crossword" should be loaded from the file crossword.txt
checking-words should be loaded from file words.txt and
result should be written in the file results.txt
example:
crossword.txt '(7 4 LNUFEDVIARRAYCSEGATAUTDHLRGO)
LNUFEDV
IARRAYC
SEGATAU
TDHLRGO
words.txt '(defun array defmacro list cons) ;words that your program
should find
results.txt '(t t nil t nil)
fireblade <········@yahoo.com> wrote:
> Hidden Words
> Write a code findins presence of a words in a 8-way M x N"crossword" :
> the "crossword" should be loaded from the file crossword.txt
> checking-words should be loaded from file words.txt and
> result should be written in the file results.txt
Well, skipping the file I/O bit since it's boring, here's a quick &
cheesy solution using abundant brute force and ignorance, and some
displaced arrays since I'd never used them before. :)
It assumes that the "grid" is a 2-dimensional array of characters, and
the "word list" is a list of strings. Capitalization counts.
(defmethod transpose ((a array))
"Transpose a 2-dimensional array. Why isn't this function in Lisp?"
(assert (= (array-rank a) 2))
(let* ((rows (array-dimension a 0))
(cols (array-dimension a 1))
(result (make-array (list cols rows)
:element-type (array-element-type a))))
(dotimes (row rows result)
(dotimes (col cols)
(setf (aref result col row)
(aref a row col))))))
(defun word-in-grid-bfi (word grid)
"Is this word in the grid?"
(let ((rows (array-dimension grid 0))
(cols (array-dimension grid 1)))
(dotimes (row-num rows)
(let ((row (make-array cols
:element-type (array-element-type grid)
:displaced-to grid
:displaced-index-offset (* row-num cols))))
(when (search word row)
(return-from word-in-grid-bfi t))
(when (search word (nreverse (copy-seq row))) ; ew yuck
(return-from word-in-grid-bfi t))))
nil))
(defun wordsearch-bfi (grid words)
"Which of these words are in the grid?"
(let ((grid2 (transpose grid)))
(loop for word in words
collecting (or (word-in-grid-bfi word grid)
(word-in-grid-bfi word grid2)))))
; And here's a test case:
(defparameter *grid*
(make-array '(4 4) :element-type 'character
:initial-contents '(( #\G #\R #\I #\D )
( #\A #\O #\G #\U )
( #\M #\A #\D #\E )
( #\E #\M #\A #\T ))))
(defparameter *word-list*
'(; words that are obviously there
"GRID" "GAME" "ROAM" "DUET" "MADE"
; words that are only there in reverse
"TAME" "EDAM" "MAO"
; words that are NOT there
"SCORE" "EXIT" "PANT" "COW"))
(wordsearch-bfi *grid* *word-list*)
; outputs (T T T T T T T T NIL NIL NIL NIL)
Some possible optimizations:
* Compile the word list into a prefix tree, and traverse the grid once.
* Traverse the grid first, building a hash table of which rows and
columns have which letters in them. Then traverse the word list,
searching ONLY those rows and columns of the grid that have the right
letters.
* Take note of the grid dimensions. Reject up front any word that is
too long to fit on the grid!
--
Karl A. Krueger <········@example.edu> { s/example/whoi/ }
Since this is probably too easy even for a newbie
try the opposite , which is a challenging , at least for me:
Make a programm that constructs the 8-way crossword from a given
words,
the less chars in the crossword better solution .
For example :
words : '(bold big boom inn song leon noel moob)
solutions one (the obvious) 30 chars
bold
boom
song
leon
noel
moob
big
inn
solution two : 13 char
dlob
eoi
song
mn
"lispnewbie" <··········@yahoo.com> writes:
> And most code is or trivial or too advanced for me.
> So could somebody post some other task like this?
> Presumably from some contest , or anything alike/
Hmmm. Do you know differential calculus?
If so, the task is to build a simple symbolic differentiator function.
This can be a bit of an open-ended project, since the expansion of the
math forms you can handle can become large.
OK, here's what to do:
Implement a function DIFFERENTIATE that takes two arguments. A form and
a symbol. The form is an s-expression of a mathematical expression and
the symbol is a variable in that equation. The function returns the
differentiation of that expression.
For example:
(differentiate '(* 2 x) 'x) => 2
(differentiate '(expt x 3) 'x) => (* 3 (expt x 2))
etc.
OK this is not from a contest, but from a class I took in 1976 :)
--
Thomas A. Russ, USC/Information Sciences Institute
I can vouch for this: it's a very fun little project, and you can do
some neat things with it. For example, it would be cool if you could
write differentiation rules like this, and have the program do
automatic dispatching:
(defdiff * (a b dx)
`(+ (* ,(differentiate a dx) b)
(* a ,(differentiate b dx))))
And you could write trigonometric rules like this:
(defdiff sin (x dx)
`(* (cos ,x)
,(differentiate x dx)))
Or better yet
(defdiff-chain sin (x dx)
`(cos ,x))
Where DEFDIFF-CHAIN is a macro that expands into a DEFDIFF.
Then you'll probably want to do some basic simplification. For example,
(* 1 x) simplifies to x. If you don't do this, you will be very
annoyed. When you're doing simplification, it's nice to be able to ask,
"Is one of the arguments a constant? If so, bind it to a symbol and
bind the other one to another symbol." This takes abstraction. Whether
you decide to encapsulate this in a macro, or do a normalization pass
to get everything in a standard form, or something else, is your
choice.
The great thing about this is that you can do very interesting things
with it incrementally. You can start out simple and build up.
-Peter
Several people have posted great problems that are not too hard. A
textbook I often recommend is Winston and Horn, _Lisp_, 3rd ed. It has
lots of exercises, some easy, some not so easy.
"lispnewbie" <··········@yahoo.com> wrote:
> And most code is or trivial or too advanced for me.
> So could somebody post some other task like this?
> Presumably from some contest , or anything alike/
another idea would be to implement some real world application, like my
maze game:
http://www.frank-buss.de/lisp/clim.html
You don't need a fancy GUI, you can start it with "(play-maze
level-number)" in text mode. While implementing such a game, you have to
solve many little problems, like testing for valid moves and some more
complicated problems, like my solver for single targets. Perhaps you
want to enhance it for multiple targets.
Very interesting is OpenGL together with Lisp. Currently I'm developing
a small cellular automaton explorer. A screenshot of an early alpha
version, which shows an animation of the "Rabbits" pattern of the 2D
Game of Life automaton, where each iteration is another level at the z
axis:
http://www.frank-buss.de/tmp/ca.jpg
The source:
http://www.frank-buss.de/tmp/ca-explorer.lisp.txt
you have to install a bunch of other applications to run it, see:
······················································@newsreader3.netcologne.de
Because of the hardware acceleration and compiled OpenGL display lists,
the animation is very smooth.
--
Frank Bu�, ··@frank-buss.de
http://www.frank-buss.de, http://www.it4-systems.de
"lispnewbie" <··········@yahoo.com> wrote:
> And most code is or trivial or too advanced for me.
> So could somebody post some other task like this?
> Presumably from some contest , or anything alike/
There is an old book "Computers and Problem Solving", by the famous
numerical analyst T. E. Hull of the University of Toronto and
D. D. F. Day of the "North York Board of Education"; my copy was
published by "Addison-Wesley (Canada) Ltd. in 1970, but it seems
to have also been published in the US. I discovered this book while
I was in high school and spent the summer of 1971 working through
some of the projects in it.
I got to meet Tom Hull around 1987 (we had lunch), and it was quite
a lot of fun. I told him I loved the book because you could work for
a whole week on one of the problems at the end of a chapter. He told
me rather ruefully that the book was a dramatic failure, for precisely
the same reason ;-). The book teaches programming in Fortran in Part I,
but ignore that and go to part II, with chapters on Numerical Calculations,
Statistics, Simulations, Data Processing, Nonnumerical Calculations, and
Applications in Computer Science. There are substantial projects at the
end of each chapter.
Brad
>So could somebody post some other task like this?
>Presumably from some contest , or anything alike/
Actually there is a contest going on right now, and the Lisp team could
use some support ^^
http://shootout.alioth.debian.org/
There are many separate programming challenges, and languages are
scored based on how many challenges they can complete and how fast they
complete each challenge. Some of the challenges have no Lisp entries so
far, which hurts our score. If you decide to do one of them, post your
solution here before you send it in. That way other CLLers can help you
to optimize it.
Eric Lavigne wrote:
> >So could somebody post some other task like this?
> >Presumably from some contest , or anything alike/
>
> Actually there is a contest going on right now, and the Lisp team
could
> use some support ^^
>
> http://shootout.alioth.debian.org/
>
> There are many separate programming challenges, and languages are
> scored based on how many challenges they can complete and how fast
they
> complete each challenge. Some of the challenges have no Lisp entries
so
> far, which hurts our score. If you decide to do one of them, post
your
> solution here before you send it in. That way other CLLers can help
you
> to optimize it.
Interesthing contest , will try at home what can i do with pidigit ,
and why the wordfrequency
Lisp programm doesn't work.
Have you looked at Lindenmayer systems? By writing just a little code,
you can start making cool pictures in a cool and interesting way. The
L-system code itself is pretty simple; the hardest part is getting some
sort of image output set up. I've used McCLIM, CAPI, and LTk, but if
you're not familiar with any of those, I recommend either PostScript or
the CL-GD library from Edi Weitz.
Here's the article that got me started:
http://en.wikipedia.org/wiki/Lindenmayer_system
-Peter
"Peter Scott" <·········@gmail.com> wrote:
> Have you looked at Lindenmayer systems? By writing just a little code,
> you can start making cool pictures in a cool and interesting way. The
> L-system code itself is pretty simple; the hardest part is getting
> some sort of image output set up.
LTk is not so difficult, see for example this thread:
http://groups.google.com/groups?threadm=cgrcvj%24oaa%241%40newsreader3.netcologne.de
More interesting would be to use OpenGL and 3D Lindenmayer systems.
--
Frank Bu�, ··@frank-buss.de
http://www.frank-buss.de, http://www.it4-systems.de