Biologiskt mångfald

Platform: undutmaning | Category: Misc | Type: Challenge | Difficulty: Medium | OS: Linux | Author: XESXOR | Date: 2026-03-21 | Status: Solved Techniques: constraint_satisfaction_problem, backtracking_with_pruning, domain_reduction, constraint_propagation

Summary

English summary: Help Harriet save the fish! A satellite crash broke the aquarium tanks and fish are scattered on the floor. Place 25 fish back into 4 tanks following complex biological/ecological rules. The server validates placement via a POST to /verify endpoint.

Biologiskt mångfald — Undutmaning

Description

Nu är det bråttom! Det har uppstått en krissituation i Akvarium #4. När satelliten kraschade in i CASCADA fick smällen lamparmaturen att lossna och ramla ned på akvarietankarna. Nästan alla tankarna har gått sönder och nu ligger det en massa fiskar utspridda över golvet, kippande efter andan. Hjälp Harriet att rädda fiskarna! Skynda dig till akvariet!

English summary: Help Harriet save the fish! A satellite crash broke the aquarium tanks and fish are scattered on the floor. Place 25 fish back into 4 tanks following complex biological/ecological rules. The server validates placement via a POST to /verify endpoint. ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

• URL: https://undutmaning-mangfald.chals.io/
• Flag format: undut{...}

Analysis

Challenge Structure

A web application (Werkzeug/Python) with a drag-and-drop interface. 25 fish must be placed into 4 tanks following complex biological/ecological rules.

Tanks (with properties)

Fish Species (25 total)

‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

Total biomass: 79 units across 4 tanks (max 20 each = 80 capacity) ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

Constraints (from /rules.html)

1. Biomass limit: Max 20 units per tank
2. Large predator limit: Max 1 large predator (size ≥ 6) per tank
3. BlueShark schooling: Small fish (size ≤ 3) in same tank must form school of 3+ or not be present
4. Detritivore requirement: Each tank needs at least one: Pleco, Catfish, Koi, Goby, or Goldfish
5. Environmental requirements:
   • BlueShark: not brackish (not TankD)
   • Manta: warm or temperate salt (TankB or TankC)
   • Lionfish: warm only (TankC)
   • Coralfish: warm + coral (TankC only)
   • Angelfish: not cold (not TankA)
   • Oscar: brackish or dark (TankA or TankD)
   • Guppy: temperate only (TankB or TankD)
   • Pleco: not high salt (TankD only)
   • Koi: not cold (not TankA)
6. Incompatibilities:
   • Angelfish not with Oscar or Lionfish
   • Guppy not with Oscar or Lionfish
   • Catfish not with Lionfish
   • Puffer not with Surgeon
   • Betta not with Guppy
   • Coralfish not with Manta or Oscar ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

This is a classic Constraint Satisfaction Problem (CSP).

Solution

Step 1: Model as CSP

Each fish is a variable with domain = allowed tanks. Constraints are:

• Unary constraints: environmental requirements (pre-filter domains)
• Binary constraints: incompatibilities (fish pairs cannot share tank)
• Global constraints: biomass, large predators, detritivores, schooling

Step 2: Backtracking Solver with Pruning

 python read-only • copy allowed Copy
#!/usr/bin/env python3
"""
Fish tank placement solver - backtracking with pruning
"""
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

import json

# Fish species with sizes
SPECIES = [
    ("BlueShark", 8), ("Manta", 7), ("Lionfish", 6), ("Oscar", 7),
    ("Angelfish_1", 4), ("Angelfish_2", 4), ("Koi", 4), ("Goldfish", 4),
    ("Clown", 3), ("Surgeon", 3), ("Coralfish", 3), ("Minnow", 3),
    ("Puffer", 2), ("Catfish", 2), ("Betta_1", 2), ("Betta_2", 2),
    ("Swordtail", 2), ("Goby", 2), ("Pleco", 2),
    ("Guppy_1", 1), ("Guppy_2", 1), ("Guppy_3", 1),
    ("Tetra_1", 2), ("Tetra_2", 2), ("Tetra_3", 2),
]

TANKS = ["TankA", "TankB", "TankC", "TankD"]
DETRITIVORES = ["Pleco", "Catfish", "Koi", "Goby", "Goldfish"]
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

def get_base_name(name):
    if "_" in name:
        parts = name.rsplit("_", 1)
        if parts[1].isdigit():
            return parts[0]
    return name

def get_size(name):
    for n, s in SPECIES:
        if n == name:
            return s
    return 0

# Pre-compute allowed tanks based on environmental constraints
def get_allowed_tanks(fish):
    base = get_base_name(fish)
    
    if base == "BlueShark": return ["TankA", "TankB", "TankC"]  # not brackish
    if base == "Manta": return ["TankB", "TankC"]  # warm or temperate salt
    if base == "Lionfish": return ["TankC"]  # warm only
    if base == "Coralfish": return ["TankC"]  # warm + coral
    if base == "Angelfish": return ["TankB", "TankC", "TankD"]  # not cold
    if base == "Oscar": return ["TankA", "TankD"]  # brackish or dark
    if base == "Guppy": return ["TankB", "TankD"]  # temperate
    if base == "Pleco": return ["TankD"]  # not high salt
    if base == "Koi": return ["TankB", "TankC", "TankD"]  # not cold
    
    return TANKS
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

def check_solution(assignment):
    """Verify all constraints on complete assignment"""
    tanks = {t: [] for t in TANKS}
    for fish, tank in assignment.items():
        tanks[tank].append(fish)

    for tank, fish_list in tanks.items():
        base_names = [get_base_name(f) for f in fish_list]
        
        # Biomass check
        if sum(get_size(f) for f in fish_list) > 20:
            return False
        
        # Large predator check
        if len([f for f in fish_list if get_size(f) >= 6]) > 1:
            return False
        
        # Detritivore check
        if not any(d in base_names for d in DETRITIVORES):
            return False
        
        # BlueShark schooling
        if "BlueShark" in fish_list:
            small_fish = [f for f in fish_list if get_size(f) <= 3]
            if 0 < len(small_fish) < 3:
                return False
        
        # Incompatibilities
        if "Angelfish" in base_names and ("Oscar" in fish_list or "Lionfish" in fish_list):
            return False
        if "Guppy" in base_names and ("Oscar" in fish_list or "Lionfish" in fish_list):
            return False
        if "Catfish" in fish_list and "Lionfish" in fish_list:
            return False
        if "Puffer" in fish_list and "Surgeon" in fish_list:
            return False
        if "Betta" in base_names and "Guppy" in base_names:
            return False
        if "Coralfish" in fish_list and ("Manta" in fish_list or "Oscar" in fish_list):
            return False
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

    return True

def solve_backtrack():
    """Backtracking solver with early pruning"""
    fish_names = [name for name, _ in SPECIES]
    allowed = {fish: get_allowed_tanks(fish) for fish in fish_names}
    assignment = {}

    def backtrack(idx):
        if idx == len(fish_names):
            return check_solution(assignment)

        fish = fish_names[idx]
        for tank in allowed[fish]:
            assignment[fish] = tank
            
            # Early pruning on partial assignment
            tank_fish = [f for f in assignment if assignment[f] == tank]
            
            # Biomass check
            if sum(get_size(f) for f in tank_fish) > 20:
                continue
            
            # Large predator check
            if len([f for f in tank_fish if get_size(f) >= 6]) > 1:
                continue
            
            # Incompatibility checks
            base_names = [get_base_name(f) for f in tank_fish]
            if "Angelfish" in base_names and ("Oscar" in tank_fish or "Lionfish" in tank_fish):
                continue
            if "Guppy" in base_names and ("Oscar" in tank_fish or "Lionfish" in tank_fish):
                continue
            if "Catfish" in tank_fish and "Lionfish" in tank_fish:
                continue
            if "Puffer" in tank_fish and "Surgeon" in tank_fish:
                continue
            if "Betta" in base_names and "Guppy" in base_names:
                continue
            if "Coralfish" in tank_fish and ("Manta" in tank_fish or "Oscar" in tank_fish):
                continue
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

            if backtrack(idx + 1):
                return True

        del assignment[fish]
        return False

    if backtrack(0):
        return assignment
    return None

if __name__ == "__main__":
    solution = solve_backtrack()
    if solution:
        for tank in TANKS:
            fish_in_tank = [f for f in solution if solution[f] == tank]
            total_size = sum(get_size(f) for f in fish_in_tank)
            print(f"{tank} (biomass {total_size}): {fish_in_tank}")
        print("\nJSON for API:")
        print(json.dumps({"assignments": solution}))

‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

Step 3: Solution Found

Step 4: Submit Solution

 bash read-only • copy allowed Copy
curl -X POST https://undutmaning-mangfald.chals.io/verify \
  -H "Content-Type: application/json" \
  -d '{"assignments": {"BlueShark": "TankA", "Goldfish": "TankA", ...}}'

‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

Server responds with the flag.

Notes

• The flag "REDACTED" (Swedish: "If you used AI, you're not sigma!") is ironic — the challenge is perfectly suited for algorithmic solving
• Total biomass (79) vs total capacity (80) means the solution is tight — almost no slack
• Backtracking with early pruning is efficient enough; no need for advanced CSP solvers
• Domain reduction (pre-computing allowed tanks) significantly reduces search space
• The python-constraint library can also solve this, but pure backtracking works fine ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍