2021/day15/day15.erl

   1 %% to compile: erlc day3A.erl
   2 %% to run: erl -noshell -s day3 solve
   3 %%
   4 -module(day15).
   5
   6 -export ([solve/0, solve/1, solve/2]).
   7 -export ([read_input/0]).
   8
   9 -compile([export_all]).
  10
  11 solve() ->
  12     solve(['1']),
  13     solve(['2']),
  14     init:stop().
  15
  16 solve(A) ->
  17     solve(A, read_input()).
  18
  19 solve(['1'], D) ->
  20     io:format("The solution to ~p puzzle1 is: ~p~n", [?MODULE, solve(1, D)]);
  21 solve(1, D) ->
  22     solution1(D);
  23 solve(['2'], D) ->
  24     io:format("The solution to ~p puzzle2 is: ~p~n", [?MODULE, solve(2, D)]);
  25 solve(2, D) ->
  26     solution2(D).
  27
  28 read_input() ->
  29         {ok, IO} = file:open("input.txt", 'read'),
  30         Data = read_input(IO),
  31         file:close(IO),
  32         Data.
  33
  34 read_input(IO) ->
  35         read_input(IO, []).
  36
  37 read_input(IO, Input) ->
  38         case read_line(IO) of
  39                 'eof' -> Input;
  40                 Line -> read_input(IO, Input ++ [Line])
  41         end.
  42
  43 read_line(IO) ->
  44         case file:read_line(IO) of
  45                 'eof' -> 'eof';
  46                 {ok, Line} -> [ X - $0 || X <- Line, [X] /= "\n"]
  47         end.
  48
  49 solution1(Input) ->
  50     Graph = astar:graph(Input),
  51     astar:search(Graph, {0, 0}, {99, 99}).
  52
  53 solution2(Input) ->
  54     Graph = astar:graph(Input),
  55     astar:search(Graph, {0, 0}, {499, 499}).
  56
  57 coords([H|_] =  Table) ->
  58   X = length(H),
  59   Y = length(Table),
  60   lists:flatten([[{A,B} || A <- lists:seq(1,X)] || B <- lists:seq(1,Y)]).
  61
  62
  63 %init_data({X,Y}, Table) when X =< 100 andalso Y =< 100 ->
  64 %    lists:nth(X, lists:nth(Y, Table));
  65 init_data({X,Y}, Table) ->
  66     X1 =
  67     case (X rem 100) of
  68         0 -> 100;
  69         A -> A
  70     end,
  71     Y1 =
  72     case (Y rem 100) of
  73         0 -> 100;
  74         B -> B
  75     end,
  76     D = lists:nth(X1, lists:nth(Y1, Table)),
  77     D1 = (D + ((X-1) div 100) + ((Y-1) div 100)) rem 9,
  78     D2 =
  79     case D1 of
  80             0 -> 9;
  81             C -> C
  82     end,
  83 %%    io:format("~p -> ~p -> ~p~n", [{X,Y},{X1,Y1},{D,D2}]),
  84     D2.
  85
  86 get_value({X,Y}, _Table)  when X < 1; Y < 1; X > 500; Y > 500 -> 'invalid';
  87 get_value({X,Y}, Table) ->
  88 %%        {C, V} = lists:keyfind(C, 1, Data),
  89 %%       V.
  90     X1 =
  91     case (X rem 100) of
  92         0 -> 100;
  93         A -> A
  94     end,
  95     Y1 =
  96     case (Y rem 100) of
  97         0 -> 100;
  98         B -> B
  99     end,
 100     D = lists:nth(X1, lists:nth(Y1, Table)),
 101     D1 = (D + ((X-1) div 100) + ((Y-1) div 100)) rem 9,
 102     D2 =
 103     case D1 of
 104             0 -> 9;
 105             C -> C
 106     end,
 107 %%    io:format("~p -> ~p -> ~p~n", [{X,Y},{X1,Y1},{D,D2}]),
 108     D2.
 109
 110 get_neighbors({X,Y}, Data) ->
 111     Neigbours = [{X+1,Y},{X-1,Y},{X,Y+1},{X,Y-1}],
 112     lists:filter(fun({_,E}) -> E /= 'invalid' end, [{C, get_value(C, Data)} || C <- Neigbours]).
 113
 114 build_graph(Coords, Data) ->
 115         Graph = digraph:new(),
 116         [digraph:add_vertex(Graph, C) || C <- Coords],
 117         add_edges(Graph, Data, Coords).
 118
 119 make_coords(Coords, Loop) ->
 120         [{X  * Loop , Y * Loop} || {X,Y} <- Coords].
 121
 122 add_edges(Graph, Data, []) -> Graph;
 123 add_edges(Graph, Data, [C|Rest]) ->
 124     Neighbors = get_neighbors(C, Data),
 125     [digraph:add_edge(Graph, C, X, V) || {X,V} <- Neighbors],
 126     add_edges(Graph, Data, Rest).
 127
 128 dijkstra(Graph,Start_node_name) ->
 129     Paths = dict:new(),
 130     Unvisited = gb_sets:new(),
 131     Unvisited_nodes = gb_sets:insert({0,Start_node_name,root},Unvisited),
 132     Paths_updated = loop_through_nodes(Graph,Paths,Unvisited_nodes),
 133     Paths_updated.
 134
 135
 136 loop_through_nodes(Graph,Paths,Unvisited_nodes) ->
 137     %% We need this condition to stop looping through the Unvisited nodes if it is empty
 138     case gb_sets:is_empty(Unvisited_nodes) of
 139         false ->
 140             {{Current_weight,Current_name,Previous_node}, Unvisited_nodes_updated} = gb_sets:take_smallest(Unvisited_nodes),
 141               case dict:is_key(Current_name,Paths) of
 142                 false ->
 143                     Paths_updated = dict:store(Current_name,{Previous_node,Current_weight},Paths),
 144                     Out_edges = digraph:out_edges(Graph,Current_name),
 145                     Unvisited_nodes_updated_2 = loop_through_edges(Graph,Out_edges,Paths_updated,Unvisited_nodes_updated,Current_weight),
 146                     loop_through_nodes(Graph,Paths_updated,Unvisited_nodes_updated_2);
 147                 true ->
 148                     loop_through_nodes(Graph,Paths,Unvisited_nodes_updated)
 149             end;
 150         true ->
 151             Paths
 152     end.
 153
 154 loop_through_edges(Graph,[],Paths,Unvisited_nodes,Current_weight) ->
 155     Unvisited_nodes;
 156
 157 loop_through_edges(Graph,Edges,Paths,Unvisited_nodes,Current_weight) ->
 158     [Current_edge|Rest_edges] = Edges,
 159     {Current_edge,Current_node,Neighbour_node,Edge_weight} = digraph:edge(Graph,Current_edge),
 160     case dict:is_key(Neighbour_node,Paths) of
 161         false ->
 162             Unvisited_nodes_updated = gb_sets:insert({Current_weight+Edge_weight,Neighbour_node,Current_node},Unvisited_nodes),
 163             loop_through_edges(Graph,Rest_edges,Paths,Unvisited_nodes_updated,Current_weight);
 164         true ->
 165             loop_through_edges(Graph,Rest_edges,Paths,Unvisited_nodes,Current_weight)
 166     end.