To my letter with the "improved" Cryptarithm test
Fergus Henderson <[EMAIL PROTECTED]> writes
>> -- C++ -------------------------------------------------------------
...
>> int condition2 (vector<long> x)
>> {int i = 0;
>> while ( i < 20 & x[i]==9-i ) i++;
> That has undefined behaviour, since your vector `x' only has length 10,
> not 20.
Thank you.
It should be while ( i < 10 & x[i]==9-i ) i++;
By occasion, this error had not spoiled the test, because
for i > 9 x[i]==9-i is false.
Also D. Tweed <[EMAIL PROTECTED]> writes
>> Now it shows the ratio * 6 *.
T> One small comment is that in your functions condition1 & condition2 I
T> think most C++ programmers would say that you want to write
T>
T> int condition1 (const vector<long>& x)
T>
T> since otherwise the compiler generally has to obey the normal function
T> call semantics and create a copy of the vector when it passes it the
T> function, rather than work directly with the existing list.
T> [..]
Thank you.
Here is again the improved test.
As earlier,
condition1 corresponds to Haskell program's all (< 20) p
(for all i x[i] < 20),
condition2 corresponds to p == [9,8..0].
And now the performance ratio shows * 16 *.
I understand this so, that this particular task allows to set
`const'. Because first, condition1, condition2 apply to the
vector x; as they do not modify x, next_permutation(x)
yields the correct value when applied after them.
Probably, other tasks and `condition1' variants would not allow to
set `const' like here.
Do i understand right?
And for these cases the ratio is smaller, say, 6, as showed the
earlier test
- ?
------------------
Sergey Mechveliani
[EMAIL PROTECTED]
------------------------- C++, improved program ---------
#include <vector>
#include <algorithm>
#include <iostream.h>
using namespace std;
int condition1 (const vector<long>& x)
{
int i = 0;
while (i < 10 & x[i] < 20) i++;
return (i > 9);
}
int condition2 (const vector<long>& x)
{
int i = 0;
while (i < 10 & x[i]==9-i) i++;
return (i > 9);
}
void main()
{long t,h,i,r,y,w,e,l,v,n;
long temp[10] = {0,1,2,3,4,5,6,7,8,9};
vector<long> x(temp,temp+10);
while (!(condition1(x) & condition2(x)))
{
next_permutation(x.begin(), x.end());
}
cout << x[0] << x[1] << x[2] << x[3] << x[4] << x[5] << x[6] <<
x[7] << x[8] << x[9] << '\n';
}
-- Haskell ------------------------------------------------------
import List (find)
permutations :: [Int] -> [[Int]]
-- build the full permutation list given an ordered list
permutations [] = [[]]
permutations (j:js) = addOne $ permutations js
where
addOne [] = []
addOne (ks:pms) = (ao ks)++(addOne pms)
ao [] = [[j]]
ao (k:ks) = (j:k:ks):(map (k:) $ ao ks)
main = putStr $ shows (find condition $ permutations p0) "\n"
where
(p0, pLast) = ([0..9], reverse [0..9])
condition p = all (< 20) p && p==pLast
