Lem-in 🐜

A Go implementation of the classic Lem-in algorithm that finds optimal paths for ants to move from a start room to an end room through a network of connected rooms.

📋 Table of Contents

• Overview
• Features
• Installation
• Usage
• Input Format
• Algorithm
• Project Structure
• Examples
• Error Handling
• Contributing

📖 Overview

Lem-in is a pathfinding problem where:

• A colony of ants needs to move from a start room to an end room
• Rooms are connected by tunnels (links)
• Only one ant can occupy a room at a time (except start and end rooms)
• The goal is to find the optimal combination of paths to move all ants in the minimum number of steps

This implementation uses advanced pathfinding algorithms to:

1. Find all possible paths from start to end
2. Select the optimal combination of non-overlapping paths
3. Distribute ants across these paths efficiently
4. Simulate the movement and output the result

✨ Features

• Efficient Pathfinding: Finds all possible paths using recursive depth-first search
• Path Optimization: Selects the best combination of non-overlapping paths
• Ant Distribution: Intelligently distributes ants across multiple paths
• Input Validation: Comprehensive error checking for malformed input files
• Movement Simulation: Visualizes ant movement step by step

🚀 Installation

Prerequisites

• Go 1.21.1 or higher

Clone and Build

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

💻 Usage

./lem-in example00.txt

The program takes exactly one argument - the name of the input file (must be in the example/ directory).

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 L2-2 L3-2 L4-2 
L1-3 L2-3 L3-3 L4-3 
L1-1 L2-1 L3-1 L4-1 

📄 Input Format

The input file must follow this specific format:

<number_of_ants>
##start
<start_room> <x> <y>
<room1> <x1> <y1>
<room2> <x2> <y2>
##end
<end_room> <x> <y>
<room1>-<room2>
<room2>-<room3>
...

Rules:

• First line: Number of ants (positive integer)
• ##start marks the starting room (exactly one required)
• ##end marks the ending room (exactly one required)
• Room format: name x_coordinate y_coordinate
• Link format: room1-room2
• Room names cannot start with L, #, or contain -
• Comments start with # (but not ##start or ##end)

🧠 Algorithm

1. Path Discovery

• Uses recursive depth-first search to find all possible paths
• Avoids cycles and ensures paths don't revisit rooms
• Stores all valid paths from start to end

2. Path Selection

• Finds the optimal combination of non-overlapping paths
• Considers the maximum number of paths based on start/end room connections
• Sorts paths by length for optimal distribution

3. Ant Distribution

• Distributes ants across selected paths based on path lengths
• Ensures balanced load to minimize total steps
• Uses a greedy approach for optimal ant assignment

4. Movement Simulation

• Simulates step-by-step ant movement
• Outputs each turn showing ant positions
• Format: L<ant_number>-<room_name>

📁 Project Structure

lem-in/
├── main.go              # Entry point and main logic
├── go.mod               # Go module definition
├── models/
│   └── models.go        # Data structures (Room, Link, NbrAnts)
├── tools/
│   ├── recuperation.go  # File parsing and input validation
│   ├── searchPath.go    # Pathfinding algorithms
│   └── moving.go        # Ant movement simulation
├── example/
│   ├── example00.txt    # Test cases
│   ├── example01.txt
│   └── ...
└── push.sh             # Git automation script

Key Components:

• models.go: Defines data structures for rooms, links, and ant distribution
• recuperation.go: Handles file parsing and comprehensive input validation
• searchPath.go: Implements pathfinding algorithms and path optimization
• moving.go: Manages ant distribution and movement simulation

📚 Examples

Simple Example (example00.txt)

4          # 4 ants
##start
0 0 3      # Start room at coordinates (0,3)
2 2 5      # Regular room
3 4 0      # Regular room
##end
1 8 3      # End room at coordinates (8,3)
0-2        # Links between rooms
2-3
3-1

Complex Example (example05.txt)

A more complex network with 9 ants and multiple possible paths, demonstrating the algorithm's ability to find optimal path combinations.

⚠️ Error Handling

The program includes comprehensive error checking for:

• Invalid number of ants: Must be a positive integer
• Missing start/end rooms: Exactly one ##start and one ##end required
• Invalid room format: Must be name x y with valid coordinates
• Invalid room names: Cannot start with L, #, or contain -
• Invalid links: Must be room1-room2 format with existing rooms
• Duplicate rooms/links: No duplicates allowed
• Empty lines: Not permitted in input files
• Malformed data: Various format validation checks

🤝 Contributing

1. Fork the repository
2. Create a feature branch (git checkout -b feature/amazing-feature)
3. Commit your changes (git commit -m 'Add amazing feature')
4. Push to the branch (git push origin feature/amazing-feature)
5. Open a Pull Request

---

Note: This implementation efficiently handles complex ant colony pathfinding scenarios and provides optimal solutions for the Lem-in problem. The algorithm is designed to work with various network topologies and ant quantities.

---

⭐ Star this repository if you found it helpful! ⭐

Made with ❤️ from 🇸🇳