Help nesting data structures

Help
1

Problem statement

Hey there. I’m doing advent of code day 6 and I want to store checks for a coordinate (x,y) and I want x to be able to map to many y’s.

I immediately wanted to use something which allows for duplicate y values.
I understand I can go off and craft my own data structures, but I’d rather not do that.

Attempting to nest autohashmap

I know this is possible, but I get memory access errors when I try it. There is some trick I’m unaware of.

AutoHashMap 
const std = @import("std");
const input = @embedFile("input.txt");

const Coord = struct {
    x: usize,
    y: usize,
};

const DIRECTION = enum(u3) {
    UP,
    RIGHT,
    DOWN,
    LEFT,
};

fn check_for_obstical(data: std.ArrayList([]const u8), location: Coord, direction: DIRECTION) bool {
    switch (direction) {
        DIRECTION.UP => {
            return data.items[location.y - 1][location.x] != '#';
        },
        DIRECTION.RIGHT => {
            return data.items[location.y][location.x + 1] != '#';
        },
        DIRECTION.DOWN => {
            return data.items[location.y + 1][location.x] != '#';
        },
        DIRECTION.LEFT => {
            return data.items[location.y][location.x - 1] != '#';
        },
    }
}

fn spin(data: std.ArrayList([]const u8), location: Coord, direction: DIRECTION) DIRECTION {
    const begin = direction;
    var new_dir = blk: {
        var nd = begin;
        switch (begin) {
            DIRECTION.UP => {
                nd = DIRECTION.RIGHT;
            },
            DIRECTION.RIGHT => {
                nd = DIRECTION.DOWN;
            },
            DIRECTION.DOWN => {
                nd = DIRECTION.LEFT;
            },
            DIRECTION.LEFT => {
                nd = DIRECTION.UP;
            },
        }
        break :blk nd;
    };

    while (begin != new_dir) {
        if (check_for_obstical(data, location, new_dir)) {
            return new_dir;
        }
        new_dir = blk: {
            var nd = begin;
            switch (begin) {
                DIRECTION.UP => {
                    nd = DIRECTION.RIGHT;
                },
                DIRECTION.RIGHT => {
                    nd = DIRECTION.DOWN;
                },
                DIRECTION.DOWN => {
                    nd = DIRECTION.LEFT;
                },
                DIRECTION.LEFT => {
                    nd = DIRECTION.UP;
                },
            }
            break :blk nd;
        };
    }
    unreachable;
}

fn part_1(in: []const u8) !usize {
    var solution: usize = undefined;
    solution = 0;

    var arena = std.heap.ArenaAllocator.init(std.heap.page_allocator);
    defer arena.deinit();
    const allocator = arena.allocator();

    var data = std.ArrayList([]const u8).init(allocator);
    var guard_location: Coord = undefined;

    var it = std.mem.tokenizeScalar(u8, in, '\n');

    while (it.next()) |line| {
        try data.append(line);

        // look for the starting point
        const guard = std.mem.indexOf(u8, line, "^");
        if (guard) |location| {
            guard_location.x = location;
            guard_location.y = data.items.len - 1;
        }
    }

    var visited = std.AutoHashMap(usize, std.AutoHashMap(usize, void)).init(allocator);
    var inside_data = true;
    var direction = DIRECTION.UP;
    while (inside_data) {
        // mark current location as visited
        const gop_result = try visited.getOrPut(guard_location.x);
        try gop_result.value_ptr.*.put(guard_location.y, {});
        switch (direction) {
            DIRECTION.UP => {
                // check if can proceed upwards
                inside_data = guard_location.y - 1 > 0;
                if (!inside_data) break;
                const can_proceed = inside_data and check_for_obstical(data, guard_location, direction);
                if (can_proceed) {
                    guard_location.y = guard_location.y - 1;
                } else {
                    // attempt to turn right
                    direction = spin(data, guard_location, direction);
                }
            },
            DIRECTION.DOWN => {},
            DIRECTION.LEFT => {},
            DIRECTION.RIGHT => {},
        }
    }

    std.debug.print("start: {}\n", .{guard_location});
    std.debug.print("solution: {d}\n", .{solution});
    return solution;
}

pub fn main() !void {
    _ = try part_1(input);
}

test "test" {
    const test_in =
        \\....#.....
        \\.........#
        \\..........
        \\..#.......
        \\.......#..
        \\..........
        \\.#..^.....
        \\........#.
        \\#.........
        \\......#...
    ;
    const test_1 = try part_1(test_in);
    try std.testing.expect(test_1 == 41);
}
Errors 
[jud@archlinux day_6]$ zig run src/main.zig
thread 13578 panic: incorrect alignment
/home/jud/zig_versions/0.13.0/files/lib/std/hash_map.zig:985:44: 0x10a58db in header (main)
            return @ptrCast(@as([*]Header, @ptrCast(@alignCast(self.metadata.?))) - 1);
                                           ^
/home/jud/zig_versions/0.13.0/files/lib/std/hash_map.zig:999:31: 0x108be57 in capacity (main)
            return self.header().capacity;
                              ^
/home/jud/zig_versions/0.13.0/files/lib/std/hash_map.zig:1371:39: 0x108bfcb in getOrPutAssumeCapacityAdapted__anon_8971 (main)
            const mask = self.capacity() - 1;
                                      ^
/home/jud/zig_versions/0.13.0/files/lib/std/hash_map.zig:1345:54: 0x107ed4d in getOrPutContextAdapted__anon_8793 (main)
            return self.getOrPutAssumeCapacityAdapted(key, key_ctx);
                                                     ^
/home/jud/zig_versions/0.13.0/files/lib/std/hash_map.zig:1318:56: 0x106f5d5 in getOrPutContext (main)
            const gop = try self.getOrPutContextAdapted(allocator, key, ctx, ctx);
                                                       ^
/home/jud/zig_versions/0.13.0/files/lib/std/hash_map.zig:1244:52: 0x10402f0 in putContext (main)
            const result = try self.getOrPutContext(allocator, key, ctx);
                                                   ^
/home/jud/zig_versions/0.13.0/files/lib/std/hash_map.zig:552:45: 0x103af0a in put (main)
            return self.unmanaged.putContext(self.allocator, key, value, self.ctx);
                                            ^
/home/jud/code/AoC24/day_6/src/main.zig:110:39: 0x103a655 in part_1 (main)
        try gop_result.value_ptr.*.put(guard_location.y, {});
                                      ^
/home/jud/code/AoC24/day_6/src/main.zig:136:19: 0x103b831 in main (main)
    _ = try part_1(input);
                  ^
/home/jud/zig_versions/0.13.0/files/lib/std/start.zig:524:37: 0x103a0a5 in posixCallMainAndExit (main)
            const result = root.main() catch |err| {
                                    ^
/home/jud/zig_versions/0.13.0/files/lib/std/start.zig:266:5: 0x1039bc1 in _start (main)
    asm volatile (switch (native_arch) {
    ^
???:?:?: 0x0 in ??? (???)
Aborted (core dumped)
2

When you say duplicate y values do you mean multiple? The way you have it set up with the hash-map you won’t get duplicate ys for each individual x value.

Have you looked at StaticBitSet. You give it the size (The Maximum Y value in this case) and then can flip individual bits between 0 and that Maximum value.

3

Right to be more explicit my goal with the current setup is that I want to have multiple y values for every x value.

So I have two hashmaps.

the first is key’d on the x and the second is key’d on the y. I don’t really care about the value of the second.

So if I insert.

(1,2) —> check first map for x key. It’s not there create k/v pair and put 2 in inner map
(1,3) —> check first map for x key. It’s there. Insert 3 into existing inner map.

I’m essentially storing unique coordinates.

1 Like
4

Do you have an algorithmic reason to use nesting?

If not, you also could use the 2d coordinate as the key directly, the benefit of that would be that you can use a single hash map, instead of multiple; and you have easier write and read patterns, especially in cases where there isn’t a preferred direction, it can be beneficial; or if the data is very sparse.

If one of the directions is shared by many coordinates, it might be beneficial to use nesting, for example if you want to lookup all y’s for a specific x. But if you only want to check specific calculated coordinates, then you don’t really need a nested setup.

const std = @import("std");

const Coord = struct {
    x: usize,
    y: usize,
};

pub fn main() !void {
    var gpa = std.heap.GeneralPurposeAllocator(.{ .stack_trace_frames = 8 }){};
    const allocator = gpa.allocator();
    defer _ = gpa.deinit();

    const Coords = std.AutoHashMap(Coord, void);
    var coords = Coords.init(allocator);
    defer coords.deinit();

    try coords.put(.{ .x = 3, .y = 5 }, {});
    try coords.put(.{ .x = 3, .y = 7 }, {});
    try coords.put(.{ .x = 3, .y = 3 }, {});
    try coords.put(.{ .x = 5, .y = 5 }, {});
    try coords.put(.{ .x = 7, .y = 7 }, {});

    {
        var it = coords.keyIterator();
        while (it.next()) |coord| {
            std.debug.print("{}\n", .{coord.*});
        }
    }

    var visited = std.AutoHashMap(usize, std.AutoHashMap(usize, void)).init(allocator);
    defer {
        var it = visited.valueIterator();
        while (it.next()) |inner| inner.deinit();
        visited.deinit();
    }

    {
        var it = coords.keyIterator();
        while (it.next()) |coord| {
            var entry = try visited.getOrPut(coord.x);
            // NOTE if the entry didn't exist yet you have to initialize the inner map
            if (!entry.found_existing) entry.value_ptr.* = std.AutoHashMap(usize, void).init(allocator);
            try entry.value_ptr.put(coord.y, {});
        }
    }

    {
        var it = visited.iterator();
        while (it.next()) |entry| {
            std.debug.print("x: {}\n", .{entry.key_ptr.*});
            var ys = entry.value_ptr.keyIterator();
            while (ys.next()) |y| std.debug.print("    y: {}\n", .{y.*});
            std.debug.print("\n", .{});
        }
    }
}

When you really want to nest, you need to make sure that you initialize the inner hash map when gop_result.found_existing is false, because in that case you are supposed to set the value to its initial value and only then start using it.

So in this code:

The last line uses value_ptr which points to uninitialized memory.

5

I got it figured out.

This may not be the optimal solution @Sze, but I have struggled to do this many times before and searching for stuff online hasn’t really helped.

Hopefully this post is helpful to the next person with the same problem.

Here is the solution.

Working nested AutoHashMap 
const std = @import("std");
const input = @embedFile("input.txt");

const Coord = struct {
    x: usize,
    y: usize,
};

const DIRECTION = enum(u3) {
    UP,
    RIGHT,
    DOWN,
    LEFT,
};

fn check_for_obstical(data: std.ArrayList([]const u8), location: Coord, direction: DIRECTION) bool {
    switch (direction) {
        DIRECTION.UP => {
            return data.items[location.y - 1][location.x] != '#';
        },
        DIRECTION.RIGHT => {
            return data.items[location.y][location.x + 1] != '#';
        },
        DIRECTION.DOWN => {
            return data.items[location.y + 1][location.x] != '#';
        },
        DIRECTION.LEFT => {
            return data.items[location.y][location.x - 1] != '#';
        },
    }
}

fn spin(data: std.ArrayList([]const u8), location: Coord, direction: DIRECTION) DIRECTION {
    const begin = direction;
    var new_dir = blk: {
        var nd = begin;
        switch (begin) {
            DIRECTION.UP => {
                nd = DIRECTION.RIGHT;
            },
            DIRECTION.RIGHT => {
                nd = DIRECTION.DOWN;
            },
            DIRECTION.DOWN => {
                nd = DIRECTION.LEFT;
            },
            DIRECTION.LEFT => {
                nd = DIRECTION.UP;
            },
        }
        break :blk nd;
    };

    while (begin != new_dir) {
        if (check_for_obstical(data, location, new_dir)) {
            return new_dir;
        }
        new_dir = blk: {
            var nd = begin;
            switch (begin) {
                DIRECTION.UP => {
                    nd = DIRECTION.RIGHT;
                },
                DIRECTION.RIGHT => {
                    nd = DIRECTION.DOWN;
                },
                DIRECTION.DOWN => {
                    nd = DIRECTION.LEFT;
                },
                DIRECTION.LEFT => {
                    nd = DIRECTION.UP;
                },
            }
            break :blk nd;
        };
    }
    unreachable;
}

fn part_1(in: []const u8) !usize {
    var solution: usize = undefined;
    solution = 0;

    var arena = std.heap.ArenaAllocator.init(std.heap.page_allocator);
    defer arena.deinit();
    const allocator = arena.allocator();

    var data = std.ArrayList([]const u8).init(allocator);
    var guard_location: Coord = undefined;

    var it = std.mem.tokenizeScalar(u8, in, '\n');

    while (it.next()) |line| {
        try data.append(line);

        // look for the starting point
        const guard = std.mem.indexOf(u8, line, "^");
        if (guard) |location| {
            guard_location.x = location;
            guard_location.y = data.items.len - 1;
        }
    }

    var visited = std.AutoHashMap(usize, std.AutoHashMap(usize, void)).init(allocator);
    var inside_data = true;
    var direction = DIRECTION.UP;
    while (inside_data) {
        // mark current location as visited
        if (visited.getPtr(guard_location.x)) |inner| {
            try inner.put(guard_location.y, {});
        } else {
            var inner = std.AutoHashMap(usize, void).init(allocator);
            try inner.put(guard_location.y, {});
            try visited.put(guard_location.x, inner);
        }
        switch (direction) {
            DIRECTION.UP => {
                // check if can proceed upwards
                inside_data = guard_location.y - 1 >= 0;
                if (!inside_data) break;
                const can_proceed = inside_data and check_for_obstical(data, guard_location, direction);
                if (can_proceed) {
                    guard_location.y = guard_location.y - 1;
                } else {
                    // attempt to turn right
                    direction = spin(data, guard_location, direction);
                }
            },
            DIRECTION.RIGHT => {
                // check if can proceed down
                inside_data = guard_location.x + 1 < data.items[0].len;
                if (!inside_data) break;
                const can_proceed = inside_data and check_for_obstical(data, guard_location, direction);
                if (can_proceed) {
                    guard_location.x = guard_location.x + 1;
                } else {
                    // attempt to turn right
                    direction = spin(data, guard_location, direction);
                }
            },
            DIRECTION.DOWN => {
                // check if can proceed down
                inside_data = guard_location.y + 1 < data.items.len;
                if (!inside_data) break;
                const can_proceed = inside_data and check_for_obstical(data, guard_location, direction);
                if (can_proceed) {
                    guard_location.y = guard_location.y + 1;
                } else {
                    // attempt to turn right
                    direction = spin(data, guard_location, direction);
                }
            },
            DIRECTION.LEFT => {
                // check if can proceed left
                inside_data = guard_location.x - 1 >= 0;
                if (!inside_data) break;
                const can_proceed = inside_data and check_for_obstical(data, guard_location, direction);
                if (can_proceed) {
                    guard_location.x = guard_location.x - 1;
                } else {
                    // attempt to turn right
                    direction = spin(data, guard_location, direction);
                }
            },
        }
    }

    { // calculate solution
        var outer_key_iter = visited.valueIterator();
        while (outer_key_iter.next()) |inner_map| {
            var inner_map_key_iter = inner_map.keyIterator();
            while (inner_map_key_iter.next()) |_| {
                solution = solution + 1;
            }
        }
    }

    std.debug.print("start: {}\n", .{guard_location});
    std.debug.print("solution: {d}\n", .{solution});
    return solution;
}

pub fn main() !void {
    _ = try part_1(input);
}

test "test" {
    const test_in =
        \\....#.....
        \\.........#
        \\..........
        \\..#.......
        \\.......#..
        \\..........
        \\.#..^.....
        \\........#.
        \\#.........
        \\......#...
    ;
6

Or do this:

const gop_result = try visited.getOrPut(guard_location.x);
if(!gop_result.found_existing) gop_result.value_ptr.* = std.AutoHashMap(usize, void).init(allocator);
try gop_result.value_ptr.put(guard_location.y, {});

std.hash_map.HashMap.getOrPut:

If key exists this function cannot fail. If there is an existing item with key, then the result’s Entry pointers point to it, and found_existing is true. Otherwise, puts a new item with undefined value, and the Entry pointers point to it. Caller should then initialize the value (but not the key).

You didn’t figure it out, you avoided the problem by making your code more complicated. You need to initialize the value when .found_existing is false.

7

oof. ok.

Thanks for the code review. I’ll update my code. lol.

8

As I’ve been doing AoC myself, I’ve often wanted to use nested container types just like @Judsen, even though I know there can be better ways of doing the same. But regardless, the thought of grabbing a hold of a hashmap and sticking more hashmaps into it is almost a reflex-like reaction for someone used to coding in say Python, and I don’t feel like anyone should feel bad for doing just that, esp. in throw away code like AoC entries. @Sze 's getOrPut example is the type of thing that would be lovely as an example in the std api docs.

1 Like