Patrick Steele's .NET Blog

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.

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<int, int> answer = (number) => {

 int c = 1;

 Func<int> scaler = () => (c*=10) / 10;

 Func<int, int, int> recurse = null;

 Func<int, int, int> partialAnswer = (n, scale) =>

   (n < 4 ? 0 : (n < 5 ? 1 : scale))

   + n * (scale==1 ? 0 : recurse(10, scale/10));

 recurse = partialAnswer;

 return

   (from digit in number.ToString().Reverse()

   select new { digit = ((int)digit)-(int)'0', scale = scaler.Invoke() })

   .Sum(v => partialAnswer(v.digit, v.scale));

};

And at last, without recursion:

Func<int, int> answer = (number) => {

 int c = 1;

 Func<int> scaler = () => (c*=10) / 10;

 Func<int, int, int> partialAnswer = (n, scale) =>

   (n < 4 ? 0 : (n < 5 ? 1 : scale))

   + n * (int) Math.Log10(scale) * scale / 10;

 return

   (from digit in number.ToString().Reverse()

   select new { digit = ((int)digit)-(int)'0', scale = scaler.Invoke() })

   .Sum(v => partialAnswer(v.digit, v.scale));

};

More clear version using Zip from .NET 4:

Func<int, int> answer = (number) => {

 Func<int, int, int> partialAnswer = (n, scale) =>

  (n < 4 ? 0 : (n < 5 ? 1 : scale))

  + n * (int) Math.Log10(scale) * scale / 10;

 return

   number.ToString()

   .Select(c => ((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));

};

Pingback from  Twitter Trackbacks for                 LINQ and Homework - Patrick Steele's .NET Blog         [asp.net]        on Topsy.com

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 < 4, so no "extras"

2) 352 / 100 = 3 r52

   r52 > 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?