Friday programming quiz
-
jesarg wrote:
it's at worst O(N^3).
See you in a few years when a billion iterations finish ;p
-
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();
+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
-
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();
"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, 1932 -
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();
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 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();
Won't work when
inputsis of zero length. :) /raviMy new year resolution: 2048 x 1536 Home | Articles | My .NET bits | Freeware ravib(at)ravib(dot)com
-
+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
BillWoodruff wrote:
linquidity
Interesting term... I think I'll adopt that! :-D
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 -
Won't work when
inputsis of zero length. :) /raviMy new year resolution: 2048 x 1536 Home | Articles | My .NET bits | Freeware ravib(at)ravib(dot)com
-
:thumbsup: /ravi
My new year resolution: 2048 x 1536 Home | Articles | My .NET bits | Freeware ravib(at)ravib(dot)com
-
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();
jesarg wrote:
you must use nothing but a single LINQ lambda statement
Frack that; I thought you said this was a programming quiz.
-
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.
-
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.