binary-trees

Published:
Difficulty: Medium
Platform: The Computer Language Benchmarks Game
URL: https://benchmarksgame-team.pages.debian.net/benchmarksgame/performance/binarytrees.html
Tags: #challenges-medium #challenges-benchmarksgame #go

In this challenge, you will be given a string. You must remove characters until the string is made up of any two alternating characters. When you choose a character to remove, all instances of that character must be removed. Your goal is to create the longest string possible that contains just two alternating letters.

As an example, consider the string "abaacdabd". If you delete the character 'a', you will be left with the string "bcdbd". Now, removing the character 'c' leaves you with a valid string "bdbd" having a length of 4. Removing either 'b' or 'd' at any point would not result in a valid string.

Given a string s, convert it to the longest possible string t made up only of altrenating characters. Print the length of string t on a new line. If no string t can be formed, print 0 instead.

Input Format

A single integer, max.

Constraints:

  • 1 <= |max| <= 62

Output Format

Print a single integer denoting the maximum length of t for the given s; if it is not possible to form string t, print 0 instead.

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

main.go
package main

import (
  "fmt"
  "os"
  "runtime"
  "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()
    runtime.GC()

    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)
}