8000 2022: Add day 12. · HoffmannChristian/adventofcode@165682a · GitHub
[go: up one dir, main page]
Skip to content

Commit 165682a

Browse files
HoffmannChristianHoffmannChristian
committed
2022: Add day 12.
1 parent 3218fc9 commit 165682a

File tree

1 file changed

+130
-1
lines changed

1 file changed

+130
-1
lines changed

‎2022/advent_of_code_2022.ipynb

Lines changed: 130 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -806,6 +806,135 @@
806806
"\n",
807807
"get_level_of_monkey_business(monkeys, 10_000)"
808808
]
809+
},
810+
{
811+
"attachments": {},
812+
"cell_type": "markdown",
813+
"metadata": {},
814+
"source": [
815+
"## Day 12: Hill Climbing Algorithm\n",
816+
"\n",
817+
"What is the fewest steps required to move from your current position to the location that should get the best signal?"
818+
]
819+
},
820+
{
821+
"cell_type": "code",
822+
"execution_count": null,
823+
"metadata": {},
824+
"outputs": [],
825+
"source": [
826+
"from sys import maxsize\n",
827+
"\n",
828+
"def argmin(dict):\n",
829+
" return min(dict, key=dict.get)\n",
830+
"\n",
831+
"def get_position(lines, marker):\n",
832+
" return get_positions(lines, marker)[0]\n",
833+
"\n",
834+
"def get_positions(lines, marker):\n",
835+
" positions = []\n",
836+
" for row_idx,line in enumerate(lines):\n",
837+
" for col_idx,char in enumerate(line):\n",
838+
" if char == marker:\n",
839+
" positions.append((row_idx, col_idx))\n",
840+
" return positions\n",
841+
"\n",
842+
"def get_height_matrix(lines, start_pos, end_pos):\n",
843+
" height_matrix = [[ord(elevation) for elevation in line] for line in lines]\n",
844+
" height_matrix[start_pos[0]][start_pos[1]] = ord('a')\n",
845+
" height_matrix[end_pos[0]][end_pos[1]] = ord('z')\n",
846+
" return height_matrix\n",
847+
"\n",
848+
"def get_all_pos(heigh_matrix):\n",
849+
" return [(x, y) for x in range(len(height_matrix)) for y in range(len(height_matrix[0]))]\n",
850+
"\n",
851+
"def get_neighbours(pos, height_matrix):\n",
852+
" x, y = pos\n",
853+
" neighbours = []\n",
854+
" if x > 0:\n",
855+
" neighbours.append((x-1, y))\n",
856+
" if x < len(height_matrix)-1:\n",
857+
" neighbours.append((x+1, y))\n",
858+
" if y > 0:\n",
859+
" neighbours.append((x, y-1))\n",
860+
" if y < len(height_matrix[0])-1:\n",
861+
" neighbours.append((x, y+1))\n",
862+
" return neighbours\n",
863+
"\n",
864+
"def is_elevation_passable(current_pos, neighbour_pos):\n",
865+
" current_height = height_matrix[current_pos[0]][current_pos[1]]\n",
866+
" neighbour_height = height_matrix[neighbour_pos[0]][neighbour_pos[1]]\n",
867+
" return neighbour_height <= current_height + 1\n",
868+
"\n",
869+
"def get_shortest_path(height_matrix, start_pos, end_pos):\n",
870+
" dist, prev, unvisited = {}, {}, set()\n",
871+
" for pos in get_all_pos(height_matrix):\n",
872+
" dist[pos] = maxsize\n",
873+
" prev[pos] = None\n",
874+
" unvisited.add(pos)\n",
875+
" dist[start_pos] = 0\n",
876+
"\n",
877+
" while len(unvisited):\n",
878+
" current = argmin({ pos: dist[pos] for pos in unvisited })\n",
879+
" if current == end_pos:\n",
880+
" break\n",
881+
" unvisited.remove(current)\n",
882+
"\n",
883+
" neighbours = get_neighbours(current, height_matrix)\n",
884+
" for neighbour in unvisited.intersection(neighbours):\n",
885+
" if not is_elevation_passable(current, neighbour):\n",
886+
" continue\n",
887+
" alternative_dist = dist[current] + 1\n",
888+
" if alternative_dist < dist[neighbour]:\n",
889+
" dist[neighbour] = alternative_dist\n",
890+
" prev[neighbour] = current\n",
891+
"\n",
892+
" if(prev[end_pos] == None):\n",
893+
" return None\n",
894+
" shortest_path = []\n",
895+
" pos = end_pos\n",
896+
" while pos != None:\n",
897+
" shortest_path.insert(0, pos)\n",
898+
" pos = prev[pos]\n",
899+
" return shortest_path\n",
900+
"\n",
901+
"lines = open('12_input.txt', 'r').readlines()\n",
902+
"lines = [line.strip() for line in lines]\n",
903+
"\n",
904+
"start_pos = get_position(lines, 'S')\n",
905+
"end_pos = get_position(lines, 'E')\n",
906+
"height_matrix = get_height_matrix(lines, start_pos, end_pos)\n",
907+
"shortest_path = get_shortest_path(height_matrix, start_pos, end_pos)\n",
908+
"len(shortest_path)-1"
909+
]
910+
},
911+
{
912+
"attachments": {},
913+
"cell_type": "markdown",
914+
"metadata": {},
915+
"source": [
916+
"What is the fewest steps required to move starting from any square with elevation `a` to the location that should get the best signal?"
917+
]
918+
},
919+
{
920+
"cell_type": "code",
921+
"execution_count": null,
922+
"metadata": {},
923+
"outputs": [],
924+
"source": [
925+
"for i,line in enumerate(lines):\n",
926+
" lines[i] = line.replace('S', 'a')\n",
927+
"\n",
928+
"end_pos = get_position(lines, 'E')\n",
929+
"\n",
930+
"num_steps = maxsize\n",
931+
"for start_pos in get_positions(lines, 'a'):\n",
932+
" height_matrix = get_height_matrix(lines, start_pos, end_pos)\n",
933+
" shortest_path = get_shortest_path(height_matrix, start_pos, end_pos)\n",
934+
" if shortest_path and len(shortest_path)-1 < num_steps:\n",
935+
" num_steps = len(shortest_path)-1\n",
936+
"num_steps"
937+
]
809938
}
810939
],
811940
"metadata": {
@@ -824,7 +953,7 @@
824953
"name": "python",
825954
"nbconvert_exporter": "python",
826955
"pygments_lexer": "ipython3",
827-
"version": "3.10.8"
956+
"version": "3.10.8 | packaged by conda-forge | (main, Nov 24 2022, 14:07:00) [MSC v.1916 64 bit (AMD64)]"
828957
},
829958
"vscode": {
830959
"interpreter": {

0 commit comments

Comments
 (0)
0