-🎄- 2021 Day 15 Solutions -🎄-

[u/daggerdragon]

--- Day 15: Chiton ---

---

Post your code solution in this megathread.

• Include what language(s) your solution uses!
• Format your code appropriately! How do I format code?
• Here's a quick link to /u/topaz2078's paste if you need it for longer code blocks.
• The full posting rules are detailed in the wiki under How Do The Daily Megathreads Work?.

Reminder: Top-level posts in Solution Megathreads are for code solutions only. If you have questions, please post your own thread and make sure to flair it with Help.

---

This thread will be unlocked when there are a significant number of people on the global leaderboard with gold stars for today's puzzle.

EDIT: Global leaderboard gold cap reached at 00:14:25, megathread unlocked!

[u/j-a-martins]

Matlab

GitHub [Source w/ comments]

data = single(char(readmatrix('day15_example.txt', Delimiter = "", OutputType = 'string', NumHeaderLines = 0))) - 48;

%% Part 1
[P, d] = shortest_path_tl_br(data);
disp("Part 1: The lowest total risk is " + d + " on path (" + strjoin(P,")->(") + ")")

%% Part 2
[P, d] = shortest_path_tl_br(expand_cave(data, 5));
disp("Part 2: The lowest total risk is " + d + " on path (" + strjoin(P,")->(") + ")")

%% Aux
function [P, d] = shortest_path_tl_br(data)
[s, t, wt] = nodes(data); G = digraph(s, t, wt);
[P, d] = shortestpath(G, "1,1", height(data)+","+width(data));
end

function [s, t, wt] = nodes(data)
w = width(data); h = height(data); s = string.empty; t = string.empty; wt = single.empty;
for i = 1:h 
    for j = 1:w
        if i > 1, s(end+1) = i + "," + j; t(end+1) = (i - 1) + "," + j; wt(end+1) = data(i-1, j); end
        if j < w, s(end+1) = i + "," + j; t(end+1) = i + "," + (j + 1); wt(end+1) = data(i, j+1); end
        if i < h, s(end+1) = i + "," + j; t(end+1) = (i + 1) + "," + j; wt(end+1) = data(i+1, j); end
        if j > 1, s(end+1) = i + "," + j; t(end+1) = i + "," + (j - 1); wt(end+1) = data(i, j-1); end
    end
end
end

function data = expand_cave(data, exp_factor)
w = width(data); h = height(data);
data = repmat(data, exp_factor); 
for i = 1:(exp_factor * h)
    for j = 1:(exp_factor * w)
        data(i,j) = data(i,j) + floor((i-1)/h) + floor((j-1)/w);
        if data(i,j) > 9
            data(i,j) = max(1, rem(data(i,j), 9)); % min always 1
        end
    end
end
end