Programming Forums
Page 1 of 2 1 2 >
Show 40 post(s) from this thread on one page

Programming Forums (http://www.programmingforums.org/forumindex.php)
-   Java (http://www.programmingforums.org/forum17.html)
-   -   can someone please help me with this tree (http://www.programmingforums.org/showthread.php?t=13993)

cwl157 Sep 19th, 2007 7:27 PM
can someone please help me with this tree
 
Ok, so i need to make a tree where each node is a 2d array and it can have possibly 4 children per node. Each 2d array has 1 blank spot represented by 0. This blank can move either, left, up, right, down in that order, thats where the 4 children come from. It finds the first set of children fine, in fact it even finds the goal fine, if the goal is among the first set of children. If the goal is not among the first set of children it goes into an infinite loop because it keeps producing the same 4 children over and over again. I think its something with how it saves the children, i think it might over write them or something, im not sure but i have until tomorrow at noon to have this done and i am close, i think. All i am missing is the recursive step that is needed to produce the next layers of children. I also need to keep track of a function f(n) and state that has the lowest f(n) is the state that i produce its children. The children are checked to see if they are the goal right when they are produced. F(n) is simply the level of the tree i am on plus the number of ints in the 2d array that the current state has that are different from the goal state. So while im going through this tree making children i need to keep track of the level, i actually think i do that correctly but can not make the chidlren correctly, again i think because of the way java references objects or something. I know i've asked a few questions related to this without telling what the whole thing is, mainly out of laziness. But anyway here are the 2 classes that i am using. The GridNode clas contains the 2d array and all the methods to manipulate it. The other class has main as well as the methods that go up and down the tree. Its pretty sloppy because i only have a little bit of time to finish it so ive just been doing whatever i can to try and figure it out. If anyone can tell me what i need to do i would appreciate it. Thanks,

:
import java.io.*;
public class GridNode
{
  private int[][] state;
  private GridNode leftChild;
  private GridNode upChild;
  private GridNode rightChild;
  private GridNode downChild;
  private int level;
  private int f;
  private int h;
 
  // set state to newState and firstChild to newFirstChild and nextSibling to newNextSibling
  public GridNode(int[][] newState, GridNode newLeftChild, GridNode newUpChild, GridNode newRightChild, GridNode newDownChild)
  {
      setState(newState);
      setLeftChild(newLeftChild);
      setUpChild(newUpChild);
      setRightChild(newRightChild);
      setDownChild(newDownChild);
  } // end GridNode constructor
 
  // empty constructor
  public GridNode()
  {
  }
 
  // copy one state to another
  public static int[][] copy(int[][] a)
  {
      int[][] b = new int[a[0].length][a.length];
      for (int i = 0; i < a.length; i++)
          for (int j = 0; j < a[0].length; j++)
              b[i][j] = a[i][j];
   
      return b;
} // end copy
 
  public int getLevel()
  {
      return level;
  } // end getLevel
 
  public int getF()
  {
      return f;
  } // end getF
 
  public int getH()
  {
      return h;
  } // end getH
 
  public void setLevel(int newLevel)
  {
      level = newLevel;
  } // end setLevel
 
  public void setF(int newF)
  {
      f = newF;
  } // end setF
 
  public void setH(int newH)
  {
      h = newH;
  } // end setH
 
  public static GridNode copy(GridNode a)
  {
      GridNode b = a;
      return b;
  } // end copy
 
  // get current state
  public int[][] getState()
  {
      return state;
  } // end getState
 
  public void setState(int[][] newState)
  {
      state = newState;
  } // end setState
 
  // set leftChild
  public void setLeftChild(GridNode newLeftChild)
  {
      leftChild = newLeftChild;
  } // end setLeftChild
 
  // set UpChild
  public void setUpChild(GridNode newUpChild)
  {
      upChild = newUpChild;
  } // end setUpChild
 
  // set right child
  public void setRightChild(GridNode newRightChild)
  {
      rightChild = newRightChild;
  } // end setRightChild
 
  // set down child
  public void setDownChild(GridNode newDownChild)
  {
      downChild = newDownChild;
  } // end setDownChild;
 
  // get leftChild
  public GridNode getLeftChild()
  {
      return leftChild;
  } // end getLeftCHild
 
  // getUpChild
  public GridNode getUpChild()
  {
      return upChild;
  } // end getUpChild
 
  // get right child
  public GridNode getRightChild()
  {
      return rightChild;
  } // getRightChild;
 
  public GridNode getDownChild()
  {
      return downChild;
  } // end getDownChild
 
  // print the current state
  public void printNode()
  {
      for(int row = 0; row < 3; row++)
      {
        for(int col = 0; col < 3; col++)
          System.out.print(state[row][col] + "  ");
       
        System.out.println();
      } // end for
    } // end printNode
 
  // check to see if current state is equal to the goal state
  public boolean isEqual(int[][] state, int[][] goalState)
  {
      for (int row = 0; row < 3; row++)
      {
        for (int col = 0; col < 3; col++)
        {
            if (state[row][col] == goalState[row][col])
              continue;
           
            else
            return false;
        } // end for
      }  // end for
      return true;
  } // end isEqual
 
  // calculates h1(n)
  public int findHone(int[][] state, int[][] goalState)
  {
      int hOne = 0;
      for (int row = 0; row < 3; row++)
      {
        for (int col = 0; col < 3; col++)
        {
            if (state[row][col] != goalState[row][col] && state[row][col] != 0)
              hOne++;
           
            else
            continue;
        } // end for
      }  // end for
      return hOne;
  } // end findHone
 
  // find f(n) = g(n) + h(n)
  public int findF(int g, int h)
  {
      return g + h;
  } // end findF
 
  // check to see if it can move left
  public boolean canMoveLeft(int[][] state)
  {
      int tempPos = -1;
      for (int row = 0; row < 3; row++)
      {
        for (int col = 0; col < 3; col++)
        {
            if (state[row][col] == 0)
                tempPos = col;
        } // end for
      } // end for
     
      if (tempPos == 0)
        return false;
      else
      return true;
  } // end canMoveLeft
 
  // check to see if it can move up
  public boolean canMoveUp(int[][] state)
  {
      int tempPos = -1;
      for (int row = 0; row < 3; row++)
      {
        for (int col = 0; col < 3; col++)
        {
            if (state[row][col] == 0)
                tempPos = row;
        } // end for
      } // end for
     
      if (tempPos == 0)
        return false;
      else
      return true;
  } // end canMoveUp
 
  // check to see if it can move right
  public boolean canMoveRight(int[][] state)
  {
      int tempPos = -1;
      for (int row = 0; row < 3; row++)
      {
        for (int col = 0; col < 3; col++)
        {
            if (state[row][col] == 0)
                tempPos = col;
        } // end for
      } // end for
     
      if (tempPos == 2)
        return false;
      else
      return true;
  } // end canMoveRight
 
  // check to see if it can move down
  public boolean canMoveDown(int[][] state)
  {
      int tempPos = -1;
      for (int row = 0; row < 3; row++)
      {
        for (int col = 0; col < 3; col++)
        {
            if (state[row][col] == 0)
                tempPos = row;
        } // end for
      } // end for
     
      if (tempPos == 2)
        return false;
      else
      return true;
  } // end canMoveDown
 
    // move it left, the old one
  public void moveLeft(int[][] state)
  {
      for (int row = 0; row < 3; row++)
      {
        for (int col = 0; col < 3; col++)
        {
            if (state[row][col] == 0)
            {
                  state[row][col] = state[row][col-1];
                  state[row][col-1] = 0;
                  //printNode();
                  return;
            } // end if
        } // end for
      } // end for
  } // end moveLeft
 
 
  // move it Up
  public void moveUp(int[][] state)
  {
      for (int row = 0; row < 3; row++)
      {
        for (int col = 0; col < 3; col++)
        {
            if (state[row][col] == 0)
            {
                  state[row][col] = state[row-1][col];
                  state[row-1][col] = 0;
                // printNode(state);
                  return;
            } // end if
        } // end for
      } // end for
  } // end moveUp
 
    // move it right
  public void moveRight(int[][] state)
  {
      for (int row = 0; row < 3; row++)
      {
        for (int col = 0; col < 3; col++)
        {
            if (state[row][col] == 0)
            {
                  state[row][col] = state[row][col+1];
                  state[row][col+1] = 0;
                  // printNode(state);
                  return;
            } // end if
        } // end for
      } // end for
  } // end moveRight
 
    // move it down
  public void moveDown(int[][] state)
  {
      //int tempPos = -1;
      for (int row = 0; row < 3; row++)
      {
        for (int col = 0; col < 3; col++)
        {
            if (state[row][col] == 0)
            {
                state[row][col] = state[row+1][col];
                state[row+1][col] = 0;
                // printNode(state);
                return;
            } // end if
        } // end for
      } // end for
  } // end moveDown
 
} // end GridNode

:
import java.util.*;
public class NewMain
{
  private static int level;
  private static List tree = new LinkedList();
 
  private static int[][] goalState = {{7, 2, 6},
                                      {8, 0, 4},
                                      {1, 5, 3}
                                      };
 
 
      static int[][] initialState = {{7, 6, 4},
                            {8, 5, 2},
                            {1, 0, 3}
                            };
 
  // insert root and check if its goal
  static void insertRoot(GridNode root)
  {
    tree.add(0, root);
  } // end insertRoot
 
  // return node with the smallest f(n)
  static GridNode findF(List tree, int level)
  {
      GridNode temp;
      int lowestF = 200;
      int tempLowestF = 200;
      int tempLowestH = 200;
      int i = 0;
      int tempI = 0;
     
      while (i < tree.size())
      {
        temp = (GridNode) tree.get(i);
        tempLowestH = temp.findHone(temp.getState(), goalState);
        tempLowestF = level + tempLowestH;
         
        if (tempLowestF < lowestF)
        {
          lowestF = tempLowestF;
          tempI = i;
        } // end if
        i++;
      } // end while
      return (GridNode) tree.get(tempI);
  } // end findF
 
  // insert children
  static void insertChild(GridNode parent, GridNode child)
  {
        if (parent.canMoveLeft(parent.getState()))
        {
          child.setState(parent.copy(parent.getState()));
          child.moveLeft(child.getState());
         
          if (child.isEqual(child.getState(), goalState))
          {
              child.printNode();
              return;
          } // end if
         
          tree.add(child);
          parent.setLeftChild(child);
          System.out.println("The child is");
          child.printNode();
          System.out.println();
          //System.out.println("the parent is");
          //parent.printNode();
          level++;
         
          if (parent.canMoveUp(parent.getState()))
          {
              child.setState(parent.copy(parent.getState()));
              child.moveUp(child.getState());
             
              if (child.isEqual(child.getState(), goalState))
              {
                child.printNode();
                return;
              } // end if
             
              tree.add(child);
              parent.setUpChild(child);
              System.out.println("The child is");
              child.printNode();
              System.out.println();
              //System.out.println("the parent is");
              //parent.printNode();
          } // end if
         
          if (parent.canMoveRight(parent.getState()))
          {
              child.setState(parent.copy(parent.getState()));
              child.moveRight(child.getState());
             
              if (child.isEqual(child.getState(), goalState))
              {
                child.printNode();
                return;
              } // end if
             
              tree.add(child);
              parent.setRightChild(child);
              System.out.println("The child is");
              child.printNode();
              System.out.println();
              //System.out.println("the parent is");
              //parent.printNode();
          } // end if
         
          if (parent.canMoveDown(parent.getState()))
          {
              child.setState(parent.copy(parent.getState()));
              child.moveDown(child.getState());
             
              if (child.isEqual(child.getState(), goalState))
              {
                child.printNode();
                return;
              } // end if
             
              tree.add(child);
              parent.setDownChild(child);
              System.out.println("The child is");
              child.printNode();
              System.out.println();
            // System.out.println("the parent is");
              //parent.printNode();
          } // end if
        }  // end if
     
     
        else  if (parent.canMoveUp(parent.getState()))
        {
          child.setState(parent.copy(parent.getState()));
          child.moveUp(child.getState());
         
          if (child.isEqual(child.getState(), goalState))
          {
                child.printNode();
                return;
          } // end if
         
          tree.add(child);
          parent.setUpChild(child);
          parent.setUpChild(parent.copy(child));
          System.out.println("The child is");
          child.printNode();
          System.out.println();
          //System.out.println("the parent is");
          //parent.printNode();
          level++;
         
          if (parent.canMoveRight(parent.getState()))
          {
                child.setState(parent.copy(parent.getState()));
                child.moveRight(child.getState());
               
                if (child.isEqual(child.getState(), goalState))
                {
                  child.printNode();
                  return;
                } // end if
               
                tree.add(child);
                parent.setRightChild(child);
                System.out.println("The child is");
                child.printNode();
                System.out.println();
                //System.out.println("the parent is");
                //parent.printNode();
          } // end if
         
          if (parent.canMoveDown(parent.getState()))
          {
                child.setState(parent.copy(parent.getState()));
                child.moveDown(child.getState());
               
                if (child.isEqual(child.getState(), goalState))
                {
                  child.printNode();
                  return;
                } // end if
               
                tree.add(child);
                parent.setDownChild(child);
                System.out.println("The child is");
                child.printNode();
                System.out.println();
              // System.out.println("the parent is");
              // parent.printNode();
          } // end if
        } // end else if
     
        else if (parent.canMoveRight(parent.getState()))
        {
          child.setState(parent.copy(parent.getState()));
          child.moveRight(child.getState());
         
          if (child.isEqual(child.getState(), goalState))
              {
                child.printNode();
                return;
              } // end if
         
          tree.add(child);
          parent.setRightChild(child);
          System.out.println("The child is");
          child.printNode();
          System.out.println();
          //System.out.println("the parent is");
          //parent.printNode();
          level++;
         
          if (parent.canMoveDown(parent.getState()))
          {
                child.setState(parent.copy(parent.getState()));
                child.moveDown(child.getState());
               
                if (child.isEqual(child.getState(), goalState))
                {
                  child.printNode();
                  return;
                } // end if
               
                tree.add(child);
                parent.setDownChild(child);
                System.out.println("The child is");
                child.printNode();
                System.out.println();
                //System.out.println("the parent is");
                //parent.printNode();
          } // end if
      } // end else if
     
        else  if (parent.canMoveDown(parent.getState()))
      {
          child.setState(parent.copy(parent.getState()));
          child.moveDown(child.getState());
         
          if (child.isEqual(child.getState(), goalState))
              {
                child.printNode();
                return;
              } // end if
         
          tree.add(child);
          parent.setDownChild(child);
          System.out.println("The child is");
          child.printNode();
          System.out.println();
          //System.out.println("the parent is");
          //parent.printNode();
          level++;
      } // end else if
       
      if (!child.isEqual(child.getState(), goalState))
      {
          System.out.println("the level is " + level);
            insertChild(findF(tree, level), child);
      } // end if
  } // end insertChild
 
  // print the node and f(n) for the node being used
  public static void printOutput(GridNode node, int f, int g, int h)
  {
      node.printNode();
      System.out.println("the f(n) function is: " + f + " = " + g + " + " + h);
      System.out.println();
  } // end printOutput
 
  public static void main(String[] args)
  {
      GridNode parent = new GridNode(initialState, null, null, null, null);
      GridNode child = new GridNode(null, null, null, null, null);
      insertChild(parent, child);
      System.out.println("the size of the list is " + tree.size());
      System.out.println();
      // find out its f(n) value
      // find out if its the goal
      // if not find next set of children
      //System.out.println(findF(tree));
  } // end main
 
} // end NewMain

DaWei Sep 19th, 2007 7:56 PM
Why are you starting a new thread over each facet of a single problem? It dilutes your responses. Shall we answer here or there?

cwl157 Sep 19th, 2007 7:59 PM
i dont know cause im losing my mind cause ive been working on this for about 6 - 10 hours a day for the past 7 days straight and am just frustrated cause there is no one (excluding what i got from you guys on this forum which i appreciate very much) that will give me even the slightest hint at anything that can help me. so to answer your question i dont care, i just want to know how to do this.

DaWei Sep 19th, 2007 9:07 PM
If you don't care, why should anyone else? Just curious.

cwl157 Sep 19th, 2007 9:30 PM
no no no i mean i dont care where you put the answer, i do very much care about figuring this out. I'm been pulling my hair out over it for the past week and would really like to know what to do

DaWei Sep 20th, 2007 9:24 AM
:
package ArrayThangy;
import java.io.*;

public class Main
{
    public Main (){}
    public static class ArrayThangy
    {
        public int[] theGoodies = {1, 2, 3};
        public ArrayThangy (){}
    }

    public static void main (String args [])
    {
        ArrayThangy numeroUno = new ArrayThangy ();
        ArrayThangy numeroDos = new ArrayThangy ();
        ArrayThangy numeroTres = new ArrayThangy ();
       
        System.out.println ("Assign array one to array two");
        // The following will result in a shallow copy, a reference
        numeroDos = numeroUno;
       
        System.out.println ("Note that the arrays are identical");
        System.out.print ("Array one: ");
        for (int i = 0; i < numeroUno.theGoodies.length; i++)
        {
            System.out.print (numeroUno.theGoodies [i]);
            System.out.print (" ");
        }
        System.out.print ("\nArray two: ");
                for (int i = 0; i < numeroDos.theGoodies.length; i++)
        {
            System.out.print (numeroDos.theGoodies [i]);
            System.out.print (" ");
        }
       
        System.out.println ("\n\nChange the value of an element in array two");
        numeroDos.theGoodies [0] = 5;
        System.out.println ("Note that the arrays are still identical");
        System.out.print ("Array one: ");
        for (int i = 0; i < numeroUno.theGoodies.length; i++)
        {
            System.out.print (numeroUno.theGoodies [i]);
            System.out.print (" ");
        }
        System.out.print ("\nArray two: ");
                for (int i = 0; i < numeroDos.theGoodies.length; i++)
        {
            System.out.print (numeroDos.theGoodies [i]);
            System.out.print (" ");
        }
       
        System.out.println ("\n\nMake a deep copy of one to three");
        // The following will result in a deep copy
        for (int i = 0; i < numeroUno.theGoodies.length; i++)
            numeroTres.theGoodies [i] = numeroUno.theGoodies [i];
       

        System.out.println ("Note that arrays one and three are also identical");
        System.out.print ("Array one: ");
        for (int i = 0; i < numeroUno.theGoodies.length; i++)
        {
            System.out.print (numeroUno.theGoodies [i]);
            System.out.print (" ");
        }
        System.out.print ("\nArray three: ");
                for (int i = 0; i < numeroTres.theGoodies.length; i++)
        {
            System.out.print (numeroTres.theGoodies [i]);
            System.out.print (" ");
        }
        System.out.println ("\nChange the value of an element in array three");
        numeroTres.theGoodies [0] = 1;
        System.out.println ("Note that the arrays are NOT identical");
        System.out.print ("Array one: ");
        for (int i = 0; i < numeroUno.theGoodies.length; i++)
        {
            System.out.print (numeroUno.theGoodies [i]);
            System.out.print (" ");
        }
        System.out.print ("\nArray three: ");
                for (int i = 0; i < numeroTres.theGoodies.length; i++)
        {
            System.out.print (numeroTres.theGoodies [i]);
            System.out.print (" ");
        }
    }
 
}
Quote:
Originally Posted by Output
compile:
run:
Assign array one to array two
Note that the arrays are identical
Array one: 1 2 3
Array two: 1 2 3

Change the value of an element in array two
Note that the arrays are still identical
Array one: 5 2 3
Array two: 5 2 3

Make a deep copy of one to three
Note that arrays one and three are also identical
Array one: 5 2 3
Array three: 5 2 3
Change the value of an element in array three
Note that the arrays are NOT identical
Array one: 5 2 3
Array three: 1 2 3

cwl157 Sep 20th, 2007 10:51 AM
i dont understand, I do make a copy of the array when i store it in the other one... i was thinking maybe something with setting the leftChild, upChild, rightChild, and downChild, but i also have a method that does that, i think it does it correctly anyway, and that didnt work either. I dont know, i think its kinda stupid too, that ive taken 2 years of java classes and this is the first time ive run into any problems with copying things from one instance to another or have heard anything about shallow copy and deep copy and all that, youd think in 4 java classes that somewhere along the line that would have been talked about, but it wasnt and i think thats part of what really threw me off for this assignment.

DaWei Sep 20th, 2007 11:20 AM
Okay, I don't know exactly what you're trying to do. Are you trying to make a matrix with a link from each element to the four adjoining, orthogonal elements?

Are you growing the matrix as time goes by? Does it always have an equal number of elements or each row? How do you determine the values to be placed in the elements?

cwl157 Sep 20th, 2007 4:14 PM
each matrix is always 3 x 3 im trying to link matrices together

DaWei Sep 20th, 2007 4:17 PM
So you have a stack of 3x3 2D matrices, which makes a 3D entity. Does each matrix need to link to every other matrix, or only to the ones 'above' and 'below'?

I'm just trying to get a simplified picture so I can farble with it some.


All times are GMT -5. The time now is 11:20 PM.
Page 1 of 2 1 2 >
Show 40 post(s) from this thread on one page

Powered by vBulletin® Version 3.7.0, Copyright ©2000 - 2008, Jelsoft Enterprises Ltd.
Copyright ©2007 DaniWeb® LLC