bag.py

'''
Our team's solution for Edinburgh Python Dojo (with @davidjamesmoss & @andyhasit)

Based on https://xkcd.com/287/
My Hobby: Embedding NP-Complete problems in restaurant orders

Solved the so called NP-Complete problem using dynamic programming algorithm
(https://en.wikipedia.org/wiki/Dynamic_programming).
'''

from flask import Flask
from flask import request, jsonify

import json

app = Flask(__name__)

with open("menu.json") as f:
    courses = json.load(f)['appetisers']

for c in courses:
    c['price'] = int(c['price'] * 100)

@app.route("/calc/<int:budget>")
def work(budget):
    budget = int(budget)
    # budget = 1505
    bags = [-1 for i in range(budget + 1)]
    bags[0] = []

    for c in courses:
        for w in range(0, budget + 1):
            if w - c['price'] >= 0 and bags[w - c['price']] != -1:
                bags[w] = bags[w - c['price']] + [c]

    return jsonify({'appetisers': bags[budget]})

if __name__ == "__main__":
    app.run(host='0.0.0.0', port=5000)

Dockerfile

FROM ubuntu:14.04

RUN apt-get update && apt-get install -y \
    build-essential \
    python3 \
    python3-pip

RUN pip3 install flask

COPY ./menu.py /menu.py
COPY ./menu.json /menu.json

EXPOSE 5000

# locale settings
RUN locale-gen "en_US.UTF-8"
ENV LC_ALL en_US.UTF-8

CMD python3 /menu.py

menu.json

{
    "appetisers": [
        {
            "item": "Mixed Fruit",
            "price": 2.15
        },
        {
            "item": "French Fries",
            "price": 2.75
        },
        {
            "item": "Side Salad",
            "price": 3.35
        },
        {
            "item": "Hot Wings",
            "price": 3.55
        },
        {
            "item": "Mozzarella Sticks",
            "price": 4.20
        },
        {
            "item": "Sampler Plate",
            "price": 5.80
        }
    ]
}