aoc2025/day12/areacache.zig

const std = @import("std");

const areaModule = @import("area.zig");

const Area = areaModule.Area;

pub const AreaHashContext = struct {
    pub fn hash(ctx: AreaHashContext, key: Area) u64 {
        _ = ctx;

        var hasher = std.hash.Wyhash.init(0);
        hasher.update(std.mem.asBytes(&key.rows));
        hasher.update(std.mem.asBytes(&key.cols));
        hasher.update(key.data);
        return hasher.final();
    }

    pub fn eql(ctx: AreaHashContext, a: Area, b: Area) bool {
        _ = ctx;

        if (a.rows != b.rows) {
            return false;
        }

        if (a.cols != b.cols) {
            return false;
        }

        return std.mem.eql(u8, a.data, b.data);
    }
};

const AreaCacheEntry = struct {
    possibleShapeCounts: std.ArrayList([]i32) = std.ArrayList([]i32).empty,
    impossibleShapeCounts: std.ArrayList([]i32) = std.ArrayList([]i32).empty,
};

const AreaHashMap = std.hash_map.HashMap(Area, AreaCacheEntry, AreaHashContext,
                                         std.hash_map.default_max_load_percentage);

pub const AreaCacheResult = enum {
    kNotFound,
    kPossible,
    kImpossible
};

fn matchesPossible(shapeCounts: []i32, possibleShapeCounts: [][]i32) bool {
    for (possibleShapeCounts) |possibleShapeCount| {
        var isPossible = true;

        for (0 .. shapeCounts.len) |i| {
            if (shapeCounts[i] > possibleShapeCount[i]) {
                isPossible = false;
                break;
            }
        }

        if (isPossible) {
            return true;
        }
    }

    return false;
}

fn matchesImpossible(shapeCounts: []i32, impossibleShapeCounts: [][]i32) bool {
    for (impossibleShapeCounts) |impossibleShapeCount| {
        var isImpossible = true;

        for (0 .. shapeCounts.len) |i| {
            if (shapeCounts[i] < impossibleShapeCount[i]) {
                isImpossible = false;
                break;
            }
        }

        if (isImpossible) {
            return true;
        }
    }

    return false;
}


pub const AreaCache = struct {
    childAllocator: std.mem.Allocator,
    arenaAllocator: *std.heap.ArenaAllocator,
    allocator: std.mem.Allocator,
    context: AreaHashContext,
    entries: AreaHashMap,
    hitStat: u64,
    totalStat: u64,



    pub fn init(childAllocator: std.mem.Allocator) !AreaCache {
        var areaCache: AreaCache = undefined;
        areaCache.childAllocator = childAllocator;
        areaCache.arenaAllocator = try childAllocator.create(std.heap.ArenaAllocator);
        areaCache.arenaAllocator.* = std.heap.ArenaAllocator.init(childAllocator);
        areaCache.allocator = areaCache.arenaAllocator.allocator();
        areaCache.context = .{};
        areaCache.entries = AreaHashMap.initContext(areaCache.allocator, areaCache.context);
        areaCache.hitStat = 0;
        areaCache.totalStat = 0;

        return areaCache;
    }

    pub fn deinit(self: *const AreaCache) void {
        self.arenaAllocator.deinit();
        self.childAllocator.destroy(self.arenaAllocator);
    }

    pub fn addPossibleCacheEntry(self: *AreaCache, area: *const Area, shapeCounts: []i32) !void {
        var result = try self.entries.getOrPut(area.*);
        if (!result.found_existing) {
            result.key_ptr.data = try self.allocator.alloc(u8, area.data.len);
            std.mem.copyForwards(u8, result.key_ptr.data, area.data);
            result.value_ptr.* = .{};
        }

        const newShapeCounts = try result.value_ptr.possibleShapeCounts.addOne(self.allocator);
        newShapeCounts.* = try self.allocator.alloc(i32, shapeCounts.len);
        std.mem.copyForwards(i32, newShapeCounts.*, shapeCounts);
    }

    pub fn addImpossibleCacheEntry(self: *AreaCache, area: *const Area, shapeCounts: []i32) !void {
        var result = try self.entries.getOrPut(area.*);
        if (!result.found_existing) {
            result.key_ptr.data = try self.allocator.alloc(u8, area.data.len);
            std.mem.copyForwards(u8, result.key_ptr.data, area.data);
            result.value_ptr.* = .{};
        }

        const newShapeCounts = try result.value_ptr.impossibleShapeCounts.addOne(self.allocator);
        newShapeCounts.* = try self.allocator.alloc(i32, shapeCounts.len);
        std.mem.copyForwards(i32, newShapeCounts.*, shapeCounts);
    }

    pub fn check(self: *AreaCache, area: *const Area, shapeCounts: []i32) AreaCacheResult {
        self.totalStat += 1;
        if (self.entries.get(area.*)) |cacheEntry| {
            if (matchesPossible(shapeCounts, cacheEntry.possibleShapeCounts.items)) {
                self.hitStat += 1;
                return AreaCacheResult.kPossible;
            }

            if (matchesImpossible(shapeCounts, cacheEntry.impossibleShapeCounts.items)) {
                self.hitStat += 1;
                return AreaCacheResult.kImpossible;
            }
        }

        return AreaCacheResult.kNotFound;
    }
};