C++11 - nearly working :)
On my modest PC it seems to be able to twist over 4 million snakes per minute, but just a few reptiles seem to manage to crawl under the radar.
#include <cmath>
#include <cassert>
#include <ctime>
#include <sstream>
#include <vector>
#include <map>
#include <unordered_set>
#include <algorithm> // sort
using namespace std;
// theroretical max snake lenght (but the Sun would burn out before you'll reach that)
#define MAX_LENGTH ((int)(1+8*sizeof(unsigned)))
#ifndef QT_DEBUG // using Qt IDE for g++ builds
#ifndef NDEBUG
#define NDEBUG
#endif
#endif
#ifdef NDEBUG
inline void tprintf(const char *, ...){}
#else
#define tprintf printf
#endif
void panic(const char * msg)
{
printf("PANIC: %s\n", msg);
exit(-1);
}
// ============================================================================
// fast bit reversal
// ============================================================================
unsigned bit_reverse(register unsigned x, unsigned len)
{
x = (((x & 0xaaaaaaaa) >> 1) | ((x & 0x55555555) << 1));
x = (((x & 0xcccccccc) >> 2) | ((x & 0x33333333) << 2));
x = (((x & 0xf0f0f0f0) >> 4) | ((x & 0x0f0f0f0f) << 4));
x = (((x & 0xff00ff00) >> 8) | ((x & 0x00ff00ff) << 8));
return((x >> 16) | (x << 16)) >> (32-len);
}
// ============================================================================
// 2D geometry (restricted to integer coordinates and right angle rotations)
// ============================================================================
// points using integer- or float-valued coordinates
template<typename T>struct tTypedPoint;
typedef int tCoord;
typedef double tFloatCoord;
typedef tTypedPoint<tCoord> tPoint;
typedef tTypedPoint<tFloatCoord> tFloatPoint;
template <typename T>
struct tTypedPoint {
T x, y;
template<typename U> tTypedPoint(const tTypedPoint<U>& from) : x((T)from.x), y((T)from.y) {} // conversion constructor
tTypedPoint() {}
tTypedPoint(T x, T y) : x(x), y(y) {}
tTypedPoint(const tTypedPoint & p) { *this = p; }
tTypedPoint operator+ (const tTypedPoint & p) const { return{ x + p.x, y + p.y }; }
tTypedPoint operator- (const tTypedPoint & p) const { return{ x - p.x, y - p.y }; }
tTypedPoint operator* (T scalar) const { return{ x * scalar, y * scalar }; }
tTypedPoint operator/ (T scalar) const { return{ x / scalar, y / scalar }; }
bool operator== (const tTypedPoint & p) const { return x == p.x && y == p.y; }
bool operator!= (const tTypedPoint & p) const { return !operator==(p); }
T dot(const tTypedPoint &p) const { return x*p.x + y * p.y; } // dot product
int cross(const tTypedPoint &p) const { return x*p.y - y * p.x; } // z component of cross product
T norm2(void) const { return dot(*this); }
// works only with direction = 1 (90° right) or -1 (90° left)
tTypedPoint rotate(int direction) const { return{ direction * y, -direction * x }; }
tTypedPoint rotate(int direction, const tTypedPoint & center) const { return (*this - center).rotate(direction) + center; }
// used to compute the length of a ragdoll snake segment
unsigned manhattan_distance(const tPoint & p) const { return abs(x-p.x) + abs(y-p.y); }
};
struct tArc {
tPoint c; // circle center
tFloatPoint middle_vector; // vector splitting the arc in half
tCoord middle_vector_norm2; // precomputed for speed
tFloatCoord dp_limit; // dot product of point with the middle vector
// will be >= dp_limit if the point is inside the arc
tArc() {}
tArc(tPoint c, tPoint p, int direction) : c(c)
{
tPoint r = p - c;
tPoint end = r.rotate(direction);
middle_vector = ((tFloatPoint)(r+end)) / sqrt(2);
middle_vector_norm2 = r.norm2();
dp_limit = r.dot(middle_vector);
}
bool contains(tFloatPoint p) // p must be a point on the circle
{
if ((p-c).dot(middle_vector) >= dp_limit)
{
return true;
}
else return false;
}
};
// returns the point of line (p1 p2) that is closest to c
// handles degenerate case p1 = p2
tPoint line_closest_point(tPoint p1, tPoint p2, tPoint c)
{
if (p1 == p2) return{ p1.x, p1.y };
tPoint p1p2 = p2 - p1;
tPoint p1c = c - p1;
return p1 + p1p2 * (p1c.dot(p1p2) / p1p2.norm2());
}
// variant of closest point computation that checks if the projection falls within the segment
bool closest_point_within(tPoint p1, tPoint p2, tPoint c, tPoint & res)
{
tPoint p1p2 = p2 - p1;
tPoint p1c = c - p1;
tCoord nk = p1c.dot(p1p2);
if (nk <= 0) return false;
tCoord n = p1p2.norm2();
if (nk >= n) return false;
res = p1 + p1p2 * (nk / n);
return true;
}
// tests intersection of line (p1 p2) with an arc
bool inter_seg_arc(tPoint p1, tPoint p2, tArc arc)
{
tPoint m = line_closest_point(p1, p2, arc.c);
tCoord r2 = arc.middle_vector_norm2;
tPoint cm = m - arc.c;
tCoord h2 = cm.norm2();
if (r2 < h2) return false; // no circle intersection
tPoint p1p2 = p2 - p1;
tCoord n2p1p2 = p1p2.norm2();
// works because by construction p is on (p1 p2)
auto in_segment = [&](const tFloatPoint & p) -> bool
{
tFloatCoord nk = p1p2.dot(p - p1);
return nk >= 0 && nk <= n2p1p2;
};
if (r2 == h2) return arc.contains(m) && in_segment(m); // tangent intersection
//if (p1 == p2) return false; // degenerate segment located inside circle
assert(p1 != p2);
tFloatPoint u = (tFloatPoint)p1p2 * sqrt((r2-h2)/n2p1p2); // displacement on (p1 p2) from m to one intersection point
tFloatPoint i1 = m + u;
if (arc.contains(i1) && in_segment(i1)) return true;
tFloatPoint i2 = m - u;
return arc.contains(i2) && in_segment(i2);
}
// test intersection of segments [a1 b1] and [a2 b2]
// segments may degenerate to points
bool inter_seg_seg(tPoint a1, tPoint b1, tPoint a2, tPoint b2)
{
tPoint u1 = b1 - a1;
tPoint u2 = b2 - a2;
tCoord det = u1.cross(u2);
tPoint link = a2 - a1;
if (det == 0) // parallel
{
if (link.cross(u1) != 0) return false; // disjoint
// 1st range bounds are not ordered while 2nd range's are
auto ranges_overlap = [](tCoord a1, tCoord a2, tCoord bmin, tCoord bmax)
{
return (a1 <= a2)
? (a1 <= bmax && a2 >= bmin)
: (a2 <= bmax && a1 >= bmin);
};
tCoord k1 = u1.dot(link);
tCoord k2 = u1.dot(b2 - a1);
return ranges_overlap(k1, k2, 0, u1.norm2());
}
else // secant
{
tCoord det2 = det*det;
tCoord k1 = link.cross(u1) * det;
if (k1 < 0 || k1 > det2) return false;
tCoord k2 = link.cross(u2) * det;
return k2 >= 0 && k2 <= det2;
}
}
// ============================================================================
// partitions of a snake into segments
// ============================================================================
class sPartition {
vector<int>segment;
public:
sPartition() {} // only used in vector inits
// split a flat snake into straight segments
sPartition(unsigned generator, unsigned num_joints)
{
int segment_len = 1;
for (size_t i = 0; i != num_joints; i++)
{
if (generator & 1)
{
segment.push_back(segment_len);
segment_len = 1;
}
else
{
segment_len++;
}
generator >>= 1;
}
segment.push_back(segment_len);
}
// direct access to underlying array of segment lengths
size_t size(void) const { return segment.size(); }
int & operator[] (size_t i) { return segment[i]; }
int operator[] (size_t i) const { return segment[i]; }
};
// ============================================================================
// compact storage of a configuration (64 bits)
// ============================================================================
struct sConfiguration {
unsigned partition;
unsigned folding;
sConfiguration(unsigned partition, unsigned folding) : partition(partition), folding(folding) {}
// textual representation
string text(unsigned length)
{
ostringstream res;
unsigned f = folding;
unsigned p = partition;
int segment_len = 1;
int direction = 1;
for (size_t i = 1; i != length; i++)
{
if (p & 1)
{
res << segment_len * direction << ',';
direction = (f & 1) ? -1 : 1;
segment_len = 1;
}
else segment_len++;
p >>= 1;
f >>= 1;
}
res << segment_len * direction;
return res.str();
}
// for final sorting
bool operator< (const sConfiguration& c) const
{
return (partition == c.partition) ? folding < c.folding : partition < c.partition;
}
// hash table setup
struct Hasher {
size_t operator() (const sConfiguration& c) const
{
return c.partition ^ c.folding;
}
};
struct Equalizer {
bool operator() (const sConfiguration& c1, const sConfiguration& c2) const
{
return c1.partition == c2.partition && c1.folding == c2.folding;
}
};
typedef unordered_set<sConfiguration, Hasher, Equalizer> set;
};
// ============================================================================
// snake ragdoll
// ============================================================================
class tSnakeDoll {
vector<tPoint>point; // snake geometry. Head at (0,0) pointing right
// allows to check for collision with the area swept by a rotating segment
struct rotatedSegment {
struct segment { tPoint a, b; };
segment org, end;
tArc arc[3];
bool extra_arc; // see if third arc is needed
// empty constructor to avoid wasting time in vector initializations
rotatedSegment(){}
// copy constructor is mandatory for vectors *but* shall never be used, since we carefully pre-allocate vector memory
rotatedSegment(const rotatedSegment &){ assert(!"rotatedSegment should never have been copy-constructed"); }
// rotate a segment
rotatedSegment(tPoint pivot, int rotation, tPoint o1, tPoint o2)
{
arc[0] = tArc(pivot, o1, rotation);
arc[1] = tArc(pivot, o2, rotation);
tPoint middle;
extra_arc = closest_point_within(o1, o2, pivot, middle);
if (extra_arc) arc[2] = tArc(pivot, middle, rotation);
org = { o1, o2 };
end = { o1.rotate(rotation, pivot), o2.rotate(rotation, pivot) };
}
// check if a segment intersects the area swept during rotation
bool intersects(tPoint p1, tPoint p2) const
{
auto print_seg = [&](const segment & s) { tprintf("(%d,%d)(%d,%d) -> (%d,%d)(%d,%d)", p1.x, p1.y, p2.x, p2.y, s.a.x, s.a.y, s.b.x, s.b.y); };
auto print_arc = [&](int a) { tprintf("(%d,%d)(%d,%d) -> %d (%d,%d)[%f,%f]", p1.x, p1.y, p2.x, p2.y, a, arc[a].c.x, arc[a].c.y, arc[a].middle_vector.x, arc[a].middle_vector.y); };
if (p1 == org.a) return false; // pivot is the only point allowed to intersect
if (inter_seg_seg(p1, p2, org.a, org.b)) { print_seg(org); return true; }
if (inter_seg_seg(p1, p2, end.a, end.b)) { print_seg(end); return true; }
if (inter_seg_arc(p1, p2, arc[0])) { print_arc(0); return true; }
if (inter_seg_arc(p1, p2, arc[1])) { print_arc(1); return true; }
if (extra_arc && inter_seg_arc(p1, p2, arc[2])) { print_arc(2); return true; }
return false;
}
};
public:
unsigned folding; // compressed folding list
int level; // ;!;
// holds results of a folding attempt
class snakeFolding {
friend class tSnakeDoll;
vector<rotatedSegment>segment; // rotated segments
unsigned joint;
int direction;
size_t i_rotate;
// pre-allocate rotated segments
void reserve(size_t length)
{
segment.clear(); // this supposedly does not release vector storage memory
segment.reserve(length);
}
// handle one segment rotation
void rotate(tPoint pivot, int rotation, tPoint o1, tPoint o2)
{
segment.emplace_back(pivot, rotation, o1, o2);
}
public:
// nothing done during construction
snakeFolding() {};
};
// empty default constructor to avoid wasting time in array/vector inits
tSnakeDoll() {}
// constructs ragdoll from compressed configuration
tSnakeDoll(unsigned size, unsigned generator, unsigned folding) : point(size), folding(folding)
{
tPoint direction(1, 0);
tPoint current = { 0, 0 };
size_t p = 0;
point[p++] = current;
for (size_t i = 1; i != size; i++)
{
current = current + direction;
if (generator & 1)
{
direction.rotate((folding & 1) ? -1 : 1);
point[p++] = current;
}
folding >>= 1;
generator >>= 1;
}
point[p++] = current;
point.resize(p);
}
// constructs the initial flat snake
tSnakeDoll(int size) : point(2), folding(0)
{
point[0] = { 0, 0 };
point[1] = { size, 0 };
level = 0;
}
// constructs a new folding with one added rotation
tSnakeDoll(const tSnakeDoll & start, const snakeFolding & fold)
{
point.resize(start.point.size()+1);
size_t i;
// copy unmoved points
for (i = 0; i != fold.i_rotate; i++) point[i] = start.point[i];
// copy rotated points
for (; i != start.point.size(); i++) point[i] = fold.segment[i - fold.i_rotate].end.a;
point[i] = fold.segment[i - 1 - fold.i_rotate].end.b;
// update folding bitfield
folding = start.folding;
if (fold.direction == -1) folding |= (1 << fold.joint);
level = start.level + 1;
//tprintf("snake doll level %d fold %X\n", level, folding);
}
// prepare one folding at a specified joint
// rotation is 1 for right, -1 for left
bool fold_at(unsigned joint, int rotation, snakeFolding & res) const
{
// first bend is only on the right
if (level == 0 && rotation == -1)
{
tprintf("1st left ");
return false;
}
res.joint = joint;
res.direction = rotation;
// locate folding point
joint++;
tPoint pivot;
size_t i_rotate = 0;
for (size_t i = 1 ; i != point.size(); i++)
{
unsigned len = point[i].manhattan_distance(point[i-1]);
if (len > joint)
{
pivot = point[i-1] + ((point[i] - point[i - 1]) / len) * joint;
i_rotate = i;
break;
}
else joint -= len;
}
res.i_rotate = i_rotate;
// rotate around joint
res.reserve(point.size() - i_rotate); // number of rotated segments
res.rotate(pivot, rotation, pivot, point[i_rotate]);
for (size_t i = i_rotate + 1; i != point.size(); i++) res.rotate (pivot, rotation, point[i-1], point[i]);
// check collisions
for (const rotatedSegment & fold : res.segment)
{
for (size_t i = 1; i != i_rotate; i++) if (fold.intersects(point[i], point[i - 1])) return false;
if (fold.intersects(pivot, point[i_rotate - 1])) return false;
}
return true;
}
};
// ============================================================================
// snake twisting engine
// ============================================================================
class cSnakeFolder {
int length;
unsigned num_joints;
unsigned reverse_start;
map<unsigned,sPartition>partitions;
sConfiguration::set config_hash;
// recursive folding
void fold(unsigned generator, tSnakeDoll snake, unsigned first_joint)
{
// filter redundant partitions
if (partitions.count(generator) == 0)
{
tprintf("%s %s P cut\n", string(snake.level, '|').c_str(), sConfiguration(generator, snake.folding).text(length).c_str());
return;
}
// filter redundant foldings
unsigned reverse = bit_reverse(snake.folding, num_joints);
if (reverse & 1) reverse = ~reverse & ((1<<num_joints)-1); // invert only significant bits
if (config_hash.count({ generator, reverse }))
{
tprintf("%s %s F cut\n", string(snake.level, '|').c_str(), sConfiguration(generator, snake.folding).text(length).c_str());
return;
}
// store this configuration
config_hash.emplace(generator, snake.folding);
// try to bend remaining joints
for (size_t joint = first_joint; joint != num_joints; joint++)
{
unsigned next_partition = generator | (1 << joint);
tSnakeDoll::snakeFolding bend;
tprintf("%s %s -> %s ", string(snake.level, '|').c_str(), sConfiguration(generator, snake.folding).text(length).c_str(), sConfiguration(next_partition, snake.folding).text(length).c_str());
if (snake.fold_at(joint, 1, bend))
{
tprintf("ok\n");
fold(next_partition, tSnakeDoll(snake, bend), joint + 1);
}
else tprintf("failed\n");
tprintf("%s %s -> %s ", string(snake.level, '|').c_str(), sConfiguration(generator, snake.folding).text(length).c_str(), sConfiguration(next_partition, snake.folding | (1 << joint)).text(length).c_str());
if (snake.fold_at(joint, -1, bend))
{
tprintf("ok\n");
fold(next_partition, tSnakeDoll(snake, bend), joint + 1);
}
else tprintf("failed\n");
}
}
public:
// all found configurations, in compressed format
vector<sConfiguration>configurations;
// constructor does all the job
cSnakeFolder(int n) : length(n)
{
num_joints = length - 1;
reverse_start = 1 << num_joints;
// generate snake partitions
unsigned num_part = 1 << num_joints;
for (unsigned partition = 0; partition != num_part; partition++)
{
// filter out symetric partitions
if (partitions.count(bit_reverse(partition, num_joints))) continue;
// generate and store partition
partitions[partition] = sPartition (partition, num_joints);
}
// launch recursive folding
fold(0, tSnakeDoll(length), 0);
// collect configurations
for (auto c : config_hash) configurations.emplace_back(c);
sort(configurations.begin(), configurations.end());
config_hash.clear(); // that's a huge lump of memory taken care of
}
// get a ragdoll representing a particular configuration
/*
For a snake of length N, the ragdoll is a list of N+1 points defining the N unitary segments.
By convention, the snake head starts at coordinates (0,0) pointing to the right.
*/
tSnakeDoll doll(size_t conf)
{
if (conf >= configurations.size()) conf = 0; // out of bounds queries will get a flat snake
sConfiguration & c = configurations[conf];
return tSnakeDoll(length, c.partition, c.folding);
}
// get text description of a particular configuration
/*
Absolute values are segment lengths
Sign indicate a preceding turn (by convention, positive for right, negative for left)
1st segment is always positive by convention.
Snake length is the sum of segment lengths absolute values.
___ For instance 2,-1,3 represents a snake of length 6 bent as
__| 2 segments, left turn, 1 segment, right turn, 3 segments
*/
string text(size_t conf)
{
if (conf >= configurations.size()) return "**out of bounds**";
return configurations[conf].text(length);
}
};
// ============================================================================
// here we go
// ============================================================================
int main(int argc, char * argv[])
{
#ifdef NDEBUG
if (argc != 2) panic("give me a snake length or else");
int length = atoi(argv[1]);
#else
(void)argc; (void)argv;
int length = 5;
#endif // NDEBUG
if (length <= 0 || length > MAX_LENGTH) panic("a snake of that length is hardly foldable");
time_t start = time(NULL);
cSnakeFolder snakes(length);
time_t duration = time(NULL) - start;
#ifndef NDEBUG
for (size_t i = 0; i != snakes.configurations.size(); i++) printf("%3d: %s\n", i, snakes.text(i).c_str());
#endif // NDEBUG
printf ("Found %d configuration%c of length %d in %lds\n", snakes.configurations.size(), (snakes.configurations.size() == 1) ? '\0' : 's', length, duration);
return 0;
}
Building the executable
Compile with g++ -O3 -std=c++11
I use MinGW under Win7 with g++4.8 for "linux" builds, so portabiity is not 100% guaranteed.
It also works (sort of) with a standard MSVC2013 project
Performances
It is my second computation-intensive challenge using STL new-ish hash tables (unordered_set), and again Microsoft implementation performs poorly, to say the least.
g++ build is 2.5 times faster and uses about 15% less memory.
On the other hand, I find Microsoft IDE a lot more convenient than Qt Creator, with better on-the-fly error checking and more powerful debug features.
The g++ build uses about 32 bytes/configuration.
A snake configuration is 8 bytes, the remaining 24 are mostly used by hash table internals.
For convenience I transfer the results from the hash table into a sorted vector in the end, which increases memory consumption significantly.
Even so, the program can compute up to n=19 before hitting the Win32 2Gb allocation limit, and compiling for x64 would allow to go a couple of steps beyond.
Since collision check is roughly in O(n), computation time should be in O(nkn), with k slightly lower than 3.
On my [email protected], n=19 takes about 4 minutes.
This means memory should be less an issue than speed.
Counting shapes
A N size snake has N-1 joints.
Each joint can be left straight or bent to the left or right (3 possibilities).
The number of possible foldings is thus 3N-1
However, many such foldings lead to identical shapes.
two shapes are identical if there is either a rotation or a symetry that can transform one into the other.
Let's define a segment as any straight part of the folded body.
For instance a size 5 snake folded at 2nd joint would have 2 segments (one 2 units long and the second 3 units long).
The first segment will be named head, and the last tail.
By convention we orient the snakes's head horizontally with the body pointing right (like in the OP first figure).
We designate a given figure with a list of signed segment lengths, with positive lengths indicating a right folding and negative ones a left folding.
Initial lenght is positive by convention.
Separating segments and bends
If we consider only the different ways a snake of length N can be split into segments, we end up with a repartition identical to the compositions of N.
Using the same algorithm as shown in the wiki page, it is easy to generate all the 2N-1 possible partitions of the snake.
Each partition will in turn generate all possible foldings by applying either left or right bends to all of its joints. One such folding will be called a configuration.
All possible partitions can be represented by an integer of N-1 bits, where each bit represents the presence of a joint. We will call this integer a generator.
Pruning partitions
By noticing that bending a given partition from the head down is equivalent to bending the symetrical partition from the tail up, we can find all couples of symetrical partitions and eliminate one out of two.
The generator of a symetrical partition is the partition's generator written in reverse bit order, which is trivially easy and cheap to detect.
This will eliminate almost half of the possible partitions, the exceptions being the partitions with "palindromic" generators that are left unchanged by bit reversal (for instance 00100100).
Taking care of horizontal symetries
With our conventions (a snake starts pointing to the right), the very first bend applied to the right will produce a family of foldings that will be horizontal symetrics from the ones that differ only by the first bend.
If we decide that the first bend will always be to the right, we eliminate all horizontal symetrics in one big swoop.
Mopping up the palindromes
These two cuts are efficient, but not enough to take care of these pesky palindromes.
The most thorough check in the general case is as follows:
consider a configuration C with a palindromic partition.
- if we invert every bend in C, we end up with a horizontal symetric of C.
- if we reverse C (applying bends from the tail up), we get the same figure rotated right
- if we both reverse and invert C, we get the same figure rotated left.
We could check every new configuration against the 3 others. However, since we already generate only configurations starting with a right turn, we only have one possible symetry to check:
- the inverted C will start with a left turn, which is by construction impossible to duplicate
- out of the reversed and inverted-reversed configurations, only one will start with a right turn.
That is the only one configuration we can possibly duplicate.
Order of generation
Clearly collision check will be the most time-consuming part, so the main avenue for optimization is to reduce these computations.
A possible solution is to have a "ragdoll snake" that will start in a flat configuration and be gradually bent, to avoid recomputing the whole snake geometry for each possible configuration.
By choosing the order in which configurations are tested, so that at most a ragdoll is stored for each total number of joints, we can limit the number of instances to N-1.
Collision check
When a snake folds around one joint, each rotated segment will sweep an area whose shape is anything but trivial.
Clearly you can check collisions by testing inclusion within all such swept areas individually, though a more global check would be more efficient.
After an interesting discussion with trichoplax and a bit of JavaScript to get my bearings, I devised a method that should enable to get an analytic description of the swept area under certain conditions.
To try to put it in a few words, if you call
- C the center of rotation,
- S a rotating segment of arbitrary lenght and direction that does not contain C,
- L the line prolongating S
- H the line orthogonal to L passing through C,
- I the intersection of L and H,
maths http://petiteleve.free.fr/SO/sweep.png
For any segment that does not contain I, the swept area is bound by 2 arcs and 2 segments.
If I falls within the segment, a third arc must be taken into account.
This means we can check each unmoving segment against each rotating segment with
- 2 segment-with-segment intersections
- 2 or 3 segment-with-arc intersections
I used vector geometry to avoid trigonometric functions altogether.
Vector operations produce compact and (relatively) readable code.
Better than most of the matrix crunching stuff I found on MathWorld or many gaming sites, anyway.
This allows to compute segment-with-segment intersections with integer values.
Segment-to-arc intersection requires a floating point vector, but the logic should be immune to rounding errors.
I found this elegant and efficient solution in an obscure forum post. I wonder why it is not more widely publicized.
Why does it not work?
I am not done tweaking the collision code yet, but it does not seem to explain why a very few configurations are not detected.
For n=4 I miss one snake though collision detection works as planned (eliminating only the "square" snake biting its own tail).
Most likely the cuts are just a tad bit too selective, but for now I am not able to pinpoint the logic error.