package main

import (
	"bufio"
	"fmt"
	"math"
	"os"
	"sort"

	//"slices"
	"strconv"
	"strings"
)

var red_walls [][2]int
var the_map map[[2]int]byte
var max_x,min_x int
var max_y,min_y int

func main() {
	fmt.Println("Advent of Code 2025 - Day 9 - Part 2")
	f,_:= os.Open("9/test")
	defer f.Close()
	scanner:=bufio.NewScanner(f)
	max_x = 0
	min_x = math.MaxInt
	max_y = 0
	min_y = math.MaxInt
	the_map = make(map[[2]int]byte)
	for scanner.Scan(){
		line:= scanner.Text()
		line_sp := strings.Split(line, ",")
		x,_:= strconv.Atoi(line_sp[0])
		y,_:= strconv.Atoi(line_sp[1])
		max_x = max(x,max_x)
		min_x = min(x,min_x)
		max_y = max(y,max_y)
		min_y = min(y,min_y)
		red_walls = append(red_walls, [2]int{x,y})
		the_map[[2]int{x,y}] = '#'
	}
	construct_border()
	store_borders()
	print_map()
	res := int64(0)
	for i:= range red_walls {
		w1:= red_walls[i]
		for j:= i+1; j < len(red_walls); j++{
		w2:= red_walls[j]
			if (is_valid_area(w1,w2)){
				area := calculate_area2(w1,w2)
				if area > res {
					//				fmt.Println(w1,w2)
					res = area
				}
			}
		}
	}
	fmt.Println(row_borders)
	fmt.Println(col_borders)
	fmt.Println(res)
}


var row_borders = map[int][]int{}
var col_borders = map[int][]int{}

func store_borders(){
	for p := range the_map {
		x,y := p[0], p[1]
		row_borders[y] = append(row_borders[y],x)
		col_borders[x] = append(col_borders[x],y)
	}
	for y:= range row_borders{
		sort.Ints(row_borders[y])
	}

	for x:= range col_borders{
		sort.Ints(col_borders[x])
	}
}


func print_map(){
	for i := range 15 {
		for j:= range 15{
			c,ok := the_map[[2]int{j,i}]
			if ok {
				fmt.Printf(string(c))
			} else {
				fmt.Printf(".")
			}
		}
		fmt.Printf("\n")
	}
}


func construct_border() {
	for i:= 0; i < len(red_walls); i++{
		px,py := red_walls[(i+1)%len(red_walls)][0], red_walls[(i+1)%len(red_walls)][1]
		x,y:= red_walls[i][0], red_walls[i][1]

		if x == px {
			//points from min(y,py) to max(y,py)
			for ln := min(y,py)+1; ln < max(y,py); ln++{
				the_map[[2]int{x,ln}] = 'O'
			}
		}

		if y == py {
			//points from min(x,px) to max(x,px)
			for ln := min(x,px)+1; ln < max(x,px); ln++{
				the_map[[2]int{ln,y}] = 'O'
			}
		}
	}
}
	
// Given a point []int{x,y} look for the border to the 4 directions (W,N,E,S)
// B_W should have same y and <= x
// B_E should have same y and >= x
// B_N should have same x and >= y
// B_S should have same x and <= y
// if all borders are found then the point is a green or red wall
// otherwise it's out of boundaries
var green_cache = map[[2]int]bool{}

func is_green(w [2]int) bool {
	if v, ok := green_cache[w]; ok {
		return v
    }
	ok_bw,ok_be := false,false
	ok_bn,ok_bs := false,false
	glob_ok := true
	x,y := w[0],w[1]
	
	_,ok:= the_map[w]
	if ok  {
		green_cache[w] = true
		return true
	}

	xs, ok := row_borders[y]
	if !ok{
		green_cache[w] = false
		return false
	}

	ys, ok:= col_borders[x]
	if !ok{
		green_cache[w] = false
		return false
	}

	i := sort.SearchInts(xs,x)
	ok_be = (i!=0)
	ok_bw = (i!=len(xs))
	glob_ok = glob_ok && ok_be && ok_bw
	if !glob_ok {
		green_cache[w] = false
		return false
	}
	j:= sort.SearchInts(ys,y)
	ok_bn = (j!=0)
	ok_bs = (j!=len(ys))
	glob_ok = glob_ok && ok_bn && ok_bs
	green_cache[w] = glob_ok
	return glob_ok
} 

func is_valid_area(w1,w2 [2]int) bool{
	x1,y1:=w1[0],w1[1]
	x2,y2:=w2[0],w2[1]
	w3 := [2]int{x1,y2}
	w4 := [2]int{x2,y1}
	return is_valid_line(w1,w4) && is_valid_line(w2,w4) && is_valid_line(w2,w3) && is_valid_line(w3,w1)
}

var valid_line_cache = map[[2][2]int]bool{}

func is_valid_line(w1,w2 [2]int) bool{
	if v, ok := valid_line_cache[[2][2]int{w1,w2}]; ok {
		return v
    }
	x1,y1:=w1[0],w1[1]
	x2,y2:=w2[0],w2[1]
	if x1 == x1 && y1 == y2 {
		valid_line_cache[[2][2]int{w1,w2}] = true
		return true
	}
	if x1 == x2 {
		start_y := min(y1,y2)
		end_y := max(y1,y2)
		for i:= start_y; i <= end_y; i++{
			if (!is_green([2]int{x1,i})){
				valid_line_cache[[2][2]int{w1,w2}] = false
				return false
			}
		}
	} else if y1 == y2 {
		start_x := min(x1,x2)
		end_x := max(x1,x2)
		for i:= start_x; i <= end_x; i++{
			if (!is_green([2]int{i,y1})){
				valid_line_cache[[2][2]int{w1,w2}] = false
				return false
			}
		}
	} else {
		valid_line_cache[[2][2]int{w1,w2}] = false
		return false
	}
	valid_line_cache[[2][2]int{w1,w2}] = true
	return true
}


func calculate_area2(w1,w2 [2]int) int64{
	dx, dy := int64(math.Abs(float64(w1[0]-w2[0]))), int64(math.Abs(float64(w1[1]-w2[1])))
	return (dx+1) * (dy+1)
}