Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss
Accessing Memory out of bounds?
48 views
Skip to first unread message
Kuroneko
Oct 13, 2012, 8:54:21 PM10/13/12
to
I'm getting some strange errors on a USACO training problem (clocks). I suspect that I'm accessing memory out of bounds somewhere in my code, but I can't figure out where...
Errors
Compiling...
Compile: OK
Executing...
Test 1: TEST OK [0.000 secs, 3356 KB]
Test 2: TEST OK [0.000 secs, 3356 KB]
Test 3: TEST OK [0.281 secs, 9032 KB]
Test 4: TEST OK [0.659 secs, 14708 KB]
> Run 5: Execution error: Your program had this runtime error:
Illegal file open (/sys/devices/system/cpu/online). The program
ran for 0.767 CPU seconds before the error. It used 16292 KB of
memory.
------ Data for Run 5 [length=26 bytes] ------
6 12 12
12 12 12
12 12 12
----------------------------
Test 5: SIGNAL 50 (0.767 secs, 16292 KB)
My Code:
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <map>
#define ord(ch) ((int)(ch - 'A'))
using namespace std;
vector<string> moves;
vector<int> ideal;
void print(vector<int>);
vector<int> find(vector<int>);
vector<int> move(vector<int>, int);
void turn(vector<int> &, int);
int main(void)
{
moves.resize(9);
ideal.resize(9);
moves[0] = "ABDE";
moves[1] = "ABC";
moves[2] = "BCEF";
moves[3] = "ADG";
moves[4] = "BDEFH";
moves[5] = "CFI";
moves[6] = "DEGH";
moves[7] = "GHI";
moves[8] = "EFHI";
for (int i = 0; i < 9; i++)
ideal[i] = 12;
vector<int> v(9);
ifstream f("clocks.in");
ofstream g("clocks.out");
if (f.fail())
{
cerr << "FILE ERROR" << endl;
return 1;
}
for (int i = 0; i < 9; i++)
f >> v[i];
vector<int> sol = find(v);
for (vector<int>::iterator it = sol.begin(); it < sol.end(); ++it)
g << *it + 1 << (it < sol.end() - 1 ? " " : "");
g << endl;
}
vector<int> find(vector<int> v)
{
queue< vector<int> > open_list;
open_list.push(v);
map< vector<int>, vector<int> > path;
path[v] = vector<int>();
while (open_list.size() > 0)
{
vector<int> curr = open_list.front();
open_list.pop();
for (int i = 0; i < 9; i++)
{
vector<int> next = move(curr, i);
if (path.find(next) == path.end())
{
path[next] = path[curr];
path[next].push_back(i);
open_list.push(next);
}
}
if (path.find(ideal) != path.end())
return path[ideal];
}
return vector<int>();
}
vector<int> move(vector<int> v, int n)
{
for (string::iterator it = moves[n].begin(); it < moves[n].end(); ++it)
turn(v, ord(*it));
return v;
}
void turn(vector<int> &v, int n)
{
v[n] = (v[n] == 12 ? 3 : v[n] == 3 ? 6 : v[n] == 6 ? 9 : 12);
}
By the way the code functions fine (gets the right answers), but seems to cause memory errors. Thanks for your time!
--Kuroneko
Errors
Compiling...
Compile: OK
Executing...
Test 1: TEST OK [0.000 secs, 3356 KB]
Test 2: TEST OK [0.000 secs, 3356 KB]
Test 3: TEST OK [0.281 secs, 9032 KB]
Test 4: TEST OK [0.659 secs, 14708 KB]
> Run 5: Execution error: Your program had this runtime error:
Illegal file open (/sys/devices/system/cpu/online). The program
ran for 0.767 CPU seconds before the error. It used 16292 KB of
memory.
------ Data for Run 5 [length=26 bytes] ------
6 12 12
12 12 12
12 12 12
----------------------------
Test 5: SIGNAL 50 (0.767 secs, 16292 KB)
My Code:
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <map>
#define ord(ch) ((int)(ch - 'A'))
using namespace std;
vector<string> moves;
vector<int> ideal;
void print(vector<int>);
vector<int> find(vector<int>);
vector<int> move(vector<int>, int);
void turn(vector<int> &, int);
int main(void)
{
moves.resize(9);
ideal.resize(9);
moves[0] = "ABDE";
moves[1] = "ABC";
moves[2] = "BCEF";
moves[3] = "ADG";
moves[4] = "BDEFH";
moves[5] = "CFI";
moves[6] = "DEGH";
moves[7] = "GHI";
moves[8] = "EFHI";
for (int i = 0; i < 9; i++)
ideal[i] = 12;
vector<int> v(9);
ifstream f("clocks.in");
ofstream g("clocks.out");
if (f.fail())
{
cerr << "FILE ERROR" << endl;
return 1;
}
for (int i = 0; i < 9; i++)
f >> v[i];
vector<int> sol = find(v);
for (vector<int>::iterator it = sol.begin(); it < sol.end(); ++it)
g << *it + 1 << (it < sol.end() - 1 ? " " : "");
g << endl;
}
vector<int> find(vector<int> v)
{
queue< vector<int> > open_list;
open_list.push(v);
map< vector<int>, vector<int> > path;
path[v] = vector<int>();
while (open_list.size() > 0)
{
vector<int> curr = open_list.front();
open_list.pop();
for (int i = 0; i < 9; i++)
{
vector<int> next = move(curr, i);
if (path.find(next) == path.end())
{
path[next] = path[curr];
path[next].push_back(i);
open_list.push(next);
}
}
if (path.find(ideal) != path.end())
return path[ideal];
}
return vector<int>();
}
vector<int> move(vector<int> v, int n)
{
for (string::iterator it = moves[n].begin(); it < moves[n].end(); ++it)
turn(v, ord(*it));
return v;
}
void turn(vector<int> &v, int n)
{
v[n] = (v[n] == 12 ? 3 : v[n] == 3 ? 6 : v[n] == 6 ? 9 : 12);
}
By the way the code functions fine (gets the right answers), but seems to cause memory errors. Thanks for your time!
--Kuroneko
Bill Gill
Oct 14, 2012, 12:53:56 PM10/14/12
to
but when I have a problem like that I generally put in a pause
at the place where the problem may be occurring, then step
through it one command at a time and check the values of
the iterators to see where one of them oversteps the bounds
of the vector.
That is assuming that the problem is someplace in one of the
loops, which is where I usually have that kind of problem.
Bill
Ben Bacarisse
Oct 14, 2012, 2:19:57 PM10/14/12
to
Kuroneko <zeng.a...@gmail.com> writes:
> I'm getting some strange errors on a USACO training problem (clocks).
> I suspect that I'm accessing memory out of bounds somewhere in my
> code, but I can't figure out where...
A link to the problem (or a description of it would help). It's not
> I'm getting some strange errors on a USACO training problem (clocks).
> I suspect that I'm accessing memory out of bounds somewhere in my
> code, but I can't figure out where...
going to help diagnose the issue, but it help people feel interested!
> Errors
>
> Compiling...
> Compile: OK
>
> Executing...
> Test 1: TEST OK [0.000 secs, 3356 KB]
> Test 2: TEST OK [0.000 secs, 3356 KB]
> Test 3: TEST OK [0.281 secs, 9032 KB]
> Test 4: TEST OK [0.659 secs, 14708 KB]
> > Run 5: Execution error: Your program had this runtime error:
> Illegal file open (/sys/devices/system/cpu/online). The program
> ran for 0.767 CPU seconds before the error. It used 16292 KB of
> memory.
>
> ------ Data for Run 5 [length=26 bytes] ------
> 6 12 12
> 12 12 12
> 12 12 12
> ----------------------------
> Test 5: SIGNAL 50 (0.767 secs, 16292 KB)
>
> My Code:
> By the way the code functions fine (gets the right answers), but seems
> to cause memory errors.
valgrind (a memory checker) and it reported no problems. That's not
foolproof but it is string evidence.
--
Ben.
Kuroneko
Oct 14, 2012, 2:38:09 PM10/14/12
to
On Sunday, 14 October 2012 14:19:59 UTC-4, Ben Bacarisse wrote:
> A link to the problem (or a description of it would help). It's not
>
> going to help diagnose the issue, but it help people feel interested!
>
>
The problem description can be found here: http://www.bunny.idv.tw/~kcwu/usaco/prob/58.html
> A link to the problem (or a description of it would help). It's not
>
> going to help diagnose the issue, but it help people feel interested!
>
>
>
> What makes you think this? I ran the test case in question under
>
> valgrind (a memory checker) and it reported no problems. That's not
>
> foolproof but it is string evidence.
>
Ike Naar
Oct 14, 2012, 5:14:56 PM10/14/12
to
On 2012-10-14, Kuroneko <zeng.a...@gmail.com> wrote:
> I'm getting some strange errors on a USACO training problem (clocks).
> I suspect that I'm accessing memory out of bounds somewhere in my
> code, but I can't figure out where...
>
> Errors
>
> Compiling...
> Compile: OK
>
> Executing...
> Test 1: TEST OK [0.000 secs, 3356 KB]
> Test 2: TEST OK [0.000 secs, 3356 KB]
> Test 3: TEST OK [0.281 secs, 9032 KB]
> Test 4: TEST OK [0.659 secs, 14708 KB]
> > Run 5: Execution error: Your program had this runtime error:
> Illegal file open (/sys/devices/system/cpu/online). The program
> ran for 0.767 CPU seconds before the error. It used 16292 KB of
> memory.
The error message does not seem to indicate that memory is accessed
> I'm getting some strange errors on a USACO training problem (clocks).
> I suspect that I'm accessing memory out of bounds somewhere in my
> code, but I can't figure out where...
>
> Errors
>
> Compiling...
> Compile: OK
>
> Executing...
> Test 1: TEST OK [0.000 secs, 3356 KB]
> Test 2: TEST OK [0.000 secs, 3356 KB]
> Test 3: TEST OK [0.281 secs, 9032 KB]
> Test 4: TEST OK [0.659 secs, 14708 KB]
> > Run 5: Execution error: Your program had this runtime error:
> Illegal file open (/sys/devices/system/cpu/online). The program
> ran for 0.767 CPU seconds before the error. It used 16292 KB of
> memory.
out of bounds. Could it be that there are constraints being put on
the cpu time usage and/or memory usage of the running program, and
that the program hits one of these limits when computing the solution
for run 5?
Ian Collins
Oct 14, 2012, 5:25:19 PM10/14/12
to
On 10/14/12 13:54, Kuroneko wrote:
Please wrap your lines!
> I'm getting some strange errors on a USACO training problem (clocks). I suspect that I'm accessing memory out of bounds somewhere in my code, but I can't figure out where...
There don't appear to be any out of bounds accesses in your code.
But..
> vector<int> move(vector<int> v, int n)
> {
> for (string::iterator it = moves[n].begin(); it< moves[n].end(); ++it)
It's better to use != when comparing iterators.
--
Ian Collins
Please wrap your lines!
> I'm getting some strange errors on a USACO training problem (clocks). I suspect that I'm accessing memory out of bounds somewhere in my code, but I can't figure out where...
But..
> vector<int> move(vector<int> v, int n)
> {
> for (string::iterator it = moves[n].begin(); it< moves[n].end(); ++it)
--
Ian Collins
Kuroneko
Oct 14, 2012, 8:11:10 PM10/14/12
to
On Sunday, 14 October 2012 17:14:56 UTC-4, Ike Naar wrote:
> The error message does not seem to indicate that memory is accessed
> out of bounds. Could it be that there are constraints being put on
> the cpu time usage and/or memory usage of the running program, and
> that the program hits one of these limits when computing the solution
> for run 5?
The time usage bound is 1 sec, so that's probably not the problem, but I may be using too much memory; I'll look into that.
> The error message does not seem to indicate that memory is accessed
> out of bounds. Could it be that there are constraints being put on
> the cpu time usage and/or memory usage of the running program, and
> that the program hits one of these limits when computing the solution
> for run 5?
Francis Glassborow
Oct 15, 2012, 4:02:35 AM10/15/12
to
On 14/10/2012 01:54, Kuroneko wrote:
> I'm getting some strange errors on a USACO training problem (clocks).
I suspect that I'm accessing memory out of bounds somewhere in my code,
but I can't figure out where...
>
> Errors
>
It seems that the amount of memory used after each TEST increases by
> I'm getting some strange errors on a USACO training problem (clocks).
I suspect that I'm accessing memory out of bounds somewhere in my code,
but I can't figure out where...
>
> Errors
>
5676 bytes. Assuming that there is a maximum amount of memory of 16384
(i.e. 2^14) then the error message is generated when the next memory
request takes your program pass its permitted limit.
Note that there is little purpose in providing only part of the code
without any explanation as to what it is supposed to do. If this code is
written by you then you have other problems. If it was largely written
by someone else then find another teacher.
Francis
0 new messages