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

What's the problem?

*Moved to C programming forum*

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...

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.

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".

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.

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.

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".

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

Any company that hires someone because they solved a stupid puzzle like that deserves what they get.