Hello,
I am working on a successor function which given the current state
(and state value) and the overall configuration space of the puzzle,
gives all valid possible moves from the current state.
The puzzle is as following -
First configuration space (a 5x2 array, starting from {0,0} element
i.e. the Start state)
S...G
.*...
According to the rules for the puzzle, we start with a 6 sided
standard dice with 1 facing top and 3 facing right. The dice can be
slided onto any of four sides i.e. north, south, east and west. But
any such move is invalid if after sliding the dice on to any of its
sides results a 6 facing top.
Lets say that we start from S (with a 1 on top, 3 on right). If we
move to {0,1} cell i.e. to its right, it'll result in a state with (4
on top, 1 on right) and its a valid state. But if we try to move again
right, we happen to have 6 on top that is an invalid move. Okay, from
our current position at {0,1} if we try to move south then we land
into a "*" which also is an invalid move.
Like wise we have to keep on rolling the dice, until we reach to
G(goal) from S (start).
Following is another configuration space
S.......*
...**..G.
Successor function thus, will return all valid moves given a position
on the space and the space itself. I am thinking to represent the
current state as (x co-ord, y co-ord, and the value of the position
i.e. a "S", ".","*" or a "G".
Please help.
···········@gmail.com writes:
> Hello,
Hello.
> I am working on a successor function which given the current state
> (and state value) and the overall configuration space of the puzzle,
> gives all valid possible moves from the current state.
>
> The puzzle is as following -
This sounds like homework. If it is, you need to say so. If it is
not, then you should identify that clearly as well so that people who
might respond know they needn't worry about that.
You could also say more about where the puzzle came from. It is
expressed in a manner that is in certain ways abstract and yet seems
to be highly specific about seemingly arbitrary details, which is why
it has the feel of homework. In particular, almost nothing of what
you've offered is expressed in terms of Lisp terminology.
This group has traditionally provided support for homework, but you
should be sincere to say it is.
What seems to have been asked from you is to remake the "General
Problem Solver" program, discussed in detail in Dr.Norvig's PAIP book:
http://www.amazon.com/Paradigms-Artificial-Intelligence-Programming-Studies/dp/1558601910
Is it perhaps the text book for your course?
From: vanekl
Subject: Re: Successor function in LISP
Date:
Message-ID: <ftc9v3$vts$1@aioe.org>
···········@gmail.com wrote:
> Hello,
> I am working on a successor function which given the current state
> (and state value) and the overall configuration space of the puzzle,
> gives all valid possible moves from the current state.
>
> The puzzle is as following -
>
> First configuration space (a 5x2 array, starting from {0,0} element
> i.e. the Start state)
>
> S...G
> .*...
>
> According to the rules for the puzzle, we start with a 6 sided
> standard dice with 1 facing top and 3 facing right. The dice can be
> slided onto any of four sides i.e. north, south, east and west. But
> any such move is invalid if after sliding the dice on to any of its
> sides results a 6 facing top.
>
> Lets say that we start from S (with a 1 on top, 3 on right). If we
> move to {0,1} cell i.e. to its right, it'll result in a state with (4
> on top, 1 on right) and its a valid state. But if we try to move again
> right, we happen to have 6 on top that is an invalid move. Okay, from
> our current position at {0,1} if we try to move south then we land
> into a "*" which also is an invalid move.
>
> Like wise we have to keep on rolling the dice, until we reach to
> G(goal) from S (start).
>
> Following is another configuration space
>
> S.......*
> ...**..G.
>
> Successor function thus, will return all valid moves given a position
> on the space and the space itself. I am thinking to represent the
> current state as (x co-ord, y co-ord, and the value of the position
> i.e. a "S", ".","*" or a "G".
>
> Please help.
If you are unable to convert your problem to code in one step then
try to decompose the problem into smaller, simpler steps.
Try stating the solution in plain English. It doesn't have to be
precise at this stage, but just give you an idea as to whether
you understand the problem well enough to describe an algorithm
in high level terms.
If you cannot do this, then no amount of time sitting in front of
a Lisp REPL is going to help.
If you can do this, then try being more precise by restating the
English algorithm in pseudocode. You don't have to know Lisp to
do this.
Again, if you can't do this, there's no sense in trying to program
because Lisp doesn't have a solve-my-die-problem function that I'm
aware of, but it's possible that I just haven't stumbled upon it
yet---CL is a large language.
If you can write pseudocode for this problem, then learn some Lisp.
There was a thread just two days ago titled "Lisp power pack" that
should get you started. If that doesn't help, try searching, reading,
and learning the enormous quantities of Lisp information that have
already been made available to you before asking us to do your
homework assignment for you, or make copious amounts of money
available.
You also may want to look up bfs.
···········@gmail.com writes:
> Hello,
> I am working on a successor function which given the current state
> (and state value) and the overall configuration space of the puzzle,
> gives all valid possible moves from the current state.
>
> The puzzle is as following -
>
> First configuration space (a 5x2 array, starting from {0,0} element
> i.e. the Start state)
>
> S...G
> .*...
>
> According to the rules for the puzzle, we start with a 6 sided
> standard dice with 1 facing top and 3 facing right. The dice can be
> slided onto any of four sides i.e. north, south, east and west. But
> any such move is invalid if after sliding the dice on to any of its
> sides results a 6 facing top.
>
> Lets say that we start from S (with a 1 on top, 3 on right). If we
> move to {0,1} cell i.e. to its right, it'll result in a state with (4
> on top, 1 on right) and its a valid state. But if we try to move again
> right, we happen to have 6 on top that is an invalid move. Okay, from
> our current position at {0,1} if we try to move south then we land
> into a "*" which also is an invalid move.
>
> Like wise we have to keep on rolling the dice, until we reach to
> G(goal) from S (start).
>
> Following is another configuration space
>
> S.......*
> ...**..G.
>
> Successor function thus, will return all valid moves given a position
> on the space and the space itself. I am thinking to represent the
> current state as (x co-ord, y co-ord, and the value of the position
> i.e. a "S", ".","*" or a "G".
>
> Please help.
You need to modelize the dice:
- you need to know what number is on each side,
- what is the current orientation of the dice,
- how to 'rotate' it in either of the four directions. It's actually a
combination of rotation and translation.
One way to do that is to represent the die as a vector in 9
dimensions: 6 for the sides, two coordinates, and one constant, used to
easily translate the die, and the movements as matrices. Then moving
the die is trivial:
(defstruct (die (:type vector))
top right bottom left front back x y (c 1))
(defvar *die* (make-die :top 1 :right 3 :bottom 6 :left 4 :front 2 :back 5 :x 0 :y 0))
(defun move-die (die direction)
(matrix*vector direction die))
You can then check for a valid move as:
(let ((new-die (move-die *die* direction)))
(cond
((and (/= 6 (die-top new-die))
(valid-position *box* (die-x new-die) (die-y new-die)))
;; a valid move
(setf *die* new-die))
(t
;; not a valid move
)))
Here are the direction matrices:
(defparameter *right* #2A(( 0 1 0 0 0 0 0 0 0 )
( 0 0 1 0 0 0 0 0 0 )
( 0 0 0 1 0 0 0 0 0 )
( 1 0 0 0 0 0 0 0 0 )
( 0 0 0 0 1 0 0 0 0 )
( 0 0 0 0 0 1 0 0 0 )
( 0 0 0 0 0 0 1 0 1 )
( 0 0 0 0 0 0 0 1 0 )
( 0 0 0 0 0 0 0 0 1 )))
(defparameter *left* (matrix-invert *right*))
(defparameter *fore* #2A(( 0 0 0 0 0 1 0 0 0 )
( 0 1 0 0 0 0 0 0 0 )
( 0 0 0 0 1 0 0 0 0 )
( 0 0 0 1 0 0 0 0 0 )
( 1 0 0 0 0 0 0 0 0 )
( 0 0 1 0 0 0 0 0 0 )
( 0 0 0 0 0 0 1 0 0 )
( 0 0 0 0 0 0 0 1 1 )
( 0 0 0 0 0 0 0 0 1 )))
(defparameter *back* (matrix-invert *fore*))
C/USER[122]> (move-die *die* *fore*)
#(5 3 2 4 1 6 0 1 1)
C/USER[123]> (move-die *die* *back*)
#(2 3 5 4 6 1 0 -1 1)
C/USER[124]> (move-die (move-die *die* *fore*) *fore*)
#(6 3 1 4 5 2 0 2 1)
C/USER[125]> (move-die *die* *left*)
#(4 1 3 6 2 5 -1 0 1)
C/USER[126]> (move-die *die* *right*)
#(3 6 4 1 2 5 1 0 1)
C/USER[127]>
--
__Pascal Bourguignon__
On Apr 7, 6:32 am, ····@informatimago.com (Pascal J. Bourguignon)
wrote:
> ···········@gmail.com writes:
> > Hello,
> > I am working on a successor function which given the current state
> > (and state value) and the overall configuration space of the puzzle,
> > gives all valid possible moves from the current state.
>
> > The puzzle is as following -
>
> > First configuration space (a 5x2 array, starting from {0,0} element
> > i.e. the Start state)
>
> > S...G
> > .*...
>
> > According to the rules for the puzzle, we start with a 6 sided
> > standard dice with 1 facing top and 3 facing right. The dice can be
> > slided onto any of four sides i.e. north, south, east and west. But
> > any such move is invalid if after sliding the dice on to any of its
> > sides results a 6 facing top.
>
> > Lets say that we start from S (with a 1 on top, 3 on right). If we
> > move to {0,1} cell i.e. to its right, it'll result in a state with (4
> > on top, 1 on right) and its a valid state. But if we try to move again
> > right, we happen to have 6 on top that is an invalid move. Okay, from
> > our current position at {0,1} if we try to move south then we land
> > into a "*" which also is an invalid move.
>
> > Like wise we have to keep on rolling the dice, until we reach to
> > G(goal) from S (start).
>
> > Following is another configuration space
>
> > S.......*
> > ...**..G.
>
> > Successor function thus, will return all valid moves given a position
> > on the space and the space itself. I am thinking to represent the
> > current state as (x co-ord, y co-ord, and the value of the position
> > i.e. a "S", ".","*" or a "G".
>
> > Please help.
>
> You need to modelize the dice:
>
> - you need to know what number is on each side,
>
> - what is the current orientation of the dice,
>
> - how to 'rotate' it in either of the four directions. It's actually a
> combination of rotation and translation.
>
> One way to do that is to represent the die as a vector in 9
> dimensions: 6 for the sides, two coordinates, and one constant, used to
> easily translate the die, and the movements as matrices. Then moving
> the die is trivial:
>
> (defstruct (die (:type vector))
> top right bottom left front back x y (c 1))
>
> (defvar *die* (make-die :top 1 :right 3 :bottom 6 :left 4 :front 2 :back 5 :x 0 :y 0))
>
> (defun move-die (die direction)
> (matrix*vector direction die))
>
> You can then check for a valid move as:
>
> (let ((new-die (move-die *die* direction)))
> (cond
> ((and (/= 6 (die-top new-die))
> (valid-position *box* (die-x new-die) (die-y new-die)))
> ;; a valid move
> (setf *die* new-die))
> (t
> ;; not a valid move
> )))
>
> Here are the direction matrices:
>
> (defparameter *right* #2A(( 0 1 0 0 0 0 0 0 0 )
> ( 0 0 1 0 0 0 0 0 0 )
> ( 0 0 0 1 0 0 0 0 0 )
> ( 1 0 0 0 0 0 0 0 0 )
> ( 0 0 0 0 1 0 0 0 0 )
> ( 0 0 0 0 0 1 0 0 0 )
>
> ( 0 0 0 0 0 0 1 0 1 )
> ( 0 0 0 0 0 0 0 1 0 )
> ( 0 0 0 0 0 0 0 0 1 )))
>
> (defparameter *left* (matrix-invert *right*))
>
> (defparameter *fore* #2A(( 0 0 0 0 0 1 0 0 0 )
> ( 0 1 0 0 0 0 0 0 0 )
> ( 0 0 0 0 1 0 0 0 0 )
> ( 0 0 0 1 0 0 0 0 0 )
> ( 1 0 0 0 0 0 0 0 0 )
> ( 0 0 1 0 0 0 0 0 0 )
>
> ( 0 0 0 0 0 0 1 0 0 )
> ( 0 0 0 0 0 0 0 1 1 )
> ( 0 0 0 0 0 0 0 0 1 )))
>
> (defparameter *back* (matrix-invert *fore*))
>
> C/USER[122]> (move-die *die* *fore*)
> #(5 3 2 4 1 6 0 1 1)
> C/USER[123]> (move-die *die* *back*)
> #(2 3 5 4 6 1 0 -1 1)
> C/USER[124]> (move-die (move-die *die* *fore*) *fore*)
> #(6 3 1 4 5 2 0 2 1)
> C/USER[125]> (move-die *die* *left*)
> #(4 1 3 6 2 5 -1 0 1)
> C/USER[126]> (move-die *die* *right*)
> #(3 6 4 1 2 5 1 0 1)
> C/USER[127]>
>
> --
> __Pascal Bourguignon__
Rest all, it sure is my homework project. The only missing information
remaining is that I was totally unaware of the amount of Lisp usage in
my AI course beforehand.
Had I known that was the case and we will not be learning Lisp at all,
I would have re-considered taking this course but now that I am in the
course and did almost 3 assignments already (of course not in Lisp,
but in Java) I want to go ahead with some struggling and complete this
only project in Lisp. Most of the undergrad (and grad) students had
taken Lisp/Scheme programming course in their freshmen year but I have
never studied (nor worked) on these two.
I would have also not appreciated the fact that the student is
skirting off his work but this isn't the real picture. Assuming that
all of the students knew Lisp, this task was given to us two weeks
before and I have been trying to put whatever free time that I have to
complete this.
Now, Pascal thanks for your encouragement.
Last night, after studying defstruct in the book "COMMON LISP: A
Gentle Introduction to Symbolic Computation" that I happened to find
out, I became sure that I was going to use it in some way because
representing a node in the linklist using structures is quite a usual
way of C/C++ representation.
However, I have not really understood the meaning of (c 1) apart from
using c to represent the actual value of the cell that we are on right
now. Possible values of which could be "S", "G", "." or "*".
Also, looking at your direction matrices blew me completely because I
have not studied Lisp arrays and vectors. I have just started studying
arrays and vectors too i.e. I have jumped almost about half of the
book and trying to find my way out. :)
Please let me know any specific functions that I should study so in a
way studying those functions itself will guide me to the right
approach. I have to make most of my time in these two days to complete
whatever portion of the project complete and working.
Jhumpa Lahiri <··········@gmail.com> writes:
> [...]
> Rest all, it sure is my homework project. The only missing information
> remaining is that I was totally unaware of the amount of Lisp usage in
> my AI course beforehand.
>
> Had I known that was the case and we will not be learning Lisp at all,
> I would have re-considered taking this course but now that I am in the
> course and did almost 3 assignments already (of course not in Lisp,
> but in Java) I want to go ahead with some struggling and complete this
> only project in Lisp. Most of the undergrad (and grad) students had
> taken Lisp/Scheme programming course in their freshmen year but I have
> never studied (nor worked) on these two.
>
> I would have also not appreciated the fact that the student is
> skirting off his work but this isn't the real picture. Assuming that
> all of the students knew Lisp, this task was given to us two weeks
> before and I have been trying to put whatever free time that I have to
> complete this.
>
> Now, Pascal thanks for your encouragement.
>
> Last night, after studying defstruct in the book "COMMON LISP: A
> Gentle Introduction to Symbolic Computation" that I happened to find
> out, I became sure that I was going to use it in some way because
> representing a node in the linklist using structures is quite a usual
> way of C/C++ representation.
Well, you're lucky, arrays come just next, on chapter 13.
Note in section 13.4 that this is not the proper way to make a fresh
vector. In a program '#(nil nil) will always refer to the same
(possibly stored in read-only area) array. To create a fresh vector,
use: (vector 1 2 3), or make-array.
> However, I have not really understood the meaning of (c 1) apart from
> using c to represent the actual value of the cell that we are on right
> now. Possible values of which could be "S", "G", "." or "*".
This constant is a little trick used when representing affine
transformations as matrices.
http://en.wikipedia.org/wiki/Affine_transformation
For linear transformations in dimension N, you only need a N-vector to
represent your points, and a NxN matrix to represent any linear
transformation.
Eg. (scaling by 2) o (rotation by pi/3) is represented by the matrix:
( 2 0 ) x ( cos(pi/3) -sin(pi/3) ) = ( 2cos(pi/3) -2sin(pi/3) )
( 0 2 ) ( sin(pi/3) cos(pi/3) ) ( 2sin(pi/3) cos(pi/3) )
So you can get the tranformed point just multiplying the matrix
representing the transformation by the vector representing the point:
( 2cos(pi/3) -2sin(pi/3) ) x ( 1 ) = ( 2cos(pi/3) )
( 2sin(pi/3) cos(pi/3) ) ( 0 ) ( 2sin(pi/3) )
But for translations, we need to be able to add a constant per
coordinate. One way to do that, is to add a dimension, storing 1 in
the vectors, and the translation constants in the matrix:
( 2cos(pi/3) -2sin(pi/3) a ) ( 1 ) ( 2cos(pi/3)+a )
( 2sin(pi/3) cos(pi/3) b ) x ( 0 ) = ( 2sin(pi/3)+b )
( 0 0 1 ) ( 1 ) ( 1 )
The field C stores this last 1 in the vector, used in the matrix
multiplication to get +a and +b on the new X and Y coordinates.
You will need to keep a representation of the "terrain", of the grid,
with its size and the obstacles in it, to test whether the position of
the die after the move is valid.
Indeed, one easy way to do that is to use a 2D array again. Since the
movements are only �1 on each axis, we can simplify the test for a
valid move by representing walls around the terrain:
*******
*S...G*
*.*...*
*******
So the coordinate of S will be (1 1) instead of (0 0). But then,
testing for a valid move will just be:
(defun valid-move-p (new-die terrain)
(and (/= 6 (die-top new-die))
(not (wallp (aref terrain (die-x new-die) (die-y new-die))))))
(let ((new-die (move-die *die* direction)))
(cond
((valid-move-p new-die *terrain*)
;; a valid move
(setf *die* new-die))
(t
;; not a valid move
)))
> Also, looking at your direction matrices blew me completely because I
> have not studied Lisp arrays and vectors. I have just started studying
> arrays and vectors too i.e. I have jumped almost about half of the
> book and trying to find my way out. :)
Yes, and I've not provided the matrix operations, which are left as an
exercise for you. But you can also write the movements directly in
lisp. Since the matrices are very sparse, multiplying them with a
vector (top left bottom right front back x y 1) simplifies a lot, and
you can easily deduce these functions (or just invent them from
scratch).
> Please let me know any specific functions that I should study so in a
> way studying those functions itself will guide me to the right
> approach. I have to make most of my time in these two days to complete
> whatever portion of the project complete and working.
Well, really there are a lot of ways to represent this problem domain
and to implement a solution.
The idea is to invent a representation for the die, along with
functions to transform the die from one position to the next; invent a
representation for the terrain, along with functions to test whether
the die is in a valid or winning position, and to glue everything
together.
You can use almost any data structure to implement your
representaions, as long as you encapsulate them in an abstraction
layer. This is what I've done implicitely with DEFSTRUCT. Note that
I don't store my dice in a structure, but in a vector, as specified by
the defstruct option (:TYPE VECTOR). DEFSTRUCT provides the abstract
constructor (MAKE-DIE) and accessors (DIE-LEFT, DIE-X, etc) for a die,
hidding the fact that it's actually a vector. MOVE-DIE is another
function that hides this implementation detail: we just pass a die to
move-die, and it does its magic:
(move-die (make-die :left 'red :right 'green
:front 'yellow :back 'violet
:top 'blue :bottom 'red
:x 2 :y 3) *left*)
there's nothing related to the way a die or move-die is implemented
here. So you can implement them with whatever tool you know.
The only consequences of choosing an inadequate representation are
possibly time or space inefficiencies, and difficulty in writting the
algorithms. Choosing a matrix and vector representations allows me to
implement move-die without thinking about it, with just a matrix *
vector product. Another representation may need more work here.
On the other hand, this matrix representation is costly in space and
time (to multiply these matrices with vectors), given that it's mostly
zeroes. But this can be optimized without much work on the part of
the programmer:
`(progn
,@(loop
:for (funame direction) :in (list (list 'move-right *right*)
(list 'move-left *left*)
(list 'move-fore *fore*)
(list 'move-back *back*))
:collect (let ((die #(top right bottom left front back x y 1)))
(let* ((olds (butlast (coerce die 'list)))
(news (map 'list
(lambda (slot) (list (intern (format nil "DIE-~A" slot)) 'die))
olds)))
(labels ((substies (news olds tree)
(if (endp news)
tree
(substies (rest news) (rest olds) (subst (first news) (first olds) tree)))))
`(defun ,funame (die)
(make-die ,@(mapcan (lambda (slot new-value)
(when (symbolp slot)
(list (intern (symbol-name slot) "KEYWORD") (substies news olds new-value))))
(coerce die 'list)
(map 'list 'simplify-expression (symbolic-matrix*vector *right* die)))))))))
'done)
-->
(PROGN
(DEFUN MOVE-RIGHT (DIE)
(MAKE-DIE :TOP (DIE-RIGHT DIE) :RIGHT (DIE-BOTTOM DIE) :BOTTOM (DIE-LEFT DIE) :LEFT (DIE-TOP DIE) :FRONT (DIE-FRONT DIE) :BACK
(DIE-BACK DIE) :X (+ 1 (DIE-X DIE)) :Y (DIE-Y DIE)))
(DEFUN MOVE-LEFT (DIE)
(MAKE-DIE :TOP (DIE-RIGHT DIE) :RIGHT (DIE-BOTTOM DIE) :BOTTOM (DIE-LEFT DIE) :LEFT (DIE-TOP DIE) :FRONT (DIE-FRONT DIE) :BACK
(DIE-BACK DIE) :X (+ 1 (DIE-X DIE)) :Y (DIE-Y DIE)))
(DEFUN MOVE-FORE (DIE)
(MAKE-DIE :TOP (DIE-RIGHT DIE) :RIGHT (DIE-BOTTOM DIE) :BOTTOM (DIE-LEFT DIE) :LEFT (DIE-TOP DIE) :FRONT (DIE-FRONT DIE) :BACK
(DIE-BACK DIE) :X (+ 1 (DIE-X DIE)) :Y (DIE-Y DIE)))
(DEFUN MOVE-BACK (DIE)
(MAKE-DIE :TOP (DIE-RIGHT DIE) :RIGHT (DIE-BOTTOM DIE) :BOTTOM (DIE-LEFT DIE) :LEFT (DIE-TOP DIE) :FRONT (DIE-FRONT DIE) :BACK
(DIE-BACK DIE) :X (+ 1 (DIE-X DIE)) :Y (DIE-Y DIE)))
'DONE)
So now I represent the movements as lisp functions:
(defparameter *left* (function move-left))
...
and move-die becomes:
(defun move-die (die direction)
(funcall direction die))
Which will be at least ten times faster, and use almost a hundredth of the space.
But the point is that, unless this is the purpose of the exercise,
these optimizations don't matter (they're always possible). You
could implement make-die, die-left, die-right, etc using the list
processing functions you know, (and leaving a 'todo' comment to
reimplement them more efficiently when you'll know lisp vector and
array primitives).
What matters is to find abstractions that allow you to easily (clearly
and correctly) implement a solution to your problem.
--
__Pascal Bourguignon__
Jhumpa Lahiri <··········@gmail.com> writes:
> Most of the undergrad (and grad) students had
> taken Lisp/Scheme programming course in their freshmen year but I have
> never studied (nor worked) on these two.
This is OT, but which university are you at? I'm kind of surprised that
anybody gets undergrad courses in Lisp. I was told that even the MIT
replaced lisp by java.
BTW, re-doing homework in lisp is really a very nice way to improve your
programming capabilities. At least is was for me last year, as I was
bullheaded enough to keep coding stuff in CL, even when the libraries
provided by the course instructor were written in C++. But it brought
in a bottle of wine, as I found a bug in one of the libraries that way.
(Plus my lisp solution was faster by an order of magnitude).
Good luck with your project.
Albert
On Apr 7, 11:35 am, Albert Krewinkel <·········@gmx.net> wrote:
> Jhumpa Lahiri <··········@gmail.com> writes:
> > Most of the undergrad (and grad) students had
> > taken Lisp/Scheme programming course in their freshmen year but I have
> > never studied (nor worked) on these two.
>
> This is OT, but which university are you at? I'm kind of surprised that
> anybody gets undergrad courses in Lisp. I was told that even the MIT
> replaced lisp by java.
>
> BTW, re-doing homework in lisp is really a very nice way to improve your
> programming capabilities. At least is was for me last year, as I was
> bullheaded enough to keep coding stuff in CL, even when the libraries
> provided by the course instructor were written in C++. But it brought
> in a bottle of wine, as I found a bug in one of the libraries that way.
> (Plus my lisp solution was faster by an order of magnitude).
>
> Good luck with your project.
> Albert
Well aware of my current understanding of Lisp, looking at that code
made me shiver and made me to think about a bit approachable
representation of a node and the successor function that will generate
valid moves given a die state and the direction.
Now, let's say I represent a die using a list itself in the following
way
(list :top 1 :right 3 :front 2 :left 4 :back 5 :down 6 :x 0 :y 0)
I can readily retrieve the value of top and right by
(getf (list :top 1 :right 3 :front 2 :left 4 :back 5 :down 6 :x 0 :y
0) :top)
(getf (list :top 1 :right 3 :front 2 :left 4 :back 5 :down 6 :x 0 :y
0) :right)
Our 6 sided die can only move to four directions (right, left, front,
back) and therefore for a given number on top (let's say a 1), there
can be four different number(s) in its right (3, 2, 4, 5) and in the
same way for a 2 on top, there could be (3, 4, 6, 1) on its right.
If we have the top and right position for a certain dice we already
know the certain representation of the dice at that instant. For e.g.
if there's a 5 on top and a 4 on right, there can be only one distinct
combination existing for the given top and right and that is
(list :top 5 :right 4 :front 6 :left 3 :back 1 :down 2)
Thus we can make a 24 x 6 sized static array, valid-die-combinations,
which will have all of the valid possible die-states. i.e. 4 for each
(1, 2, 3, 4, 5, 6)
The following array considers the same order
(:top :right :front :left :back :down)
starting from ((1, 3, 2, 4, 5, 6), (1, 2, 4, 5, 3, 6), (1, 4, 5, 3, 2,
6) and the last one for 1 is (1, 5, 3, 2, 4, 6).....
and so on for 2, 3, 4, 5, 6....each
We will also have to make another puzzle-space array that will
represent the given puzzle in the row, column form such as
[S . . . G
. . . . .]
Where S can be retrieved using aref on puzzle-space array with the
help of row and column and therefore we can determine a IN-valid
"LEFT" move standing on (0, 0) position already.
Now let's start some wishful thinking for making a validate move
function
[CODE]
(defun validate-move (die direction)
"Make sure incrementing x by one when moving in x direction remains
lesser than or equal to max-x, where max-x can be retrieved from
puzzle-space array"
(cond ((not (eq (1+ (getf die :x)) max-x))
"Make sure that the new x and y in puzzle space is not an "*"
(not (eq (aref puzzle space x y) "*"))
(t
"We are allowed to move right"))
[/CODE]
Making a generate-move function
[CODE]
(defun generate-move(die direction)
(setf vdc-top (getf die :top))
(setf vdc-right (getf die :right))
(setf newdie (using aref and two pointers vdc-top, vdc-right
bring on the correct row, where vdc is the valid-die-combination array
and we have the information about a distinct row that has a unique
combination of top and right element)
[/CODE]
Here's the mean n mighty successor function .. which will generate the
moves and return it to my search algorithm.
[CODE]
(defun successor (die)
"We will be executing the same validate-move code for all four
directions one by one to generate at most four next valid states to
move from the current position in the puzzle"
"First for right"
(if (not (eq (validate-move die right) nil))
"Call generate-move function and generate a single state moving
right"
(if (not (eq (getf generate-move (die right) :top) 6))
(setf right-move generate-move (die right))
"second for front" and so on..
"At the end we will combine all generated right-move, front-move,
left-move and back-move, into a list and return it as a return value
)
[/CODE]
Pascal, please suggest me some keywords that I must use to make my
life easier to implement the above structural representation. I would
have surely liked the idea of going through each topic in the book one
by one myself, but as I have only a day left - I cant really enjoy
that leisure.
This representation looks familiar and I can understand it really
well. But when I will have enough knowledge of all Lisp, I would
surely try to better it off.
On Apr 7, 2:47 pm, ···········@gmail.com wrote:
> On Apr 7, 11:35 am, Albert Krewinkel <·········@gmx.net> wrote:
>
>
>
> > Jhumpa Lahiri <··········@gmail.com> writes:
> > > Most of the undergrad (and grad) students had
> > > taken Lisp/Scheme programming course in their freshmen year but I have
> > > never studied (nor worked) on these two.
>
> > This is OT, but which university are you at? I'm kind of surprised that
> > anybody gets undergrad courses in Lisp. I was told that even the MIT
> > replaced lisp by java.
>
> > BTW, re-doing homework in lisp is really a very nice way to improve your
> > programming capabilities. At least is was for me last year, as I was
> > bullheaded enough to keep coding stuff in CL, even when the libraries
> > provided by the course instructor were written in C++. But it brought
> > in a bottle of wine, as I found a bug in one of the libraries that way.
> > (Plus my lisp solution was faster by an order of magnitude).
>
> > Good luck with your project.
> > Albert
>
> Well aware of my current understanding of Lisp, looking at that code
> made me shiver and made me to think about a bit approachable
> representation of a node and the successor function that will generate
> valid moves given a die state and the direction.
>
> Now, let's say I represent a die using a list itself in the following
> way
> (list :top 1 :right 3 :front 2 :left 4 :back 5 :down 6 :x 0 :y 0)
>
> I can readily retrieve the value of top and right by
> (getf (list :top 1 :right 3 :front 2 :left 4 :back 5 :down 6 :x 0 :y
> 0) :top)
> (getf (list :top 1 :right 3 :front 2 :left 4 :back 5 :down 6 :x 0 :y
> 0) :right)
>
> Our 6 sided die can only move to four directions (right, left, front,
> back) and therefore for a given number on top (let's say a 1), there
> can be four different number(s) in its right (3, 2, 4, 5) and in the
> same way for a 2 on top, there could be (3, 4, 6, 1) on its right.
>
> If we have the top and right position for a certain dice we already
> know the certain representation of the dice at that instant. For e.g.
> if there's a 5 on top and a 4 on right, there can be only one distinct
> combination existing for the given top and right and that is
> (list :top 5 :right 4 :front 6 :left 3 :back 1 :down 2)
>
> Thus we can make a 24 x 6 sized static array, valid-die-combinations,
> which will have all of the valid possible die-states. i.e. 4 for each
> (1, 2, 3, 4, 5, 6)
>
> The following array considers the same order
> (:top :right :front :left :back :down)
> starting from ((1, 3, 2, 4, 5, 6), (1, 2, 4, 5, 3, 6), (1, 4, 5, 3, 2,
> 6) and the last one for 1 is (1, 5, 3, 2, 4, 6).....
> and so on for 2, 3, 4, 5, 6....each
>
> We will also have to make another puzzle-space array that will
> represent the given puzzle in the row, column form such as
> [S . . . G
> . . . . .]
>
> Where S can be retrieved using aref on puzzle-space array with the
> help of row and column and therefore we can determine a IN-valid
> "LEFT" move standing on (0, 0) position already.
>
> Now let's start some wishful thinking for making a validate move
> function
> [CODE]
> (defun validate-move (die direction)
> "Make sure incrementing x by one when moving in x direction remains
> lesser than or equal to max-x, where max-x can be retrieved from
> puzzle-space array"
> (cond ((not (eq (1+ (getf die :x)) max-x))
> "Make sure that the new x and y in puzzle space is not an "*"
> (not (eq (aref puzzle space x y) "*"))
> (t
> "We are allowed to move right"))
> [/CODE]
>
> Making a generate-move function
>
> [CODE]
> (defun generate-move(die direction)
> (setf vdc-top (getf die :top))
> (setf vdc-right (getf die :right))
> (setf newdie (using aref and two pointers vdc-top, vdc-right
> bring on the correct row, where vdc is the valid-die-combination array
> and we have the information about a distinct row that has a unique
> combination of top and right element)
> [/CODE]
>
> Here's the mean n mighty successor function .. which will generate the
> moves and return it to my search algorithm.
>
> [CODE]
> (defun successor (die)
> "We will be executing the same validate-move code for all four
> directions one by one to generate at most four next valid states to
> move from the current position in the puzzle"
> "First for right"
> (if (not (eq (validate-move die right) nil))
> "Call generate-move function and generate a single state moving
> right"
> (if (not (eq (getf generate-move (die right) :top) 6))
> (setf right-move generate-move (die right))
>
> "second for front" and so on..
>
> "At the end we will combine all generated right-move, front-move,
> left-move and back-move, into a list and return it as a return value
> )
>
> [/CODE]
>
> Pascal, please suggest me some keywords that I must use to make my
> life easier to implement the above structural representation. I would
> have surely liked the idea of going through each topic in the book one
> by one myself, but as I have only a day left - I cant really enjoy
> that leisure.
>
> This representation looks familiar and I can understand it really
> well. But when I will have enough knowledge of all Lisp, I would
> surely try to better it off.
Let's say that I have this array
(setf *puzzle-space* (make-array '(2 5)
:initial-contents
'((S D D D G)
(D D D D D))))
How do I retrieve the first row from it?
On Apr 7, 6:58 pm, ···········@gmail.com wrote:
> On Apr 7, 2:47 pm, ···········@gmail.com wrote:
>
>
>
> > On Apr 7, 11:35 am, Albert Krewinkel <·········@gmx.net> wrote:
>
> > > Jhumpa Lahiri <··········@gmail.com> writes:
> > > > Most of the undergrad (and grad) students had
> > > > taken Lisp/Scheme programming course in their freshmen year but I have
> > > > never studied (nor worked) on these two.
>
> > > This is OT, but which university are you at? I'm kind of surprised that
> > > anybody gets undergrad courses in Lisp. I was told that even the MIT
> > > replaced lisp by java.
>
> > > BTW, re-doing homework in lisp is really a very nice way to improve your
> > > programming capabilities. At least is was for me last year, as I was
> > > bullheaded enough to keep coding stuff in CL, even when the libraries
> > > provided by the course instructor were written in C++. But it brought
> > > in a bottle of wine, as I found a bug in one of the libraries that way.
> > > (Plus my lisp solution was faster by an order of magnitude).
>
> > > Good luck with your project.
> > > Albert
>
> > Well aware of my current understanding of Lisp, looking at that code
> > made me shiver and made me to think about a bit approachable
> > representation of a node and the successor function that will generate
> > valid moves given a die state and the direction.
>
> > Now, let's say I represent a die using a list itself in the following
> > way
> > (list :top 1 :right 3 :front 2 :left 4 :back 5 :down 6 :x 0 :y 0)
>
> > I can readily retrieve the value of top and right by
> > (getf (list :top 1 :right 3 :front 2 :left 4 :back 5 :down 6 :x 0 :y
> > 0) :top)
> > (getf (list :top 1 :right 3 :front 2 :left 4 :back 5 :down 6 :x 0 :y
> > 0) :right)
>
> > Our 6 sided die can only move to four directions (right, left, front,
> > back) and therefore for a given number on top (let's say a 1), there
> > can be four different number(s) in its right (3, 2, 4, 5) and in the
> > same way for a 2 on top, there could be (3, 4, 6, 1) on its right.
>
> > If we have the top and right position for a certain dice we already
> > know the certain representation of the dice at that instant. For e.g.
> > if there's a 5 on top and a 4 on right, there can be only one distinct
> > combination existing for the given top and right and that is
> > (list :top 5 :right 4 :front 6 :left 3 :back 1 :down 2)
>
> > Thus we can make a 24 x 6 sized static array, valid-die-combinations,
> > which will have all of the valid possible die-states. i.e. 4 for each
> > (1, 2, 3, 4, 5, 6)
>
> > The following array considers the same order
> > (:top :right :front :left :back :down)
> > starting from ((1, 3, 2, 4, 5, 6), (1, 2, 4, 5, 3, 6), (1, 4, 5, 3, 2,
> > 6) and the last one for 1 is (1, 5, 3, 2, 4, 6).....
> > and so on for 2, 3, 4, 5, 6....each
>
> > We will also have to make another puzzle-space array that will
> > represent the given puzzle in the row, column form such as
> > [S . . . G
> > . . . . .]
>
> > Where S can be retrieved using aref on puzzle-space array with the
> > help of row and column and therefore we can determine a IN-valid
> > "LEFT" move standing on (0, 0) position already.
>
> > Now let's start some wishful thinking for making a validate move
> > function
> > [CODE]
> > (defun validate-move (die direction)
> > "Make sure incrementing x by one when moving in x direction remains
> > lesser than or equal to max-x, where max-x can be retrieved from
> > puzzle-space array"
> > (cond ((not (eq (1+ (getf die :x)) max-x))
> > "Make sure that the new x and y in puzzle space is not an "*"
> > (not (eq (aref puzzle space x y) "*"))
> > (t
> > "We are allowed to move right"))
> > [/CODE]
>
> > Making a generate-move function
>
> > [CODE]
> > (defun generate-move(die direction)
> > (setf vdc-top (getf die :top))
> > (setf vdc-right (getf die :right))
> > (setf newdie (using aref and two pointers vdc-top, vdc-right
> > bring on the correct row, where vdc is the valid-die-combination array
> > and we have the information about a distinct row that has a unique
> > combination of top and right element)
> > [/CODE]
>
> > Here's the mean n mighty successor function .. which will generate the
> > moves and return it to my search algorithm.
>
> > [CODE]
> > (defun successor (die)
> > "We will be executing the same validate-move code for all four
> > directions one by one to generate at most four next valid states to
> > move from the current position in the puzzle"
> > "First for right"
> > (if (not (eq (validate-move die right) nil))
> > "Call generate-move function and generate a single state moving
> > right"
> > (if (not (eq (getf generate-move (die right) :top) 6))
> > (setf right-move generate-move (die right))
>
> > "second for front" and so on..
>
> > "At the end we will combine all generated right-move, front-move,
> > left-move and back-move, into a list and return it as a return value
> > )
>
> > [/CODE]
>
> > Pascal, please suggest me some keywords that I must use to make my
> > life easier to implement the above structural representation. I would
> > have surely liked the idea of going through each topic in the book one
> > by one myself, but as I have only a day left - I cant really enjoy
> > that leisure.
>
> > This representation looks familiar and I can understand it really
> > well. But when I will have enough knowledge of all Lisp, I would
> > surely try to better it off.
>
> Let's say that I have this array
> (setf *puzzle-space* (make-array '(2 5)
> :initial-contents
> '((S D D D G)
> (D D D D D))))
>
> How do I retrieve the first row from it?
Sorry, let me rephrase my earlier question.
If we have following array
(setf *possible-die-combinations* (make-array '(20 6)
:initial-contents
'((1 3 2 4 5 6)
(1 2 4 5 3 6)
(1 4 5 3 2 6)
(1 5 3 2 4 6)
(2 3 6 4 1 5)
(2 6 4 1 3 5)
(2 4 1 3 6 5)
(2 1 3 6 4 5)
(3 5 6 2 1 4)
(3 6 2 1 5 4)
(3 2 1 5 6 4)
(3 1 5 6 2 4)
(4 6 5 1 2 3)
(4 5 1 2 6 3)
(4 1 2 6 5 3)
(4 2 6 5 1 3)
(5 3 1 4 6 2)
(5 1 4 6 3 2)
(5 4 6 3 1 2)
(5 6 3 1 4 2))))
If you would notice, in every row the set of first and second elements
together is unique. For e.g. the first row has (1, 3) and the second
row has (1, 2).
Now I want to retrieve a specific row based on this given combination
of first and second element. How do I do it?
···········@gmail.com writes:
> If we have following array
> (setf *possible-die-combinations* (make-array '(20 6)
> :initial-contents
> '((1 3 2 4 5 6)
> (1 2 4 5 3 6)
> (1 4 5 3 2 6)
> (1 5 3 2 4 6)
> (2 3 6 4 1 5)
> (2 6 4 1 3 5)
> (2 4 1 3 6 5)
> (2 1 3 6 4 5)
> (3 5 6 2 1 4)
> (3 6 2 1 5 4)
> (3 2 1 5 6 4)
> (3 1 5 6 2 4)
> (4 6 5 1 2 3)
> (4 5 1 2 6 3)
> (4 1 2 6 5 3)
> (4 2 6 5 1 3)
> (5 3 1 4 6 2)
> (5 1 4 6 3 2)
> (5 4 6 3 1 2)
> (5 6 3 1 4 2))))
>
> If you would notice, in every row the set of first and second elements
> together is unique. For e.g. the first row has (1, 3) and the second
> row has (1, 2).
> Now I want to retrieve a specific row based on this given combination
> of first and second element. How do I do it?
With this data structure, you would have to search for it. But even
worse, once you got the correct row, you would then have to be careful
in your data access to get to the proper place.
So, I would use a data structure, either list-based (as in your earlier
example), or based on DEFSTRUCT to hold the representation of your die
orientation.
You can then introduce some additional data structures that would allow
you get access much faster. One simple answer would be to make a new
6x6 array that holds the valid positions. You could populate this from
a list of the data structures that you have already created. So, for
example:
(defparameter *valid-orientations* '((1 3 2 4 5 6)
(1 2 4 5 3 6)
(1 4 5 3 2 6)
(1 5 3 2 4 6)
(2 3 6 4 1 5)
(2 6 4 1 3 5)
(2 4 1 3 6 5)
(2 1 3 6 4 5)
(3 5 6 2 1 4)
(3 6 2 1 5 4)
(3 2 1 5 6 4)
(3 1 5 6 2 4)
(4 6 5 1 2 3)
(4 5 1 2 6 3)
(4 1 2 6 5 3)
(4 2 6 5 1 3)
(5 3 1 4 6 2)
(5 1 4 6 3 2)
(5 4 6 3 1 2)
(5 6 3 1 4 2)))
(defparameter *orientation-array*
(let ((array (make-array '(6 6) :initial-element nil)))
(dolist (orientation *valid-orientations*)
(setf (aref array (first orientation) (second orientation))
orientation))
array))
Now you have a data structure that uses the first two items as its key
to do an array lookup to find the value. So, to find the 4,2
orientation, you would just have to do:
(aref *orientation-array* 4 2) => (4 2 6 5 1 3)
and that gives you your data structure.
Now, you presumably will also want to have ways of finding the next
items as well. It is here that a more structured representation will
help you out. For example, you could also pre-compute and then store
the transformations for each type of move. That will give you a nice
foundation on which to build your algorithm.
Then you can just look up the answer instead of computing it each time.
--
Thomas A. Russ, USC/Information Sciences Institute
On Apr 7, 8:36 pm, ····@sevak.isi.edu (Thomas A. Russ) wrote:
> ···········@gmail.com writes:
> > If we have following array
> > (setf *possible-die-combinations* (make-array '(20 6)
> > :initial-contents
> > '((1 3 2 4 5 6)
> > (1 2 4 5 3 6)
> > (1 4 5 3 2 6)
> > (1 5 3 2 4 6)
> > (2 3 6 4 1 5)
> > (2 6 4 1 3 5)
> > (2 4 1 3 6 5)
> > (2 1 3 6 4 5)
> > (3 5 6 2 1 4)
> > (3 6 2 1 5 4)
> > (3 2 1 5 6 4)
> > (3 1 5 6 2 4)
> > (4 6 5 1 2 3)
> > (4 5 1 2 6 3)
> > (4 1 2 6 5 3)
> > (4 2 6 5 1 3)
> > (5 3 1 4 6 2)
> > (5 1 4 6 3 2)
> > (5 4 6 3 1 2)
> > (5 6 3 1 4 2))))
>
> > If you would notice, in every row the set of first and second elements
> > together is unique. For e.g. the first row has (1, 3) and the second
> > row has (1, 2).
> > Now I want to retrieve a specific row based on this given combination
> > of first and second element. How do I do it?
>
> With this data structure, you would have to search for it. But even
> worse, once you got the correct row, you would then have to be careful
> in your data access to get to the proper place.
>
> So, I would use a data structure, either list-based (as in your earlier
> example), or based on DEFSTRUCT to hold the representation of your die
> orientation.
>
> You can then introduce some additional data structures that would allow
> you get access much faster. One simple answer would be to make a new
> 6x6 array that holds the valid positions. You could populate this from
> a list of the data structures that you have already created. So, for
> example:
>
> (defparameter *valid-orientations* '((1 3 2 4 5 6)
> (1 2 4 5 3 6)
> (1 4 5 3 2 6)
> (1 5 3 2 4 6)
> (2 3 6 4 1 5)
> (2 6 4 1 3 5)
> (2 4 1 3 6 5)
> (2 1 3 6 4 5)
> (3 5 6 2 1 4)
> (3 6 2 1 5 4)
> (3 2 1 5 6 4)
> (3 1 5 6 2 4)
> (4 6 5 1 2 3)
> (4 5 1 2 6 3)
> (4 1 2 6 5 3)
> (4 2 6 5 1 3)
> (5 3 1 4 6 2)
> (5 1 4 6 3 2)
> (5 4 6 3 1 2)
> (5 6 3 1 4 2)))
>
> (defparameter *orientation-array*
> (let ((array (make-array '(6 6) :initial-element nil)))
> (dolist (orientation *valid-orientations*)
> (setf (aref array (first orientation) (second orientation))
> orientation))
> array))
>
> Now you have a data structure that uses the first two items as its key
> to do an array lookup to find the value. So, to find the 4,2
> orientation, you would just have to do:
>
> (aref *orientation-array* 4 2) => (4 2 6 5 1 3)
>
> and that gives you your data structure.
>
> Now, you presumably will also want to have ways of finding the next
> items as well. It is here that a more structured representation will
> help you out. For example, you could also pre-compute and then store
> the transformations for each type of move. That will give you a nice
> foundation on which to build your algorithm.
>
> Then you can just look up the answer instead of computing it each time.
>
> --
> Thomas A. Russ, USC/Information Sciences Institute
Thanks Russ, I have bypassed that search itself. I came up with
another rule to define the required change. :)
But I will soon be coming with another question.
On Apr 7, 9:57 pm, ···········@gmail.com wrote:
> On Apr 7, 8:36 pm, ····@sevak.isi.edu (Thomas A. Russ) wrote:
>
>
>
> > ···········@gmail.com writes:
> > > If we have following array
> > > (setf *possible-die-combinations* (make-array '(20 6)
> > > :initial-contents
> > > '((1 3 2 4 5 6)
> > > (1 2 4 5 3 6)
> > > (1 4 5 3 2 6)
> > > (1 5 3 2 4 6)
> > > (2 3 6 4 1 5)
> > > (2 6 4 1 3 5)
> > > (2 4 1 3 6 5)
> > > (2 1 3 6 4 5)
> > > (3 5 6 2 1 4)
> > > (3 6 2 1 5 4)
> > > (3 2 1 5 6 4)
> > > (3 1 5 6 2 4)
> > > (4 6 5 1 2 3)
> > > (4 5 1 2 6 3)
> > > (4 1 2 6 5 3)
> > > (4 2 6 5 1 3)
> > > (5 3 1 4 6 2)
> > > (5 1 4 6 3 2)
> > > (5 4 6 3 1 2)
> > > (5 6 3 1 4 2))))
>
> > > If you would notice, in every row the set of first and second elements
> > > together is unique. For e.g. the first row has (1, 3) and the second
> > > row has (1, 2).
> > > Now I want to retrieve a specific row based on this given combination
> > > of first and second element. How do I do it?
>
> > With this data structure, you would have to search for it. But even
> > worse, once you got the correct row, you would then have to be careful
> > in your data access to get to the proper place.
>
> > So, I would use a data structure, either list-based (as in your earlier
> > example), or based on DEFSTRUCT to hold the representation of your die
> > orientation.
>
> > You can then introduce some additional data structures that would allow
> > you get access much faster. One simple answer would be to make a new
> > 6x6 array that holds the valid positions. You could populate this from
> > a list of the data structures that you have already created. So, for
> > example:
>
> > (defparameter *valid-orientations* '((1 3 2 4 5 6)
> > (1 2 4 5 3 6)
> > (1 4 5 3 2 6)
> > (1 5 3 2 4 6)
> > (2 3 6 4 1 5)
> > (2 6 4 1 3 5)
> > (2 4 1 3 6 5)
> > (2 1 3 6 4 5)
> > (3 5 6 2 1 4)
> > (3 6 2 1 5 4)
> > (3 2 1 5 6 4)
> > (3 1 5 6 2 4)
> > (4 6 5 1 2 3)
> > (4 5 1 2 6 3)
> > (4 1 2 6 5 3)
> > (4 2 6 5 1 3)
> > (5 3 1 4 6 2)
> > (5 1 4 6 3 2)
> > (5 4 6 3 1 2)
> > (5 6 3 1 4 2)))
>
> > (defparameter *orientation-array*
> > (let ((array (make-array '(6 6) :initial-element nil)))
> > (dolist (orientation *valid-orientations*)
> > (setf (aref array (first orientation) (second orientation))
> > orientation))
> > array))
>
> > Now you have a data structure that uses the first two items as its key
> > to do an array lookup to find the value. So, to find the 4,2
> > orientation, you would just have to do:
>
> > (aref *orientation-array* 4 2) => (4 2 6 5 1 3)
>
> > and that gives you your data structure.
>
> > Now, you presumably will also want to have ways of finding the next
> > items as well. It is here that a more structured representation will
> > help you out. For example, you could also pre-compute and then store
> > the transformations for each type of move. That will give you a nice
> > foundation on which to build your algorithm.
>
> > Then you can just look up the answer instead of computing it each time.
>
> > --
> > Thomas A. Russ, USC/Information Sciences Institute
>
> Thanks Russ, I have bypassed that search itself. I came up with
> another rule to define the required change. :)
> But I will soon be coming with another question.
I am almost finishing my complete successor function but the thing
which is troubling me is I cant list'up a global variable in a loop
Code:
(defvar *successor-states* ())
(defun give-me-next-move(die)
(setf *successor-states* ())
(dolist (x '(right left up down))
(when (validate-constraints die x)
(when (not (eq (getf (generate-move die x) :top) 6))
(setf *successor-states* (cons *successor-states*
(generate-move die x)))))))
Is there tiny little thing that I am missing here. validate-
constraints function just tell me if I can move in a specific
direction or not, generate-move function generates the dice state
specific to an already validated move.
I have thoroughly tested the validate-constraints and generate-move
functions and I am pasting the output here.
For a given die like the one below
(setq die (list :top 1 :right 3 :front 2 :left 4 :back 5 :bottom 6 :x
0 :y 0))
> (validate-constraints die 'right)
T
> (validate-constraints die 'left)
NIL
> (generate-move die 'right)
(:TOP 4 :RIGHT 1 :FRONT 2 :LEFT 6 :BACK 5 :BOTTOM 3 :X 1 :Y 0)
> (generate-move die 'down)
(:TOP 2 :RIGHT 3 :FRONT 6 :LEFT 4 :BACK 1 :BOTTOM 5 :X 0 :Y 1)
···········@gmail.com writes:
> Let's say that I have this array
> (setf *puzzle-space* (make-array '(2 5)
> :initial-contents
> '((S D D D G)
> (D D D D D))))
>
> How do I retrieve the first row from it?
2d arrays in Common Lisp are not 1d arrays of 1d arrays. The only way
to access a "row" of it is to write yourself a function to retrieve it.
There is no builtin row operator. You can easily write something
that takes a 2d array and constructs the row. I don't know that you
want to--it sounds very memory intensive. If you really want arrays of
arrays, you can just do
(vector (vector 's 'd 'd 'd 'g)
(vector 'd 'd 'd 'd 'd))
Or if you're not planning to modify it, you can make it literally as
#(#(s d d d g) #(d d d d d))
That's not a 2d array, that's a 1d array of 1d arrays, and is distinct
from
#2A((s d d d g) (d d d d d))
If you're going to grow and shrink these arrays, btw, you might want to
look at more elaborate array constructors than just VECTOR. e.g., MAKE-ARRAY
and the :ADJUSTABLE and :FILL-POINTER options are sometimes useful.
Kent M Pitman <······@nhplace.com> writes:
> ···········@gmail.com writes:
>
>> Let's say that I have this array
>> (setf *puzzle-space* (make-array '(2 5)
>> :initial-contents
>> '((S D D D G)
>> (D D D D D))))
>>
>> How do I retrieve the first row from it?
>
> 2d arrays in Common Lisp are not 1d arrays of 1d arrays. The only way
> to access a "row" of it is to write yourself a function to retrieve it.
Besides, I fail to see the need to retrive a row, for this problem.
I thought the die could move only one step in either direction.
What we need is to know what is in the next cell in a given direction.
Otherwise, one easy way to get a row is to use a displaced array:
(defun rowref (array row &rest rows)
(if (endp rows)
(make-array (rest (array-dimensions array))
:displaced-to array
:displaced-index-offset (apply (function array-row-major-index)
array row
(make-list (1- (array-rank array))
:initial-element 0)))
(apply (function rowref) (rowref array row) rows)))
C/USER[350]> (rowref #3A(((1 2) (3 4)) ((5 6) (7 8)) ((9 a) (b c))) 1 0)
#(5 6)
C/USER[351]> (rowref #3A(((1 2) (3 4)) ((5 6) (7 8)) ((9 a) (b c))) 1 )
#2A((5 6) (7 8))
C/USER[352]> (rowref #3A(((1 2) (3 4)) ((5 6) (7 8)) ((9 a) (b c))) 1 1)
#(7 8)
But then, getting at the columns would not be possible with displaced
arrays, you'll have to copy the slots.
--
__Pascal Bourguignon__
···········@gmail.com writes:
> [...]
> Now, let's say I represent a die using a list itself in the following
> way
> (list :top 1 :right 3 :front 2 :left 4 :back 5 :down 6 :x 0 :y 0)
>
> I can readily retrieve the value of top and right by
> (getf (list :top 1 :right 3 :front 2 :left 4 :back 5 :down 6 :x 0 :y
> 0) :top)
> (getf (list :top 1 :right 3 :front 2 :left 4 :back 5 :down 6 :x 0 :y
> 0) :right)
> [...]
> We will also have to make another puzzle-space array that will
> represent the given puzzle in the row, column form such as
> [S . . . G
> . . . . .]
>
> Where S can be retrieved using aref on puzzle-space array with the
> help of row and column and therefore we can determine a IN-valid
> "LEFT" move standing on (0, 0) position already.
>
> Now let's start some wishful thinking for making a validate move
> function
> [CODE]
> (defun validate-move (die direction)
> "Make sure incrementing x by one when moving in x direction remains
> lesser than or equal to max-x, where max-x can be retrieved from
> puzzle-space array"
> (cond ((not (eq (1+ (getf die :x)) max-x))
> "Make sure that the new x and y in puzzle space is not an "*"
> (not (eq (aref puzzle space x y) "*"))
> (t
> "We are allowed to move right"))
> [/CODE]
The only problem with this function is that it depends on your
representation choice.
You should encapsulate your representation choices in an abstraction layer.
(defun make-die (top left bottom right front back x y)
(list :top top :left left :bottom bottom :right right :back back :x x :y y))
(defun die-x (die) (getf die :x))
(defun die-y (die) (getf die :y))
(defun die-top (die) (getf die :top))
...
Same with the 'puzzle'. You must choose how you represent the cells
too. With symbols, strings or something else?
For example if you represent a wall by the symbol *, you can write:
(defun wallp (cell) (eql '* cell))
but if you want to represent your cells with strings, you should write:
(defun wallp (cell) (string= "*" cell))
unless you make sure you're using always the same string (eql
corresponds to == in C, while string= corresponds to strcmp()). In
general we have: (not (eq "*" "*")). Also in general we have (not (eq
1 1)). Actually, you should never use EQ. At the very least, use
EQL, but when you have numbers, use =, when you have strings, string=,
etc.
In anycase, you can write your terrain abstraction using the cell
abstraction, independently of those implementation details:
(defun wall-at-position-p (terrain x y)
(wallp (aref terrain x y)))
so you can write your validate-move function using these abstractions:
(defun validate-move (die direction terrain)
"Make sure incrementing x by one when moving in x direction remains
lesser than or equal to max-x, where max-x can be retrieved from
puzzle-space array"
(cond ((getf die :x)
;; Make sure that the new x and y in puzzle space is not an "*"
(not (eq (aref puzzle space x y) "*"))
(t
"We are allowed to move right"))
But it might be simplier to generate a new die, and check if it's in a
valid position (within bounds, without a top 6, etc), than to check
whether some transformation wouldn't lead to an invalid position.
I would decompose this validate-move into two functions:
(valid-position-p die terrain) --> boolean
and (move-die die direction) --> new-die
so you could write:
(defun validate-move (die direction terrain)
(valid-position-p (move-die die direction) terrain))
or just avoid it, since you may want to avoid recomputing again and
again the new die.
> Making a generate-move function
>
> [CODE]
> (defun generate-move(die direction)
> (setf vdc-top (getf die :top))
> (setf vdc-right (getf die :right))
> (setf newdie (using aref and two pointers vdc-top, vdc-right
> bring on the correct row, where vdc is the valid-die-combination array
> and we have the information about a distinct row that has a unique
> combination of top and right element)
> [/CODE]
Use LET to define local variables, not SETQ or SETF.
(defun move-die (die direction)
(let ((vdc-top (die-top die))
(vdc-right (die-right die))
(new-die (make-die ...)))
new-die))
Since it returns a new die, I call it move-die, instead of generate-move.
> Here's the mean n mighty successor function .. which will generate the
> moves and return it to my search algorithm.
>
> [CODE]
> (defun successor (die)
> "We will be executing the same validate-move code for all four
> directions one by one to generate at most four next valid states to
> move from the current position in the puzzle"
> "First for right"
> (if (not (eq (validate-move die right) nil))
> "Call generate-move function and generate a single state moving
> right"
> (if (not (eq (getf generate-move (die right) :top) 6))
> (setf right-move generate-move (die right))
>
> "second for front" and so on..
>
> "At the end we will combine all generated right-move, front-move,
> left-move and back-move, into a list and return it as a return value
> )
>
> [/CODE]
Boolean can be used directly as conditions;
write (if (valid-move-p die right) ... ...)
instead of (if (not (eq (valid-move-p die right) 'nil)) ... ...)
Instead of: (if c1 (if c2 then))
you can write: (when (and c1 c2) then)
Instead of processing sequentially the various movements, doing
exactly the same for each of them you should put them in a sequence
and process it iteratively.
(loop :for direction :in (list fore back left right)
:for new-die (move-die die direction)
:when (valid-position-p new-die terrain)
:collect (list direction new-die))
or, using simplier lisp primitives:
(let ((results '()))
(dolist (direction (list fore back left right) results)
(let ((new-die (move-die die direction)))
(when (valid-position-p new-die terrain)
(push (list direction new-die) results)))))
> Pascal, please suggest me some keywords that I must use to make my
> life easier to implement the above structural representation. I would
> have surely liked the idea of going through each topic in the book one
> by one myself, but as I have only a day left - I cant really enjoy
> that leisure.
>
> This representation looks familiar and I can understand it really
> well. But when I will have enough knowledge of all Lisp, I would
> surely try to better it off.
--
__Pascal Bourguignon__