CODEWITHSUNDEEP
javalist
mpv1504
mpv1504

Reputation: 31

Java : verifying if an object already exists in a List?

The probleme is described in details here : https://adventofcode.com/2015/day/3 Shortly to summarize : I successively visit locations thanks to indications given in a text file, and i want to know how many locations I have visited at least once.

I have created a class Point like this : 

public class Point {
  private int x;
  private int y;

  public Point (int x, int y) {
    this.x=x;
    this.y=y;
  }

  public int getAbs() {
    return x;
  }

  public int getOrd() {
    return y;
  }
}

It is simply a point formed by two coordinates, to indicate the location of a house. I use it here : 

public class Exo3 {

  public static void main(String[] args) throws IOException {
    FileReader fr = new FileReader("C:/Users/mpv15_000/Documents/Advent/input3.txt");   
    int c = fr.read();

    int x=0;
    int y=0;
    Point init = new Point(x,y);

    List<Point> visitedHouses = new ArrayList<Point>();
    visitedHouses.add(init);

    Boolean b = true;

    while ((c == '^') || (c == 'v') || (c == '<') || (c == '>'))
    {           
      if (c == '^')  
        y++;
      else if (c == 'v')
        y--;    
      else if (c == '<')
        x--;
      else
        x++;

      for (Point p : visitedHouses) {
        if ((p.getAbs() != x) || (p.getOrd() != y))
          b = true;
        else 
          b = false;
      }     

      if (b == true) {
        visitedHouses.add(new Point(x,y));
      }
      c = fr.read();
    }

    System.out.println("Number of houses visited at least once : " + visitedHouses.size());
    fr.close();
  }
}

I get "8193", which is the total number of iterations I suppose, but not what I am looking for. I want to know what are the locations I have visited at least once. I think the problem comes from the for-loop on the visitedHouses list. I would like to compare if the current x and y already exist in a Point located in this list. What should I do ?

Upvotes: 1

Views: 689

Answers (3)

MaxZoom
MaxZoom

Reputation: 7753

As mentioned in the question comment above, you need to break the visitedHouses loop, as soon as you find the duplicated point.
For performance, I have changed the condition a bit inside the loop, see below:

  boolean found = false;
  for (Point p : visitedHouses) {
    if ((p.getAbs() == x) && (p.getOrd() == y)) {
      found = true;
      break;
    }
  }     

  if (!found) {
    visitedHouses.add(new Point(x,y));
  }

DEMO

Upvotes: 0

Edwin Buck
Edwin Buck

Reputation: 70959

the section of code 

    for (Point p : visitedHouses)
    {
        if ((p.getAbs() != x) || (p.getOrd() != y))
            b = true;
        else 
            b = false;
    }       

    if (b == true)
    {
        visitedHouses.add(new Point(x,y));
    }

looks especially problematic

If you find the "visited" house in the middle of the list, the next entry will not (hopefully) be a duplicate of that house, and will set the "b" flag to false, resulting in a duplicate.

This is due to the programming smell "caching a control variable". I recommend you don't store control variables (variables that are later checked in if statements to alter the behavior of your block.

Point newCandidate = new Point(x,y);
for (Point p : visitedHouses) {
    if (newCandidate.getAbs() == p.getAbs() &&
        newCandidate.getOrd() == p.getOrd()) {
      newCandidate = null;
      break;
    }
}
if (newCandidate != null) {
    visitedHouses.add(newCandidate);
}

However, this is still mostly like a control variable. What would be much faster is if we just used a java Set like HashSet.

public Point {
   ... same stuff you have ...

   @Override
   public int hashcode() {
       return 37*x + 23*y + 13;
   }

   @Override
   public boolean equals(Object object) {
       if (! object instanceof Point) {
           return false;
       }
       Point other = (Point)object;
       if (this.x != other.x) { return false; }
       if (this.y != other.y) { return false; }
       return true;
   }
}

Then you can do

Set<Point> visitedHouses = new HashSet<Point>();
// possibly initialize the first house
visitedHouses.add(new Point(0, 0));
while (... visiting each house ...) {
    Point currentHouse = new Point(currentX, currentY);
    visitedHouses.add(currentHouse);
}

and rely upon the Set interface to assure that you never get a duplicate Point entry in the Collection as Sets cannot contain duplicates (and your Point now knows how to take two instances and determine if they are equal).

Not only will the last approach be much faster, since it is stored in a HashSet you don't need to go through each Point in the Set to determine if you have a match for the current location. The hashcode(...) is ran on the "point being used to query the Set" and lookup by it's returned value avoids 99% of the other entries. The small subset of entries that have a matching hashcode are then compared with the equals(...) method to really determine if they are equivalent, or if they "just happen" to have the same hashcode.

Upvotes: 1

Vadim
Vadim

Reputation: 4120

You need to override equals method in Point class to return true when x and y are the same. something like this:

  @Override
  public boolean equals(Object other)
  {
      if (this == other) return true;
      if (!(other instanceof Point)) return false;
      return (this.x == ((Point)other).x) && (this.y == ((Point)other).y);

  }

Then use Set instead of List. Set will hold only unique Points.

If you'd like to stay with List just do:

    if (b == true)
    {
        Point visitedPoint = new Point(x,y);
        if (!visitedHouses.contains(visitedPoint)) {
           visitedHouses.add(visitedPoint);
        }
    }

BTW: how you identify visited House is up to you...

Upvotes: 1

Related Questions