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)
high return rate (Score:3, Insightful)
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 (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:plurals don't end in 'i' in English (Score:2)
(The Rubik's Cube has not two but three axes.)
Furhtermore, the existence of thousands of University campii throughout the world leads me to believe you might benefit from attending one.
Rubik's Cube (Score:2)
I do believe that some people would understand how to solve the Rubik
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 a
Re:Rubik's Cube (Score:2)
If you don't really like puzzles, you're right.
When I bought my Rubik's Cube (was that in '82?), it was because it was a complete enigma to me.
I simply had to have it because I did not understand it one bit.
Then I just started to turn, and turn, and turn, and gradually I started recognizing patterns in what specific com
the 15-square puzzle (Score:5, Interesting)
Re:the 15-square puzzle (Score:3, Funny)
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 be
Re:the 15-square puzzle (Score:2)
Or give a couple of the corner pieces a clockwise rotation. That's even more evil.
Re:the 15-square puzzle (Score:3, Funny)
If you swap the labels on two pieces it could make it unsolvable.
I'm looking at my Rubix Cube now and I'm noticing that a couple of the labels aren't on straight. Hmmmm....
Either this means that manufacturing standards are low enough that you probably wouldn't notice this type of hoaxing, or it means that someone has already done it to my Rubix cube and I still haven't noticed.
Re:the 15-square puzzle (Score:5, Interesting)
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.
Re:the 15-square puzzle (Score:3, Informative)
Re:the 15-square puzzle (Score:3, Insightful)
For this to work right, you also have to color the squares in a checkerboard pattern, like the old plastic ones I used to have. Then the two R's are the same color, but the two A's are not. So if your victim uses the other A, the puzzle still won't look right
Re:the 15-square puzzle (Score:3, Informative)
Re:the 15-square puzzle (Score:2)
The "15" Puzzle (Score:4, Interesting)
Re:The "15" Puzzle (Score:2)
is the curve allowed to cross itself?
Re:The "15" Puzzle (Score:2)
green assumes each line counts only once, red and blue count each intersection as breaking a segment into two parts.
Flash/Java... version of this puzzle? (Score:2, Informative)
You can play it here (Score:5, Informative)
Re:You can play it here (Score:2, Informative)
Unfortunately, reading the solution is almost a puzzle intself.
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: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:FULL SOLUTION (Score:2, Funny)
lets see if i can reproduce it here for people.
AD...1L...1L...2U...3U...6U...6U...3D...
It's amazing what you can learn playing the 11th Hour
Re:FULL SOLUTION (Score:2)
Re:FULL SOLUTION (Score:3, Informative)
Despite that, the instructions were quite helpful. Thank you.
Re:You can play it here (Score:2)
Re:You can play it here (Score:2)
Whats so special? (Score:3, Insightful)
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? (Score:3, Insightful)
What's so current about A*? (Score:2)
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?
one related puzzle I remember (Score:2)
Man I remember messing with that in the labs at school (back when they had macs) instead of doing work.
Traffic (Score:3, Informative)
More computer assisted puzzles (Score:3, Informative)
Re:I will help YOU get a JOB! (Programming puzzles (Score:4, Informative)
Re:I will help YOU get a JOB! (Programming puzzles (Score:3, Funny)
15. Go outside and meet girls.
Re:I will help YOU get a JOB! (Programming puzzles (Score:2)
Oh but that one is easy. Go downtown and get a hooker! It decreases the rejection rate from 100% to a more managable 82%, for me anyway.
Re:I will help YOU get a JOB! (Programming puzzles (Score:4, Interesting)
Re:I will help YOU get a JOB! (Programming puzzles (Score:3, Insightful)
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 (Score:2)
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.
Re:Question 3 Solved (Score:2, Interesting)
a ^= b ^= a ^= b;
or
#define SWAP(a,b) (a^=b^=a^=b);
Re:Question 3 Solved (Score:2)
Re:Question 3 Solved (Score:3, Insightful)
Re:Question 3 Solved (Score:3, Insightful)
Re:Question 3 Solved (Score:2)
Re:Question 3 Solved (Score:2)
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:Question 3 Solved (alternative method) (Score:3, Informative)
Re:Question 3 Solved (Score:4, Informative)
What a mouthful! Us Perl programmers are, of course, lazy :)
cLive ;-)
Re:Question 3 Solved (Score:2)
Why would the XOR swap method run slower than the TMP register method on an out of order processor?
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 t
Re:Question 3 Solved (Score:2)
Easy C++ solution (Score:2)
And before you complain about any alleged use of variables, 'temp' is a constant ;-)
And unlike those oh-so-clever xor based solutions, this one works for any type that supports assignment (including floating point numbers and classes that have operator= overloaded).
Plus, you can actually expect to be able to understand it in five years time when you do to some maintenance on the code.
Re:Question 3 Solved (Score:2)
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.
Re:Question 3 Solved (Score:2)
x -= b
b += a
a = b-a
With your 3 and -4:
3 -4 (start)
7 -4 (after x-=b)
7 3 (after b+=a)
-4 3 (a = b-a)
I think if there's no overflow it'll work. Even if there is, as long as it doesn't trap and just rolls over to the opposite sign, I think it'd be okay.
Re:Question 3 Solved (Score:2)
Re:Use only subtraction and addition (Score:2)
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:Use only subtraction and addition (Score:3, Insightful)
Maybe the people who start generating code without properly understanding and defining the problem to be solved don't get the job? Who wants a programmer who jumps into code-writing as the first step of design?
Two *REAL* solutions to #2 (Score:2)
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-
Another... (Score:2)
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.
Re:Two *REAL* solutions to #2 (Score:2)
You don't need to actually use the result of the ?: operator in order to use it as a control structure. (You do need to provide it with expressions which have the same type; this is why printnum() returns int and not void.) If ?: is too close to 'if',
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...
Re:Solutions to some of these... (Score:2)
Re:Solutions to some of these... (Score:2)
Try recursion instead....
Any programmer, let alone computer scientist, who hardcodes a list of values that is otherwise easily constructed programmatically should be drug out into the street and shot. Trust me -- I once worked at a small dot-com company where the CTO(!!) literally did not understand the concept of a loop. He'd copy a
Re:Solutions to some of these... (Score:3, Informative)
Re:I will help YOU get a JOB! (Programming puzzles (Score:2)
#2 solution (Score:2)
void print_down(int base)
{
if (base == 0) {
return;
} else {
printf("%d\n", base);
print_down(base - 1);
}
}
Hmmm, no conditionals?
Then you're asking for a C++ template solution. You can get templates to evaluate conditionals at compile time to generate the correct code. This makes my head hurt.
Re:I will help YOU get a JOB! (Programming puzzles (Score:2)
There are 2^N sub-groups in an array of N elements (inluding the NULL group). There is a 1-to-1 mapping from the binary represenatation of all numbers from 0 to (2^N)-1.
Let's say our array has 3 elements
1 2 3
The subsets are
000 = { x x x }
001 = { x x 3 }
010 = { x 2 x }
011 = { x 2 3 }
100 = { 1 x x }
101 = { 1 x 3 }
110 = { 1 2 x }
111 = { 1 2 3 }
Re:I will help YOU get a JOB! (Programming puzzles (Score:2)
Just looking through that list, some of those questions strike me as quite clever (#2/4) whereas others strike me as pure syntatical trickery (#1) or truly bad coding practices (#3/13, for instance).
I don't know how I'd judge the results of #3/13. They're clever, but they've done something that I never want to see in code. (Okay, okay... there are some exceptions, but in general it's true.)
Re:I will help YOU get a JOB! (Programming puzzles (Score:2, Insightful)
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 (Score:2)
8. this is just graph traversal; keep track of all visited nodes (mark them, or make your own list of them)
7. nearly same technique as #8, but with just the numbers
12 involves a bit of work, but doesn't sound difficult. just keep careful track of everything.
14 is ambiguous... is this an unordered set? or an order-critical list? the list is slightly easier, but, the set subgroups can be generated from the list subgroups by ordering each subgroup and removing duplicate ones.
2:
a(int c){prin
Re:I will help YOU get a JOB! (Programming puzzles (Score:2)
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 xo
Re:I will help YOU get a JOB! (Programming puzzles (Score:2)
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 (Score:2)
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 (Score:2)
for (i=0; i<n-1; i++) {ttl = val[i]; cmp += i;}
if (ttl != cmp) return true;
return false;
Re:I will help YOU get a JOB! (Programming puzzles (Score:2)
Re:I will help YOU get a JOB! (Programming puzzles (Score:2)
it also means that any value in the array will also be a valid index into the array. we can flag the values we find by marking the equivalent position in the array by adding N. if we find a position is >=N when we go to add N to it, we must have had a duplicate. in a way, this does use extra storage, but, we'll assume we aren't going from 0 to MAXUINT
Re:I will help YOU get a JOB! (Programming puzzles (Score:2)
Or it could just be the sleep deprivation talking. Anybody?
Re:I will help YOU get a JOB! (Programming puzzles (Score:2)
But, as I understand it, it sounds like a good idea, but, I'm not sure it would work:
1+2+3+4+5=15
001,010,011,100,101={2,2,3}={E,E, O }={0,0,1}
1+2+2+5+5=15
001,010,010,101,101={2,2,3}={E,E,O }={0,0,1}
As long as a bitwise carry doesn't occur when modifying two values by some +Z and -Z, respectively, the XOR trick will always fail to detect a change (like a parity error where two bits flip).
There might be a similar technique that would work
Re:I will help YOU get a JOB! (Programming puzzles (Score:2)
Say you have [0,1,2,3]. They sum to 6 right enough, but so does [0,2,2,2].
Re:I will help YOU get a JOB! (Programming puzzles (Score:2)
4. B. shoudl have said for (i=0; i<LONG_BITS; i++) printf...
Assuming a long int. Appropriate changes otherwise.
Re:I will help YOU get a JOB! (Programming puzzles (Score:2)
Besides, it said I couldn't echo the source -file-, and by 'echo', I assume they meant cat, since echoing the source file would probably result in something resembling stupid_problem.c[newline]. Either way, echoing "the source file" wouldn't make the output be "an exact copy of the source".
Re:I will help YOU get a JOB! (Programming puzzles (Score:2)
Re:I will help YOU get a JOB! (Programming puzzles (Score:2)
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 (Score:2)
312211
Yaz.
Re:I will help YOU get a JOB! (Programming puzzles (Score:2)
More efficiently:
Re:I will help YOU get a JOB! (Programming puzzles (Score:2, Informative)
#include <stdio.h>
int main()
{
if (printf("Hello, world\n")) { }
}
Re:I will help YOU get a JOB! (Programming puzzles (Score:2)
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 9
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 a
Re:I will help YOU get a JOB! (Programming puzzles (Score:2)
#include <stdio.h>
int main ()
{
if(printf("Hello World\n")) {}
}
alderaan 8% gcc crap.c
alderaan 9% a.out
Hello World
alderaan 10% gcc --version
gcc (GCC) 3.3
Copyright (C) 2003 Free Software Foundation, Inc.
This is free software; see the source for copying conditions. There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
alderaan 11%
Re:I will help YOU get a JOB! (Programming puzzles (Score:2)
alderaan 2% gcc -Wall crap.c
crap.c: In function `main':
crap.c:6: warning: control reaches end of non-void function
alderaan 3%
Didn't think to compile with -Wall.
Re:I will help YOU get a JOB! (Programming puzzles (Score:2)
Number one revisited (Score:2)
Re:Solutions for Questions 1-6 (Score:2)
Re:this was my first assignment at uni (Score:2)
Re:this was my first assignment at uni (Score:2)
(define (solve grid)
(return-whichever-grid-is-solved
(solve (slide-hole-up grid))
(solve (slide-hole-down grid))
(solve (slide-hole-left grid))
(solve (slide-hole-right grid))))
slow, but, works (i think?).
you can squeeze it all into one function using lambda and let.