Minimum Penalty Path Discussions | Algorithms | HackerRank
We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Algorithms
  3. Graph Theory
  4. Minimum Penalty Path
  5. Discussions

Minimum Penalty Path

Sort by

recency

|

58 Discussions

|

  • fdaliran
     + 0 comments

    For python code, at the begining I had a lot of test cases with time limit. I did a lot of tweaking and solved most of them. However, I could not pass test case 2. I changed the way I read input, as a result the prblem was solved.

    if name == 'main': # Read all input at once using sys.stdin.read() input_data = sys.stdin.read().splitlines()

    # Process the first line to extract n and m
n, m = map(int, input_data[0].split())

# Initialize an empty list for edges
edges = []

# Process each of the next m lines to extract edges
for i in range(1, m + 1):
    edges.append(list(map(int, input_data[i].split())))

# Process the second to last line to extract A and B
A, B = map(int, input_data[m + 1].split())

# Call the function with the parsed data
result = beautifulPath(n, edges, A, B)

# Write the result to the output file
with open(os.environ['OUTPUT_PATH'], 'w') as fptr:
    fptr.write(str(result) + '\n')

  • C_jain
     + 0 comments

    Golang solution just in case someone is looking. NOTE: Dijkstra will not work as explained [here]https://www.hackerrank.com/challenges/beautiful-path/forum/comments/121506). We need to go with brute force as input size is small, so a simple dfs/bfs needed to check all possible distances of a vertex from starting vertex(in this case 'A').

    package main

import (
    "bufio"
    "fmt"
    "io"
    "os"
    "strconv"
    "strings"
    "math"
)

/*
 * Complete the 'beautifulPath' function below.
 *
 * The function is expected to return an INTEGER.
 * The function accepts following parameters:
 *  1. 2D_INTEGER_ARRAY edges
 *  2. INTEGER A
 *  3. INTEGER B
 */

func beautifulPath(n int32, edges [][]int32, A int32, B int32) int32 {
    const INF = int32(1024)
    
    adjList := edgeListToAdjList(n, edges)

    var queue [][]int32
    queue = append(queue, []int32{A, 0})
    
    dist := initDist(n)
    dist[A][0] = true
    
    result := INF
    
    for len(queue) > 0 {
        front := queue[0]
        u := front[0]
        d := front[1]
        
        queue = queue[1:]
        
        for _, edge := range adjList[u] {
            v := edge[0]
            w := edge[1]
            
            newDistForV := d | w
            
            if !dist[v][newDistForV] {
                dist[v][newDistForV] = true
                
                queue = append(queue, []int32{v, newDistForV})
                
                if v == B {
                    result = int32(math.Min(float64(result), float64(newDistForV)))
                }
            }
        }
    }
    
    if result == INF {
        return -1
    }
    
    return result
}

func initDist(V int32) map[int32]map[int32]bool {
    dist := make(map[int32]map[int32]bool)
    
    for i := int32(0); i <= V; i++ {
        dist[i] = make(map[int32]bool)
    }
    
    return dist
}

func edgeListToAdjList(V int32, edgeList [][]int32) [][][]int32 {
    adjList := make([][][]int32, V+1)
    
    for _, edge := range edgeList {
        u := edge[0]
        v := edge[1]
        w := edge[2]
        
        adjList[u] = append(adjList[u], []int32{v, w})
        adjList[v] = append(adjList[v], []int32{u, w})
    }
    
    return adjList
}

func main() {
    reader := bufio.NewReaderSize(os.Stdin, 16 * 1024 * 1024)

    stdout, err := os.Create(os.Getenv("OUTPUT_PATH"))
    checkError(err)

    defer stdout.Close()

    writer := bufio.NewWriterSize(stdout, 16 * 1024 * 1024)

    firstMultipleInput := strings.Split(strings.TrimSpace(readLine(reader)), " ")

    nTemp, err := strconv.ParseInt(firstMultipleInput[0], 10, 64)
    checkError(err)
    n := int32(nTemp)

    mTemp, err := strconv.ParseInt(firstMultipleInput[1], 10, 64)
    checkError(err)
    m := int32(mTemp)

    var edges [][]int32
    for i := 0; i < int(m); i++ {
        edgesRowTemp := strings.Split(strings.TrimRight(readLine(reader)," \t\r\n"), " ")

        var edgesRow []int32
        for _, edgesRowItem := range edgesRowTemp {
            edgesItemTemp, err := strconv.ParseInt(edgesRowItem, 10, 64)
            checkError(err)
            edgesItem := int32(edgesItemTemp)
            edgesRow = append(edgesRow, edgesItem)
        }

        if len(edgesRow) != 3 {
            panic("Bad input")
        }

        edges = append(edges, edgesRow)
    }

    secondMultipleInput := strings.Split(strings.TrimSpace(readLine(reader)), " ")

    ATemp, err := strconv.ParseInt(secondMultipleInput[0], 10, 64)
    checkError(err)
    A := int32(ATemp)

    BTemp, err := strconv.ParseInt(secondMultipleInput[1], 10, 64)
    checkError(err)
    B := int32(BTemp)

    result := beautifulPath(n, edges, A, B)

    fmt.Fprintf(writer, "%d\n", result)

    writer.Flush()
}

func readLine(reader *bufio.Reader) string {
    str, _, err := reader.ReadLine()
    if err == io.EOF {
        return ""
    }

    return strings.TrimRight(string(str), "\r\n")
}

func checkError(err error) {
    if err != nil {
        panic(err)
    }
}

  • yashparihar729
     + 0 comments

    Here is my solution in java, javascript, python, C, C++, csharp HackerRank Minimum Penalty Path Solution

  • seonandla
     + 0 comments

    Hi There! i want to use it for my Gaming Website .

  • mineman1012221
     + 0 comments

    Here is the solution of Minimum Penalty Path Click Here