dynamic programming - Counting change in Haskell -

-

i came across following solution dp problem of counting change:

count' :: int -> [int] -> int count' cents coins = aux coins !! cents   aux = foldr addcoin (1:repeat 0)           addcoin c oldlist = newlist                   newlist = (take c oldlist) ++ zipwith (+) newlist (drop c oldlist)

it ran faster naive top-down recursive solution, , i'm still trying understand it.

i given list of coins, aux computes every solution positive integers. solution amount index list @ position.

i'm less clear on addcoin, though. somehow uses value of each coin draw elements list of coins? i'm struggling find intuitive meaning it.

the fold in aux ties brain in knots. why 1:repeat 0 initial value? represent?

it's direct translation of imperative dp algorithm problem, looks (in python):

def count(cents, coins):     solutions = [1] + [0]*cents # [1, 0, 0, 0, ... 0]     coin in coins:         in range(coin, cents + 1):             solutions[i] += solutions[i - coin]     return solutions[cents]

in particular, addcoin coin solutions corresponds to

for in range(coin, cents + 1):     solutions[i] += solutions[i - coin]

except addcoin returns modified list instead of mutating old one. haskell version, result should have unchanged section @ beginning until coin-th element, , after must implement solutions[i] += solutions[i - coin].

we realize unchanged part take c oldlist , modified part zipwith (+) newlist (drop c oldlist). in modified part add i-th elements of old list , i - coin-th elements of resulting list. shifting of indices implicit in drop , take operations.

a simpler, classic example kind of shifting , recursive definition fibonacci numbers:

fibs = 0 : 1 : zipwith (+) fibs (tail fibs)

we write imperatively as

def fibs(limit):     res = [0, 1] + [0]*(limit - 2)     in range(2, limit):         res[i] = res[i - 2] + res[i - 1]     return res

turning coin change, foldr addcoin (1:repeat 0) corresponds initialization of solutions , loop on coins, change initial list infinite instead of finite (because laziness lets that).


Comments

Post a Comment

Popular posts from this blog

qt - Using float or double for own QML classes -

-
i've created components , helper methods using c++ , qt used in qml gui. of methods calculate gui elements (size, transformations, scene graph items creation). target arm 32 bit using opengl / eglfs render output. opengl using float , qml using real (defined double ). what should use in c++ do not lose precision? if use qreal ( double ) shouldn't lose precision. if git grep float in qtbase.git , can find out bit more: dist/changes-5.2.0-**************************************************************************** dist/changes-5.2.0-* important behavior changes * dist/changes-5.2.0-**************************************************************************** dist/changes-5.2.0- dist/changes-5.2.0- - qt compiled qreal typedef'ed double on dist/changes-5.2.0: platforms. qreal float on arm chipsets before. guarantees more dist/changes-5.2.0- consistent behavior between platforms qt supports, binary dist/chan...
Read more

Create Outlook appointment via C# .Net -

-
i need create outlook appointment using microsoft.office.interop.outlook , while can work locally on own workstation , works if run web application via server's browser, not work when connect server externally. hence, think might permission issue. i changed application pool identity " localsystem " don't access denied error. unfortunately, doesn't work. the app behaves if appointment created, appointment doesn't appear in outlook. here include file on top of aspx.cs page using outlook = microsoft.office.interop.outlook; here code using pop appointment. outlook.application apptapp = new outlook.application(); outlook.appointmentitem appt = apptapp.createitem(outlook.olitemtype.olappointmentitem) outlook.appointmentitem; appt.subject = txtfirstname.text + " " + txtlastname.text; appt.body = txtcomment.text; appt.alldayevent = false; appt.start = datetime.parse(txtreminderdate.text + " 8:00 am"); appt.end = datetime.p...
Read more

ios - Swift Array Resetting Itself -

-
i have 2 arrays: pointhistory , datehistory . have nstimer , , when timer runs out, action called. in action appending int pointhistory , , current date string datehistory . here timer action: func timeraction() { let steppervalue = int(stepper.value) employee.numberofpoints = steppervalue networking.saveemployee(employee, completion: { (error) -> void in if error != nil { let alert = uialertcontroller(title: "error", message: "there error updating \(self.employee.name)'s points", preferredstyle: .alert) let alertaction = uialertaction(title: "ok", style: .cancel, handler: nil) alert.addaction(alertaction) self.presentviewcontroller(alert, animated: true, completion: nil) } }) var dateformatter = nsdateformatter() dateformatter.dateformat = "mm-dd-yyyy" dateformatter.timezone = nstimezone.localtimezone() var date = nsdate() var ...
Read more