19
\$\begingroup\$

It's the end of the year, you and your friends have just received your grades and ranks for the GOLF101 class. On a chat group, everyone sends their grade and rank to see who's got the best one.

Problem: someone is lying.

Here is an excerpt from the chat:

<A> I'm ranked 1 with a grade of 85.
<B> Ranked 3, got 50.
<C> Ranked 1st, prof. gave me 65/100.
<D> Got ranked second with 70/100

Obviously here, student C is lying (at least) on their rank; they can't be 1st with a grade of 65 since both A and D got a better grade.

There can also be cases where someone is lying but we can't know who, specifically.

Rank | Grade
-------------
  2     71
  1     80
  3     60
  2     70

Here, one of the two rank-2 students is lying (since two students can't have the same rank while having different grades) but we can't know which one.

Challenge

Create a function or program that, when given a sequence of (rank, grade) tuples which contains exactly one lie, returns the index of the lie in the list or a sentinel value if is impossible to know.

A lie is a tuple that, when removed from the list, makes the list valid (i.e. without any conflicting ranks/grades).

A valid list contains all the possible ranks starting from 1 (or 0 if you use 0-indexing), so the rank sequence 1 2 3 is valid while 2 3 4 is not. The only way to not have every possible rank is when there are equal grades, in which case you can get sequences like 1 2 2 or 1 2 3 3 3.

Multiple tuples may have the same grade, in which case they will have the same rank, and other tuples' ranks will not be affected. Two tuples having the second-best grade will lead to the sequence 1 2 2 4 ....

The input format is not fixed, you may use whatever is easier to parse for your language (a 2D int array, a list of tuples, a list of strings containing space-separated ints). The logic is more important than the parser's implementation details.

The output format is not fixed either. The "index" returned may be 0-based or 1-based, and the sentinel value can be anything that is clearly distinguishable from an index (if you're using 1-based indexing, 0 is a valid sentinel value).

Test Cases

Rank | Grade
-------------
  2     71
  1     80
  3     60
  2     70

Output: impossible to know

Rank | Grade
-------------
  1     85
  3     50
  1     65
  2     70

Output: third student

Rank | Grade
-------------
  1     85
  3     50
  1     65
  2     70

Output: third student

Additional cases, thanks to @tsh:

  • [(1, 100), (2, 60), (3, 90), (3, 90)] -> invalid input because we can't remove a single item to get a valid list
  • [(1, 100), (1, 100), (2, 90), (3, 90)] -> fourth (if we remove the third we get an invalid list with ranks [1, 1, 3])

This is , so the lowest byte count for each language wins!

EDIT: printing multiple values is a valid sentinel as long as you specify it. 0-indexing for ranks is fine too.

\$\endgroup\$
23
  • 7
    \$\begingroup\$ Is it acceptable to output a list of all potential liars, when there are more than 1? \$\endgroup\$ Feb 22, 2021 at 19:24
  • 1
    \$\begingroup\$ Can we use 0-indexing for ranks? \$\endgroup\$
    – Shaggy
    Feb 22, 2021 at 19:24
  • 3
    \$\begingroup\$ Multiple tuples may have the same grade, in which case they will have the same rank: you should probably include some test cases covering this (I think my current solution would fail on them). \$\endgroup\$
    – Arnauld
    Feb 22, 2021 at 20:01
  • 1
    \$\begingroup\$ @Jonah, "other tuples' ranks will not be affected". \$\endgroup\$
    – Shaggy
    Feb 22, 2021 at 21:10
  • 4
    \$\begingroup\$ @tsh You say that all current answers are invalid but without OP confirming, it could be possible that you’re wrong, or that you’ve misunderstood the challenge. I would wait for OP to confirm that specific test cases are what you say they are before commenting on every answer that it fails to work for an example you’ve just come up with \$\endgroup\$ Feb 25, 2021 at 4:12

2 Answers 2

6
\$\begingroup\$

J, 49 47 22 bytes

[:I.1(-:\:~i.])/@|:\.]

Try it online!

-14 bytes after reading xigoi's idea of comparing the first index matches to the ranks.

Thanks to tsh for a test case showing that we needed "length not equal to 1" rather than "length greater than 1" as the failure criterion.

Returns 0-based index if exactly one liar is found, and 0 or multiple values otherwise. Takes "length" by 2 matrix with 0-indexed rank list as left column, score list as right column.

  • 1...\.] For each 1-item outfix (list with item removed), apply the verb...
  • (...)/@|: Transpose and put the verb in parens between the two rows, so that the rank list is its left arg, and the score list is its right arg.
  • -:\:~i.] Does the rank list match -: the first index of the score list i.] within the score list sorted descending \:~? We now have a 0-1 list, where 1 indicates a liar.
  • [:I. Return the indexes of all ones.
\$\endgroup\$
3
  • 1
    \$\begingroup\$ From the edit into the question: “ printing multiple values is a valid sentinel as long as you specify it.”, so you might be able to save 11 bytes? \$\endgroup\$ Feb 23, 2021 at 5:15
  • \$\begingroup\$ g 1 90 1 90 1 90 2 80. 2 80 is lying. 1 90 1 90 2 80 is still invalid as after 2 rank 1, the grade 80 should be rank 3 not 2. \$\endgroup\$
    – tsh
    Feb 25, 2021 at 6:17
  • \$\begingroup\$ @tsh For 0 90 0 90 1 80 -- If I remove any single 1 of them, the remaining 2 are valid. So all 3 could be the liar. This is what my code says, it returns 0 1 2. Am i missing something? For 0 90 0 90 0 90 1 80, my code identifies 80 as the liar. \$\endgroup\$
    – Jonah
    Feb 25, 2021 at 14:33
4
\$\begingroup\$

Jelly, 15 bytes

ṙJṖZNÞiⱮḷ⁼ʋ/Ɗ€T

Try it online!

I'm pretty sure it works correctly with the multiple equal grades rule, but I'd appreciate a testcase for that.

Takes a list of [grade, rank]. Returns a 1-indexed list of all possible liars.

Explanation

ṙJṖZNÞiⱮḷ⁼ʋ/Ɗ€T   Main monadic link
ṙ                 Rotate left by
 J                  all of [1..length]
             €    For each rotation
            Ɗ     (
  Ṗ                 Pop (remove the last pair)
   Z                Zip, change to a pair of [grades, ranks]
           /        Reduce by
          ʋ         (
     Þ                Sort the grades by
    N                   their negation
      iⱮḷ             Find the first index of each grade in the reverse-sorted grades
         ⁼            Is this equal to the list of ranks?
          ʋ         )
            Ɗ     )
              T   Find the indices where this is true
\$\endgroup\$
6
  • \$\begingroup\$ Failed: [[1, 100], [2, 60], [3, 90], [3, 90]], \$\endgroup\$
    – tsh
    Feb 25, 2021 at 2:43
  • \$\begingroup\$ @tsh That's not a valid test case, there's not a single student you can remove to make the order correct. \$\endgroup\$
    – xigoi
    Feb 25, 2021 at 6:47
  • \$\begingroup\$ Sorry for wrong order: It should be [[100,1],[60,2],[90,3],[90,3]]. Changing [60, 2] to [95, 2] makes everything valid, I believe. So [60, 2] is the student lying. \$\endgroup\$
    – tsh
    Feb 25, 2021 at 7:20
  • \$\begingroup\$ @tsh You're not supposed to change a student, but to remove a student. \$\endgroup\$
    – xigoi
    Feb 25, 2021 at 7:47
  • 1
    \$\begingroup\$ @tsh [(100, 1), (90, 3), (90, 3)] does have a conflict. The two students with 90 are in 2nd place, not in 3rd place. \$\endgroup\$
    – xigoi
    Feb 25, 2021 at 12:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.