Nusha Language Interpreter
A Java-based interpreter and logic puzzle solver for the Nusha programming language. This project parses Nusha code into an Abstract Syntax Tree (AST), builds runtime data structures, and uses a constraint satisfaction algorithm to solve complex logic puzzles.
📌 Project Overview
This interpreter was built in two major phases corresponding to the language's execution pipeline:
State Construction (Interpreter 1): Reads the AST to build "live" data structures (structInstance and variableInstance) representing the puzzle grid.
Logic Solving (Interpreter 2): Implements a permutation-based solver that cycles through possible states, validates "unique" constraints, and enforces user-defined logic rules.
🚀 Key Features
Custom Data Structures: * Maps language constructs to Java objects (structInstance, variableInstance).
Handles arrays of structures and nested variable lookups.
Constraint Satisfaction Engine:
Solves logic puzzles by finding valid permutations of variable assignments.
Enforces unique constraints across specific struct fields.
Complex Rule Evaluation:
Supports simple assignments (Fleet[0].g = E5).
Supports conditional logic (IF condition THEN constraints).
Handles deep variable references and dot-notation traversal.
Performance Optimization (Pinning):
Includes a pre-processing step to identify "pinned" variables (simple assignment rules).
Drastically reduces search space (e.g., reduces Battleship from
🧩 Supported Puzzles
The interpreter has been tested against various logic puzzles defined in Nusha:
Battleship: A large-scale grid puzzle (optimized via pinning).
Birthday: Logic deduction regarding party guests and gifts.
Cafe: Deduction of orders based on customer names.
Dating: Matching couples based on preferences.
Dish: Chef and cuisine logic.
Friends: Logical exclusion puzzle.
Pets & Stationery: standard logic grid problems.
🛠️ Technical Implementation
The Interpreter Class
The core logic resides in Interpreter.java. It orchestrates the execution flow:
Populate Definitions: Reads domain definitions (e.g., ShipType = {Battleship, Cruiser...}).
Build Variables: Instantiates the puzzle grid.
Optimization: Scans rules to "pin" known values immediately.
Solve: Uses a BigInteger counter to iterate through permutations, checking:
Uniqueness constraints.
User-defined logic rules (via EvaluateExpression and FindMatch).
Data Structures
variableInstance: Represents a single cell in the logic grid. Stores the current value as an integer index for efficiency.
structInstance: Represents a row in the logic grid (e.g., a specific Ship or Person), containing a map of member variables.
📦 How to Run
Clone the repository.
Open the project in IntelliJ IDEA or Eclipse.
Ensure the AST package is available in the classpath.
Run InterpreterTests.java to execute the test suite containing the Battleship and Logic puzzles.
javac InterpreterTests.java java InterpreterTests
📝 Example Output
========== Battleship ========== SUCCESS: Fleet[0].s = Battleship Fleet[0].g = E5 Fleet[0].sz = Length4 ...
========== Cafe ========== SUCCESS: Puzzles[0].p = Eclairs Puzzles[0].d = Coffee Puzzles[0].n = Brian ...
👤 Author Ahmed Al-Mashraie CS 311 - Programming Language Design and Implementation