AoC 2019 Day 25

day25.go

package day25

import (
	"bufio"
	"errors"
	"fmt"
	"io"
	"os"
	"regexp"
	"strings"

	"github.com/Aneurysm9/pathfinder"
)

var (
	roomRE     = regexp.MustCompile(`\=\=\s+([^\=]+)\s+\=\=`)
	doorsRE    = regexp.MustCompile(`Doors here lead:`)
	itemsRE    = regexp.MustCompile(`Items here:`)
	passcodeRE = regexp.MustCompile(`should be able to get in by typing (\d+) on the keypad`)
	errDenied  = errors.New("cannot enter this room")
	badItems   = map[string]bool{
		"giant electromagnet": true,
		"photons":             true,
		"escape pod":          true,
		"molten lava":         true,
		"infinite loop":       true,
	}
	items = []string{}
)

type direction string

func (d direction) opposite() direction {
	switch d {
	case "north":
		return "south"
	case "south":
		return "north"
	case "east":
		return "west"
	case "west":
		return "east"
	}
	return ""
}

type doors map[direction]*room

type room struct {
	name        string
	description string
	d           doors
	items       []string
}

type graph struct{}

type node struct {
	dir direction
	tgt *room
}

func (g graph) Neighbors(src pathfinder.Node) []pathfinder.Edge {
	n, ok := src.(node)
	if !ok {
		panic("Invalid node provided")
	}
	res := []pathfinder.Edge{}
	for k, v := range n.tgt.d {
		res = append(res, pathfinder.Edge{
			Target: node{dir: k, tgt: v},
			Cost:   1,
		})
	}
	return res
}

type Runner struct{}

func (r Runner) PartA(in io.Reader) string {
	m := newVM(readInput(in, 1024))
	go func() {
		m.run()
	}()
	i := bufio.NewReader(m)

	rm := readRoom(i)
	err := rm.explore(i, m, "origin", rm)
	if err != nil {
		panic(err)
	}
	f := pathfinder.NewFinder(graph{})
	path, _, _ := f.AStarFunc(node{dir: "origin", tgt: rm}, func(n pathfinder.Node) bool {
		m := n.(node)
		return m.tgt.name == "Pressure-Sensitive Floor"
	})
	for _, v := range path[1 : len(path)-1] {
		mv := v.(node)
		move(mv.dir, m)
		rm = readRoom(i)
	}

	dropItems(items, i, m)
	lastNode := path[len(path)-1].(node)

	for sz := 1; sz < len(items); sz++ {
		for _, is := range comb(sz, items) {
			takeItems(is, i, m)
			move(lastNode.dir, m)
			if matches := passcodeRE.FindAllStringSubmatch(readToPrompt(i), -1); matches != nil {
				return matches[0][1]
			}
			dropItems(is, i, m)
		}
	}
	return ""
}

func comb(m int, l []string) [][]string {
	out := make([][]string, 0)
	tmp := make([]string, m)
	last := m - 1
	var rc func(int, int)
	rc = func(i, next int) {
		for j := next; j < len(l); j++ {
			tmp[i] = l[j]
			if i == last {
				t2 := make([]string, m)
				copy(t2, tmp)
				out = append(out, t2)
			} else {
				rc(i+1, j+1)
			}
		}
	}
	rc(0, 0)
	return out
}

func (r *room) explore(in *bufio.Reader, out io.Writer, from direction, source *room) error {
	for n, c := range r.d {
		if c != nil {
			continue
		}
		if from == n {
			r.d[n] = source
			continue
		}

		move(n, out)
		r.d[n] = readRoom(in)
		if r.d[n].name == "Pressure-Sensitive Floor" {
			readToPrompt(in)
			continue
		}
		for _, i := range r.d[n].items {
			if badItems[i] {
				continue
			}
			takeItem(i, in, out)
			items = append(items, i)
		}
		r.d[n].items = []string{}
		if err := r.d[n].explore(in, out, n.opposite(), r); err == nil {
			move(n.opposite(), out)
			readToPrompt(in)
		}
	}
	return nil
}

func move(d direction, out io.Writer) {
	out.Write(append([]byte(d), '\n'))
}

func takeItem(i string, in *bufio.Reader, out io.Writer) {
	out.Write([]byte(fmt.Sprintf("take %s\n", i)))
	readToPrompt(in)
}

func takeItems(is []string, in *bufio.Reader, out io.Writer) {
	for _, i := range is {
		takeItem(i, in, out)
	}
}

func readToPrompt(in *bufio.Reader) string {
	o := strings.Builder{}
	for s, err := in.ReadString('\n'); s != "Command?\n"; s, err = in.ReadString('\n') {
		if err != nil {
			return o.String()
		}
		o.WriteString(s)
	}
	return o.String()
}

func dropItem(i string, in *bufio.Reader, out io.Writer) {
	out.Write([]byte(fmt.Sprintf("drop %s\n", i)))
	readToPrompt(in)
}

func dropItems(is []string, in *bufio.Reader, out io.Writer) {
	for _, i := range is {
		dropItem(i, in, out)
	}
}

func readRoom(in *bufio.Reader) *room {
	r := room{}
	d := readToPrompt(in)
	r.name = readName(d)

	r.d = make(doors)
	readingDoors := false
	for _, l := range strings.Split(d, "\n") {
		if l == "Doors here lead:" {
			readingDoors = true
			continue
		} else if len(r.d) > 0 && l == "" {
			readingDoors = false
			break
		}

		if readingDoors {
			l = strings.Trim(strings.TrimSpace(l), "- ")
			r.d[direction(l)] = nil
		}
	}

	readingItems := false
	for _, l := range strings.Split(d, "\n") {
		if l == "Items here:" {
			readingItems = true
			continue
		} else if len(r.items) > 0 && l == "" {
			readingItems = false
			break
		}
		if readingItems {
			l = strings.Trim(strings.TrimSpace(l), "- ")
			r.items = append(r.items, l)
		}
	}

	return &r
}

func readName(l string) string {
	if ls := roomRE.FindAllStringSubmatch(l, -1); ls != nil {
		return ls[0][1]
	}
	return ""
}

func (r Runner) PartB(in io.Reader) string {
	m := newVM(readInput(in, 1024))
	go func() {
		m.run()
	}()
	i := bufio.NewReader(m)
	o := bufio.NewReader(os.Stdin)

	for {
		t, _ := i.ReadString('\n')
		fmt.Print(t)
		if t == "Command?\n" {
			l, e := o.ReadBytes(byte('\n'))
			if e != nil {
				panic(e)
			}
			m.Write(l)
		}
	}

	return ""
}

vm.go

package day25

import (
	"bytes"
	"io"
	"io/ioutil"
	"strconv"
	"time"
)

func readInput(in io.Reader, buflen int) []int {
	in1, err := ioutil.ReadAll(in)
	if err != nil {
		panic(err)
	}

	in2 := bytes.Split(bytes.TrimRight(in1, "\n"), []byte(","))
	input := make([]int, len(in2)+buflen)
	for i, v := range in2 {
		input[i], err = strconv.Atoi(string(v))
		if err != nil {
			panic(err)
		}
	}

	return input
}

type vm struct {
	pc          int
	base        int
	mem         []int
	input       chan int
	output      chan int
	breakpoints map[int]bool
}

type opcode func(*vm, []mode) int

type mode int

const (
	position  mode = 0
	immediate mode = 1
	relative  mode = 2
)

var opcodes = map[int]opcode{
	1: func(m *vm, modes []mode) int {
		m.set(m.get(1, modes[0])+m.get(2, modes[1]), 3, modes[2])
		return 4
	},
	2: func(m *vm, modes []mode) int {
		m.set(m.get(1, modes[0])*m.get(2, modes[1]), 3, modes[2])
		return 4
	},
	3: func(m *vm, modes []mode) int {
		m.set(<-m.input, 1, modes[0])
		return 2
	},
	4: func(m *vm, modes []mode) int {
		m.output <- m.get(1, modes[0])
		return 2
	},
	5: func(m *vm, modes []mode) int {
		if m.get(1, modes[0]) != 0 {
			m.pc = m.get(2, modes[1])
			return 0
		}
		return 3
	},
	6: func(m *vm, modes []mode) int {
		if m.get(1, modes[0]) == 0 {
			m.pc = m.get(2, modes[1])
			return 0
		}
		return 3
	},
	7: func(m *vm, modes []mode) int {
		res := 0
		if m.get(1, modes[0]) < m.get(2, modes[1]) {
			res = 1
		}
		m.set(res, 3, modes[2])
		return 4
	},
	8: func(m *vm, modes []mode) int {
		res := 0
		if m.get(1, modes[0]) == m.get(2, modes[1]) {
			res = 1
		}
		m.set(res, 3, modes[2])
		return 4
	},
	9: func(m *vm, modes []mode) int {
		m.base += m.get(1, modes[0])
		return 2
	},
}

func newVM(mem []int) *vm {
	memcpy := make([]int, len(mem))
	copy(memcpy, mem)
	return &vm{pc: 0, mem: memcpy, input: make(chan int), output: make(chan int), breakpoints: map[int]bool{}}
}

func (m *vm) run() int {
	for m.running() {
		instr, modes := readInstr(m.mem[m.pc])
		m.pc += opcodes[instr](m, modes)
	}
	return m.pc
}

func (m *vm) write(in int) {
	m.input <- in
}

func (m *vm) Write(p []byte) (n int, err error) {
	for n = 0; n < len(p); n++ {
		m.write(int(p[n]))
	}
	return
}

func (m *vm) read() int {
	return <-m.output
}

func (m *vm) Read(p []byte) (n int, err error) {
	for n = 0; n < len(p); n++ {
		t := time.NewTimer(10 * time.Microsecond)
		select {
		case v := <-m.output:
			p[n] = byte(v)
		case <-t.C:
			return n, nil
		}
	}
	return
}

func (m *vm) ReadLn() string {
	out := []byte{}
	var i int
	for i != 10 {
		i = m.read()
		if i < 255 {
			out = append(out, byte(i))
		} else {
			s := strconv.Itoa(i)
			return s
		}
	}
	return string(out)
}

func (m vm) get(offset int, md mode) int {
	if md == immediate {
		return m.mem[m.pc+offset]
	} else if md == relative {
		return m.mem[m.base+m.mem[m.pc+offset]]
	}
	return m.mem[m.mem[m.pc+offset]]
}

func (m *vm) set(val, offset int, md mode) {
	if md == immediate {
		m.mem[m.pc+offset] = val
	} else if md == relative {
		m.mem[m.base+m.mem[m.pc+offset]] = val
	} else {
		m.mem[m.mem[m.pc+offset]] = val
	}
}

func (m vm) running() bool {
	return m.mem[m.pc] != 99 && m.breakpoints[m.pc] == false
}

func (m vm) copy() *vm {
	new := newVM(m.mem)
	new.pc = m.pc
	new.base = m.base
	for k, v := range m.breakpoints {
		new.breakpoints[k] = v
	}
	return new
}

func readInstr(in int) (int, []mode) {
	return in % 100, []mode{
		mode((in % 1000) / 100),
		mode((in % 10000) / 1000),
		mode((in % 100000) / 10000),
	}
}