[Community Puzzle] Find the Replacement

Puzzles
1

https://www.codingame.com/training/medium/find-the-replacement

There is something hinky with either the validators or the test cases. My code does not pass validator 5 (Random, all different), but passes the test cases 100%.

If I don’t check for endless loops, my algorithm correctly identifies all of the changes the validator is looking for, then will just infinitely cycle between two letters.

Has anyone else seen this behavior.

2

Hello, validator 5 contains letters and uppercase letters. Like all other test cases, there exists a set of replacements A->B such that 1. A does not repeat, and 2. multiple replacements may point to B.

Due to the nature of the problem requiring the output to print found replacements in the same order as they are found (output specification), if the dict / set type in your language does not maintain order, you may need to keep a separate ordered array to complement your solution to prevent printing them in the wrong order and being considered a wrong solution. If you already have that covered, as the test case is long, you may need to use a lookup table for efficiency if your current implementation uses multiple nested loops to prevent timeouts.

1 Like
3

i don’t understand the case who return CAN’T
how can we obtain the state “CAN’T”???

4

I’m not really sure about what you’re asking… Do you have a problem in understanding the puzzle statement, or do you have a problem with a particular test case? Please provide more details.

5

for the output we have this : " If not possible: One line: CAN’T" but i don’t know how get this state exemple for test 3 why the ouput is can’t ?? i don’t understand the requirement to get " CAN’T"

6

The mapping must be consistent, so with the following input:

AA
BC

The output should be CAN’T, because the letter ‘A’ can’t be mapped to both ‘B’ and ‘C’.

7

ok thanks you it’s good now

8

Very belated reply to @kjasghlisuagerhdfn;
Yes I have the same behaviour for test case 5 ‘Random, all different’.

I believe test case has a slight error;
In test case output, the change ‘s->k’ is done before change ‘k->d’, so initial s characters will end up as d’s.
This change (‘s->k’) should be after change ‘k->d’ as below.

Test Input 
i pdnwspak aeeomaegant ganwua ediap ons
yzzdhfkzfdzfjjfkfjkfhzzkfhfzfzjdyfzzfhk
Test Output 
i->y
 ->z
p->z
n->h
w->f
s->k   * -> remove s->k
a->f
k->d
       * <- insert s->k (after k->d change)
e->j
o->f
m->k
g->k
t->z
u->z
9

Actually, Test 5 “Random, all different” doesn’t contain an error. However, the statement is ambiguous about whether the replacement sequences are applied sequentially to the modified string or independently to the original characters.

The intended behaviour is the second approach.

Do you think it’d help if I added the following paragraph to the statement?

The replacement sequences are always applied based on the characters of the original text X. For example, if a character FROM1 is replaced with TO1, it cannot be replaced again by a later rule that replaces TO1 with TO2.

10

Apologies - I was making it harder than necessary.
Interesting that only one test and no validators had issues with the alternative approach - built in ambiguity allowance feature :slight_smile:

Yes, the extra paragraph makes intended behavior clear.

Thanks for the quick reply!

1 Like