Programming C, C++, Java, PHP, Ruby, Turing, VB
Computer Science Canada 
Programming C, C++, Java, PHP, Ruby, Turing, VB  

Username:   Password: 
 RegisterRegister   
 Rush Hour Project
Index -> General Programming
Goto page 1, 2  Next
View previous topic Printable versionDownload TopicSubscribe to this topicPrivate MessagesRefresh page View next topic
Author Message
Panphobia




PostPosted: Wed Dec 05, 2012 10:52 am   Post subject: Rush Hour Project

For my final project in grade 12 programming, we have to have a group project, and my group wanted to do the Rush Hour game, which is basically, where you are a car, and you have to move other cars so you can get to your destination. We have to create the shortest number of moves for the differentiation between easy,medium,and hard. Which algorithm should I use, would a BFS be ok?
Sponsor
Sponsor
Sponsor
sponsor
Raknarg




PostPosted: Wed Dec 05, 2012 5:31 pm   Post subject: RE:Rush Hour Project

In this situation, I would venture to say no... It seems like something that would take way too much recursion. Any disagreements? I'm just judging on first glance here
Insectoid




PostPosted: Wed Dec 05, 2012 6:57 pm   Post subject: RE:Rush Hour Project

I don't think there's so many moves on a Rush Hour board that you couldn't use recursion. It's only a 6x6 grid. There are only 16 vehicles. Vehicle data shouldn't be more than a few bytes each in a basic implementation (type, location, orientation) so it's not like you're going to run out of RAM.
Panphobia




PostPosted: Wed Dec 05, 2012 7:24 pm   Post subject: RE:Rush Hour Project

Basically for this project we are supposed to use everything we learned in grade 12, so recursion, object orientation, arraylists etc, so with recursion, should I check for the shortest path between the car and the end, and if there is a car in the way, to move the car, and recurse my way until i get the minimum amount of moves?
Panphobia




PostPosted: Thu Dec 06, 2012 12:39 am   Post subject: RE:Rush Hour Project

It seems that recursion would be kind of inefficient. Would it not?
Insectoid




PostPosted: Thu Dec 06, 2012 8:50 am   Post subject: RE:Rush Hour Project

It's probably less efficient than a more intelligent algorithm, but a more intelligent algorithm would be harder to write and would require you to study the game itself for a bit. The number of moves really is very small. Trucks have six valid moves each (three backward/three forward) and cars have eight. There are only 120 valid moves total, but that's without any obstructions. Of course, you can't fit all vehicles on the table simultaneously because they would take up all 36 squares, for 0 moves each. Considering that a vehicle is likely blocked by another and may have all, some, or no valid moves, the tree becomes much smaller. The program shouldn't take more than a few seconds to run at worst, and should be apparently instant at best.
mirhagk




PostPosted: Thu Dec 06, 2012 3:32 pm   Post subject: RE:Rush Hour Project

BFS traditionally uses a queue, not a stack, and therefore is usually only implemented recursively if the language is extremely high level and nearly forces recursion (like haskell).

You could make the while loop recursive, but it'd just increase memory consumption and time (unless the language has tail recursion and you optimize for that).

Essentially the point is BFS should not be done recursively (but requires the same sort of knowledge, and therefore should be easy to convince the teacher that the knowledge is transferable).

See here for more info:
http://stackoverflow.com/questions/2549541/performing-breadth-first-search-recursively
Panphobia




PostPosted: Thu Dec 06, 2012 3:59 pm   Post subject: RE:Rush Hour Project

So I can use an arraylist for the BFS, and I can say that it can be done recursively but is less efficient? But the arraylist will work as a queue so that will knock two of the criteria down?
Sponsor
Sponsor
Sponsor
sponsor
mirhagk




PostPosted: Thu Dec 06, 2012 6:07 pm   Post subject: RE:Rush Hour Project

the arraylist solution actually only works with a binary tree (which you won't have).

Just do a regular BFS, and then convert the while loop to a recursive loop
code:

BFS()
{
while(true)
{
  doWork
  if(done)
    return
}
}

Becomes
code:

BFS(localVars)
{
  doWork
  if (done)
    return
  BFS(localVars)
}

You need to pass in all the local variables as parameters (pass the queue as a reference so you don't need to copy it). Any loop can trivially be turned into a recursive function like that. Then spend the rest of your time making sure you fully comprehend BFS and the queue it uses.
Panphobia




PostPosted: Thu Dec 06, 2012 6:26 pm   Post subject: RE:Rush Hour Project

What I mean by using ArrayList is like when you dequeue you just (arraylist).remove(0), which gives the same effect right?
mirhagk




PostPosted: Thu Dec 06, 2012 11:49 pm   Post subject: RE:Rush Hour Project

oh yeah sorry, so long as you're using a queue interface that works.
Panphobia




PostPosted: Thu Dec 06, 2012 11:57 pm   Post subject: RE:Rush Hour Project

yea, now if a bfs is a good way to go, would i use the bfs to move the cars or to check if you can make it to the exit without obstruction, or both?
AntoxicatedDevil78




PostPosted: Fri Dec 07, 2012 11:03 am   Post subject: RE:Rush Hour Project

Deos grade 12 programming contain Gaming
Panphobia




PostPosted: Fri Dec 07, 2012 11:24 am   Post subject: RE:Rush Hour Project

Well for the final project, you can make a game, but it has to do with project management, so a group with 3 people, and make a program that uses everything in the curriculum
Insectoid




PostPosted: Fri Dec 07, 2012 3:48 pm   Post subject: RE:Rush Hour Project

@AntoxicatedDevil78- don't spam threads with unrelated comments. If you'd like to know what 12th grade compsci involves, ask in the appropriate forum (Student Life).
Display posts from previous:   
   Index -> General Programming
View previous topic Tell A FriendPrintable versionDownload TopicSubscribe to this topicPrivate MessagesRefresh page View next topic

Page 1 of 2  [ 23 Posts ]
Goto page 1, 2  Next
Jump to:   


Style:  
Search: