🐜 Lem-in Project

This project implements the Lem-in challenge, where ants must travel from a Start room to an End room in the minimum number of turns. It uses graph algorithms, Edmonds–Karp max-flow, node splitting, and a turn-based simulator.

---

🚀 Features

• Parser — Reads and validates the ant-farm input (ants, rooms, links).
• Pathfinder —
  • Builds a split-graph representation.
  • Runs Edmonds–Karp to compute vertex-disjoint paths.
  • Extracts valid paths in deterministic order.
• Optimizer — Distributes ants to minimize total turns.
• Simulator — Executes movements turn-by-turn.
• Visualizer (optional) — Real-time web animation via WebSocket.
• Error Handling — Descriptive validation errors.
• Unit Tests — Parser, pathfinder, optimizer, simulator.

---

📂 Project Structure

lem-in/
├── cmd/
│   ├── lem-in/          # CLI entry point
│   │   └── main.go
│   └── visualizer/      # Web visualizer (optional tag)
│       ├── main.go
│       └── stub.go
│
├── parser/
├── pathfinder/
├── simulator/
├── graph/
└── visualizer/
    ├── server.go
    └── static/
        ├── index.html
        ├── style.css
        ├── controls.js
        ├── graph.js
        └── script.js

---

⚡ Quick Start

# CLI (no build)
go run ./cmd/lem-in examples/example00.txt

# CLI (build + run)
go build -o lem-in ./cmd/lem-in
./lem-in examples/example00.txt

# Visualizer (run with tag)
go run -tags=visualizer ./cmd/visualizer
# then open http://localhost:8080

Example Output

L1-A L2-B
L1-E L2-E L3-A
L3-E

Simulation finished in 3 turns (elapsed 2ms)

---

🌐 Web Visualizer (Optional)

The browser-based visualizer runs only when compiled with the visualizer tag.

Run directly

go run -tags=visualizer ./cmd/visualizer

If you omit the tag you’ll see:

Visualizer disabled. Run with: go run -tags=visualizer cmd/visualizer/main.go

Open in browser

http://localhost:8080

Usage

1. Upload a .txt map file.
2. Click Start Simulation.
3. Control playback speed, pause, or zoom the map.

Build as standalone binary

go build -tags=visualizer -o lem-in-visualizer ./cmd/visualizer

---

🧠 Algorithms Overview

Algorithm	Purpose
BFS	Finds shortest augmenting paths
Node Splitting	Enforces one-ant-per-room capacity
Edmonds–Karp Max-Flow	Finds maximum number of disjoint paths
Greedy Ant Distribution	Minimizes total turns
Simulator	Executes sequential movements

---

🧩 Architecture Overview

Parser → Graph Builder → Pathfinder → Optimizer → Simulator → (optional Visualizer)

• parser validates input and builds the colony graph
• pathfinder finds disjoint paths
• simulator performs movements
• visualizer streams and animates turns

---

👨‍💻 Authors

• Alex Smyroglou — [asmyrogl]
• Chris Baikas — [chbaikas]
• Erti Karameta — [ekaramet]
• Nancy Zemperligkou — [nzemperl]

---

📘 Algorithms Used

• Breadth-First Search (BFS) — for distances and augmenting path search.
• Node Splitting — to enforce vertex capacities (1 ant per room).
• Edmonds–Karp Algorithm — to find maximum number of disjoint paths.
• Greedy Ant Distribution — to minimize the makespan (total turns).

---

🧪 Testing

go test ./...

---

✅ Evaluation Checklist

• Handles all parser errors with clear messages and line numbers.
• Produces correct ant movement simulation.
• Uses only Go standard library.
• Deterministic output for identical inputs.
• Unit tests included.