Binary Trees

See the challenge description.

Usage

$ go build -o solution main.go

$ echo 10 | ./solution

Sample

input00.txt
10
output00.txt
stretch tree of depth 11	 check: 4095
1024	 trees of depth 4	 check: 31744
256	 trees of depth 6	 check: 32512
64	 trees of depth 8	 check: 32704
16	 trees of depth 10	 check: 32752
long lived tree of depth 10	 check: 2047

Solution

This solution is not fully compliant to the challenge rules, I just wanted to learn about profiling Go programs and tweak them to run as fast as its C and Rust counter-parts (and indeed it is faster).

main.go
package main

import (
  "fmt"
  "os"
  "runtime/pprof"
  "sync"
)

func main() {
  if cpup := os.Getenv("CPUPROFILE"); cpup != "" {
    f, err := os.Create(cpup)
    if err != nil {
      fmt.Fprintf(os.Stderr, "Can't create CPU profile file: %v", err)
      os.Exit(1)
    }

    defer f.Close()

    if err := pprof.StartCPUProfile(f); err != nil {
      fmt.Fprintf(os.Stderr, "Can't profile CPU usage: %v", err)
      os.Exit(1)
    }

    defer pprof.StopCPUProfile()
  }

  min := 4
  var max int
  fmt.Scan(&max)

  if max < min+2 {
    max = min + 2
  }

  {
    st := NewTree(max + 1)
    fmt.Printf("stretch tree of depth %d\t check: %d\n", max+1, st.Check())
  }

  llt := NewTree(max)

  var wg sync.WaitGroup
  msgs := make([]string, max+1)

  for cd := min; cd <= max; cd += 2 {
    wg.Add(1)

    go func(cd int) {
      defer wg.Done()

      pool := NewPool(cd)
      n := 1 << (max - cd + min)
      i := 0
      sum := 0

      for ; i < n; i++ {
        t := NewTreeWithPool(cd, pool)
        sum += t.Check()
      }

      msgs[cd] = fmt.Sprintf("%d\t trees of depth %d\t check: %d", i, cd, sum)
    }(cd)
  }

  wg.Wait()

  for cd := min; cd <= max; cd += 2 {
    fmt.Println(msgs[cd])
  }

  fmt.Printf("long lived tree of depth %d\t check: %d\n", max, llt.Check())

  if memp := os.Getenv("MEMPROFILE"); memp != "" {
    f, err := os.Create(memp)
    if err != nil {
      fmt.Fprintf(os.Stderr, "Can't create memory profile file: %v", err)
      os.Exit(1)
    }

    defer f.Close()

    if err := pprof.WriteHeapProfile(f); err != nil {
      fmt.Fprintf(os.Stderr, "Can't profile memory usage: %v", err)
      os.Exit(1)
    }
  }
}

type Tree struct {
  left, right *Tree
}

func NewTree(d int) Tree {
  return NewTreeWithPool(d, NewPool(d))
}

func NewTreeWithPool(d int, pool []Tree) Tree {
  if d < 1 {
    return Tree{}
  }

  base := 1 << d
  total := base<<1 - 2
  pool = pool[:0]

  for i := 0; i < base; i++ {
    pool = append(pool, Tree{})
  }

  for i := 0; i < total-2; i += 2 {
    pool = append(pool, Tree{&pool[i], &pool[i+1]})
  }

  return Tree{&pool[total-2], &pool[total-1]}
}

func (t *Tree) Check() int {
  if t.left != nil {
    return t.left.Check() + t.right.Check() + 1
  }

  return 1
}

func NewPool(d int) []Tree {
  total := 1<<(d+1) - 2
  return make([]Tree, total)
}