You can create a directed graph by replacing all edges A <-> B with A -> B and B -> A.
Aetherus
lkuty
It still does not work. I am wondering if I will implement it in C and then call a NIF. In the very specific case of an undirected unweighted graph. But then, it is not 100% Elixir anymore 
Or maybe I implement it directly in Elixir 
0
sevenseacat
Author of Ash Framework
Yeah undirected graphs in libgraph are a bit iffy. Directed graphs are fine though, I’ve used them a lot in Advent of Code - your code might have a bug in it somewhere.
edit: I think your logic of turning coordinates into integers with rc2i may be buggy - does it distinguish between say {20, 70} and {21, 0} ?
Also you’re only counting rows and cols up to 69 - the problem states the grid goes up to {70,70}, counting from zero.
1
lkuty
I multiply the row number by 71. Thus {20,70} gives 20 * 71+70=1490 and {21,0} gives 21 * 71=1491. I count only from 1 to 69 to avoid getting out of the grid and then I add manually the edges for the four corners ({0,0}, {0,70}, {70,0} and {70,70}). When I go from 1 to 69 for row and col, I add the edges to {row-1,col}, {row,col+1}, {row+1,col} and {row,col-1} to make connections to its four neighbors.
However there might still be a bug lurking somewhere.
0
sevenseacat
Author of Ash Framework
Yeah it sounds like its overcomplicating things for sure! Bugs lurk when there is overcomplication… This is why I stick to using {row, col} as my graph vertices, it also helps me print out grids to see errors
0
lkuty
Ha I thought it was quite simple If I don’t place any obstacles, A* finds a path from {0,0} to {70,70} which looks good: [{0, 0}, {0, 1}, {1, 1}, {1, 2}, {1, 3}, {1, 4}, {1, 5}, {1, 6}, {1, 7}, {1, 8}, {1, 9}, {1, 10}, {1, 11}, {1, 12}, {1, 13}, {1, 14}, {1, 15}, {1, 16}, {1, 17}, {1, 18}, {1, 19}, {1, 20}, {1, 21}, {1, 22}, {1, 23}, {1, 24}, {1, 25}, {1, 26}, {1, 27}, {1, 28}, {1, 29}, {1, 30}, {1, 31}, {1, 32}, {1, 33}, {1, 34}, {1, 35}, {1, 36}, {1, 37}, {1, 38}, {1, 39}, {1, 40}, {1, 41}, {1, 42}, {1, 43}, {1, 44}, {1, 45}, {1, 46}, {1, 47}, {1, 48}, {1, 49}, {1, 50}, {1, 51}, {1, 52}, {1, 53}, {1, 54}, {1, 55}, {1, 56}, {1, 57}, {1, 58}, {1, 59}, {1, 60}, {1, 61}, {1, 62}, {1, 63}, {1, 64}, {1, 65}, {1, 66}, {1, 67}, {1, 68}, {1, 69}, {2, 69}, {3, 69}, {4, 69}, {5, 69}, {6, 69}, {7, 69}, {8, 69}, {9, 69}, {10, 69}, {11, 69}, {12, 69}, {13, 69}, {14, 69}, {15, 69}, {16, 69}, {17, 69}, {18, 69}, {19, 69}, {20, 69}, {21, 69}, {22, 69}, {23, 69}, {24, 69}, {25, 69}, {26, 69}, {27, 69}, {28, 69}, {29, 69}, {30, 69}, {31, 69}, {32, 69}, {33, 69}, {34, 69}, {35, 69}, {36, 69}, {37, 69}, {38, 69}, {39, 69}, {40, 69}, {41, 69}, {42, 69}, {43, 69}, {44, 69}, {45, 69}, {46, 69}, {47, 69}, {48, 69}, {49, 69}, {50, 69}, {51, 69}, {52, 69}, {53, 69}, {54, 69}, {55, 69}, {56, 69}, {57, 69}, {58, 69}, {59, 69}, {60, 69}, {61, 69}, {62, 69}, {63, 69}, {64, 69}, {65, 69}, {66, 69}, {67, 69}, {68, 69}, {69, 69}, {69, 70}, {70, 70}]
EDIT 1: Well I thought it would go diagonally from {0,0} to {70,70}. Doesn’t look like the shortest path.
EDIT 2: Anyway it should go horizontally from 0 to 70 and vertically from 0 to 70 thus it looks ok in the end Diagonally it would be the same moves.
EDIT 3: OK, I think I forgot to link some vertices together e.g. {0,10} to {0,11} 
I will fix the code.
0
lkuty
sevenseacat
Author of Ash Framework
No - that really doesn’t work with a lot of vertices in a grid. See: Duplicate vertex ids when adding high number of vertices · Issue #44 · bitwalker/libgraph · GitHub
0
Aetherus
I implemented my own priority queue with no duplicate values and lazy decrease-key operation.
Part 1 I used that priority queue to implement Dijkstra.
Part 2 I used a totally different approach. For each “byte” dropped down, I check if there are byte chunks horizontally, vertically, or diagonally adjacent to that “byte”, and merge those chunks with the new byte to form a larger chunk. Then I just need to find the first chunk over time that horizontally or vertically crosses the whole “memory space”.
Here’s my approach:
3
Aetherus
If you are using libgraph, you can just use Function.identity/1 as the vertex identifier, if each vertex is not that big.
graph = Graph.new(vertex_identifier: &Function.identity/1)
0