 Feature Articles
 CodeSOD
 Error'd
 Forums

Other Articles
 Random Article
 Other Series
 Alex's Soapbox
 Announcements
 Best of…
 Best of Email
 Best of the Sidebar
 Bring Your Own Code
 Coded Smorgasbord
 Mandatory Fun Day
 Off Topic
 Representative Line
 News Roundup
 Editor's Soapbox
 Software on the Rocks
 Souvenir Potpourri
 Sponsor Post
 Tales from the Interview
 The Daily WTF: Live
 Virtudyne
Admin
This particular developer, who left a long time ago and is now making more money than we do (we haven't quite caught up yet with Western European standards), now is referred to as "he who shall not be mentioned".
@1: He grabbed an algorythm off the internet and modified it, without actually understanding it. @2: No, that is actually correct. Well, it should have been char**, but at the time we had fewer than 20,000 contract customers. @3: See #1. @4: See #1. @5: That comment is actually quite unique. Usually, there are none, and there's just confusing code. He probably couldn't be bother to remove it. @6: And it really should have used strcmp()... @7: If it were just the indents... @8: But atof() is used for string comparison, because the strings happen to consist of 15 digits. @9: Just a reference, this is C after all, and 20,000 postpaid mobile phone customers should be enough for anybody. :) @10: Good point. Since the code actually worked, I presume it was, but then again...
Read my previous comments on this article for some more gems, like a goto statement in C code. :)
Admin
I also think 9/10 is a correct answer. However I think it's more complicated. Each day chances to get a lemon are different: on the first day it's 9/10. On the second day it's 89/99 or 90/99 depending which flavor was picked on the first day. And so on. This is called permutations with repetition.
And you guys using Excel  how did you get this 0.(81)? I don't get it at all. Also I don't think that 10x90 table is enough to make a brute force in this case.
Anyone feel free to correct me if I'm wrong, last time I had maths at school over 10 years ago!
Admin
On the first day, there is 9/10 chance of picking a lemon. 1/10 chance of picking a cherry. But you failed to note the bit where picking a cherry gives a second chance. And on that second chance (all the drops are back in the bag), he again has a 9/10 chance of picking a lemon anyway.
So, to eat a cherry on the first day requires a 1/10 * 1/10 chance. There is 99% chance of picking a lemon, not 90%. This is why the lemons get consumed much faster than you expect.
(FWIW, I left school much longer ago than you.)
Admin
Admin
Addendum (20081223 10:32): Stupid me! I knew I should have reread the actual problem... Well who looks like a fool now?
Admin
I was somehow misunderstood, defended and then argued against by the opposite result in the same post by the same person.
At any rate, the principal of the Halloween Candy Corn Law clearly states that the least desirable candy will be left when the bottom of the sack is reached. In George's case, this is cherry. Hence, there's no possible way a delicious lemon treat is waiting for him as he polishes off the bag of goodness. QED.
Admin
Since the original question indicates that George takes another candy, I.E. a different individual sweet than the one involved in the first trial, then cherry flavoured sweets will be elliminated until there is only one left, at which point the second trial will always evaluate as "lemon".
As such the last sweet in the bag would be a charry flavoured one.
If the candidates for the second trial selection included the cherry flavoured specemin from the first trial, then things get markedly more complicated! However, even when the proportion reaches parity, lemon will still be eliminated at least three times more often than cherry. cherry will only be eliminated more often when they outnumber Lemon by 2.41 to 1. This would hint that it won't happen until there are about four lemons left!
Getting to the very end of my lunchbreak here I'm going to say "meh, it probably tends to 1".
Meh, it probably tends to 1.
The true WTF is that the guy who used excel didn't use matlab instead!
Admin
Admin
Apart from all the other problems with the binsearch algorithm (eg atof), I'm not really sure what the issue is with the recursion.
It's a binary search! So for zillions of entries to search it will only have a depth of a few. It may well not have needed further optimisation. If it's only search 20,000 entries, it will have a depth of 14. That'll hardly be noticeable.
It's not necessarily a case of 'for someone who doesn't know about optimisation it's OK'. It could be more like 'for something that doesn't need optimisation it's reasonable'
As for the 4000>40,000 thing. The only issue I can see with that is that it crashes with a buffer overflow (rather than exiting cleanly) when it reaches 40,001 entries. Programmers are always setting arbitrary limits, eg 'size of memory' or '65535' or '4294967295' or whatever. 40,000 is just another example of that.
Without more information we don't know if 40,000 is a reasonable limit. Each item may be 40kB, or they may just have 200 new entries a year or whatever.
Dynamic allocation won't solve the issue, just move it a bit further away. At some point virtual memory space will run out, and that will be less deterministic than a fixed maximum size, so harder to deal with.
Howver, it DOES need a clean termination (with a sensible error message) if it goes over the limit, rather than just waiting for it to crash.
Admin
What kind of crappy candy company sells lemon candies that contain 90 lemon and 10 cherry flavor?
I'm not sure if I could trust a company selling lemon candy that seems to always drop 10 cherry candies I didn't like into my bag of lemon candy...
Also, why doesn't he just buy a bag with 100 lemon candies if you don't like cherry don't buy them.
Admin
I'd love to understand the Haskell version, especially the "optimized" code. Can anyone shed some light on the stuff? Especially some operators aren't clear to me and the whole ps stuff..
I'm trying to get into functional stuff, but I haven't looked at Haskell once and would probably take quite some time to get it on my own.
Any takers?
Admin
It all boils down to that He Who Shall Not Be Mentioned just didn't know what he was doing, or he just didn't care, and there was nobody to check his code.
Nowadays, we run source code analysis tools like PMD on the Subversion repository, so things have changed a bit since then.
Admin
That's not a good point at all.
I can't fathom why people who are worried about the execution time and stack issues of a binary search algorithm done recursively rather than iteratively on a data set that's only 20,000 records (max of 15 recursive calls) are implying that he should check to see if the array is sorted. Sure lets throw a linear scan of the array in there to see if it's sorted before we do our binary search, that'll be great for performance!
A binary search algorithm should not care if the array is sorted, that concern should be left to the person calling the algorithm. If you are stupid enough call binsearch on an unsorted array you deserve to not find your result.
I'm not defending this guys code, anyone with a brain can see that it's poorly designed and written, but some people just pick the stupidest stuff to complain about.
Admin
It all boils down to that He Who Shall Not Be Mentioned just didn't know what he was doing, or he just didn't care, and there was nobody to check his code.
Nowadays, we run source code analysis tools like PMD on the Subversion repository, so things have changed a bit since then.
Admin
Well, not stupid. He simply didn't care.
Admin
Objection, facts not in evidence. The OP indicates that, "But if the candy he chose is cherry flavored, he puts it back in the bag and then randomly picks a candy out of the bag and eats it regardless of the flavor."
If he puts it back in the bag, then it's possible he can indeed select the same cherry piece twice.
Admin
Sean, I think you misunderstand. One person raised the worry about the data being sorted. Given reasonable coding standards, it's a reasonable assumption.
What most people are complaining about with the recursion is that it is often better practice* to write such searches as a loop rather than as an recursive function. That's what they mean by "iterative" as opposed to "recursive".
*These habits are often formed when the compiler won't optimize the code to a loop anyway. The concerns are function overhead in runtime and RAM usage (for the iterative people) vs. ease of understanding (for the recursive people).
Admin
Sean, I think you misunderstand. One person raised the worry about the data being sorted. Given reasonable coding standards, it's a reasonable assumption.
What most people are complaining about with the recursion is that it is often better practice* to write such searches as a loop rather than as an recursive function. That's what they mean by "iterative" as opposed to "recursive".
*These habits are often formed when the compiler won't optimize the code to a loop anyway. The concerns are function overhead in runtime and RAM usage (for the iterative people) vs. ease of understanding (for the recursive people).
Admin
Sean, I think you misunderstand. One person raised the worry about the data being sorted. Given reasonable coding standards, it's a reasonable assumption.
What most people are complaining about with the recursion is that it is often better practice* to write such searches as a loop rather than as an recursive function. That's what they mean by "iterative" as opposed to "recursive".
*These habits are often formed when the compiler won't optimize the code to a loop anyway. The concerns are function overhead in runtime and RAM usage (for the iterative people) vs. ease of understanding (for the recursive people).
Admin
You sir are incorrect. Don't feel bad, you fell for a common mistake. Read up on Gambler's fallacy. The odds of picking a lemon or cherry do not change on the second pick. Think of it this way, on a 6 sided die, what are your chances of rolling a 1? Exactly 1 in 6. Now say you roll a 1, now you roll again, what are your chances of rolling a 1. Once again 1 in 6, even though the odds of rolling two 1's in a row are less, each rolls odds are figured on its own and not influenced by what has gone before it.
See downfall gets it. If there are 90% lemons, then there will ve a 90% chance that a lemon will be last. No programming needed.
Admin
Cumulative probability. Look into it.
Admin
I see what you've done there. Well played, sir. Well played.
Admin
I love all these people assuming that all compilers will always perform tail call optimisation.
Most mainstream compilers only perform it in very limited circumstances, if at all. It is NEVER guaranteed in any mainstream compiler. And it is guaranteed NOT to happen in cases like the code in the WTF, which doesn't contain any tail calls ...
Admin
Admin
The thing I find the craziest about the candy problem is that there is...
a 1763 in 753249978808893720 chance of having 53 lemons and no cherries,
a 1763 in 501668471336346545 chance of having 52 lemons and no cherries,
a 1763 in 334885997323933770 chance of having 51 lemons and no cherries, and
a 1763 in 223989322800270456 chance of having 50 lemons and no cherries!
Isn't that wild?!
Admin
Ummm, that's what "realloc()" is for...
if (size>capacity) { capacity *= 2; foo = realloc(foo,capacity); }
Admin
Here is my code:
it runs in 171 ms how do you guys are getting 26 ms?
Admin
[The previous poster]
The general expression is very easy to derive provided you know the hypergeometric distribution.
Admin
I still have to differ. Given 90% lemon, 10% red, the chances of any single candy being a lemon is 90%. It doesn't matter if you pick one or 99, the single candy has a 90% chance of being lemon. The trick here is in the way the picking was described, Since the original candy was returned to the bag before the next candy is picked, it has no affect on the resulting pick. Now if the second pick was made before return the first pick to the bag, then the odds of the last one being a lemon would be less than 90%. For a simple example, say there are two candies left, one lemon one cherry, what are the odds the last one will be lemon, 50%. Now pick one and get a cherry, out it back, now what are the odds the last will be a lemon, once again 50%. Now pick one and get a cherry, hold it and pick again, what are your odds, this time 100%. The odds only change when you hold the first pick until after the second pick is made. Returning it brings the odds back in line with the original count.
Admin
Consider the case where there are exactly two candies left, one lemon, one cherry. The possible draws are:
lemon (50% odds) cherry (50% odds)
But then you put the cherry back and redraw. So half of the time you make two draws and half of that time it is also a lemon. Thus, you draw
lemon (50% odds) cherry then lemon (25% odds) cherry then cherry (25% odds)
Thus, when you have precisely one lemon candy and one cherry candy left, you will eat the lemon candy 75% of the time and the cherry candy 25% of the time and the final piece will thus be cherry 75% of the time and lemon 25% of the time.
Admin
The world is so simple!
And the year is 365.000 days long!!
And pi is 3.0000!!!
And the probability of any event is the same as the probability of any other event!!!!
Admin
Runs in 2ms on my six year old thing. Of course working out the formula leads to a faster algorithm :)
Admin
Never mind, python's 3 interpreter takes 171 ms to startup.
Admin
Gamblers Fallacy, look it up.
The previous draw has no affect on the next draw. Given two pieces, your chances are always 50% to draw a chosen peice, regardless of what you drew the last time.
Admin
Here it is with the percentages written out more explicitly:
Draw 1:
lemon (50% odds) cherry (50% odds)
Draw 2 if Lemon in Draw 1:
lemon (100% odds) cherry (0% odds)
Draw 2 if Cherry in Draw 1:
lemon (50% odds) cherry (50% odds) (same odds as Draw 1, see Gamblers Fallacy)
Overall odds over both draws:
lemon (50% * 100% + 50% * 50% = 75%) cherry (50% * 0% + 50% * 50% = 25%)
hth, Douglas
Admin
Admin
If you are trolling, you aren't funny. If you aren't trolling, you are stupid (and damn arrogant in not even bothering to check to see if you are wrong)
Admin
Admin
The formula was presented before, and I've checked the recurrence relation, but how would you "work out" the formula given the problem description?
Admin
Admin
Thanks! for writing the rant I would otherwise have written. It seems deeply ingrained in the imperative mindset that recursion = recomputing intermediate results = inefficient. There's nothing wrong with programming in imperative languages to accomplish a goal. I do it all the time. But it's rather sad that so many programmers are unable to fathom even the possibility that nonimperative and loopfree yet efficient solutions exist. Unfortunately, eric76 still doesn't get it.
Admin
So in other words, you found a way to write a slow recursive function, and therefore there are no ways to write fast recursive functions.
The point that you completely missed is that "keeping a table" (or memoization as it is called more generally) has nothing to do with recursion or looping. In fact, you totally confuse control flow (recursion vs. looping) with data flow (memoization). In fact, because in Haskell expression evaluation is nonstrict and free of sideeffects, runtime control flow is determined by data dependencies and compiler whims and mostly irrelevant.
Here's another, timeless and simpler example of naive vs. nonnaive use of recursion:
Admin
Oh, gimme a break. Without knowing what the records are, what sort of activity causes them to expand, there may or may not be justification for using a dynamic scheme or not.
Since that data isn't given, this may qualify as a WtF or not.
If the records in question use a keycode specification that can only handle 3999 records, max, then fixed 4000 records would be a reasonable spec. That doesn't seem to be the case, here, but that doesn't mean that there aren't constraints on the record count which makes a presumed maximum count a reasonable notion.
Sometimes people just love to complicate the hell out of things (and proper deallocation of dynamic records and GC is always an extra step of complication  even when it's handled automagically by the system in the background) for the sake of a foolish consistency.
Then people wonder how code gets so ridiculously bloated and everyone needs to have a quadcore @ 3Ghz with 4 gigs of RAM.
"I see no reason why any microcomputer, anywhere, should ever require more than 16 mb of RAM"  Bill Gates, ca. 1982
Sure, 16mb is a bit low for a modern graphical OS, but the whole "just throw more hardware at it" notion breaks down at some point.
Sooner or later you bozos are going to have to actually pay some attention to code efficiency.
Admin
Another point which may reinforce the prejudice against recursion is that often a naive (and horribly inefficient) recursion is obvious while an iterative solution is not easy to see and once seen the avoidance of the worst inefficiencies is obvious, as for example in the candy problem.
And that's why tail recursion is mostly a red herring in Haskell land.Not really incredibly fast, you should use foldl' and a strict pair, otherwise you'll still build an enormous thunk and get a stack overflow for large arguments (~500,000  1,000,000).
But isn't the official definition of the Fibonacci sequence
?Admin
The sad part of the gamblers fallacy is that even knowing my odds were no better (or worse) then the last few times I went, I still went to a casino this week and lost another $500 on the penny slots.
Admin
In case anybody wants it, naive Mathematica code for the problem (with memoization):
p[0, y] = 0; p[x, 0] = 1; px[x, y] := x/(x + y) py[x, y] := y/(x + y) p[x, y] := p[x, y] = (py[x, y] + 1) px[x, y] p[x  1, y] + py[x, y]^2 p[x, y  1] p[90, 10]
result:
9/110
(in about 40 milliseconds on a slow machine)
Admin
Admin
Yeah, it should be obvious that both formulae are the same formula refactored.
Admin
buy prednisone without prescription paypal: http://prednisone1st.store/# prednisone acetate