Skip to content

Instantly share code, notes, and snippets.

@Araq
Created January 24, 2020 01:15
Show Gist options
  • Save Araq/74fc6cfe26e807f7279f65b65500251a to your computer and use it in GitHub Desktop.
Save Araq/74fc6cfe26e807f7279f65b65500251a to your computer and use it in GitHub Desktop.
include prelude
type
Node {.acyclic.} = ref object
le, ri: Node
proc checkTree(n: Node): int =
if n.le == nil: 1
else: 1 + checkTree(n.le) + checkTree(n.ri)
proc makeTree(depth: int): Node =
if depth == 0: Node(le: nil, ri: nil)
else: Node(le: makeTree(depth-1), ri: makeTree(depth-1))
proc main =
let maxDepth = parseInt(paramStr(1))
const minDepth = 4
let stretchDepth = maxDepth + 1
echo("stretch tree of depth ", stretchDepth, "\t check:",
checkTree makeTree(stretchDepth))
let longLivedTree = makeTree(maxDepth)
var iterations = 1 shl maxDepth
for depth in countup(minDepth, maxDepth, 2):
var check = 0
for i in 1..iterations:
check += checkTree(makeTree(depth))
echo iterations, "\t trees of depth ", depth, "\t check:", check
iterations = iterations div 4
let t = epochTime()
main()
echo("Completed in ", $(epochTime() - t), "s. Success!")
# use '21' as the command line argument
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment