stau.space
My omnium-gatherom of scripts and source code.
1{
2 "cells": [
3 {
4 "cell_type": "code",
5 "execution_count": 2,
6 "id": "ee0b670d-30e5-49df-891f-d7cb7c7d8216",
7 "metadata": {},
8 "outputs": [],
9 "source": [
10 "def max_heapify(lst: list) -> list:\n",
11 " print(\"hola\")"
12 ]
13 },
14 {
15 "cell_type": "code",
16 "execution_count": 8,
17 "id": "4ef52abf-c4c8-473d-ae00-615248010c86",
18 "metadata": {},
19 "outputs": [],
20 "source": [
21 "# void copias::BubbleSort() {\n",
22 "# //este ciclo va desde la primera posicion hasta la penúltima\n",
23 "# //en cada iteracion se asegura que hay un elemento en la posicion correcta (el mas pequeño)\n",
24 "# for (int i = 0; i < size - 1; i++) {\n",
25 "# //empieza desde el penultimo elemento\n",
26 "# for (int j = size - 1; j > i; j--) {\n",
27 "# if (arregloC[j] < arregloC[j - 1]) {\n",
28 "# this->swap(j, j - 1); //se intercambian los elementos \n",
29 "# }\n",
30 "# }\n",
31 "# }\n",
32 "# return;\n",
33 "# }\n",
34 "def BubbleSort(arr: list[int]) -> list[int]:\n",
35 " def swap(i: int, j: int) -> list[int]:\n",
36 " arr[i], arr[j] = arr[j], arr[i]\n",
37 "\n",
38 " for i in range(len(arr) - 1):\n",
39 " for j in range(size - 1, i):\n",
40 " if arr[j] < arr[j - 1]:\n",
41 " swap(j, j - 1)\n",
42 " return arr"
43 ]
44 },
45 {
46 "cell_type": "code",
47 "execution_count": 9,
48 "id": "fd7cac2f-f8ed-40ed-8d8f-a82cb13f203a",
49 "metadata": {},
50 "outputs": [],
51 "source": [
52 "# void copias::MergeSort(int p, int r){\n",
53 "# //caso base\n",
54 "# if(p >= r){\n",
55 "# return;\n",
56 "# }\n",
57 "# //se calcula q como el midpoint (piso)\n",
58 "# int q = (p + r) / 2;\n",
59 "# //recursion con el arreglo \"izquierdo\"\n",
60 "# MergeSort(p, q);\n",
61 "# //recursion con el arreglo \"derecho\"\n",
62 "# MergeSort(q + 1, r);\n",
63 "# //union de todo bajo las llamadas recursivas\n",
64 "# Merge(p, q, r);\n",
65 "\n",
66 "# return;\n",
67 "# }\n",
68 "\n",
69 "def MergeSort(arr: list[int], p = 0, r = None) -> list[int]:\n",
70 " if r == None:\n",
71 " r = len(arr) - 1\n",
72 " if p >= r:\n",
73 " return arr\n",
74 "\n",
75 " q = (p + r) // 2\n",
76 " arr = MergeSort(arr, p, q)\n",
77 " arr = MergeSort(arr, q + 1, r)\n",
78 " arr = Merge(arr, p, q, r)\n",
79 "\n",
80 " return arr"
81 ]
82 },
83 {
84 "cell_type": "code",
85 "execution_count": 6,
86 "id": "abefcc33-6e81-49e7-9134-b71115f4d029",
87 "metadata": {},
88 "outputs": [],
89 "source": [
90 "# void copias::Merge(int p, int q, int r){\n",
91 "# int qty1 = q - p + 1; //cantidad de elementos del arreglo izquierdo\n",
92 "# int qty2 = r - q; //cantidad de elementos del arreglo derecho\n",
93 "# int L[qty1], R[qty2]; //declaración del arreglo izquierdo y derecho\n",
94 "\n",
95 "# //se copian los datos del arreglo a los subarreglos\n",
96 "# for(int i = 0; i < qty1; i++){\n",
97 "# L[i] = arregloC[p + i];\n",
98 "# }\n",
99 "\n",
100 "# for(int j = 0; j < qty2; j++){\n",
101 "# R[j] = arregloC[q + 1 + j];\n",
102 "# }\n",
103 "\n",
104 "# int i = 0;\n",
105 "# int j = 0;\n",
106 "# int k = p;\n",
107 "# //este ciclo sucede siempre que no se hayan evaluado todos los elementos\n",
108 "# //de alguno de los subarreglos\n",
109 "# while(i < qty1 && j < qty2){\n",
110 "\n",
111 "# //se va verificando cual de los \"tops\" de ambos arreglos es el menor, ese se va asignando al indice k\n",
112 "# if( L[i] <= R[j] ){\n",
113 "# arregloC[k] = L[i];\n",
114 "# i++;\n",
115 "# }\n",
116 "\n",
117 "# else{\n",
118 "# arregloC[k] = R[j];\n",
119 "# j++;\n",
120 "# }\n",
121 "# k++;\n",
122 "# }\n",
123 "\n",
124 "# //estos ciclos suceden para meter al arreglo los elementos del subarreglo que faltaron por evaluar\n",
125 "# //porque eran mas grandes que todos los elementos del otro subarreglo\n",
126 "# while(i < qty1){\n",
127 "# arregloC[k] = L[i];\n",
128 "# i++;\n",
129 "# k++;\n",
130 "# }\n",
131 "\n",
132 "# while(j < qty2){\n",
133 "# arregloC[k] = R[j];\n",
134 "# j++;\n",
135 "# k++;\n",
136 "# }\n",
137 "# return;\n",
138 "# }\n",
139 "def Merge(arr: list[int], p: int, q: int, r: int) -> list[int]:\n",
140 " qty1 = q - p + 1\n",
141 " qty2 = r - q\n",
142 " l = arr[0:qty1]\n",
143 " r = arr[0:qty2]\n",
144 "\n",
145 " i = 0\n",
146 " j = 0\n",
147 " k = p\n",
148 " while i < qty1 and j < qty2:\n",
149 " if l[i] < r[j]:\n",
150 " arr[k] = l[i]\n",
151 " i += 1\n",
152 " else:\n",
153 " arr[k] = r[j]\n",
154 " j += 1\n",
155 " k += 1\n",
156 "\n",
157 " while i < qty1:\n",
158 " arr[k] = l[i]\n",
159 " i += 1\n",
160 " k += 1\n",
161 " while k < qty2:\n",
162 " arr[k] = r[j]\n",
163 " j += 1\n",
164 " k += 1\n",
165 " return arr"
166 ]
167 },
168 {
169 "cell_type": "code",
170 "execution_count": 16,
171 "id": "595d00e7-7d5e-4645-a41e-1560c431e81a",
172 "metadata": {},
173 "outputs": [],
174 "source": [
175 "def BubbleMergeSort(arr: list[int]) -> list[int]:\n",
176 " def BubbleSort(lst: list[int]) -> list[int]:\n",
177 " def swap(i: int, j: int) -> list[int]:\n",
178 " lst[i], lst[j] = lst[j], lst[i]\n",
179 " \n",
180 " for i in range(len(lst) - 1):\n",
181 " for j in range(size - 1, i):\n",
182 " if lst[j] < lst[j - 1]:\n",
183 " swap(j, j - 1)\n",
184 " return lst\n",
185 "\n",
186 " def MergeSort(lst: list[int], p = 0, r = None) -> list[int]:\n",
187 " if r == None:\n",
188 " r = len(lst) - 1\n",
189 " if p >= r:\n",
190 " return lst\n",
191 " if len(lst) <= 143:\n",
192 " return BubbleSort(lst)\n",
193 " \n",
194 " q = (p + r) // 2\n",
195 " lst = MergeSort(lst, p, q)\n",
196 " lst = MergeSort(lst, q + 1, r)\n",
197 " lst = Merge(lst, p, q, r)\n",
198 " \n",
199 " return arr\n",
200 "\n",
201 " if len(arr) <= 143:\n",
202 " return BubbleSort(arr)\n",
203 " else:\n",
204 " return MergeSort(arr)"
205 ]
206 },
207 {
208 "cell_type": "code",
209 "execution_count": 55,
210 "id": "f2c30cc6-0c7d-496f-b940-f047db86e90d",
211 "metadata": {},
212 "outputs": [],
213 "source": [
214 "def DC_POSITIVE_PROD(A: list[int], f = 0, l = None) -> tuple[int, int]:\n",
215 " if l == None:\n",
216 " l = len(A)\n",
217 " if l - f == 1:\n",
218 " if A[f] <= 0:\n",
219 " return 0, 1\n",
220 " else:\n",
221 " return 1, A[f]\n",
222 "\n",
223 " n = len(A)\n",
224 " m = (f + l) // 2\n",
225 " x, left = DC_POSITIVE_PROD(A, f, m)\n",
226 " y, right = DC_POSITIVE_PROD(A, m, l)\n",
227 " return x + y, left * right"
228 ]
229 },
230 {
231 "cell_type": "code",
232 "execution_count": 56,
233 "id": "f4701e84-2f6a-4f77-8987-10fcf64a7b47",
234 "metadata": {},
235 "outputs": [
236 {
237 "data": {
238 "text/plain": [
239 "(3, 42)"
240 ]
241 },
242 "execution_count": 56,
243 "metadata": {},
244 "output_type": "execute_result"
245 }
246 ],
247 "source": [
248 "DC_POSITIVE_PROD(lst)"
249 ]
250 },
251 {
252 "cell_type": "code",
253 "execution_count": 54,
254 "id": "3b52dfb5-7f87-48f2-a58e-7a671af08477",
255 "metadata": {},
256 "outputs": [
257 {
258 "ename": "SyntaxError",
259 "evalue": "invalid syntax (1079348763.py, line 1)",
260 "output_type": "error",
261 "traceback": [
262 "\u001b[0;36m Cell \u001b[0;32mIn[54], line 1\u001b[0;36m\u001b[0m\n\u001b[0;31m if x := 0 else elif break;core\u001b[0m\n\u001b[0m ^\u001b[0m\n\u001b[0;31mSyntaxError\u001b[0m\u001b[0;31m:\u001b[0m invalid syntax\n"
263 ]
264 }
265 ],
266 "source": [
267 "if x := 0 else elif break;core"
268 ]
269 },
270 {
271 "cell_type": "code",
272 "execution_count": 50,
273 "id": "1a591d37-fdf5-4058-b680-ace7f34c526f",
274 "metadata": {},
275 "outputs": [],
276 "source": [
277 "lst = [2, 0, -1, 7, -9, 0, 3, -20]"
278 ]
279 },
280 {
281 "cell_type": "code",
282 "execution_count": 26,
283 "id": "95f7f682-f7ea-4cf2-a792-7523763ccc10",
284 "metadata": {},
285 "outputs": [],
286 "source": [
287 "memo = {}\n",
288 "def coin_change(amount, coins):\n",
289 " if amount == 0:\n",
290 " return 0\n",
291 " elif amount < 0:\n",
292 " return -1\n",
293 " elif amount not in memo:\n",
294 " amounts = filter(lambda x: x >= 0, [coin_change(amount - coin, coins) for coin in coins])\n",
295 " memo[amount] = min(amounts) + 1\n",
296 " return memo[amount]\n",
297 " else:\n",
298 " return memo[amount]"
299 ]
300 },
301 {
302 "cell_type": "code",
303 "execution_count": 30,
304 "id": "519b39fe-43aa-4711-8de2-e0a61f26a362",
305 "metadata": {},
306 "outputs": [
307 {
308 "name": "stdout",
309 "output_type": "stream",
310 "text": [
311 "1 1\n",
312 "2 2\n",
313 "3 1\n",
314 "4 2\n",
315 "5 3\n",
316 "6 2\n",
317 "7 1\n",
318 "8 2\n",
319 "9 3\n",
320 "10 2\n",
321 "11 3\n",
322 "12 4\n",
323 "13 3\n",
324 "14 2\n",
325 "15 3\n",
326 "16 4\n",
327 "17 3\n",
328 "18 4\n",
329 "19 5\n",
330 "20 4\n",
331 "21 3\n",
332 "22 4\n",
333 "23 5\n",
334 "24 4\n",
335 "25 5\n",
336 "26 6\n",
337 "27 5\n",
338 "28 4\n",
339 "29 5\n",
340 "30 6\n",
341 "31 5\n",
342 "32 6\n",
343 "33 7\n",
344 "34 6\n",
345 "35 5\n",
346 "36 6\n",
347 "37 7\n",
348 "38 6\n",
349 "39 7\n",
350 "40 8\n",
351 "41 7\n",
352 "42 6\n",
353 "43 7\n",
354 "44 8\n",
355 "45 7\n",
356 "46 8\n",
357 "47 9\n",
358 "48 8\n",
359 "49 7\n",
360 "50 8\n",
361 "51 9\n",
362 "52 8\n",
363 "53 9\n",
364 "54 10\n",
365 "55 9\n",
366 "56 8\n",
367 "57 9\n",
368 "58 10\n",
369 "59 9\n",
370 "60 10\n",
371 "61 11\n",
372 "62 10\n",
373 "63 9\n",
374 "64 10\n",
375 "65 11\n",
376 "66 10\n",
377 "67 11\n",
378 "68 12\n",
379 "69 11\n",
380 "70 10\n",
381 "71 11\n",
382 "72 12\n",
383 "73 11\n",
384 "74 12\n",
385 "75 13\n",
386 "76 12\n",
387 "77 11\n"
388 ]
389 }
390 ],
391 "source": [
392 "for x in range(1,78):\n",
393 " print(x, coin_change(x, [7, 1, 3]))"
394 ]
395 },
396 {
397 "cell_type": "code",
398 "execution_count": null,
399 "id": "73bae520-31fb-4c05-bb30-5fc92fc1ea70",
400 "metadata": {},
401 "outputs": [],
402 "source": []
403 }
404 ],
405 "metadata": {
406 "kernelspec": {
407 "display_name": "Python 3 (ipykernel)",
408 "language": "python",
409 "name": "python3"
410 },
411 "language_info": {
412 "codemirror_mode": {
413 "name": "ipython",
414 "version": 3
415 },
416 "file_extension": ".py",
417 "mimetype": "text/x-python",
418 "name": "python",
419 "nbconvert_exporter": "python",
420 "pygments_lexer": "ipython3",
421 "version": "3.12.3"
422 }
423 },
424 "nbformat": 4,
425 "nbformat_minor": 5
426}