current community

your communities

more stack exchange communities

company blog
Stack Exchange Inbox Reputation and Badges
tour help
Join the Stack Overflow Community
Stack Overflow is a community of 6.4 million programmers, just like you, helping each other.
Join them; it only takes a minute:
Sign up
up vote 1 down vote favorite

I was given this question in a programming test for an IT company. I will try my best to explain it.

The problem is as follows:

Given an Ant at origin (0,0) which moves only in clockwise direction( takes only right turns) on a given path array. so for example if the path array is {2,3,4,5,7} the ant moves 2 units left, then moves 3 units down , then moves 4 units right, then moves 5 units up and then 7 units left so on and so forth.

So write a code which displays the ant's final position(coordinates) and state if the ant intersects it's path in the format:

Ant: (x1,y1) :(yes / no)

for example: (1) array={1,6,3,5,4} output: Ant: (2,-1) :yes

showing it graphically

         (0, 0)__(1,0)
                    |
 (-2,-1)   __ __ __ __(2,-1)
        |           |
        |           |
        |           |
        |           |
        |           |
  (-2,-6)  __ __ __    (1,-6)

here the ant is intersecting its path at (1,-1)

(2) array={2,2,2,1} output: Ant: (0,-1) :no

showing it graphically

(0, 0)__ __(2,0)
 .(0,-1)    |
 |          |
(0,-2)__ __(2,-2)

here the ant doesn't intersect its path.

I wrote a code to find the final position:

public class Ant {

    static void findAnt(int arr[])
    {
        int count = 0;
        int x=0,y=0;
        for(int element: arr){
            if(count>3)
                count = 0;

            switch(count++){

            case 0: x=x+element;
                    break;
            case 1: y=y-element;
                    break;
            case 2: x=x-element;
                    break;
            case 3: y=y+element;
                    break;

            }
        }
        System.out.println("Ant: "+x+" "+y);
    }
    public static void main(String[] args)
    {
        int arr[] = new int[]{2,2,2,1};
        findAnt(arr);
    }


}

However I cannot devise an algorithm that shows if the ant intersects or not. Please advise.

share|improve this question

put on hold as unclear what you're asking by Rhymoid, khelwood, thebjorn, rkosegi, chridam 13 hours ago

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question.If this question can be reworded to fit the rules in the help center, please edit the question.
1  
Create a boolean array, fill it all to false, then when an ant would "walk" on that tile, flip it to true. Then when you have the ants final position check if that tile is already true, if so then it's been there before. – user123 yesterday
    
Thanks @user123, If you could elaborate your solution, it would be of great help? – Vedant Aggrawal yesterday
    
Create a boolean[][] gameBoard, you can make it n * n in size, initialize it to false. Then start looping through your array of movements, as the ant walks along each index flip the value to true (it's been there). Then when you get to the last index in your movements array, you check to see if the tile is already true, if it is, then you've been there already. – user123 yesterday
1  
@user123: what if the path of the ant intersects with itself on a tile which is not the last one the ant visits? :) – dingalapadum yesterday
    
Another way of doing this is to create a whole bunch of lines (ants starting point to end point), then doing a point in line test, where the point is the ants ending position against all of the lines. – user123 yesterday
up vote 1 down vote

It will horizontally intersect if arr[1] <= arr[3] and vertically if arr[0] <= arr[2] you just need to check these positions.

for (int i = 0; i < arr.length; i++){
     if (i == arr.length-2)
         return false;//prevents indexoutofbounds
     if (arr[i] <= arr[i+2])
         return true;//intersects
}

this should check to see if p0 is less than p2, p1, is less than p3, and p2 is less than p4, and so on.

boolean intersect = false;



    for (int i = 0; i < arr.length; i++){
            if (arr[i] == arr[arr.length-2]){//i changed this
                intersect = false;//prevents indexoutofbounds
                break;

            }
            if (arr[i] <= arr[i+2])
                intersect =  true;//intersects
                break;
       }

and then print out intersect

share|improve this answer
    
in your code you will need to break out of the loop when you find either true or false, since you cant use a return – sbowde4 yesterday
    
I am afraid it isn't working. for array={2,2,2,1} it outputs true even though the ant doesn't intersect. – Vedant Aggrawal yesterday
    
I got false, i'll show you how i implemented it, – sbowde4 yesterday
    
oh, i know why, change the <= to <. I was assuming if they touched it counted as an intersect. – sbowde4 yesterday
    
Although it worked for some test cases , it didn't work on all, I considered an array={5,6,3,5,4} and when executed it the output came out to be false. – Vedant Aggrawal yesterday
up vote 1 down vote

One solution that doesn't keep a grid in memory, is to keep a set of visited locations in memory. This has the advantage that you don't need to know the boundary of the ant's potential path in advance. Whether it takes more or less memory than a grid, depends on the size of the grid, and the length of the ant's journey.

public class VisitedTileLog {

      Set visitedTiles = new HashSet<Coordinates>();
      boolean hasIntersected = false;

      public void logVisit(Coordinates c) {
          if(! visitedTiles.add(c)) {
              hasIntersected = true;
          }
      }

      public boolean hasIntersected() {
          return hasIntersected;
      }
}

Of course you need a Coordinates class with equals() and hashCode():

public class Coordinates {
     private int x,y;

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

     public boolean equals(Object o) {
        // Let your IDE write this, or read up on best practice.
     }

     public int hashCode() {
        // Let your IDE write this, or read up on best practice.
     }

     // Examples of other methods this might have...
     public int getX() { ... }
     public int getY() { ... }
     public Coordinates move(int distance, Direction direction);
}

Now you can take your ant for a walk, and each time it moves, update hasIntersected:

 VisitedTileLog log = new VisitedTileLog();
 for(int distance : distances) {
      ...
      log.logVisit(...);
      ...
 }

This class could be enhanced with convenience methods that log a whole step's line -- logVisit(Coordinates from, Coordinates to) or logVisit(Coordinates start, int distance, CompassPoint direction).

Depending on the interviewer, a solution like this might get you extra credit for being object-oriented. Indeed, this class could be enhanced to solve the whole of the problem, if it also maintained a currentPosition field.

share|improve this answer
2  
You are still brute forcing. Since the ant only makes the same turns, the steps it made quickly become irrelevant (a path intersecting old segments must necessarily intersect a newer one). In the worst case, only 5 last segments must be traced. – user58697 yesterday
    
@user58697 that last sentence is the crucial observation that needs to be done. Only the last 5 segments must be traced. Congrats you solved the puzzle. With this knowledge the linear time solution should be really easy to implement... – dingalapadum yesterday
    
This is a fair point, and the approach I've described could be enhanced to age-off logged squares after their usefulness has passed. It could also store a list of lines rather than squares, and calculate intersections in a more sophisticated way. With unlimited time I would start with this brute-force solution, write unit tests, then refine it to be smarter. – slim yesterday
    
@slim hey! can you describe the coordinate class's methods for a better understanding? thanks. – Vedant Aggrawal 12 hours ago
1  
@slim I'm saying you should keep a queue<segments> of fixed size (5). When creating a new segment check against elements 0, 1, 2, 3 (you'll always intersect element number 4). Then remove the first element and put the newly created segment at the end of the queue. This will make that for each point in the path you do a constant number of operations (create segment + 4 checks) rather than O(n) checks (checking against all the other segments) – dingalapadum 11 hours ago
up vote 0 down vote

One way to achieve this is to draw the line during each move for reference. And check before every move that if it is encountering the same coordinate that is already drawn. Below is the code for this approach. You can definitely fine tune it , but here is one way to tackle it.

Steps :
Create Coordinate type to store coordinates.
Create Ant that can hold : current coordinate: this will hold the Ant Current Coordinate at any time
Direction to Move next : right , left , up or down
data set to keep track of traversed coordinate
data structure to hold all coordinates that are revisited

Now on every move of ant, it knows what direction to move next. And in each move , we draw all coordinates in between the current coordinate and the end point , and store them in traversed coordinate set. If there is hit, we store it in intersected coordinate set instead.

At the end, current coordinate of ant gives us the final coordinate and the line crosses over if the intersected set is not empty.

Here is the long code , that I assume is working fine.

public class PathCross {

public static void main(String[] args) {

    int[] movementArray = { 2, 2, 2, 1 };// {1,6,3,5,4};
    PathCross driver = new PathCross();
    Ant ant = driver.new Ant();

    for (int i : movementArray) {
        ant.move(i);
    }

    System.out.println("Ant: (" + ant.currentCoordinate.getX() + "," + ant.getCurrentCoordinate().getY() + ") :"
            + !ant.getIntersectingCoordinates().isEmpty());
}

class Ant {

    Coordinate currentCoordinate = new Coordinate(0, 0);
    Direction nextDirection = Direction.RIGHT;

    Set<Coordinate> intersectingCoordinates = new HashSet<>();

    Set<Coordinate> traversedCoordinateSet = new HashSet<>();

    public Ant() {
        traversedCoordinateSet.add(new Coordinate(0, 0));
    }

    public Coordinate getCurrentCoordinate() {
        return currentCoordinate;
    }

    public void setCurrentCoordinate(Coordinate currentCoordinate) {
        this.currentCoordinate = currentCoordinate;
    }

    public Direction getNextDirection() {
        return nextDirection;
    }

    public void setNextDirection(Direction nextDirection) {
        this.nextDirection = nextDirection;
    }



    public Set<Coordinate> getIntersectingCoordinates() {
        return intersectingCoordinates;
    }

    public void setIntersectingCoordinates(Set<Coordinate> intersectingCoordinates) {
        this.intersectingCoordinates = intersectingCoordinates;
    }

    public Set<Coordinate> getTraversedCoordinateSet() {
        return traversedCoordinateSet;
    }

    public void setTraversedCoordinateSet(Set<Coordinate> traversedCoordinateSet) {
        this.traversedCoordinateSet = traversedCoordinateSet;
    }

    public void move(int distance) {
        Coordinate newCoordinate = null;
        switch (nextDirection) {

        case RIGHT:
            newCoordinate = new Coordinate(currentCoordinate.getX() + distance, currentCoordinate.getY());
            for (int i = currentCoordinate.getX() + 1; i <= (currentCoordinate.getX() + distance); i++) {
                if (!traversedCoordinateSet.add(new Coordinate(i, currentCoordinate.getY()))) {
                    intersectingCoordinates.add(new Coordinate(i, currentCoordinate.getY()));
                }

            }
            nextDirection = Direction.DOWN;
            break;

        case DOWN:
            newCoordinate = new Coordinate(currentCoordinate.getX(), currentCoordinate.getY() - distance);
            for (int i = currentCoordinate.getY() - 1; i >= (currentCoordinate.getY() - distance); i--) {
                if (!traversedCoordinateSet.add(new Coordinate(currentCoordinate.getX(), i))) {
                    intersectingCoordinates.add(new Coordinate(currentCoordinate.getX(), i));
                }
            }
            nextDirection = Direction.LEFT;
            break;

        case LEFT:
            newCoordinate = new Coordinate(currentCoordinate.getX() - distance, currentCoordinate.getY());
            for (int i = currentCoordinate.getX() - 1; i >= (currentCoordinate.getX() - distance); i--) {
                if (!traversedCoordinateSet.add(new Coordinate(i, currentCoordinate.getY()))) {
                    intersectingCoordinates.add(new Coordinate(i, currentCoordinate.getY()));
                }
            }
            nextDirection = Direction.UP;
            break;

        case UP:
            newCoordinate = new Coordinate(currentCoordinate.getX(), currentCoordinate.getY() + distance);
            for (int i = currentCoordinate.getY() + 1; i <= (currentCoordinate.getY() + distance); i++) {
                if (!traversedCoordinateSet.add(new Coordinate(currentCoordinate.getX(), i))) {
                    intersectingCoordinates.add(new Coordinate(i, currentCoordinate.getY()));
                }
            }
            nextDirection = Direction.RIGHT;
            break;

        default:
            System.err.println("ERRor");

        }

        this.currentCoordinate = newCoordinate;

    }

}

enum Direction {
    LEFT, DOWN, RIGHT, UP;
}

class Coordinate {
    int x;
    int y;

    public Coordinate() {

    }

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

    public int getX() {
        return x;
    }

    public void setX(int x) {
        this.x = x;
    }

    public int getY() {
        return y;
    }

    public void setY(int y) {
        this.y = y;
    }

    @Override
    public int hashCode() {
        final int prime = 31;
        int result = 1;
        result = prime * result + getOuterType().hashCode();
        result = prime * result + x;
        result = prime * result + y;
        return result;
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj)
            return true;
        if (obj == null)
            return false;
        if (getClass() != obj.getClass())
            return false;
        Coordinate other = (Coordinate) obj;
        if (!getOuterType().equals(other.getOuterType()))
            return false;
        if (x != other.x)
            return false;
        if (y != other.y)
            return false;
        return true;
    }

    private PathCross getOuterType() {
        return PathCross.this;
    }

    @Override
    public String toString() {
        return "x=" + x + ", y=" + y;
    }

}

}

share|improve this answer
up vote -1 down vote

The problem is hard to find out whether it intersect the previous paths. I create a boolean to record whether it is increase the circle or not. if it is always increasing, it will not intersect the previous paths. If it change to the decreasing, once it began to increasing again, it will intersects the paths. Otherwise, it will not intersects the path

def ant(arr):
    length = len(arr)
    x = sum(arr[::4]) - sum(arr[2:][::4])
    y = sum(arr[3:][::4]) - sum(arr[1:][::4]) 
    if length < 4:
        return x, y, False
    t1, (t2, t3, t4) = 0, arr[:3]
    increase = (t2 < t4)
    for i in xrange(3, length):
        t5 = arr[i]
        if increase and t3 >= t5:
            if t1 + t5 - t3 < 0 or i+1 < length and arr[i+1] + t2 - t4 < 0:
                increase = False
            elif i + 1 < length:
                return x, y, True

        elif not increase and t3 <= t5:
            return x, y, True
        t1, t2, t3, t4 = t2, t3, t4, t5
    return x, y, False
share|improve this answer

Not the answer you're looking for? Browse other questions tagged or ask your own question.