Tag Archives: tree

Competitive programming in Haskell: building unordered trees

In my previous post I challenged you to solve Subway Tree System, which encodes trees by recording sequences of steps taken away from and towards the root while exploring the whole tree, and asks whether two such recordings denote the … Continue reading

Posted in competitive programming, haskell | Tagged , , , , , , , , , | 26 Comments

Competitive programming in Haskell: sorting tree shapes

In my previous post I challenged you to solve this problem, which essentially asks how many distinct binary tree shapes are created when we take lists of numbers and build a tree from each by repeated binary search tree insertion. … Continue reading

Posted in competitive programming, haskell | Tagged , , , , , , , | 19 Comments

Data structure challenge: application

I forgot to mention this in my previous post, but the thing which got me thinking about the predecessor problem in the first place was this competitive programming problem on Open Kattis: Profitable Pizzas I challenge you to go and … Continue reading

Posted in data structures | Tagged , , , , , , , , , , , , , , | Leave a comment

Data structure challenge: solutions

In my previous post I challenged you to find a way to keep track of a sequence of slots in such a way that we can quickly (in or better) either mark any empty slot as full, or find the … Continue reading

Posted in data structures | Tagged , , , , , , , , , , , , | 3 Comments

Counting inversions via rank queries

In a post from about a year ago, I explained an algorithm for counting the number of inversions of a sequence in time. As a reminder, given a sequence , an inversion is a pair of positions such that and … Continue reading

Posted in haskell | Tagged , , , , , , , , , | 4 Comments

Random binary trees with a size-limited critical Boltzmann sampler

Today I’d like to talk about generating random trees. First, some imports and such (this post is literate Haskell). > {-# LANGUAGE GeneralizedNewtypeDeriving #-} > > module BoltzmannTrees where > > import Control.Applicative > import Control.Arrow ((&&&)) > import Control.Lens … Continue reading

Posted in combinatorics, haskell, math, species | Tagged , , , , , | 14 Comments

Effective parse tree support for the working semanticist

If, like me, you spend large amounts of time designing, discussing, and proving things about programming languages and formal calculi, chances are you have used Ott (and if you do, but you haven’t, you are really missing out). You write … Continue reading

Posted in haskell, projects | Tagged , , , , , | 2 Comments