NAUX Examples

Verified learner corpus

Algorithms written in NAUX—not delegated to host builtins.

Eight representative programs from the 30-exercise S1 corpus. Every example has deterministic input and expected output.

Corpus: 30
Shown: 8
Domains: 7

Basics

Sum an array

Counted input, a bounded loop, and scalar accumulation.

solution.nxNAUX Learn

~ rite
    $n = read_int()
    $sum = 0
    ~ loop $n
        $sum = $sum + read_int()
    ~ end
    !say $sum
~ end

Input

5
3 -2 7 10 4

Output

naux run solution.nx < input.txt

Number theory

Prime check

Trial division terminates at the integer square-root boundary.

solution.nxNAUX Learn

~ rite
    $n = read_int()
    $prime = $n >= 2
    $divisor = 2
    ~ while $prime && $divisor * $divisor <= $n
        ~ if $n % $divisor == 0
            $prime = false
        ~ end
        $divisor = $divisor + 1
    ~ end
    !say $prime
~ end

Input

Output

true

naux run solution.nx < input.txt

Binary search

Search a sorted learner-built collection without a host search builtin.

solution.nxNAUX Learn

~ rite
    $n = read_int()
    $values = []
    ~ loop $n
        $values = queue_push($values, read_int())
    ~ end
    $target = read_int()
    $left = 0
    $right = $n - 1
    $answer = -1
    ~ while $left <= $right && $answer == -1
        $span = $right - $left
        $middle = $left + ($span - ($span % 2)) / 2
        ~ if $values[$middle] == $target
            $answer = $middle
        ~ else
            ~ if $values[$middle] < $target
                $left = $middle + 1
            ~ else
                $right = $middle - 1
            ~ end
        ~ end
    ~ end
    !say $answer
~ end

Input

7
1 3 5 7 9 11 13
9

Output

naux run solution.nx < input.txt

Sorting

Bubble sort

Mutable indexing, nested loops, and an explicit swap.

solution.nxNAUX Learn

~ rite
    $n = read_int()
    $values = []
    ~ loop $n
        $values = queue_push($values, read_int())
    ~ end
    $pass = 0
    ~ while $pass < $n
        $i = 0
        ~ while $i + 1 < $n - $pass
            ~ if $values[$i] > $values[$i + 1]
                $temporary = $values[$i]
                $values[$i] = $values[$i + 1]
                $values[$i + 1] = $temporary
            ~ end
            $i = $i + 1
        ~ end
        $pass = $pass + 1
    ~ end
    $i = 0
    ~ loop $n
        !say $values[$i]
        $i = $i + 1
    ~ end
~ end

Input

5
5 1 4 2 8

Output

naux run solution.nx < input.txt

Graphs

Breadth-first search

An adjacency matrix, explicit queue state, and visited tracking.

solution.nxNAUX Learn

~ rite
    $n = read_int()
    $start = read_int()
    $adjacency = []
    ~ loop $n * $n
        $adjacency = queue_push($adjacency, read_int())
    ~ end
    $seen = []
    $queue = []
    ~ loop $n
        $seen = queue_push($seen, 0)
        $queue = queue_push($queue, 0)
    ~ end
    $head = 0
    $tail = 1
    $queue[0] = $start
    $seen[$start] = 1
    ~ while $head < $tail
        $node = $queue[$head]
        $head = $head + 1
        !say $node
        $next = 0
        ~ while $next < $n
            ~ if $adjacency[$node * $n + $next] != 0 && $seen[$next] == 0
                $seen[$next] = 1
                $queue[$tail] = $next
                $tail = $tail + 1
            ~ end
            $next = $next + 1
        ~ end
    ~ end
~ end

Input

Output

naux run solution.nx < input.txt

Greedy

Coin change

A descending denomination set and repeated greedy selection.

solution.nxNAUX Learn

~ rite
    $count = read_int()
    $coins = []
    ~ loop $count
        $coins = queue_push($coins, read_int())
    ~ end
    $amount = read_int()
    $used = 0
    $i = 0
    ~ while $i < $count
        ~ while $amount >= $coins[$i]
            $amount = $amount - $coins[$i]
            $used = $used + 1
        ~ end
        $i = $i + 1
    ~ end
    !say $used
~ end

Input

4
25 10 5 1
87

Output

naux run solution.nx < input.txt

Dynamic programming

0/1 knapsack

One-dimensional descending-capacity dynamic programming.

solution.nxNAUX Learn

~ rite
    $n = read_int()
    $capacity = read_int()
    $weights = []
    $values = []
    ~ loop $n
        $weights = queue_push($weights, read_int())
    ~ end
    ~ loop $n
        $values = queue_push($values, read_int())
    ~ end
    $best = []
    ~ loop $capacity + 1
        $best = queue_push($best, 0)
    ~ end
    $item = 0
    ~ while $item < $n
        $space = $capacity
        ~ while $space >= $weights[$item]
            $candidate = $best[$space - $weights[$item]] + $values[$item]
            ~ if $candidate > $best[$space]
                $best[$space] = $candidate
            ~ end
            $space = $space - 1
        ~ end
        $item = $item + 1
    ~ end
    !say $best[$capacity]
~ end

Input

4 5
2 3 4 5
3 4 5 6

Output

naux run solution.nx < input.txt

Dynamic programming

Longest increasing subsequence

A quadratic learner implementation with explicit state.

solution.nxNAUX Learn

~ rite
    $n = read_int()
    $values = []
    $length = []
    ~ loop $n
        $values = queue_push($values, read_int())
        $length = queue_push($length, 1)
    ~ end
    $answer = 0
    $i = 0
    ~ while $i < $n
        $j = 0
        ~ while $j < $i
            ~ if $values[$j] < $values[$i]
                $candidate = $length[$j] + 1
                ~ if $candidate > $length[$i]
                    $length[$i] = $candidate
                ~ end
            ~ end
            $j = $j + 1
        ~ end
        ~ if $length[$i] > $answer
            $answer = $length[$i]
        ~ end
        $i = $i + 1
    ~ end
    !say $answer
~ end

Input

8
10 9 2 5 3 7 101 18

Output

naux run solution.nx < input.txt

Complete S1 inventory

30 deterministic exercises across six tracks

Foundations 8

Sum array
Maximum
Count even
Reverse
Factorial
Fibonacci
Euclidean GCD
Prime check

Search and prefix 4

Linear search
Binary search
First occurrence
Prefix range sum

Sorting 4

Bubble
Selection
Insertion
Counting

Graphs 6

BFS
DFS
Shortest unweighted
Dijkstra
Connected components
Topological sort

Greedy 3

Coin change
Interval scheduling
Maximum items under budget

Dynamic programming 5

0/1 knapsack
Minimum coin change
LIS
Grid paths
Subset sum