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": {}
  }
 ]
}