[Community Puzzle] Jump the Queue - Puzzle discussion

Puzzles
1

Coding Games and Programming Challenges to Code Better

Send your feedback or ask for help here!

Created by @java_coffee_cup,validated by @TBali,@selenae and @Ayza.
If you have any issues, feel free to ping them.

2

Hi,

While it is mentionned :

“When a student comes and wants to join the queue, he will search the queue from head to tail to check if any of his friends are already in the queue”

It looks like the tests and validators expect this :

“When a student comes and wants to join the queue, he will search the queue from tail to head to check if any of his friends are already in the queue”

(swap the words ‘head’ and ‘tail’)

Am I wrong ?

Nice puzzle anyway…

1 Like
3

Can you give an example?

4

I proposed the phrase before (the one actually present but is not what the tests and validators check) and the replacement phrase, which is how the game actually behaves.

I’m not sure I understand your question.

Perhaps we misuderstand the words ‘head’ and ‘tail’ for a queue. To me ‘head’ represents the student that is the closest from the food counter, i.e. the one that will next be served, while the tail is the last who came into the queue.

5

That’s the correct interpretation, but can you give an example of why you think the tests and validators expect the search is from tail to head? For example, can you simulate one of the cases step by step to illustrate your point?

6

When a new student arrives, if you look at the queue from the head to the tail in order to find another student that belongs to the same group, some tests will fail.

If you look at the queue from the tail to the head, all tests and validators are OK ; that’s why I suggest the correction above.

While reviewing other users code after finishing the puzzle, I noted that one of them had noted this point as a comment in his code.

Do you want me to send you my code (and how) so that you can verify this point by yourself ?

7

I don’t understand how. Can you explain your point with reference to Test 1?

Input

2 14
111 112 113
221 222 223
111 222 333 112 223 113 221 -1 -1 -1 -1 -1 -1 -1

Output

111
112
113
222
223
221
333
8

Let’s say 333 was first in line, then a friend from his friend group (say 222 from the friend group 111 222 333) entered the queue, he’d be inserted right before 333 as expected.

However, when 111, the final one, enters the queue, then if the search was truly head-to-tail, he’d be inserted right behind 333 too, but contrary to that, he’s inserted behind 222, because it’s a tail-to-head search, a more “first to enter has the higher priority to skipping” approach.

It’s a good catch, I think the statement should be edited.

9

I think @ChristopheLa and @Ayza you both misunderstood the statement. The search is head to tail.
However, the sentence “If any friend is found, he will jump the queue to insert himself right behind his friend group in the queue” means: If you find a first friend (searching from head to tail), you still need to check if this friend is alone or there are multiple friends from the same friend group who are waiting in the queue together. You are inserted AFTER the last member of this friend group. (The first such group you found starting from the head.)

3 Likes
10

Right, I forgot about that part. Indeed, they get inserted right behind their current friend group in the queue.

11

I think I get it : Since no group can be split, you always get the same result if you :

  • search from head to tail and insert behind the last group member you find
  • search from tail to head and insert behind the first group member you find

Thanks for the comments.