Thread Rules
1. This is not a "do my homework for me" thread. If you have specific questions, ask, but don't post an assignment or homework problem and expect an exact solution.
2. No recruiting for your cockamamie projects (you won't replace facebook with 3 dudes you found on the internet and $20)
3. If you can't articulate why a language is bad, don't start slinging shit about it. Just remember that nothing is worse than making CSS IE6 compatible.
4. Use [code] tags to format code blocks.

Acrofales

Spain17849 Posts

May 31 2017 17:00 GMT

#17681

On June 01 2017 01:00 Hanh wrote:
What would an algorithmic solution be?

What the guys above you did.

Deleted User 3420

24492 Posts

May 31 2017 19:38 GMT

#17682

Ok we've been given homework #1.

It is okay for me to post homeworks, and to discuss them. I figure you guys will probably find this fun so I am posting it, I'll post my attempt before I read any solutions.

Assume you have a necklace of stones. Some of the stones have positive value and some
have negative value. You have the opportunity to snip the necklace in two places (creating two
bands) and weld the endpoints of one of the two bands back into a necklace. You would like
your new necklace to be as valuable as possible. You can assume the necklace has n stones
with values v[0], v[1], . . . , v[n − 1].

ah, so we have a circular connecting necklace and you snip it in 2 places, using one of the new bands to make a new necklace

(a) Give an algorithm to find the value of the new necklace. If all of the stones have negative
value your answer should be 0. Make your algorithm as clean and elegant as possible.

(b) Give an algorithm to determine where you should snip the original necklace (not just its
value). Make your algorithm as clean and elegant as possible. If all of the values are
positive you should not snip and your algorithm should print:
Do not snip.
If all of the values are negative you should not snip and your algorithm should print:
Throw necklace away.
If possible the algorithm should determine these two situations without explicitly checking
for them.

CecilSunkure

United States2829 Posts

May 31 2017 19:49 GMT

#17683

What the heck kind of homework question is that lol. My eyes glaze over trying to read the paragraphs. Sounds like a pretty hard problem. Looks like a linked list, or an array kind of problem. Linked list would probably be the easiest to write code for.

"Some have positive, some have negative", why can't we say signed integers? It's just signed integers.

It sounds like one of those "maximal subset" problems. I hate those problems man. Actually this problem here is my least favorite programming question I have ever heard, and sounds pretty similar to yours.

Edit: When it says clean and elegant, what do those terms even mean. Those are really subjective terms. It sort of sounds like "try to find the trick that makes this problem easy to solve", like the trick in the wikipedia page.

Deleted User 3420

24492 Posts

May 31 2017 19:57 GMT

#17684

When he says clean and elegant I imagine he is hinting that there is at least one efficient solution that will not be super complicated, and he wants that solution.

I think that interestingly enough this question is almost the opposite of question 1 of the 3 questions I posted back a little bit ago.

For the sake of familiarity I would view the necklace as a circular array (just "decide" that the ends connect)

Blisse

Canada3710 Posts

May 31 2017 20:05 GMT

#17685

Overcomplicating it a bit, the problem simply boils down to the maximum subarray problem.

Of course, part of the course is learning how to decipher word problems.

Acrofales

Spain17849 Posts

May 31 2017 20:05 GMT

#17686

Sounds like dynamic programming to me. Did you learn dynamic programming yet?

E: re Blisse
+ Show Spoiler +

Yeah. That. Just have to make sure you copy the values twice, so you get the fact that the first and last element are connected. Alternatively you could loop an extra time at the end until your previous value is greater or equal to the newest one.

Deleted User 3420

24492 Posts

May 31 2017 20:21 GMT

#17687

It isn't the same problem though, I think. I haven't started it yet but I think for this one we actually need to find the minimum subarray. Finding the maximum could give us an incorrect result.

For example if our necklace is:

5 7 -2 5 -2
and then we return back the whole necklace - we are wrong. (or if you don't like this example, replace with much bigger more complicated examples)

I know of dynamic programming but I haven't really done much of it in practice. I think I will be okay though since I know the premise behind it.

CecilSunkure

United States2829 Posts

May 31 2017 20:29 GMT

#17688

What's wrong with returning the whole array?

Deleted User 3420

24492 Posts

May 31 2017 20:32 GMT

#17689

in the example above the correct answer would be to remove an instance of negative 2 and return everything else, ie: 5 7 5 -2

CecilSunkure

United States2829 Posts

May 31 2017 20:34 GMT

#17690

Minimum subarray means lowest value, so -2. Maximum means 5 7 -2 5, for value of 15 (like you correctly pointed out).

Acrofales

Spain17849 Posts

May 31 2017 20:38 GMT

#17691

On June 01 2017 05:29 CecilSunkure wrote:
What's wrong with returning the whole array?

In that example? It doesn't maximize the value. By just returning [5, 7] you get a value of 12. If you add negative values, your value isn't maximal.

@Travis: you don't want a minimal length. You don't want maximal length. You want maximal value, which is what blisse's link describes.

E: I read -5 for the second 5 :p. But even so you don't want to return the whole array

Deleted User 3420

24492 Posts

May 31 2017 20:43 GMT

#17692

I didn't actually realize he had posted a link, it seems to be the exact same color as normal text for me. I thought he was referring to a problem I had posted yesterday.

Which, actually is that problem. But making it circular changes it a bit.

I know we don't want maximal or minimal length, but I am now seeing there really is no difference between looking for minimum subarray or looking for maximum subarray.

CecilSunkure

United States2829 Posts

May 31 2017 20:44 GMT

#17693

Yep that's right, maximum and minimum subarrays can have any length, because the values are what determine max/min, not the element indices or how many elements the subarray has.

And yeah... TL links seem to have lost their luster. It's impossible to see them.

Deleted User 3420

24492 Posts

May 31 2017 20:53 GMT

#17694

okay now that I am actually working on this it is a bit harder than what I thought it was.

I don't think Blisse's link does it justice - the trouble for me is in handling that it is circular.

edit: I looked up an answer and it's really cute - you guys were underselling this problem

a hint is that my intuition was right that I needed to find the maximum negative subarray, but there is more to it than that.

CecilSunkure

United States2829 Posts

May 31 2017 21:37 GMT

#17695

lol well i'm glad you're enjoying it. You model student you

Acrofales

Spain17849 Posts

May 31 2017 21:54 GMT

#17696

Pretty sure you can solve it just fine as follows:

+ Show Spoiler +


neckarray = 2*necklace 

maxstart = 0
maxend = 0
maxval = 0

tempstart = 0
tempval = 0

for index, value in neckarray:
   tempval = max(value, tempval + value);
   if tempval == value:
     tempstart = index

   maxval = max(tempval, maxval)
   if maxval == tempval:
      maxstart = tempstart
      maxend = index +1

if maxend - maxstart > len(necklace):
   print "Don't cut"
elif maxval == 0:
   print "Trash"
else:
   maxend = maxend%len(necklace)
   maxstart = maxstart%len(necklace)
   print("cut at", maxstart, maxend, "for a necklace with value", maxval)

Deleted User 3420

24492 Posts

May 31 2017 22:14 GMT

#17697

edit2:

I don't know what language that is, but I am guessing what you are doing is

1.) make an array that repeats the original array once
2.) find the maximum continuous subarray.
3.) if the maximum continuous subarray is greater in length than the original array, don't cut

{5, 5, -1, 5, -1, 5} would return "don't cut", which would be wrong because the correct answer would remove an instance of -1

Blisse

Canada3710 Posts

May 31 2017 22:39 GMT

#17698

@travis, haven't walked through, but arcofales's code repeats the original array twice, and performs the maximal subarray code on that repeated array.

~~Seems to be missing a check to ensure that the selected maximum subarray is only of length N though.~~

edit: oo, neat lol

Acrofales

Spain17849 Posts

May 31 2017 22:40 GMT

#17699

On June 01 2017 07:14 travis wrote:
edit2:

I don't know what language that is, but I am guessing what you are doing is

1.) make an array that repeats the original array once
2.) find the maximum continuous subarray.
3.) if the maximum continuous subarray is greater in length than the original array, don't cut

{5, 5, -1, 5, -1, 5} would return "don't cut", which would be wrong because the correct answer would remove an instance of -1

It is pseudopython. Mostly python, but too lazy to make it properly. And yeah, completely interested code.

Unless I made a mistake somewhere, it'd return 5, 4 as the start and end for your cut, which is what you'd want. The loop would end with 5, 10 as the maxstart, maxend. Those would then be adjusted (just the maxend in this case) to not be greater than the necklace's length.