C++

Forum

 
optimize problem 22

Pages: 12
closed account (ETAkoG1T)
The problem: http://projecteuler.net/problem=22
note that there is a textfile that goes with it.
It seems that my program either is eternal or takes over 5 hours. If you can spot something that makes this slow, whithout changing the approach totally, please note me. I am a bit tired, that is why I need some extra help. Thanks in advance!

my program this far:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
 
#include "stdafx.h"
#include <iostream>
#include <fstream>
#include <cstdio>

bool compare(const char * name1, const char * name2);
int position(const char * name);
int value(const char * name);
int main()
{
	using namespace std;
	ifstream inFile;
	inFile.open("names.txt");
	int total_character_value = 0;
	char name[30];
	while(!inFile.eof())
	{
		int i = 0;
		char ch;
		inFile.get(ch);
		if(ch == ',')
			inFile.get(ch);
		if(ch == '"')
		{
			inFile.get(ch);
			while(ch != '"')
			{
				name[i] = ch;
				i++;
				inFile.get(ch);
			}
		}
		if(name == "")
			break;
		int pos = position(name);
		total_character_value += (value(name) * pos);
		cout << "total_character_value = " << total_character_value;
		cout << endl;
	}
	cout << "total = " << total_character_value;
	cin.get();
	return 0;
}

bool compare(const char * name1, const char * name2)
{
	int i = 0;
	while(name1[i] != '\0' && name2[i] != '\0' )
	{
		if(name1[i] > name2[i])
			return 1;
		if(name1[i] < name2[i])
			return 0;
		else
			i++;
	}
	return 0;
}
int position(const char * name)
{
	std::ifstream inFile;
	inFile.open("names.txt");
	int pos = 1;
	char *str;
	char ch;
	char n[20];
	while(!inFile.eof())
	{
		inFile.get(ch);
		if(ch == ',')
			inFile.get(ch);
		if(ch == '"')
		{
			int i = 0;
			inFile.get(ch);
			while(ch != '\"')
			{
				n[i] = ch;
				i++;
				inFile.get(ch);
			}
			str = n;
			if(str == "")
				break;
			std::cout << "Comparing, ";
			if(compare(name, str))
			{
				pos++;
			}
			std::cout<< "Done comparing\n";
		}
		std::cout << "pos = " << pos;
		if(str == "ALONSO")
			break;
	}
	return pos;
}

int value(const char * name)
{
	int i = 0;
	int tot = 0;
	while(name[i])
	{
		tot = tot + (int(name[i]) - 64);
		i++;
	}
	return tot;
}
Last edited on
Lowest0ne (1536)
You aren't null terminating your c-strings, this would be the first thing. I don't think position() will be able to open the file, since it is already open in main. Also just noticed you are trying to do == with a c-string, this shouldn't even compile.
Last edited on
cire (8284)
Holy gratuitous disk thrashing, Batman.

Read the names into a vector (preferably as std::strings.) Sort the vector. Calculate and sum the scores.

Parse the file one time.
Last edited on
closed account (ETAkoG1T)
I don't think I want to change my hole approach cire, it doesn't take more than one minute anyways. I try to keep my programs under one minute and this does not go over 1min. I have tried my program now with the example name in the problem and I got the exact same result. The program compiles but give wrong answer.
UPDATED CODE:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
 

#include "stdafx.h"
#include <iostream>
#include <fstream>
#include <string>

bool compare(const char * name1, const char * name2);
int position(const char * name);
int value(const char * name);
int main()
{
	using namespace std;
	ifstream inFile;
	inFile.open("names.txt");
	int total_character_value = 0;
	char *name;
	char temp[30];
	while(!inFile.eof())
	{
		int i = 0;
		char ch;
		inFile.get(ch);
		if(ch == ',')
			inFile.get(ch);
		if(ch == ';')
			break;
		if(ch == '"')
		{
			inFile.get(ch);
			while(ch != '"')
			{
				temp[i] = ch;
				i++;
				inFile.get(ch);
			}
			temp[i] = '\0';
		}
		name = temp;
		int pos = position(name);
		total_character_value += (value(name) * pos);
	}
	cout << "total = " << total_character_value;
	cin.get();
	return 0;
}

bool compare(const char * name1, const char * name2)
{
	int i = 0;
	while(name1[i] != '\0' && name2[i] != '\0' )
	{
		if(name1[i] > name2[i])
			return 1;
		if(name1[i] < name2[i])
			return 0;
		else
			i++;
	}
	return 0;
}
int position(const char * name)
{
	std::ifstream inFile;
	inFile.open("names.txt");
	int pos = 1;
	char *str;
	char ch;
	char n[20];
	while(!inFile.eof())
	{
		inFile.get(ch);

		
		if(ch == ',')
			inFile.get(ch);
		if(ch == ';')
			break;
		if(ch == '"')
		{
			int i = 0;
			inFile.get(ch);
			
			while(ch != '\"')
			{
				n[i] = ch;
				i++;
				inFile.get(ch);
			}
			n[i] = '\0';
			str = n;
			if(str == '\0')
				break;
			if(compare(name, str))
			{
				pos++;
			}
		}
	}
	return pos;
}

int value(const char * name)
{
	int i = 0;
	int tot = 0;
	while(name[i])
	{
		tot = tot + (int(name[i]) - 64);
		i++;
	}
	return tot;
}
helios (17574)
What cire said.

Aside from that, this check sucks pretty bad:
1
2
 
if(str == "ALONSO")
	break;
closed account (ETAkoG1T)
I already removed 
1
2
 
if(str == "ALONSO")
	break;

Didn't really understand what cire said, just want to fix my own program.
naraku9333 (2163)
I believe he was saying do something like this. 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
 
//project euler #22
#include <iostream>
#include <fstream>
#include <algorithm>
#include <string>
#include <vector>

int main()
{
	std::fstream file("names.txt", std::ios::in);

	std::string temp;
	std::vector<std::string> vec;
	
	//parse file
	while(std::getline(file, temp, ','))
	{
		vec.push_back(temp.substr(1,temp.size() - 2));//get rid of quotes
	}
	
	//sort alphebetically (defualt)
	std::sort(vec.begin(), vec.end());

	unsigned long long total = 0ULL;

	for(int i = 0; i < vec.size(); ++i)++i)
	{
		unsigned int subTotal = 0;
		
		for(int j = 0; j < vec[i].size(); ++j)
			subTotal += vec[i][j] - 64;//sum the chars
			
		total += subTotal * (i + 1);//sum the product
	}

	std::cout << total << std::endl;
}
Last edited on
closed account (ETAkoG1T)
Thanks for the replies, don't want to venture into vectors yet. If you could just help me find the mistake in my program that would be great!
naraku9333 (2163)
I don't see you sort the names anywhere and the correct answer depends on them being sorted alphabetically. And as cire said already, you are opening the file thousands of times, very inefficient. Just open the file and parse once, store the names into an array. Sort it like 
1
2
 
 std::string arr[5000];
std::sort(arr[0], arr[4999]);
then just loop through the array getting the sum.
closed account (ETAkoG1T)
naraku9333 My solution is counting all the names that are before itself, in alphabetical order. It may not be the most efficient but it still should work. Even if I were to do it with another approach i still want to find the problem with my current program.
cire (8284)
The compare function is a potential problem. It could return the wrong value when comparing "Carl" and "Carlos". It's also poorly named. greaterThan would be more appropriate.

You're also looping on EOF, which is another potential problem.


closed account (ETAkoG1T)
what is first in alphabetical order? carl or carlos? That is an easy fix :)
Last edited on
closed account (ETAkoG1T)
I think all of this is just reversing my progress, when I tested it 5 hours ago with one name it worked fine. I think the problem is in getting the names... Please try to help me spot mistakes in my current code. (the one above)
cire (8284)
I did help you spot some mistakes. I don't see them fixed.

Get rid of the looping on EOF, and fix the comparison function. Depending on how you fix those, you may need to make additional changes.
Lowest0ne (1536)
The program I wrote for this takes less than 100 milliseconds, for all intents, the same code as naraku9333's.

You haven't fixed any of the already posted mistakes.

Actually, maybe I will hijack a little:
1
2
3
4
5
6
7
8
9
10
11
12
13
 
std::vector<unsigned int> scores(names.size());
std::transform(names.begin(), names.end(), scores.begin(),
  [](std::string s)->unsigned int
  {
    unsigned int l = s.length();
    unsigned int total = 0;
    for (unsigned int i = 0; i < l; i++)
      total += s[i] - 'A' + 1;
    return total;
  }
);
for (unsigned int i=0; i < scores.size(); i++)
  max += scores[i] * (i+1);


Any way to get that second loop inside the transform? The problem being the index of the container.

Last edited on
helios (17574)
If the function took a reference rather than an object, you could return total*(&s-start+1);, where start is &scores[0]. I don't quite remember how binding works with lambdas, though.
closed account (ETAkoG1T)
I checked my previous code with a single name and it worked, (and i got the right answer) This is my fixed code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
 
#include "stdafx.h"
#include <iostream>
#include <fstream>
#include <string>

bool compare(const char * name1, const char * name2);
int position(const char * name);
int value(const char * name);
int main()
{
	using namespace std;
	ifstream inFile;
	inFile.open("names.txt");
	int total_character_value = 0;
	char *name;
	char temp[30];
	while(1)
	{
		int i = 0;
		char ch;
		inFile.get(ch);
		if(ch == ',')
			inFile.get(ch);
		if(ch == ';')
			break;
		if(ch == '"')
		{
			inFile.get(ch);
			while(ch != '"')
			{
				temp[i] = ch;
				i++;
				inFile.get(ch);
			}
			temp[i] = '\0';
		}
		name = temp;
		int pos = position(name);
		total_character_value += (value(name) * pos);
	}
	cout << "total = " << total_character_value;
	cin.get();
	return 0;
}

bool compare(const char * name1, const char * name2)
{
	int i = 0;
	while(name1[i] != '\0' && name2[i] != '\0')
	{
		if(int(name1[i]) > int(name2[i]))
			return 0;
		if(int(name1[i]) < int(name2[i]))
			return 1;
		else
			i++;
		if(name2[i] == '\0')
			return 1;
	}
	return 0;
}
int position(const char * name)
{
	std::ifstream inFile;
	inFile.open("names.txt");
	int pos = 1;
	char *str;
	char ch;
	char n[20];
	while(1)
	{
		inFile.get(ch);
		if(ch == ',')
			inFile.get(ch);
		if(ch == ';')
			break;
		if(ch == '"')
		{
			int i = 0;
			inFile.get(ch);
			
			while(ch != '"')
			{
				n[i] = ch;
				i++;
				inFile.get(ch);
			}
			n[i] = '\0';
			str = n;
			if(compare(name, str))
			{
				pos++;
			}
		}
	}
	return pos;
}

int value(const char * name)
{
	int i = 0;
	int tot = 0;
	while(name[i])
	{
		tot = tot + (int(name[i]) - 64);
		i++;
	}
	return tot;
}
cire (8284)
Traditionally a "compare" function works by returning 0 if the two parameters are equal to each other, greater than 0 if the first is greater than the second and less than 0 if the first is less than the second. Why didn't you just use strcmp?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
 
#include <iostream>

bool compare(const char * name1, const char * name2)
{
	int i = 0;
	while(name1[i] != '\0' && name2[i] != '\0')
	{
		if(int(name1[i]) > int(name2[i]))
			return 0;
		if(int(name1[i]) < int(name2[i]))
			return 1;
		else
			i++;
		if(name2[i] == '\0')
			return 1;
	}
	return 0;
}

int main()
{
    char * a = "A" ;
    char * b = "B" ;
    char * bb = "BB" ;

    std::cout << compare(a,b) << " should be the same as " << compare(b,bb) << '\n' ;
}
 
1 should be the same as 0
Last edited on
closed account (ETAkoG1T)
This should fix it, still think the problem may be in the main()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
 
#include "stdafx.h"
#include <iostream>
#include <fstream>
#include <string>

bool compare(const char * name1, const char * name2);
int position(const char * name);
int value(const char * name);
int main()
{
	using namespace std;
	ifstream inFile;
	inFile.open("names.txt");
	int total_character_value = 0;
	char *name;
	bool x = 1;
	char temp[30];
	while(x)
	{
		int i = 0;
		char ch;
		while(inFile.get(ch) && ch != '"')
		{
			if(ch == ';')
				x = 0;
		}
		if(ch == '"')
		{
			inFile.get(ch);
			while(ch != '"')
			{
				temp[i] = ch;
				i++;
				inFile.get(ch);
			}
			temp[i] = '\0';
		}
		name = temp;
		int pos = position(name);
		total_character_value += (value(name) * pos);
	}
	cout << "total = " << total_character_value;
	cin.get();
	return 0;
}

bool compare(const char * name1, const char * name2)
{
	int i = 0;
	while(name1[i] != '\0' && name2[i] != '\0')
	{
		if(int(name1[i]) > int(name2[i]))
			return 1;
		if(int(name1[i]) < int(name2[i]))
			return 0;
		else
			i++;
		if(name2[i] == '\0')
			return 1;
	}
	return 0;
}
int position(const char * name)
{
	std::ifstream inFile;
	inFile.open("names.txt");
	int pos = 1;
	char *str;
	char ch;
	char n[20];
	while(1)
	{
		while(inFile.get(ch) && ch != '"')
		{
			if(ch == ';')
				return pos;
		}
		if(ch == '"')
		{
			int i = 0;
			inFile.get(ch);
			
			while(ch != '"')
			{
				n[i] = ch;
				i++;
				inFile.get(ch);
			}
			n[i] = '\0';
			str = n;
			if(compare(name, str))
			{
				pos++;
			}
		}
	}
	return pos;
}

int value(const char * name)
{
	int i = 0;
	int tot = 0;
	while(name[i])
	{
		tot = tot + (int(name[i]) - 64);
		i++;
	}
	return tot;
}
Last edited on
cire (8284)
What made you choose x as the variable name for your bool in main? Just that uncreative?

still think the problem may be in the main()


Afraid not. You should really stop guessing where the problem may be and reason about why the program behaves the way it does.

Now that you have a working compare function, you need to revisit position.

When you're comparing the parameter to names read from the file, at some point you're going to compare the name to itself. Given that the compare function returns true when you compare a string to itself (making it the equivalent of a greater-than-or-equal function) and lines 91-94 in your code, what do you think should be the initial value of pos in position?
Last edited on
Pages: 12