473,320 Members | 1,979 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,320 software developers and data experts.

HashSet confusion

3
Hi all, I'm writing a program to solve sliding block puzzles like these and while I think I've more or less figured it out, I have one problem before I start coding it.

During execution, the program will take the possible moves that can be performed on an board position, perform them, and add the new boards to a HashSet if they aren't in there already until a board that satisifies a solution is found. The trouble is I've never used a HashSet before so I'm not exactly sure how to go about this. Now with HashMaps, when you're putting something in it you clearly pass it a key and a value, but looking at HashSet on the API, you just pass it one object. So, what do you do when adding something to a HashSet? I plan on having it so a move in the HashSet will be a key to the board it generates. What would my HashSet.add() call look like?

Also, when I'm retrieving the solution I'm going to need the series of moves taken to arrive at it... this is also a bit confusing. I'm not entirely sure, but I think I would do this by looking at the key to the solution, but the problem is how do I go from that key (move) to the value (board) that it was executed on? I.e. how do I work my way backwards? Please, if you can help with this, only tell me in pseudo-code or English, I wouldn't want to commit any academic offenses.

Thanks much!
Dec 3 '07 #1
5 1294
JosAH
11,448 Expert 8TB
If you want a board configuration to be the key in a Map, and all the possible
moves to be the values of that entry, I'd say that you encode a board position.
The possible moves can be implemented as a Set of other board positions.

As a first thought (given the board position in your link), I'd say you can encode
that board position as follows:

Expand|Select|Wrap|Line Numbers
  1. 2 4 4 2
  2. 2 4 4 2 
  3. 2 3 3 2
  4. 2 1 1 2
  5. 1 0 0 1
  6.  
Consider this a number in radix 5 and do the (simple) math. A board configuration
ends up as a number with a list of numbers as the possible moves given that number.

Can you take it from there?

kind regards,

Jos

ps. Use a HashMap instead of a HashTable; it's more 'en vogue'.
Dec 3 '07 #2
BaronB
3
First, let me say thank you for the response :) Though those aren't actually my problems.

From the starting code for the assignment, trays will be encoded into 2-d arrays of integers, where each value at a row/col will be either -1 for empty or the id of an instance of Block in the tray. Mea culpa for not mentioning that in the OP. There's already a possibleMoves method too, which returns a SortedSet of instances of the class Move.

My problem is with adding things to a HashSet and then retrieving them. It makes me feel very stupid but I just can't grasp how I can add keys and values to a HashSet, and then later use them and retrieve a path of boards leading to moves. The code for finding a solution will look broadly like this

Expand|Select|Wrap|Line Numbers
  1. boolean foundSolution = false;
  2.   Iterator moves = bp.moveIterator();
  3.   while(moves.hasNext()){
  4.     Move m = (Move) moves.next();
  5.     newbp = bp.makeMove(m);
  6.     if(!positionSet.contains(newbp)){
  7.       positionSet.add(newbp);
  8.       boardPosition.add(newbp);
  9.     }
  10.     if(bp.solvedState()) {foundSolution = true; break;}
  11.   }
  12.   return foundSolution;
  13.  
It's retrieving the actual path to the solution that is the biggest issue. I can't quite think how to do it - working backwards from the solution -> move that begot the solution -> board that move was applied to -> the move that made that board -> etc etc etc all the way back to the intial configuration seems like the easiest way but I don't know how to make that work with a HashSet.

Thank you again and my apologies for inadvertently omitting relevant information from the OP.
Dec 3 '07 #3
JosAH
11,448 Expert 8TB
You're mixing up two disjunct problems:

1) how to find a solution to the puzzle
2) (much simpler) how to use a board configuration as a key to a Map.

I just answered 2) now what is your problem?

kind regards,

Jos
Dec 3 '07 #4
BaronB
3
Er, ok, I guess I am. Well I suppose my problem is that I don't know how I could keep track of the moves that eventually lead to the solution when actually trying all the possible moves. I don't suppose a nudge in the right direction would be out of the question / morally unacceptable?

Thanks
Dec 3 '07 #5
JosAH
11,448 Expert 8TB
Er, ok, I guess I am. Well I suppose my problem is that I don't know how I could keep track of the moves that eventually lead to the solution when actually trying all the possible moves. I don't suppose a nudge in the right direction would be out of the question / morally unacceptable?

Thanks
For every possible board configuration you have to keep track of 'where it came from',
i.e. the board configuration before you made the move. Basically you're building a
tree of board configurations on the nodes and the moves on the edges; remembering
where the board configuration 'came from' is a pointer pointing upwards to the root:
it points to the parent node.

kind regards,

Jos
Dec 4 '07 #6

Sign in to post your reply or Sign up for a free account.

Similar topics

1
by: Doug Farrell | last post by:
Hi all, I'm trying to do the following from within a code module: import re # text to match text = "Good morning x something /x, how are you today x something else /x"
4
by: JMCN | last post by:
object invalid or no longer set - confusion of the recordset in access 2003. i am currently converting from access 97 to access 2003. majority of the codes converted over perfectly fine, though...
0
by: i_have_control | last post by:
I'd be grateful for any input on this one: I have three web domains. The destinations of two are set to folders on the first, though that fact is transparent to the user (i.e: it does not...
13
by: Steve | last post by:
I have a form with a dataset and a datagrid. I created a dataview on this dataset. When the user modifies the datagrid, I look up this record in the dataview to make sure it is unique. Here is...
10
by: joelagnel | last post by:
hi friends, i've been having this confusion for about a year, i want to know the exact difference between text and binary files. using the fwrite function in c, i wrote 2 bytes of integers in...
1
by: Richard Lewis Haggard | last post by:
I'm having a problem with what appears to be some sort of confusion with references. I have a single solution with a dozen projects which has been working quite nicely for a while. The references...
2
by: Riaaaa | last post by:
Hello, We are doing the project in VB.Net. We had a great confusion for ASP.Net and VB.Net. Is VB.Net project performed in Microsoft Visual Studio 2005 ?? We have...
2
by: puzzlecracker | last post by:
is there a comparable class to HashSet (java's) in csharp? Thanks
8
mickey0
by: mickey0 | last post by:
Hello, I'm new to java and my problem is this: class Word { private String _value; public Word(String value) { _value = new String(value); } } //main
0
by: DolphinDB | last post by:
The formulas of 101 quantitative trading alphas used by WorldQuant were presented in the paper 101 Formulaic Alphas. However, some formulas are complex, leading to challenges in calculation. Take...
0
by: DolphinDB | last post by:
Tired of spending countless mintues downsampling your data? Look no further! In this article, you’ll learn how to efficiently downsample 6.48 billion high-frequency records to 61 million...
0
by: ryjfgjl | last post by:
ExcelToDatabase: batch import excel into database automatically...
0
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
1
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
0
by: jfyes | last post by:
As a hardware engineer, after seeing that CEIWEI recently released a new tool for Modbus RTU Over TCP/UDP filtering and monitoring, I actively went to its official website to take a look. It turned...
0
by: ArrayDB | last post by:
The error message I've encountered is; ERROR:root:Error generating model response: exception: access violation writing 0x0000000000005140, which seems to be indicative of an access violation...
1
by: Shællîpôpï 09 | last post by:
If u are using a keypad phone, how do u turn on JavaScript, to access features like WhatsApp, Facebook, Instagram....
0
by: af34tf | last post by:
Hi Guys, I have a domain whose name is BytesLimited.com, and I want to sell it. Does anyone know about platforms that allow me to list my domain in auction for free. Thank you

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.