Skip to content

Instantly share code, notes, and snippets.

@JoaoFelipe

JoaoFelipe/Saque.ipynb

Created June 28, 2015 01:25
Show Gist options
  • Save JoaoFelipe/997b454a666b5830b927 to your computer and use it in GitHub Desktop.
Save JoaoFelipe/997b454a666b5830b927 to your computer and use it in GitHub Desktop.
Download ZIP
Display the source blob
Display the rendered blob
Raw
Saque.ipynb
{
"metadata": {
"name": "",
"signature": "sha256:5990f2b7cfbaac61a3f0eefb62ce038bd523bfffca2b2d2d2f01a83ed9f645cf"
},
"nbformat": 3,
"nbformat_minor": 0,
"worksheets": [
{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Inicializa\u00e7\u00e3o"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"from collections import OrderedDict, Counter\n",
"import sys\n",
"\n",
"# Sem cache, valores acima de 40 demoram muito (mais de 5 segundos com tempo exponencial)\n",
"if sys.version_info < (3, 0):\n",
" # Python 2\n",
" # Como estou usando Python 2, precisei implementar meu decorator de cache\n",
" cache = {}\n",
" def lru_cache(*args, **kwargs):\n",
" def dec(fn):\n",
" def f(x):\n",
" if (fn.__name__, x) not in cache:\n",
" cache[(fn.__name__, x)] = fn(x)\n",
" return cache[(fn.__name__, x)]\n",
" return f\n",
" return dec\n",
"else:\n",
" # Python 3\n",
" from functools import lru_cache\n",
"\n",
"notas = OrderedDict([\n",
" (100, 'cem'),\n",
" (50, 'cinquenta'),\n",
" (20, 'vinte'),\n",
" (10, 'dez'),\n",
" (5, 'cinco'),\n",
" (2, 'dois')\n",
"])"
],
"language": "python",
"metadata": {},
"outputs": [],
"prompt_number": 1
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Fun\u00e7\u00e3o comentada"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"def inc(counter, nota):\n",
" \"\"\" Incrementa a quantidade da nota no counter \"\"\"\n",
" counter[nota] += 1\n",
" return counter\n",
"\n",
"@lru_cache(maxsize=None)\n",
"def saque(valor):\n",
" \"\"\" Verifica todas as combina\u00e7\u00f5es de notas para o valor desejado \n",
" e retorna a melhor \"\"\"\n",
" # Caso base: se o valor for 0, retorna nenhuma nota\n",
" if valor == 0: \n",
" return Counter()\n",
" # Encontra todas as possibilidades recursivamente e atribui a p\n",
" # As possibilidades de construir 90 s\u00e3o:\n",
" # => 1 nota de 50 + melhor possibilidade de construir (90-50) = 40\n",
" # => 1 nota de 20 + melhor possibilidade de construir (90-20) = 70\n",
" # => 1 nota de 10 + melhor possibilidade de construir (90-10) = 80\n",
" # => 1 nota de 5 + melhor possibilidade de construir (90-5) = 85\n",
" # => 1 nota de 2 + melhor possibilidade de construir (90-2) = 88\n",
" # A fun\u00e7\u00e3o saque(x) retorna a melor possibilidade de construir x\n",
" # Para cada resultado de saque(valor - nota), eu incremento a solu\u00e7\u00e3o adicionando a nota usada\n",
" # Isso s\u00f3 \u00e9 v\u00e1lido quando valor - nota >= 0. N\u00e3o d\u00e1 pra sacar 90 com uma nota de 100\n",
" # Por isso tem o filtro no final\n",
" p = [inc(saque(valor - nota).copy(), nome)\n",
" for nota, nome in notas.items()\n",
" if valor - nota >= 0]\n",
" # Se houver possibilidades, retorna a possibilidade com o menor n\u00famero de notas\n",
" # Se n\u00e3o houver, retornar uma solu\u00e7\u00e3o com infinitas notas falsas para ser ignorada no resto\n",
" return Counter(i=float('inf')) if not p else min(p, key=lambda x: sum(x.values()))"
],
"language": "python",
"metadata": {},
"outputs": [],
"prompt_number": 2
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Resultado"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"for i in range(151):\n",
" print(i, saque(i))"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"(0, Counter())\n",
"(1, Counter({'i': inf}))\n",
"(2, Counter({'dois': 1}))\n",
"(3, Counter({'i': inf, 'dois': 1}))\n",
"(4, Counter({'dois': 2}))\n",
"(5, Counter({'cinco': 1}))\n",
"(6, Counter({'dois': 3}))\n",
"(7, Counter({'cinco': 1, 'dois': 1}))\n",
"(8, Counter({'dois': 4}))\n",
"(9, Counter({'dois': 2, 'cinco': 1}))\n",
"(10, Counter({'dez': 1}))\n",
"(11, Counter({'dois': 3, 'cinco': 1}))\n",
"(12, Counter({'dez': 1, 'dois': 1}))\n",
"(13, Counter({'dois': 4, 'cinco': 1}))\n",
"(14, Counter({'dois': 2, 'dez': 1}))\n",
"(15, Counter({'cinco': 1, 'dez': 1}))\n",
"(16, Counter({'dois': 3, 'dez': 1}))\n",
"(17, Counter({'cinco': 1, 'dez': 1, 'dois': 1}))\n",
"(18, Counter({'dois': 4, 'dez': 1}))\n",
"(19, Counter({'dois': 2, 'cinco': 1, 'dez': 1}))\n",
"(20, Counter({'vinte': 1}))\n",
"(21, Counter({'dois': 3, 'cinco': 1, 'dez': 1}))\n",
"(22, Counter({'vinte': 1, 'dois': 1}))\n",
"(23, Counter({'dois': 4, 'cinco': 1, 'dez': 1}))\n",
"(24, Counter({'dois': 2, 'vinte': 1}))\n",
"(25, Counter({'cinco': 1, 'vinte': 1}))\n",
"(26, Counter({'dois': 3, 'vinte': 1}))\n",
"(27, Counter({'cinco': 1, 'vinte': 1, 'dois': 1}))\n",
"(28, Counter({'dois': 4, 'vinte': 1}))\n",
"(29, Counter({'dois': 2, 'cinco': 1, 'vinte': 1}))\n",
"(30, Counter({'dez': 1, 'vinte': 1}))\n",
"(31, Counter({'dois': 3, 'cinco': 1, 'vinte': 1}))\n",
"(32, Counter({'dez': 1, 'vinte': 1, 'dois': 1}))\n",
"(33, Counter({'dois': 4, 'cinco': 1, 'vinte': 1}))\n",
"(34, Counter({'dois': 2, 'dez': 1, 'vinte': 1}))\n",
"(35, Counter({'cinco': 1, 'dez': 1, 'vinte': 1}))\n",
"(36, Counter({'dois': 3, 'dez': 1, 'vinte': 1}))\n",
"(37, Counter({'cinco': 1, 'dez': 1, 'vinte': 1, 'dois': 1}))\n",
"(38, Counter({'dois': 4, 'dez': 1, 'vinte': 1}))\n",
"(39, Counter({'dois': 2, 'cinco': 1, 'dez': 1, 'vinte': 1}))\n",
"(40, Counter({'vinte': 2}))\n",
"(41, Counter({'dois': 3, 'cinco': 1, 'dez': 1, 'vinte': 1}))\n",
"(42, Counter({'vinte': 2, 'dois': 1}))\n",
"(43, Counter({'dois': 4, 'cinco': 1, 'dez': 1, 'vinte': 1}))\n",
"(44, Counter({'vinte': 2, 'dois': 2}))\n",
"(45, Counter({'vinte': 2, 'cinco': 1}))\n",
"(46, Counter({'dois': 3, 'vinte': 2}))\n",
"(47, Counter({'vinte': 2, 'cinco': 1, 'dois': 1}))\n",
"(48, Counter({'dois': 4, 'vinte': 2}))\n",
"(49, Counter({'vinte': 2, 'dois': 2, 'cinco': 1}))\n",
"(50, Counter({'cinquenta': 1}))\n",
"(51, Counter({'dois': 3, 'vinte': 2, 'cinco': 1}))\n",
"(52, Counter({'cinquenta': 1, 'dois': 1}))\n",
"(53, Counter({'dois': 4, 'vinte': 2, 'cinco': 1}))\n",
"(54, Counter({'dois': 2, 'cinquenta': 1}))\n",
"(55, Counter({'cinco': 1, 'cinquenta': 1}))\n",
"(56, Counter({'dois': 3, 'cinquenta': 1}))\n",
"(57, Counter({'cinco': 1, 'cinquenta': 1, 'dois': 1}))\n",
"(58, Counter({'dois': 4, 'cinquenta': 1}))\n",
"(59, Counter({'dois': 2, 'cinco': 1, 'cinquenta': 1}))\n",
"(60, Counter({'cinquenta': 1, 'dez': 1}))\n",
"(61, Counter({'dois': 3, 'cinco': 1, 'cinquenta': 1}))\n",
"(62, Counter({'cinquenta': 1, 'dez': 1, 'dois': 1}))\n",
"(63, Counter({'dois': 4, 'cinco': 1, 'cinquenta': 1}))\n",
"(64, Counter({'dois': 2, 'cinquenta': 1, 'dez': 1}))\n",
"(65, Counter({'cinco': 1, 'dez': 1, 'cinquenta': 1}))\n",
"(66, Counter({'dois': 3, 'cinquenta': 1, 'dez': 1}))\n",
"(67, Counter({'cinco': 1, 'dez': 1, 'cinquenta': 1, 'dois': 1}))\n",
"(68, Counter({'dois': 4, 'cinquenta': 1, 'dez': 1}))\n",
"(69, Counter({'dois': 2, 'cinco': 1, 'dez': 1, 'cinquenta': 1}))\n",
"(70, Counter({'cinquenta': 1, 'vinte': 1}))\n",
"(71, Counter({'dois': 3, 'cinco': 1, 'dez': 1, 'cinquenta': 1}))\n",
"(72, Counter({'cinquenta': 1, 'vinte': 1, 'dois': 1}))\n",
"(73, Counter({'dois': 4, 'cinco': 1, 'dez': 1, 'cinquenta': 1}))\n",
"(74, Counter({'dois': 2, 'cinquenta': 1, 'vinte': 1}))\n",
"(75, Counter({'cinco': 1, 'vinte': 1, 'cinquenta': 1}))\n",
"(76, Counter({'dois': 3, 'cinquenta': 1, 'vinte': 1}))\n",
"(77, Counter({'cinco': 1, 'vinte': 1, 'cinquenta': 1, 'dois': 1}))\n",
"(78, Counter({'dois': 4, 'cinquenta': 1, 'vinte': 1}))\n",
"(79, Counter({'dois': 2, 'cinco': 1, 'vinte': 1, 'cinquenta': 1}))\n",
"(80, Counter({'cinquenta': 1, 'dez': 1, 'vinte': 1}))\n",
"(81, Counter({'dois': 3, 'cinco': 1, 'vinte': 1, 'cinquenta': 1}))\n",
"(82, Counter({'cinquenta': 1, 'dez': 1, 'vinte': 1, 'dois': 1}))\n",
"(83, Counter({'dois': 4, 'cinco': 1, 'vinte': 1, 'cinquenta': 1}))\n",
"(84, Counter({'dois': 2, 'cinquenta': 1, 'dez': 1, 'vinte': 1}))\n",
"(85, Counter({'cinco': 1, 'dez': 1, 'vinte': 1, 'cinquenta': 1}))\n",
"(86, Counter({'dois': 3, 'cinquenta': 1, 'dez': 1, 'vinte': 1}))\n",
"(87, Counter({'cinco': 1, 'dez': 1, 'vinte': 1, 'cinquenta': 1, 'dois': 1}))\n",
"(88, Counter({'dois': 4, 'cinquenta': 1, 'dez': 1, 'vinte': 1}))\n",
"(89, Counter({'dois': 2, 'cinco': 1, 'dez': 1, 'vinte': 1, 'cinquenta': 1}))\n",
"(90, Counter({'vinte': 2, 'cinquenta': 1}))\n",
"(91, Counter({'dois': 3, 'cinco': 1, 'dez': 1, 'vinte': 1, 'cinquenta': 1}))\n",
"(92, Counter({'vinte': 2, 'cinquenta': 1, 'dois': 1}))\n",
"(93, Counter({'dois': 4, 'cinco': 1, 'dez': 1, 'vinte': 1, 'cinquenta': 1}))\n",
"(94, Counter({'vinte': 2, 'dois': 2, 'cinquenta': 1}))\n",
"(95, Counter({'vinte': 2, 'cinco': 1, 'cinquenta': 1}))\n",
"(96, Counter({'dois': 3, 'vinte': 2, 'cinquenta': 1}))\n",
"(97, Counter({'vinte': 2, 'cinco': 1, 'cinquenta': 1, 'dois': 1}))\n",
"(98, Counter({'dois': 4, 'vinte': 2, 'cinquenta': 1}))\n",
"(99, Counter({'vinte': 2, 'dois': 2, 'cinco': 1, 'cinquenta': 1}))\n",
"(100, Counter({'cem': 1}))\n",
"(101, Counter({'dois': 3, 'vinte': 2, 'cinco': 1, 'cinquenta': 1}))\n",
"(102, Counter({'cem': 1, 'dois': 1}))\n",
"(103, Counter({'dois': 4, 'vinte': 2, 'cinco': 1, 'cinquenta': 1}))\n",
"(104, Counter({'dois': 2, 'cem': 1}))\n",
"(105, Counter({'cinco': 1, 'cem': 1}))\n",
"(106, Counter({'dois': 3, 'cem': 1}))\n",
"(107, Counter({'cinco': 1, 'cem': 1, 'dois': 1}))\n",
"(108, Counter({'dois': 4, 'cem': 1}))\n",
"(109, Counter({'dois': 2, 'cinco': 1, 'cem': 1}))\n",
"(110, Counter({'dez': 1, 'cem': 1}))\n",
"(111, Counter({'dois': 3, 'cinco': 1, 'cem': 1}))\n",
"(112, Counter({'dez': 1, 'cem': 1, 'dois': 1}))\n",
"(113, Counter({'dois': 4, 'cinco': 1, 'cem': 1}))\n",
"(114, Counter({'dois': 2, 'dez': 1, 'cem': 1}))\n",
"(115, Counter({'cinco': 1, 'dez': 1, 'cem': 1}))\n",
"(116, Counter({'dois': 3, 'dez': 1, 'cem': 1}))\n",
"(117, Counter({'cinco': 1, 'dez': 1, 'cem': 1, 'dois': 1}))\n",
"(118, Counter({'dois': 4, 'dez': 1, 'cem': 1}))\n",
"(119, Counter({'dois': 2, 'cinco': 1, 'dez': 1, 'cem': 1}))\n",
"(120, Counter({'cem': 1, 'vinte': 1}))\n",
"(121, Counter({'dois': 3, 'cinco': 1, 'dez': 1, 'cem': 1}))\n",
"(122, Counter({'cem': 1, 'vinte': 1, 'dois': 1}))\n",
"(123, Counter({'dois': 4, 'cinco': 1, 'dez': 1, 'cem': 1}))\n",
"(124, Counter({'dois': 2, 'cem': 1, 'vinte': 1}))\n",
"(125, Counter({'cinco': 1, 'cem': 1, 'vinte': 1}))\n",
"(126, Counter({'dois': 3, 'cem': 1, 'vinte': 1}))\n",
"(127, Counter({'cinco': 1, 'cem': 1, 'vinte': 1, 'dois': 1}))\n",
"(128, Counter({'dois': 4, 'cem': 1, 'vinte': 1}))\n",
"(129, Counter({'dois': 2, 'cinco': 1, 'cem': 1, 'vinte': 1}))\n",
"(130, Counter({'dez': 1, 'vinte': 1, 'cem': 1}))\n",
"(131, Counter({'dois': 3, 'cinco': 1, 'cem': 1, 'vinte': 1}))\n",
"(132, Counter({'dez': 1, 'vinte': 1, 'cem': 1, 'dois': 1}))\n",
"(133, Counter({'dois': 4, 'cinco': 1, 'cem': 1, 'vinte': 1}))\n",
"(134, Counter({'dois': 2, 'dez': 1, 'vinte': 1, 'cem': 1}))\n",
"(135, Counter({'cinco': 1, 'dez': 1, 'vinte': 1, 'cem': 1}))\n",
"(136, Counter({'dois': 3, 'dez': 1, 'vinte': 1, 'cem': 1}))\n",
"(137, Counter({'cinco': 1, 'dez': 1, 'vinte': 1, 'cem': 1, 'dois': 1}))\n",
"(138, Counter({'dois': 4, 'dez': 1, 'vinte': 1, 'cem': 1}))\n",
"(139, Counter({'dois': 2, 'cinco': 1, 'dez': 1, 'vinte': 1, 'cem': 1}))\n",
"(140, Counter({'vinte': 2, 'cem': 1}))\n",
"(141, Counter({'dois': 3, 'cinco': 1, 'dez': 1, 'vinte': 1, 'cem': 1}))\n",
"(142, Counter({'vinte': 2, 'cem': 1, 'dois': 1}))\n",
"(143, Counter({'dois': 4, 'cinco': 1, 'dez': 1, 'vinte': 1, 'cem': 1}))\n",
"(144, Counter({'vinte': 2, 'dois': 2, 'cem': 1}))\n",
"(145, Counter({'vinte': 2, 'cinco': 1, 'cem': 1}))\n",
"(146, Counter({'dois': 3, 'vinte': 2, 'cem': 1}))\n",
"(147, Counter({'vinte': 2, 'cinco': 1, 'cem': 1, 'dois': 1}))\n",
"(148, Counter({'dois': 4, 'vinte': 2, 'cem': 1}))\n",
"(149, Counter({'vinte': 2, 'dois': 2, 'cinco': 1, 'cem': 1}))\n",
"(150, Counter({'cinquenta': 1, 'cem': 1}))\n"
]
}
],
"prompt_number": 3
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# 5 linhas\n",
"Grandes, mas sem ; nem \\\\. \n",
"\n",
"No m\u00e1ximo uma express\u00e3o por linha"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"add = lambda c, n: (c.update(**{n:1}), c)[-1]\n",
"@lru_cache(max_size=None)\n",
"def saque2(valor):\n",
" p = [inc(saque2(valor - nota).copy(), nome) for nota, nome in notas.items() if valor - nota >= 0]\n",
" return Counter() if valor == 0 else Counter(i=float('inf')) if not p else min(p, key=lambda x: sum(x.values()))"
],
"language": "python",
"metadata": {},
"outputs": [],
"prompt_number": 4
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"all(saque(i) == saque2(i) for i in range(151))"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 5,
"text": [
"True"
]
}
],
"prompt_number": 5
},
{
"cell_type": "code",
"collapsed": false,
"input": [],
"language": "python",
"metadata": {},
"outputs": []
}
],
"metadata": {}
}
]
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment