HackerRank Clues on a Binary Path problem solution

In this HackerRank Clues on a Binary Path problem solution, Logan and Veronica live in Neptune, which has n houses and m bidirectional roads connecting them. Each road has an assigned value, ci, where ci ∈ {0,1}, and each house is numbered with a distinct integer from 1 to n.

Logan and Veronica are looking for clues and need to find the number of different paths of length d from house number 1. Each path is characterized by a binary sequence of length d, where each integer j in the path is the value of cj for the jth edge in the path. Two paths are different if the binary sequences characterizing these paths are distinct. Note that they may need to visit the same house several times or use the same road several times to find all possible paths.

Given a map of Neptune, help Logan and Veronica find and print the number of different paths of length d from house number 1 to the other houses in Neptune.

HackerRank Clues on a Binary Path problem solution in Java.

import java.io.*;
import java.util.StringTokenizer;

public class Solution {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);

        int n = in.nextInt();
        int m = in.nextInt();
        int d = in.nextInt();

        if (
                !(1 <= n && n <= 70) ||
                !(0 <= m && m <= n * (n - 1)) ||
                !(1 <= d && d <= 20))
            throw new RuntimeException();

        int[] x = new int[m];
        int[] y = new int[m];
        int[] w = new int[m];

        for (int i = 0; i < m; ++i) {
            x[i] = in.nextInt(); x[i]--;
            y[i] = in.nextInt(); y[i]--;
            if (!(0 <= x[i] && x[i] < n) || !(0 <= y[i] && y[i] < n))
                throw new RuntimeException();
            w[i] = in.nextInt();
            if (!(0 <= w[i] && w[i] <= 1))
                throw new RuntimeException();
        }

        int l = (d + 1) / 2;

        int[][] dp =  new int[n][1 << l];
        int[][] ndp = new int[n][1 << l];

        for (int i = 0; i < n; ++i)
            for (int j = 0; j < (1 << l); ++j)
                dp[i][j] = ndp[i][j] = 0;

        dp[0][0] = 1;
        for (int i = 0; i < n; ++i)
            dp[i][0] |= 2;

        for (int c = 0; c < l; ++c) {
            for (int i = 0; i < m; ++i) {
                int u = x[i];
                int v = y[i];
                int b = w[i];

                for (int t = 0; t < (1 << c); ++t) {
                    ndp[u][(t << 1) | b] |= dp[v][t];
                    ndp[v][(t << 1) | b] |= dp[u][t];
                }
            }

            if (c + 1 < l) {
                for (int i = 0; i < n; ++i) {
                    for (int j = 0; j < (1 << (c + 1)); ++j) {
                        dp[i][j] = ndp[i][j];
                        ndp[i][j] = 0;
                    }
                }
            }
        }

        Boolean[] can = new Boolean[1 << d];
        for (int i = 0; i < (1 << d); ++i)
            can[i] = false;

        int r = d - l;
        for (int v = 0; v < n; ++v) {
            for (int t = 0; t < (1 << r); ++t) {
                int c = (l == r ? ndp[v][t] : dp[v][t]);
                if ((c & 1) == 0)
                    continue;
                for (int s = 0; s < (1 << l); ++s) {
                    if ((ndp[v][s] & 2) > 0)
                        can[(t << l) ^ s] = true;
                }
            }
        }

        int res = 0;
        for (int i = 0; i < (1 << d); ++i)
            if (can[i])
                res++;

        out.println(res);
        out.close();
    }
}

class InputReader {
    private final BufferedReader reader;
    private StringTokenizer tokenizer;

    public InputReader(InputStream stream) {
        reader = new BufferedReader(new InputStreamReader(stream));
        tokenizer = null;
    }

    public String nextLine() {
        try {
            return reader.readLine();
        } catch (IOException e) {
            throw new RuntimeException(e);
        }
    }

    public String next() {
        while (tokenizer == null || !tokenizer.hasMoreTokens()) {
            tokenizer = new StringTokenizer(nextLine());
        }
        return tokenizer.nextToken();
    }

    public int nextInt() {
        return Integer.parseInt(next());
    }

}

Clues on a Binary Path problem solution in C++.

#include <stdio.h>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
  
using namespace std;
   
#define pb push_back
#define mp make_pair
#define F first
#define S second

const int N = 99;
const int L = 13;

int n, m, l;
bool used[(1 << 20) + 100];
bool canMake[N][(1 << 10) + 100];
bool f[N][N][L][(1 << 10) + 100];
vector< pair<int, int> > g[N];

int main() {
    scanf("%d%d%d", &n, &m, &l);
    for (int i = 1; i <= m; i++) {
        int u, v, c;
        scanf("%d%d%d", &u, &v, &c);
        g[u].pb(mp(v, c));
        g[v].pb(mp(u, c));
    }
    queue<int> q_start, q_ver, q_len, q_mask;
    for (int i = 1; i <= n; i++) {
        f[i][i][0][0] = true;
        q_start.push(i);
        q_ver.push(i);
        q_len.push(0);
        q_mask.push(0);
    }
    int maxMoves = (l + 1) / 2;
    while (!q_start.empty()) {
        int start = q_start.front();
        int ver = q_ver.front();
        int len = q_len.front();
        int mask = q_mask.front();
        q_start.pop(); q_ver.pop(); q_len.pop(); q_mask.pop();
        if (len == maxMoves) {
            continue;
        }
        for (int i = 0; i < (int)g[ver].size(); i++) {
            int to = g[ver][i].F;
            int bit = g[ver][i].S;
            int newMask = mask;
            if (bit == 1) {
                newMask += (1 << len);
            }
            if (f[start][to][len + 1][newMask] == false) {
                f[start][to][len + 1][newMask] = true;
                q_start.push(start);
                q_ver.push(to);
                q_len.push(len + 1);
                q_mask.push(newMask);
            }
        }
    }
    int maxMask = (1 << maxMoves);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            for (int mask = 0; mask < maxMask; mask++) {
                if (f[i][j][maxMoves][mask]) {
                    canMake[j][mask] = true;
                }
            }
        }
    }
    int lengthOfFirstPart = l - maxMoves;
    int maxMask2 = (1 << lengthOfFirstPart);
    for (int ver = 1; ver <= n; ver++) {
        for (int m1 = 0; m1 < maxMask2; m1++) {
            if (f[1][ver][lengthOfFirstPart][m1]) {
                for (int m2 = 0; m2 < maxMask; m2++) {
                    if (canMake[ver][m2]) {
                        used[(m1 << maxMoves) + m2] = true;
                    }
                }
            }
        }
    }
    int ans = 0;
    int maxMaskOverall = (1 << l);
    for (int i = 0; i < maxMaskOverall; i++) {
        if (used[i]) {
            ++ans;
        }
    }
    printf("%dn", ans);
    return 0;
}

HackerRank Clues on a Binary Path problem solution

HackerRank Clues on a Binary Path problem solution in Java.

Clues on a Binary Path problem solution in C++.

Pages

Practice