Beta
×

Welcome to the Slashdot Beta site -- learn more here. Use the link in the footer or click here to return to the Classic version of Slashdot.

Thank you!

Before you choose to head back to the Classic look of the site, we'd appreciate it if you share your thoughts on the Beta; your feedback is what drives our ongoing development.

Beta is different and we value you taking the time to try it out. Please take a look at the changes we've made in Beta and  learn more about it. Thanks for reading, and for making the site better!

Programming Puzzles

michael posted more than 9 years ago | from the my-brane-hurts dept.

Toys 392

An anonymous reader writes "Spotted over at the Economist: 'Sliding-block puzzles look easy, but they can be tricky to solve. The best known is the 15 Puzzle, which became hugely popular in the late 1870s. This involves square tiles labelled with the numbers 1 to 15, which must be arranged in the correct order inside a four-by-four frame.' While we've all tried these puzzles, the inventor of Quzzle set out to design the easiest looking - yet most difficult puzzle around and turned to CS to find it. While the original article touches on it, at the puzzle's site you'll find Jim Lewis, the inventor, wrote a program in Haskell, a functional programming language to find the best design."

Sorry! There are no comments related to the filter you selected.

Frost piss (-1, Offtopic)

Anonymous Coward | more than 9 years ago | (#10994818)

I 0wnz j00, bitchez!!!

Re:Frost piss (-1, Troll)

BEA6D (124745) | more than 9 years ago | (#10994829)

y00 d0n't kn0w j@ck.

Re:Frost piss (-1, Flamebait)

Anonymous Coward | more than 9 years ago | (#10994958)

w3ll, 1f j00'r3 50 sm4r+, h0w c0me j00 d1dn'+ g3+ Fr05+ P155?

sometimes puzzles are fun (-1, Offtopic)

Anonymous Coward | more than 9 years ago | (#10994821)

You knwo when i was a kid i rellay liekd these puzzles i got one soemwhere of Curious George it was pretty difficult i remember...it had him the man with a yellow hat and a boat

I will help YOU get a JOB! (Programming puzzles) (1, Interesting)

Amsterdam Vallon (639622) | more than 9 years ago | (#10994825)

Check these out that I found online, they're great things to use b4 interviews!

Programming Puzzles

Some companies certainly ask for these things. Specially Microsoft. Here are my favorite puzzles. Don't send me emails asking for the solutions.

1. Write a "Hello World" program in 'C' without using a semicolon.
2. Write a C++ program without using any loop (if, for, while etc) to print numbers from 1 to 100 and 100 to 1;
3. C/C++ : Exchange two numbers without using a temporary variable.
4. C/C++ : Find if the given number is a power of 2.
5. C/C++ : Multiply x by 7 without using multiplication (*) operator.
6. C/C++ : Write a function in different ways that will return f(7) = 4 and f(4) = 7
7. Remove duplicates in array
8. Finding if there is any loop inside linked list.
9. Remove duplicates in an no key access database without using an array
10. Convert (integer) number in binary without loops.
11. Write a program whose printed output is an exact copy of the source. Needless to say, merely echoing the actual source file is not allowed.
12. From a 'pool' of numbers (four '1's, four '2's .... four '6's), each player selects a number and adds it to the total. Once a number is used, it must be removed from the pool. The winner is the person whose number makes the total equal 31 exactly.
13. Swap two numbers without using a third variable.
14. Given an array (group) of numbers write all the possible sub groups of this group.

[ von http://www.onesmartclick.com ]

Re:I will help YOU get a JOB! (Programming puzzles (3, Informative)

mtrisk (770081) | more than 9 years ago | (#10994870)

That's all great and dandy, but take a look at the article. It's about a guy who writes programs that will make physical puzzles; this has nothing to do with programming puzzles or exercises.

Re:I will help YOU get a JOB! (Programming puzzles (-1, Troll)

Amsterdam Vallon (639622) | more than 9 years ago | (#10994893)

Look, I realize you're trolling, but I have a free minute or two while I burn this CD to respond.

I DID read the article. It's quite good and interesting, in fact.

But you imply that my post is NOT interesting, and you are wrong. Most moderators HAVE found it to be interesting, and it will be VERY helpful for the thousands of Slashdot readers who are interviewing for jobs soon. The difference between a prepared job condidate and one who is ill-prepared is often times puzzle knowledge like I give and encourage in my post above.

How dare you criticize me when I'm simply trying to help out our young coders, our young Linux fans, our own FLESH and blood. You should be ashamed of yourself. An experienced academic like me, an experienced CODER like me, is a guy who should be mentoring our youngsters. You are a lowly hater akin to bickering spinsters.

You are a TROLL!

Re:I will help YOU get a JOB! (Programming puzzles (0)

Anonymous Coward | more than 9 years ago | (#10994970)

A troll calling someone else a troll.

Humour, thy name is Slashdot.

Re:I will help YOU get a JOB! (Programming puzzles (0)

Anonymous Coward | more than 9 years ago | (#10995015)

Did Not Have Very Flesh Coder Troll?
|\
You suck |-\t it.
| \

Re:I will help YOU get a JOB! (Programming puzzles (1)

Refrozen (833543) | more than 9 years ago | (#10994891)

1. Inline Assembly (I guess that doesn't count as C)? 2. cout "1"; cout "2"; ? There must be a trick there. 3. Not a clue. 4. Fooling around with sqrt() (or mod?) for a while might help? I don't know though. 5. result = x + x + x + x + x + x + x? 6. Ahahaha, yeah.... Later. 7. Use a temporary array, add them all, the repeatedly loop through comparing all values... removing is a little harder. 8. Dunno anything 'bout Linked Lists, am not really a C programmer my self. 9. Is there not a ACCESS function to do that, like adding a unique column? 10. Mmm, you can typecast it or something, I remember that from when I was using C. 11. Well, since C isn't a scripting language I don't see how that's possible. 12. Bah. 13. What's the difference in this, and 3? I give up.

Re:I will help YOU get a JOB! (Programming puzzles (2, Insightful)

Anonymous Coward | more than 9 years ago | (#10994960)

1. int main(void) { if(puts("Hello, world")) {} }
3. int x = 5, y = 10; x ^= y; y ^= x; x ^= y;
4. !(var & (var - 1))
5. x /= (1.0 / 7); =)
6. simple: int f(int i) { return i == 7 ? 4 : 7; }
"clever": return 11 - i;


I only did the ones that specifically listed C. Number 3 (and, I suppose, 4 for that matter) is dubious because ^ won't work for all types. And beware of the "better" version: x ^= y ^= x ^= y; That's not defined behavior in C!

Re:I will help YOU get a JOB! (Programming puzzles (1)

binary42 (801099) | more than 9 years ago | (#10995069)

5. could be this... much better btw. a = (a)+(a1)+(a2);

Re:I will help YOU get a JOB! (Programming puzzles (1)

binary42 (801099) | more than 9 years ago | (#10995074)

!! stupid formating!!! a = (a)+(a<<1)+(a<<2);

Re:I will help YOU get a JOB! (Programming puzzles (0)

Anonymous Coward | more than 9 years ago | (#10995093)

how about:

a = (a3) - a;

Re:I will help YOU get a JOB! (Programming puzzles (1)

binary42 (801099) | more than 9 years ago | (#10995118)

yeah... just saw that lower on this page. nifty. Here is correct formatting ;) a = (a<<3) - a;

Re:I will help YOU get a JOB! (Programming puzzles (1)

dgatwood (11270) | more than 9 years ago | (#10994998)

1. Depending on how literally you take this, you might say "I didn't use a semicolon. I used two."

Failing that, how about:

cat > filename.c main()
{
printf("Hello World")SEMI
}
EOF

gcc -DSEMI=';'

Or I've seen other people write it as "if (prinf("Hello world")) {}".

2. "if" is not a loop. that said:

printf("1 2 3 4 5 6 7 8 9 .... 100");
printf("100 99 98 97... 1");

or

function(int k)
{
return (k > 100 ? 0 : printf("%d", k) && function(k+1));
}

function(1);

3. This involves xor. I'm not going to do it.

4. A. Use log functions.
B. bits=0;
for (i=0; i if (bits != 1) printf("Not power of two\n"); else printf("yup.\n");

5. x+x+x+x+x+x+x

6. return (number ^ 3)

7. What's hard about that? 1. Sort. 2. if val[k]== val[k-1] dump it.

8. The lazy way? Free each entry as you go. If you crash, there was a loop. :-D Alternately, just set a bit in the data structure to 1 and if you see it set to 1, there was a loop. Much faster than the naive method, and it's provably optimal-O(n) in the length of the list. :-D

9. Step 1: repartition the computer. Step 2: install Linux and MySQL. Step 3: save the Access database as a text file. Step 4: use 'sort' on the text file with -u. Step 5: import into MySQL.

10. Easy way? Create a table containing 256 entries each with appropriate 8 character strings for each possible value. Then printf("%s%s%s%s\n", bitvalues[int>>24], bitvalues[(int>>16) & 0xff], bitvalues[(int>>8) & 0xff], bitvalues[int & 0xff]);

11. How about:

main()
{
printf("an exact copy of the source\n");
}

12.

Re:I will help YOU get a JOB! (Programming puzzles (1)

dgatwood (11270) | more than 9 years ago | (#10995031)

Whoops, meant to click preview.

12. Pick 1. Then, whatever the other person picks, pick 7-n, unless they pick too many 6s. As your final number, pick a number large enough to win. There will always be a number large enough to win... if I'm doing the math right.

13. See #3 and I'm still not doing it.

14. Umm... no.

Re:I will help YOU get a JOB! (Programming puzzles (0)

Anonymous Coward | more than 9 years ago | (#10995106)

4. A. Use log functions.
B. bits=0;
for (i=0; i if (bits != 1) printf("Not power of two\n"); else printf("yup.\n");


Happened to see a better solution to this one earlier today:
if (x<1) return false;
return (x&(x-1))==0;

stolen from here [gpwiki.org]

Re:I will help YOU get a JOB! (Programming puzzles (1)

Refrozen (833543) | more than 9 years ago | (#10995156)

For number 11, it states you cannot just echo the source. :-(

Other then that, you are a flippin' genious.

Re:I will help YOU get a JOB! (Programming puzzles (1)

EvanED (569694) | more than 9 years ago | (#10995157)

"7. What's hard about that? 1. Sort. 2. if val[k]== val[k-1] dump it."

Okay, now do it in faster time. I bet that they want a better solution.

Here's a somewhat related problem from my MS interview:
You have an array of n integers in the range 0 to n-1. Write a function that returns true if there are duplicates in the array and false if not. That runs in O(n) time. Without allocating extra storage.

Re:I will help YOU get a JOB! (Programming puzzles (3, Funny)

Tablizer (95088) | more than 9 years ago | (#10994905)

But if you really want to stump a slashdotter:

15. Go outside and meet girls.

Re:I will help YOU get a JOB! (Programming puzzles (3, Interesting)

ajs (35943) | more than 9 years ago | (#10994907)

ITA Software [itasoftware.com] also has some great puzzles related to employment.

MOD PARENT DOWN TROLL (0)

Anonymous Coward | more than 9 years ago | (#10994920)

Author is a KNOWN TROLL. If you do not believe me, check his posting history for yourself. Also, some of the puzzles in the list are impossible.

Re:MOD PARENT DOWN TROLL (1)

LnxAddct (679316) | more than 9 years ago | (#10995017)

Everything in there is possible. I've done them before. Any CS undergraduate should have done most of those.
Regards,
Steve

Re:I will help YOU get a JOB! (Programming puzzles (2, Insightful)

Stevyn (691306) | more than 9 years ago | (#10994933)

Here's the thing. I can look at each example and see a solution. But how important is it to actually give the solution?

Computer science has devolved into programming. Is the code that important, or the solution in regular syntax?

I think most people would find this difficult because they forget how to program in these languages, but that doesn't mean they can't see the answer

Re:I will help YOU get a JOB! (Programming puzzles (0)

Anonymous Coward | more than 9 years ago | (#10994957)

computers tend to use exhaustive methods to find solutions. Perhaps they should consult a mathmatician.

Re:I will help YOU get a JOB! (Programming puzzles (1)

kyhwana (18093) | more than 9 years ago | (#10994945)

3 and 13 are the same..

Question 3 Solved (5, Informative)

LighthouseJ (453757) | more than 9 years ago | (#10994948)

3. C/C++ : Exchange two numbers without using a temporary variable.

My Computer Architecture teacher asked us essentially this question, he said Intel asked it in a way more palatible for computer engineers than CS students but it still works.

If A contains one number (int or register) and B contains the other:

B = A XOR B;
A = A XOR B;
B = A XOR B;

Explanation:
XOR is bitwise exclusive OR and is basically true when the bits differ.
Say if we're dealing with 4-bit numbers. In the example, say A = 1011 (11 in decimal) and B = 0101 (5 in decimal).

Step 1: If you take the exclusive OR of A (1011) and B(0101), the result is 1110 and put that into B (or A would be fine). Do bit by bit comparisons based on position from left to right and if the bits are different, mark a one in it's position, if they are the same, mark a zero. By this point A contains an original pattern, 1011 (decimal 11) and B contains the difference 1110 (decimal 14) between patterns.

Step 2: Take the XOR of A and B again and store in the variable with an original pattern (A in this instance). 1011 XOR 1110 comes out to being 0101 (the original value for B) and we store it in A.

Step 3: Take the final XOR of A and B again, store in last register B. 0101 XOR 1110 comes out to 1011 (our original A) and is stored in register B.

Voila, 2 values exchanged very elegantly without wasted space and done in the same amount of steps as using a temporary variable. If you still don't understand, it works on the premise that if you have two piece of data, you only need one piece of data and whats different from the two pieces of data, that way you can reconstruct the other piece of data.

Re:Question 3 Solved (0)

Anonymous Coward | more than 9 years ago | (#10994961)

I guess you could do this with exclusive nor as well.

Re:Question 3 Solved (1, Interesting)

szap (201293) | more than 9 years ago | (#10994967)

The solution is canonically written in C/C++ as:

a ^= b ^= a ^= b;

or

#define SWAP(a,b) (a^=b^=a^=b);

Re:Question 3 Solved (1)

LighthouseJ (453757) | more than 9 years ago | (#10994985)

I'm sure there was a bitwise XOR operator, but I am more familiar with assembly and assembly-style level of thought.

Re:Question 3 Solved (2, Insightful)

brer_rabbit (195413) | more than 9 years ago | (#10995121)

That isn't correct C/C++. You're modifying the same variable multiple times in the same statement. Although it'll probably work on most compilers, the result is technically undefined.

Re:Question 3 Solved (alternative method) (2, Informative)

JasonSkywalker (204047) | more than 9 years ago | (#10994984)

This is what popped into my head upon reading this post... same principal as the XOR method but simpler to explain to layfolk...

A = A*B
B = A/B (gives B the orig A)
A = A/B (gives A the orig B)

Re:Question 3 Solved (alternative method) (1)

kylemonger (686302) | more than 9 years ago | (#10995004)

This fails if A or B is zero because A * B will lose information.

Re:Question 3 Solved (alternative method) (2, Informative)

LighthouseJ (453757) | more than 9 years ago | (#10995011)

True, but what if you have large numbers, like 64-bit values? To properly handle that, your ALU need to be able to multiply 2 64-bit values and the result is a 128-bit product then perform the division. With my style, you can keep the 64-bit bus sizes and the computation needed is considerably small, XOR is a very cheap instruction computationally.

Re:Question 3 Solved (0)

Anonymous Coward | more than 9 years ago | (#10995041)

How about :
x = x + y
x = x - y
y = x - y

Re:Question 3 Solved (0)

Anonymous Coward | more than 9 years ago | (#10995052)

oops, make that :
x = x + y
y = x - y
x = x - y

Re:Question 3 Solved (1)

LighthouseJ (453757) | more than 9 years ago | (#10995091)

I refer you here [slashdot.org] .

Re:Question 3 Solved (1)

LighthouseJ (453757) | more than 9 years ago | (#10995053)

Doesn't work with signed numbers.

If x = 3, and y = -4:

x = 3 + -4 -> x:= -1
x = -1 - -4 -> x:= +4
y = 3 - -4 -> y:= +7

At completion, x = 4, y = 7, won't work.

Use only subtraction and addition (1)

silvergoose (807387) | more than 9 years ago | (#10995046)

a = a + b b = a - b a = a - b Same idea as the multiplication answer, since both are commutative, but this gets around divide by zero.

Re:Use only subtraction and addition (1)

LighthouseJ (453757) | more than 9 years ago | (#10995080)

The only problem I see now is what if A and B are unsigned integers and you were dealing with 4-bit numbers and a = 1111 and b = 1101, you get overflows and crap.

The addition/subtraction responses shows thought, but it's too much. The original XOR method is very slim and cheap computationally because the addition/subtraction requires you to wait for the calculations. XOR is more like a straight shot and it works with any bus length.

Re:I will help YOU get a JOB! (Programming puzzles (0)

Anonymous Coward | more than 9 years ago | (#10994990)

I generally find people using these sorts of things as an employment test to be asinine, since most of them are generally just "oh, you heard how to do that, eh?" or you find them out by a lot of experience. But since other posters here haven't seemed to figure it out, I'll suggest a few answers...

1. Tri-graphs; 2. Recursion; 3. x ^= y ^= x ^= y; 4. Search for a single 1-bit; 5. Good googly moogly x86 assembly programmers love this one: (x << 2) + (x << 1) + x; 9. select with a sort on the desired column, check each row to see if it's the same as the last; 11. This one's been covered ad nauseum but needless to say, it is possible. Is 12 even a programming problem?!

That's just at a glance, so I don't doubt they are all possible one way or another.

Anyway, to remain on topic (and prove I RTFA ;), since when are problems based on computability an "bizarre diversion" of CS? Last I checked, that was most of the point of it, at least if you asked Turing. Certainly that is one of the areas of most ongoing research.

Re:I will help YOU get a JOB! (Programming puzzles (1)

dgatwood (11270) | more than 9 years ago | (#10995051)

There is no trigraph for semicolon. Otherwise, that would be a good answer. You might be able to define your own in some way, though.... not sure.

And 12 is a variant on nim, I think. Very much not a programming problem, but a logic problem.

Here's another one that took about 30 seconds and had me rolling on the floor:

1
1 1
2 1
1 2 1 1
1 1 1 2 2 1

What's the next entry in the pattern?

Re:I will help YOU get a JOB! (Programming puzzles (1)

falzer (224563) | more than 9 years ago | (#10995071)

3 1 2 2 1 1

Re:I will help YOU get a JOB! (Programming puzzles (1)

Yaztromo (655250) | more than 9 years ago | (#10995084)

What's the next entry in the pattern?

312211

Yaz.

Re:I will help YOU get a JOB! (Programming puzzles (0)

Anonymous Coward | more than 9 years ago | (#10995134)

312211

?

Re:I will help YOU get a JOB! (Programming puzzles (0)

Anonymous Coward | more than 9 years ago | (#10995062)

"2. Recursion"

Okay, now how do you notice you're at the base case without an if statement? (?: is cheating too I think)

Re:I will help YOU get a JOB! (Programming puzzles (1)

fredrikj (629833) | more than 9 years ago | (#10995066)

5. Good googly moogly x86 assembly programmers love this one: (x << 2) + (x << 1) + x

More efficiently:
(x << 3) - x

Re:I will help YOU get a JOB! (Programming puzzles (1)

davebaum (653977) | more than 9 years ago | (#10995070)

Trigraphs were my first thought on how to solve #1 too, but then I looked them up and it turns out that semicolon is part of the ISO 646 standard 7-bit character set, so there isn't a trigraph for it. I think the intended solution is to exploit the fact that code blocks after an if or while statement do not need a terminating semicolon: #include int main() { if (printf("Hello, world\n")) { } }

Re:I will help YOU get a JOB! (Programming puzzles (2, Informative)

davebaum (653977) | more than 9 years ago | (#10995088)

ooops - should've previewed. The code didn't paste well into HTML. Here's another try:

#include <stdio.h>

int main()
{
if (printf("Hello, world\n")) { }
}

Re:I will help YOU get a JOB! (Programming puzzles (1)

LnxAddct (679316) | more than 9 years ago | (#10995060)

For number 11, here is the solution. I'm not the guy who coded this and I don't know who to attribute it to so I guess we'll just say: Copyright SCO 1994-2004 ;) (laugh)
Here is the C program that prints itself (also known as a self-reproducing program or a quine)

char*f="char*f=%c%s%c;main(){printf(f,34,f,34,10 );}%c"; main(){printf(f,34,f,34,10);}

Regards,
Steve

Re:I will help YOU get a JOB! (Programming puzzles (1)

sahonen (680948) | more than 9 years ago | (#10995089)

I'm not a programmer, so excuse my ignorance, but how does a quine work? When you compile it, it gets turned into machine code, so how does the program know what the source code is?

Re:I will help YOU get a JOB! (Programming puzzles (3, Interesting)

LnxAddct (679316) | more than 9 years ago | (#10995139)

It doesn't. It is simply a clever trick on the programmers part. Another quine, in perl is:
$b='$b=%c%s%c;printf$b,39,$b,39;';printf$b,39 ,$b,39;
Looks confusing right? Actually if you format it nicer it makes more sense:
$b='$b=%c%s%c;printf$b,39,$b,39;';
printf$b,39, $b,39;

You'll see that $b is a string that is equal to the entire source code except for what b is equal to. (Give it some thought and it'll make sense). printf then prints b substituting %c%s%c with the appropriate values ( quotation marks and the value of $b in the middle). It's going to be hard for a non-programmer to grasp, but hopefully this helped.
Regards,
Steve

Number 5 (0)

Anonymous Coward | more than 9 years ago | (#10995081)

5. C/C++: Multiply x by 7 without using multiplication (*) operator.

Too easy (assumed x was int)

x / (1.0/7.0)

(x << 3) - x

Two *REAL* solutions to #2 (1)

EvanED (569694) | more than 9 years ago | (#10995090)

It is possible to do #2 without any explicit control structures, and without manually typing all the numbers from 1 to 100.

No If, While, For, ?:, etc.

Hints to the solution I found:

Hint 1:
If you know Ml, think how you could do it with Ml. If you don't know Ml, it would look like this in pseudo-Ml code:

fun printI(1) = (print "1";)
| printI(i) = (printI(i-1); print i;);

Ml performs pattern matching on the code. It's functionally equivalant to:
fun printI(i) = if i=1 then print "1!;
else (printI(i-1);
print i;)
end;

Is there anything in C++ that can mimic Ml's pattern matching?

Hint 2:

Look up C++'s template specialization.

My solution is at http://www.personal.psu.edu/users/e/e/eed132/misc/ count.cpp

There is another solution a friend of mine came up that I think is slighty more conventional and doesn't use features that are anywhere near as obscure.

Hints to his solution:

The following code:
stupidfoo(int i) {}

print(int i)
{
if(i > 0)
{
print(i-1);
printf("%i", i);
}
else
{
stupidfoo(i);
}
}

is as good as a normal recursive solution in terms of correctness. Calling a function that returns right away is as good as just returning right away in the first place.

Step 2:
So we can replace the if statement with a single expression (this gets into the realm of questionable readability, but whatever):
print(int i)
{
((i > 0) ? print : uselessfoo)(i);
}

Ponder that line for a moment, it may not be clear right away.

Step 3:
We can put print and uselessfoo into an array of type void(*)(int), with print in [0] and uselessfoo in [1]. Thus the above line can be replaced by
(functions[(i > 0) ? 0 : 1])(i);

Step 4:
Now, can you get a 0 or 1 out of i without using any control expressions?

href="http://www.personal.psu.edu/ users/e/e/eed132/misc/count2.cpp has the final code.

I'm also imagining solutions with purposely raising exceptions when i is 0 and then catching them in main.

Another... (1)

EvanED (569694) | more than 9 years ago | (#10995132)

Here's the fruit of my thoughts on the exception:

void print(int x)
{
double i = 1/(101-x);
printf("%i ", x);
print(x+1);
}

int main()
{
try{ print(1); }
catch(...){}
}

I suspect this is closest to what they are looking for.

Solutions to some of these... (4, Informative)

Otto (17870) | more than 9 years ago | (#10995111)

1. Write a "Hello World" program in 'C' without using a semicolon.

void main()
{
if (printf("Hello World!\n") {}
}

2. Write a C++ program without using any loop (if, for, while etc) to print numbers from 1 to 100 and 100 to 1;

Dumb....

void main()
{
printf("1\n2\n3\n... and so on...");
}

3. C/C++ : Exchange two numbers without using a temporary variable.

x^=y; y^=x; x^=y;

4. C/C++ : Find if the given number is a power of 2.

if (!( x & (x-1)) printf("x is a power of 2\n");

5. C/C++ : Multiply x by 7 without using multiplication (*) operator.

x = (x6. C/C++ : Write a function in different ways that will return f(7) = 4 and f(4) = 7

int function(int x) {
switch (x)
{
case 7: return 4;
case 4: return 7;
}
}
Or countless other ways...

10. Convert (integer) number in binary without loops.

I assume you mean to print the binary form of an int without using loops. So I didn't use a loop, I used recursion. ;)

void printbits(int x)
{
int n=x%2;
if(x>=2) printbits(x/2);
printf("%d", n);
}

13. Swap two numbers without using a third variable.

Same problem as #3 above.

That's enough for now...

Re:I will help YOU get a JOB! (Programming puzzles (1)

OneHungLo (265284) | more than 9 years ago | (#10995115)

The stupid filter doesn't like me posting the code to answer these, so I guess I'll just post the first 3.

1.
#include <stdio.h>

main()
{
if (printf("Hello, world!")) {}
}
2.
#include <iostream>

template<class T>
inline void printinc(T i, const T limit)
{
std::cout<<i<<" ";
if(i<limit)
printinc(++i, limit);
}

template<class T>
inline void printdec(T i, const T limit)
{
std::cout<<i<<" ";
if(i>limit)
printdec(--i, limit);
}

int main()
{
using namespace std;

printinc(1, 100);

cout<<endl<<endl;

printdec(10 0, 1);
}
3.
#include <algorithm>

int main()
{
using std::swap;

int x=1, y=2;

swap(x,y);
}

Re:I will help YOU get a JOB! (Programming puzzles (0)

Anonymous Coward | more than 9 years ago | (#10995144)

'if' is outlawed for #2. If you could use if, even without goto, it'd be much, much simpler than what you say.

And why do you go "using std::swap; ... swap(x,y);" instead of just saying "std::swap(x,y);"?

Re:I will help YOU get a JOB! (Programming puzzles (0)

Anonymous Coward | more than 9 years ago | (#10995152)

I've got problems with #1: You can't write a valid (i.e. compiles without errors or warnings) C program without a semicolon. Every complete, valid C program must have a main() function. The main function must have a return statement (and each statement must end in a semicolon). (The return statement in main is optional in C++ but not in C.) So, the answer to #1 as stated is "you can't".

I can write something without a semicolon that prints "Hello World" when passed through gcc, but it uses only the C pre-processor and does not result in a compiled program, therefore it can't really be called a C program:

#error Hello World

Reminds me of Klotski (1, Informative)

TheLink (130905) | more than 9 years ago | (#10994833)

One version [freehackers.org] .

Re:Reminds me of Klotski (1)

Refrozen (833543) | more than 9 years ago | (#10994860)

Klotski is such a 1337/hard game. It was so much fun, I remember playing it in the Windows 98 WEP pack when I was a young gaffer.

Here's another version [bricks-game.de]

this was my first assignment at uni (1)

Leonig Mig (695104) | more than 9 years ago | (#10994839)

using CLEAN, a functional language no-body had ever heard before.

nobody got it to work (except a couple of russian guys?).

apparently the professor said that was the whole point of the assignment?

Re:this was my first assignment at uni (1)

eeg3 (785382) | more than 9 years ago | (#10994942)

The point was to prove Russians are better than us? Interesting professor.

Re:this was my first assignment at uni (1)

Leonig Mig (695104) | more than 9 years ago | (#10994947)

yeah, i think he was trying to teach us we all suck.

- but the russian guys got him beat. ;)

high return rate (3, Insightful)

Tablizer (95088) | more than 9 years ago | (#10994843)

People are going to buy it because it *looks* simple, but take it back after long times of fiddling in frustration. Or, give it bad reviews in websites.

Ideally puzzles offer some form of partial gratification if one can see that they are getting closer. I don't know yet if this puzzle is all-or-nothing. There are a lot of different factors that make a puzzle commercially successful. Driving them crackers with deceiptful design is not aways one of them. But, it is an interesting idea.

Re:high return rate (2, Interesting)

Hatta (162192) | more than 9 years ago | (#10994872)

People are going to buy it because it *looks* simple, but take it back after long times of fiddling in frustration. Or, give it bad reviews in websites.

Ideally puzzles offer some form of partial gratification if one can see that they are getting closer.


In solving the rubiks cube the partial gratification of completing a side must be forsaken for the larger goal of solving the whole cube. This didn't stop it from becoming immensely popular.

Re:high return rate (1)

Tablizer (95088) | more than 9 years ago | (#10994887)

This didn't stop it from becoming immensely popular.

Yeah, but a lot of puzzles flopped. I think Rubix was commercially successful because of the physical concept of spinning two axises (axi?), not so much the puzzlement.

plurals don't end in 'i' in English (0)

Anonymous Coward | more than 9 years ago | (#10994952)

Main Entry: axis
Pronunciation: 'ak-s&s
Function: noun
Inflected Form(s): plural axes /-"sEz/
Etymology: Latin, axis, axle; akin to Old English eax axis, axle, Greek axOn, Lithuanian asis, Sanskrit aksa
1 a : a straight line about which a body or a geometric figure rotates or may be supposed to rotate b : a straight line with respect to which a body or figure is symmetrical -- called also axis of symmetry c : a straight line that bisects at right angles a system of parallel chords of a curve and divides the curve into two symmetrical parts d : one of the reference lines of a coordinate system

Rubik's Cube (1)

microbox (704317) | more than 9 years ago | (#10995116)

Look up the solution... there's no way that someone works out how to do it without learning the solution... the solution required study from specialized people. The last "move" took a whole bunch of people a long time to work out how to do reliably. The solution is easy to learn as an algorithm, but understanding how it works and reaching those conclusions without help... is a wild leap. It was the most simple-complex puzzle of its time.

I do believe that some people would understand how to solve the Rubik's Cube intuitively, but I think you'd be talking 1 in a million... adding to the myth-ous and "coolness" of the puzzle.

the 15-square puzzle (5, Interesting)

bm17 (834529) | more than 9 years ago | (#10994844)

here's an interesting factoid: Put 15 squares in a 4x4 frame at random and that state will fall into one of two subspaces; call it parity, odd or even. From there, sliding a piece is an operation that will keep the resulting state within the original subspace. So if you have a friend with one of these puzzles, and you pry out two of the pieces and swap them, you will reverse the partiy of the game and he'll never be able to solve it. I leave it to the reader to come up with usefull applications.

Re:the 15-square puzzle (1)

PMJ2kx (828679) | more than 9 years ago | (#10994865)

That reminds me of what i did to my friend's Rubiks cube.

Re:the 15-square puzzle (3, Funny)

Tablizer (95088) | more than 9 years ago | (#10994879)

So if you have a friend with one of these puzzles, and you pry out two of the pieces and swap them, you will reverse the partiy of the game and he'll never be able to solve it.

My brother used to pull multiple Rubix Cubes apart and add extra color blocks to a side or two (making it unsolvable), and them give them to Rubix gurus to solve under the guise of needing help. It was interesting to watch them as their facial expression switched from a confident processing mode to confusion mode. We could take bets on how long it would take them to identify why it was not solvable. The good ol' Rubix days.

Re:the 15-square puzzle (0)

Anonymous Coward | more than 9 years ago | (#10995096)

Couldn't you do this merely by flipping one of the edge blocks around, so that for those two adjoining color sides, there is one block that's flipped, and then mix it up and melt brains with it?

Re:the 15-square puzzle (1)

Otto (17870) | more than 9 years ago | (#10995141)

It's easier to just flip over a couple of the edge pieces. With even one of the edges reversed, it becomes unsolvable. Of course, if you do it to only one edge piece it's obviously messed up. Do it to 4 or 5 of them, and it's not quite so obvious. ;)

Or give a couple of the corner pieces a clockwise rotation. That's even more evil.

Re:the 15-square puzzle (5, Interesting)

Fortran IV (737299) | more than 9 years ago | (#10994934)

A nasty variant of that I've read (but never seen) about is a 15-block puzzle that starts with the pattern:
R A T E
Y O U R
M I N D
P A L
Show your victim the solved puzzle, then scramble it up. Before you give it to him, make sure the R from YOUR is moved into the top-left corner (replacing the R from RATE). If your target is someone who thinks he already knows how these things work, he's likely to leave that R right where you put it - destroying the parity of the puzzle. He's seen that the puzzle can be solved, but he'll never solve it until he moves that R (so I'm told).

Re:the 15-square puzzle (1)

Artifakt (700173) | more than 9 years ago | (#10994940)

Niven and Barnes used this trick for a minor puzzle in the novel "The California Voodoo Game" (part of the Dream Park series). The poser swapped two letter R's that could only be told apart by color.

Got an idea (1)

Tablizer (95088) | more than 9 years ago | (#10994850)

I am going to run over a bunch of Rubix cubes in an SUV and sell them on Ebay as "sliding block 2D puzzles with unknown solutions".

Computers play games, too (1)

PMJ2kx (828679) | more than 9 years ago | (#10994854)

Eh, I think it'd be more fun to play chess with Deep Blue [ibm.com] . Heck, how fast do you think Deep Blue could solve it?

Re:Computers play games, too (0)

Anonymous Coward | more than 9 years ago | (#10994944)

Never, dipshit.

Re:Computers play games, too (1)

shoolz (752000) | more than 9 years ago | (#10994975)

Since Deep Blue is designed to play chess, and chess alone, I'd have to say "never".

The "15" Puzzle (3, Interesting)

Claire-plus-plus (786407) | more than 9 years ago | (#10994856)

I am reminded that the "15" puzzle was set up to be impossibleby the inventor. As is stated on this page [thrijswijk.nl] and other places the way the puzzle was set up made it impossible to solve. This is because there was a prize for the first person to solve it. It looked possible but wasn't. What a scam eh?

Re:The "15" Puzzle (0)

Anonymous Coward | more than 9 years ago | (#10995042)

__________
|____|___|
|________|

1. Draw this on a piece of paper (use lead not ink)
2. Draw a single continuous curve through all line segments in the figure without crossing a straight line twice.
3. ????
4. Profit.

Re:The "15" Puzzle (0)

Anonymous Coward | more than 9 years ago | (#10995048)

Err, this should be:

_______________
| | |
|______|_______|
| |
|______________|

Anyone Know (0)

Omkar (618823) | more than 9 years ago | (#10994861)

A java version of this hardest version? It would be nice to preview the puzzle without the expense^W hassle of a plastic version.

Flash/Java... version of this puzzle? (2, Informative)

CheesyPeteza (814646) | more than 9 years ago | (#10994871)

You'd think he would have created a web version of this puzzle so we could all try it out. :/

You can play it here (5, Informative)

ambrosine10 (747895) | more than 9 years ago | (#10994873)

The puzzle can be played here [puzzleworld.org] .

Re:You can play it here (1)

CheesyPeteza (814646) | more than 9 years ago | (#10994974)

Thank you. It tooke all of 2 minutes to get stuck. I just keep going back and forward. :/

Re:You can play it here (2, Informative)

Anonymous Coward | more than 9 years ago | (#10994992)

And for those looking to cheat, the solution is availible here (warning: pdf document) [johnrausch.com] on page 20.

Unfortunately, reading the solution is almost a puzzle intself.

Whats so special? (3, Insightful)

ryen (684684) | more than 9 years ago | (#10994885)

The Economist needs to do some research on current AI practices.. in particular, that of which taught in a beginning AI course at any university.
The puzzle presented in the article can be solved easily using a variety of basic AI heuristic search algorithms. A* and its varients come to mind.
I fail to see the significance of this guys program when people in my beginners AI class do this stuff for course projects every semester.

Re:Whats so special? (2, Insightful)

Fortran IV (737299) | more than 9 years ago | (#10994913)

He didn't write a program to solve the puzzle; he wrote a program to invent the puzzle. "Given a specific class of simple-looking puzzles, find the most difficult to solve." A much broader and deeper problem than finding the solution for a specific puzzle.

GAP (1, Informative)

Anonymous Coward | more than 9 years ago | (#10994901)

You can analyze puzzles like this using GAP. Here [st-and.ac.uk] is an example using Rubik's cube(Google cache [64.233.161.104] since the site seems down to be down at the moment.)

Done the 8 Puzzle (2, Interesting)

cmad_x (723313) | more than 9 years ago | (#10994939)

I have done the 8 Puzzle in C++. I doubt the 15 puzzle is more difficult. Sure some things might change, but the idea should remain the same :)

A plug and a question... (3, Informative)

Rahga (13479) | more than 9 years ago | (#10994951)

First of all, for GNOME 2.10, gnome-game's Klotski has been updated and now supports SVG and comes with 37 puzzles, several classic wood puzzles from Minrobu Abe (this one may be solvable in 227 moves, not sure [rahga.com] ...)

I've also started a hint function that thells the user the precalculated minimum number of moves for each puzzle. The only problem is that Microsoft's Sunshine [rahga.com] puzzle is huge, and I've not seen any solutions for it online yet, never mind a calculated minimum. Any klotski addicts out there want to help me out?

you FRail It (-1, Troll)

Anonymous Coward | more than 9 years ago | (#10994966)

one related puzzle I remember (1)

jonwil (467024) | more than 9 years ago | (#10995010)

Is that old puzzle that apple had where you had to reassemble the apple logo.
Man I remember messing with that in the labs at school (back when they had macs) instead of doing work.

hum. (0)

Anonymous Coward | more than 9 years ago | (#10995045)

Too bad he couldn't program his computer to recognize the difference between the possessive "its" and the contraction "it's," or to recognize that "ten's" is possessive, not a plural. Imagine the possibilities... a program that could find grammar mistakes! Revolutionary!

And, of course, we all remember... (0)

Anonymous Coward | more than 9 years ago | (#10995072)

...that in "Metamagical Themas", Douglas Hofstadter used the "15 puzzle" to prove/demonstrate some things. If you reassemble the puzzle, but switch two of the tiles:

1 2 3 4
5 6 7 8
9 a b c
d f e ...the puzzle is unsolvable. The challenge, then is to make a computer program that can compute the probability of a random assemblage of the tiles for solvability.

nice to know (1)

glitch23 (557124) | more than 9 years ago | (#10995124)

It's nice to know the puzzle dissolves in water. As the story says, it is soluble.

Traffic (3, Informative)

FlunkedFlank (737955) | more than 9 years ago | (#10995131)

The pic in the article reminds me of Traffic [stanford.edu] , that awesomely addicting old Palm game (based on a real-world sliding block puzzle). I wish there was a PocketPC version!
Load More Comments
Slashdot Login

Need an Account?

Forgot your password?