127 lines
3.1 KiB
Plaintext
127 lines
3.1 KiB
Plaintext
{
|
|
"cells": [
|
|
{
|
|
"cell_type": "markdown",
|
|
"id": "68f75185",
|
|
"metadata": {},
|
|
"source": [
|
|
"# [Path Sum: Four Ways](https://projecteuler.net/problem=83)\n",
|
|
"\n",
|
|
"This is the same matrix as [problem 81](https://projecteuler.net/problem=81) and [problem 82](https://projecteuler.net/problem=82)."
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "code",
|
|
"execution_count": 1,
|
|
"id": "95e759ee",
|
|
"metadata": {},
|
|
"outputs": [],
|
|
"source": [
|
|
"with open(\"txt/0083_matrix.txt\") as f:\n",
|
|
" mat = matrix((int(n) for n in line.split(',')) for line in f)"
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "markdown",
|
|
"id": "7c263e59",
|
|
"metadata": {},
|
|
"source": [
|
|
"Once again, we can reuse our solution from problem 81, simply modifying so that when adding entries to the queue, we'll add all entries above, below, left, and right of our current entry."
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "code",
|
|
"execution_count": 2,
|
|
"id": "f261a6ff",
|
|
"metadata": {},
|
|
"outputs": [],
|
|
"source": [
|
|
"import heapq\n",
|
|
"\n",
|
|
"def minimal_path_sum(mat):\n",
|
|
" m, n = mat.dimensions()\n",
|
|
" \n",
|
|
" visited = set()\n",
|
|
" queue = [(0, (0, 0))]\n",
|
|
" while queue != []:\n",
|
|
" cost, (i, j) = heapq.heappop(queue)\n",
|
|
" \n",
|
|
" if (i, j) in visited:\n",
|
|
" continue\n",
|
|
" visited.add((i, j))\n",
|
|
" \n",
|
|
" cost += mat[i, j]\n",
|
|
" \n",
|
|
" if (i, j) == (m - 1, n - 1):\n",
|
|
" break\n",
|
|
" \n",
|
|
" if i - 1 >= 0:\n",
|
|
" heapq.heappush(queue, (cost, (i - 1, j)))\n",
|
|
" \n",
|
|
" if j - 1 >= 0:\n",
|
|
" heapq.heappush(queue, (cost, (i, j - 1)))\n",
|
|
" \n",
|
|
" if i + 1 < m:\n",
|
|
" heapq.heappush(queue, (cost, (i + 1, j)))\n",
|
|
" \n",
|
|
" if j + 1 < n:\n",
|
|
" heapq.heappush(queue, (cost, (i, j + 1)))\n",
|
|
" \n",
|
|
" return cost"
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "code",
|
|
"execution_count": 3,
|
|
"id": "e04dd640",
|
|
"metadata": {},
|
|
"outputs": [
|
|
{
|
|
"data": {
|
|
"text/plain": [
|
|
"425185"
|
|
]
|
|
},
|
|
"execution_count": 3,
|
|
"metadata": {},
|
|
"output_type": "execute_result"
|
|
}
|
|
],
|
|
"source": [
|
|
"minimal_path_sum(mat)"
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "markdown",
|
|
"id": "f1685769",
|
|
"metadata": {},
|
|
"source": [
|
|
"#### Copyright (C) 2025 filifa\n",
|
|
"\n",
|
|
"This work is licensed under the [Creative Commons Attribution-ShareAlike 4.0 International license](https://creativecommons.org/licenses/by-sa/4.0/) and the [BSD Zero Clause license](https://spdx.org/licenses/0BSD.html)."
|
|
]
|
|
}
|
|
],
|
|
"metadata": {
|
|
"kernelspec": {
|
|
"display_name": "SageMath 9.5",
|
|
"language": "sage",
|
|
"name": "sagemath"
|
|
},
|
|
"language_info": {
|
|
"codemirror_mode": {
|
|
"name": "ipython",
|
|
"version": 3
|
|
},
|
|
"file_extension": ".py",
|
|
"mimetype": "text/x-python",
|
|
"name": "python",
|
|
"nbconvert_exporter": "python",
|
|
"pygments_lexer": "ipython3",
|
|
"version": "3.11.2"
|
|
}
|
|
},
|
|
"nbformat": 4,
|
|
"nbformat_minor": 5
|
|
}
|