chicken-wing-prices.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "from decimal import Decimal\n",
    "prices = [(n,Decimal(p)) for n,p in [\n",
    "    (4,'4.55'),\n",
    "    (5,'5.70'),\n",
    "    (6,'6.80'),\n",
    "    (7,'7.95'),\n",
    "    (8,'9.10'),\n",
    "    (9,'10.20'),\n",
    "    (10,'11.35'),\n",
    "    (11,'12.50'),\n",
    "    (12,'13.60'),\n",
    "    (13,'14.75'),\n",
    "    (14,'15.90'),\n",
    "    (15,'17.00'),\n",
    "    (16,'18.15'),\n",
    "    (17,'19.30'),\n",
    "    (18,'20.40'),\n",
    "    (19,'21.55'),\n",
    "    (20,'22.70'),\n",
    "    (21,'23.80'),\n",
    "    (22,'24.95'),\n",
    "    (23,'26.10'),\n",
    "    (24,'27.25'),\n",
    "    (25,'27.80'),\n",
    "    (26,'28.95'),\n",
    "    (27,'30.10'),\n",
    "    (28,'31.20'),\n",
    "    (29,'32.35'),\n",
    "    (30,'33.50'),\n",
    "    (35,'39.15'),\n",
    "    (40,'44.80'),\n",
    "    (45,'50.50'),\n",
    "    (50,'55.60'),\n",
    "    (60,'67.00'),\n",
    "    (70,'78.30'),\n",
    "    (75,'83.45'),\n",
    "    (80,'89.10'),\n",
    "    (90,'100.45'),\n",
    "    (100,'111.25'),\n",
    "    (125,'139.00'),\n",
    "    (150,'166.85'),\n",
    "    (200,'222.50'),\n",
    "]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "from collections import defaultdict\n",
    "cache = {}\n",
    "def make(target):\n",
    "    if target in cache:\n",
    "        return cache[target]\n",
    "    out = defaultdict(lambda:0)\n",
    "    for n,p in prices:\n",
    "        if n==target:\n",
    "            out[p] += 1\n",
    "        elif n<target:\n",
    "            for total,count in make(target-n).items():\n",
    "                out[total+p] += count\n",
    "    cache[target] = out\n",
    "    return out"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "ways = make(100)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "14,942,204,102,374 total ways, 39 different prices\n",
      "111.20: 5\n",
      "111.25: 3\n",
      "111.75: 8,685\n",
      "111.80: 142,106\n",
      "111.85: 218,482\n",
      "111.90: 41,584\n",
      "111.95: 251\n",
      "112.30: 2,306,645\n",
      "112.35: 51,658,919\n",
      "112.40: 210,289,261\n",
      "112.45: 238,884,273\n",
      "112.50: 81,384,672\n",
      "112.55: 6,990,998\n",
      "112.60: 77,381\n",
      "112.80: 486,230\n",
      "112.85: 177,763,308\n",
      "112.90: 4,399,396,182\n",
      "112.95: 27,692,635,767\n",
      "113.00: 62,941,934,292\n",
      "113.05: 59,135,175,362\n",
      "113.10: 23,723,122,092\n",
      "113.15: 3,859,272,687\n",
      "113.20: 215,586,587\n",
      "113.25: 2,740,415\n",
      "113.30: 2,161\n",
      "113.35: 22,863,948\n",
      "113.40: 4,094,412,892\n",
      "113.45: 105,193,605,366\n",
      "113.50: 856,554,356,024\n",
      "113.55: 2,924,569,785,520\n",
      "113.60: 4,775,841,173,315\n",
      "113.65: 3,969,694,775,537\n",
      "113.70: 1,709,598,385,472\n",
      "113.75: 373,504,482,261\n",
      "113.80: 38,710,807,851\n",
      "113.85: 1,657,168,501\n",
      "113.90: 22,120,199\n",
      "113.95: 47,139\n",
      "114.00: 1\n"
     ]
    }
   ],
   "source": [
    "print('{:,} total ways, {:,} different prices'.format(sum(ways.values()),len(ways)))\n",
    "for price,n in sorted(ways.items(),key=lambda x:x[0]):\n",
    "    print('{}: {:,}'.format(price,n))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "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.5.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}