Ancestors

Written by gosha on 2025-01-27 at 06:23

The #SICP example of counting change (page 51 of the PDF) is kicking my butt, ha. It took me a really long time to understand that "using all n kinds of coins" means "you can choose freely from all the n available types of coins but don't need to use all of them". And now, as a challenge, I'm trying to come up with an iterative process to solve this and I'm really struggling!

No one said that studying computer science at 42yo would be easy 😌

=> More informations about this toot | More toots from gosha@merveilles.town

Toot

Written by gosha on 2025-01-28 at 06:30

Oooh it's dynamic programming™

=> More informations about this toot | More toots from gosha@merveilles.town

Descendants

Written by gosha on 2025-01-28 at 07:03

Had to go learn to use let, iterations, and vectors to come up with that one, but it works.

=> View attached media

=> More informations about this toot | More toots from gosha@merveilles.town

Written by gosha on 2025-01-28 at 07:13

Or just use a do instead of a named let!

=> View attached media

=> More informations about this toot | More toots from gosha@merveilles.town

Written by Kototama on 2025-01-29 at 10:19

@gosha is the exercise supposed to be done with recursion or it does not matter?

=> More informations about this toot | More toots from kototama@merveilles.town

Written by gosha on 2025-01-29 at 10:23

@kototama It's not an exercise per se, but a challenge that follows an example. The example is of a recursive tree algorithm for solving the same problem, but it's very inefficient because it recomputes identical subtrees many times. And the challenge is to come up with a more efficient algorithm. In a previous example, this is done via a tail recursive procedure, but here I couldn't come up with a way to do that. The only other alternative I could find was to use memoization on the original tree recursive algorithm, but that's a bit too obvious... so searching further I landed on dynamic programming, which I learned when I was grinding leetcode for job interviews last year. It's likely not what the authors intended!

=> More informations about this toot | More toots from gosha@merveilles.town

Written by Kototama on 2025-01-29 at 10:25

@gosha ah thanks. I always confused them both a bit :-)

=> More informations about this toot | More toots from kototama@merveilles.town

Written by gosha on 2025-01-29 at 10:31

@kototama Me too!

=> More informations about this toot | More toots from gosha@merveilles.town

Written by フェリ―ペ on 2025-01-28 at 11:22

@gosha shouldn't the iterative approach still use recursion?

=> More informations about this toot | More toots from fkinoshita@merveilles.town

Written by gosha on 2025-01-28 at 11:32

@fkinoshita I thought so too but couldn't come up with one! How did you go about it?

=> More informations about this toot | More toots from gosha@merveilles.town

Written by フェリ―ペ on 2025-01-28 at 16:04

@gosha i also couldn't figure out for this exercise, i was hopeful you had another implementation!

=> More informations about this toot | More toots from fkinoshita@merveilles.town