#!/usr/bin/env python2.7
# -*- coding: utf-8 -*-
'''
Assignment 1, Problem 1: Birthday Present

Team Number:
Student Names:
'''

'''
Copyright: Pierre.Flener@it.uu.se and his teaching assistants, 2019.

This file is part of course 1DL231 at Uppsala University, Sweden.

Permission is hereby granted only to the registered students of that
course to use this file, for a homework assignment.

The copyright notice and permission notice above shall be included in
all copies and extensions of this file, and those are not allowed to
appear publicly on the internet, both during a course instance and
forever after.
'''

import unittest
import numpy as np



def birthday_present(P, n, t):
    '''
    Sig:  int[0..n-1], int, int --> Boolean
    Pre:
    Post:
    Ex:   P = [2, 32, 234, 35, 12332, 1, 7, 56]
          birthday_present(P, len(P), 299) = True
          birthday_present(P, len(P), 11) = False
    '''
    # Initialise the dynamic programming matrix, A
    # Type: Boolean[0..n][0..t]
    A = [[None for i in range(t + 1)] for j in range(n + 1)]

    # T = 0 => True
    for i in range(n + 1):
        A[i][0] = True

    # N = 0, T > 0 => False
    for i in range(1,t+1):
        A[0][i] = False

    # Go through matrix
    for i in range(1, n + 1):
        for j in range(1, t + 1):
            # Sum < number => same as previous
            if j < P[i - 1]:
                A[i][j] = A[i - 1][j]
            # Sum >= number => can use it
            if j >= P[i - 1]:
                # Not use number or use number
                A[i][j] = (A[i - 1][j] or A[i - 1][j - P[i - 1]])


    return A[n][t]


def birthday_present_subset(P, n, t):
    '''
    Sig:  int[0..n-1], int, int --> int[0..m]
    Pre:
    Post:
    Ex:   P = [2, 32, 234, 35, 12332, 1, 7, 56]
          birthday_present_subset(P, len(P), 299) = [56, 7, 234, 2]
          birthday_present_subset(P, len(P), 11) = []
    '''
    A = [[None for i in range(t + 1)] for j in range(n + 1)]

    # T = 0 => True
    for i in range(n + 1):
        A[i][0] = True

    # N = 0, T > 0 => False
    for i in range(1,t+1):
        A[0][i] = False

    # Go through matrix
    for i in range(1, n + 1):
        for j in range(1, t + 1):
            # Sum < number => same as previous
            if j < P[i - 1]:
                A[i][j] = A[i - 1][j]
            # Sum >= number => can use it
            if j >= P[i - 1]:
                # Not use number or use number
                A[i][j] = (A[i - 1][j] or A[i - 1][j - P[i - 1]])

    # Go through matrix again but in to get sum
    #for i in xrange(1, n + 1, -1):
     #   for j in xrange(1, t + 1, -1):
      #      if j == True:

    auxboi = n
    auxT = t
    newP = []

    if A[n][t] is False:
        return newP
    else:
        #loop stops when A[0][t] is reached
        while auxboi > -1:
            # if the element is True move "up" on step in the matrix
            if A[auxboi][auxT] == True:
                print "NOT ADD", A[auxboi][auxT], auxboi, auxT
                auxboi = auxboi - 1
            # if the current element in the matrix is False
            # add the value of the element in p[auxboi]
            # subtract the value of p[auxboi] from auxT
            # to jump to the next possible value in the subset
            if A[auxboi][auxT] == False:
                print "ADD", A[auxboi][auxT], auxboi, auxT
                newP.append(P[auxboi])
                print newP
                auxT = auxT - P[auxboi]
                print "auxT is", auxT


    return newP








if __name__ == '__main__':
    P = [2, 32, 234, 35, 12332, 1, 7, 56]
    n = len(P)
    t = 11
    print(birthday_present_subset(P, n, t))