Medallia Blog

A nice selection!

I propose bonus puzzle 3:
Find the least obvious way to fix the first program by changing TWO characters.

And please let me know if somebody beats my solution for problem 4!

What about including a link to the recruiting brochure on the blog?

eh, i haven't got a compiler here, but won't this do?

int i, n = 42;
for (i = 0; i < n; n--)
  printf("-");

Puzzle "Find the dupe" is very easy. SPOILER FOLLOWS:

Create a bit-array of size n (=fixed memory usage for given n), all initialized to 0. Go through the array of numbers, for each number x you encounter set bitarray[x] = 1 - like you would implement a hashtable.

The first time you encounter an x for which bitarray[x] was already set is when you have found your duplicate.

Also, making the first puzzle print only one dash: add a semicolon at the end of line 2.

>Then find two more!

What is the context of this statement? Two more characters to change afterwards? Or two more 1 character change after the first one? Or two more 1 character changes to the original program?

As for bonus puzzle 2, a possible solution would be to change one of the spaces in front of the printf statement to a semicolon.


int i, n = 42;
for (i = 0; i < n; i--)
; printf("-");


You might be interested more such c puzzles here at my site:
http://www.gowrikumar.com/

I'm curious what's the solution to the 4th.

Isn't magic() undefined behavior? C isn't my strongest language, but I don't think the standard requires the 2s-complement signed overflow that it relies on.

For #1, you can let the terminating condition be i - n (or -i

Another solution is changing the middle of the for to "-i < n".

The "Magic Function" counts the number of ones in the binary form of the number.

j = 1337;
j *= 42 reaches 0 after 32 attempts --one per bit in a common int-- and that's the end of most of the magic.

k -= i += (i<0) + i;

expands to

i += (i<0) + i;
k = k - i;

expands to

i = i + (i<0) + i;
k = k - i;

which equals

i = i * 2 + (i < 0);
k = k - i;

And that's as far as I've gotten at first.

My 42s (I got 4):

int i, n = 42;
for (i = 0; i < n; n--)
  printf("-");

int i, n = 42;
for (i = 0; i + n; i--)
  printf("-");

int i, n = 42;
for (i = 0; i < n; i--1)
  printf("-");

int i, n = 42;
for (i = 0; -i   printf("-")

I haven't found a 43 yet.
My 1:

int i, n = 42;
for (i = 0; i < n; i--);
printf("-");


For positive arguments, the magic function seems to print the highest power of 2 dividing the i-th Catalan number. (But this might depend on the size of int.) Are people supposed to find that by looking at the source code? Or would the following answer be acceptable:

It sets j to be 1337, and k to be 0. Then i is incremented by the sum of (i<0) and i, and k is ...

A few answers:

int main(){

int i, n = 42;
for (i = 0;-i < n; i--)
printf("-");

} // 42 dashes

Changing the < for a + also prints 42 dashes.

You can print one dash by appending a semi-colon to the for loop.

Find the dupe:
Assuming there is only one duplicate, the duplicate is

    int i,sum=0;

    for(i=0;i<len(arr);i++) sum+=arr[i];

    int dup=sum - n*(n-1)/2;

Very interesting! It's a good reminder of how fun it can be to find alternate solutions to the same, simple problem.

The first one is, as I see it, quite easy, I've figured several ways for it already.

1. To print 42 dashes:
1.1 Change the '42' in int n = 41 to (duh) '43' or
1.2 Change the '0' in i = 0 to '-1' or
1.3 Change the '

2. To print 43 dashes:
2.1 Change the '42' to a '44' or
2.2 change the '0' to '-2'

I'll look at the other ones some time today, I'm in a bit of a hurry.

Congratulations on your post :-)


int i, n = 42;
for (i = 0; i < n; i--)
; printf("-");

// runtime --> infinity ;-)

int i, n = 42;
for (i = n; i < n; i--)
printf("-");

/* constant runtime */

The cd problem seems most interesting to me. I doubt I have the optimal answer, but I've not seen any better answers that guarantee results in pathological cases.

I depend on the fact that we have a STACK of cds to choose from, and what matters is how many we end up *using*.

a) given 8 (or 20) cds, we can find two which have at least 20% common zeroes - complicated application of the pigeonhole principle. (or more usefully, disjoint set theory)

b) find 5 pairs of cds that fit this criteria from your stack, for a total of 10 cds.

c) for each pair, write the OR to both, so that they match, and have at least 20% of their bits be zero.

d) on the first of each pair, put your data into the zero bits, use the second as a reference disc to tell you which bits you used.

The proof of (a) isn't really short or easy to render in text, and assumes that heavy and time-consuming comparisons between large numbers of discs up front is alright.

Two possible answers:

int i, n = 42;
for (i = 0; i printf("-");

int i, n = 42;
for (i = 0; -i printf("-");

I want to know what the answer to "Find the dupe" is. Spoilers' answer is silly, because "fixed memory usage for given n" isn't what "constant memory usage" means.

neelesh:
I think you've misinterpreted the duplicate problem. You're assuming that the list is a permutation of the numbers up to n, with one duplicated... that's not the case. All we know is that the numbers are all less than n, and the length of the array is n.

You can use a solution like Spoiler's, using an int as the bit-array, with bitwise operators and powers of 2:
bitarray |= 1

bitarray & 1

But it only works for numbers from 0 to 31 (in a 32b machine).

aoeu:
neelesh is just assuming that there's only one duplicate.
if you take the duplicate out you have a list of length n-1 of positive integers less than n without duplicates and that's a permutation of the numbers up to n.

Spacksack:

you've assumed an int will never overflow - in this case, it will eventually print the character - it might just take a while (especially if the int happens to be 64bit)

The problem says "find *a* duplicate element", so it doesn't matter if there are multiple duplicates, you just have to find 1 of them in linear time.

Doh! (Slaps self in forehead)

Fix the program.

There are not that many ways to attempt to fix the program, just write some code to try them all!

There are 3 ways to get 42 dashes, one way to get 1, 4 to output just one dash, and 2 more that might "display" just one dash.

#2645 listed the 3 ways to get 42 dashes, but i--1 doesn't work - it could only possibly parse as i - (-1), which won't change i. (gcc 4.1.2 doesn't l ike it at all).

The others are
int i, n = 42;
for (i = 0; i < n; n--)
printf("-");

int i, n = 42;
for (i = 0; -i < n; i--)
printf("-");

int i, n = 42;
for (i = 0; i + n; i--)
printf("-");


43 comes from the test ~i < n

1 dash is interesting. Of course
int i, n = 42;
for (i = 0; i < n; i--);
printf("-");

works, if you don't use a 64-bit box (or are very patient). For more fun, use pointer arithmetic (don't mind the nasal demons)
int *i, n = 42;
for (i = 0; i < n; i--)
printf("-");

int i, *n = 42;
for (i = 0; i < n; i--)
printf("-");

For bonus fun, assume the stack is somewhere between bytes 0 and ~0:
int i, n = 42;
for (i = 0; i < &n; i--)
printf("-");

Then, there are two more which write rather more than one '-', but might end up "printing" just one, depending on your terminal and prompt - stick a literal ^H character before or after the '-' in the string. Whee!

Everything else gcc will compile prints more than a billion dashes, or nothing at all. Phooey.

Magic.

Magic, as said before, counts bits set in k (so long as int is two's complement).

Why it works:
1337 === 1 mod 2, 42 === 2 mod 4, and the loop just runs till all the bits have been shifted off. Might as well be j = 1, and do ... while (j <<= 1). i += (i<0) + i rotates i left ((i<0) is true iff the high bit of i is set). Summing every circular shift of i gives ~0 (or -1) times the number of bits set in i, or -#{of bits set}, and subtracting that from k leaves the bit count.