LoginSignup
0

More than 3 years have passed since last update.

HackerRank - Snakes and Ladders: The Quickest Way Up

Last updated at Posted at 2021-02-02
package main

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

 // Complete the quickestWayUp function below.
 type Queue []int32
 func (q *Queue)Enque(s int32){
     *q=append(*q,s)
 }
 func (q *Queue)Deque()(int32,error){
     if q.isEmpty(){
         return -1,fmt.Errorf("the q is empty")
     }
     v:=(*q)[0]
     *q=(*q)[1:]
     return v,nil
 }
 func (q *Queue)Peek()(int32,error){
     if q.isEmpty(){
         return -1,fmt.Errorf("the q is empty")
     }
     return (*q)[len(*q)],nil
 }
 func (q *Queue)Size()int{
     return len(*q)
 }
 func (q *Queue)isEmpty()bool{
     return q.Size()==0
 }
 func NewQueue()*Queue{
     s:=new(Queue)
     return s
 }
 var color []int32
 var M [][]int32
 var Q *Queue
 var d []int32
 var n int32
 //color white:-1,gray:0,black:1
 const(
     white=-1
     gray=0
     black=1
     INFTY=-1
     )
 func bfs(s int32){ //s=start index
     color[s]=gray
     d[s]=0
     Q.Enque(s)
     for !Q.isEmpty(){
         u,e:=Q.Deque()
         if e!=nil{
             panic(e)
         }
         for _,v:=range M[u]{
             if color[v]==white{
                 color[v]=gray
                 d[v]=d[u]+1
                 Q.Enque(v)
             }
         }
         color[u]=black
         //fmt.Println("Q",Q)
     }
 }
 // Init initializes variables for bfs.
 func Init(){
     Q = NewQueue()
     d=make([]int32,n)
     color=make([]int32,n)
     var i int32
     for i=0;i<n;i++{
         color[i]=white
         d[i]=INFTY
     }
 }
 func containsInLadStart(x int32,sl [][]int32)int32{
     for i:=0;i<len(sl);i++{
         if x==sl[i][0]{
             return int32(i)
         }
     }
     return -1
 }
 func containsInSnakeStart(x int32,sl [][]int32)int32{
     for i:=0;i<len(sl);i++{
         if x==sl[i][0]{
             return int32(i)
         }
     }
     return -1
 }
 func quickestWayUp(ladders [][]int32, snakes [][]int32) int32 {
     n=100
     M=make([][]int32,n)
     var i,j int32
     for i=0;i<n;i++{
         if k:=containsInLadStart(i,ladders);k>=0 && ladders[k][0]==i{
             continue
         }else if k:=containsInSnakeStart(i,snakes);k>=0 && snakes[k][0]==i{
             continue
         }
         for j=1;j<=6;j++{
             t:=i+j
             if k:=containsInLadStart(t,ladders);k>=0{
                 M[i]=append(M[i],ladders[k][1])
             }else if k:=containsInSnakeStart(t,snakes);k>=0{
                 M[i]=append(M[i],snakes[k][1])
             }else if i+j<100{
                 M[i]=append(M[i],t)
             }
         }
     }
     // fmt.Println("ladders",ladders)
     // fmt.Println("snakes",snakes)
     // for i=0;i<n;i++{
     //     fmt.Println(i,M[i])
     // }
     // fmt.Println(containsInLadStart(31,ladders))
     Init()
     bfs(0)
     //fmt.Println("d",d)
     return d[99]
 }

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

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

     defer stdout.Close()

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

     tTemp, err := strconv.ParseInt(readLine(reader), 10, 64)
     checkError(err)
     t := int32(tTemp)

     for tItr := 0; tItr < int(t); tItr++ {
         nTemp, err := strconv.ParseInt(readLine(reader), 10, 64)
         checkError(err)
         n := int32(nTemp)

         var ladders [][]int32
         for i := 0; i < int(n); i++ {
             laddersRowTemp := strings.Split(readLine(reader), " ")

             var laddersRow []int32
             for _, laddersRowItem := range laddersRowTemp {
                 laddersItemTemp, err := strconv.ParseInt(laddersRowItem, 10, 64)
                 checkError(err)
                 laddersItem := int32(laddersItemTemp)-1
                 laddersRow = append(laddersRow, laddersItem)
             }

             if len(laddersRow) != int(2) {
                 panic("Bad input")
             }

             ladders = append(ladders, laddersRow)
         }

         mTemp, err := strconv.ParseInt(readLine(reader), 10, 64)
         checkError(err)
         m := int32(mTemp)

         var snakes [][]int32
         for i := 0; i < int(m); i++ {
             snakesRowTemp := strings.Split(readLine(reader), " ")

             var snakesRow []int32
             for _, snakesRowItem := range snakesRowTemp {
                 snakesItemTemp, err := strconv.ParseInt(snakesRowItem, 10, 64)
                 checkError(err)
                 snakesItem := int32(snakesItemTemp)-1
                 snakesRow = append(snakesRow, snakesItem)
             }

             if len(snakesRow) != int(2) {
                 panic("Bad input")
             }

             snakes = append(snakes, snakesRow)
         }

         result := quickestWayUp(ladders, snakes)

         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)
     }
 }

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
0