LINQ and Homework

13 Comments

• That is cool. I did a similar problem solving a coin problem with my son. couple lines of code then blame. Then I thought, "How fast is Linq" for real world solutions where you may have to do this 100's of time. To my suprise a simple for loop was 20 times faster!!!! I love Linq but I certainly understand that nothing is for free.
  

• Nice, but I hope your daughter did not submit the output of your expression.
  
  You're counting the pages that have the digit 4 as their page number.
  
  But page 44 for instance has two 4's...
  
  Enumerable.Range(1,352).Sum(p => p.ToString().Count(c => c == '4'))
  
  Is uglier but accounts for 44, 144, 244 and 344 (75 total)
  
  

• You don't count all 4s in numbers like 144, 244. The correct version is:
  
  Enumerable.Range(1, 352).Sum(p => p.ToString().ToCharArray().Count(it => it == '4'))
  
  which gives you 75.
  
  

• Unless I misunderstood the question, .Contains does not take into account repeating digits like 44.
  
  var answer = Enumerable.Range(1, 352).Sum((p) => p.ToString().Split('4').Length - 1);
  
  answer = 75
  

• Could you also give a few words about the mathematical way to do this please? I am curious.
  
  

• rajbk/liggett78/Yann,
  
  Good catch!! Totally missed that one. A great thinking question.
  

• Joining rajnk/liggett78/Yann, but apparently - as I just discovered, I'm not the first one :)
  
  My answer is:
  
  (from number in Enumerable.Range(1, 352)
  let regex = new Regex("4")
  select regex.Matches(number.ToString()).Count).Sum()
  

• Mathematical answer:
  
  Func answer = (number) => {
  int c = 1;
  Func scaler = () => (c*=10) / 10;
  Func recurse = null;
  Func partialAnswer = (n, scale) =>
  (n < 4 ? 0 : (n partialAnswer(v.digit, v.scale));
  };
  

• And at last, without recursion:
  
  Func answer = (number) => {
  int c = 1;
  Func scaler = () => (c*=10) / 10;
  Func partialAnswer = (n, scale) =>
  (n < 4 ? 0 : (n partialAnswer(v.digit, v.scale));
  };
  

• More clear version using Zip from .NET 4:
  
  Func answer = (number) => {
  Func partialAnswer = (n, scale) =>
  (n < 4 ? 0 : (n ((int)c) - (int)'0')
  .Reverse()
  .Zip(Enumerable.Range(0, 10),
  (l,r) => new { digit = l, scale = (int) Math.Pow(10,r) })
  .Sum(p => partialAnswer(p.digit, p.scale));
  };
  

• Regarding a "mathematical" solution, I think a little bit of logic and reasoning can be used here.
  
  The problem can be solved in two parts.
  
  1) How many times will 4 appear in the "ones" place?
  2) How many times will 4 appear in the "tens" place?
  
  1) 352 / 10 = 35 r2 (35 times in the ones place)
  Note: r2 49 so we include 340-349
  so: 3x10 + 10 extra
  
  1) 35
  2) 40
  Total: 75
  
  If N = 345
  1) 34 r5 -> 34 + 1 = 35
  2) 3 r45 -> 30 + 6 = 36
  note: 6 gained from 40-45
  Total: 71
  
  If N = 429
  1) 42 r9 -> 42x1 + 1 = 43
  2) 4 r29 -> 4x10 + 0 = 40
  3) 0 r429 -> 0x100 + 30 = 30
  Total = 113
  
  Summary of the "math":
  ones: N = q1 x 10 + r1
  n1 = q1
  if r1 >= 4, then add one more (n1++)
  tens: N = q2 x 100 + r2
  where r2 = (a2 x 10 + b2)
  n2 = q2 x 10
  if a2 > 4, then add 10 (n2 += 10)
  if a2 = 4, then add b2+1 (n2 += b2+1)
  hundreds: N = q3 x 1000 + r3
  where r3 = (a3 x 100 + b3)
  n3 = q3 x 100
  if a3 > 4, then add 100 (n3 += 100)
  if a3 = 4, then add b3+1 (n3 += b3+1)
  pattern continues from here...
  
  Total = n1 + n2 + n3 + ...
  
  one last example:
  If N = 27348
  1) 2734x10 + 8 -> 2734x1 + 1 = 2735
  2) 273x100 + 4x10 + 8 -> 273x10 + 9 = 2739
  3) 27x1000 + 3x100 + 48 -> 27x100 + 0 = 2700
  4) 2x10000 + 7x1000 + 348 -> 2x1000 + 1000 = 3000
  5) 0x100000 + 2x10000 + 7348 -> 0x10000 + 0 = 0
  Total = 11174
  
  
  My mathematical code solution:
  var totalFours = 0;
  
  //tens
  var remainder = pageCount % 10;
  var quotient = pageCount / 10;
  totalFours += quotient;
  if( remainder >= 4 )
  totalFours++;
  
  //all other places:
  var remainder2 = 0;
  var place = 1;
  while( quotient > 0)
  {
  remainder2 = place * remainder + remainder2;
  remainder = quotient % 10;
  quotient = quotient / 10;
  place *= 10;
  
  totalFours += quotient * place;
  if( remainder > 4 )
  totalFours += place;
  else if( remainder == 4 )
  totalFours += remainder2 + 1;
  }
  Console.WriteLine(totalFours);
  
  

• A version of the code that merges the "trivial" ones place with the loop that covers all of the other places.
  
  var pageCount = 27348;
  var totalFours = 0;
  var remainder = 0;
  var remainder2 = 0;
  var place = 1;
  var quotient = pageCount;
  while( quotient > 0 )
  {
  remainder = quotient % 10;
  quotient = quotient / 10;
  
  totalFours += quotient * place;
  if( remainder > 4 )
  totalFours += place;
  else if( remainder == 4 )
  totalFours += remainder2 + 1;
  
  remainder2 = place * remainder + remainder2;
  place *= 10;
  }
  Console.WriteLine( totalFours );
  
  Cheers.
  

• Patrick, I bet you never thought your daughter's homework assignment would be this interesting?