Thread: C/C++ Challenge

  1. #1
    Registered User
    Join Date
    Feb 2012
    Posts
    2

    C/C++ Challenge

    The next problem was presented to me during a job interview when I started looking for work earlier.

    Some time has passed and I just can't see the solution! It is a fact that I've been occupied ever since, but still it bites me not to know how to solve this problem.

    Code:
    #include <stdio.h>
    #include <stdint.h>
    
    
    int main(void)
    {
      int64_t c, r, x, y;
      c = 0;
      r = 968790360;
      for (x = -r; x <= r; x++)
        for (y = -r; y <= r; y++)
          c += ((x * x) + (y * y) <= (r * r));
     
      c = (c * 0x671659AD2B395A35LL) ^ 0x6A657B39259F7846LLU;
      printf("%.8s\n", (char *) &c);
      return 0;
    }
    Error at line 14...

    Thanks

  2. #2
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    What's the problem?

    *Moved to C programming forum*
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  3. #3
    Registered User
    Join Date
    Feb 2012
    Posts
    2
    seems my compiler doesn't recognize the Base 36 numbers...

    ...and the solution asked doesn't allow changing the existing code.

    I could just pass the Base 36 numbers to a more common base, but that would be "taking the charm" of the problem...

  4. #4
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Quote Originally Posted by jc_ferreira
    seems my compiler doesn't recognize the Base 36 numbers...
    Those integer literals are in base 16, not base 36. However, they are long long and unsigned long long, so you need to compile the code with respect to the 1999 edition of the C standard (C99).

    Quote Originally Posted by jc_ferreira
    ...and the solution asked doesn't allow changing the existing code.

    I could just pass the Base 36 numbers to a more common base, but that would be "taking the charm" of the problem...
    Changing the base does not change the underlying code, as long as your changes are correct.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  5. #5
    Registered User
    Join Date
    Dec 2011
    Posts
    795
    Your loop will run 3,754,219,046,515,718,000 times. The variable "c" can hold up to 9,223,372,036,854,775,807, so it will technically hold what you're trying to put in it (each time it adds either a one or a zero, because of the logic operator). But it seems really pointless.

    Especially because the rest of the program does nothing until the printf, where it generates a signal and immediately terminates. This is expected, because you're trying to print out a character representation of the memory address at variable "c".

  6. #6
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Quote Originally Posted by memcpy
    Especially because the rest of the program does nothing until the printf, where it generates a signal and immediately terminates. This is expected, because you're trying to print out a character representation of the memory address at variable "c".
    A string representation, actually, so undefined behaviour might not happen with a suitable null byte before an out of bounds access happens.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  7. #7
    - - - - - - - - oogabooga's Avatar
    Join Date
    Jan 2008
    Posts
    2,808
    The printf specification "%.8s" will only print up to 8 chars, so no null char is needed. Presumably there is a secret 8 character message to be discovered.

    The idea of this challenge is that you can't run the program since it would run for a very long time (3.7 billion billion iterations, over 100 years if each iteration took a billionth of a second). So you have to figure out the result of the double loop without running it.

    The inner statement would execute [(2r+1)squared] times. Think of this as going through the pixels of a digitized square of that area. Imagine a circle of radius r inscribed within the square. All points within and on the circle satisfy x*x + y*y <= r*r. The proportion of such points to the total number of points in the square is pi/4 because the area of the circle is [pi*(r squared)] and that of the square is [4*(r squared)].

    So after the double loop, c should contain [(2r+1)squared] * pi/4.

    Having said all that, I can't actually get it to work! Can someone else?

    At any rate, if you can calculate c with the above information, just feed it into the next step (the linear congruential RNG) and Bob's your uncle.

  8. #8
    - - - - - - - - oogabooga's Avatar
    Join Date
    Jan 2008
    Posts
    2,808
    Returning to this problem after dinner I realized that its discrete nature dooms the above method, so I resorted to actual counting but as efficiently as I could manage. I've written a program that solves it in about 70 seconds (32-bit 2.5ghz machine). The inner loop repeats 968,790,360 times, just less than a billion compared to 3.7 billion billion for the original program. However, I can't help but feel there's a much simpler solution. Anyway, here's mine.

    Consider the puzzle with r = 10. The picture below shows the "pixels" that are within and on the circle in just one quadrant (not including the axes):
    Code:
    0
    9 * * * *
    8 * * * * * *
    7 * * * * * * *
    6 * * * * * * * *
    5 * * * * * * * *
    4 * * * * * * * * *
    3 * * * * * * * * *
    2 * * * * * * * * *
    1 * * * * * * * * *
    0 1 2 3 4 5 6 7 8 9 0
    The idea is to find the first pixel that is outside the circle starting at line r - 1 (line 9 above). Then step straight down and start scanning the next row from that point, and so on. Just sum the number of pixels you find in each row to count how many there are in the whole quadrant. To get the final answer, multiply that count by 4 (for 4 quadrants) and add in r * 4 + 1 for the axes.

    Code:
    #include <stdio.h>
    #include <stdint.h>
    
    int main(void)
    {
      int64_t c = 0, r = 968790360, sr, i, j, last = 0;
    
      for (i = 1; i < r; i++) {
        sr = r * r - (r - i) * (r - i);
        for (j = last; j * j <= sr; j++)
          ;
        last = j;
        c += last - 1;
      }
      c *= 4;
      c += 4 * r + 1;
    
      c = (c * 0x671659AD2B395A35LL) ^ 0x6A657B39259F7846LLU;
      printf("%.8s\n", (char*)&c);
    
      return 0;
    }
    BTW, the secret message is "welldone".

  9. #9
    'Allo, 'Allo, Allo
    Join Date
    Apr 2008
    Posts
    639
    Great stuff, if you live in Portugal you can also apply for the job the OP and everybody who googles for those constants will now apply for

  10. #10
    - - - - - - - - oogabooga's Avatar
    Join Date
    Jan 2008
    Posts
    2,808
    Any company that hires someone because they solved a stupid puzzle like that deserves what they get.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. C challenge
    By me77 in forum C Programming
    Replies: 3
    Last Post: 04-18-2008, 05:06 PM
  2. A Challenge in C++
    By Brad0407 in forum C++ Programming
    Replies: 38
    Last Post: 07-18-2007, 12:56 PM
  3. Challenge
    By arjunajay in forum C++ Programming
    Replies: 8
    Last Post: 08-20-2005, 02:13 AM
  4. Challenge?
    By Mackology101 in forum C Programming
    Replies: 5
    Last Post: 11-23-2004, 02:30 PM
  5. Take the challenge...
    By correlcj in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 11-15-2002, 09:33 PM

Tags for this Thread