|
Unless you want a lot of spam in your inbox, please do not put your e-mail address in a message posted publicly.
"Science is facts; just as houses are made of stones: so, is science made of facts. But, a pile of stones is not a house, and a collection of facts is not, necessarily, science." Henri Poincare
|
|
|
|
|
This article: Graphical solution to eight queen problem[^] mentions "the old algorithm from Horowitz-Sahani". Does anyone here have more information on this? I haven't found anything online, I'm thinking it's only in a text book.
|
|
|
|
|
|
Ah, good, thanks. That first one still just shows the snippet* posted in the article I mentioned, I was hoping to see more on the algorithm.
* And that's what I came up with on my own last week.
Also, I note in the second one that he's using recursion -- my algorithm is non-recursive.
P.S. I just ordered a used copy of that book from Amazon. 
modified 1-Jan-12 10:27am.
|
|
|
|
|
I would be interested in seeing your algo to see how it stacks up with some of my algos for removing recursion.
Dave.
|
|
|
|
|
Once I've seen what's in the book I'll decide whether or not mine is unique enough to form an article.
|
|
|
|
|
The book arrove today. My code is very much like the code they show on page 338 with two main differences:
0) They have the test in a separate function and therefore a global array.
(Which also has a needless call to ABS.)
1) They have an extra while loop.
public static System.Collections.Generic.IEnumerable<System.Collections.Generic.IList<int>>
nQueens
(
int HowMany
)
{
int[] board = new int [ HowMany ] ;
int row = 0 ;
board [ row ] = -1 ;
while ( row >= 0 )
{
board [ row ]++ ;
if ( board [ row ] == HowMany )
{
row-- ;
}
else
{
int i ;
for ( i = 0 ; i < row ; i++ )
{
int diff = board [ row ] - board [ i ] ;
if ( ( diff == 0 ) || ( System.Math.Abs ( diff ) == ( row - i ) ) )
{
break ;
}
}
if ( i == row )
{
row++ ;
if ( row == HowMany )
{
yield return ( System.Array.AsReadOnly ( board ) ) ;
row-- ;
}
else
{
board [ row ] = -1 ;
}
}
}
}
yield break ;
}
|
|
|
|
|
Thank you for your reply. I gather that this is your algorithms since it only has one "while" loop. It may take me a while to digest this, I am primarily a MASM developer, but come here for algorithms.
Do you have any guesses as to how large "HowMany" can be and not run out of memory, i.e., what would be the maximum n for nQueens with this algo?
Dave. (Another Desert Rat from West Phoenix)
|
|
|
|
|
Oh, yes, that's mine. The book uses a Pascal-like language the authors created called SPARKS.
On my system (Win 7 32bit, 4GB RAM), somewhere around 438330000 depending on what else is going on:
C:\Projects>nQueens 438330000
^C
C:\Projects>nQueens 438335000
System.OutOfMemoryException: Exception of type 'System.OutOfMemoryException' was thrown.
at PIEBALD.Lib.LibMth.<nQueens>d__0.MoveNext()
at PIEBALD.Utilities.nQueens.Main(String[] args)
I have heard that .net limits the size of a structure (e.g. an array) to two gigabytes.
Member 4194593 wrote: Desert Rat from West Phoenix
Ah, then I invite you to join the Tosche Station group. http://www.codeproject.com/Members/Tosche-Station[^]
modified 11-Jan-12 16:22pm.
|
|
|
|
|
Does .net limit you if the /3GB switch is used in c:\boot.ini.bat?
Dave.
|
|
|
|
|
I expect so, but I haven't tried it.
|
|
|
|
|
If you go to try it, be aware if the pitfalls:
Boot.ini is System,Hidden,Readonly.
I think you need to be Administrator.
Change the permissions to R/W.
Even as Admin you cannot edit boot.ini with ordinary editors, use RUN NOTEPAD.
Open boot.ini
Change [OS] multi(0)... and add /3GB.
Save boot.ini
For your own safety, change permissions back to RO.
Boot the system.
Also, you do have a good disk image backup don't you?
Dave.
|
|
|
|
|
Ah, thanks, but I'm not going to try it.
|
|
|
|
|
Turing Machine Simulator
Write a program that simulates a Turing machine (Tm). A Tm is a primitive model of a general purpose computer. Programs for a Tm consist of a collection of quadruples, each of the following form:
<state> <symbol> <action> <nextstate>
where
<state> ::= a non-negative integer
<symbol> ::= 1 | B
<action> ::= <symbol> | L | R
<nextstate> ::= a non-negative integer
A Tm stores data on a tape divided into squares, each of which contains one symbol, either 1 or B. Only one square can be inspected at a time. Initially, a sequence of symbols is written on the tape (this is the input to the Tm), the Tm's "read/write head" is positioned over the leftmost symbol, and the state of the Tm is set to some "start state".
At any point in a Tm computation, the Tm is in a particular state with its read/write head scanning the symbol in a particular square. What happens next depends on whether the Tm's program contains a quadruple whose <state> is the Tm's current state and whose <symbol> is the symbol contained in the square currently being scanned. If such a quadruple exists (there cannot be more than one such), the <action> part of this quadruple controls what happens next:
if <action> specifies a symbol, then that symbol replaces whatever symbol is in the square currently under scan
if <action> is L, the Tm's read/write head is moved one square to the left (the symbol in the square previously under scan is not changed)
if <action> is R, the Tm's read/write head is moved one square to the right (the symbol in the square previously under scan is not changed)
After one of the above actions is done, the Tm changes to state <nextstate> and we repeat the process of searching for an appropriate quadruple to "execute". This is continued until no quadruple matches the current state and symbol under scan, in which case the Tm halts and we consider its output to be the sequence of symbols between the first and last 1's on the tape, inclusive (if no 1's remain, we consider the output to be just B).
The input is a sequence of Tm instruction quadruples followed by a "start" line that specifies the initial state for the Tm, followed by the sequence of symbols that make up the initial value stored on the Tm's tape. Generically:
<state> <symbol> <action> <nextstate>
<state> <symbol> <action> <nextstate>
<state> <symbol> <action> <nextstate>
<state> <symbol> <action> <nextstate>
...
start <state>
<symbol>
<symbol>
<symbol>
<symbol>
<symbol>
...
For example:
0 1 R 0
0 B 1 1
start 0
1
1
1
1
Given the above input, the output should be:
11111
Note
If a quadruple requires moving left from the leftmost symbol on the tape, or right from the rightmost symbol, a square containing the symbol B must be added to the appropriate end of the tape (which is thus "finite, but unbounded")
|
|
|
|
|
Nobody is going to write your homework for you.
Unrequited desire is character building. OriginalGriff
I'm sitting here giving you a standing ovation - Len Goodman
|
|
|
|
|
Ooooohhh... Turing Machines. I love Turing Machines, I played with writing them a few different ways* a year ago and was thinking of writing an article. I also read The Annotated Turing/[^] last summer. 
But I won't do your homework for you.
* One of my favorites is written in XML / XSLT; what language are you supposed to use?
|
|
|
|
|
Hi out there,
I am writing a component which parses current html-data.
This data contains a list of elements depending on a date time. Unfortunately this date time is given in the following format: "Day.Month DayOfWeek" - e.g. "22.12 Thursday".
Now, in december, the list contains elements with a date time set in the next year, e.g. "5.1 Thursday", so the parser has to decide which year he use to return an unique date time (2011 or 2012 or others).
Since the data could be in the past too (20010), my idea is the following:
The last YPast and the next YFuture years are checked whether the given day in the given month is actually the given day of week (e.g. if the 22.12.2012 actually is a thursday) and the year with the smallest distance to today which meets this condition is used.
Because it is very important, that the parsed date time is correct, the algorithm has to be as good as possible.
So my question: Are there any better ideas than mine or any improvements? In which circumstances it comes to collisions? Which value should be selected for YPast and YFuture?
If you find spelling- or grammer-mistakes, please let me know, so that I can correct them (at least for me) - english is not my first language...
|
|
|
|
|
Henning Dieterichs wrote: Because it is very important, that the parsed date time is correct, the algorithm has to be as good as possible.
So you already know it isn't really going to work; either it is guaranteed to be correct, or it is as good as possible; it won't be both.
Each year, the day-of-week for a given date moves one or two positions, due to a year having a multiple of 7 plus 1 or 2 days in it, depending on non-leap/leap year. So if you move back or forth some 5 or 6 years, you'll encounter the same day-of-week as you have this year. OTOH within the range [now - 4 years, now + 4 years ] you won't find a collision with this year's day-of-week.
It is up to you what you do with the information; as you lack sufficient information to uniquely identify the actual year, you'll have to come up with a guess (for a random year you have a 1-in-7 chance the DOW matches). Trying a number of possibilities seems the best approach there is.
|
|
|
|
|
Given three doubles minx, maxx and delta I want to work out how many times delta fits in the interval between minx and maxx without touching the maxx.
I've found this solution to the problem in some inherited code. This is fine when m is small, but as m grows it obviously takes longer and longer. I guess it was easy to code, but not particularly efficient.
public int FindMaxM(double minx, double maxx, double delta)
{
int m;
while (minx + m * delta < maxx)
{
m++;
}
return m;
}
My own implementation looks like this, but I wondered in an academic way if there was an even better way to do it. How would you implement it?
public int FindMaxM(double minx, double maxx, double delta)
{
int m = (int) (((maxx - minx)/delta));
if (minx + m * delta >= maxx)
{
m--;
}
return m;
}
|
|
|
|
|
Just off the cuff I would say:
m = (int)((maxx-minx) / delta);
The difficult we do right away...
...the impossible takes slightly longer.
|
|
|
|
|
I am not paid by lines, so I might do something like this.
return --((int)Math.Ceiling((maxx - minx) / delta));
|
|
|
|
|
The answers so far probably don't satisfy the "without touching the maxx" requirement; it may depend on your definition of "touching". You might get away with it by subtracting a tiny fraction of delta from maxx before using the division approach...
|
|
|
|
|
|
Plenty of novices ask pretty much the same question when start to work with brokers who help them to earn money by means of the Forex trading. This question concerns the compensation that brokers take in order to get profits from collaboration with traders. Brokers are often to forget this when it comes to actual trading process and that is why the compensation in the most cases is not limited by spread rates the brokers set in every particular case. Due to the fact this scheme is bit complicated and important because every trader should know the rules the other participants of the Forex trading follow we have decided to enlighten it below.
In a case you want to disclose all forex trading software secrets and rules you need to know what the participants of this market come back in the trading day by day and what benefits they expect to get because you may like in idea of changing your profession of a trader into a broker’s occupation within the Forex market. Well, we hope you figure out by now that knowing what fee your broker gets from working with you can be very handy and interesting info to know so let’s try to figure out by item what benefits and compensations a broker may get in the Forex market.
Unlikely other assets’ brokers FX brokers never charge commissions on the traders with who they work. They use other ways of the money source which appear during the actual Forex trading process:
1) By Currency Buying/Selling
The lion’s share of profits a broker gets from forex trading comes from actual buying and selling of currencies. Money comes from getting spreads which stands for the differences between the bid and the ask prices. The ask price is that price at which the FX market sells a trader the currency and the bid price in its turn the price at which this currency can be bought from you while you are conducting your trading positions.
2) By Charging Leveraged Spreads
When a broker offers high leverage to traders he or she makes it not profitable to earn money on spreads because they are getting to be too small. By means of the high leverage brokers can multiply the potential profits however with high risks as well. Proposing the leverage 1:100 a Forex broker can make 100 times more profits than without leverage.
3) By Getting Overnight Swap Spreads
In a case the when the difference between the set interest rates is positive in the particular position of the trader the broker can pay the so called overnight swap to the trader he or she works with. In a case when the difference between the interest rates is negative the Forex trading broker get money from the account of the trader.
4) Asking for a Commission on Payment Processing
Commissions are not taken abut sometimes they are masked as payments for certain service online Forex brokers provide. You as a trader can be asked to pay for making a withdrawal or deposit. For sure, such fees are ridiculously small and measured not I pips but in the currency units but still in such way you can reduce the expenses a broker has to make while providing you the numerous online services for proper and better Forex trading.
NB: Make sure that your broker doesn’t belong to those ones who earn money on their clients’ losses. Beware of brokers offering too small spreads from working with you, proposing the irrelevant leverage conditions, too good to be true overnight swaps and free payment processing service.
Latest blogpost:Tips for Seekers of Free Forex Buy and Sell Indicator Offers.
We're online: forex market.
modified 1-Dec-11 3:17am.
|
|
|
|
|
Is there available a good introductory tutorial with code for that problem?
Чесноков
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
