readme

数据挖掘中de一个算法 hamster的实例

Hamster --- A Programming Contest

The hamster program is intended as some kind of contest for students
who only recently learned to write programs. The current version of
this program supports the programming languages C and SmallEiffel.
(I am grateful to Ilona Bl"umel, who did most of the Eiffel programming.
A Pascal version is currently being developed. If you want to use some
other language: It is fairly simple to port the client program to other
programming languages, see below.)

The current version is still a prototype. Do not expect too much of
it, there are some limitations. For example, the program is currently
restricted to a single hamster. In the future I plan to extend it to
several hamsters in order to include parallel programming in the
contest (this may involve changing the control logic, though).

Enjoy!

Christian Borgelt

------------------------------------------------------------------------

Copying:

This program is free software; you can redistribute it and/or modify it
under the terms of the GNU General Public License as published by the
Free Software Foundation.

This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.

You should have received a copy of the GNU General Public License along
with this program; if not, write to the Free Software Foundation, Inc.,
59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.

------------------------------------------------------------------------

Idea:

A hamster, who has not yet collected its winter store, is released into
a maze. In this maze a certain amount of corn is distributed in heaps
of varying size. The task of the hamster is to collect as much corn
as possible and to carry it back to its starting point. Of course,
doing this, it has to try to minimize the distance it runs, in order
not to use up the largest part of the collected corn as food right away.

The problem to be solved is the following: The contestant is expected
to write program that controls the hamster while it is running around
in the maze. To this end a limited set of functions is available, with
which certain commands can be given to the hamster, like ``Turn left 90
degrees!'', ``Move forward one field!'', ``Take three grains of corn!''
etc. The order and number of these commands lies completely within the
responsibility of the contestant. He/She can do as he/she likes.

How well a programs solved the task described above is computed on the
basis of the number of grains of corn collected, the length of the path
travelled while collecting the corn, and the number of collisions with
the walls of the maze. These values are combined into a score, which
determines the ranking of the contest programs.

------------------------------------------------------------------------

The Programs and How to Build Them:

The hamster program runs as two separate processes, called the server
(the program that displays the window into which the maze is drawn) and
the client (the program that actually controls the hamster as it runs
around in the maze). The two processes communicate via an anonymous
pipe. The names of the corresponding programs are as follows:

             server         example C client   example Eiffel client
Unix         xhamster       hamster            ehamster (S.u.S.E. Linux)
MS Windows   whamster.exe   hamster.exe

The name of the client program can be changed freely, since the server
program allows to select a program to be run as the client (via the
menu entry `File > Select Hamster...'). However, the default is the
name of the example C client program.

The two programs are compiled from the following files:

server, window version (Unix/X11 or MS Windows)
  OS independent          Unix                    MS Windows
  hamster/hamster.h       unix/menu.h
  hamster/server.h        unix/menu.c
  hamster/server.c        unix/fselect.h
  hamster/maze.h          unix/fselect.c
  hamster/maze.c          unix/sprite.h           windows/sprite.h
                          unix/sprite.c           windows/sprite.c
                                                  windows/whamster.rh
                          unix/xhamster.rsc       windows/whamster.rc
                          unix/xhamster.c         windows/whamster.c
                          unix/excl.xbm
                          unix/hamster.xbm        windows/hamster.bmp
                                                  windows/mask.bmp
                          unix/logo.xbm           windows/logo.bmp

server, command line version (Unix only)
  unix/chamster.c         + OS independent files

example C client (OS independent)
  hamster/client.c
  hamster/control.c
  hamster/hamster.h

example Eiffel client (S.u.S.E. Linux SmallEiffel)
  eiffel/client.e
  eiffel/control.e
  eiffel/hamster.e

example Pascal client (Gnu Pascal, under construction)
  pascal/client.p
  pascal/control.p
  pascal/hamster.p

To compile the programs for Unix just do a 'make all' in the top
directory (the directory that contains the makefile). If the
compilation fails, you may need to change the definitions of the
`X11INC' and `X11LIB' macros in the makefile. I provided several
definitions for these two macros which I use on different machines
at the University of Magdeburg. The default setting is for S.u.S.E.
Linux (tested under version 6.0). If the compilation was successful,
you can start the hamster server with the `xh' script.

The Eiffel version of the example client can be compiled under
S.u.S.E. Linux by 'make ehamster' (provided SmallEiffel is installed).
The Pascal version of the example client can be compiled under Unix
by 'make phamster' (provided Gnu Pascal is installed).

To compile the programs for MS Windows load the Microsoft C project
workspace (whamster.mdp or whamster.dsw) into the Microsoft C
development environment and build both subprojects. If the compilation
was successful, you can start the hamster server by pressing Ctrl-F5
or by starting `whamster.exe' from the `bin' directory.

To test the programs, first initialize the maze: Select `Actions >
Randomize Maze...' and simply press the `Ok' button. Then start the
example hamster control program with `Actions > Start Hamster'. If
starting the hamster control program fails, try to select the file
`hamster' (Unix) or `hamster.exe' (MS Windows) from the `bin' directory
with `File > Select Hamster...' before starting the hamster. To test
the example Eiffel client, select the program 'ehamster' from the 'bin'
directory; to test the example Pascal client, select 'phamster'.

------------------------------------------------------------------------

Porting to other Programming Languages:

As already mentioned above, the hamster program runs as two separate
processes. The sole task of the client program is to translate a call
of a hamster function to a command that is written to stdout, to read
the reply of the server program from stdin and to pass the result back
to the hamster control function. Thus, in principle, any programming
language can be used that allows us to compile a stand alone program
that writes to stdout and reads from stdin. The example C client program
is compiled from the files `hamster.h', `hamster.c', and `client.c' in
the directory `hamster'. Hence, to port to a programming language other
than C, it should be sufficient to translate these files to the desired
language, provided there is a C compiler to compile the server program.