Программирование теста по алгоритмам?

Question

Мне задали этот вопрос в тесте на программирование для ИТ-компании. Я постараюсь изо всех сил объяснить это.

Проблема заключается в следующем:

Дано Ant при возникновении (0,0), которая движется только в направлении по часовой стрелке (принимает только вправо поворачивается) на заданном массиве пути. так, например, если массив путей равен {2,3,4,5,7}, муравьи перемещают 2 единицы влево, затем перемещает 3 единицы вниз, затем двигает 4 единицы вправо, затем перемещает 5 единиц вверх, а затем 7 единиц, оставшихся так далее и так далее.

Так написать код, который отображает окончательную позицию муравья (координаты) и состояние, если муравей пересекает это путь в формате:

Ant: (x1, y1): (да/нет)

например: (1) массив = {1,6,3,5,4} выход: Ant: (2, -1): да

показывая его графически

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

ее е муравей пересекающиеся свой путь в точке (1, -1)

(2) массив = {2,2,2,1} выход: Ant: (0, -1): нет

показа это графически

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

здесь муравь не пересекает его путь.

Я написал код, чтобы найти окончательную позицию:

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); 
    } 


} 

Однако я не могу изобрести алгоритм, который показывает, если муравей пересекает или нет. Просьба сообщить.

Answer 1

Он будет горизонтально пересекаться, если arr[1] <= arr[3] и по вертикали, если arr[0] <= arr[2] вам просто нужно проверить эти положения.

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 
} 

это следует проверить, если р0 меньше p2, p1, меньше р3 и р2 меньше р4, и так далее.

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; 
     } 

, а затем распечатать пересекаются

Answer 2

Проблема трудно выяснить, является ли она пересекает предыдущие пути. Я создаю логическое значение для записи, увеличивать круг или нет. если он всегда увеличивается, он не будет пересекать предыдущие пути. Если он изменится на уменьшение, как только он снова начнет увеличиваться, он пересечет пути. В противном случае, он не будет пересекает тракт

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 

Answer 3

Одно решения, которое не держать сетки в памяти, чтобы сохранить набор посещаемых мест в памяти. Это имеет то преимущество, что вам не нужно заранее знать границу пути потенциального муравья. Требуется ли более или менее память, чем сетка, зависит от размера сетки и длины пути муравья.

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; 
     } 
} 

Конечно вам нужен Coordinates класс с equals() и 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); 
} 

Теперь вы можете взять ваш муравей на прогулку, и каждый раз, когда он движется, обновить hasIntersected:

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

Этот класс может быть расширен с помощью удобных методов, которые регистрируют линию всего шага - logVisit(Coordinates from, Coordinates to) или logVisit(Coordinates start, int distance, CompassPoint direction).

В зависимости от интервьюера решение, подобное этому, может дать вам дополнительный кредит за объектно-ориентированное решение. Действительно, этот класс может быть усилен для решения всей проблемы, если он также поддерживает поле currentPosition.

Answer 4

Один из способов достижения этой цели - нарисовать линию во время каждого перемещения для справки. И проверяйте перед каждым движением, что если он встречает ту же самую координату, которая уже нарисована. Ниже приведен код этого подхода. Вы можете точно настроить его, но вот один из способов его решения.

Шаги:
Создание Coordinate типа для хранения координат.
Создание Ant, который может содержать: current coordinate: это будет держать муравей Текущей координаты в любое время
Direction to Move next: вправо, влево, вверх или вниз
набора данных для отслеживания traversed coordinate
структуры данных для хранения всех coordinates that are revisited

Теперь на каждом ходу ant он знает, какое направление двигаться дальше. И в каждом шаге мы рисуем все координаты между текущей координатой и конечной точкой и сохраняем их в пройденной координате set. Если попал, мы сохраним его в пересеченной координате set.

В конце концов, current coordinate из ant дает нам окончательный coordinate и линия пересекает, если пересекались set является not empty.

Вот длинный код, который я предполагаю, что работает отлично.

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; 
    } 

} 

}