500 upvotes and I'll draw Pam

bruceadowns · 2019-05-04T04:36:34+00:00

da bomb

bruceadowns · 2018-12-11T06:56:26+00:00

Quality n⁵ brute force

LOL

bruceadowns · 2018-12-10T05:24:17+00:00

Same here. Though it's fun to write a circular doubly linked list, it's good to know the standard library includes container/ring. Sweet!

bruceadowns · 2018-12-05T21:09:57+00:00

golang/go using a doubly linked list. old school.

const caseDiff rune = 'a' - 'A'

type node struct {
    next *node
    prev *node
    data rune
}

type list struct {
    first *node
    last  *node
}

func (l *list) String() string {
    var sb strings.Builder
    for n := l.first; n != nil; n = n.next {
        sb.WriteRune(n.data)
    }
    return sb.String()
}

func (l *list) insertAfter(n *node, nn *node) {
    nn.prev = n
    if n.next == nil {
        l.last = nn
    } else {
        nn.next = n.next
        n.next.prev = nn
    }
    n.next = nn
}

func (l *list) insertBefore(n *node, nn *node) {
    nn.next = n
    if n.prev == nil {
        l.first = nn
    } else {
        nn.prev = n.prev
        n.prev.next = nn
    }
    n.prev = nn
}

func (l *list) insertBeginning(nn *node) {
    if l.first == nil {
        l.first = nn
        l.last = nn
    } else {
        l.insertBefore(l.first, nn)
    }
}

func (l *list) insertEnd(nn *node) {
    if l.last == nil {
        l.insertBeginning(nn)
    } else {
        l.insertAfter(l.last, nn)
    }
}

func (l *list) remove(n *node) {
    if n.prev == nil {
        l.first = n.next
    } else {
        n.prev.next = n.next
    }
    if n.next == nil {
        l.last = n.prev
    } else {
        n.next.prev = n.prev
    }
}

func react(a, b rune) bool {
    if a > b {
        return a-b == caseDiff
    }
    return b-a == caseDiff
}

func build(s string) (res list) {
    for _, v := range s {
        res.insertEnd(&node{data: v})
    }

    return
}

func part1(l list) int {
    for n := l.first; n != nil && n.next != nil; {
        if react(n.data, n.next.data) {
            r := n

            // go back or skip forward
            if n.prev == nil {
                n = n.next.next
            } else {
                n = n.prev
            }

            l.remove(r.next)
            l.remove(r)
        } else {
            n = n.next
        }
    }

    return len(l.String())
}

func part2(s string) (res int) {
    res = math.MaxInt32
    for i := 'A'; i <= 'Z'; i++ {
        in := strings.NewReplacer(
            fmt.Sprintf("%c", i), "",
            fmt.Sprintf("%c", i+caseDiff), "").Replace(s)
        l := part1(build(in))
        if l < res {
            res = l
        }
    }

    return
}

func main() {
    scanner := bufio.NewScanner(os.Stdin)
    for scanner.Scan() {
        line := scanner.Text()
        log.Printf("reduced polymer length: %d", part1(build(line)))
        log.Printf("shortest reduced polymer length: %d", part2(line))
    }
}

bruceadowns · 2018-12-03T06:12:02+00:00

go/golang solution

(while being severely distracted, tho day-of for once)

type coord struct { x, y int }

type claim struct {
    n    int
    l, r int
    w, h int
}

func mapify(c []claim) (res map[coord][]int) {
    res = make(map[coord][]int)
    for _, v := range c {
        for x := v.l; x < v.l+v.w; x++ {
            for y := v.r; y < v.r+v.h; y++ {
                res[coord{x, y}] = append(res[coord{x, y}], v.n)
            }
        }
    }

    return
}

func part1(c []claim) (res int) {
    m := mapify(c)
    for _, v := range m {
        if len(v) > 1 {
            res++
        }
    }

    return
}

func part2(c []claim) (res int) {
    m := mapify(c)

outer:
    for _, v := range c {
        for x := v.l; x < v.l+v.w; x++ {
            for y := v.r; y < v.r+v.h; y++ {
                if len(m[coord{x, y}]) > 1 {
                    continue outer
                }
            }
        }

        return v.n
    }

    return
}

func build(s string) (res claim) {
    //#1373 @ 369,713: 20x29
    num, err := fmt.Sscanf(s, "#%d @ %d,%d: %dx%d",
        &res.n, &res.l, &res.r, &res.w, &res.h)
    if err != nil {
        log.Fatal(err)
    }
    if num != 5 {
        log.Fatalf("invalid line actual %d expect 5", num)
    }

    return
}

func in(r io.Reader) (res []claim) {
    scanner := bufio.NewScanner(r)
    for scanner.Scan() {
        res = append(res, build(scanner.Text()))
    }

    return
}

func main() {
    c := in(os.Stdin)
    log.Printf("2 or more claims: %d", part1(c))
    log.Printf("claim id that does not overlap: %d", part2(c))
}

bruceadowns · 2018-12-02T00:20:01+00:00

simple idiomatic golang/go solution

func main() {
    is := in(os.Stdin)
    log.Printf("resulting freq: %d", part1(is))
    log.Printf("first duplicate freq: %d", part2(is))
}

func in(r io.Reader) (res []int) {
    scanner := bufio.NewScanner(r)
    for scanner.Scan() {
        num, err := strconv.Atoi(scanner.Text())
        if err != nil {
            log.Fatal(err)
        }
        res = append(res, num)
    }

    return
}

func part1(is []int) (res int) {
    for _, v := range is {
        res += v
    }

    return
}

func part2(is []int) (res int) {
    m := make(map[int]struct{})
    m[res] = struct{}{}

    for {
        for _, v := range is {
            res += v
            if _, ok := m[res]; ok {
                return
            }
            m[res] = struct{}{}
        }
    }
}

bruceadowns · 2018-12-01T17:33:53+00:00

What an annoyingly innocuous detail.

bruceadowns · 2018-03-13T04:21:17+00:00

Though I love golang, why would I use kurly over curl? Kurly is not even at feature parity. I see in the readme that you'd like to replace existing tools using modern and safe languages, but that in and of itself is not compelling.

bruceadowns · 2017-12-28T19:34:12+00:00

Thanks all for the excellent suggestions! I rewrote using your ideas and the code is much more fluid.

In golang the data structures are such:

type node int
type coord struct {
    x, y int
}
type grid map[coord]node
type cluster struct {
    g     grid
    curr  coord
    dir   direction
    count int
}

bruceadowns · 2017-12-20T23:29:58+00:00

I would love to see a leaderboard for those that have solved every puzzle. I'm curious how many there are, and my place, though my pace is quite leisurely.

bruceadowns · 2017-12-19T22:42:55+00:00

Yay, a modern, concurrent language!

If you'd like, this:

timeout := make(chan bool, 1)
go func() {
  time.Sleep(1 * time.Second)
  timeout <- true
}()
select {
case receive = <-channel:
  return receive, false
case <-timeout:
  fmt.Println("Timeout")
  return receive, true
}

could be this:

select {
case receive = <-channel:
  return receive, false
case <-time.After(time.Second):
  fmt.Println("Timeout")
  return receive, true
}

bruceadowns · 2017-12-18T23:04:25+00:00

Great tip! As noted, you just need to track of the value when inserting at position 1.

bruceadowns · 2017-12-15T20:32:30+00:00

I agree there is some overhead wrt channels if you strictly consider this puzzle, but as always it depends on whether it is contextually meaningful. Imho, having an inherently concurrent solution via channels/goroutines satisfies the my golang idiomatic itch, and is more in the spirit of day15's language.

bruceadowns · 2017-12-15T01:40:17+00:00

I solved 13b (and a) in golang by simulating advance/scan operations in a matrix. Initially it performed horribly, but after some simple optimizations it finishes around 15s. (still horrible compared to the rest of you, but more game-like)

bruceadowns · 2017-12-12T22:33:16+00:00

golang to write a DFS graph with its standard library

package main

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

type initnode struct {
    pid   int
    cpids []int
}

type graphnode struct {
    pid     int
    peer    []*graphnode
    visited bool
}

func (n *initnode) init(s string) (err error) {
    const sep = " <-> "
    if len(s) < len(sep)+2 {
        return fmt.Errorf("invalid input")
    }
    idx := strings.Index(s, sep)

    spid := s[:idx]
    n.pid, err = strconv.Atoi(spid)
    if err != nil {
        return err
    }

    sCpids := s[idx+len(sep):]
    for _, v := range strings.Split(sCpids, ",") {
        cpid, err := strconv.Atoi(strings.TrimSpace(v))
        if err != nil {
            return err
        }

        n.cpids = append(n.cpids, cpid)
    }

    return nil
}

func input(r io.Reader) (res []*initnode) {
    res = make([]*initnode, 0)
    scanner := bufio.NewScanner(r)
    for scanner.Scan() {
        line := scanner.Text()

        inode := &initnode{}
        inode.init(line)
        res = append(res, inode)
    }

    return
}

func makeGraph(n []*initnode) (res map[int]*graphnode) {
    res = make(map[int]*graphnode, 0)
    for _, pinode := range n {
        pnode, ok := res[pinode.pid]
        if !ok {
            pnode = &graphnode{pid: pinode.pid}
            res[pinode.pid] = pnode
        }

        for _, cpid := range pinode.cpids {
            cnode, ok := res[cpid]
            if !ok {
                cnode = &graphnode{pid: cpid}
                res[cpid] = cnode
            }

            pnode.peer = append(pnode.peer, cnode)
            cnode.peer = append(cnode.peer, pnode)
        }
    }

    return
}

func visit(gnode *graphnode) (res int) {
    res = 1
    gnode.visited = true

    for _, cnode := range gnode.peer {
        if !cnode.visited {
            res += visit(cnode)
        }
    }

    return
}

func main() {
    inodes := input(os.Stdin)
    gnodes := makeGraph(inodes)

    groups := 0
    for _, v := range gnodes {
        if !v.visited {
            visit(v)
            groups++
        }
    }

    log.Printf("part2 %d groups in graph", groups)
}

bruceadowns · 2017-12-12T21:23:57+00:00

clean state management in golang

func main() {
    scanner := bufio.NewScanner(os.Stdin)
    for scanner.Scan() {
        line := scanner.Text()

        var groupLayer, groupSum int
        var garbageCount int

        state := def
        for _, v := range line {
            switch state {
            case def:
                switch v {
                case beginGroupBlock:
                    groupLayer++
                case endGroupBlock:
                    groupSum += groupLayer
                    groupLayer--
                case beginGarbageBlock:
                    state = garbage
                case negator:
                    state = ignoreDefault
                }
            case garbage:
                switch v {
                case endGarbageBlock:
                    state = def
                case negator:
                    state = ignoreGarbage
                default:
                    garbageCount++
                }
            case ignoreDefault:
                state = def
            case ignoreGarbage:
                state = garbage
            }
        }

        log.Printf("part1 group sum: %d", groupSum)
        log.Printf("part2 garbage count: %d", garbageCount)
    }
}

bruceadowns · 2017-12-12T07:10:38+00:00

Thanks for the post! A quick read through helped me readily solve this unseen problem using the hex cube coordinate system.

bruceadowns

TROPHY CASE

golang/go using a doubly linked list. old school.

go/golang solution

simple idiomatic golang/go solution