The Birdie handbook

A few familiar problems

On this page

These examples are design sketches. They help work out what should feel natural in Birdie before implementing the language. Switch to Python to compare the same algorithm in familiar syntax.

Not executable yet

The Birdie examples use proposed syntax. The Python versions are provided for comparison. This page displays the code without executing it.

Two Sum

For each value, calculate the partner needed to reach the target. A map records previously seen values and their indices. Check the map before inserting the current value so the same element is not used twice.

fn twoSum(nums: [int], target: int) [int]:
    seen = map()

    for i, num in nums:
        diff = target - num

        if diff in seen:
            return [seen[diff], i]

        seen[num] = i

    return []

def two_sum(nums: list[int], target: int) -> list[int]:
    seen: dict[int, int] = {}

    for i, num in enumerate(nums):
        diff = target - num

        if diff in seen:
            return [seen[diff], i]

        seen[num] = i

    return []

The function returns the two indices when it finds a pair, or an empty list when no pair exists.

Valid Parentheses

Keep opening brackets on a stack. Each closing bracket must match the most recent opening bracket. Reject a closing bracket if the stack is empty or the brackets disagree.

fn isValid(s: str) bool:
    matching = {')': '(', ']': '[', '}': '{'}
    opened = stack()

    for char in s:
        if char in matching:
            if not opened or opened.pop() != matching[char]:
                return false
        else:
            opened.push(char)

    return not opened

def is_valid(s: str) -> bool:
    matching = {')': '(', ']': '[', '}': '{'}
    opened: list[str] = []

    for char in s:
        if char in matching:
            if not opened or opened.pop() != matching[char]:
                return False
        else:
            opened.append(char)

    return not opened

The input is assumed to contain only ()[]{} characters. At the end, an empty stack means all brackets were matched. Birdie proposes a dedicated stack type; Python uses a list with append and pop.

Binary Search

The input list must already be sorted in ascending order. Compare the middle value with the target, then narrow the search interval. Return the matching index, or -1 when the interval becomes empty.

fn search(nums: [int], target: int) int:
    left = 0
    right = nums.size - 1

    while left <= right:
        mid = (left + right) // 2

        if nums[mid] == target:
            return mid

        if nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    return -1

def search(nums: list[int], target: int) -> int:
    left = 0
    right = len(nums) - 1

    while left <= right:
        mid = (left + right) // 2

        if nums[mid] == target:
            return mid

        if nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    return -1

Both versions use // for integer floor division and zero-based indexing. Birdie uses .size for the list length; Python uses len(nums).