lem-in

A digital ant farm. The program reads a colony (a set of rooms connected by tunnels, plus a number of ants), then figures out how to move every ant from the start room to the end room in the fewest possible turns.

Each room holds only one ant at a time (except start and end), and each tunnel can be used only once per turn. The program finds the best set of non-overlapping paths and moves the ants along them turn by turn.

Requirements

• Go 1.24 or newer

How to run

From the project folder, pass the path to a colony file:

go run . tests/example00.txt

Or build a binary first and run that:

go build -o lem-in .
./lem-in tests/example00.txt

The program expects exactly one argument (the file name). Running it with the wrong number of arguments prints:

Usage: go run . <filename.txt>

Input file format

A colony file is plain text with three kinds of lines, in this order:

1. Number of ants — the very first line (a positive whole number).
2. Rooms — one per line as name x y, where x and y are integer coordinates (used only for display, not for the pathfinding).
   • The room after a ##start line is the start room.
   • The room after a ##end line is the end room.
3. Links (tunnels) — one per line as name1-name2, connecting two rooms.

Extra rules:

• Lines starting with a single # are comments and are ignored.
• Lines starting with ## are commands; only ##start and ##end are used.
• Room names cannot start with L or #, and coordinates must be unique.

Example input (tests/example00.txt)

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

This colony has 4 ants and one path: 0 → 2 → 3 → 1 (start 0, end 1).

Output format

The program first echoes the original input, prints a blank line, then prints one line per turn. Each move looks like Lx-room, meaning "ant number x moves into room". Ants are numbered L1, L2, L3, …

Running the example above:

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

Ticks taken: 6
Finished in: 1.4294ms

• Ticks taken — the total number of turns needed to move all ants.
• Finished in — how long the program took to run.

Errors

If a file is invalid (bad room format, missing start/end, unreachable end, and so on) the program prints a message describing the problem and exits. The tests/ folder includes badexample00.txt and badexample01.txt to try these cases:

go run . tests/badexample00.txt

Project layout

main.go                 Program entry point (ties the steps together)
functions/
  readfileline.go       Reads the input file into lines
  parse.go              Parses ants, rooms, and links into a Farm
  structs.go            Data types (Room, Farm, Path, ...)
  bfs.go, dfs.go        Path-finding through the colony
  combinations.go       Builds groups of non-overlapping paths
  schedual.go           Picks the cheapest path combination and assigns ants
  simulator.go          Moves the ants turn by turn and prints the result
  helpers.go            Small shared helper functions
tests/                  Sample colony files (example*.txt, badexample*.txt)

How it works (in short)

1. Read the file into lines.
2. Parse the lines into a colony (ants, rooms, links, start/end).
3. Find all paths from start to end.
4. Combine paths into sets that don't share rooms.
5. Choose the combination that moves all ants in the fewest turns.
6. Simulate the ants moving and print each turn.