Anagram Test with Unicode Letters is Flawed

Exercism Support
1

I was creating the Anagram test for a new track (Odin) and realized that one of the test is flawed.

The Test in question is:

 {
      "uuid": "a6854f66-eec1-4afd-a137-62ef2870c051",
      "description": "handles case of greek letters",
      "scenarios": ["unicode"],
      "property": "findAnagrams",
      "input": {
        "subject": "ΑΒΓ",
        "candidates": ["ΒΓΑ", "ΒΓΔ", "γβα", "αβγ"]
      },
      "expected": ["ΒΓΑ", "γβα"]
    },

This test is the only one using Unicode, with, I suspect, the goal to prevent people just converting the word and candidate strings to bytes, sorting them and then comparing. It looks like the test is designed to force them to process the string as unicode characters.

But I did just that (convert to a bunch of bytes and sort the two strings before comparing) and, to my surprise, the test passed.

The problem is that all 6 letters used in that case “ΒΓΔγβα” have the same upper byte (0x03) so when I break (accidentally) the unicode characters into their separate bytes and sort them, I end up with the same six top bytes followed by the 6 lower bytes and the comparison passes.

To make the test fail when the student forget to deal with unicode, we should have at least one of the six letter have a different upper byte (we may have to mix greek and chinese for example).

Note: the next exercise, compare “a⬂”, “€a” which have the same bytes and therefore require the student to deal with unicode for the test not to fail. So this is really not a big deal as they can’t pass all the tests without dealing with unicode.

2

Do you have a specific test you’d like to propose adding?

3

Putting a prior discussion here for context.

As a reminder: the instructions for the exercise were never changed. They still say:

The target word and candidate words are made up of one or more ASCII alphabetic characters (A -Z and a -z ). Lowercase and uppercase characters are equivalent: for example, "PoTS" is an anagram of "sTOp" , but "StoP" is not an anagram of "sTOp" . The words you need to find should be taken from the candidate words, using the same letter case.

Which may be part of the problem, since there are Greek letters in ASCII. But is also a problem, because these instructions contradict the named test.

I don’t think this exercise is the place for additional canonical tests that include Unicode, for many reasons. If we’d like students to deal with the intricacies of unicode and significant bytes, we are better off either purpose-building a new exercise or further modifying exercises such as reverse-string and microblog, and others.

And yes - tracks can opt out of tests. But given the way different languages handle Unicode, it feels better to have tracks supplement their tests with Unicode if desired (and amend their instructions), rather than add a bunch of things that then need to be skipped.

1 Like
4

TLDR;

  • The exercise as designed is fine, no changes needed. I jumped the gun too fast (apologies).
  • The last two tests are definitively using non-ASCII characters (i.e. characters not between 1-255).

The long story:

I wrote that email last night and I got a chance to think about it some more this morning.

To the question: do you have a specific test you’d like to propose adding? My response is no. I have convinced myself that the test can’t be improved.

The greek letters (at least in Odin which uses UTF-8) are not ASCII because they are two bytes long (My definition of ASCII is code from 0 to 255). The problem I thought I had was that my solution sorts the bytes from the (UTF-8) string in ascending order and compare the word and the anagram candidate. I had it in my head that, because for unicode characters I am breaking up each code point into individual bytes and shuffling them around, my algorithm would fail for words containing non ASCII characters.

But this is not the case. I was confused last night because I thought that if the unicode characters have the same high bytes (D0) , then my solution would work (A (D0 91), α (D0 B1), B (D0 92), β (D0 B2), Γ (D0 93), γ (D0 B3) but that if there were different, then it would fail.

I looked for an example with such characters and found one with Korean names. Suzy (수지) and Jisoo (지수)
are obvious anagrams and the two characters have different sets of bytes (수 (Su) EC 88 98 vs. 지 (Ji) EC A7 80) but if you think about it, it doesn’t matter when they are true anagram. Because they are anagrams, the sets of UTF-8 bytes in each word is the same, just in a different order, so I can just compare the bytes.

In short, there is nothing wrong with the example as it is defined today. There is no way to improve it to make it fail if the student assumes the words are ASCII because a byte-wise comparison is sufficient to check that two true anagrams are the same.

What can happen, if you are assuming ASCII, is that when re-ordering the bytes you can find two different characters with the same set of bytes in UTF-8 and a byte-wise comparison will falsely return a match. This is what the next test case is designed to detect. It uses the fact that the unicode characters ⬂ (E2 AC 82) and € (E2 82 AC) have the same set of UTF-8 bytes but are obviously different. The only way to solve the last exercise is to compare the unicode code points (or their UTF-8 equivalent) atomically.

 {
      "uuid": "fd3509e5-e3ba-409d-ac3d-a9ac84d13296",
      "description": "different characters may have the same bytes",
      "comments": ["a⬂ => 61 E2 AC 82", "€a => E2 82 AC 61"],
      "scenarios": ["unicode"],
      "property": "findAnagrams",
      "input": {
        "subject": "a⬂",
        "candidates": ["€a"]
      },
      "expected": []
    }

Sorry for commotion I may have caused.

2 Likes
5

It may be worth noting that we have extra tests that you do not NEED to implement. Sometimes they have comments in the problem spec to explain why they exist, and often they have a keyword there.