Problem with Algorithm to find minimum path of a 2d array

Question

Question:

There are 10 people at a meetup.
Each person has levels 0 - 9 (the index of the input) and knows a few other people there.
Your job is to find the cheapest way for person 0 to meet person 9. Introductions have a cost that equals the square of the difference in levels.

Goal: Level 0 person wants to meet level 9 using the fewest possible points.
Cost: square of difference of levels
The index of the array represents the level (0-9)
the value is an array with the index of the other people each person knows.
Note that relationships are one directional (e.g. 2 can introduce you to 3 but not vice versa) e.g. Min cost: 23 Min path: [0, 1, 4, 6, 9]

 people = [
   [1, 2, 3],   # person 0 knows 1, 2, 3
   [8, 6, 4],   # person 1 knows 8, 6, 4
   [7, 8, 3],   # person 2 knows 7, 8, 3
   [8, 1],      # person 3 knows 8, 1
   [6],         # person 4 knows 6
   [8, 7],      # person 5 knows 8, 7
   [9, 4],      # person 6 knows 9, 4
   [4, 6],      # person 7 knows 4, 6
   [1],         # person 8 knows 1 
   [1, 4],      # person 9 knows 1, 4
 ]

My solution:

To use a priority queue and as well as set to track the elements that have already being visited. Basically a breadth first search approach. Also i will use a map to track the levels.

My problem

I attempt to use a priority queue but not able to traverse the 2d array with the queue. I only cover level 0 and not other levels. Below is my attempted solution

class Solution {
  public static void main(String[] args) {
    int[][] arr ={{1, 2, 3},
                  {8, 6, 4},
                  {7, 8, 3},
                  {8, 1},
                  {6},
                  {8,7},
                  {9, 4},
                  {4, 6},
                  {1},
                  {1,4}};
    
    Solution sol = new Solution();
    sol.meetUp(arr);
  }
  
  List<Integer> meetUp(int[][] arr) {
   if (arr == null || arr.length == 0)  {
     return new ArrayList<>();
  }
    
  Set<Integer> visited = new HashSet<>();
  PriorityQueue<MinQueue> pq = new PriorityQueue<>();
  Map<Integer, Integer> parentMap = new HashMap<>();
    
  pq.offer(new MinQueue(0, 0, arr[0][0]));
    
  while(!pq.isEmpty()) {
   MinQueue temp = pq.poll();
   int col = temp.col + 1;
   while (col < arr[temp.row].length) {
    if(!visited.contains(arr[temp.row][col])) {
     pq.offer(new MinQueue(temp.row, col, arr[temp.row][col])); 
     col += 1;
    }
  }
     
  if(!parentMap.containsKey(temp.row)) {
        parentMap.put(temp.row, temp.data);
      } else {
          int v = parentMap.get(temp.row);
          int n = (int)Math.pow(temp.data, 2) - (int)Math.pow(temp.row, 2);
          int o = (int)Math.pow(v, 2) - (int)Math.pow(temp.row, 2);
        if(n < o) {
          parentMap.put(temp.row, temp.data);
      }
    }
    visited.add(temp.data);
  }
    return new ArrayList<>();
  }
}

class MinQueue implements Comparable<MinQueue> {
  
   int data;
   int row;
   int col;
  
   MinQueue(int row, int col, int data) {
     this.row = row;
     this.col = col;
     this.data = data;
   }
  
  public int compareTo(MinQueue other) {
    if(this.data - other.data > 0) return 1;
    else if(this.data - other.data < 0) return -1;
    else return 0;
  }
}

@SazzadurRahaman because of the square difference. your solution will be 35. That is the cost path — EI-01
– EI-01, Commented Sep 8, 2018 at 2:02
@SazzadurRahaman my problem is after i traverse the first level i'm not able to proceed further down other levels using the priority queue. — EI-01
– EI-01, Commented Sep 8, 2018 at 2:19
@user3497437 where do you offer it next levels? The only offer is in while - which for entry item (Level0-Known0) offers to queue L0-K0, L0-K1, L0-K2 - then on next item from priority queue it offers L0-K1, L0-K2, then on next L0-K2 and then after that, the priority queue becomes empty - see the problem? — Worthless
– Worthless, Commented Sep 8, 2018 at 2:58

RaffleBuffle · Accepted Answer · 2018-09-08 16:21:22Z

2

You're looking for the minimum cost path through a directed graph. As such, Dijkstra's algorithm is what you want.

Here's a simple Java implementation, customized to your task. It returns -1 if no path exists.

static int minCost(int[][] relations, int[] prev)
{
    PriorityQueue<Person> q = new PriorityQueue<>();

    Person[] person = new Person[relations.length];
    for(int i=0; i<relations.length; i++) 
    {
        person[i] = new Person(i, i==0 ? 0 : Integer.MAX_VALUE);
    }

    q.offer(person[0]);     
    while(!q.isEmpty())
    {
        Person p = q.poll();

        if(p.level == person.length-1) 
            return p.cost;          

        for(int n : relations[p.level])
        {
            int d = p.cost + (n-p.level)*(n-p.level); 
            if(d < person[n].cost)
            {
                q.offer(person[n] = new Person(n, d));
                prev[n] = p.level;
            }
        }
    }       
    return -1;
}

static class Person implements Comparable<Person>
{
    public int level;
    public int cost;

    public Person(int level, int cost)
    {
        this.level = level;
        this.cost = cost;
    }

    @Override
    public int compareTo(Person o)
    {
        return cost - o.cost;
    }
}

static String buildPath(int[] arr, int i, String path)
{
    path = i + " " + path;
    if(i == 0) return path;
    else return buildPath(arr, arr[i], path);
}

public static void main(String[] args) 
{
    int[][] arr ={{1, 2, 3},
                  {8, 6, 4},
                  {7, 8, 3},
                  {8, 1},
                  {6},
                  {8,7},
                  {9, 4},
                  {4, 6},
                  {1},
                  {1,4}};

    int[] prev = new int[arr.length];
    int min = minCost(arr, prev);
    if(min < 0) System.out.println("No path");    
    else System.out.println(min + " : " + buildPath(prev, arr.length-1, ""));        
}

Output:

23 : 0 1 4 6 9

edited Sep 8, 2018 at 16:21

answered Sep 8, 2018 at 7:18

RaffleBuffle

5,4651 gold badge11 silver badges17 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

EI-01 Over a year ago

return the list of level and not the actual minimum cost

EI-01 Over a year ago

thanks for your answer. I figured it out. My issue was not creating an array like u did with Person Object. That was my issue. Thanks and how did you come about creating the array. My initial idea was to create a Graph class.

RaffleBuffle Over a year ago

I've updated the answer to track and print the path through the levels. The array is just a cheap way of recovering the neighbours of a Person. A Graph class would be a good idea.

Collectives™ on Stack Overflow

Problem with Algorithm to find minimum path of a 2d array

Question:

My solution:

My problem

1 Answer 1

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

Question:

My solution:

My problem

1 Answer 1

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related