what do you think about my code

On Jan 14, 6:37 pm, vtail <victor.kryu...@gmail.com> wrote:
> On Jan 14, 7:29 am, Kamen T <ka...@cybuild.com> wrote:
>
> > Hi,
>
> > I wrote a program for a programming competition and it would be great
> > if I could hear your comments on it. The idea and the code can be
> > found from here:
>
> >http://kamentomov.blogspot.com/2008/...mpetition.html

> More comments to follow once I understand the problem better.
>
> Victor.

Well, there's so much more that could be improved in your code.
Sometimes your use loop very straightforward; read about summing in
PCL. Sometimes you should use correct lisp idioms for doing things;
e.g. for collecting elements into lists it's a pair of push and
nreverse, not nconc. Here is the way to rewrite your read-avail-seats
function (note - in your version you return multiple values, but only
use the first one). I've added some closure for working with counters,
as you seam to use this same idea once more with node-num. Although do
seams a bit foreign at first, you should learn it - that will make you
more comfortable with loop, among other things.

(let ((counter 0))
(defun reset-counter ()
(setf counter 0))
(defun increment-counter ()
(incf counter))
(defun counter ()
counter))

(defun read-avail-seats (stream)
"Read a list of available seats from input stream and return
list of coordinates"
(reset-counter)
(let ((line (read-line stream)))
(with-input-from-string (s line)
(do ((x (read s nil 'eof) (read s nil 'eof)) ; x coordinate
(y (read s nil 'eof) (read s nil 'eof)) ; y coordinate
result) ; resulting list
((eql x 'eof) (nreverse result))
(push (make-coordinates :x x :y y :node (increment-counter))
result)))))

To make it somewhat more interactive - why don't your refactor your
code based on the ideas above: using read, moving stuff into separate
functions (hints: centroid, make-node inside the loop, etc.), and
refactoring repeating templates, and post your results here so that we
could improve it further.

Best,
Victor.

In article
<485f2746-d498-4b51-91e5-164f960b954e@v29g2000hsf.googlegroups.com>,
vtail <victor.kryukov@gmail.com> wrote:

> On Jan 14, 6:37 pm, vtail <victor.kryu...@gmail.com> wrote:
> > On Jan 14, 7:29 am, Kamen T <ka...@cybuild.com> wrote:
> >
> > > Hi,
> >
> > > I wrote a program for a programming competition and it would be great
> > > if I could hear your comments on it. The idea and the code can be
> > > found from here:
> >
> > >http://kamentomov.blogspot.com/2008/...mpetition.html
>
> > More comments to follow once I understand the problem better.
> >
> > Victor.
>
> Well, there's so much more that could be improved in your code.
> Sometimes your use loop very straightforward; read about summing in
> PCL. Sometimes you should use correct lisp idioms for doing things;
> e.g. for collecting elements into lists it's a pair of push and
> nreverse, not nconc. Here is the way to rewrite your read-avail-seats
> function (note - in your version you return multiple values, but only
> use the first one). I've added some closure for working with counters,
> as you seam to use this same idea once more with node-num. Although do
> seams a bit foreign at first, you should learn it - that will make you
> more comfortable with loop, among other things.
>
> (let ((counter 0))
> (defun reset-counter ()
> (setf counter 0))
> (defun increment-counter ()
> (incf counter))
> (defun counter ()
> counter))
>
> (defun read-avail-seats (stream)
> "Read a list of available seats from input stream and return
> list of coordinates"
> (reset-counter)
> (let ((line (read-line stream)))
> (with-input-from-string (s line)
> (do ((x (read s nil 'eof) (read s nil 'eof)) ; x coordinate
> (y (read s nil 'eof) (read s nil 'eof)) ; y coordinate
> result) ; resulting list
> ((eql x 'eof) (nreverse result))
> (push (make-coordinates :x x :y y :node (increment-counter))
> result)))))

The first problem with that is that this does not
work in a threaded environment or with multiple counter
uses. There is just one counter variable
and the counter functions can be called from any thread.
Two 'read-avail-seats' at the same time will reset/increment
the same counter variable.

Just don't do DEFUNs like that. It is evil.

Better:

a) make an instance of class counter

(defclass counter () (count))
(defmethod reset-counter ((counter counter))
(with-slots (count) counter (setf count 0))
counter)
(defun make-counter ()
(reset-counter (make-instance 'counter)))
and so on.

or

(defun make-counter ()
(let ((counter 0))
(lambda (action)
(case action
(:reset (setf counter 0))
(:incr ...

and so on.



or

(defun read-avail-seats (stream)
"Read a list of available seats from input stream and return
list of coordinates"
(let ((count 0) (line (read-line stream)))
(with-input-from-string (s line)
(do ((x (read s nil 'eof) (read s nil 'eof)) ; x coordinate
(y (read s nil 'eof) (read s nil 'eof)) ; y coordinate
result) ; resulting list
((eql x 'eof) (nreverse result))
(push (make-coordinates :x x :y y :node (incf count))
result))))))


>
> To make it somewhat more interactive - why don't your refactor your
> code based on the ideas above: using read, moving stuff into separate
> functions (hints: centroid, make-node inside the loop, etc.), and
> refactoring repeating templates, and post your results here so that we
> could improve it further.
>
> Best,
> Victor.

On Jan 14, 8:26 pm, Rainer Joswig <jos...@lisp.de> wrote:
> In article
> <485f2746-d498-4b51-91e5-164f960b9...@v29g2000hsf.googlegroups.com>,
>
>
>
> vtail <victor.kryu...@gmail.com> wrote:

>
> > (let ((counter 0))
> > (defun reset-counter ()
> > (setf counter 0))
> > (defun increment-counter ()
> > (incf counter))
> > (defun counter ()
> > counter))
>
> The first problem with that is that this does not
> work in a threaded environment or with multiple counter
> uses. There is just one counter variable
> and the counter functions can be called from any thread.
> Two 'read-avail-seats' at the same time will reset/increment
> the same counter variable.
>
> Just don't do DEFUNs like that. It is evil.
>
> Better:
>
> a) make an instance of class counter
>
> (defclass counter () (count))
> (defmethod reset-counter ((counter counter))
> (with-slots (count) counter (setf count 0))
> counter)
> (defun make-counter ()
> (reset-counter (make-instance 'counter)))
> and so on.
>
> or
>
> (defun make-counter ()
> (let ((counter 0))
> (lambda (action)
> (case action
> (:reset (setf counter 0))
> (:incr ...
>
> and so on.
>
> or
>
> (defun read-avail-seats (stream)
> "Read a list of available seats from input stream and return
> list of coordinates"
> (let ((count 0) (line (read-line stream)))
> (with-input-from-string (s line)
> (do ((x (read s nil 'eof) (read s nil 'eof)) ; x coordinate
> (y (read s nil 'eof) (read s nil 'eof)) ; y coordinate
> result) ; resulting list
> ((eql x 'eof) (nreverse result))
> (push (make-coordinates :x x :y y :node (incf count))
> result))))))

Yes, you're absolutely right - it's not thread-safe, thanks for
catching it.

Victor beat me to some of the stuff coming up, but
I still have some questions:


On Jan 15, 4:58 am, Kamen T <ka...@cybuild.com> wrote:

[[...]]

> The program was written under (time) pressure so you'd have to excuse
> the lack of documentation.

If there's time pressure, then I would probably skip the
regexps. Assuming there're no errors, why not use just use "read"?

(with-open-file (s "/cygdrive/c/home/temp/temp.txt")
(let ((num-students (read s))
(m (read s)))
(flet ((read-student (s)
(let ((num (read s)))
(loop
repeat num
collect (loop repeat 3 collect (read s)))))
(read-coord (s)
(list (read s) (read s))))
(list num-students m
(loop
for i from 1 upto num-students
collect `(,i ,(read-coord s)))
(loop
for i from 1 upto num-students
collect (list i (read-student s)))))))

That returns (pretty printed) ...

(10 99999
((33 3) (66 536) (99 39) (132 1514) (165 141) (198 2777) (231
326) ...)
((1
((8 28 3092) (6 37 631) (9 26 4908) (7 170 5782) (3 342 7076) (10
444 7883)
(8 372 9995) ...))
(2
((9 1 3915) (8 54 8653) (10 159 1990) (6 260 4307) (1 271 3504) (7
124 3117)
(3 186 3136) ...))
(3
((1 36 8379) (10 104 172) (8 152 7140) (9 110 8664) (7 62 4506)
(10 330 2313) (9 592 3789) ...))
(4 NIL)
(5
((10 8 9260) (7 51 5766) (2 169 5732) (6 293 7246) (6 330 1585) (6
202 2386)
(8 110 962) ...))
(6
((2 45 3312) (9 125 5273) (2 188 7353) (5 160 5465) (2 10 9740) (8
296 4180)
(10 600 9593)))
(7
((2 62 1347) (4 87 6198) (6 29 2561) (5 136 9222) (1 359 368) (4 537
2612)
(10 547 8575) ...))
...))

It is a function that just reads the file and gives you the
appropriate data-structure -- functional, no side-effects
required. Since this function is fewer than 20 lines, and is already
split into chunks, it should be easy to refactor or extend. eg flet
local funs -> defuns; instead of list or cons, you can use the
make-xxx struct creators/hash-tables instead.

[[ ... ]]

Your code runs in like 30 milliseconds (on my box), so I would
find a more effective (but intensive) algorithm before thinking
about optimising. Did you say the time limit was 10 secs?

Eg rotate "with best-pt-ix = 0" to start at different positions
and keep the best one?

> > Generally the code is quite readable, but it lacks
> > any documentation and any hints what the variables
> > and slots should hold.

A most appropriate comment here would be something high level,
that describes your
algorithm. What is it? A greedy depth-first graph-search that
allocates seats based on the centroid to all previously seated
students?

Well, how did you go? Was that an effective algorithm?

Thank you for sharing, and happy hacking.

On Tue, Jan 15 2008, szergling wrote:

> Victor beat me to some of the stuff coming up, but
> I still have some questions:
>
>
> On Jan 15, 4:58 am, Kamen T <ka...@cybuild.com> wrote:
>
> [[...]]
>
>> The program was written under (time) pressure so you'd have to
>> excuse the lack of documentation.
>
> If there's time pressure, then I would probably skip the
> regexps.
>
I meant time pressure to finish the program on time. However, the
program should also be very speed-optimized.

> Assuming there're no errors, why not use just use "read"?
>
How about because I never used it and it didn't occur to me it can do
such a good job so fast :-)

> (with-open-file (s "/cygdrive/c/home/temp/temp.txt")
> (let ((num-students (read s))
> (m (read s)))
> (flet ((read-student (s)
> (let ((num (read s)))
> (loop
> repeat num
> collect (loop repeat 3 collect (read s)))))
> (read-coord (s)
> (list (read s) (read s))))
> (list num-students m
> (loop
> for i from 1 upto num-students
> collect `(,i ,(read-coord s)))
> (loop
> for i from 1 upto num-students
> collect (list i (read-student s)))))))
>
> That returns (pretty printed) ...
>
> (10 99999
> ...))

That results in a real boost in performance.

> It is a function that just reads the file and gives you the
> appropriate data-structure -- functional, no side-effects
> required. Since this function is fewer than 20 lines, and is already
> split into chunks, it should be easy to refactor or extend. eg flet
> local funs -> defuns; instead of list or cons, you can use the
> make-xxx struct creators/hash-tables instead.
>
> [[ ... ]]
>
> Your code runs in like 30 milliseconds (on my box), so I would
> find a more effective (but intensive) algorithm before thinking
> about optimising. Did you say the time limit was 10 secs?
>
> Eg rotate "with best-pt-ix = 0" to start at different positions
> and keep the best one?
>
Hmm, I either don't understand your idea or it is not possible with my
algorithm. Every time we look for the best point we compare with a
newly calculated one. I'll explain further.

>> > Generally the code is quite readable, but it lacks
>> > any documentation and any hints what the variables
>> > and slots should hold.
>
> A most appropriate comment here would be something high level, that
> describes your algorithm. What is it? A greedy depth-first
> graph-search that allocates seats based on the centroid to all
> previously seated students?
>
> Well, how did you go? Was that an effective algorithm?
>

For each student we have a list of correspondents (other students whom
s/he has to send messages).

The algorithm is roughly the following: The list of correspondents is
sorted for each student so that the students who have more messages to
send/receive are in the beginning. Anyway we parse the graph in level
(not in depth) starting from the first element and we place in the
room with available seats each node we visit.

When choosing where to place the student we take into account the
placement of all previously placed students. We calculate the
theoretically best position (the centroid) and compare the distance
between it and each available seat. We place the student on the best
available seat. We do that until the list of students is exhausted and
all students are placed.

There is one known issue in the version that you've seen: The senders
are not taken into account when sorting the list of correspondents.

Thanks, the same to you!

I'm very grateful for the idea to use "read". I will rewrite the code
to integrate it and will publish it here.

--
Kamen

On Tue, Jan 15 2008, vtail wrote:

> On Jan 14, 7:29 am, Kamen T <ka...@cybuild.com> wrote:
>> Hi,
>>
>> I wrote a program for a programming competition and it would be
>> great if I could hear your comments on it. The idea and the code
>> can be found from here:
>>
>> http://kamentomov.blogspot.com/2008/...mpetition.html
>>
>> --
>> Kamen
>
> I've started looking into the problem, and it sounds
> interesting. Can you please comment what's the purpose of the
> message length / maximum message size? Does it put constraint on how
> students can exchange messages?
>
The purpose of the message size is the following: Each student can
send messages containing one or more themes. The number of themes a
message can contain depends on the size of the themes and the size of
the messages. The themes vary in size whereas the size of a message is
fixed and it is defined in the input file.

> Also, you seem to be impressed with CL-PPCRE, which is a very good
> library indeed. However, sometimes you can achieve the same with less
> effort. E.g. instead of
>
> (defun read-two-numbers (file)
> (multiple-value-bind (sss arr)
> (scan-to-strings
> '(:sequence
> (:register (:greedy-repetition 1 nil :digit-class))
> (:greedy-repetition 0 nil :whitespace-char-class)
> (:register (:greedy-repetition 1 nil :digit-class)))
> (read-line file nil))
> (declare (ignore sss))
> (values (parse-integer (aref arr 0))
> (parse-integer (aref arr 1)))))
>
> you could just say:
>
> (defun read-two-numbers (stream)
> "Read two numbers from the input stream and return them as values"
> (values (read stream) (read stream)))
>
> (defun test-read-two-numbers ()
> (with-input-from-string (s "12 13")
> (read-two-numbers s)))
>
> BASSCOM> (test-read-two-numbers)
> 12
> 13
>
Yeah, viva the CL "read"! Thanks!

> Even if for some reasons you forgot (or didn't know) about 'read',
> you may notice that (:register (:greedy-repetition 1 nil
> :digit-class)) etc. is the frequent pattern in your program. Usually
> something that is repeated over and over again is a good sign for
> refactoring.
>
Yeah of course - that's a good idea. I just didn't refactor, because
there wasn't time for it.

> Also, (macroexpand `,(* 2 (expt 10 (* 7 2)))) looks very...
> intriguing. What were you trying to say? (* 2 (expt 10 14)) provides
> the same answer. Also, if this constant is something meaningful for
> your algorithm, by no means define a symbolic constant for it.
>
:-) I just wanted to say `,(* 2 (expt 10 (* 7 2))), and the
macroexpand call remained from testing. I will define a constant when
refactoring.

> More comments to follow once I understand the problem better.
>
> Victor.

Sure - I'll try to answer all your questions.

--
Kamen

On Tue, Jan 15 2008, vtail wrote:

> On Jan 14, 6:37 pm, vtail <victor.kryu...@gmail.com> wrote:
>
> ...
> To make it somewhat more interactive - why don't your refactor your
> code based on the ideas above: using read, moving stuff into
> separate functions (hints: centroid, make-node inside the loop,
> etc.), and refactoring repeating templates, and post your results
> here so that we could improve it further.

Hi,

You can find the refactored code here:

http://paste.lisp.org/display/54481

The original was here:

http://paste.lisp.org/display/54164

I've replaced CL-PPCRE with the CL "read" as you and szergling
suggested (using szergling's code) and now the only required package
is #:cl. I've also documented the program it and applied some other
ideas. Also the algorithm is slightly improved.

Any further ideas (code, algorithm) would be much appreciated, not
because of the program, but for learning purposes.

--
Kamen