wolfsinner

So I've got a few things to inform everyone of. If you're an active participant in the Problem Solving thing, intend to become active, or just read this out of curiosity, I'd appreciate it if you "like" this post so that I know who's been informed.
 
First of all, I just added Problem #5, so there's that.
Second, I'll be travelling during most of the month of August (I "take off" this Monday) and as such I won't be as active as I'd want to be in the forums. That also means it'll be much harder for me to put out a problem every week. I'll still try to post at least one during the month of August, but I can't guarantee anything. I'll return to my regular "routine" in September. If someone is interested in replacing me while I'm gone, please PM me so we can talk about it.
 
Lastly, I just want to share a few things about the gateway itself. I've been working on a system that actually runs your code and compares its output to the correct output in the server. So you'd post your code at the gateway and everything is tested for you. This will allow me to add a few things like:
Time limits for run-time. Memory limit constraints. Automatic testing and compiling. Users being able to see other's "successful" code, once they've solved the problem themselves. Perhaps a point system for grading the quality of a solution automatically. Anyway, I was hoping I would have it done by now, but I didn't have enough time. It's a delicate process since I need to make sure the processes are properly isolated, limited and secure. I'll continue working on it when I come back.
 
And that's it. I hope when I get back to my "routine" you guys are still active and interested in this initiative.

This topic will serve as an index, or listing, of all the problems that are a part of the Problem Solving series I've been doing. This way they won't get lost.
Somewhere in the near future I'll write a few "Problem Solving basics" articles where I explain a few techniques used in solving problems (graphs, combinatorial optimization, time complexity, etc), those will also be listed here.
 
Problems
 
Problem #1 - Deletable Primes (Discussion | Gateway)
Problem #2 - Sharing is Caring (Discussion | Gateway)
Problem #3 - Polygon Phobia (Discussion | Gateway)
Problem #4 - Lego Mosaics (Discussion | Gateway)
Problem #5 - User-Friendly Manuals (Discussion | Gateway)
Problem #6/7 - Solving the N-Puzzle (Discussion | Gateway (C <= 3) | Gateway (15-Puzzle))
 
Articles
 
None.
 
 
 
If you have any suggestions for problems, articles, or would like to contribute in some other way to the series, this is the place to say it (or via PM to me).

Alright, a few tips. If you're a beginner, start by finding all of the primes in the interval [0, 10000000]. A simple, yet efficient enough for this, algorithm for that is the Sieve of Eratosthenes. It can easily be implemented using an array of booleans (preferably), and a loop.
Pseudo-code for a simple implementation:
boolean primes[10000000];boolean checked[10000000];for each integer i in [2, 9999999] dobegin   if not checked[i] then      prime[i] = true; //i is prime      for each integer k multiple of i < 10000000 do         checked[k] = true;end//after the main loop, you can check if a number is prime by accessing prime[n] and checking if it is true Once you can check all of the primes in that interval, it is a matter of going through the numbers that are prime, and working on code to remove single digits from a number and testing those for primality. I can help with this part, but first try implementing the Sieve.

Problem #6/7 - Solving the N-Puzzle
 
So here's Problem #6 and #7 of the series. This is a two-parter, where #6 has easier test cases than #7.
I'm back, and with a vengeance. This is a problem classified as NP-Hard. However, it is so famous that there's great documentation out there for it.
The solution I wrote for this uses a very famous Artificial Intelligence search algorithm. This can be solved in many ways though, albeit many of them are very inefficient. 
I hope you guys enjoy this one, and thrive on the difficulty. Knowing how to solve this efficiently is an immensely useful skill. On to the problem!
 
Problem Description:
 
A classic problem in Computer Science is to find the answer to the following question:  Given an initial and final setup of an N-Puzzle of size CxC (where C = sqrt(N+1)), find the minimum number of steps required to get from the initial to the final setup.   For example, given the following initial and final set ups of a 8-Puzzle:     A minimum of 26 steps are required to reach the final setup. Your task is to find this value. Note that there isn't a standard "final state".   All of the given tests are solvable.  
Input:
 
(You can download the zip file containing all of the input files here.)   The first line of the input contains an integer, C (an indicative of the size of the puzzle, CxC). The following C lines each contain C integers, representing the initial setup of the puzzle. Each integer is separated by a space. The next C lines each contain C integers, representing the final setup of the puzzle. Each integer is separated by a space.   These integers are a number in the range 0-[(CxC)-1], where 0 represents the "empty" space.   Input example   3 7 2 4 5 0 6 8 3 1 0 1 2 3 4 5 6 7 8  
Output:
The output consists of a single integer representing the minimum amount of steps required to reach the final setup, from the initial setup. The output must end with a line break.   Output example 26    
How to test your solution:
To submit your output solutions you need to run your code with each of the input files provided in the zip file, and place your output in the appropriate text box.
So your program's output with input from file "input1.txt" should be placed in the "Output 1" box.
 
I recommend downloading the zip file, and using command-line input redirection to send the file contents into the standard input stream of your program, and the output into the standard output stream. In Windows, Linux or Mac OS, you would do something like:
[command to run your program] < inputN.txt > outputN.txt
You can submit your output solutions through the problem solving gateway here.
 
Final notes:
Create your account at the gateway with the same username as the one you use at the forums. Include your code in spoiler tags, so that the thread isn't cluttered with code. If you're having trouble solving the problem, ask the community for help! You may learn a lot from them. Don't worry too much about efficiency if you're starting out. Solve the problem first, we'll then tell you how to improve it. Please don't share the output solution if you've solved the problem. If the problem description isn't clear, please ask for further explanation!

OK. Good looking out. It's a start. Here's a quick rundown of how a floating point value is represented with IEEE 754 (let's see single precision, double is similar). I'll try not to be confusing.
A single precision floating point is 4 bytes, which makes it a 32-bit representation. The general representation of a floating point is scientific notation in the form of (-1)signal * 1.mantissa * 2exp.
Remember that a bit may hold 0 or 1.
 
The bit distribution is as follows:
[s][eeeeeeee][mmmmmmmmmmmmmmmmmmmmmmm]
 
[s] - Represents the signal of the number (0 is positive, 1 is negative). 1 bit
[eeeeeeee] - Exponent portion of the number. This is calculated with a -127 excess (we'll see what this means below). 8 bits (can represent a number as high as 28-1 = 255)
[mmmmmmmmmmmmmmmmmmmmmmm] - The mantissa portion of the number. This is the fractional part of your real number. 23 bits
 
Let's take a look at an example:
[0] [01101000] [10101010100001101000010]
 
First of all, it is clear that this is a positive number (the signal bit is 0).
Next up, the exponent has a value of 01101000, which means that it represents 104 in decimal1. The reason for the -127 excess, is so that you can represent numbers in [-127,128]. This way it is possible to represent negative and positive exponents (for really big and really small numbers).
So this exponent is in fact 104-127 = -23.
 
Finally, the mantissa (the troublemaker). Conversion is (naturally) done this way. I assume you know your math and understand why we're using negative exponents. :P
Right to left, -1 to -n. So, in this case:
1*2-1 + 0*2-2 + .... + 0*2-22 = 0.666115.
 
As I mentioned previously, the general form of this standard is (-1)signal * 1.mantissa * 2exp. So my example number effectively represents 1.666115 * 2-23, which is roughly 1.986 * 10-7.
That is a simple explanation of how you would convert FP to decimal. Now, consider the following 2 representations:
 
0 01111010 01001111110111110011110 = 0.041 (this is the result of assigning this value to a variable)
+       -5                      0.312
 
0 01111010 01001111110111110011101 = 1.3118778 * 2-5 = 0.04099618125 ~= 0.041 (this is the result of adding 0.001 to a variable with 0.04)
+       -5                     0.3118778
 
The reason why this approximation is done, is pretty well explained in point 3 of that link you found. The final mantissa bits are approximations, rather than precise numerics (the only numbers that you can represent precisely are numbers which can be represented by fractions with a 2n denominator).
Now, if you are curious and want to understand why that's the result of this sum, go check out how to calculate floating point arithmetic. Also, a quick Google search brought this up.
 
Good luck! 
 
TL;DR: Never use floating point values for arithmetic when you'll need to compare them. This is why any (decent) programming teacher will tell you never to use floating point variables to handle things like bank balances. Most of them don't know why, but it's still good advice. :)
 
________________________________________________________________________________
1 - If you don't know how to convert from binary to decimal, a simple way is to sum powers of 2 from left to right, counting only the ones with a 1. So the first bit is worth 1, the next is 2, then 4, etc. 
So in this case 01101000 is 8+32+64 = 104. The general form is, in this case, 011010002 = 0*20 + 0*21 + 0*22 + 1*23 + 0*24 + 1*25 + 1*26 + 0*27 = 0+0+0+8+0+32+64+0 = 10410

Part 1 of Scrapyard Wars came out last week, part 2 came out this weekend. Next part is next Saturday. What is your point?   Multi-part is fine, and in Scrapyard Wars' case it's coming out in a consistent schedule. I'm loving this series and it's tough waiting so long for it but I want them to not only edit it properly as well as generate good revenue from such an awesome (and somewhat expensive) series so I'm definitely OK with how they're doing it. Stop being so impatient people.

The last one (PSR-1) is a PHP standard developed by the PHP Framework Interoperability Group. This is the base standard for many open-source projects and frameworks in PHP.
 
You may do it for fun and not care about learning how to code correctly but many people asking questions are here to learn.
 
It's better for those people to learn about these standards and be aware of them rather than ignoring them, picking up bad coding habits and then finding it harder when doing it in a job if they go that way.

This topic will serve as an index, or listing, of all the problems that are a part of the Problem Solving series I've been doing. This way they won't get lost.
Somewhere in the near future I'll write a few "Problem Solving basics" articles where I explain a few techniques used in solving problems (graphs, combinatorial optimization, time complexity, etc), those will also be listed here.
 
Problems
 
Problem #1 - Deletable Primes (Discussion | Gateway)
Problem #2 - Sharing is Caring (Discussion | Gateway)
Problem #3 - Polygon Phobia (Discussion | Gateway)
Problem #4 - Lego Mosaics (Discussion | Gateway)
Problem #5 - User-Friendly Manuals (Discussion | Gateway)
Problem #6/7 - Solving the N-Puzzle (Discussion | Gateway (C <= 3) | Gateway (15-Puzzle))
 
Articles
 
None.
 
 
 
If you have any suggestions for problems, articles, or would like to contribute in some other way to the series, this is the place to say it (or via PM to me).

I'd like to subscribe to the "don't use floating point variables" suggestions. The reason why your code has absolutely no problems is because there's no arithmetic going on that will mess up your decimal point approximation - you only care about the cases where there is no decimal value. Also, Math.round actually returns a long, which means there's some auto-casting magic going on there you don't know about.
 
Just don't use floating point when you need to perform arithmetic on values and compare them later for equality. There are safer (albeit less efficient) alternatives. It'll save you a sea of headaches.
If you are curious about why that's not cool, I wrote here about the problem.

Good job - I think these kinds of threads are beneficial to the community.
 
But... I'm a sucker for correctness so I have to correct you there. We may be arguing semantics but when you say:
 
 
You're actually allocating space for pointers to Constructor_Tut objects, not the objects themselves. That should be made clearer, even if that is not the topic being discussed.
Additionally, I subscribe to what SSL said. But other than that, keep them coming.

Good job - I think these kinds of threads are beneficial to the community.
 
But... I'm a sucker for correctness so I have to correct you there. We may be arguing semantics but when you say:
 
 
You're actually allocating space for pointers to Constructor_Tut objects, not the objects themselves. That should be made clearer, even if that is not the topic being discussed.
Additionally, I subscribe to what SSL said. But other than that, keep them coming.

"Object oriented" has nothing to do with graphics.
 
Objects in a programming language are a type of structure that groups together related variables (fields) and functions (methods) into a "class". This is opposed to procedural programming, which is composed solely of functions and procedures.
 
An API is an "Application - Program Interface". Basically, building blocks which don't do much on their own but when put together form a full application or program. Often they provide the "controls" that one application uses to interact with another.
 
The longer you use a particular language the more you will naturally learn and memorize. However, I doubt there is any programmer out there that ever stops needing to refer to the documentation.
 
Personally, I think "studying" a specific language or API is a waste of time. As I said above, you naturally learn things about a language as you use it, referring to the documentation and tutorials. It's better to have a solid understanding of the core ideas such as data structures, algorithms, and design patterns which are generally not tied to any particular language, or even computers in general. If you know those things you will be able to use any language more effectively.

I may be reading this wrong but, did you leave it as a .txt file?

Well, everyone's entitled to their opinion. I appreciate open-source, but could never demand or expect software to be open-source. Why should it be? I understand the advantages of proprietary code for companies. Software is a business, so it makes sense.
Bottom line for me is: trying to demonize those who oppose, or do not practice, open-source/free software is not cool in my book.

Are you a good developer? If you think this thread has no point, how can you possibly think that question does? Why are you being so hostile?
 
On-topic, I've never contributed to a big open-source project. While I like the concept of open-source, the people who admire and practice it are many times a pain in the butt (Stallman is a prime example).
It's unfortunate that you had to deal with such an unpleasant experience, but that is life. There are a-holes everywhere, and there's nothing we can do about it. Some people can't appreciate other people's effort and dedication - or simply don't have enough sensibility to realize it is there.
This kind of behaviour is mostly prejudicial to them, so don't think too much about it. You're better than them, in that regard at least. Additionally, from personal experience, overly hostile developers are often times incapable developers.
 
If a group doesn't appreciate your effort, take your talents elsewhere. Their loss.

Are you a good developer? If you think this thread has no point, how can you possibly think that question does? Why are you being so hostile?
 
On-topic, I've never contributed to a big open-source project. While I like the concept of open-source, the people who admire and practice it are many times a pain in the butt (Stallman is a prime example).
It's unfortunate that you had to deal with such an unpleasant experience, but that is life. There are a-holes everywhere, and there's nothing we can do about it. Some people can't appreciate other people's effort and dedication - or simply don't have enough sensibility to realize it is there.
This kind of behaviour is mostly prejudicial to them, so don't think too much about it. You're better than them, in that regard at least. Additionally, from personal experience, overly hostile developers are often times incapable developers.
 
If a group doesn't appreciate your effort, take your talents elsewhere. Their loss.

Just a quick update. I managed to get the image back up, so the gateway is available again. All of the old problems are still there if new users want to give them a shot. (Gateway Link)

That is sad, but I am happy for you that you let it go, as you indeed seem quite busy
I am really interested in your video course, I would love to learn more. And I want to thank you for the initiatives you started and for your helpful guidance. See you soon!

Last solution was incapable of solving 15-puzzles due to horrible memory efficiency. Storing the entire visited tree is dumb and defeats the purpose of IDA*.
 
New solution ditches trees and allocation altogether. Not only is memory performance infinitely better, it's faster too.
 
 
Could use a better heuristic, but performance is satisfactory.

update: as an alternative to the Pattern DB solution i found another heuristic function (Walking Distance) that should be much more accurate than the manhattan distance, and that makes use of a lookup table of around 25k elements for a 15-puzzle
 
the problem is that the euristhic was invented by a japanese guy who cannot speak english. i found something, but i'm having a hard time wrapping my head around it, so i'll leave some links here for now, go to sleep and try again tomorrow
 
have fun reading the japanese article, eventually translated with google translator. if it's not clear enough, here you have the C source code and a picture that shows how the Walking Distance heuristics works
 

Thanks a lot but you didn't have to since it was my fault for being an idiot . Sorry about that will keep in mind for future submission and thanks again.

I deleted the incorrect submissions since it was a matter of formatting. All problem results end with a line break, keep that in mind from now on.
 
Good job, I encourage you to keep going!

mmm they look right to me
the number of primes is correct, the last few primes and the first few primes are correct too, so you should be good
be careful to put a line break after each of the two line when you submit your solution

i think that they both should work, but i usually go with manually pressing enter, so you should be safe using that method

OHHH lol I need to press enter again for the second line as well.....FML all those "incorrect"s lol
Sorry
 
COMPLETE LACK OF ABILITY TO FOLLOW DIRECTIONS!!! lol my bad
 
 
Code: VB.net
 
Code: C#