Quantcast

Maximum PC
It is currently Tue May 21, 2013 7:00 am

View unanswered posts | View active topics


Board index » OS/Software/Programming » Programmers' Paradise

All times are UTC - 8 hours




Post new topic Reply to topic  Page 1 of 3
  [ 52 posts ]  Go to page 1, 2, 3  Next
  Print view Previous topic | Next topic 
Author Message
CrashTECH
 Post subject: Programmers can't program...
PostPosted: Tue Jul 13, 2010 10:52 am 
SON OF A GUN
SON OF A GUN
User avatar

Joined: Mon Nov 01, 2004 5:41 am
Posts: 11602
Old article, but still! I wrote the FizzBuzz app in about two minutes, including waiting for VS 2010 to open! I find it crazy that most CS graduates can't do it. Even more so that "Senior Programers" take 10-15 minutes? I should be paid more...

http://tinyurl.com/yzdlqx6
Top
  Profile  
 
Jipstyle
 Post subject:
PostPosted: Tue Jul 13, 2010 12:54 pm 
Java Junkie
Java Junkie
User avatar

Joined: Mon Jun 14, 2004 10:23 am
Posts: 24150
Location: Granite Heaven
Have you seen some of the 'solutions' offered in the comments?

I know it is just a little test but still .. if I'm offering my code up to thousands of readers, I think I'd try to make it a bit more optimal than:

Code:
for (int x = 1; x < 100; x++) {
   If ((x mod 3 == 0) && (x mod 5 == 0)) then output ("FizzBuzz")
   Else if ( x mod 5 == 0) then output "Fizz")
   Else if ( x mod 3 == 0) then output "Buzz")
endfor


That is just ugly

How about:
Code:
int three = 0
int five = 0
for (int x = 1; x < 100; x++) {
   three++; five++;
   if (three ==3) {
      if (five == 5) {
         output "fizzbuzz"
         three=0; five=0;
      else {
         output "fizz"
      endif
   else if (five == 5) {
      output "buzz"
      five=0
   endif
endfor


/me waits for someone to point out that my solution uses more lines of code and is therefore less efficient than the version that i'm criticizing. :P

Note: I'm assuming that the mod calculation is more expensive than simply tracking two ints. This is not always the case and the code could be made more obvious by using the modulus operation instead. It is the logic that I'm trying to improve on rather than the arithmetic. Doing 4 comparisons in every loop is a waste when most iterations of the loop require only two.
Top
  Profile  
 
CrashTECH
 Post subject:
PostPosted: Tue Jul 13, 2010 6:38 pm 
SON OF A GUN
SON OF A GUN
User avatar

Joined: Mon Nov 01, 2004 5:41 am
Posts: 11602
When I wrote it, it was the simple for loop...

We both know that fewer lines isn't necessarily better... we just had that discussion :)

But, I wonder what the difference is. I am not sure there is any really good information on it... or that it is measurable. I suppose it would depend how it (mod) is implemented. I honestly can't say that I know the algorithm for it.

Resources are so trivial though, but I would guess your solution uses a tiny bit more memory and mine and the criticized (thanks, ass :) ) one a few cpu cycles?
Top
  Profile  
 
Jipstyle
 Post subject:
PostPosted: Tue Jul 13, 2010 8:14 pm 
Java Junkie
Java Junkie
User avatar

Joined: Mon Jun 14, 2004 10:23 am
Posts: 24150
Location: Granite Heaven
Yeah .. mine runs through 2 comparisons on average and 3 at most, whereas the other runs through 4 on average, with occasional runs of 3 or 4.

Of course, with x = 100, it is a pointless exercise .. but I prefer to think that x always = n.
Top
  Profile  
 
CrashTECH
 Post subject:
PostPosted: Wed Jul 14, 2010 5:29 am 
SON OF A GUN
SON OF A GUN
User avatar

Joined: Mon Nov 01, 2004 5:41 am
Posts: 11602
The libraries probably aren't needed, but are the default....

The Read Line is just to wait for me to hit enter to exit.

Code:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace FizzBuzz
{
    class Program
    {
        static void Main(string[] args)
        {
            for (int i = 1; i <= 100; i++)
            {
                if ((i % 5 == 0) && (i % 3 == 0))
                {
                    Console.WriteLine("FizzBuzz");
                }
                else if (i % 5 == 0)
                {
                    Console.WriteLine("Buzz");
                }
                else if (i % 3 == 0)
                {
                    Console.WriteLine("Fizz");
                }
                else
                {
                    Console.WriteLine(i);
                }
            }

            Console.ReadLine();
        }
    }
}


I also just thought it would make a difference if you did i%5 or i%3 first... Because if the first conditional in the if is false, it doesn't evaluate the other.
Top
  Profile  
 
CrashTECH
 Post subject:
PostPosted: Wed Jul 14, 2010 5:31 am 
SON OF A GUN
SON OF A GUN
User avatar

Joined: Mon Nov 01, 2004 5:41 am
Posts: 11602
Wonder about this small change?

Code:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace FizzBuzz
{
    class Program
    {
        static void Main(string[] args)
        {
            for (int i = 1; i <= 100; i++)
            {
                if (i % 5 == 0)
                {
                    if (i % 3 == 0)
                    {
                        Console.WriteLine("FizzBuzz");
                    }
                    else
                    {
                        Console.WriteLine("Buzz");
                    }
                }
                else if (i % 3 == 0)
                {
                    Console.WriteLine("Fizz");
                }
                else
                {
                    Console.WriteLine(i);
                }
            }

            Console.ReadLine();
        }
    }
}
Top
  Profile  
 
Jipstyle
 Post subject:
PostPosted: Wed Jul 14, 2010 8:34 am 
Java Junkie
Java Junkie
User avatar

Joined: Mon Jun 14, 2004 10:23 am
Posts: 24150
Location: Granite Heaven
The second is better .. you're only checking to see if i mod 5 is true once.

I can't see a performance increase if you check mod 5 or [/i]mod 3[/i] first .. you have to check both conditions regardless. So long as you check each only once, you're optimal.

In fact, I should have thrown a break in my for-loop to avoid checking i mod 5 twice.

Aaaah .. trivial programming to avoid doing work. Fun. :D
Top
  Profile  
 
Gadget
 Post subject: Re: Programmers can't program...
PostPosted: Wed Jul 14, 2010 5:18 pm 
Bitchin' Fast 3D Z8000*
Bitchin' Fast 3D Z8000*
User avatar

Joined: Tue Jun 29, 2004 11:32 pm
Posts: 2555
Location: Somewhere between compilation and linking
CrashTECH wrote:
Old article, but still! I wrote the FizzBuzz app in about two minutes, including waiting for VS 2010 to open! I find it crazy that most CS graduates can't do it. Even more so that "Senior Programers" take 10-15 minutes? I should be paid more...

I've seen some "senior programmers" that weren't pile crap... but I don't think that I've ever come across anyone that couldn't code something this simple (this would be the easiest of easy TopCoder problems). Honestly, I can't explain how many of them managed to find employment (beside at McD's) and retain it long enough to have "senior" in front of their name.

The second persons assertion that most applicants can't tell you what comes after A or F in hex or use recursion surprises me less. With all of these stupid "software engineering" programs churning out mindless dimwits quoting design pattern books and software metrics... and never having written anything of interest. Sometimes I really wish that I was old enough to have been employed during the 60's or 70's.
Top
  Profile  
 
Gadget
 Post subject:
PostPosted: Wed Jul 14, 2010 5:39 pm 
Bitchin' Fast 3D Z8000*
Bitchin' Fast 3D Z8000*
User avatar

Joined: Tue Jun 29, 2004 11:32 pm
Posts: 2555
Location: Somewhere between compilation and linking
Jipstyle wrote:
That is just ugly

Yes. Your code is ugly. When are you going to start using a language that resembles mathematical poetry?! ;)

Personally, I think that checking for the "five" inside the "three" condition is probably not buying you any speed (and costing you a bit in cleanliness) -- the thing that is going to suck up all the time is the output to the console (of course) -- the "speed up" would probably amount to less than the noise created by other processes on the system.

Here is a much prettier version of Jip's algo... ;)

Code:
CL-USER> (defun fizzbuzz (max)
      (let ((three 0)
         (five 0))
        (loop for i from 1 to max do
         (incf three)
         (incf five)
         (cond ((and (= three 3)
                (= five 5))
           (setf three 0 five 0)
           (print "FizzBuzz"))
          ((= five 5)
           (setf five 0)
           (print "Buzz"))
          ((= three 3)
           (setf three 0)
           (print "Fizz"))
          (t (print i))))))
FIZZBUZZ
CL-USER> (fizzbuzz 20)

1
2
"Fizz"
4
"Buzz"
"Fizz"
7
8
"Fizz"
"Buzz"
11
"Fizz"
13
14
"FizzBuzz"
16
17
"Fizz"
19
"Buzz"

NIL
CL-USER>


I need to finish getting ready for a trip tomorrow. I'll post a slight change to problem a bit later tonight.
Top
  Profile  
 
Gadget
 Post subject:
PostPosted: Thu Jul 15, 2010 7:11 pm 
Bitchin' Fast 3D Z8000*
Bitchin' Fast 3D Z8000*
User avatar

Joined: Tue Jun 29, 2004 11:32 pm
Posts: 2555
Location: Somewhere between compilation and linking
Problem variation: Given a value max, compute the sum of the integers from 1 to max unless the number is a multiple of both 3 and 5. Test and time your solution with a max value of 100 million.

CrashTECH wrote:
I suppose it would depend how it (mod) is implemented. I honestly can't say that I know the algorithm for it.

I'm not sure how it is implemented on standard hardware either. I know that there are quite a few algorithms extending back a number of years and probably over a hundred variations due to algorithms used in various crypto systems.

Why didn't you implement this using the .NET parallel library?! JK.
Top
  Profile  
 
CrashTECH
 Post subject:
PostPosted: Thu Jul 15, 2010 7:14 pm 
SON OF A GUN
SON OF A GUN
User avatar

Joined: Mon Nov 01, 2004 5:41 am
Posts: 11602
LOL

You can't just throw the library at things and expect magic :)

I mean I could run and do all the comparisons and use a hash-map or something and then just dump the map with the proper outputs out... but not sure that is more efficient.

I'll run your variation tomorrow at work. I'll try it on a couple boxes. Wish I had time to run it on my home PC.
Top
  Profile  
 
CrashTECH
 Post subject:
PostPosted: Fri Jul 16, 2010 9:56 am 
SON OF A GUN
SON OF A GUN
User avatar

Joined: Mon Nov 01, 2004 5:41 am
Posts: 11602
10000: 1062.534ms
100000: 2531.331ms
1000000: 25032.051ms

I got bored waiting for your 100 MM to finish. I'll run it at home or over the weekend or something.
Top
  Profile  
 
CrashTECH
 Post subject:
PostPosted: Fri Jul 16, 2010 9:56 am 
SON OF A GUN
SON OF A GUN
User avatar

Joined: Mon Nov 01, 2004 5:41 am
Posts: 11602
Code:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace FizzBuzz
{
    class Program
    {
        static void Main(string[] args)
        {
            DateTime start = DateTime.Now;
            Console.WriteLine("Starting...");
            for (int i = 1; i <= 1000000; i++)
            {
                if (i % 5 == 0)
                {
                    if (i % 3 == 0)
                    {
                        Console.WriteLine("FizzBuzz");
                    }
                    else
                    {
                        Console.WriteLine("Buzz");
                    }
                }
                else if (i % 3 == 0)
                {
                    Console.WriteLine("Fizz");
                }
                else
                {
                    Console.WriteLine(i);
                }
            }

            DateTime end = DateTime.Now;

            Console.WriteLine("Duration: " + (end - start).TotalMilliseconds + "ms");

            Console.ReadLine();
        }
    }
}
Top
  Profile  
 
Gadget
 Post subject:
PostPosted: Sat Jul 17, 2010 12:32 pm 
Bitchin' Fast 3D Z8000*
Bitchin' Fast 3D Z8000*
User avatar

Joined: Tue Jun 29, 2004 11:32 pm
Posts: 2555
Location: Somewhere between compilation and linking
You darn LOB programmers!!! =)

Think back to your algorithm and/or math classes... here is a BIG hint:

1 2 3 4 5
5 4 3 2 1
-----------
6 6 6 6 6

time for slow version... O(n)
Real time: 115.805 sec.

time for fast version... O(1)
Real time: 0.0 sec.
Top
  Profile  
 
Gadget
 Post subject:
PostPosted: Sat Jul 17, 2010 12:35 pm 
Bitchin' Fast 3D Z8000*
Bitchin' Fast 3D Z8000*
User avatar

Joined: Tue Jun 29, 2004 11:32 pm
Posts: 2555
Location: Somewhere between compilation and linking
Ah... I just noticed that you're still printing out the values. No printing this time...

Problem variation: Given a value max, compute the sum of the integers from 1 to max unless the number is a multiple of both 3 and 5. Test and time your solution with a max value of 100 million.
Top
  Profile  
 
CrashTECH
 Post subject:
PostPosted: Sun Jul 18, 2010 8:27 am 
SON OF A GUN
SON OF A GUN
User avatar

Joined: Mon Nov 01, 2004 5:41 am
Posts: 11602
You expected me to think on Friday? wth is wrong with you?
Top
  Profile  
 
Gadget
 Post subject:
PostPosted: Tue Jul 20, 2010 10:47 pm 
Bitchin' Fast 3D Z8000*
Bitchin' Fast 3D Z8000*
User avatar

Joined: Tue Jun 29, 2004 11:32 pm
Posts: 2555
Location: Somewhere between compilation and linking
Haha... Friday is the ONLY day to get caught up on everything, no?! =)

Here is my O(1) solution to the alternate problem. Basically, a combination of the integral sum (ie (n+1)*n / 2) and LCM are all that is needed to compute the value.

Code:
(defmacro sum (n)
  `(/ (* ,n (1+ ,n)) 2))

(defun fizzbuzz (max)
  (let* ((lcm 15)                               
         (num-multiples (truncate (/ max lcm))))
    (- (sum max) (* lcm (sum num-multiples)))))
Top
  Profile  
 
Jipstyle
 Post subject:
PostPosted: Wed Jul 21, 2010 8:56 am 
Java Junkie
Java Junkie
User avatar

Joined: Mon Jun 14, 2004 10:23 am
Posts: 24150
Location: Granite Heaven
Nice solution.

And that is why I switched from programming to information architecture. :P
Top
  Profile  
 
BlueL
 Post subject:
PostPosted: Thu Jul 22, 2010 3:43 pm 
8086
8086

Joined: Mon Nov 09, 2009 9:15 pm
Posts: 5
Doesn't LCM take variable time to compute?
Top
  Profile  
 
Gadget
 Post subject:
PostPosted: Sun Aug 01, 2010 3:17 pm 
Bitchin' Fast 3D Z8000*
Bitchin' Fast 3D Z8000*
User avatar

Joined: Tue Jun 29, 2004 11:32 pm
Posts: 2555
Location: Somewhere between compilation and linking
BlueL wrote:
Doesn't LCM take variable time to compute?


Yes. In this case, I knew the LCM in advance, so I simply plugged the value in as a magic number (bad Gadget!). Computing the LCM is relatively inexpensive (ie < O(n) keeping things simple...) and can be found using:

LCM(m,n) = (m*n) / GCD(m,n)

Adding m and n as parameters and using the built-in CL LCM function...
Code:
(defmacro sum (n)
  `(/ (* ,n (1+ ,n)) 2))

(defun fizzbuzz (max m n)
  (let* ((lcm (lcm m n))    ;;Here the var lcm is given the value from calling the LCM function...
         (num-multiples (truncate (/ max lcm))))
    (- (sum max) (* lcm (sum num-multiples)))))

(time (fizzbuzz 1000000000 5 3))
Real time: 0.0 sec.
Run time: 0.0 sec.
Space: 176 Bytes
466666667333333335
Top
  Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  Page 1 of 3
  [ 52 posts ]  Go to page 1, 2, 3  Next

Board index » OS/Software/Programming » Programmers' Paradise

All times are UTC - 8 hours


Who is online

Users browsing this forum: No registered users and 2 guests

You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group