Programming Puzzles 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."
I will help YOU get a JOB! (Programming puzzles) (Score:1, Interesting)
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
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 ]
the 15-square puzzle (Score:5, Interesting)
The "15" Puzzle (Score:4, Interesting)
Re:high return rate (Score:3, Interesting)
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:I will help YOU get a JOB! (Programming puzzles (Score:4, Interesting)
Re:the 15-square puzzle (Score:5, Interesting)
Done the 8 Puzzle (Score:1, Interesting)
Re:Question 3 Solved (Score:2, Interesting)
a ^= b ^= a ^= b;
or
#define SWAP(a,b) (a^=b^=a^=b);
Re:I will help YOU get a JOB! (Programming puzzles (Score:3, Interesting)
$b='$b=%c%s%c;printf$b,39,$b,39;';printf$b,3
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
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
Re:Rubik's Cube (Score:3, Interesting)
I was a kid when the Rubik's Cube came out. Our neighbor was a topologist. He went out and bought the cube, and presented it to his wife to have her scramble it. Then it sat, unmolested, on the coffee table for many nights while the topologist figured out the necessary moves to solve the puzzle.
It took him lots of pages on a legal pad but he did solve it. After about two weeks as I recall.
I, being a kid, bought the "How To Solve The Rubik's Cube" book on the family vacation and was solving the cube in under a minute shortly thereafter. I've long since forgotten the patterns, but I bet the topologist could still solve it.
Re:Question 3 Solved (Score:0, Interesting)
a = b + 0*(b=a);
~avinu
Re:the 15-square puzzle (Score:5, Interesting)
For this reason, an alternate way to ensure his confounding is to leave the orginal R for RATE in the corner and then mix the puzzle up such that the A of PAL is near the top and the A of RATE is near the bottom.
The solution (Score:1, Interesting)
a1, 12, 21, 31, 62, 32, 21, 62, a1, 42, 51, 71, 82, 72, 51, 82, a1, 62, 21, 32, a1, 82, 51, 72, a1
Try it here [puzzleworld.org]
Re:Whats so special? (Score:2, Interesting)
And incredibly so, he did it in Haskell (crowd gasps!), a functional programming language which requires recursive execution of algorithms. What was it, 50 lines of code? 75?
What impresses me is how this guy got so many column inches in the Economist. I need better marketting...
Map of Quzzle puzzle space (Score:2, Interesting)
We've put together a graph [ylett.com] linking all the positions you can get to with the Quzzle.
Starting point shown in red. Top/right Ending point(s) shown in blue. And the (incorrect) bottom right solution in pink. The path from start to solution is shown in green.
Notes: Used aiSee [aisee.com] to draw the graph. The circuits that seem to appear in the solution are just due to the graph being drawn with crossovers.
Ok.. time to go and find something less geeky to do with the rest of the evening.