zingbretsen @zingbretsen@qoto.org

@timorl @Absinthe I can't see your repo

@Absinthe #toyprogrammingchallenge

https://git.qoto.org/zingbretsen/nonadjacent_sums/blob/master/main.py

This solution modifies the list as we loop over it. It ensures that at each step, we have the maximum possible sum at each step.

The possibility of having negative numbers necessitates checking at each step.

O(N) time, and repurposes the original list for calculations, so adds no space overhead. This could also be done with a separate 2-item register if the original list should not be modified. This would also be constant space.

@Absinthe @freemo never heard of it 😆

@Absinthe #toyprogrammingchallenge I did this with recursion (plus caching). Will create a repo tomorrow, but the lru_cache in Python is pretty awesome. The recursive solution starts to slow down significantly as the input strong gets longer, but caching the intermediate results keeps it super fast.

@Absinthe looks good.

I'll try to do something with the dynamic programming approach tomorrow or Monday.

For something like multiplication, I don't think it will make much of a difference in the execution time, but for a more expensive operation it would

@Absinthe looks right to me

@Absinthe @freemo there's probably a dynamic programming approach where you cache the results of sub problems.

Maybe a recursive solution where you split the filtered list in half and return the product of the result of calling the function on both halves. Python has a decorator you can use called lru_cache which can cache the results of calling a function with specific inputs. This way, when it hits a problem that it's already seen before, it can just serve the result up from the cache instead of recomputing.

@Absinthe Rather than maintaining state with the deque, it would probably be better to pass the index in to the product function.

@Absinthe Yeah, MapReduce is (well, was) pretty widely used for "big data" processing

@Absinthe Yes, you could do it that way. And that would also probably be better with the functional approach.

@Absinthe The lambda is basically an anonymous function. It's passed in to the reduce call. Reduce calls that repeatedly until you're left with only one value.

@Absinthe https://book.pythontips.com/en/latest/map_filter.html

I think that gives a good breakdown of map, filter, and reduce, which are common in functional programming.

@Absinthe Here is my #toyprogrammingchallenge no-division solution:

```
#!/usr/bin/env python
from collections import deque
from functools import reduce
from random import randint

def get_product_and_rotate(d):
"""Gets product of all but the first items in the queue"""
prod = reduce(lambda a, b: a * b, list(d)[1:])
d.rotate(-1) # Rotates left so that the next
return prod

if __name__ == "__main__":
n_items = randint(2, 10)
input_list = [randint(0, 9) for _ in range(n_items)]
print(input_list)
product_queue = deque(input_list)
print([get_product_and_rotate(product_queue) for _ in input_list])
```

Uses `reduce` for the multiplication, and uses a `deque` (double-ended queue) to rotate the list. I've read that using a deque is actually more efficient than just taking slices out of the list.

@Absinthe exactly, if you already visited an item, you don't need to check it again.

List slicing is very useful. It is inclusive of the first index and exclusive of the second index. e.g.,

[0,1,2,3,4][1:3] would return [1,2]

Leaving off the first index will start you at the beginning of the list.

Leaving off the second index will include everything through the end of the list.

@Absinthe #toyprogrammingchallenge Still not at a computer, but I think this would work (and be slightly more efficient):

print(any(the_num - item in the_list[n+1:] for n, item in enumerate(the_list)))

i.e., only check elements to the right of the current element

Was also considering list.remove(item) to remove the item under consideration, but that operates in place (without returning the modified list) and I think the slicing solution is clearer. Also, it's generally not good to modify a list that you're looping over.

Does the line above make sense?

@Absinthe I have an idea, but not sure if it will work in one line

@Absinthe I will remember to do so when I post my solution 🙃

@Absinthe That sounds very fair. I'll submit am example using a `deque` later today!