OpenAI

package main

import (
	"bufio"
	"flag"
	"fmt"
	"io"
	"log"
	"os"
	"strings"
)


type Tile struct {
	char rune
	row  int
	col  int
}

const (
	
	OPENING = '.'

	
	OBSTRUCTION = '#'

	
	
	ROUTE = '+'
)


type Maze struct {
	grid [][]Tile
	rows int
	cols int
}









func NewMaze(r io.Reader) *Maze {
	maze := &Maze{
		grid: make([][]Tile, 0),
		rows: 0,
		cols: 0,
	}

	scanner := bufio.NewScanner(r)
	for scanner.Scan() {
		row := make([]Tile, 0)
		col := 0
		for _, char := range scanner.Text() {
			var t rune
			switch char {
			case '0':
				t = OPENING
			case '1':
				t = OBSTRUCTION
			default:
				continue
			}
			row = append(row, Tile{
				char: t,
				row:  maze.rows,
				col:  col,
			})
			col++
		}
		maze.grid = append(maze.grid, row)
		maze.rows++
	}

	
	
	
	for _, row := range maze.grid {
		maze.cols = len(row)
		break
	}

	return maze
}




func (maze *Maze) Solve() (steps uint) {
	start := &maze.grid[0][0]
	if start.char != OPENING {
		
		
		
		
		return
	}

	end := &maze.grid[maze.rows-1][maze.cols-1]

	visited := make(map[*Tile]bool)

	predecessors := make(map[*Tile]*Tile)

	var queue []*Tile
	queue = append(queue, start)

	for len(queue) > 0 {
		t := queue[0]
		queue = queue[1:]

		if t == end {
			break
		}

		nbrs := make([]*Tile, 0, 4)

		
		
		if t.row > 0 {
			nbrs = append(nbrs, &maze.grid[t.row-1][t.col])
		}
		if t.row < maze.rows-1 {
			nbrs = append(nbrs, &maze.grid[t.row+1][t.col])
		}
		if t.col > 0 {
			nbrs = append(nbrs, &maze.grid[t.row][t.col-1])
		}
		if t.col < maze.cols-1 {
			nbrs = append(nbrs, &maze.grid[t.row][t.col+1])
		}

		for _, neighbor := range nbrs {
			
			if neighbor.char == OBSTRUCTION {
				continue
			}

			
			if visited[neighbor] {
				continue
			}

			visited[neighbor] = true
			predecessors[neighbor] = t
			queue = append(queue, neighbor)
		}
	}

	
	if !visited[end] {
		return
	}

	start.char = ROUTE
	steps = 1
	for t := end; t != start; t = predecessors[t] {
		t.char = ROUTE
		steps++
	}

	return
}

func (maze *Maze) String() string {
	var builder strings.Builder

	
	boxTopBottom := "|" + strings.Repeat("-", 2*maze.cols+1) + "|\n"

	builder.WriteString(boxTopBottom)

	for i, row := range maze.grid {
		if i == 0 {
			builder.WriteRune(' ')
		} else {
			builder.WriteRune('|')
		}

		for _, tile := range row {
			builder.WriteRune(' ')
			builder.WriteRune(tile.char)
		}

		builder.WriteRune(' ')

		if i == len(maze.grid)-1 {
			builder.WriteRune(' ')
		} else {
			builder.WriteRune('|')
		}

		builder.WriteRune('\n')
	}

	builder.WriteString(boxTopBottom)

	return builder.String()
}

func main() {
	var (
		printStart          bool
		printSolutionLength bool
		printSolution       bool
		infile, outfile     string
	)

	flag.BoolVar(&printStart, "d", false,
		"Pretty-print (display) the maze after reading.")
	flag.BoolVar(&printSolutionLength, "s", false,
		"Print length of shortest path or 'No solution'.")
	flag.BoolVar(&printSolution, "p", false,
		"Pretty-print maze with the path, if one exists.")

	flag.StringVar(&infile, "i", "",
		"Read maze from infile. (default: stdin)")
	flag.StringVar(&outfile, "o", "",
		"Write all output to outfile. (default: stdout)")

	flag.Parse()

	var (
		in  io.Reader
		out io.Writer
	)
	if infile == "" {
		in = os.Stdin
	} else {
		var err error
		in, err = os.Open(infile)
		if err != nil {
			log.Fatalf("failed to open '%s': %v\n", infile, err)
		}
		f := in.(*os.File)
		defer f.Close()
	}
	if outfile == "" {
		out = os.Stdout
	} else {
		var err error
		out, err = os.Create(outfile)
		if err != nil {
			log.Fatalf("failed to open '%s': %v\n", outfile, err)
		}
		f := in.(*os.File)
		defer func() {
			if err := f.Close(); err != nil {
				log.Fatalf("failed to close outfile '%s': %v\n",
					err)
			}
		}()
	}

	maze := NewMaze(in)

	if printStart {
		fmt.Fprint(out, maze.String())
	}

	if steps := maze.Solve(); printSolutionLength {
		if steps == 0 {
			fmt.Fprintln(out, "No solution.")
		} else {
			fmt.Fprintf(out, "Solution in %v steps.\n", steps)
		}
	}

	if printSolution {
		fmt.Fprint(out, maze.String())
	}
}