HackerRank Synchronous Shopping Solution

In this post, we will solve HackerRank Synchronous Shopping Problem Solution.

Bitville is a seaside city that has a number of shopping centers connected by bidirectional roads, each of which has a travel time associated with it. Each of the shopping centers may have a fishmonger who sells one or more kinds of fish. Two cats, Big Cat and Little Cat, are at shopping center 1 (each of the centers is numbered consecutively from 1 to n). They have a list of fish they want to purchase, and to save time, they will divide the list between them. Determine the total travel time for the cats to purchase all of the types of fish, finally meeting at shopping center n. Their paths may intersect, they may backtrack through shopping center n, and one may arrive at a different time than the other. The minimum time to determine is when both have arrived at the destination.
For example, there are n = 5 shopping centers selling k = 3 types of fish. The following is a graph that shows a possible layout of the shopping centers connected by m = 4 paths. Each of the centers is labeled
center number/fish types offered/cat(s) that visit (s). Here B and L represent Big Cat and Little Cat, respectively. In this example, both cats take the same path, i.e. 1 → 3→ 5 and arrive at time 15+ 5 = 20 having purchased all three types of fish they want. Neither cat visits shopping centers 2 or 4.

Function Description

Complete the shop function in the editor below. It should return an integer that represents the minimum time required for their shopping.

shop has the following parameters:
– n: an integer, the number of shopping centers
– k: an integer, the number of types of fish
– centers: an array of strings of space-separated integers where the first integer of each element is the number of types of fish sold at a center and the remainder are the types sold
– roads: a 2-dimensional array of integers where the first two values are the shopping centers connected by the bi-directional road, and the third is the travel time for that road

Input Format
The first line contains 3 space-separated integers: n (the number of shopping centers), m (the number of roads), and k (the number of types of fish sold in Bitville), respectively. Each line ¿ of the n subsequent lines (1 ≤ i ≤ n) describes a shopping center as a line of space-separated integers. Each line takes the following form:

The first integer, t[i], denotes the number of types of fish that are sold by the fishmonger at the ith shopping center.
Each of the t[i] subsequent integers on the line describes a type of fish sold by that fishmonger, denoted by A[i][z], where 1 ≤ z <t[i] going forward.
Each line j of the m subsequent lines (1 ≤ j ≤ m) contains 3 space-separated integers that describe a road. The first two integers, u[j] and [j], describe the two shopping centers it connects. The third integer, w[j], denotes the amount of time it takes to travel the road.

Output Format

Print the minimum amount of time it will take for the cats to collectively purchase all k fish and meet up at shopping center n.

Sample Input

Sample Output

Explanation

B represents a location Big Cat visits, I represents a location where Little Cat visits. Big Cat can travel 1→2→4→ 5 and buy fish at all of the shopping centers on his way. Little Cat can then travel 1 → 3→ 5, and buy fish from the fishmonger at the 3rd shopping center only.

HackerRank Synchronous Shopping Problem Solution

Synchronous Shopping C Solution

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#include <limits.h>

struct Node {
    void *data;
    struct Node *next;
};

struct Node *head = NULL;
struct Node *tail = NULL;

void Enqueue(void *d){
    struct Node *temp = malloc(sizeof(struct Node));
    temp->data = d;
    temp->next = NULL;
    if(head == NULL && tail == NULL){
        head = tail = temp;
        return;
    }
    tail->next = temp;
    tail = temp;
}

void *Dequeue(){
    if(head == NULL){
        printf("Queue is Empty\n");
        return 0;
    }
    struct Node *temp = head;
    if(head == tail){
        head = tail = NULL;
    }else{
        head = head->next;
    }
    void *d = temp->data;
    free(temp);
    return d;
}

int IsEmpty(){
    if(head == NULL){
        return 1;
    }
    return 0;
}

struct Fishmonger{
    int num;
    int types;
};

struct Edge{
    int vex;
    int cost;
    struct Edge *next;
};

struct Vextypes{
    int vex;
    int types;
};

void read_fishmonger(struct Fishmonger *fm, int n){
    for(int i = 0; i < n; i++){
        scanf("%d",&fm[i].num);
        fm[i].types = 0;
        for(int j = 0; j < fm[i].num; j++){
            int t;
            scanf("%d",&t);
            fm[i].types |= 1 << (t - 1);
        }
    }
}

void append(struct Edge **graph, int i, int v, int t){
    struct Edge *tmp = malloc(sizeof(struct Edge));
    tmp->vex = v;
    tmp->cost = t;
    tmp->next = NULL;
    if(graph[i] == NULL){
        graph[i] = tmp;
    }else{
         struct Edge *next = graph[i];
         while(next != NULL){
            struct Edge *pre = next;
            next = next->next;
            if(next == NULL){
                pre->next = tmp;
                break;
            }
         }
    }
}

int min(int a, int b){
    return a > b ? b : a;
}

int max(int a, int b){
    return a < b ? b : a;
}

int main() {

    /* Enter your code here. Read input from STDIN. Print output to STDOUT
     n(the number of shopping centers),m  (the number of roads), and  k(the number of types of fish sold in Bitville*/
    int n,m,k;
    scanf("%d %d %d", &n, &m, &k);
    int max_mask = 1 << k;
    int dis[n];
    int shortest_path[n][max_mask];
    for(int i = 0; i < n; i++){
        dis[i] = INT_MAX / 2;
        for(int j = 0; j < max_mask; j++){
            shortest_path[i][j] = INT_MAX / 2;
        }
    }
    struct Fishmonger *fs = malloc(n * sizeof(struct Fishmonger));
    read_fishmonger(fs, n);
    struct Edge *graph[n];
    for(int i = 0; i< n; i++){
        graph[i] = NULL;
    }
    for(int i = 0; i < m; i++){
        int x,y,t;
        scanf("%d %d %d", &x, &y, &t);
        append(graph, x-1, y-1, t);
        append(graph, y-1, x-1, t);
    }
 
    struct Vextypes start = {0,fs[0].types};
    Enqueue(&start);
    shortest_path[0][fs[0].types] = 0;
    while(!IsEmpty()){
        struct Vextypes *from = (struct Vextypes*)Dequeue();
        struct Edge *edge = graph[from->vex];
       
        while(edge != NULL){
            int cost = edge->cost;
            int to = edge->vex;
            int types = fs[to].types | from->types;
            if(shortest_path[to][types] > shortest_path[from->vex][from->types] + cost){
                shortest_path[to][types] = shortest_path[from->vex][from->types] + cost;
                struct Vextypes *vt = malloc(sizeof(struct Vextypes));
                vt->vex = to;
                vt->types = types;
                
                Enqueue(vt);
            }
            edge = edge->next;
        }
    }
    
    int min_cost = INT_MAX;
    for(int i = 0; i < max_mask; i++){
       
        for(int j = i; j < max_mask; j++){
            if((i | j) == max_mask - 1){
                min_cost = min(min_cost, max(shortest_path[n-1][i], shortest_path[n-1][j]));
            }
        }
    }
    printf("%d", min_cost);
    return 0;
}

Synchronous Shopping C++ Solution

#include <algorithm>
#include <climits>
#include <functional>
#include <iostream>
#include <queue>
#include <tuple>
#include <type_traits>
#include <utility>
#include <vector>
using namespace std;

typedef pair<long, long> pll;
#define FOR(i, a, b) for (remove_cv<remove_reference<decltype(b)>::type>::type i = (a); i < (b); i++)
#define REP(i, n) FOR(i, 0, n)

const long N = 1000, K = 10;
long a[N], d[N << K];
vector<pll> adj[N];

int main()
{
  long n, m, k, u, v, w;
  cin >> n >> m >> k;
  REP(i, n) {
    long t;
    for (cin >> t; t--; ) {
      cin >> w;
      a[i] |= 1 << w-1;
    }
  }
  while (m--) {
    cin >> u >> v >> w;
    u--, v--;
    adj[u].emplace_back(v, w);
    adj[v].emplace_back(u, w);
  }
  priority_queue<pll, vector<pll>, greater<pll>> pq;
  fill_n(d, n << K, LONG_MAX/2);
  d[a[0]] = 0;
  pq.emplace(0, a[0]);
  while (pq.size()) {
    tie(w, u) = pq.top();
    pq.pop();
    if (d[u] < w) continue;
    for (pll& e: adj[u >> K]) {
      long v = e.first << K | u & (1<<K)-1 | a[e.first];
      if (d[u] + e.second < d[v]) {
        d[v] = d[u] + e.second;
        pq.emplace(d[v], v);
      }
    }
  }
  long ans = LONG_MAX;
  REP(i, 1 << k)
    for (long j = i; ; j = j-1 & i) {
      ans = min(ans, max(d[(n-1) << K | i], d[(n-1) << K | (1 << k) - 1 - i | j]));
      if (! j) break;
    }
  cout << ans << endl;
}

Synchronous Shopping C Sharp Solution

using System.CodeDom.Compiler;
using System.Collections.Generic;
using System.Collections;
using System.ComponentModel;
using System.Diagnostics.CodeAnalysis;
using System.Globalization;
using System.IO;
using System.Linq;
using System.Reflection;
using System.Runtime.Serialization;
using System.Text.RegularExpressions;
using System.Text;
using System;

class Result
{

    /*
     * Complete the 'shop' function below.
     *
     * The function is expected to return an INTEGER.
     * The function accepts following parameters:
     *  1. INTEGER n
     *  2. INTEGER k
     *  3. STRING_ARRAY centers
     *  4. 2D_INTEGER_ARRAY roads
     */

    public static int shop(int n, int k, List<string> centers, List<List<int>> roads)
        {

            int m = roads.Count, n1 = 0, n2 = 0, n3 = 0, v1,v2,v3;
            int inf = int.MaxValue;
            int[,] dist = new int[n + 1, 1025];
            int[] a = new int[n + 1];



            List<ValueTuple<int, int>>[] edges = new List<(int, int)>[n + 1];

            for (int i = 1; i <= n; i++)
            {
                edges[i] = new List<(int, int)>();
            }

            for (int i = 0; i < centers.Count; i++)
            {

                string s = centers[i];
                n1 = Convert.ToInt32(s.Split(' ')[0]);

                for (int j = 1; j <= n1; j++)
                {
                    n2 = Convert.ToInt32(s.Split(' ')[j]);
                    a[i + 1] |= 1 << (n2 - 1);
                }
            }
            for (int i = 0; i < m; i++)
            {
                n1 = roads[i][0]; n2 = roads[i][1]; n3 = roads[i][2];
                edges[n1].Add((n2, n3));
                edges[n2].Add((n1, n3));
            }
            for (int i = 1; i <= n; i++)
            {
                for (int j = 0; j < (1 << k); j++)
                {
                    dist[i, j] = inf;
                }
            }
            Queue<(int, int)> q = new Queue<(int, int)>();

            
            dist[1, a[1]] = 0;
            q.Enqueue((1, a[1]));
            while (q.Count > 0)
            {

                var tt = q.Peek();
                n2 = tt.Item2;
                n1 = tt.Item1;
                n3 = dist[n1, n2];
                q.Dequeue();
                for (int i = 0; i < edges[n1].Count; i++)
                {
                    v1 = edges[n1][i].Item1; v2 = n2 | a[edges[n1][i].Item1];v3 = n3 + edges[n1][i].Item2;
                    if (dist[v1, v2] <= v3) continue;
                    
                    dist[v1, v2] = v3;
                    q.Enqueue((v1, v2));
                }
            }


            int res = int.MaxValue;

            for (int i = 0; i < (1 << k); i++)
            {
                for (int j = 1; j < (1 << k); j++)
                {
                    if ((i | j) == (1 << k) - 1)
                        res = Math.Min(res, (Math.Max(dist[n, i], dist[n, j])));

                }
            }
            return res;
        }
}

class Solution
{
    public static void Main(string[] args)
    {
        TextWriter textWriter = new StreamWriter(@System.Environment.GetEnvironmentVariable("OUTPUT_PATH"), true);

        string[] firstMultipleInput = Console.ReadLine().TrimEnd().Split(' ');

        int n = Convert.ToInt32(firstMultipleInput[0]);

        int m = Convert.ToInt32(firstMultipleInput[1]);

        int k = Convert.ToInt32(firstMultipleInput[2]);

        List<string> centers = new List<string>();

        for (int i = 0; i < n; i++)
        {
            string centersItem = Console.ReadLine();
            centers.Add(centersItem);
        }

        List<List<int>> roads = new List<List<int>>();

        for (int i = 0; i < m; i++)
        {
            roads.Add(Console.ReadLine().TrimEnd().Split(' ').ToList().Select(roadsTemp => Convert.ToInt32(roadsTemp)).ToList());
        }

        int res = Result.shop(n, k, centers, roads);

        textWriter.WriteLine(res);

        textWriter.Flush();
        textWriter.Close();
    }
}

Synchronous Shopping Java Solution

import java.util.*;

public class Solution {
  public static class Edge {
    public int node;
    public int distance;

    public Edge(int node, int distance) {
      this.node = node;
      this.distance = distance;
    }
  }

  public static class Waypoint {
    public int node;
    public int mask;
    public int distance;

    public Waypoint(int node, int mask, int distance) {
      this.node = node;
      this.mask = mask;
      this.distance = distance;
    }

    public String toString() {
      return node + " " + Integer.toBinaryString(mask) + " " + distance;
    }
  }

  public static class WaypointComparator implements Comparator<Waypoint> {
    @Override
    public int compare(Waypoint wp1, Waypoint wp2) {
      if (wp1.distance > wp2.distance) return 1;
      else if (wp1.distance < wp2.distance) return -1;
      return 0;
    }
  }

  static int N, M, K;
  static HashMap<Integer, ArrayList<Edge>> edges = new HashMap<>();
  static HashMap<Integer, HashMap<Integer, Integer>> messages = new HashMap<>();

  static PriorityQueue<Waypoint> queue = new PriorityQueue<>(1000, new WaypointComparator());

  static int[] fishTypes;
  static int happyCats;
  static int[][] distances;

  public static void route(int i) {
    boolean[] visited = new boolean[N];
    PriorityQueue<Waypoint> dijkstra = new PriorityQueue<>(1000, new WaypointComparator());
    dijkstra.add(new Waypoint(i, -1, 0));

    while (!dijkstra.isEmpty()) {
      Waypoint wp = dijkstra.poll();
      if (visited[wp.node]) continue;
      visited[wp.node] = true;

      boolean validEnd = fishTypes[wp.node] != 0 || wp.node == 0 || wp.node == N - 1;
      if (wp.node != i && validEnd) {
        edges.get(i).add(new Edge(wp.node, wp.distance));
      } else {
        for (int j = 0; j < N; j++) {
          if (visited[j]) continue;
          if (distances[wp.node][j] == -1) continue;
          dijkstra.add(new Waypoint(j, -1, wp.distance + distances[wp.node][j]));
        }
      }
    }
  }

  public static long fanout(Waypoint wp) {
    messages.get(wp.node).put(wp.mask, wp.distance);

    if (wp.node == N - 1) {
      long minTime = Long.MAX_VALUE;
      for (Map.Entry<Integer, Integer> entry : messages.get(N - 1).entrySet())
        if ((wp.mask | entry.getKey()) == happyCats)
          minTime = Math.min(minTime, Math.max(wp.distance, entry.getValue()));
      if (minTime < Integer.MAX_VALUE) return minTime;
    }

    for (Edge neighborEdge : edges.get(wp.node)) {
      Waypoint nwp =
          new Waypoint(
              neighborEdge.node,
              wp.mask | fishTypes[neighborEdge.node],
              wp.distance + neighborEdge.distance);

      if (messages.get(nwp.node).containsKey(nwp.mask)) {
        if (nwp.distance < messages.get(nwp.node).get(nwp.mask)) {
          queue.add(nwp);
        }
      } else {
        queue.add(nwp);
      }
    }

    return -1;
  }

  public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);

    N = scanner.nextInt();
    M = scanner.nextInt();
    K = scanner.nextInt();

    fishTypes = new int[N];
    happyCats = 0;

    distances = new int[N][N];
    for (int n = 0; n < N; n++) {
      distances[n][n] = 0;
      Arrays.fill(distances[n], -1);
    }

    for (int k = 0; k < K; k++) happyCats |= 1 << k;
    int zeroes = 0;
    for (int n = 0; n < N; n++) {
      int T = scanner.nextInt();
      if (T == 0) zeroes++;
      for (int t = 0; t < T; t++) {
        fishTypes[n] |= 1 << (scanner.nextInt() - 1);
      }
      edges.put(n, new ArrayList<>());
      messages.put(n, new HashMap<>());
    }

    // if graph contains a lot of void nodes (no shopping centers)
    // we can squeeze it to a smaller one
    if (zeroes > N * 0.8) {
      for (int m = 0; m < M; m++) {
        int X = scanner.nextInt() - 1, Y = scanner.nextInt() - 1, D = scanner.nextInt();
        distances[X][Y] = D;
        distances[Y][X] = D;
      }

      for (int i = 0; i < N; i++) if (fishTypes[i] != 0 || i == 0 || i == N - 1) route(i);
    } else {
      for (int m = 0; m < M; m++) {
        int X = scanner.nextInt() - 1, Y = scanner.nextInt() - 1, D = scanner.nextInt();
        edges.get(X).add(new Edge(Y, D));
        edges.get(Y).add(new Edge(X, D));
      }
    }

    // brute force solution in optimized graph
    queue.add(new Waypoint(0, fishTypes[0], 0));
    while (!queue.isEmpty()) {
      long result = fanout(queue.poll());
      if (result != -1) {
        System.out.println(result);
        return;
      }
    }
  }
}

Synchronous Shopping JavaScript Solution

'use strict';

const fs = require('fs');

process.stdin.resume();
process.stdin.setEncoding('utf-8');

let inputString = '';
let currentLine = 0;

process.stdin.on('data', function(inputStdin) {
    inputString += inputStdin;
});

process.stdin.on('end', function() {
    inputString = inputString.split('\n');

    main();
});

function readLine() {
    return inputString[currentLine++];
}

/*
 * Complete the 'shop' function below.
 *
 * The function is expected to return an INTEGER.
 * The function accepts following parameters:
 *  1. INTEGER n
 *  2. INTEGER k
 *  3. STRING_ARRAY centers
 *  4. 2D_INTEGER_ARRAY roads
 */

function shop(n, k, centers, roads) {
    const r = roads.reduce((acc, [a, b, cost]) => {
        if (!acc[a]) {
            acc[a] = [];
        }
        if (!acc[b]) {
            acc[b] = [];
        }
        acc[a].push([b, cost]);
        acc[b].push([a, cost]);
        return acc;
    }, new Array(n + 1));

    const lowest = [];
    for (let i = 0; i < n + 1; i += 1) {
        lowest.push(new Array(2 ** k).fill(null));
    }

    const c = centers.map(
        (item) => item.split(` `).slice(1).reduce((acc, it) => acc + 2 ** (it - 1), 0)
    );
    lowest[1][c[0]] = 0;

    const queue = [1];

    while (queue.length) {
        const center = queue.shift();
        r[center].forEach(([to, cost]) => {
            let isRefreshed = false;
            const fishes = c[to - 1];
            lowest[center].forEach((item, i) => {
                if (lowest[center][i] === null) {
                    return;
                }
                const b = (i | fishes);
                if (!lowest[to][b] || lowest[to][b] > item + cost) {
                    lowest[to][b] = item + cost;
                    isRefreshed = true;
                }
            });
            if (isRefreshed) {
                queue.push(to);
            }
        });
    }

    let min = lowest[n][2 ** k - 1] || Infinity;
    for (let i = 0; i < lowest[n].length - 1; i += 1) {
        if (!lowest[n][i]) {
            continue;
        }
        for (let j = i + 1; j < lowest[n].length; j += 1) {
            if (!lowest[n][j]) {
                continue;
            }
            if ((i | j) === 2 ** k - 1) {
                min = Math.min(min, Math.max(lowest[n][i], lowest[n][j]));
            }
        }
    }

    return min;
}

function main() {
    const ws = fs.createWriteStream(process.env.OUTPUT_PATH);

    const firstMultipleInput = readLine().replace(/\s+$/g, '').split(' ');

    const n = parseInt(firstMultipleInput[0], 10);

    const m = parseInt(firstMultipleInput[1], 10);

    const k = parseInt(firstMultipleInput[2], 10);

    let centers = [];

    for (let i = 0; i < n; i++) {
        const centersItem = readLine();
        centers.push(centersItem);
    }

    let roads = Array(m);

    for (let i = 0; i < m; i++) {
        roads[i] = readLine().replace(/\s+$/g, '').split(' ').map(roadsTemp => parseInt(roadsTemp, 10));
    }

    const res = shop(n, k, centers, roads);

    ws.write(res + '\n');

    ws.end();
}

Synchronous Shopping Python Solution

#!/bin/python3


import math
import os
import random
import re
import sys
import heapq as pq
from collections import defaultdict
from collections import deque
# Complete the 'shop' function below.
#
# The function is expected to return an INTEGER.
# The function accepts following parameters:
#  1. INTEGER n
#  2. INTEGER k
#  3. STRING_ARRAY centers
#  4. 2D_INTEGER_ARRAY roads
#

def getFishset(k,centers,bitset):
    for centerN in range(0,len(centers)):
        centers[centerN] = centers[centerN].rstrip().split()
        limit = int(centers[centerN][0])
        for each_f in range(1,limit + 1 ) :
            bitset[centerN + 1] |= 1 << (int(centers[centerN][each_f]) - 1)
    return bitset  
def getPath(n, k, centers, roads, bitset, graph):
    hQ = []
    power2 = int(math.pow(2,k))
    dist = [[999999 for j in range(0, power2 )]  for each in range(0,n + 1 )]
    visited = [[0 for j in range(0, int(math.pow(2,k)) )]  for each in range(0,n + 1 )]
    bitset = getFishset(k,centers,bitset)
    pq.heappush(hQ,(0,1,bitset[1]))
    dist[1][bitset[1]] = 0
    while len(hQ) != 0:
        distance,centerN,eachSet = pq.heappop(hQ)
        #if dist[centerN] == distance :
        if visited[centerN][eachSet] == 1:
            continue
        visited[centerN][eachSet] = 1
        for neighbor in graph[centerN]:
            bitadd = eachSet|bitset[neighbor[0]]
            f_dist = distance + neighbor[1]#roads[centerN][neighbor]
            if f_dist < dist[neighbor[0]][bitadd]:
                dist[neighbor[0]][bitadd] = f_dist
                pq.heappush(hQ,(dist[neighbor[0]][bitadd],neighbor[0],bitadd))
    totalCost  = 999999
    range_l = len(dist[n])
    for i in range(range_l - 1, 0, -1):
        if dist[n][i] == 999999:
            continue 
        if i  == (power2 - 1) and dist[n][i] < totalCost:
            totalCost = dist[n][i]
            continue
        for j in range(1,i):
            if i | j == (power2 - 1) and max(dist[n][i] , dist[n][j]) < totalCost:
                totalCost = max(dist[n][i] , dist[n][j])
    return totalCost
def shop(n, k, centers, roads):
    # Write your code here
    bitset = [0 for each in range(0, n + 1)]
    graph = defaultdict(list)
    #roadsG = defaultdict(defaultdict)
    for each in roads:
        graph[each[0]].append((each[1],each[2]))
        graph[each[1]].append((each[0],each[2]))
        #roadsG[each[0]][each[1]] = each[2]
        #roadsG[each[1]][each[0]] = each[2]
    totalCost = getPath(n, k, centers, roads, bitset, graph) 
    return totalCost
if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    first_multiple_input = input().rstrip().split()

    n = int(first_multiple_input[0])

    m = int(first_multiple_input[1])

    k = int(first_multiple_input[2])

    centers = []

    for _ in range(n):
        centers_item = input()
        centers.append(centers_item)

    roads = []

    for _ in range(m):
        roads.append(list(map(int, input().rstrip().split())))

    res = shop(n, k, centers, roads)

    fptr.write(str(res) + '\n')

    fptr.close()

c C# C++ HackerRank Solutions java javascript python C cpp CSharp Hackerrank Solutions java javascript python