Quantcast

Maximum PC

It is currently Thu Jul 24, 2014 6:06 am

All times are UTC - 8 hours




Post new topic Reply to topic  [ 6 posts ] 
Author Message
 Post subject: I have a LISP II - The Farmer, Fox, Goose, and Grain
PostPosted: Thu Feb 14, 2008 6:15 am 
SON OF A GUN
SON OF A GUN
User avatar

Joined: Mon Nov 01, 2004 5:41 am
Posts: 11605
So... I have pretty much figured out this solution, and I am representing it by a n-bit number, giving 2^n=16 states. I know HOW to solve it, but we need to take the state space (Which I built, but I am not 100% sure it is correct) and search it with some generic blind search...

So, I have the following functions written already, but I am totally lost with the path-search portion of it. I have some "pseudocode" for that, but I am not sure how to do it.....

Edit: Apparently, I shouldn't believe everything I read on the internet. :) I will hopefully have this figured out sometime Sunday, and I will post my answer.

Code:
;; Function to create a target state, that takes in the location of each of the 4 entities of the problem
(defun make-state (farmer fox goose grain)
   (let ((state nil))
      (push grain state)
      (push goose state)
      (push fox state)
      (push farmer state)
   );; pushes the entities onto the list in reverse order so that the farmer is first and the grain is last.
)

;; Finds the side that the farmer is currently standing on
(defun farmer-side (state)
   (setq side (car state))
)

;; Finds the side that the fox is currently standing on
(defun fox-side (state)
   (setq side (second state))
)

;; Finds the side that the goose is currently standing on
(defun goose-side (state)
   (setq side (third state))
)

;; Finds the side that the grain is currently piled on
(defun grain-side (state)
   (setq side (last state))
)

;; Function that performs the blind search through the statespace to find a path / solution
;; to the problem
(defun path-search (state goal pathlist)

)


Code:
path (state, goal, pathlist){
   if state == goal{
      append state to pathlist
      return pathlist
   }
   else{
      while (child states exist){
         prev_state = state
         new_child_state = generated child state
         if child == valid
            append prev_state to pathlist
            path (new_child_state, goal, pathlist)
      }
   }
}


Top
  Profile  
 
 Post subject:
PostPosted: Mon Feb 18, 2008 10:42 am 
SON OF A GUN
SON OF A GUN
User avatar

Joined: Mon Nov 01, 2004 5:41 am
Posts: 11605
welp, never figured it out by the time it was due... =/

Here is a solution one of my classmates came up with:

Code:
;;;For this project all you need to do is (load "textfilename") and run
;;;commands  (solve-ffgg start goal) where start and goal are in form of
;;;'(T T T T) or '(O O O O) or some combo of O and T only

;;returns side of farmer the first element in state
(defun farmer-side (state)
  (first state)
)
;;returns side of fox the second element in state
(defun fox-side (state)
  (second state)
)
;;returns side of goose the third element in state
(defun goose-side (state)
  (third state)
)
;;returns side of grain the fourth element in state
(defun grain-side (state)
  (fourth state)
)
; ;change give state from this side to other side or other side to this side
(defun opposite (currentSide)
   (cond
      ((equal currentSide 'O) 'T); If it was other side its now this side
      ((equal currentSide 'T) 'O);If it was this side it is other side
   )
)
;;Makes a list with the correct format of farmer fox goose grain
(defun make-state (farmer fox goose grain)
   (list farmer fox goose grain)
   )
;;farmer changes side others same
(defun oppositeFsameFGG (state)
  (valid (make-state (opposite (farmer-side state))     ; farmer changes side and checks to see if valid state
            (fox-side state)         ;fox stays on same side
            (goose-side state)         ; goose stays on same side
            (grain-side state)      ; grain stays on same side
   )
  )
)
;;farmer and fox changes side others stay
(defun oppositeFFsameGG (state) (cond
  ((equal (farmer-side state) (fox-side state))   
    (valid (make-state (opposite (farmer-side state))   ; farmer change sides and checks to see if it a valid state
                      (opposite (fox-side state))   ; change sides
                      (goose-side state)         ; goose stays on same side
                      (grain-side state)      ; grain stays on same side
          )
    )
  )
  (t nil) ; not possible to take this path
))                       
;;farmer and goose change side and others stay
(defun oppositeFGosameFG (state) (cond
  ((equal (farmer-side state) (goose-side state))
    (valid (make-state (opposite (farmer-side state))   ; farmer changes sides and checks to see if valid state
                      (fox-side state)         ; fox stays on same side
                      (opposite (goose-side state))   ; goose changes side
                      (grain-side state)      ; grain stays on same side
          )
    )
  )
  (t nil) ; not possible to take this path
))
; ; checks for valid states and returns true if it is or nil if not
(defun valid (state)
   (cond;check to see if invalid state was passed
      ((and (equal (goose-side state) (fox-side state))  ; fox eats goose
      (not (equal (farmer-side state) (fox-side state))) ;no farmer supervision
      ) nil); true so return false, not valid since fox eats goose
   ((and (equal (goose-side state) (grain-side state))  ; goose eats grain
        (not (equal (farmer-side state) (goose-side state))); no farmer supervision
   ) nil); true so return false, not valid since goose eats grain
   (t state)
))
;;farmer and grain change sides and others stay
(defun oppositeFGrsameFG (state) (cond
  ((equal (farmer-side state) (grain-side state))
    (valid (make-state (opposite (farmer-side state))   ; farmer changes side and checks if valid state
                      (fox-side state)         ; fox stays on same side
                      (goose-side state)         ; goose stays on same side
                      (opposite (grain-side state))   ; grain changes side
          )
    )
  )
  (t nil) ; not possible to take this path
))
; ;recurcive calls to search path from given start to goal state
(defun path (start goal previousState)
   (cond
      ((null start) nil)   ; base case we are done since we ran out of nodes
      ((equal start goal) (reverse (cons start previousState)))  ; found state
      ((not (member start previousState :test #'equal))  ; checks based off previous states array for already visited state
      ;Needed to override original to compare strings
      ; if we havent visited it lefts try there children
      (or (path (oppositeFsameFGG start) goal (cons start previousState)) ; only farmer crosses
         (path (oppositeFFsameGG start) goal (cons start previousState))     ; farmer takes fox accross with him
         (path (oppositeFGosameFG start) goal (cons start previousState))     ; farme takes goose accrossed with him
         (path (oppositeFGrsameFG start) goal (cons start previousState))  ; takes grain
   ))))
; ;searches path from start to goal
(defun solve-ffgg (start goal)
      ;Checks for valid strings in the list
      (if(not (valid start)) "Invalid start"
      (if(not (valid goal)) "Invalid Goal Node"
      ;Following checks of invalid char in the list
      (if(not (or (equal (first start) 'T) (equal (first start) 'O))) "Invalid first char in start Node"
      (if(not (or (equal (second start) 'T) (equal (second start) 'O))) "Invalid first char in start Node"
      (if(not (or (equal (third start) 'T) (equal (third start) 'O))) "Invalid first char in start Node"
      (if(not (or (equal (fourth start) 'T) (equal (fourth start) 'O))) "Invalid first char in start Node"
      (if(not (or (equal (first goal) 'T) (equal (first goal) 'O))) "Invalid first char in start Node"
      (if(not (or (equal (second goal) 'T) (equal (second goal) 'O))) "Invalid first char in start Node"
      (if(not (or (equal (third goal) 'T) (equal (third goal) 'O))) "Invalid first char in start Node"
      (if(not (or (equal (fourth goal) 'T) (equal (fourth goal) 'O))) "Invalid first char in start Node"
    (path start goal nil)) ; then info corrent
))))))))))


Top
  Profile  
 
 Post subject: Re: I have a LISP II - The Farmer, Fox, Goose, and Grain
PostPosted: Mon Feb 18, 2008 6:30 pm 
Bitchin' Fast 3D Z8000*
Bitchin' Fast 3D Z8000*
User avatar

Joined: Tue Jun 29, 2004 11:32 pm
Posts: 2555
Location: Somewhere between compilation and linking
CrashTECH wrote:
So... I have pretty much figured out this solution, and I am representing it by a n-bit number, giving 2^n=16 states.

Assuming n = 4, sure. =)

CrashTECH wrote:
I know HOW to solve it, but we need to take the state space (Which I built, but I am not 100% sure it is correct) and search it with some generic blind search...

I love how the first path finding exercise in almost every AI class requires you to expand the entire state-space then search it. Obviously, you won't want to do this in real life... you search as you're expanding the space... but anyways.

Let's make things simple and use an adjacency matrix to represent the graph. It will have 16 rows and 16 cols with Mij = 0 if it isn't possible to go from state i to state j and Mij = 1 if it is possible to go from state i to state j. Keeping with the bit representation, the starting state is 0000 and the goal state is 1111. Simply use a for-each row, for-each col nested loop to fill in the matrix for this graph.

Obviously, it isn't possible to go from 0000 to 0001 - 0111. The farmer has to be on the boat. Also, you don't want to leave the fox and goose OR the goose and grain on the same side. However, these probably shouldn't be eliminated from the search space... go with your teachers instructions on this one. After 16^2 calculations, you'll have created the search-space.

CrashTECH wrote:
So, I have the following functions written already, but I am totally lost with the path-search portion of it. I have some "pseudocode" for that, but I am not sure how to do it.....

Based on the pseudo-code, you were supposed to perform a DFS. Pretty basic... sounds like you need to spend some time working on TopCoder problems. =)

What part was screwing you up?


Top
  Profile  
 
 Post subject:
PostPosted: Mon Feb 18, 2008 6:45 pm 
SON OF A GUN
SON OF A GUN
User avatar

Joined: Mon Nov 01, 2004 5:41 am
Posts: 11605
For this problem, n is 4 :)

Just writing it in LISP mostly. I have never seen the language, and tbh, I am a bit lost on it. Not to mention I went to go buy a book over the weekend and neither Borders nor Barns and Noble had one in stock....

The guy is kind of impossible though, he is very vague with what he wants but he wants our solutions to be super descriptive and detailed. I could write a DFS search, that isn't the issue...

The issue I was having, apart from trying to decipher what he actually wanted, was coming up with a way to take the state, no matter which one, and generate it's possible child states (there aren't many) and then recall it. So I basically needed to build the "tree" and then search it.

Here is a bit from the project assignment:
Quote:
Define a function, called path, to implement the search algorithm. The function path should take as arguments a state and a goal and first check to see whether they are equal, indicating a successful termination of the search. If they are not equal, path should generate all four of the neighboring states in the state space graph, calling itself recursively on each of these neighboring states in turn to try to find a path from them to a goal. Note that you need to make sure path does not get stuck in a loop (visits a certain state more than once).

Now, if you actually look at the state-space, there aren't any valid states where there are 4 children... there is actually only one state, that has 2 children and the rest have 1, it is a pretty simple graph imo... however, if we included all the possible states, I am not sure there would be ONLY 4 moves if you included everything, there in lies the problem...

So really, I wasted too much time trying to figure out what he wanted, rather than just solving the problem, so I ran out of time to actually do it. Then it also boils down to not having any familiarity with LISP. If this was C/C++/C# etc I could have done it and the report in a couple of hours...


Top
  Profile  
 
 Post subject:
PostPosted: Mon Feb 18, 2008 7:25 pm 
Bitchin' Fast 3D Z8000*
Bitchin' Fast 3D Z8000*
User avatar

Joined: Tue Jun 29, 2004 11:32 pm
Posts: 2555
Location: Somewhere between compilation and linking
CrashTECH wrote:
Here is a bit from the project assignment:
Quote:
Define a function, called path, to implement the search algorithm. The function path should take as arguments a state and a goal and first check to see whether they are equal, indicating a successful termination of the search. If they are not equal, path should generate all four of the neighboring states in the state space graph, calling itself recursively on each of these neighboring states in turn to try to find a path from them to a goal. Note that you need to make sure path does not get stuck in a loop (visits a certain state more than once).

Now, if you actually look at the state-space, there aren't any valid states where there are 4 children...

True. You were supposed to determine that as you went along. Be careful with the language (AI and algorithm classes speak slightly different dialects!). By four neighbors, I believe he was referring to the branching factor for the problem which is four: farmer, farmer&fox, farmer&goose, farmer&grain. You were supposed to try all four possibilities from every state and then check to see if it was valid. Live and learn I suppose...


Top
  Profile  
 
 Post subject:
PostPosted: Mon Feb 18, 2008 7:37 pm 
SON OF A GUN
SON OF A GUN
User avatar

Joined: Mon Nov 01, 2004 5:41 am
Posts: 11605
Somebody asked him, and even came back and said that it wasn't four, so we have no idea what he was originally talking about.

On our HW, he decided to tell me that I didn't understand A*, when in fact, I think I do. Seeing as it is how we handled movement in our game for senior design. I think the guy has a power/ego issue and is just exercising it. However, this is less about the a actual project..

Project 4 is to code A*. So we will see how that goes :)


Top
  Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 6 posts ] 

All times are UTC - 8 hours


Who is online

Users browsing this forum: No registered users and 1 guest


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group