The procedure given below is required to find and replace certain characters…
20132013
The procedure given below is required to find and replace certain characters inside an input character string supplied in array \(A\). The characters to be replaced are supplied in array \(oldc\), while their respective replacement characters are supplied in array \(newc\). Array \(A\) has a fixed length of five characters, while arrays \(oldc\) and \(newc\) contain three characters each. However, the procedure is flawed.
void find_and_replace (char *A, char *oldc, char *newc) {
for (int i = 0; i < 5; i++)
for (int j = 0; j < 3; j++)
if (A[i] == oldc[j])
A[i] = newc[j];
}The procedure is tested with the following four test cases.
(1) \(oldc = “abc”, newc = “dab” \) (2) \(oldc = “cde”, newc = “bcd”\)
(3) \(oldc = “bca”, newc = “cda” \) (4) \(oldc = “abc”, newc = “bac”\)
If array A is made to hold the string \(“abcde”\), which of the above four test cases will be successful in exposing the flaw in this procedure?
- A.
None
- B.
2 only
- C.
3 and 4 only
- D.
4 only
Attempted by 32 students.
Show answer & explanation
Correct answer: C
Concept
The replacement is meant to be a simultaneous (single-pass) substitution: each ORIGINAL character of the string should be mapped exactly once using the oldc -> newc table. A correct implementation must decide every character's replacement from the ORIGINAL string only.
The given code instead overwrites A[i] in place and then KEEPS scanning the rest of oldc. So a character that was just written can match a LATER entry of oldc and be replaced a second time. This chaining (a write feeding a later comparison) is the bug; it shows up only when a replacement character also appears as a still-unscanned old character for the same position.
How to test a case
Compute the intended result: map each original character once (simultaneous mapping).
Simulate the code: for each
A[i], applyoldc[j]==A[i] -> A[i]=newc[j]for j=0,1,2 in order, letting later j see what earlier j wrote.If the two results differ, that test case exposes the flaw.
Input string is always A = "abcde".
Case-by-case
oldc="abc", newc="dab" (a->d, b->a, c->b)
Intended: a->d, b->a, c->b gives
"dabde".Code: each written character (d, a, b) is not a later old character at its position, so no second hit; code gives
"dabde".Results match -> does NOT expose the flaw.
oldc="cde", newc="bcd" (c->b, d->c, e->d)
Intended: c->b, d->c, e->d gives
"abbcd".Code: the written characters (b, c, d) never match a still-unscanned old character for the same position, so no chaining; code gives
"abbcd".Results match -> does NOT expose the flaw.
oldc="bca", newc="cda" (b->c, c->d, a->a)
Intended: b->c, c->d, a->a gives
"acdde".Code at the 'b' position: j=0 writes 'c'; j=1 then sees that 'c' (it equals the next old char) and rewrites it to 'd'. The position becomes 'd' instead of 'c'. Code gives
"addde".Results differ (
"addde"vs"acdde") -> EXPOSES the flaw.
oldc="abc", newc="bac" (a->b, b->a, c->c)
Intended: a->b, b->a, c->c gives
"bacde".Code at the 'a' position: j=0 writes 'b'; j=1 then sees that 'b' (it equals the next old char) and rewrites it to 'a'. The position becomes 'a' instead of 'b'. Code gives
"aacde".Results differ (
"aacde"vs"bacde") -> EXPOSES the flaw.
Summary
oldc / newc | intended | code output | exposes flaw? |
|---|---|---|---|
abc / dab | dabde | dabde | no |
cde / bcd | abbcd | abbcd | no |
bca / cda | acdde | addde | yes |
abc / bac | bacde | aacde | yes |
The two cases where a freshly written character matches a later old character are the ones that fail, i.e. the pair "bca"/"cda" and the pair "abc"/"bac".
Cross-check / fix
The bug needs a replacement char to equal a later old char at the same position. That happens exactly in the two failing cases above and in neither of the other two. To fix the routine, read from an unmodified copy of A (decide every output from the original), or break out of the inner loop after the first match so each character is replaced at most once.