Slashdot Mirror
Programming Puzzles
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."
Check these out that I found online, they're great things to use b4 interviews!
.... 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.
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 ]
Reply or e-mail; don't vaguely moderate. Ex-O'Reilly/MIT employee, now a full-time Google employee.
One version.
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?
i'm trying to give up sigs.
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.
Table-ized A.I.
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.
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".
Table-ized A.I.
Eh, I think it'd be more fun to play chess with Deep Blue. Heck, how fast do you think Deep Blue could solve it?
I am reminded that the "15" puzzle was set up to be impossibleby the inventor. As is stated on this page 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?
99 bottles of beer in 175 characte
A java version of this hardest version? It would be nice to preview the puzzle without the expense^W hassle of a plastic version.
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.
Without a proper flamewar, Anonymous was undecided on what shell to run.
You'd think he would have created a web version of this puzzle so we could all try it out. :/
The puzzle can be played here.
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.
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.
You can analyze puzzles like this using GAP. Here is an example using Rubik's cube(Google cache since the site seems down to be down at the moment.)
But if you really want to stump a slashdotter:
15. Go outside and meet girls.
Table-ized A.I.
ITA Software also has some great puzzles related to employment.
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.
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
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 :)
3 and 13 are the same..
My email addy? should be easy enough.
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.
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...)
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 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?
Main Entry: axis /-"sEz/
Pronunciation: 'ak-s&s
Function: noun
Inflected Form(s): plural axes
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
computers tend to use exhaustive methods to find solutions. Perhaps they should consult a mathmatician.
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!
A troll calling someone else a troll.
Humour, thy name is Slashdot.
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)
I have Unix underpants.
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.
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.
Check out my sci-fi/humor trilogy at PatriotsBooks.
This fails if A or B is zero because A * B will lose information.
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.
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.
Did Not Have Very Flesh Coder Troll?
|\
You suck |-\t it.
| \
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.
Check out my sci-fi/humor trilogy at PatriotsBooks.
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!
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.
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?
Check out my sci-fi/humor trilogy at PatriotsBooks.
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)
0 );}%c";
main(){printf(f,34,f,34,10);}
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,1
Regards,
Steve
"2. Recursion"
Okay, now how do you notice you're at the base case without an if statement? (?: is cheating too I think)
More efficiently:
5. could be this... much better btw. a = (a)+(a1)+(a2);
ruby -le"32.times{|y|print' '*(31-y),(0..y).map{|x|~y&x>0?'
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")) { } }
3 1 2 2 1 1
...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:
...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.
1 2 3 4
5 6 7 8
9 a b c
d f e
!! stupid formating!!! a = (a)+(a<<1)+(a<<2);
ruby -le"32.times{|y|print' '*(31-y),(0..y).map{|x|~y&x>0?'
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
312211
Yaz.
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")) { }
}
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?
Make me a friend and I'll mod you up
It is possible to do #2 without any explicit control structures, and without manually typing all the numbers from 1 to 100.
/ count.cpp
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
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.
how about:
a = (a3) - a;
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
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...
- Give a man a fire and he's warm for a day, but set him on fire and he's warm for the rest of his life.
1. 2. 3.
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.
Like all pain, suffering is a signal that something isn't right
yeah... just saw that lower on this page. nifty. Here is correct formatting ;)
a = (a<<3) - a;
ruby -le"32.times{|y|print' '*(31-y),(0..y).map{|x|~y&x>0?'
The pic in the article reminds me of Traffic, that awesomely addicting old Palm game (based on a real-world sliding block puzzle). I wish there was a PocketPC version!
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.
312211
?
It doesn't. It is simply a clever trick on the programmers part. Another quine, in perl is:9 ,$b,39;, $b,39;
$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
'if' is outlawed for #2. If you could use if, even without goto, it'd be much, much simpler than what you say.
... swap(x,y);" instead of just saying "std::swap(x,y);"?
And why do you go "using std::swap;
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
For number 11, it states you cannot just echo the source. :-(
Other then that, you are a flippin' genious.
"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.
simple offer them candy for their passwords!
All pretty intro puzzles. Btw if is not a loop, its a conditional statement.
[13. identical to 3]1 );puts("\000");}
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){printf("%d ",c);(c^100)&&a(c+1);}
b(int c){printf("%d ",c,(c^100)&&b(c+1));}
main(){a(1);puts("\n");b(
10:
d(int x){
int i;
i = x&1;
x&&d(x>>1);
printf("%d",i);
}
main(){
d(1234);
puts("");
}
11 can be generated by this prog:
main(){
char q[1]={34};
char x[3]={98,61,34};char y[3]={99,61,34};
char*a=
"main(){char q[1]={34};"
"char x[3]={98,61,34};char y[3]={99,61,34};"
"char*a=";
char*b=";char*";
char*c=
";"
"write(1,a,strlen(a));"
"write(1,q,1);"
"write(1,a,strlen(a));"
"write(1,q,1);"
"write(1,b,strlen(b));"
"write(1,x,3);"
"write(1,b,strlen(b));"
"write(1,q,1);"
"write(1,b,strlen(b));"
"write(1,y,3);"
"write(1,c,strlen(c));"
"write(1,q,1);"
"write(1,c,strlen(c));"
"}";
write(1,a,strlen(a));
write(1,q,1);
write(1,a,strlen(a));
write(1,q,1);
write(1,b,strlen(b));
write(1,x,3);
write(1,b,strlen(b));
write(1,q,1);
write(1,b,strlen(b));
write(1,y,3);
write(1,c,strlen(c));
write(1,q,1);
write(1,c,strlen(c));
}
--TheOrangeSquid Is it any wonder things seem so awry? We swim in a sea of confusion and don't have to think to survive
312211
I've seen that one before though. It's just taking the last one, and incrementing the numbers across so they are the same... Wow, it's hard to explain
alderaan 7% cat crap.c
#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%
#2 (Thewe two functions could probably be combined, but I'm not going to bother optimizing and factoring coe for Slashdot. This gives you the idea, at lesat:)
#include <stdio.h>
int printDown(int num)
{
return num ? (printf("%d ", num), printDown(num-1)) : 0;
}
int printUp(int num, int stop)
{
return (num <= stop) ? (printf("%d ", num), printUp(num+1, stop)) : 0;
}
int main(void)
{
printDown(100);
printf("\n");
printUp(1, 100);
printf("\n");
return 0;
}
#4: newNum = (num << 3) - num;
5) x= (x << 3)-x;
Snowden and Manning are heroes.
What's the difference between #3 and #13?
This idea is not new, the guy that runs www.puzzlebeast.com uses a similar program to generate ingenious puzzles. Read about the program he uses, then check our his java applets if you have a an hour or eight to spare.
sheep.horse - does not contain information on sheep or horses.
Though to be fair,
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.
Good points. I yield.
I have Unix underpants.
Shame on you for having . in your path.
What's the difference between #3 and #13?
-10
Just say it out loud to get the next line... 1 - one one 11 - two ones 21 - one one one two 1112 - three ones one two 3112 - one three two ones one two 132112 and so on..
add them and see if you get n(n-1)/2 ? easy enough...
I presume you're making a joke, but in case you aren't, soluble also means solvable. It's quite common to see it used that way in mathematical papers and journals.
1. Write a "Hello World" program in 'C' without using a semicolon.
You don't need a semicolon after a closing brace
2. Write a C++ program without using any loop (if, for, while etc) to print numbers from 1 to 100 and 100 to 1;
Use recursion instead of the loop. A pre-initialized increment is reverted once it reaches 100 (using a division)
This one is well known to people who write assembler code, simply use 3 XOR. Note that Q13 is the same. 4. C/C++ : Find if the given number is a power of 2.
A power of 2 has only one bit equal to 1. So the same number minus 1 has this bit set to zero, and all bits below set to 1. If you AND the two values, you get zero only if the number is a power of 2 or zero. 5. C/C++ : Multiply x by 7 without using multiplication (*) operator.
To multiply by anything without using a multiplication operator, do exactly as you would if you didn't have the 'mul' instruction on your
processor : binary shifts & adds. 7 == 4 + 2 + 1, so x*7 == x*4 + x*2 + x*1 6. C/C++ : Write a function in different ways that will return f(7) = 4 and f(4) = 7
Relation between 7 and 4 ? 7+4==11, 7^4==3, 7*4==28, etc... Note that other values give undefined results.Other questions take longer code and need real boring programming. Q10 is the same as Q5. I've seen a program which did Q11 once. The trick is *not* to lose time trying to put the program into a string, and instead, call a function which adds all necessary delimitors and escape where necessary. Q13 is Q3.
Have fun,
Willy
Nope.
Say you have [0,1,2,3]. They sum to 6 right enough, but so does [0,2,2,2].
for (i=0; i<n-1; i++) {ttl = val[i]; cmp += i;}
if (ttl != cmp) return true;
return false;
Check out my sci-fi/humor trilogy at PatriotsBooks.
Perhaps they are looking for a recursive solution.
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.
n integers, range 0 to n-1, means that, if there is a duplicate, there will be one missing. (but this would only help if the array were known to be sorted)
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, so there's some extra bits floating around anyway.
i hacked up something like this:
checkdup(int z[10]) {
int j, i;
for(i=0;i<10;++i) {
printf("%02d %02d %02d %02d %02d %02d %02d %02d %02d %02d\n",
z[0], z[1], z[2], z[3], z[4],
z[5], z[6], z[7], z[8], z[9]);
j = z[i];
if(j>=10)
j -= 10;
if(z[j]>=10)
return 1;
z[j] += 10;
}
return 0;
}
main(){
int a[10]={9,4,7,0,1,2,3,5,8,6};
int b[10]={2,9,5,7,2,0,8,4,3,1};
printf("%d %d\n", checkdup(a), checkdup(b));
}
--TheOrangeSquid Is it any wonder things seem so awry? We swim in a sea of confusion and don't have to think to survive
The point was to prove Russians are better than us?
In Soviet Russia, we are better than Russians!
Yeah, I'm still trying to figure it out too.
4. B. shoudl have said for (i=0; i<LONG_BITS; i++) printf...
Assuming a long int. Appropriate changes otherwise.
Check out my sci-fi/humor trilogy at PatriotsBooks.
>> 14. Given an array (group) of numbers write all the possible sub groups of this group.
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 }
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".
Check out my sci-fi/humor trilogy at PatriotsBooks.
Check out my sci-fi/humor trilogy at PatriotsBooks.
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.
Even those who arrange and design shrubberies are under considerable economic stress at this period in history.
I've worked through that solution, and writen up a much more aproachable version. Slashdots lameness filter prevents me from posting it in full, so I will link to it on my website here:n .txt
8 LLAD6DL2L3UU AR8RU5U7LLAD8RR2D1R4U6DL2L8LU3D1R2U6RR2D4D1LL8U3U6 UAU7RR5D2D6L8D1R4U2LAL3DD1R8R6R4R2UUAL6DD8L3U6RAR2 DD4L8LUAU6LL7U5RR6DR7L5L3DDAR8DD4R2UU8LD4D2D1LAU
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!
2.
#include <iostream>
using namespace std;
class incr
{
public:
incr ()
{
cout << i++ << endl;
}
~incr ()
{
cout << --i << endl;
}
private:
static int i;
};
int incr::i = 1;
int main ()
{
incr k[100] = {};
}
That works, but to put it in mathematical terms: each line is a run length encoding of the previous. (With the run length preceding the symbol, rather than following it.)
#include <stdio.h>
/* put printf here instead to count down */
void (*function[2])(int);
void print(int i)
{
printf("%d\n", i);
function[i / 100](i + 1);
}
void nop(int i)
{
}
int main(void)
{
function[0] = print;
function[1] = nop;
print(1);
return 0;
}
"[Regarding the 'cloud,'] ownership was what made America different than Russia." -- Woz
The question is: How did you solve 7?
11. Well, since C isn't a scripting language I don't see how that's possible.
It's very possible. It's called a quine. They're fascinating, and it's possible for programs to output themselves in all sorts of different interesting ways.
This page is a great resource.switch...case could work
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.
I have solved number 7. Just remove nr 3 and 13.
Write a "Hello World" program in 'C' without using a semicolon. I want to see this one.
;.
#include
int main () {printf("Hello World\n")}
Opps Gcc some modern version says where is the
"[Regarding the 'cloud,'] ownership was what made America different than Russia." -- Woz
Judging by actual research, the current AI approach would be to model the puzzles with a gaussian curve, then build a Bayesian network to find the most frustrating puzzle.
I Browse at +4 Flamebait
Open Source Sysadmin
oh well I've been told that's easy, (uh.. you dont have to get the girls to talk back, right??), now if I could only remember how to get this damn door open.
Lead me not into temptation... I can find it myself 8+)
Check out my sci-fi/humor trilogy at PatriotsBooks.
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.)
I was given a wooden puzzle very similar to this several years ago - it has the same layout and initial state as the puzzle that one reader calls 'Klotski' but I know it as 'Free The Prisoner'. A couple of my students coded it up in Java a few years ago - you can find it at: http://activation.braininavat.net/archives/000069. html
I always thought Microsofts favourite one was "Write an operating system without checking for buffer overflows".
I'm not sure I follow.. care to rephrase that, and I can reparse? ;)
O }={0,0,1}
O }={0,0,1}
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,
1+2+2+5+5=15
001,010,010,101,101={2,2,3}={E,E,
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, perhaps? It does seem like it's going in the right direction... maybe use an error-correction technique instead of a simple parity technique? =)
--TheOrangeSquid Is it any wonder things seem so awry? We swim in a sea of confusion and don't have to think to survive
Do it to one of them, and it's unsolvable -- do it to two and it's solvable again; there is a even/odd parity to the edge pieces so it's only unsolvable if an odd number of edge cubelets have been flipped from their starting state.
Whether or not the cube is solvable (even when mixed up) can be determined in a fairly straight-forward manner, but most people wouldn't bother to do this. In any case, once the cube is practically solved it becomes obvious when, of the last few edge cubelets to orient, an odd number need flipping.
Similarly, there is a modulo-3 parity involved with the corner piece orientation, and the total "twist" remains the same (at 0) when normally manipulating the cube, while randomly turning corner pieces could result in an unsolvable total twist of -1 or +1. In any case, there isn't anything "more" unsolvable that can be done by twisting multiple corners that couldn't be done by simply twisting a single corner cubelet either clockwise or counterclockwise. As with the edges, it's straight-forward but normally not worthwhile to determine ahead of time if the twist parity of the cube is what it should be, and it won't truly pose a problem until all of the corners have been properly oriented save one, at which point the tampering becomes obvious.
The Rubik's Cube (Rubik's, not Rubix -- named for Professor Erno Rubik, its inventor; he originally called it the Magic Cube but its name was changed to bear his when it started to get marketed worldwide) has a third form of parity involved that depends on the transposition of the corner and edge pieces. Swapping a single pair of edge pieces or a single pair of corners (but not both, or any even-numbered combination of pairs -- these are all solvable states) will result in the pieces of the cube not being able to be positioned properly, which is again annoying but obvious when the cube is mostly solved. One can determine if this is the case for some random cube, but I can't off the top of my head think of an algorithm that's as easy for a person to use as the ones for the other two cases.
So, to review: supposing you took a Rubik's Cube apart and assembled it back together at random, you have a 1/12 change of this random permutation being one that the puzzle could be solved from -- there's a 1/2 chance that the edge-orientation parity is even (otherwise, at the end it will look like a single edge has been flipped), a 1/3 chance of getting the corner-orientation parity correct (otherwise it will appear like a single corner has been twisted either clockwise or counterclockwise), and a 1/2 chance that the positions of the pieces are such that they can be place properly (otherwise, it will appear as if a single pair of corner or edge pieces have been swapped -- these two cases are equivalent and can be moved between)
I remember writing my first quine in basic on the commodore 64:
10 LIST
'For we walk by faith, not by sight.' II Corinthians 5:7
Xn means: move piece X with n squares.
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
My karma ran over your dogma
I don't suppose this would count as a quine?
test.c:1: error: syntax error before '.' token
Or what about:
'For we walk by faith, not by sight.' II Corinthians 5:7
Some things are just too simple to solve by a program. This is one of them. There are two states that the puzzle can be in, solvable or unsolvable. Any exchange of pieces changes that state. It might seem that there being 15 pieces rather than 16 has some effect on it and complicates things, but it doesn't. You get the exact same problem if you imagine that there are 16 pieces arranged randomly, and then that piece 16 is discarded before the puzzle is attempted to be solved. There is no preference at all for the solvable or unsolvable state when 16 pieces are put in a 4x4 matrix, so therefore there is no preference when 15 pieces and a blank space are put in a 4x4 matrix. So the solution, no matter how complex you make the computer program, will have to be 50%.
I'm an American. I love this country and the freedoms that we used to have.
It's worrying that more people *didn't* see this solution.
Similar to #5 above:
:). So, yes these exercises can help you get hired.
"Given a very simple microprocessor with no multiply, divide, or subtract instructions what algorithm would you use to implement an integer divide by 7? Assume that the microprocessor and your algorithm will be part of real-time process control system. Explain why you think your algorithm is a good choice for use in a real-time control system."
I suppose the goal of the question was to construct an algorithm without doing the simple O(n/m) version. They like my answer, and offered me the job
The hardest 4x4 instance can be played at
http://www.cwi.nl/~tromp/oriscript4.html
while the hardest 5x5 instance is at
http://www.cwi.nl/~tromp/oriscript5.html
-John
(How do you get indenting in here?) This swaps numbers in the array, with each swap putting at least one number such that array[i]==i. Each execution of the loop either swaps a number (max n times) or advances the index i (also max n times). The loop can thus never execute more than 2*n times, which is O(n).
Does anyone know if this guy has written a paper on the subject. It appears that his primary reason for doing this was as a piece of research, that just happened to produce a puzzle out of it. So, is there a paper?
Bob
I think most people would find this difficult because they forget how to program in these languages
Actually, only the questions 1 and 11 depend on syntactic knowledge of the language; the others are purely algorithmic, i.e. a valid answer could be described in plain English. And some questions, such as for instance 2 and 5 are downright trivial... Unless there is a hidden catch, or unless the goal of the questions is to test whether the candidate has chuzpa, rather than intelligence!
Funnily enough the recent Matlab comp was along these lines: Main Page. Given a number of unknown grids of boxes of different weights a program was needed to solve the rearrangement problem as efficiently as possible.
w00t arrays of functions & recursion
1 wasn't proper ANSI C. In ANSI C, main HAS TO return int. Picky teachers will "mod you down" for that.
int main(void){if (printf("Hello World!\n")){}}
(you left a parenthesis open)
That will teach ya.
You can write that and you can't get indenting!? ;-)
I don't know which is more horrible, your post, or the fact that someone modded you +1 insightful.
$ echo $PATH /usr/local/bin:.:/usr/bin:/usr/X11R6/bin:/bin:/usr /games:/opt/gnome/bin:/opt/kde3/bin:/usr/lib/java/ bin:.
Shame on me for having . in my path twice!
(SCNR)
Or as the Governor of Texas would say...:
1. ___
/
| 10 print "hello world"
\___
2.
#include <iostream>
int main() {
cout << "numbers from 1 to 100 and 100 to 1");
return 0;
}
3.
before: return 2+3;
after: return 3+2;
4.
int ispowerof2(float number) { return number>0; }
5.
x *= 7;
6.
int buf[8];
#define f [buf]
int function(void) {
return f(7)=4 && f(4)=7;
}
char *another(void) {
return "f(7)=4 and f(4)=7";
}
These kinds of sliding block puzzles have been around for a long, long time. He just picked one of the many possible designs for his plastic version using a software program.
The computer versions of these puzzles have been around for a long time and come with many levels. His particular design seems like a fairly regular collection of blocks, and some computer version probably already includes it as a level.
I hope switching the A's does not change make it possible again. I would guess it doesn't.
I have a similar puzzle at home. I was missing one 1x2 piece to build the pattern shown in the web site. I complemented it using a piece of paper.
It took me about 15 minutes of manual sliding to find a 29 moves solution. This is, by far, not the hardest form possible. Unless the picture they show on the web site is not it, I'm afraid this whole effort was in vain.
Shachar
The puzzle was popular because Sam Loyd offered a $1,000 prize for solving his sliding block puzzle, but the parity was broken because 14 & 15 were transposed. It was unsolvable. He sold lots of puzzles, and then bragged about his fraud. Those wacky victorians.
Assembly is the reverse of disassembly.
How about modifying an existing system with no time or budget and everchanging requirements. Oh, and the original developer did lots of cute little tricks like not using loops or temp variables.
THAT will get you a job.
The solution to the sliding block problems is actually fairly easy -- use an A* search. (Anyone having taken an AI course at the university level has probably coded just such a thing to solve just such a problem -- at least, I know I did.)
... oh ... at most 2 hours to cobble the code together.
I'd say that it would take about
This anonymous coward has no C/C++ skills, so many pardons if this isn't easily rewritten for those:
public class Countdown
{
public static void main(String args[])
{
Countdown c = new Countdown();
c.count(100);
}
public boolean count(int count)
{
System.out.println(count);
boolean uglyHack = (count > 1 && count(--count));
return uglyHack;
}
}
If it's any GOOD, on the other hand, is quite a different kettle of the old tea.
Seems like a perfect problem to solve via Constraint programming (which I happen to be taking a course in atm) ... Amazing stuff with the help of some magic, for example with OZ:
http://www.mozart-oz.org/documentation/fdt/
I played this old SNES game for the first time this summer, and it had this really tough puzzle near the end that I solved the first time using a walkthrough, but I thought it would be interesting to write a program that would find the shortest solution... and so I did! Source code and working java applet provided:
f f_ puzzle.html
http://homepage.mac.com/fahrenba/diff_puzzle/di
James Tiberius Kirk: "Spock, the women on your planet are logical. No other planet in the galaxy can make that claim."
More about quines than you ever wanted to know.
-30-
There was a thread about them on Perl Monks: http://perlmonks.org/?node_id=396259 .
No 11 is wrong. You wrote printf("an exact copy of the source". Given that you only wrote three lines of code, that should be pretty easy do, right?
The question is recursive. If you include the source in the printf statement, than you'd have to include the printf statement itself as well, together with the source...
I kind of had a look at it and managed to come up with this:
It should work OK in unix. Not sure about Windows. Not terribly elegant, I know. There's probably loads of better ways of doing it.
Other than that everything looks pretty good!!
At least for a computer. The scramble counting method used will result in lots of redundant positions. If you do a heuristic search, you'll never encounter redundant board configurations. The variable piece size will actually lower the effective branching factor for heuristic searches, since many moves that are feasible will generate infeasible children, and never again be visited. Also, since the ratio of open to occupied space is higher, you'll have a larger proportion of states where the branching factor is also diminished by the fact that the space is adjacent to a side of the board, meaning that no piece can fill it from that side.
I actually wrote a program that used a variety of searches and heuristics to solve the 15-puzzle (GBFS with the Manhattan Distance heuristic worked fastest, but gave less optimal answers than A*, obivously.) If I weren't in the middle of finals, I'd dust off that code and mangle it to do this to prove it.
My point is, while the puzzle shown may have a deeper and wider solution tree, by being smart, you can prune the width and avoid depth-increasing inefficiencies, so the less uniform structure actually help here.
WARNING: there is a trojan on your
I managed to come up with this after an hour or two:
There's probably loads of more elegant ways of doing it, though.Here's the thing. I can look at each example and see a solution. But how important is it to actually give the solution?
If you can't figure it out, how you reason through it is just as important to the interviewer.
Computer science has devolved into programming. Is the code that important, or the solution in regular syntax?
No, only 5% of C.S. jobs really require true C.S., the rest really are just programming jobs. And for the jobs that really do require C.S., I'm sure they'd far prefer a candidate who is not only good at the theory, but knows several programming languages inside out. (Good interviewers will let you choose one of several popular programming languages to use to answer most of your questions in.)
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
If the job involves mostly GUI programming, or server-side web app development, then this test is just nitpicky. But if the job involves writing device drivers in C, this test is totally fair. Someone who couldn't breeze their way through all of these questions would be exactly the type of person who would be likely to waste 2-3 days tracking down a silly bug involving idiosyncracies of the C language.
The hard version of #8 specifies that you can't use memory proportional to the size of the list, nor can you modify the contents of the list.
There's a slick way to handle this, which I'll write in the margin.
Oh, so it's not a case of programming your way out of a paper bag, you have to program your way out of your room/house. ;)
a^=(b^=a);b^=a;
(^ is the XOR operator)
You can be clever with shift operators, or just:
answer = x + x + x + x + x + x + x;
Now which could you have come up with faster?
"It's the height of ridiculousness to say for those 9 lines you get hundreds of millions."
James Tiberius Kirk: "Spock, the women on your planet are logical. No other planet in the galaxy can make that claim."
So the "T" in James T. Kirk stands for Tiberius. But what does the Tiberius stand for?
"It's the height of ridiculousness to say for those 9 lines you get hundreds of millions."
Can we use & n b s p ; here?
answer = (x 3) - x;
Slashdot: where don knuth is an idiot because he cant grasp the awesome power of php
I just cut out some wood blocks and tried to solve it and was able to in like under a minute.
It's not hard to see the solution , but this computer program had a hard time brute forcing it. Because it can't work towards a goal! and Can't eleminate obvious dead ends.
I am always doing that which I can not do, in order that I may learn how to do it. - Pablo Picasso
DOH!
Should have read:
answer = (x3) - x;
Foiled by the auto-formatting...
Slashdot: where don knuth is an idiot because he cant grasp the awesome power of php
#!/usr/bin/perl
@up, @down;
for($i=1; $i<=100; $i++)
{
push @up, $i;
push @down, 101 - $i;
}
$s = join(" ", @up) . " " . join(" ", @down);
open FILE, ">code.c";
print FILE <<EOF;
int main()
{
printf("$s\\n");
return 0;
}
EOF
close FILE;
1. main() { if (printf("hello world\n")){} }
2. main() { int i = 0; a: printf( "%d\n", ++i ); if (i < 100) goto a; b: printf( "%d\n", i-- ); if (i > 0) goto b; }
3 / 13. main() { int a = 65535; int b = 1453; printf( "a = %d, %b = %d\n", a, b ); swapbit( 0x0 ); swapbit( 0x1 ); swapbit( 0x2 ); swapbit( 0x3 ); swapbit( 0x4 ); swapbit( 0x5 ); swapbit( 0x6 ); swapbit( 0x7 ); swapbit( 0x8 ); swapbit( 0x9 ); swapbit( 0xa ); swapbit( 0xb ); swapbit( 0xc ); swapbit( 0xd ); swapbit( 0xe ); swapbit( 0xf ); printf( "a = %d, %b = %d\n", a, b ); }
4. main() { int a = 65535; while (a) { if (a & 1) { if (a != 1) printf( "not a power of two\n" ); else printf( "is a power of two\n" ); break; } a >>= 1; } }
These bore me, but I already have a job so I guess it doesn't matter.
Is it wrong if I came up with "x + (x1) + (x2)" faster than x+x+x+x+x+x+x?
Yeah, there should be shifts in there... x + x<<1 + x<<2
nosemi.c:1: void value not ignored as it ought to be
Unless you're treating warnings as errors, the following will work in GCC:
But if you're turning on all warnings and treating them as errors (as one would in C++), then you'll also get a warning about missing the prototype for puts() and exit(). You'll need to include stdio.h and stdlib.h, making it a three-liner. Anyway, this compiles without errors or warnings in gcc -Wall -W:
Try recursion instead
The ability to iterate using recursion without eating up the stack is an implementation quality issue, as ISO C does not require a compiler to optimize tail calls the way all Scheme compilers and interpreters must. Do the last few versions of Microsoft Visual C++ optimize tail calls? Does GCC 3.4.x (which apparently does) support the target platform?
I think this'll work:
char q = '"'; char *body = "int main(void) {printf(fmt, q, q, body, q, q, fmt, q, body); return 0;}"; char *fmt = "char q = '%c';char *body = %c%s%c;char *f = %c%s%c;%s"; int main(void) {printf(fmt, q, q, body, q, q, fmt, q, body); return 0;}
number 9 cant u just select unique rows import it to another table ? more like DISTINCT ( but i dont think access can do DISTINCT though i am not sure,
http://iesucks.org
I suspect the real way to set this problem up for a user would be to leave the word RATE on the top line, or at least RAT, but to be sure that you swapped one and only one of the first two tiles when you did this. Or to leave it so very close to that solution that the user would likely make one move and be there (for example a top line of Y R A T and a second line of [space] [something ] [something] R, with the intended incorrect R and A in each position). But the way that you set the problem up just does not work.
I'm an American. I love this country and the freedoms that we used to have.
Umm... your first example won't actually compile, and is therefore not a program. The second example is actually the shortest possible quine, and won the Obfuscated C Code contest in 1994.
These have as much relevance to real world programming as keepie-uppie does to an actual game of soccer.
1/3 of jokes get modded OT. If you get the joke, mod 1 in 3 insightful/interesting/underrated to restore karma balance.
Dude, you really need to take a second and try out the "Preview" button.
Patrick Doyle
I mod down every jackass who puts his moderation policy in his sig. Oh, wait a sec....
In Soviet Russia, a dictionary should consult you!!!
1/3 of jokes get modded OT. If you get the joke, mod 1 in 3 insightful/interesting/underrated to restore karma balance.
The guy wrote a program to design the puzzle, not to solve it.
Patrick Doyle
I mod down every jackass who puts his moderation policy in his sig. Oh, wait a sec....
...But you almost certainly did it wrong. Solving this in under a minute would require you to do more than one move per second with no errors.
Patrick Doyle
I mod down every jackass who puts his moderation policy in his sig. Oh, wait a sec....
Until B == 0.
try:
A = A + B
B = A - B
A = A - B
(but that's just xor with some superfluous carrying)
Computing something more complex might work, but all the schemes I can think of require arbitrary-size numbers. For example you could take the sum of 2^elt, effectively creating a bitstring; but that requires N bits.
So how about reusing the solution that you didn't like: Sort. Return "duplicate" if you find a duplicate entry while sorting. Given the problem's constraints, the array can be sorted in O(n) time using something like an in-place radix sort.
The inner loop is entered once per cycle within the permutation, and runs for the length of the cycle. The sum of the cycle lengths is N; thus the algorithm is O(n) even though it may not look like it at first glance.
Did you know that if you can truly "solve" the 15-square puzzle, you can win a million bucks? No joke. The 15-square puzzle is actually NP-complete. I'll spare the details, but basically, it's not known whether or not the puzzle (or any other NP-complete problem) can be solved in polynomial time. If you can write an algorithm that solves the puzzle in polynomial time (or prove that it can't be done) then you win the million bucks offered by the Clay Mathematics Institute. They call it a "Mellinium Prize." It's one of seven unanswered questions in mathematics, and each of them is worth a million bucks. Good luck...
I can't even figure out the "Two Bent Nails" puzzle...
http://www.puzzles.com/PuzzleLinks/NickBaxter'sSli dingBlockPuzzles.html
Great stuff and Nick was on the ANSI X3H2 Database Standards Committee about a million years ago. There are some other contributors there also.
--CELKO--
A general solution can be written for any (n^k)-1 puzzle using the A* algorithm. To implement A* you calculate the value of your state, and the value of each successive state. The possible successive state that gets you closest to the goal state is the state you move to next. You keep track of all visited states, so you don't keep following paths that don't reach your goal.
With a 15-puzzle, you can develop a heuristic that allows you to determine how far you are away from the goal, as well as how far each successive state is from the goal. With the same algorithm you can extend your solution to solve any (n^k)-1 puzzle.
This was actually a programming assignment in a previous class of mine. We had to implement A* and then use it to solve (n^k)-1, missionary-and-cannibal, and the shortest path problem. (and if you're interested and/or masochistic, check out the other projects that we had to complete in the space of a semester)
No, Thursday's out. How about never - is never good for you?
A bunch of people who are clearly too smart to bother reading the instructions have managed to move it to the bottom right which is indeed trivial. Has anyone actually solved the thing themselves? Can you give us a screenshot of the completed puzzle from http://www.puzzleworld.org/SlidingBlockPuzzles/quz zle.htm?
I've been messing around with it on and off for a couple of hours and damned if I can get there - so close and yet so far ...
Whipped up a solution finder. Here's the result.
# 7:2#0: 1#6:2#3:0#6:2#: 3#7:3#7:0#4:0#5: 2#5:2#0:1#8:1#: 1#8:1#7:1#6:2#6: 2#0:0#5:0#4:3#: 3#8:3#7:3#1:0#1: 0#4:2#5:2#8:1#: 3#1:1#5:2#7:1#8: 2#7:1#0:2#2:0#: 0#8:2#0:2#7:0#7: 0#3:2#2:1#2:1#: 3#5:1#6:2#6:2#8: 0#5:3#1:0#8:3#
Pieces numbered scan order as 0, 1, 4, 5, 6, 2, 7, 3, 8. 0 is left, 1 is right, 2 is up, 3 is down. Moves counted one grid pos at a time - there may well be a shorter one under different move metrics. Kinda neat that big square piece visits all corners on way to finish.
Not that anyone's impressed or anything - pretty easy to write a solver for this sort of puzzle in terms of 64 bit bit-ops. Is there anything in particular about Haskel that's good for this kind of thing?
Solution found on level 115.
0:3#1:0#1:0#4:2#5:2#7:2#7:0#5:3#5:3#4:1#7:2
2:0#8:0#8:2#3:1#3:1#2:3#8:0#8:0#0
6:3#7:0#8:2#8:2#0:0#5:3#5:3#4:1#1
1:1#7:2#8:0#5:2#3:2#2:1#2:1#0:3#6
7:3#8:1#5:3#1:1#6:2#7:0#5:0#8:0#4
2:0#3:3#7:3#7:1#0:1#6:3#6:3#5:0#8
7:3#3:0#4:3#7:0#2:0#4:3#0:1#8:3#8
6:3#1:0#0:2#
done looking - minSolution is 115.
I knew things were bad when the Sam & Max sequel was cancelled, but this...
Feeling so good natured I could drool
The puzzle actually looked really easy, but I was having a hard time visualizing it so I used my sons MegaBlocks(tm) to work it out.
Key: (blocks numbered 1-9 starting upper left, to bottom right)
1 2x2
2 1x2
3 2x1
4 2x1
5 2x1 (bottom left)
6 1x2
7 1x1
8 1x2 (bottom center)
9 1x1 (bottom right)
> left >> double left
< right << double right
^ up ^^ double up
v down vv double down
1 v
2 <
3 ^
4 ^
7 ^
7 <
4 vv
3 >
7 ^^
1 >
5 ^^
6 <
8 <
9 <
9 ^
8 >>
6 v
9 <<
1 v
7 v
7 <
3 <
4 ^^
1 >
9 >
9 ^
6 ^
8 <<
1 v
In the end it took longer to type this up than it took me to solve this. The 15x15 is much harder in my opinion.
We've put together a graph 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 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.
Believing something doesn't make it true. Not believing something doesn't make it false.
they're great things to use b4 interviews!
"b4"? Please. Go back to AOL.
Also, you might want to RTFA, or even RTF write up, because this has nothing to do with programming exercises.
This is paraphrased from _The Zen of Programming_, a semi-humorous book of some note. The CEO of a game company hires a consultant to design the world's most difficult picture puzzle. After thinking about it for some time, the consultant does as he is asked and returns to the CEO's office. He brings with him a box full of pieces, which he dumps on the CEO's desk. The consultant explains that there are two ways to make a picture puzzle difficult. The first is to make the shapes similar, and the second is to make the colors similar. The consultant has done both, making the shapes the same and the colors the same. The CEO exclaims, "But these are just a bunch of identical black squares -- a child could put this together!" "Such as it is in life," the consultant continues, "Often the most difficult puzzles are the easiest to solve."
Puzzle 3: a+=b; b=a-b; a-=b;
6. C/C++ : Write a function in different ways that will return f(7) = 4 and f(4) = 7
int f(int x) {
return (11-x);
}
Didn't see anybody answer 8. Here's a solution (it's not c++ specific or anything, more of a data structures problem): Create two instances of the linked list, and start going through the list at different rates (for example, iterate twice on the first list for every time you iterate once on the second list, if that makes sense). If either one ends, it clearly has no loop. If they intersect (ie. both point to the same element in the linked list) then there is a loop.
This C solution uses no control structures, loops, templates, conditionals, ? operator, or shortcut evaluation of logical operators to accomplish this. I could use just one printf if I wanted, but this is supposed to be fairly clear. It works if you reverse the array and remove the == operator, but I think switchptr is more robust as written.
void * switchptr(int condition, void * trueptr, void * falseptr) {
void * ptrarray[2];
ptrarray[0] = trueptr;
ptrarray[1] = falseptr;
return ptrarray[condition == 0];
}
int stopnums(int num, int max) {
return 0;
}
int printnums(int num, int max) {
int (*nextfun) (int, int);
printf("%i\n", num);
nextfun = switchptr( num >= max, &stopnums, &printnums);
nextfun(num + 1, max);
printf("%i\n", num);
return 0;
}
int main () {
return printnums(1, 100);
}
Why do multiplies when you can just as easily do
A = A+B
B = A-B
A = A-B
Kelerain describes 32 optimal solution paths, but there are actually 1152 possible paths to a solution in 84 moves. First, there are four possible ways to do the first 21 moves:
Then there are two variants for moves 22-63, each of which can be done in 36 ways. Variant a is
and Variant b isNote that Variant b arrives at a position that looks the same as the end of Variant a, but has blocks 2, 3, and 4 in the positions used by blocks 3, 4, and 2 in Variant a, respectively. The remainder is annotated for for Variant b.
Moves 64-84 can be done in four possible ways:
Note that the goal position is the (left-to-right) mirror image of the start, so solving the puzzle in reverse is the same as solving the puzzle in a mirror. Variant A is the mirror image of the reverse of Variant B.
Dan Hoey <haoyuep@aol.com>
Some people just can't leave a puzzle alone. Kudos! :)
I visited this puzzle-maker's site (quirkle.com) and discovered the super-high-power magnet set, called 'Quagnet', and bought two of them for holiday presents.
:-)
Okay, here's the deal: while the magnets are easily as powerful as described, they're too powerful for their own good! I'm serious. In about 5 minutes of playing with these things, two of the magnetic disks simply broke apart (one while I was trying to separate a magnet from the stack, the other during a playful pick-up from a distance of about 4-5 inches).
Anyone else buy these things as gifts? I mean, very cool in its own right but not so durable. Also, the d*mn things PINCH your fingers/skin whenever they snap together. A single pinch is just a minor annoyance but when it keeps happening over and over again (as it did with my set) it really starts to hurt.
I had bought these for a 12-year old girl and a 13-year old girl. Not gonna happen now. In fact, I did an on-the-sly inquiry of the 13-year old, telling her it was really a gift for her 10-year old brother and, by the way, what did she think?
Her response? "They're too powerful for him; he'll probably get hurt." So I asked her, ever so casually, "What about you? If I had bought these for you, do you think you'd enjoy them?" She answered, "No, they scare me."
C'est la vie!
Richard (aka Merwyck, aka QuaDZeRo) I blog at http://richardharlos.com