From marius.masson@insa-rouen.fr  Sun Apr  1 09:13:57 2018
Return-Path: <marius.masson@insa-rouen.fr>
Received: from mx.cims.nyu.edu (mx.cims.nyu.edu [128.122.49.99])
	by mail.cims.nyu.edu (8.15.1+Sun/8.15.1) with ESMTPS id w31DDuWP008713
	(version=TLSv1.2 cipher=DHE-RSA-AES128-GCM-SHA256 bits=128 verify=NOT)
	for <shasha@mail.cims.nyu.edu>; Sun, 1 Apr 2018 09:13:57 -0400 (EDT)
Received: from smtpout.insa-rouen.fr (smtpout-18.insa-rouen.fr [193.49.10.114])
	by mx.cims.nyu.edu (8.15.1+Sun/8.15.1) with ESMTP id w31DDrX9012521
	for <shasha@cims.nyu.edu>; Sun, 1 Apr 2018 09:13:53 -0400 (EDT)
Received: from sogo.insa-rouen.fr (sogo.insa-rouen.fr [193.49.10.84])
	by smtpout.insa-rouen.fr (Postfix) with ESMTP id C0FC1600768
	for <shasha@cims.nyu.edu>; Sun,  1 Apr 2018 14:56:25 +0200 (CEST)
Received: from localhost (localhost [127.0.0.1])
	by sogo.insa-rouen.fr (Postfix) with ESMTP id ACC684E8D3
	for <shasha@cims.nyu.edu>; Sun,  1 Apr 2018 14:56:20 +0200 (CEST)
to: "Dennis Shasha" <shasha@cims.nyu.edu>
from: "Masson Marius" <marius.masson@insa-rouen.fr>
message-id: <64ef-5ac0d700-c7-69895700@208329510>
subject: Final version of exercice 2
X-Forward: 88.179.166.137
date: Sun, 01 Apr 2018 14:56:20 +0200
MIME-Version: 1.0
content-type: multipart/mixed; boundary="----=_=-_OpenGroupware_org_NGMime-25839-1522587380.609175-7------"
User-Agent: SOGoMail 2.3.8
X-Greylist: inspected by milter-greylist-4.6.2 (mx.cims.nyu.edu [128.122.49.99]); Sun, 01 Apr 2018 09:13:53 -0400 (EDT) for IP:'193.49.10.114' DOMAIN:'smtpout-18.insa-rouen.fr' HELO:'smtpout.insa-rouen.fr' FROM:'marius.masson@insa-rouen.fr' RCPT:''
X-Greylist: Delayed for 00:17:21 by milter-greylist-4.6.2 (mx.cims.nyu.edu [128.122.49.99]); Sun, 01 Apr 2018 09:13:53 -0400 (EDT)
X-Virus-Scanned: clamav-milter 0.99.4 at mx
X-Virus-Status: Clean
X-Scanned-By: MIMEDefang 2.80 on 128.122.49.99
Status: R

Part 1:
content-type: multipart/alternative; boundary="----=_=-_OpenGroupware_org_NGMime-25839-1522587380.608937-6------"


Part 1.1:
content-type: text/plain; charset=utf-8
content-length: 664
content-transfer-encoding: quoted-printable


Hi Dennis!

I worked a lot on the two hints you gave me and I finally did two versions of the program :

1. The first one remembers the best result and avoid a lot of calculations, on average we have the solution in 4 minutes ( 242 seconds exactly I tested with a lot of value of n )

2. The second one uses Threads, we never saw that at school but I found a lesson on internet which explains well how it works, on average we have the solution in 110 seconds!!

Thank you a lot for all your advices and for the next problem I will try to be more antonomous.

I'm going to explain to others how threads work and what I did,

Warmly,
Marius Masson

Part 1.2:
content-type: text/html; charset=utf-8
content-length: 757
content-transfer-encoding: quoted-printable

<html>Hi Dennis!<br /><br />I worked a lot on the two hints you gave me and I finally did two versions of the program :<br /><br />1. The first one remembers the best result and avoid a lot of calculations, on average we have the solution in 4 minutes ( 242 seconds exactly I tested with a lot of value of n )<br /><br />2. The second one uses Threads, we never saw that at school but I found a lesson on internet which explains well how it works, on average we have the solution in 110 seconds!!<br /><br />Thank you a lot for all your advices and for the next problem I will try to be more antonomous.<br /><br />I&#39;m going to explain to others how threads work and what I did,<br /><br />Warmly,<br />Marius Masson</html>

Part 2:
content-type: text/plain
content-disposition: attachment; filename="ex2thread.py"
content-transfer-encoding: quoted-printable

import random

import sys

from threading import Thread, RLock

import time

Z=[]

def nbcoins(n,coins):  # this fonction  find the number of pieces for a denomination of coins
    tmps1=time.clock()
    p=0
    L=[]
    for i in range(0,240):
        L.append(500)
    L[coins[0]-1]=1
    L[coins[1]-1]=1
    L[coins[2]-1]=1
    L[coins[3]-1]=1
    for i in range(0,240):
        if L[i]==500:
            L[i]=min(L[i-coins[0]],L[i-coins[1]],L[i-coins[2]],L[i-coins[3]])+1
        if i%5==0:
            p=p+n*L[i]
        else :
            p=p+L[i]
    tmps2=time.clock()
    #print (tmps2-tmps1)
    return p
    
def nbcoinsfast(s,n,coins):  
    tmps1=time.clock()
    p=0
    L=[]
    j=0
    for i in range(0,240):
        L.append(500)
    L[coins[0]-1]=1
    L[coins[1]-1]=1
    L[coins[2]-1]=1
    L[coins[3]-1]=1
    while(j<240 and p<s):
        if L[j]==500:
            L[j]=min(L[j-coins[0]],L[j-coins[1]],L[j-coins[2]],L[j-coins[3]])+1
        if j%5==0:
            p=p+n*L[j]
        else :
            p=p+L[j]
        j=j+1
    tmps2=time.clock()
    #print (tmps2-tmps1)
    if (j<240):
        return 100000000000000000000000
    else:
        return p   
         
def g(n,i):
    tmps3=time.clock()    
    s=nbcoins(n,[1,2,10,20])
    d=2
    e=10
    f=20
    for a in range(i,i+10):
        
        for b in range(i+1,240):
            for c in range(b+1,241):
                z=nbcoinsfast(s,n,[1,a,b,c])
                if z<s:
                    d=a
                    e=b
                    f=c
                    s=z
    tmps4=time.clock()
    Z.append([1,d,e,f])
    #print (tmps4-tmps3)
    return 1,d,e,f

print ("Value of n")
n=int(input())
TMPS1=time.clock()

verrou = RLock()


class Afficheur(Thread):


    def __init__(self, mot):
        Thread.__init__(self)

        self.mot = mot


    def run(self):


        with verrou:
            for lettre in self.mot:

                sys.stdout.write(lettre)
                sys.stdout.flush()

    thread_1 = Afficheur(str(g(n,2)))
    thread_2 = Afficheur(str(g(n,12)))

    
    thread_1.start()
    thread_2.start()

    thread_1.join()
    thread_2.join()
    

X=[]
for i in range(0,len(Z)):
    X.append(nbcoins(n,Z[i]))
print("\n")
print("the best denomination of coins is :")
print("\n")
print(Z[X.index(min(X))])
TMPS2=time.clock()
print("\n")
print("time of execution :")
print("\n")
print(TMPS2-TMPS1)


Part 3:
content-type: text/plain
content-disposition: attachment; filename="ex2new.py"
content-transfer-encoding: quoted-printable

import time

def nbcoins(n,coins):  # this fonction  find the number of pieces for a denomination of coins
    tmps1=time.clock()
    p=0
    L=[]
    for i in range(0,240):
        L.append(500)
    L[coins[0]-1]=1
    L[coins[1]-1]=1
    L[coins[2]-1]=1
    L[coins[3]-1]=1
    for i in range(0,240):
        if L[i]==500:
            L[i]=min(L[i-coins[0]],L[i-coins[1]],L[i-coins[2]],L[i-coins[3]])+1
        if i%5==0:
            p=p+n*L[i]
        else :
            p=p+L[i]
    tmps2=time.clock()
    #print (tmps2-tmps1)
    return p

def nbcoinsfast(s,n,coins):  # this fonction  find the number of pieces for a denomination of coins
    tmps1=time.clock()
    p=0
    L=[]
    j=0
    for i in range(0,240):
        L.append(500)
    L[coins[0]-1]=1
    L[coins[1]-1]=1
    L[coins[2]-1]=1
    L[coins[3]-1]=1
    while(j<240 and p<s):
        if L[j]==500:
            L[j]=min(L[j-coins[0]],L[j-coins[1]],L[j-coins[2]],L[j-coins[3]])+1
        if j%5==0:
            p=p+n*L[j]
        else :
            p=p+L[j]
        j=j+1
    tmps2=time.clock()
    #print (tmps2-tmps1)
    if (j<240):
        return 100000000000000000000000
    else:
        return p
    
def g(n):
    tmps3=time.clock()    
    s=nbcoins(n,[1,2,10,20])
    d=2
    e=10
    f=20
    for a in range(2,239):
        print("coucou")
        for b in range(a+1,240):
            for c in range(b+1,241):
                z=nbcoinsfast(s,n,[1,a,b,c])
                if z<s:
                    d=a
                    e=b
                    f=c
                    s=z
    tmps4=time.clock()
    print (tmps4-tmps3)
    return(1,d,e,f)
                
