Wizard Meet-up - Find the cheapest way for Wizard level X to meet wizard level Y

Pratap SharmaApril 28th, 20204 mins read

Problem - Wizard Meet-up

This question was asked while giving a coding interview in Turing.

There are 10 wizards at a meet-up. Each wizard has level 0-9(the index of the input) and knows a few other wizard here.

Your job is to find the cheapest way for wizard level Xto meet wizard level Y. Introductions have a cost that equal the square of the difference in levels.

Summary

Goal: Level X wizard wants to meet level Ywizard using minimum cost.
Cost: Square of difference of level.
The index of the input array represents the level 0-9.
The value is an array ith the index of other each wizard knows.
Note that relationships are one-directional (eg 2 can introduceto 3 but not vice-versa).
Output: Eg Min Cost: 23 Path:[0,1,4,6,9]

Input Sample

Input sample explanation

0 -> wizard level 0 wants to meet 9 -> wizard level 9
123 -> wizard 0 knows wizard 1, 2 and 3
864 -> wizard 1 knows wizard 8,6 and 4
783 -> wizard 2 knows wizard 7,8 and 3
81 -> wizard 3 knows wizard 8 and 1
6 -> wizard 4 knows wizard 6
87 -> wizard 5 knows wizard 8 and 7
94 -> wizard 6 knows wizard 9 and 4
46 -> wizard 7 knows wizard 4 and 6
1 -> wizard 8 knows wizard 1
14 -> wizard 9 knows wizard 1 and 4

Solution

Solution using Javascript

function getMinCostPath() {
  //code here
}

getMinCostPath(1, 9, [
  [1, 2, 3],
  [8, 6, 4],
  [7, 8, 3],
  [8, 1],
  [6],
  [8, 7],
  [9, 4],
  [4, 6],
  [1],
  [1, 4],
]);

Solution using Java

package com.challenges.main;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class WizardLevelProblem {

    private int pathCost = Integer.MAX_VALUE;
    private List<Integer> result = null;

    private void reachLevelThroughConn(int[][] wizardConnections, int source, int destLevel, int[] connections , List<Integer> path, int cost){
        for(int wizardLevel: connections){
            if(wizardLevel == destLevel){
                int currentCost = cost + (int) Math.abs(Math.pow(wizardLevel, 2) - Math.pow(source, 2));
                path.add(wizardLevel);
                if(currentCost < pathCost){
                    pathCost = currentCost;
                    result = path;
                }
                return;
            }
            if(!path.contains(wizardLevel)){
                List<Integer> newPath = new ArrayList<>(path);
                newPath.add(wizardLevel);
                int currentCost = cost + (int) Math.abs(Math.pow(wizardLevel, 2) - Math.pow(source, 2));
                reachLevelThroughConn(wizardConnections, wizardLevel,destLevel, wizardConnections[wizardLevel-1], newPath, currentCost);
            }
        }
    }

    private void getMinCostPath(int source, int dest, int[][] wizardConnections){
        List<Integer> path = new ArrayList<>();
        path.add(source);
        reachLevelThroughConn(wizardConnections, source, dest, wizardConnections[source - 1], path, 0);
        if(null != result && result.contains(dest)){
            System.out.println("Path found: "+ result + " cost: " + pathCost);
        } else {
            System.out.println("Path not found");
        }
    }

    public static void main(String[] args) {
        new WizardLevelProblem().getMinCostPath(1, 9, new int[][]{
                {1, 5, 2},
                {8, 6, 4},
                {7, 9, 3},
                {8, 1},
                {9},
                {8, 7},
                {4, 6},
                {9, 4},
                {1},
                {1, 4}
        });
    }
}

💌 If you’d like to receive more tutorials in your inbox, you can sign up for the newsletter here.