Skip to content

Latest commit

 

History

History
144 lines (105 loc) · 6.32 KB

PROJECTS.md

File metadata and controls

144 lines (105 loc) · 6.32 KB

Big Dana Projects

This document highlights Dana projects that go beyond simple tests and played a key role in debugging our compiler implementation.

BooHoo Interpreter

Dana implementation in testing/extra-hard/boohoo/boohoo.dana

BooHoo is a Turing-complete esolang created by Nikolas Spyropoulos in 2023. It features a 3D memory space of size 100 × 100 × 100 storing integer values, and all its keywords are variations of the words "boo" and "hoo".

This Dana implementation of the BooHoo interpreter differs from the original Python version in the following ways:

  • Comments are not supported
  • Input must be provided after the main program, separated by ---
  • The program size is limited to a maximum of 1000 commands

Usage

Compile the BooHoo interpreter with:

compiler/danac.sh testing/extra-hard/boohoo/boohoo.dana -o boohoo

Example BooHoo programs are provided in testing/extra-hard/boohoo/programs. The corresponding examples from the original repository are shown in parentheses:

test_input.boohoo (boohoo_demos/test1.boohoo):

Takes an integer x as input and outputs x+1 and x-2 after some memory movements

test_loop.boohoo (boohoo_demos/test2.boohoo):

Takes an integer as input and counts reverse until 0

test_2loop.boohoo (boohoo_demos/test4.boohoo):

Copies 2x input to memory cell (1, 0, 0) and outputs the result

In order to run a BooHoo program simply use:

./boohoo < program.boohoo

For more information about the BooHoo language check the original repository.

Genetic Algorithm for the Travelling Salesman Problem

Dana implementation in testing/extra-hard/travelling-salesman/tsp.dana

This project implements a Genetic Algorithm (GA) to solve the classic Travelling Salesman Problem (TSP) in Dana.

  • Problem setup:
    • The distance matrix between cities is randomly initialized.
    • Each chromosome represents a possible tour (path through all cities).
  • Random number generation:
    • A simple linear congruential generator (LCG) is implemented as nextRand.
    • It uses constants a = 1664525, b = 1013904223, and c = 2147483647.
    • This ensures reproducible pseudo-randomness for distance initialization, population shuffling, mutation, and selection.
  • Core GA operations implemented:
    • fitness: Evaluates the total distance of a tour.
    • select_parent: Tournament selection between two candidates.
    • crossover: Order-based crossover that preserves city visits.
    • mutate: Random swap mutation with configurable probability.
  • Execution flow:
    • The algorithm initializes a random population using Fisher–Yates shuffling.
    • For each generation, the best solution is tracked and logged.
    • New generations are produced via crossover and mutation, with elitism ensuring the best path survives.
  • Output:
    • Prints the best distance and corresponding path for each generation.
    • At the end, outputs the globally best solution found across all generations.

This implementation showcases how Dana can handle arrays, modular function design, pseudo-random number generation, and evolutionary algorithms, while providing a structured, extendable solution for combinatorial optimization problems.

Perceptron

Dana implementation in testing/extra-hard/perceptron/perceptron.dana

The classic Perceptron binary classifier implemented as a Dana test to debug our compiler's array implementation.

  • The model is trained and evaluated on basic logic gates, demonstrating successful learning of both OR and AND functions.
  • All calculations use fixed-point arithmetic to simulate decimal precision.
  • Both train and predict functions are provided, making the implementation structured, modular, and easy to extend.

Sudoku

Dana implementation in testing/extra-hard/sudoku/sudoku.dana

This project is a complete 9×9 Sudoku solver implemented in Dana using classic backtracking with constraint checks. It reads a 9×9 grid of integers (use 0 for blanks), solves it recursively, and prints either the solved grid or No solution.

How it works

  • Board representation: int[9][9].

  • Printing: printBoard(b) prints the grid row by row with spaces.

  • Feasibility checks: isSafe(b, row, col, num) ensures:

    1. num not already in row,
    2. num not already in col,
    3. num not already in the 3×3 sub-box containing (row, col).

  • Empty-cell search: findEmpty(b, rowRef, colRef) scans for the next 0. It returns a byte flag and writes the location into rowRef/colRef.

  • Backtracking core: solve(b) finds an empty cell; if none, we’re done. Otherwise, it tries num = 1..9, and for each safe number:

    1. place it,
    2. recurse,
    3. if recursion fails, backtrack (reset to 0) and try the next number.

This mirrors the canonical DFS search on Sudoku’s state space with pruning via row/col/box checks.

Usage

Use the compiler:

compiler/danac.sh testing/extra-hard/sudoku/sudoku.dana -o sudoku

Run by piping a 9×9 grid (zeros for empty) into the executable:

./sudoku < testing/extra-hard/sudoku/sudoku.input

Matrix Multiplication

Dana implementation in testing/extra-hard/matrix-mul/matrix_mul.dana

This program implements standard matrix multiplication C(n×p) = A(n×m) × B(m×p) with dimensions up to 20×20.

Features

  • Matrix input/output:
    • readMatrix(rows, cols, M) reads integers row-wise into a 2D array.
    • writeMatrix(rows, cols, M) prints the matrix with space-separated values.
  • Matrix multiplication core:
    • matmul(n, m, p, A, B, C) performs the triple loop multiplication with accumulation into C.
  • Execution flow:
    1. Reads matrix sizes n, m, p (capped at 20).
    2. Reads matrix A (n×m) and B (m×p).
    3. Computes product C = A × B.
    4. Outputs the resulting matrix C (n×p).

Usage

Compile with:

compiler/danac.sh testing/extra-hard/matrix-mul/matrix_mul.dana -o matrix_mul

Run and provide dimensions and elements via standard input:

./matrix_mul < testing/extra-hard/matrix-mul/matrix_mul.input