Ugh... fiendish CS proffs...

[WarDaft]

So I'm taking a uni intro CS course in scheme (below what I'm capable of, but meh)

One particular question though, I actually got wrong. Well, I lost a mark on anyway.

Specifically, we had to write a function to detect geometric sequences. I guess it's been too long since I took whichever high-school math class they cover geometric sequences in, because I completely forgot that a 0 0 0 ... is a geometric sequence for any Real a. It was of course, one of the test cases in the automated suite.

I'm half inclined to say that I'd eat my hat if anyone actually remembered that, but I prefer my hat on my head than with a side salad.

I guess I'm saying that felt a lot more like a "gotcha" than an actual CS assignment.

[letterX]

It's a bit of a gotcha. But, I'm also not entirely sure how you wrote a detector which specifically excluded that case... the simplest code I can think of is (in C):

Code: Select all

int input[length]; // Gets filled with the input

int ratio = input[1]/input[0];
for (int i = 1; i < length; ++i) {
    if (input[i] != input[i-1]*ratio)
        return false;
}
return true;

Which works on the sequence [a, 0, 0, ...]

[jaap]

You can avoid division altogether so that you avoid possible division by zero (when a=0).
Simply test that b*b=a*c for each consecutive triplet (a,b,c) in the sequence.

Also, in letterX's code the division is integer division, which produces wrong results (even if the sequence is only integers, e.g. for [27,18,12,8] ).

[Proginoskes]

Also, letterX's code crashes for the sequence [0, 0, 0, 0, ...]

[letterX]

Ahh yikes. Forgot the possibility of divide by zero. I guess the point I was trying to make wasn't as obvious as I thought it was.

[Yakk]

It is a perfectly valid test case. You should always check your edge cases, because it is there you are more likely to get bugs.

Once you noticed the problem, you get to either patch it, or you can find a better solution -- like s_n s_n+2 = s_n+1², which is a more elegant solution from a more civilized non-divisive age.

And remember, you don't lose marks. You where given partial credit for failing to actually answer the question, but you where reasonably close to the answer, so they took pity on you. s_n = a rⁿ is what you where supposed to detect, and you don't detect it!

[WarDaft]

I wouldn't have have had a perfect mark if I didn't check edge cases. I'm going to stick with the view that I lost the marks, because there are probably dozens of more or less elegant ways I could have coded a solution, and it's a CS class, and my mark is lower because of an edge case I didn't think of for something I haven't given any thought to at all for about 7 years prior to it, that doesn't (so far as I can tell anyway) have anything actually to do with the study of the structure and nature of algorithms, except that there is in fact an algorithm that computes it. It has that in common with virtually everything else. It's also the first gotcha actually in the course so far. So yeah, it feels like a loss, from a silly little gotcha. I know it's not really, but it feels that way. I do feel better having had someone immediately post an even worse solution here though. (Sorry letterX! I mean that in the nicest possible way.)

[letterX]

I do feel better having had someone immediately post an even worse solution here though. (Sorry letterX! I mean that in the nicest possible way.)

In fairness to myself, I did spend more or less exactly a minute thinking about that solution. So it's hardly surprising that I missed some of the fine details.

Which may possibly be the point your professor is trying to make in the first place: I don't at all know the specifics of the course, but sometimes paying attention to small details like that are pointless (for instance, in a theoretical "algorithms" course, where you care more about the high-level design of the algorithm) but sometimes, they are absolutely essential (In a software-engineering type course or anything that aims at giving a feel for what production-level code is like). For real code, corner cases like that are where things end up breaking for the customer in ways that make them unhappy. For instance, this error is a failure of the software author (both you, and me) to understand* the specifics of whatever they're modeling. In real projects, this happens all the time because it takes real effort to get the customer and developer on the same page in terms of exactly what is wanted.

Of course, this is just a stupid homework error, so the above may be too much to read into it, but the exact error of the developer not quite knowing exactly what to model, due to poor communication/lack of knowledge, and consequently getting the answer wrong, is a very common failure mode in real systems.


TL;DR Getting small details right is an important concern in real software, but in all likelihood, your professor probably just doesn't like giving out perfect scores.


* And frankly, it's not really a failure to understand, but a failure to give a damn, because seriously: I totally agree that nobody cares about geometric sequence recognition...

[WarDaft]

I don't at all know the specifics of the course, but sometimes paying attention to small details like that are pointless (for instance, in a theoretical "algorithms" course, where you care more about the high-level design of the algorithm) but sometimes, they are absolutely essential (In a software-engineering type course or anything that aims at giving a feel for what production-level code is like).

From the course description, general content so far, and the fact that there are many other courses explicitly referred to as software engineering, I was sure it was the former. There was another gotcha in class today, a trend I'm not liking, but an easy 98 is almost as good as an easy 100 and it's way better than coding in say, Java. I will just pay more attention I guess.

[OmenPigeon]

I'm leaning on Yakk's side with this one, for a number of reasons.

In a purely mathematical sense, you didn't submit a correct program. You were asked (perhaps not in these words, but in this spirit) to provide a function f such that for all x, where x is a member of the set of finite sequences of real numbers (or at least the approximations of such representable by current computers), if x is part of a geometric sequence, f(x) is true, and f(x) is false otherwise. There are some x (perhaps just one) for which IsGeometric(x) -> YourF(x) doesn't hold, so your program is incorrect. That's the basis on which you were, presumably, being graded, so I can't see how it's unfair to give partial credit for a partial solution.

Second, a sequence of all zeros is hardly a gotcha. It sounds like you're relatively early in your programming career, so this isn't a dig at you, just something you need to learn. For most of the common data types in most programming languages, there are a couple cases that you should learn to always, always check whenever you right a function with them. For integers, that's usually something like { 0, small and positive, small and negative, near the overflow limit, near the underflow limit }. For floating point numbers, also consider things within epsilon of those values, and it's not a bad idea to consider what'll happen as the number gets large and IEEE floats start mapping a single value to wide range of integers.¹

I'll dispute that there's a meaningful difference between academic code and "real software" another time, but even if we grant it, small details like these are often less important in "real software" than in your classroom. Outside of a few industries that sound like they'd be spectacularly unpleasant to work in, code is basically never "correct". The most you can say is that it "is working as expected" and "has made (me|my employer) money". Fresh in my mind is a function that, to simplify a bit, takes two integers and a great big pile of external state, and returns a boolean. My final implementation of this function, which has been merged into the master branch of a real software product in the real world, returns the wrong value if one the integers is a factor of the other and the external state is just right. Everyone on my team who's looked at the function knows this, but it turns out that making the function do the right thing will be too much of a pain in the ass and introduce unwanted side effects into the code and all those other things that make writing definitely totally all the time correct software just not worth it. Your code for class has none of the funky externalities that complicate industry software, pretty much all it has to be is correct and delivered on time. Most professors will relax the time thing if you ask nice. If you're going to ever write really actually correct software in your life, it's going to be in school.²

Again, none of this is to say that you're a bad programmer, and I really don't even have enough information to know whether it was an unfair assignment or not. All I know is that from what you've described, it doesn't *sound* unfair. And your first post in this thread was probably mostly about catharsis, and now you've got people all jumping down your throat, which, whoops the internet. But as a final note, if it's this early in the semester (or late, maybe? I don't know when semesters start anymore) and you're not performing as well as you expected in this class, maybe it isn't as far beneath you as you thought? Humility is always a good idea in the face of computers, for they are never wrong, only their programmers are.

1: This gets even worse with strings: there's nulls, empty strings, strings with all whitespace, strings with literal nulls in them, strings without any nulls anywhere (if you're in C), strings with any encoding that isn't ASCII, strings with escape sequences, etc. And date/time info gets even weirder. There are a number of cases where computer time on a single machine will flow backwards, and that's expected behavior, and you might have to deal with it someday.

2: Which isn't to say that industry software sucks. All the best code I've ever written was while on the job. But it's a very different kind of code than what I wrote at school, and very little of it is 'correct' in any meaningful sense beyond "does pretty much what the users want".

[WarDaft]

Second, a sequence of all zeros is hardly a gotcha.

No, it's not. A sequence starting from an arbitrary number followed by all zeros is a bit closer though, it almost sounds like you forgot about it too. I actually checked for all zeros, just not some number X followed by all zeros. I'm also not saying it's unfair, as I do not believe there's such thing as fairness or lack thereof. My exact words were that it was frustrating.

[markop2003]

Your program didn't do what was specced, that's hardly a "got 'ya". My Systems Design module was intentionally filled with "got 'ya"s with the spec being intentionally vague and full of holes meaning that you could be marked down for not doing something that wasn't part of the spec.

[Yakk]

Yep, writing bug free software is frustrating.

When you spotted the all zeros case, did you special case it? Special cases are a big, big red flag.

Next time you find such a special case, see if you can modify your algorithm such that it "just works" without having to special case that instance.

(I'm trying to figure out how to solve the 0,0,0,0,0... case without a special case -- the code going through a different branch -- while missing the 7,0,0,0,0...)

[jareds]

I actually can't think of a way to solve the problem without any special case for zero. Think Wason selection task...

Spoiler:

What everyone appears to have missed is that, while (1,0,0,0,0) might be considered a geometric sequence, (0,0,0,0,1) definitely is not. No method that is symmetric on list reversal can work. Either you do a division method and a special case that triples (x,0,0) are geometric, or you do a multiplication method and a special case that triples (0,0,non-zero) are not geometric. Then, of course, if you allow lists shorter than 3 elements, you need a special case for (0,non-zero).

Of course, many people define geometric sequences not to have a common ratio of 0, and this seems like a point in favor of that.

[Yakk]

Ah! Fiendish!

Now, if only 0 had a multiplicative inverse. Then the nth root of that inverse would allow you to make 0,0,0,0,0,1 a geometric sequence.

Lets see if I can avoid that special case...

Spoiler:

First, we do the s_n s__n+2 = s__n+1² trick.

Then we construct an a and a b, defining s_n = a bⁿ. We set a = s₀. We then get a guess for b that has to be right if we have a geometric sequence, but can be wrong if we don't have one. Then we test each element.

Which then backs us up to "set a = s_0, set b = anything you want (heck, leave it uninitialized! (assuming uninitialized values are value numbers, if undefined ones, in your language/compiler/environement) if s_0 is zero, otherwise b = s_1/s_0. Now test s_i = a b^i for each i. If that test passes, we have a geometric sequence. There is still that annoying special case.

Annoyingly, we are trying to prove there is no b such that s_i b = s_i+1. And by choosing an arbitrary value, we just have shown that some value of b doesn't work in the s₀ = 0 case. I can't think of a sufficiently generic proof (ie, that isn't isolated to this case) such that doing this is at all universally valid.

Nope, can't get rid of it.

[Proginoskes]

There's another nuance to this problem ... Since computers can't express 1/3 exactly (with floating point), [3, 1, 1/3] wouldn't turn out to be a geometric series, since 3 * (1/3) is highly unlikely to equal 1 exactly.

[jareds]

There's another nuance to this problem ... Since computers can't express 1/3 exactly (with floating point), [3, 1, 1/3] wouldn't turn out to be a geometric series, since 3 * (1/3) is highly unlikely to equal 1 exactly.

As originally posed, the problem is in Scheme, which has exact rationals.

[WarDaft]

So basically, no one in this thread has yet actually managed to post a correct solution to this very simple problem, including me.

Let us all never speak of this again.

[Xanthir]

What? No, several solutions are around. People are just looking for one without a special case for 0, which doesn't exist. Here, have a solution in Lisp:

Code: Select all

(defun arithmetic-sequence (seq)
  (cond ((zerop (second seq)) (when (every 'zerop (rest seq)) 0))
        ((some 'zerop seq) nil)
        (t
         (when (apply '= (mapcar '/ seq (rest seq)))
           (/ (second seq) (first seq))))))

[WarDaft]

What? No, several solutions are around. People are just looking for one without a special case for 0, which doesn't exist. Here, have a solution in Lisp:

Yes, but all of the solutions or suggestions posted, at the time, all missed something somewhere in recognizing geometric sequences. Knowing that I missed this case, I can actually fix my solution trivially. (Actually, given the particular way the problem was presented, I can fix it by deleting a single character.)

Oh, and, keeping with the trend of things, that really doesn't look like a function that will detect arithmetic sequences very well.



Like I said, let us never speak of this again.

[troyp]

What? No, several solutions are around. People are just looking for one without a special case for 0, which doesn't exist. Here, have a solution in Lisp:

Yes, but all of the solutions or suggestions posted, at the time, all missed something somewhere in recognizing geometric sequences. Knowing that I missed this case, I can actually fix my solution trivially. (Actually, given the particular way the problem was presented, I can fix it by deleting a single character.)

Oh, and, keeping with the trend of things, that really doesn't look like a function that will detect arithmetic sequences very well.



Like I said, let us never speak of this again.

Huh? What's wrong with Xanthir's code? It looks correct to me. And like he said, the other solutions that have failed have been attempts at a solution that doesn't special-case 0. Apart from LetterX's initial response, the only incorrect suggestion was Jaap's before jareds pointed out the problem with it. I admit I'd had the same faulty solution in mind, but then it's easy to miss edge cases I guess (which is why you have to test them ;-)) And now the consensus seems to be that such a solution is impossible.

Of course, many people define geometric sequences not to have a common ratio of 0, and this seems like a point in favor of that.

If that's true, then it's worse than a gotcha: the question is ambiguous and WarDaft's code should be acceptable. Unless the question explicitly defined a geometric sequence, which I get the impression is not the case (if it did, then you certainly couldn't complain it's a gotcha).

edit: (oh, I get it now, he named it wrong.)

[Xanthir]

Oh, and, keeping with the trend of things, that really doesn't look like a function that will detect arithmetic sequences very well.

Code: Select all

(defun arithmetic-sequence (seq)
  (cond ((zerop (second seq)) (when (every 'zerop (rest seq)) 0))
        ((some 'zerop seq) nil)
        (t
         (when (apply '= (mapcar '/ seq (rest seq)))
           (/ (second seq) (first seq))))))

Code: Select all

(defun arithmetic-sequence (seq)

Code: Select all

arithmetic-sequence

Like I said, let us never speak of this again.

Yes, let's.

[jareds]

Let us all never speak of this again.

Oh, why not?
...but I've had my fun.

[Proginoskes]

As originally posed, the problem is in Scheme, which has exact rationals.

Oh. Well, I was confused by the C code.

[letterX]

As originally posed, the problem is in Scheme, which has exact rationals.

Oh. Well, I was confused by the C code.

Yeah, I totally spaced on the scheme part. Even after people started talking about scheme, I had to actually ctrl-F "scheme" to realize that the OP was working in it. Which is odd because it was my first language. Writing so much C++ lately that it just sort of flows out... like so much effluvia...

[douglasm]

I'd say this sort of missed detail is exactly the sort of thing that really good programmers need to be good at spotting. Missing things like this - not this kind of math thing specifically, but weird special cases in general - is how a lot of bugs get made. Take it as a lesson that you need to think more about the ways your code could conceivably break, not a pointless "gotcha".

[Sagekilla]

I'd say this sort of missed detail is exactly the sort of thing that really good programmers need to be good at spotting. Missing things like this - not this kind of math thing specifically, but weird special cases in general - is how a lot of bugs get made. Take it as a lesson that you need to think more about the ways your code could conceivably break, not a pointless "gotcha".

This. A million times this. It's easy to write an implementation that "just works." What's hard is getting it right.
Even harder is making sure it's completely safe no matter what you throw at it. That right there is what you need
when you're writing something that people will be using. You don't want it to have some weird corner case that
only happens rarely. It'll happen eventually, and when it does someone is going to be upset about it.

Better to code defensively and (when feasible) handle abnormal input. Even better is to make it impossible for
abnormal input to even reach your code.

These are exactly the sort of things that my professors watch out for when we code up implementations. What happens
when a user (accidentally or otherwise) inputs a bad value? Two of the best professors in my department stress test code
that you submit for assignments, and make sure that even in the extreme (but possible) cases, it works.

Example: We had to extend a basic calculator that was provided for us to include some extra features. The most valuable
of the choices was to implement a basic programming language by introducing state into the calculator. In this way, you could
trivially implement nested sums. If you did it wrong, you would've made the same mistake that was present in the first version
of Python, where the scope of variables was not properly defined.

It's a subtle bug to make, and one you only see in a handful of cases, but it's the worst mistake you could make since scope
semantics needs to be consistent, otherwise you may as well toss your computer out the window. Sure the mistake you made wasn't
nearly as complicated as that, but it's always good to instill these ideas early on. You learn it early and you'll become a much better
programmer for it.