Skip to content

Instantly share code, notes, and snippets.

@fuzzy-focus

fuzzy-focus/well_well_well.ipynb

Created March 6, 2018 12:41
Show Gist options
  • Save fuzzy-focus/0e8226caae0e7b3e859e9a7579f245a9 to your computer and use it in GitHub Desktop.
Save fuzzy-focus/0e8226caae0e7b3e859e9a7579f245a9 to your computer and use it in GitHub Desktop.
Download ZIP
Well Well Well - Daily Challenge
Display the source blob
Display the rendered blob
Raw
well_well_well.ipynb
{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# [Well Well Well](https://www.reddit.com/r/dailyprogrammer/comments/7zriir/20180223_challenge_352_hard_well_well_well/)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Inputs:\n",
"```\n",
"3 3\n",
"1 9 6\n",
"2 8 5\n",
"3 7 4\n",
"4\n",
"```\n",
"\n",
"```\n",
"7 7\n",
" 38 33 11 48 19 45 22\n",
" 47 30 24 15 46 28 3\n",
" 14 13 2 34 8 21 17\n",
" 10 9 5 16 27 36 39\n",
" 18 32 20 1 35 49 12\n",
" 43 29 4 41 26 31 37\n",
" 25 6 23 44 7 42 40\n",
"35\n",
"```\n",
"\n",
"```\n",
"7 7\n",
" 15 16 46 1 38 43 44\n",
" 25 10 7 6 34 42 14\n",
" 8 19 9 21 13 23 22\n",
" 32 11 29 36 3 5 47\n",
" 31 33 45 24 12 18 28\n",
" 40 41 20 26 39 48 2\n",
" 49 35 27 4 37 30 17\n",
"26\n",
"```\n",
"\n",
"First row is dimensions of the \"well\".\n",
"Then a heightmap of the well follows.\n",
"\n",
"Find the time when one cubic unit of water is on the square specified by the last input number.\n",
"\n",
"Water flows in with 1 cubic unit per time unit on square 1.\n",
"\n",
"First input here is a test input, the answer for that is 16."
]
},
{
"cell_type": "code",
"execution_count": 109,
"metadata": {},
"outputs": [],
"source": [
"import re\n",
"import itertools\n",
"\n",
"def ints(text):\n",
" return list(map(int,re.findall(r'\\b\\d+\\b', text)))\n",
"\n",
"def parse_input(text):\n",
" m, n, *well, target = ints(text)\n",
" well = [well[i*m:(i+1)*m] for i in range(n)]\n",
" return well, target\n",
"\n",
"INPUTS = ['''3 3\n",
"1 9 6\n",
"2 8 5\n",
"3 7 4\n",
"4''',\n",
" '''7 7\n",
" 38 33 11 48 19 45 22\n",
" 47 30 24 15 46 28 3\n",
" 14 13 2 34 8 21 17\n",
" 10 9 5 16 27 36 39\n",
" 18 32 20 1 35 49 12\n",
" 43 29 4 41 26 31 37\n",
" 25 6 23 44 7 42 40\n",
"35''',\n",
" '''7 7\n",
" 15 16 46 1 38 43 44\n",
" 25 10 7 6 34 42 14\n",
" 8 19 9 21 13 23 22\n",
" 32 11 29 36 3 5 47\n",
" 31 33 45 24 12 18 28\n",
" 40 41 20 26 39 48 2\n",
" 49 35 27 4 37 30 17\n",
"26''',\n",
" '''7 7\n",
" 3 50 50 50 50 50 50\n",
" 2 3 50 50 50 50 30\n",
" 2 3 4 50 3 30 30\n",
" 1 3 4 30 3 30 6\n",
" 2 3 50 50 3 30 3\n",
" 3 3 50 50 50 50 2\n",
" 4 50 50 50 50 50 50\n",
"6''',]"
]
},
{
"cell_type": "code",
"execution_count": 110,
"metadata": {},
"outputs": [],
"source": [
"def n4(point): \n",
" \"The four neighbors (without diagonals).\"\n",
" return tuple(point + step for step in [-1, +1, -1j, +1j])\n",
"\n",
"def fill(well, target, start=1):\n",
" def fill_rec(sqrs, t, s):\n",
" sqrs = dict(sqrs.items())\n",
" filled = set([s])\n",
" level = sqrs[s]\n",
" while True:\n",
" level += 1\n",
" for s in filled:\n",
" sqrs[s] = level\n",
" if t in filled:\n",
" return sqrs\n",
" while True:\n",
" bnd = set(pos for pos in itertools.chain.from_iterable(map(n4,filled)) \n",
" if pos in sqrs and pos not in filled and sqrs[pos] <= level)\n",
" if bnd:\n",
" if any(sqrs[s] < level for s in bnd):\n",
" low = min(bnd, key=lambda s: sqrs[s])\n",
" return fill_rec(sqrs, t, low)\n",
" filled |= bnd\n",
" else:\n",
" break\n",
" sqrs = {i+j*1j:val for j, row in enumerate(well) for i,val in enumerate(row)}\n",
" for pos, height in sqrs.items():\n",
" if height == start: \n",
" s = pos\n",
" elif height == target:\n",
" t = pos\n",
" return sqrs, fill_rec(sqrs, t, s)\n",
"\n",
"def print_well(well_dict):\n",
" w = max(int(x.real) for x in well_dict)\n",
" h = max(int(x.imag) for x in well_dict)\n",
" well = [[0 for _ in range(w+1)] for _ in range(h+1)]\n",
" for pos, val in well_dict.items():\n",
" well[int(pos.imag)][int(pos.real)] = val\n",
" print('\\n'.join(' '.join('{: >2}'.format(sq) for sq in row) for row in well))\n",
" "
]
},
{
"cell_type": "code",
"execution_count": 111,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"########################################\n",
"Result for this input:\n",
"\n",
" 1 9 6\n",
" 2 8 5\n",
" 3 7 4\n",
"water height after filling:\n",
" 7 0 0\n",
" 7 0 0\n",
" 7 0 5\n",
"\n",
"takes 16 s to get 1cu of water on 4\n",
"########################################\n",
"Result for this input:\n",
"\n",
"38 33 11 48 19 45 22\n",
"47 30 24 15 46 28 3\n",
"14 13 2 34 8 21 17\n",
"10 9 5 16 27 36 39\n",
"18 32 20 1 35 49 12\n",
"43 29 4 41 26 31 37\n",
"25 6 23 44 7 42 40\n",
"water height after filling:\n",
" 0 36 36 0 0 0 36\n",
" 0 36 36 36 0 36 36\n",
"36 36 36 36 36 36 36\n",
"36 36 36 36 36 0 0\n",
"36 36 36 36 36 0 0\n",
" 0 36 36 0 36 36 0\n",
"36 36 36 0 36 0 0\n",
"\n",
"takes 589 s to get 1cu of water on 35\n",
"########################################\n",
"Result for this input:\n",
"\n",
"15 16 46 1 38 43 44\n",
"25 10 7 6 34 42 14\n",
" 8 19 9 21 13 23 22\n",
"32 11 29 36 3 5 47\n",
"31 33 45 24 12 18 28\n",
"40 41 20 26 39 48 2\n",
"49 35 27 4 37 30 17\n",
"water height after filling:\n",
"27 27 0 27 0 0 0\n",
"27 27 27 27 0 0 27\n",
"27 27 27 27 27 27 27\n",
" 0 27 0 0 27 27 0\n",
" 0 0 0 27 27 27 0\n",
" 0 0 27 27 0 0 0\n",
" 0 0 0 27 0 0 0\n",
"\n",
"takes 316 s to get 1cu of water on 26\n",
"########################################\n",
"Result for this input:\n",
"\n",
" 3 50 50 50 50 50 50\n",
" 2 3 50 50 50 50 30\n",
" 2 3 4 50 3 30 30\n",
" 1 3 4 30 3 30 6\n",
" 2 3 50 50 3 30 3\n",
" 3 3 50 50 50 50 2\n",
" 4 50 50 50 50 50 50\n",
"water height after filling:\n",
"30 0 0 0 0 0 0\n",
"30 30 0 0 0 0 0\n",
"30 30 30 0 30 0 0\n",
"30 30 30 0 30 0 7\n",
"30 30 0 0 30 0 7\n",
"30 30 0 0 0 0 7\n",
"30 0 0 0 0 0 0\n",
"\n",
"takes 471 s to get 1cu of water on 6\n"
]
}
],
"source": [
"for inp in INPUTS:\n",
" c, t = parse_input(inp)\n",
" a, b = fill(c, t)\n",
" diff = {pos: b[pos] - a[pos] for pos in a}\n",
" vis = {pos: b[pos] if b[pos] != a[pos] else 0 for pos in a}\n",
" print('#'*40)\n",
" print('Result for this input:\\n')\n",
" print_well(a)\n",
" print('water height after filling:')\n",
" print_well(vis)\n",
" print('\\ntakes', sum(b[pos] - a[pos] for pos in a), 's to get 1cu of water on', t)\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": []
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3",
"language": "python",
"name": "python3"
},
"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.6.3"
}
},
"nbformat": 4,
"nbformat_minor": 2
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment