Fuel Sort level creation

main.rs

use rand::prelude::*;
use rand_pcg::Pcg64;
use rayon::prelude::*;
use rustc_hash::FxHashMap;
use std::fs::File;
use std::io::Write;

const MAX_HEIGHT: usize = 10;
const MAX_GLASSES: usize = 10;
const TOTAL_LEVELS: usize = 30;

// Fixed-size glass representation - no heap allocations
#[derive(Clone, Copy, PartialEq, Eq, Hash)]
struct Glass {
    cells: [u8; MAX_HEIGHT],
    height: u8,
}

impl Glass {
    fn new(height: usize) -> Self {
        Glass {
            cells: [0; MAX_HEIGHT],
            height: height as u8,
        }
    }

    #[inline]
    fn is_complete(&self) -> bool {
        let c = self.cells[0];
        if c == 0 {
            return true; // Empty is considered complete
        }
        for i in 1..self.height as usize {
            if self.cells[i] != c {
                return false;
            }
        }
        true
    }

    #[inline]
    fn is_single_color_full(&self) -> bool {
        let c = self.cells[0];
        if c == 0 {
            return false;
        }
        for i in 1..self.height as usize {
            if self.cells[i] != c {
                return false;
            }
        }
        true
    }

    // Returns (top_color, top_count, empty_count)
    #[inline]
    fn info(&self) -> (u8, u8, u8) {
        let h = self.height as usize;
        let mut top_color = 0u8;
        let mut top_count = 0u8;
        let mut empty_count = 0u8;
        let mut counting = true;

        for i in (0..h).rev() {
            let c = self.cells[i];
            if c > 0 {
                if top_color == 0 {
                    top_color = c;
                    top_count = 1;
                } else if c == top_color && counting {
                    top_count += 1;
                } else {
                    counting = false;
                }
            } else {
                empty_count += 1;
            }
        }
        (top_color, top_count, empty_count)
    }
}

// Fixed-size level state
#[derive(Clone, Copy, PartialEq, Eq, Hash)]
struct State {
    glasses: [Glass; MAX_GLASSES],
    num_glasses: u8,
    height: u8,
}

impl State {
    fn new(height: usize) -> Self {
        State {
            glasses: [Glass::new(height); MAX_GLASSES],
            num_glasses: 0,
            height: height as u8,
        }
    }

    #[inline]
    fn is_solved(&self) -> bool {
        for i in 0..self.num_glasses as usize {
            if !self.glasses[i].is_complete() {
                return false;
            }
        }
        true
    }

    fn has_trivial_glass(&self) -> bool {
        for i in 0..self.num_glasses as usize {
            if self.glasses[i].is_single_color_full() {
                return true;
            }
        }
        false
    }

    // Returns true if move was valid
    #[inline]
    fn try_move(&mut self, from: usize, to: usize) -> bool {
        if from == to {
            return false;
        }

        let (from_color, from_count, from_empty) = self.glasses[from].info();
        if from_color == 0 {
            return false;
        }

        let (to_color, _, to_empty) = self.glasses[to].info();

        // Can move if target is empty, or same color with enough room
        if to_color == 0 || (to_color == from_color && from_count <= to_empty) {
            let h = self.height as usize;
            // Move the blocks
            for i in 0..from_count as usize {
                self.glasses[from].cells[h - 1 - from_empty as usize - i] = 0;
                self.glasses[to].cells[h - to_empty as usize + i] = from_color;
            }
            true
        } else {
            false
        }
    }

    // Canonical form for hashing - sort glasses by content
    fn canonical(&self) -> Self {
        let mut result = *self;
        // Simple bubble sort for small arrays
        let n = self.num_glasses as usize;
        for i in 0..n {
            for j in i + 1..n {
                let mut less = false;
                for k in 0..self.height as usize {
                    if result.glasses[i].cells[k] < result.glasses[j].cells[k] {
                        less = true;
                        break;
                    } else if result.glasses[i].cells[k] > result.glasses[j].cells[k] {
                        break;
                    }
                }
                if less {
                    let tmp = result.glasses[i];
                    result.glasses[i] = result.glasses[j];
                    result.glasses[j] = tmp;
                }
            }
        }
        result
    }

    fn to_string(&self) -> String {
        let mut glasses_str = Vec::new();
        for i in 0..self.num_glasses as usize {
            let mut s = String::new();
            for j in 0..self.height as usize {
                let c = self.glasses[i].cells[j];
                if c == 0 {
                    s.push('_');
                } else {
                    s.push((b'0' + c) as char);
                }
            }
            glasses_str.push(s);
        }
        glasses_str.join(",")
    }
}

// BFS solver with visited state tracking
fn solve(initial: &State) -> Option<(Vec<(u8, u8)>, usize)> {
    if initial.is_solved() {
        return Some((Vec::new(), 1));
    }

    // Use BFS for shortest solution
    let mut visited: FxHashMap<State, (u8, u8, u32)> = FxHashMap::with_capacity_and_hasher(500000, Default::default());
    let mut queue: Vec<State> = Vec::with_capacity(10000);

    let canonical = initial.canonical();
    visited.insert(canonical, (255, 255, u32::MAX)); // Sentinel for start
    queue.push(*initial);

    let mut head = 0;

    while head < queue.len() {
        let current = queue[head];
        let current_idx = head as u32;
        head += 1;

        // Limit search
        if head > 500000 {
            return None;
        }

        let n = current.num_glasses as usize;

        for from in 0..n {
            let (from_color, _, _) = current.glasses[from].info();
            if from_color == 0 {
                continue;
            }

            // Pruning: don't move from a complete single-color glass
            if current.glasses[from].is_single_color_full() {
                continue;
            }

            for to in 0..n {
                if from == to {
                    continue;
                }

                let mut next = current;
                if next.try_move(from, to) {
                    if next.is_solved() {
                        // Reconstruct path
                        let mut path = vec![(from as u8, to as u8)];
                        let mut idx = current_idx;
                        while idx != u32::MAX {
                            let state_canon = queue[idx as usize].canonical();
                            if let Some(&(f, t, parent)) = visited.get(&state_canon) {
                                if f != 255 {
                                    path.push((f, t));
                                }
                                idx = parent;
                            } else {
                                break;
                            }
                        }
                        path.reverse();
                        return Some((path, visited.len()));
                    }

                    let next_canon = next.canonical();
                    if !visited.contains_key(&next_canon) {
                        visited.insert(next_canon, (from as u8, to as u8, current_idx));
                        queue.push(next);
                    }
                }
            }
        }
    }

    None
}

fn create_level(seed: u64, glass_height: usize, color_count: usize) -> Option<(State, Vec<(u8, u8)>, usize)> {
    let mut rng = Pcg64::seed_from_u64(seed);

    let empty_base = if color_count >= 7 { 2 } else { 1 };

    for extra_empty in 0..4 {
        let empty_count = empty_base + extra_empty;
        let total_glasses = color_count + empty_count;

        if total_glasses > MAX_GLASSES {
            continue;
        }

        // Create shuffled colors
        let mut mixed: Vec<u8> = (0..color_count)
            .flat_map(|c| vec![c as u8 + 1; glass_height])
            .collect();
        mixed.shuffle(&mut rng);

        // Build state
        let mut state = State::new(glass_height);
        state.num_glasses = total_glasses as u8;

        for c in 0..color_count {
            for i in 0..glass_height {
                state.glasses[c].cells[i] = mixed[c * glass_height + i];
            }
        }
        // Empty glasses are already zeroed

        // Check if trivial
        if state.has_trivial_glass() {
            continue;
        }

        // Try to solve
        if let Some((solution, states_explored)) = solve(&state) {
            if solution.len() >= 2 {
                return Some((state, solution, states_explored));
            }
        }
    }

    None
}

fn get_difficulty(level_idx: usize) -> (usize, usize) {
    // Original hardcoded ranges for 1000 levels:
    //   0..=24   => (3, 2),  25..=49  => (3, 3),  50..=99  => (3, 3),
    //   100..=149 => (4, 4), 150..=199 => (4, 4), 200..=249 => (4, 5),
    //   250..=299 => (5, 5), 300..=399 => (5, 6), 400..=499 => (5, 6),
    //   500..=599 => (6, 7), 600..=699 => (7, 7), 700..=799 => (8, 8),
    //   800..=899 => (9, 8), _ => (10, 8),

    // Difficulty steps with weights (higher weight = more levels at that step)
    // Fast ramp early (weight 1), slowing down in the middle (2), lingering at hard (3)
    const STEPS: [(usize, usize, usize); 14] = [
        // (height, colors, weight)
        (3, 2, 1), (3, 3, 1), (4, 3, 1), (4, 4, 1), (4, 5, 1),   // fast ramp
        (5, 5, 2), (5, 6, 2), (6, 6, 2), (6, 7, 2),               // medium
        (7, 7, 3), (7, 8, 3), (8, 8, 3), (9, 8, 3),               // slow
        (10, 8, 3),                                                  // max
    ];

    let total_weight: usize = STEPS.iter().map(|s| s.2).sum();
    let playable = TOTAL_LEVELS - 2;
    let adjusted_idx = level_idx - 2;

    // Distribute levels proportionally by weight
    let mut cumulative = 0;
    for (i, &(h, c, w)) in STEPS.iter().enumerate() {
        let step_levels = if i == STEPS.len() - 1 {
            playable - cumulative // last step gets the remainder
        } else {
            (w * playable + total_weight / 2) / total_weight  // rounded
        };
        let step_levels = step_levels.max(1);
        if adjusted_idx < cumulative + step_levels {
            return (h, c);
        }
        cumulative += step_levels;
    }

    let last = STEPS.last().unwrap();
    (last.0, last.1)
}

fn generate_level_for_slot(level_idx: usize, base_seed: u64) -> Option<String> {
    let (height, colors) = get_difficulty(level_idx);

    // Try all 100 seeds in parallel and pick the level with the most states explored (most deadends)
    let candidates: Vec<_> = (0..100u64)
        .into_par_iter()
        .filter_map(|attempt| {
            let seed = base_seed + level_idx as u64 * 1000 + attempt;
            create_level(seed, height, colors)
                .filter(|(_, solution, _)| solution.len() >= 2)
        })
        .collect();

    // Count used glasses for each candidate, then pick: fewest glasses first, most states explored second
    let best = candidates
        .into_iter()
        .map(|(state, solution, states_explored)| {
            let mut used = vec![false; state.num_glasses as usize];
            for &(f, t) in &solution {
                used[f as usize] = true;
                used[t as usize] = true;
            }
            for i in 0..state.num_glasses as usize {
                if state.glasses[i].cells[0] != 0 {
                    used[i] = true;
                }
            }
            let used_count = used.iter().filter(|&&u| u).count();
            (state, solution, states_explored, used_count)
        })
        .min_by_key(|(_, _, states_explored, used_count)| {
            // Fewest glasses first, then most states explored (negate to get max)
            (*used_count, usize::MAX - *states_explored)
        });

    best.map(|(state, solution, _, _)| {
        // Find which glasses are used in the solution
        let mut used = vec![false; state.num_glasses as usize];
        for &(f, t) in &solution {
            used[f as usize] = true;
            used[t as usize] = true;
        }
        for i in 0..state.num_glasses as usize {
            if state.glasses[i].cells[0] != 0 {
                used[i] = true;
            }
        }

        // Build old-to-new index mapping, dropping unused glasses
        let mut index_map = vec![0u8; state.num_glasses as usize];
        let mut new_state = State::new(height);
        let mut new_count = 0u8;
        for i in 0..state.num_glasses as usize {
            if used[i] {
                index_map[i] = new_count;
                new_state.glasses[new_count as usize] = state.glasses[i];
                new_count += 1;
            }
        }
        new_state.num_glasses = new_count;

        // Remap solution indices
        let solution_str: String = solution
            .iter()
            .flat_map(|(f, t)| vec![(b'a' + index_map[*f as usize]) as char, (b'a' + index_map[*t as usize]) as char])
            .collect();
        format!("{}|{}|{}", height, new_state.to_string(), solution_str)
    })
}

fn main() {
    println!("Generating {} levels using parallel processing...", TOTAL_LEVELS);

    // Tutorial levels (fixed)
    let tutorial_levels = vec![
        "3|1__,11_|ab".to_string(),
        "3|221,112,___|acbabc".to_string(),
    ];

    let base_seed = 42u64;

    // Generate remaining levels sequentially (seeds are parallelized within each level)
    let generated: Vec<Option<String>> = (2..TOTAL_LEVELS)
        .map(|idx| {
            let result = generate_level_for_slot(idx, base_seed);
            let (h, c) = get_difficulty(idx);
            eprintln!("Done level {} (h={}, c={})", idx, h, c);
            result
        })
        .collect();

    // Combine tutorial + generated levels
    let mut levels = tutorial_levels;
    for level_opt in generated {
        if let Some(level) = level_opt {
            levels.push(level);
        }
    }

    // Write to JSON
    let json = serde_json::to_string_pretty(&levels).unwrap();
    let mut file = File::create("all_levels.json").unwrap();
    file.write_all(json.as_bytes()).unwrap();

    println!("Generated {} levels to all_levels.json", levels.len());
}