Results 1 to 13 of 13

Thread: SudokuSet

  1. #1
    Lil_Aziz1's Avatar
    Lil_Aziz1 is offline Senior Member
    Join Date
    Dec 2009
    Location
    United States
    Posts
    343
    Rep Power
    5

    Default SudokuSet

    I'm thinking about completely changing my sudoku solver. The program logically solves the sudoku puzzle; consequently, the method contains(), remove(), and get() methods are used innumerable times (mostly contains()). After reading up on Sets, I decided I wanted the sudoku grid to be a HashSet<Integer>[][] instead of an ArrayList<Integer>[][] because of the efficiency of contains() and remove(); however, there is a problem with using HashSets: there is no get(int index) method. I frequently need to get the only element in the ArrayList or iterate over all the elements.

    I decided to make a class called SudokuSet that extends HashSet that will be implemented instead of just HashSet. I made two different implementations and I was wondering if anyone could tell me which one is the most efficient. If neither of em are efficient, can you tell me a better concept? Here are the two implementations:

    Java Code:
    package sudokuUpdateToSets;
    import java.util.HashSet;
    /**
     * @param <E> Generic because a 3D list of SudokuSet will be needed. 
     * 		E.g: SudokuSet<SudokuSet<SudokuSet<Integer>>>
     */
    public class SudokuSet<E> extends HashSet<E> {
    	
    	private E[] list;
    	private int size;
    	
    	public SudokuSet() {
    		super(10,1);
    		list = (E[]) new Object[9];
    		size = 0;
    	}
    	@Override
    	public boolean remove(Object o) {
    		if (contains(o)) {
    			updateList();
    			size--;
    		}
    		return super.remove(o);
    	}
    	@Override
    	public boolean add(E o)  {
    		list[size++] = o;
    		return super.add(o);
    	}
    	
    	public E get(int index) {
    		return list[index];
    	}
    	
    	private void updateList() {
    		list = (E[]) this.toArray();
    	}
    }
    Java Code:
    package sudokuUpdateToSets;
    import java.util.ArrayList;
    import java.util.HashSet;
    
    public class SudokuSet1<E> extends HashSet<E> {
    	
    	private ArrayList<E> hiddenList;
    	
    	public SudokuSet1() {
    		super(10,1);
    		hiddenList = new ArrayList<E>();
    	}
    	@Override
    	public boolean add(E o)  {
    		hiddenList.add(o);
    		return super.add(o);
    	}
    	@Override
    	public boolean remove(Object o) {
    		hiddenList.remove(o);
    		return super.remove(o);
    	}
    	
    	public E get(int index) {
    		return hiddenList.get(index);
    	}
    }
    Thanks in advance!
    Last edited by Lil_Aziz1; 07-25-2010 at 10:42 PM.
    "Experience is what you get when you don't get what you want" (Dan Stanford)
    "Rise and rise again until lambs become lions" (Robin Hood)

  2. #2
    Norm's Avatar
    Norm is offline Moderator
    Join Date
    Jun 2008
    Location
    SW Missouri
    Posts
    17,306
    Rep Power
    25

    Default

    I decided I wanted the sudoku grid to be a HashSet<Integer>[][] instead of an ArrayList<Integer>[][]
    Can you explain this decision?
    If you need a get(index) method, then HashSet won't work.

  3. #3
    Lil_Aziz1's Avatar
    Lil_Aziz1 is offline Senior Member
    Join Date
    Dec 2009
    Location
    United States
    Posts
    343
    Rep Power
    5

    Default

    Because I would like the method contains() to be O(1). Remove and get as well if possible.

    Oh sorry. I meant I want to implement SudokuSet<Integer>[][].
    "Experience is what you get when you don't get what you want" (Dan Stanford)
    "Rise and rise again until lambs become lions" (Robin Hood)

  4. #4
    Norm's Avatar
    Norm is offline Moderator
    Join Date
    Jun 2008
    Location
    SW Missouri
    Posts
    17,306
    Rep Power
    25

    Default

    I would like the method contains() to be O(1). Remove and get as well if possible.
    Sorry, O(1) has no meaning for me.
    And what does "Remove and get as well" mean?

    I guess I don't understand any of your answer.

    I was looking for something like this:
    I chose HashSet over ArrayList because HashSet allows me to .... and ArrayList does not.
    Or HashSet is more efficient when I ... and ArrayList is too slow.

  5. #5
    Fubarable's Avatar
    Fubarable is offline Moderator
    Join Date
    Jun 2008
    Posts
    19,316
    Blog Entries
    1
    Rep Power
    26

  6. #6
    Lil_Aziz1's Avatar
    Lil_Aziz1 is offline Senior Member
    Join Date
    Dec 2009
    Location
    United States
    Posts
    343
    Rep Power
    5

    Default

    Um okay I'm sorry if I'm not explicit enough for you.

    HashSet is more efficient when it comes to the method contains() and remove().

    I don't know about LinkedHashSets. Only reason I would use LinkedHashSet is when I want the order of a list to be retained, but HashSet already does that for me when it comes to Integer.
    "Experience is what you get when you don't get what you want" (Dan Stanford)
    "Rise and rise again until lambs become lions" (Robin Hood)

  7. #7
    Norm's Avatar
    Norm is offline Moderator
    Join Date
    Jun 2008
    Location
    SW Missouri
    Posts
    17,306
    Rep Power
    25

    Default

    HashMap has a get() method. Have the key be the index's value.

  8. #8
    Lil_Aziz1's Avatar
    Lil_Aziz1 is offline Senior Member
    Join Date
    Dec 2009
    Location
    United States
    Posts
    343
    Rep Power
    5

    Default

    Wouldn't I have to relocate all values if I remove an element from the Map? Let's say I have the following HashMap:

    {0=2, 1=4, 2=7, 3=9}

    and I do something like
    Java Code:
    map.remove(0)
    The list now looks like:
    {1=4, 2=7, 3=9}

    Pretty perceptive idea. Didn't think about using a Map and having the keys as indexes. It uses less space and I would only have to override the remove() method.

    EDIT: I edited my first implementation of SudokuSet, but I'm getting a yellow line under
    Java Code:
    list = (E[]) this.toArray();
    //and
    list = (E[]) new Object[9];
    How can I fix that? I probably won't use this implementation, but I would still like to know how to fix this.
    Last edited by Lil_Aziz1; 07-25-2010 at 10:53 PM.
    "Experience is what you get when you don't get what you want" (Dan Stanford)
    "Rise and rise again until lambs become lions" (Robin Hood)

  9. #9
    Norm's Avatar
    Norm is offline Moderator
    Join Date
    Jun 2008
    Location
    SW Missouri
    Posts
    17,306
    Rep Power
    25

    Default

    What did you change in the edit?
    What is the type of the list variable? What is the compiler error when you compile it?

  10. #10
    Lil_Aziz1's Avatar
    Lil_Aziz1 is offline Senior Member
    Join Date
    Dec 2009
    Location
    United States
    Posts
    343
    Rep Power
    5

    Default

    I made it so the method this.toArray(); is called less frequently. The type of the list variable can be either Integer or itself, SudokuSet.

    Yellow line means it's not recommended. It is not a compilation error. Here is what appears when I hover over the text in yellow lines:

    Type safety: Unchecked cast from Object[] to E[]

    Also, my initial question is still unanswered. :( Which SudokuSet should I implement? Or should I make a third implementation that extends HashMap and overrides the remove() method.
    "Experience is what you get when you don't get what you want" (Dan Stanford)
    "Rise and rise again until lambs become lions" (Robin Hood)

  11. #11
    Norm's Avatar
    Norm is offline Moderator
    Join Date
    Jun 2008
    Location
    SW Missouri
    Posts
    17,306
    Rep Power
    25

    Default

    The decision is based on what are the program requirements.
    Where do you need the efficiency or functionality?
    How often is get() used with it requiring a toArray() call. Perhaps you could have a changed flag and if the contents hasn't changed reuse the generated array.

  12. #12
    Lil_Aziz1's Avatar
    Lil_Aziz1 is offline Senior Member
    Join Date
    Dec 2009
    Location
    United States
    Posts
    343
    Rep Power
    5

    Default

    The most prevalent method is contains(). Next is get() and lastly remove(). You could say remove() is infinitesimal compared to the number of times contains() is used.

    Changed flag? I think I did that in my first implementation.
    "Experience is what you get when you don't get what you want" (Dan Stanford)
    "Rise and rise again until lambs become lions" (Robin Hood)

  13. #13
    Norm's Avatar
    Norm is offline Moderator
    Join Date
    Jun 2008
    Location
    SW Missouri
    Posts
    17,306
    Rep Power
    25

    Default

    Can you explain your algorithm?
    What is it you're putting into the collection and testing for contains?
    A 9 element group of digits (1-9)?
    And why three dimensions?

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •