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."
Reminds me of Klotski (Score:2, Informative)
Re:I will help YOU get a JOB! (Programming puzzles (Score:4, Informative)
Flash/Java... version of this puzzle? (Score:2, Informative)
You can play it here (Score:5, Informative)
GAP (Score:1, Informative)
Question 3 Solved (Score:5, Informative)
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.
A plug and a question... (Score:4, Informative)
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?
Re:Question 3 Solved (alternative method) (Score:2, Informative)
A = A*B
B = A/B (gives B the orig A)
A = A/B (gives A the orig B)
Re:You can play it here (Score:2, Informative)
Unfortunately, reading the solution is almost a puzzle intself.
Re:Question 3 Solved (alternative method) (Score:3, Informative)
Re:I will help YOU get a JOB! (Programming puzzles (Score:2, Informative)
#include <stdio.h>
int main()
{
if (printf("Hello, world\n")) { }
}
Solutions to some of these... (Score:5, Informative)
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...
Traffic (Score:3, Informative)
More computer assisted puzzles (Score:3, Informative)
Re:Question 3 Solved (Score:4, Informative)
What a mouthful! Us Perl programmers are, of course, lazy :)
cLive ;-)
Re:the 15-square puzzle (Score:1, Informative)
Re:Question 3 Solved (Score:2, Informative)
A good bonus question. Anyone who can answer it (or even would think to ask it) realizes how useless micro-optimizations like the XOR swap trick tend to be.
My answer, check me: an out-of-order processor does dependency analysis to form a partial order of the operations. Where there are no dependencies, some operations can be performed in parallel. The XOR swap method has a partial order length of 3. The temporary swap method has a partial order length of 2. Thus, the temporary swap method is faster. (Assuming the temporary is available and the processor can perform two operations in parallel.)
FULL SOLUTION (Score:4, Informative)
http://www.abysmalstudios.com/files/quzzlesolutio
although that will most certainly disapear in a while, as I clean up my server from time to time. In the interests of preserving history, I'll give you the excessively condensed version:
The goal is to move the A block in the far upper left corner, to the far upper right corner.
----
AA11
AA23
**23 - starting puzzle condition (* is a space)
4556
4778
----
The code below gives a block (1-8 or 'A') and an u/d/l/r direction.
AD1LL2U3U6UL3DD2R6UUAR4UU5L7L8LU7RR5D
You will have to break it up manually, because slashdots lameness filter wont even let me put line breaks in. Grab a copy of the text from my site while you can!
Re:the 15-square puzzle (Score:3, Informative)
Re:FULL SOLUTION (Score:3, Informative)
5RR6DR7L5L
The correct sequence is:
5RR6DL7L5L
Note that changes only one move from R to L.
Other than that, the solution works wonderfully
Re:Solutions to some of these... (Score:3, Informative)
Re:FULL SOLUTION (Score:3, Informative)
Despite that, the instructions were quite helpful. Thank you.
Play OriMazes in JavaScript (Score:2, Informative)
The hardest 4x4 instance can be played at
http://www.cwi.nl/~tromp/oriscript4.html [www.cwi.nl]
while the hardest 5x5 instance is at
http://www.cwi.nl/~tromp/oriscript5.html [www.cwi.nl]
-John
Re:Anyone Know (Score:2, Informative)
Re:the 15-square puzzle (Score:3, Informative)