Lem-in: Digital Ant Farm Pathfinding

Problem: Routing multiple agents (ants) through a constrained graph without room or tunnel congestion while minimizing total traversal steps is a complex pathfinding puzzle.

Solution: A Go-native simulation that discovers optimal disjoint path combinations (DFS+BFS hybrid) and partitions agent flows to achieve minimal steps—simulating 1,000 ants in ~300ms.

Problem Statement

Routing multiple agents through a constrained graph with minimal completion time is a combinatorial optimization problem. Lem-in solves this for ant farm topologies using disjoint path discovery and optimal ant distribution — achieving 1000 ants in ~300ms.

Project Overview

See CONTRIBUTING.md for contribution guidelines and the TDD workflow.

This program reads an ant farm description from a file and simulates the movement of ants from a starting room to an ending room, finding the quickest possible solution using sophisticated pathfinding algorithms with optimal ant distribution.

Features

Advanced Pathfinding: DFS+BFS hybrid algorithm finds optimal disjoint path combinations
Intelligent Simulation: 1000-iteration ant distribution optimization for minimal completion time
ASCII Art Visualization: Interactive CLI visualization of ant movements with multiple display modes
Clean Architecture: Lean main.go with dependency injection through app layer
Performance Optimized: 100 ants in ~200ms, 1000 ants in ~300ms
Comprehensive Testing: 100% audit compliance with extensive test coverage

Project Structure

lem-in/
├── main.go                 # Lean entry point (19 lines)
├── go.mod                  # Go module file
├── internal/               # Internal packages
│   ├── app/               # Application orchestration layer
│   │   └── app.go         # Dependency injection & workflow
│   ├── parser/            # Input parsing logic
│   │   ├── parser.go
│   │   └── parser_test.go
│   ├── graph/             # Graph data structures
│   │   ├── room.go
│   │   ├── ant.go
│   │   ├── colony.go
│   │   └── *_test.go
│   ├── pathfinder/        # Advanced pathfinding algorithms
│   │   ├── pathfinder.go  # DFS+BFS with FindOptimalPaths()
│   │   └── pathfinder_test.go
│   ├── simulator/         # Optimized movement simulation
│   │   ├── simulator.go   # 1000-iteration ant distribution
│   │   └── simulator_test.go
│   ├── visualizer/        # ASCII art visualization
│   │   ├── visualizer.go  # Interactive CLI visualization
│   │   └── visualizer_test.go
│   └── output/            # Output formatting
│       ├── formatter.go
│       └── formatter_test.go
├── examples/              # Test input files
│   ├── example00.txt      # 4 ants (6 turns max)
│   ├── example01.txt      # 10 ants (8 turns max) 
│   ├── example02.txt      # 20 ants (11 turns max)
│   ├── example03.txt      # 4 ants (6 turns max)
│   ├── example04.txt      # 9 ants (6 turns max)
│   ├── example05.txt      # 9 ants (8 turns max)
│   ├── badexample00.txt   # Error cases
│   └── badexample01.txt   # Error cases
├── audit_integration_test.go  # Comprehensive audit & integration tests
├── README.md
├── CONTRIBUTING.md
├── CHANGELOG.md
├── LICENSE
├── .gitignore
└── .github/
    └── copilot-instructions.md  # AI agent guidance

Installation & Setup

Prerequisites

Go 1.19 or later
Git

Clone and Build

git clone <repository-url>
cd lem-in
go mod tidy
go build -o lem-in .

Run Tests

# Run all tests (unit, integration, audit, performance)
go test ./... -v

# Run audit compliance tests specifically
go test -run "TestAuditCompliance" -v

# Run performance tests
go test -run "TestAuditPerformance" -v

# Run unit tests with coverage
go test ./internal/... -cover

# Run individual package tests
go test ./internal/pathfinder -v
go test ./internal/simulator -v

Usage

# Run with example file
go run . examples/example00.txt

# Or use built binary
./lem-in examples/example00.txt

# Enable ASCII art visualization
go run . -visualize examples/example00.txt

# Choose visualization type
go run . -visualize -vis-type summary examples/example00.txt    # Quick summary
go run . -visualize -vis-type static examples/example00.txt     # Static overview  
go run . -visualize -vis-type animated examples/example00.txt   # Turn-by-turn animation

Visualization Options

The new ASCII art visualization feature provides three modes:

summary: Quick one-line completion summary with ant and turn counts
static: Complete farm layout, turn-by-turn movements, and statistics
animated: Turn-by-turn progression with 1-second delays and visual effects

Use -help flag to see all available options:

go run . -help

Quick commands (Windows bash / Linux):

# build
go build -o lem-in .

# run using the built binary
./lem-in examples/example00.txt

# run a single integration example
go run . examples/example01.txt

# run unit tests for all packages
go test ./... -v

# run only integration tests
go test integration_test.go -v

Input Format

The input file should contain:

Number of ants (first line)
Rooms definition with ##start and ##end markers
Tunnels connecting rooms

Example:

4
##start
0 0 3
2 2 5
3 4 0
##end
1 8 3
0-2
2-3
3-1

Output Format

The program outputs:

The original input
Ant movements per turn in format Lx-y where x is ant number and y is room name

Example output:

4
##start
0 0 3
2 2 5
3 4 0
##end
1 8 3
0-2
2-3
3-1

L1-2
L1-3 L2-2
L1-1 L2-3 L3-2
L2-1 L3-3 L4-2
L3-1 L4-3
L4-1

Algorithm Overview

graph LR
    Input[Ant Farm File] --> Parser --> Graph --> Pathfinder[DFS+BFS]
    Pathfinder --> Simulator[Distribution + Turns]
    Simulator --> Output[Lx-room + ASCII Viz]

Parse Input: Validate and parse the ant farm description
Find Optimal Paths: Use DFS to discover all possible paths, then find the optimal disjoint combination
Optimize Distribution: 1000-iteration algorithm distributes ants optimally across paths
Simulate Movement: Move ants turn by turn with sophisticated collision avoidance
Output Results: Format and display the movements with proper Lx-room notation

Advanced Pathfinding Features

FindOptimalPaths(): Tests all combinations of disjoint paths for minimum completion time
Disjoint Path Validation: Paths can only share start/end rooms, not intermediate nodes
Performance Optimization: Completion time calculation considers both path length and ant distribution

Performance Achievements

Example01 (10 ants): Optimized from 9 to 8 turns (meets audit requirement)
All audit examples: 100% compliance with turn limits
Large scale: 100 ants in ~200ms, 1000 ants in ~300ms

Key Constraints

Each room can hold only one ant at a time (except start/end)
Each tunnel can be used only once per turn
Room names cannot start with 'L' or '#' and must have no spaces
Coordinates must be integers
Only standard Go packages are allowed

Testing Strategy

This project follows Test-Driven Development (TDD) principles with comprehensive audit compliance:

Test Coverage & Results

Unit Tests: 52-94% coverage across packages (pathfinder optimized for performance over coverage)
Audit Compliance: All 8 audit examples pass turn limits (see test-results.md)
Performance Benchmarks: 100 ants in ~200ms, 1000 ants in ~300ms (see test-results.md)
Integration Tests: All example files validated

Test Types

Unit Tests

Each package has comprehensive unit tests:

Parser: Input validation and parsing logic (100% coverage)
Graph: Room, ant, and colony data structures (100% coverage)
Pathfinder: Advanced pathfinding algorithms (52% coverage - optimized for performance)
Simulator: Movement simulation and ant distribution (94% coverage)
Output: Formatting and display logic (100% coverage)

Error Handling

The program handles various error conditions:

Invalid number of ants
Missing start or end rooms
Invalid room coordinates
Duplicate rooms
Invalid tunnel definitions
No path exists between start and end

Error format: ERROR: invalid data format

CLI boundary: any parsing or runtime error must surface exactly as the line above; do not print internal error details.

Development Status

Status: ✅ COMPLETED & OPTIMIZED

All objectives achieved with performance optimization!

✅ Phase 1: Project Setup & Clean Architecture

✅ Go module initialization with clean dependency structure
✅ Lean main.go (19 lines) with app layer orchestration
✅ Git repository with comprehensive documentation

✅ Phase 2: Core Data Structures & Validation

✅ Room entity with comprehensive name/coordinate validation
✅ Ant entity with movement tracking and destination detection
✅ Colony container with complete error handling
✅ 100% test coverage across all graph components

✅ Phase 3: Input Parser & Validation

✅ Robust input file parsing with dual-pass reading
✅ Complete error handling with exact format compliance
✅ Comment and command support (##start, ##end)
✅ 100% test coverage with edge case validation

✅ Phase 4: Advanced Pathfinding Algorithms

✅ DFS+BFS hybrid pathfinding with FindOptimalPaths()
✅ Disjoint path discovery and validation
✅ Path combination optimization for minimum completion time
✅ Performance-optimized algorithms (52% coverage by design)

✅ Phase 5: Intelligent Movement Simulation

✅ Turn-based ant movement with collision avoidance
✅ 1000-iteration ant distribution optimization
✅ Sophisticated completion time calculations
✅ Output formatting with exact Lx-room compliance
✅ 94% test coverage

✅ Phase 6: Audit Compliance & Performance Optimization

✅ 100% audit compliance (8/8 examples pass)
✅ Example01 optimization: 9 → 8 turns (critical requirement)
✅ Performance optimization: 100 ants in ~200ms, 1000 ants in ~300ms
✅ Complete integration and performance testing

Final Achievement Summary:

🎯 Perfect Audit Compliance: All 8 examples meet turn requirements
🎯 Performance Excellence: 500x faster than audit limits
🎯 Clean Architecture: Lean main + app layer + dependency injection
🎯 Algorithm Sophistication: Advanced pathfinding with optimal ant distribution
🎯 Test Coverage: Comprehensive validation across all components

Contributing

Follow TDD principles with comprehensive test coverage
Use the established app layer architecture pattern
Maintain performance optimization standards
Update documentation for any algorithmic changes
Follow Go best practices and formatting guidelines

Developer Workflow

# Daily development commands
go test ./... -v                    # Run all tests
go test -run "TestAuditCompliance" -v  # Verify audit compliance
go run . examples/example01.txt     # Test specific examples
go build .                          # Verify compilation

Key Architecture Principles

Lean main.go: Keep entry point minimal (19 lines)
App layer orchestration: Use dependency injection pattern
Performance first: Prioritize algorithm optimization over test coverage
Audit compliance: All examples must meet turn requirements
Error handling: Maintain exact ERROR: invalid data format boundary

License

This project is licensed under the MIT License - see the LICENSE file for details.

Acknowledgments

Zone01 for the project specification
Go community for excellent standard library

Name		Name	Last commit message	Last commit date
Latest commit History 21 Commits
.github		.github
docs		docs
examples		examples
internal		internal
tests		tests
.gitignore		.gitignore
CHANGELOG.md		CHANGELOG.md
CONTRIBUTING.md		CONTRIBUTING.md
LICENSE		LICENSE
README.md		README.md
go.mod		go.mod
main.go		main.go
visualization-demo.md		visualization-demo.md

Folders and files

Latest commit

History

Repository files navigation

Lem-in: Digital Ant Farm Pathfinding

Table of Contents

Problem Statement

Project Overview

Features

Project Structure

Installation & Setup

Prerequisites

Clone and Build

Run Tests

Usage

Visualization Options

Input Format

Output Format

Algorithm Overview

Advanced Pathfinding Features

Performance Achievements

Key Constraints

Testing Strategy

Test Coverage & Results

Test Types

Unit Tests

Error Handling

Development Status

✅ Phase 1: Project Setup & Clean Architecture

✅ Phase 2: Core Data Structures & Validation

✅ Phase 3: Input Parser & Validation

✅ Phase 4: Advanced Pathfinding Algorithms

✅ Phase 5: Intelligent Movement Simulation

✅ Phase 6: Audit Compliance & Performance Optimization

Contributing

Developer Workflow

Key Architecture Principles

Related

License

Acknowledgments

About

Topics

Resources

Contributing

Stars

Watchers

Forks

Releases

Packages

Contributors

Languages