Follow

Okay, here is another freebie :) I will put in a real one before the end of the weekend.

Basically, you are given a list from which you need to create a new list where each element is the product of all the "OTHER" elements.

I found a few interesting corner cases.

I challenge you to give it a try!

Read the challenge here:

git.qoto.org/Absinthe/productn

My attempt is checked into that repo as well.

@Absinthe I didnt get the chance to do the last one... This one is super easy but the follow up is kina cool. I can see a way of doing the follow-up in log-time, anyone have anything better?

@freemo @Absinthe #programmingchallenge

Common Lisp again:

(defun excluded-product (sequence)
(let ((product (reduce #'* sequence :initial-value 1)))
(map 'list (lambda (x) (/ product x)) sequence)))

(defun excluded-product-without-division (sequence)
(flet ((prod (seq)
(reduce #'* seq :initial-value 1)))
(loop while (cdr sequence)
for tail = (cdr sequence) then (cdr tail)
for head = nil then (append head (list (pop sequence)))
collect (* (prod head) (prod tail)))))

@freemo @Absinthe
My attempt without division
git.sr.ht/~namark/mercury_stuf
It's linear but requires 3x the space. The idea is to calculate partial products of the list, from left to right, and right to left, then the final values based on corresponding neighbouring values in partial product lists.

Probably the worst explanation and my mercury code seems unreadable to me, so here's a c++ version
ix.io/1KzG/cpp

#toyprogrammingchallenge
#mercurylang #cpp

@Absinthe Doing this without division is getting more difficult. But I am almost done with it - I think...

Finished code (Python) 

@Absinthe I did it with Python! Here is my code:

input = [1, 2, 3, 4, 5]
output = []
for x in range(0, len(input)):
i = input[x]
output.append(1)
for n in input:
if n != i:
output[x] = output[x] * n

Finished code (Python) 

@masterofthetiger @Absinthe would you mind if I gave you some feedback on your code?

Finished code (Python) 

@zingbretsen
I wouldn't mind at all. I am sure I screwed up on it. Even though I cleaned it up a bit.

@Absinthe

Finished code (Python) 

@masterofthetiger @Absinthe
I haven't tried running it yet, but I'm pretty sure you would get the wrong answer if the input list had repeated elements, e.g., [5,1,2,3,4,5]. Because you are checking that n != i, where i is the current element in the input list, if that element occurs more than once, you will not include that in the product. I believe the question wants you to exclude only the element in that given position on the list, not all elements of that value.

Finished code (Python) 

@zingbretsen
Oh yeah. I forgot about that case. Oops. I will fix that real quick.

@Absinthe

Fixed code (Python) 

@zingbretsen
Now this code should work:

input = [1, 2, 3, 4, 5]
output = []
for x in range(0, len(input)):
i = input[x]
output.append(1)
for n in range(0, len(input)):
if n != x:
output[x] = output[x] * input[n]

print(output)

@Absinthe

Finished code (Python) 

@masterofthetiger @Absinthe and style-wise, i is usually used as the index when looping over numbers, so it's confusing that it's storing your values here. Also, since this is something that's so common to do, python provides a way of looping over both the index and the value at the same time: enumerate

for i, elem in enumerate(input):
stuff

Finished code (Python) 

@zingbretsen
Thanks so much! I recently discovered range, and wanted something better to use. I will definately use enumerate in the future.

@Absinthe

@masterofthetiger @Absinthe
One last style thing is that python has some syntactic sugar regarding mathematical operations so you could do:
output[x] *= n

Which multiplies output[x] by n and stores the value back in outout[x].

A minor thing, but is generally the more pythonic way of doing it

Finished answer (Python) 

@zingbretsen

This is pretty simple now. Can you think of any edge cases which this does not cover?

input = [1, 2, 3, 4, 5]
output = []
for x in range(0, len(input)):
output.append(1)
for i, number in enumerate(input):
if i != x:
output[x] *= number

@Absinthe

Finished answer (Python) 

@masterofthetiger @zingbretsen

That works. Simpler and much more elegant looking code than my craziness. I am not sure about the relative efficiency between yours and mine, I think you might have more multiplications but you also solve the side case of "don't use division"

@Absinthe how do you feel about importing modules for these challenges? One standard lib module would make the no-division part really elegant.

@zingbretsen personally, I don't care. The "freebies" are ones I have found that were given as job interview exercises (so far).

Personally, I am working on buffing up my personal python skills, so I am trying to import as little as possible. So far I have needed only the random import for setting up data.

But you need to decide what you want to get out of these challenges. If importing libraries works for you I don't see anything much wrong with it. Unless the challenge is about the functionality that you want to import. For example. if the challenge was to write a bubblesort, obviously importing someone else's bubblesort library would be pretty much cheating.

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

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

A Python solution 

@Absinthe Here is my 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.

A Python solution 

@zingbretsen now you are stretching me. I have never seen rotate() but I can intuit what it does. I also have not used lamda's. But what is happening in the reduce() call? I assume the lamda takes 2 values how is that acting on the list? Or is the lamda being passed into the reduce call ... time to read about reduce :)

@Absinthe book.pythontips.com/en/latest/

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

@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.

@zingbretsen yeah, I looked it up. Works nice, perhaps I will try it with the list comprehension that I suggested.

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

A Python solution 

@zingbretsen Okay, this is less of a criticism as it is a question of understanding:
You used the deque to rotate and slice the list for the multiplication, Could you have also used list comprehension something like this:

current_index = the one we are working on
[ value for idx, value in enumerate(list) if idx != current_idx]

I know you wanted to use the deque

A Python solution 

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

A Python solution 

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

A Python solution 

@zingbretsen right... bbiab, errand time

A Python solution 

@zingbretsen The only problem I have with all of these no-division solutions is that you have to do the multiplication in all cases. I wonder if there is a mathematical trick to somehow solve without having to calculate the whole product each time, like the division solution. @freemo ... any ideas?

A Python solution 

@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.

A Python solution 

@zingbretsen What about this... as a one liner:

[reduce(lambda a, b: a *b, [ y for x, y in enumerate(list) if x != idx]) for idx, _ in enumerate(list)]

A Python solution 

@zingbretsen This works...

print("One Liner no division")
print([reduce(lambda a, b: a *b,
[ y for x, y in enumerate(random_list) if x != idx])
for idx, _ in enumerate(random_list)])

It's a one liner, except I am sticking to 80 columns so I split it a few times.. still calling it a one liner :)

A Python solution 

@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

re: A Python solution 

@zingbretsen @Absinthe

I can’t think of any way to avoid the multiplications.

Here’s the lisp solution using rotate. Destructive, so ugly, but actually leaves the input list the same as it came in. Conses only the result list.

(defun rotate (list) (prog1 (nconc (cdr list) list) (setf (cdr list) nil))) (defun excluded-product-with-rotation (list) (loop with l = list collect (reduce #'* (cdr l) :initial-value 1) do (setf l (rotate l)) (when (eq l list) (loop-finish))))

re: A Python solution 

@billstclair @zingbretsen Hey bill please remember to include hashtag in your responses so people can find them by searching for it.

Can I run this in gcl or emacs or do I need more code to have the list and output?

re: A Python solution 

@Absinthe @zingbretsen

I'm not writing any of my solutions in Emacs lisp. All Common Lisp. I test in Clozure Common Lisp (CCL) or LispWorks, depending on which I'm currently connected to in Slime, but it should work in gcl, clisp, or SBCL, too.

re: A Python solution 

@billstclair @zingbretsen I have access to gcl but it looks like I need more to make this function

re: A Python solution 

@Absinthe @zingbretsen

Works for me:

wws@Xossbow:~/lisp/toy-programming-challenge$ git remote -v origin https://github.com/billstclair/toy-programming-challenge.git (fetch) origin https://github.com/billstclair/toy-programming-challenge.git (push) wws@Xossbow:~/lisp/toy-programming-challenge$ ls beer.lisp excluded-product.lisp LICENSE README.md zero-to-nine.lisp wws@Xossbow:~/lisp/toy-programming-challenge$ gcl GCL (GNU Common Lisp) 2.6.12 CLtL1 Oct 29 2015 23:21:28 Source License: LGPL(gcl,gmp), GPL(unexec,bfd,xgcl) Binary License: GPL due to GPL'ed components: (XGCL READLINE UNEXEC) Modifications of this banner must retain notice of a compatible license Dedicated to the memory of W. Schelter Use (help) to get some basic information on how to use GCL. Temporary directory for compiler files: /tmp/ >(load "excluded-product.lisp") Loading excluded-product.lisp Finished loading excluded-product.lisp T >(apropos "excluded" *package*) EXCLUDED-PRODUCT Function EXCLUDED-PRODUCT-WITH-ROTATION Function EXCLUDED-PRODUCT-WITHOUT-DIVISION Function >(excluded-product '(1 2 3 4)) (24 12 8 ...) >*print-length* 3 >(setf *print-length* nil) NIL >*** (24 12 8 6) >(excluded-product-with-rotation '(1 2 3 4)) (24 12 8 6) >

re: A Python solution 

@billstclair @zingbretsen right, so I had to do more than just run it :) It just gave me some funtions to call. I got it now.

re: A Python solution 

@Absinthe @zingbretsen

You CAN make top-level command line programs in Lisp, but it's not optimized for that, so you end up with a lot of boilerplate or libraries to support the top-level call.

re: A Python solution 

@Absinthe @zingbretsen

I'm going to do the next one in Elm, working example published at https://ellie-app.com

#toyprogrammingchallenge

re: A Python solution 

@billstclair @zingbretsen excellent! I can't wait.

A Python solution 

@zingbretsen am pretty sure there is no technical reason not to use division, just to make the problem more complicated. I am getting ready to put up a new one. But feel free to keep playing with this one. I got a new one today, but it seems a little "specific" because they give a python code starting point, and want you to serialize and deserialize a binary tree. I will likely not put that one up as a freebie. Especially since I want to get the new real on up.

@Absinthe
other product using division
git.sr.ht/~namark/mercury_stuf
hate all the edge cases

no division version in the working, hopefully would be much smoother.

#toyprogrammingchallenge #mercurylang

@namark Now I really wish I had gotten the compiler installed. :) We'll see what happens during the week.

Sign in to participate in the conversation
Qoto Mastodon

QOTO: Question Others to Teach Ourselves. A STEM-oriented instance.

An inclusive free speech instance.
All cultures and opinions welcome.
Explicit hate speech and harassment strictly forbidden.
We federate with all servers: we don't block any servers.