Friday programming quiz
-
Not a very efficient approach (and hope I'm not cheating, there is only one semi-colon!) but here goes:
int closest = (from t in
from i in inputs
let avg = inputs.Average()
select new { Number = i, Delta = Math.Abs(i - avg) }
orderby t.Delta
select t.Number).FirstOrDefault(); -
int closest = inputs.OrderBy(i => Math.Abs(i - inputs.Average())).FirstOrDefault();
This is O(N²) as Average() gets called for every sort key that gets calculated. We can do better by storing the average in a variable. And we can use LINQ to introduce variables within an expression:
int closest = (from avg in new[] { inputs.Average() }
from i in inputs
orderby Math.Abs(i - avg)
select i).FirstOrDefault();This is O(N log N), but note that instead of sorting, we just need to find the minimum. Sadly, all the Min() methods compare the element itself, not just a key. However, we can build a suitable implementation using Aggregate():
int closest = (from avg in new[] { inputs.Average() }
select inputs.Aggregate((a, b) => Math.Abs(a - avg) < Math.Abs(b - avg) ? a : b)
).Single();This runs in linear time, and does pretty much the same as an implementation using a loop would do.
-
+5 Interesting challenge, even though far beyond my linquidity. Would like to take a course in Linq from you, because I feel "stymied" in my attempts to advance beyond kindergarten-level using it, assuming I am constitutionally linquidable, that is. best, Bill
"It is the mark of an educated mind to be able to entertain a thought without accepting it." Aristotle
Thanks; LINQ becomes a lot easier once you've used it for a few months, though; you probably just need more practice rather than a course. When I started out, it was confusing, but now it feels easier than loops. LINQ almost always performs worse than using regular loops, though; typically, a loop-based implementation is about 4 times faster when you have a ton of elements.
-
It remains sub-second time up until around 450 elements, so any test case you manually type should work fine. You think you can put together a solution that's O(N^2)?
This quizz is clearly O(N): computing the average is O(N); computing the absolute deviations from the average is O(N); selecting the smallest element is also O(N). I am not LINQ proficient, but I am pretty sure LINQ implements averaging in linear time, as it would do to build the deviations vector. Finding the position of the minimum of the vector is also O(N). I have nothing against high-level langages, but IMO solving such an easy problem with an O(N^3) hammer is not so welcome.
-
I promised a programming quiz a couple weeks ago, so here's one: Given an array of integers, select the integer in the array that is the closest to the average of all integers in the array; you must use nothing but a single LINQ lambda statement. If more than one integer is the closest, then any of the closest integers will do. For example, the following code should assign "14" to the int "closest":
int[] inputs = {1, 2, 3, 5, -1, 7, 145, -33, 22, 14};
int closest = // put a LINQ lambda expression hereIf you're up for actually figuring out your own solution, ignore the rest of this post. OR If you're lazy and unethical, feel free to copy-paste the sample solution in the small text below and claim it as your own. inputs.Where(x => Math.Abs(x - inputs.Average()) == inputs.Select(y => Math.Abs(y - inputs.Average())).Min()).First();
maybe I've found an alternative inputs.Select(x => new { OriginalValue = x, Distance = Math.Abs(x - inputs.Average()) }).OrderBy(a => a.Distance).First().OriginalValue;
-
Already replaced the avg with inputs.Average() before you posted. :) I triple-checked the post before posting it the first time, but still made that mistake; hopefully, nobody else sees it. As for the nested Lambda expression, it only has one semi-colon in it, so to me it counts as a single LINQ lambda statement. Maybe I should say "LINQ lambda statement with only one semi-colon at the end", but that would be confusing, and I'd get a ton of people asking for clarification. In any case, thank you for the feedback, and I'll be sure to refine my quiz-posting skills from all this. In the meantime, somebody should try and post their own solution; it's not much of a programming quiz without a few more solutions.
-
Although I don't know how the LINQ is resolved, it looks like it can't be worse than O(N^3). The Average() function costs N, the Min() costs N, the Where equals costs N, and the Select Average costs N * N. The worst nesting is N * N * N. Edited: it's at worst O(N^3).
I like Lambda expressions about as much as the help text for it is descriptive. (IE not much) I'll happily fail your quiz since I didn't sign up for your class and I'm really guessing at how this all works. In your example there were 10 items in the array. Your code:
inputs.Where(x => Math.Abs(x - inputs.Average()) == inputs.Select(y => Math.Abs(y - inputs.Average())).Min()).First();
inputs.Average() loops 10 times, summing all parties and dividing by 10 to provide the average value. y in Math.Abs(y - inputs.Average()) is obviously an interation of inputs values. How it became the iteration value is because it is in the "Select" method, I think. However this expression has to be calculated 100 times (10 y's times Average's 10 loops) to find the Min() value. Math.Abs(x - inputs.Average()) will start on that 100 loop too, so that's 10,000 calculations. (I think that C# isn't smart enough to realize all these function calls on the right side produce a constant so every time the left equation is run, the right equation is re-run.) Aah, but you've put in First() so it will short-circuit the loop when 14 is found. Since 14 is the last value, that's 10,000 loops. :-D 7 Functions executed: Where (1) Math.Abs(2) Average(2) Min(1) First(1) I am never impressed with cute code. Lambda is almost always cute. 10 lines of straightforward code are more valuable than 1 line of cute. The following code
int avg = inputs.Average(); int dif1, dif2, val1; val1 = inputs\[0\]; if (val1 > avg) dif1 = val1 - avg; else dif1 = avg - val1; foreach(int i in inputs) { if (i > avg) dif2 = i - avg; else dif2 = avg - i; if (dif2 < dif1) { dif1 = dif2; val1 = i; } }is more verbose, but even with archane variable names, to me, this seems easier to grasp without scratching your head and going: Now, what was that again???? When it is done, you have the average, the closest value to average, and the distance from average in three variables. However, show me the lambda code to do the same thing in 2*N loops my code uses instead of N^4 loops. OK, Math.Abs is easier to read, than if/else, but I think the code cost is about the same. Go ahead and use Abs, there's no advantage in using my 2 lines of code other than showing the function is fairly easy to replicate. Average is too valuable encapsulation to re-invent that wheel. With a 400 item array, 400^4 = 2
-
I promised a programming quiz a couple weeks ago, so here's one: Given an array of integers, select the integer in the array that is the closest to the average of all integers in the array; you must use nothing but a single LINQ lambda statement. If more than one integer is the closest, then any of the closest integers will do. For example, the following code should assign "14" to the int "closest":
int[] inputs = {1, 2, 3, 5, -1, 7, 145, -33, 22, 14};
int closest = // put a LINQ lambda expression hereIf you're up for actually figuring out your own solution, ignore the rest of this post. OR If you're lazy and unethical, feel free to copy-paste the sample solution in the small text below and claim it as your own. inputs.Where(x => Math.Abs(x - inputs.Average()) == inputs.Select(y => Math.Abs(y - inputs.Average())).Min()).First();
-
I like Lambda expressions about as much as the help text for it is descriptive. (IE not much) I'll happily fail your quiz since I didn't sign up for your class and I'm really guessing at how this all works. In your example there were 10 items in the array. Your code:
inputs.Where(x => Math.Abs(x - inputs.Average()) == inputs.Select(y => Math.Abs(y - inputs.Average())).Min()).First();
inputs.Average() loops 10 times, summing all parties and dividing by 10 to provide the average value. y in Math.Abs(y - inputs.Average()) is obviously an interation of inputs values. How it became the iteration value is because it is in the "Select" method, I think. However this expression has to be calculated 100 times (10 y's times Average's 10 loops) to find the Min() value. Math.Abs(x - inputs.Average()) will start on that 100 loop too, so that's 10,000 calculations. (I think that C# isn't smart enough to realize all these function calls on the right side produce a constant so every time the left equation is run, the right equation is re-run.) Aah, but you've put in First() so it will short-circuit the loop when 14 is found. Since 14 is the last value, that's 10,000 loops. :-D 7 Functions executed: Where (1) Math.Abs(2) Average(2) Min(1) First(1) I am never impressed with cute code. Lambda is almost always cute. 10 lines of straightforward code are more valuable than 1 line of cute. The following code
int avg = inputs.Average(); int dif1, dif2, val1; val1 = inputs\[0\]; if (val1 > avg) dif1 = val1 - avg; else dif1 = avg - val1; foreach(int i in inputs) { if (i > avg) dif2 = i - avg; else dif2 = avg - i; if (dif2 < dif1) { dif1 = dif2; val1 = i; } }is more verbose, but even with archane variable names, to me, this seems easier to grasp without scratching your head and going: Now, what was that again???? When it is done, you have the average, the closest value to average, and the distance from average in three variables. However, show me the lambda code to do the same thing in 2*N loops my code uses instead of N^4 loops. OK, Math.Abs is easier to read, than if/else, but I think the code cost is about the same. Go ahead and use Abs, there's no advantage in using my 2 lines of code other than showing the function is fairly easy to replicate. Average is too valuable encapsulation to re-invent that wheel. With a 400 item array, 400^4 = 2
Hear,hear! I may be an old f*rt but readability of code is paramount for maintenance. If terse and difficult to understand code is also less efficient then it fails twice. Having said that, the competition rules were set bt the creator and I'm just an aging SQL hack! :P
Life is like a s**t sandwich; the more bread you have, the less s**t you eat.
-
"We don't do homework!" AND "No programming questions in the Lounge..." ;P
Why can't I be applicable like John? - Me, April 2011
-----
Beidh ceol, caint agus craic againn - Seán Bán Breathnach
-----
Da mihi sis crustum Etruscum cum omnibus in eo!
-----
Just because a thing is new don’t mean that it’s better - Will Rogers, September 4, 1932Johnny: Good sentiment, but I've only seen one alternate solution and lots of comment ... so maybe it works as a lounge post!
Life is like a s**t sandwich; the more bread you have, the less s**t you eat.
-
Johnny: Good sentiment, but I've only seen one alternate solution and lots of comment ... so maybe it works as a lounge post!
Life is like a s**t sandwich; the more bread you have, the less s**t you eat.
I was just pulling your leg - I have no objections to your post... ;)
Why can't I be applicable like John? - Me, April 2011
-----
Beidh ceol, caint agus craic againn - Seán Bán Breathnach
-----
Da mihi sis crustum Etruscum cum omnibus in eo!
-----
Just because a thing is new don’t mean that it’s better - Will Rogers, September 4, 1932 -
I was just pulling your leg - I have no objections to your post... ;)
Why can't I be applicable like John? - Me, April 2011
-----
Beidh ceol, caint agus craic againn - Seán Bán Breathnach
-----
Da mihi sis crustum Etruscum cum omnibus in eo!
-----
Just because a thing is new don’t mean that it’s better - Will Rogers, September 4, 1932Not MY post Johnny and I was just :P
Life is like a s**t sandwich; the more bread you have, the less s**t you eat.
-
I promised a programming quiz a couple weeks ago, so here's one: Given an array of integers, select the integer in the array that is the closest to the average of all integers in the array; you must use nothing but a single LINQ lambda statement. If more than one integer is the closest, then any of the closest integers will do. For example, the following code should assign "14" to the int "closest":
int[] inputs = {1, 2, 3, 5, -1, 7, 145, -33, 22, 14};
int closest = // put a LINQ lambda expression hereIf you're up for actually figuring out your own solution, ignore the rest of this post. OR If you're lazy and unethical, feel free to copy-paste the sample solution in the small text below and claim it as your own. inputs.Where(x => Math.Abs(x - inputs.Average()) == inputs.Select(y => Math.Abs(y - inputs.Average())).Min()).First();
-
int closest = inputs.OrderBy(i => Math.Abs(i - inputs.Average())).FirstOrDefault();
This is O(N²) as Average() gets called for every sort key that gets calculated. We can do better by storing the average in a variable. And we can use LINQ to introduce variables within an expression:
int closest = (from avg in new[] { inputs.Average() }
from i in inputs
orderby Math.Abs(i - avg)
select i).FirstOrDefault();This is O(N log N), but note that instead of sorting, we just need to find the minimum. Sadly, all the Min() methods compare the element itself, not just a key. However, we can build a suitable implementation using Aggregate():
int closest = (from avg in new[] { inputs.Average() }
select inputs.Aggregate((a, b) => Math.Abs(a - avg) < Math.Abs(b - avg) ? a : b)
).Single();This runs in linear time, and does pretty much the same as an implementation using a loop would do.
Great answer. Can use let rather than that new []{} however: int closest = (from i in inputs
let avg = inputs.Average()
select inputs.Aggregate((a, b) => Math.Abs(a - avg) < Math.Abs(b - avg) ? a : b)
).Single();
That is actually wrong, but this works and average is called just once:int closest = (from c in "A" //just to get it to loop once let avg = inputs.Average() select inputs.Aggregate((a, b) => Math.Abs(a - avg) < Math.Abs(b - avg) ? a : b) ).Single();Does anyone know of a nicer way to cause just one loop in linq than my 'from c in "A"' trick?
-
Great answer. Can use let rather than that new []{} however: int closest = (from i in inputs
let avg = inputs.Average()
select inputs.Aggregate((a, b) => Math.Abs(a - avg) < Math.Abs(b - avg) ? a : b)
).Single();
That is actually wrong, but this works and average is called just once:int closest = (from c in "A" //just to get it to loop once let avg = inputs.Average() select inputs.Aggregate((a, b) => Math.Abs(a - avg) < Math.Abs(b - avg) ? a : b) ).Single();Does anyone know of a nicer way to cause just one loop in linq than my 'from c in "A"' trick?
This little change you suggest puts the perfomance back to O(N^2) and not linear. inputs.Average() gets called for each element in the inputs array. Daniel's solution is the correct one. --- Adar Wesley
-
I promised a programming quiz a couple weeks ago, so here's one: Given an array of integers, select the integer in the array that is the closest to the average of all integers in the array; you must use nothing but a single LINQ lambda statement. If more than one integer is the closest, then any of the closest integers will do. For example, the following code should assign "14" to the int "closest":
int[] inputs = {1, 2, 3, 5, -1, 7, 145, -33, 22, 14};
int closest = // put a LINQ lambda expression hereIf you're up for actually figuring out your own solution, ignore the rest of this post. OR If you're lazy and unethical, feel free to copy-paste the sample solution in the small text below and claim it as your own. inputs.Where(x => Math.Abs(x - inputs.Average()) == inputs.Select(y => Math.Abs(y - inputs.Average())).Min()).First();
Here's a good couple of questions to give programmers you're thinking of hiring -- if they can answer these, it's a good bet you've found yourself someone who can think a bit...: 1. In C, what does this do (and no, it doesn't matter what types the variables are as long as they're the same type)? a^=b^=a^=b; 2. In SQL, given the following tables (relationships being obvious), write a query which returns the names of the people who play *every* sport: People PersonID int PersonName varchar(50) Sports SportID int SportName varchar(50) PeopleSports PersonID int SportID int
-
I promised a programming quiz a couple weeks ago, so here's one: Given an array of integers, select the integer in the array that is the closest to the average of all integers in the array; you must use nothing but a single LINQ lambda statement. If more than one integer is the closest, then any of the closest integers will do. For example, the following code should assign "14" to the int "closest":
int[] inputs = {1, 2, 3, 5, -1, 7, 145, -33, 22, 14};
int closest = // put a LINQ lambda expression hereIf you're up for actually figuring out your own solution, ignore the rest of this post. OR If you're lazy and unethical, feel free to copy-paste the sample solution in the small text below and claim it as your own. inputs.Where(x => Math.Abs(x - inputs.Average()) == inputs.Select(y => Math.Abs(y - inputs.Average())).Min()).First();
Could be simplified to:
int closest = inputs.First(x => Math.Abs(x - inputs.Average()) == inputs.Min(y => Math.Abs(y - inputs.Average())));
but I don't like to perform the same calculation twice, so I'd be more comfortable with:
double avg = inputs.Average();
int closest = inputs.First(x => Math.Abs(x - avg) == inputs.Min(y => Math.Abs(y - avg))); -
I promised a programming quiz a couple weeks ago, so here's one: Given an array of integers, select the integer in the array that is the closest to the average of all integers in the array; you must use nothing but a single LINQ lambda statement. If more than one integer is the closest, then any of the closest integers will do. For example, the following code should assign "14" to the int "closest":
int[] inputs = {1, 2, 3, 5, -1, 7, 145, -33, 22, 14};
int closest = // put a LINQ lambda expression hereIf you're up for actually figuring out your own solution, ignore the rest of this post. OR If you're lazy and unethical, feel free to copy-paste the sample solution in the small text below and claim it as your own. inputs.Where(x => Math.Abs(x - inputs.Average()) == inputs.Select(y => Math.Abs(y - inputs.Average())).Min()).First();
int closest = inputs.OrderBy(x => Math.Abs(inputs.Average() - x)).First();
-
I promised a programming quiz a couple weeks ago, so here's one: Given an array of integers, select the integer in the array that is the closest to the average of all integers in the array; you must use nothing but a single LINQ lambda statement. If more than one integer is the closest, then any of the closest integers will do. For example, the following code should assign "14" to the int "closest":
int[] inputs = {1, 2, 3, 5, -1, 7, 145, -33, 22, 14};
int closest = // put a LINQ lambda expression hereIf you're up for actually figuring out your own solution, ignore the rest of this post. OR If you're lazy and unethical, feel free to copy-paste the sample solution in the small text below and claim it as your own. inputs.Where(x => Math.Abs(x - inputs.Average()) == inputs.Select(y => Math.Abs(y - inputs.Average())).Min()).First();
Here are two alternate implementations. Two might be cheating a bit, but it satisfies the "only one semi-colon" rule. :-) As others have pointed out, the answer you gave is pretty slow. To those who say LINQ can't be fast, algorithm choice makes a huge difference. I ran tests for the three implementations over the original input set, the values 1-99 and -499 to 499. To help average out timing inconsistencies, the tests were run 10,000 times. Values are in ms.
Quiz inputs
100 items
1000 items
Quiz solution
284
84,573
Unknown. I stopped it after about 6 hours.
Alternate 1
80
1,945
167,099
Alternate 2
75
479
7,246
Alternate 1
int[] inputs = {1, 2, 3, 5, -1, 7, 145, -33, 22, 14};
int closest = inputs
.Select(i => new {val = i, dist = Math.Abs(i - inputs.Average())})
.OrderBy(a => a.dist)
.First().val;Alternate 2
int[] inputs = {1, 2, 3, 5, -1, 7, 145, -33, 22, 14};
int closest = (from x in new []{1}
let avg = inputs.Average()
from i in inputs
select new { val = i, dist = Math.Abs(i-avg)})
.OrderBy(a => a.dist)
.First().val -
Not a very efficient approach (and hope I'm not cheating, there is only one semi-colon!) but here goes:
int closest = (from t in
from i in inputs
let avg = inputs.Average()
select new { Number = i, Delta = Math.Abs(i - avg) }
orderby t.Delta
select t.Number).FirstOrDefault();I'm not familiar with linq nor lambda, but I really like this solution over the original suggested one. Am I right that t is an implied class that contains 2 fields? 1. It doesn't take work to understand the logic. 2. Rather than N^4 loops, this has N^2. (Like you said, not efficient, but much better than the original.)