Celebrity Problem in one line of code

Arrow from-to, e.g., Dante knows Pat

Goal

The object of this article is to write an algorithm which solves the Celebrity Problem in one single line of code.

The provided solution is not the most optimal one, because the idea here is to focus on the most possible dense code.

Problem

N people attend a party. Identify the celebrity among the attendees.

A celebrity is a person who is known to everyone but does not know anyone at the party.

Solution

type Attendee = {
  id: string;
  knows: Array<Attendee['id']>;
}

const getCelebrity = (attendees: Array<Attendee>) =>
 attendees.find(x => attendees.filter(a => a.id !== x.id).every(k => k.knows.includes(x.id)) && !x.knows.some(k => attendees.map(a => a.id).includes(k)));

Bonus

Let’s describe briefly on how the algorithm works.

type Attendee = {
  id: string;
  knows: Array<Attendee['id']>;
}

// check if a given attendee is among each attendees' acquaintances.
// remove first the given attendee from the attendees.
const isKnownToAll = (x: Attendee, attendees: Array<Attendee>) => 
  attendees.filter(a => a.id !== x.id).every(k => k.knows.includes(x.id));

// check if the given attendee knows someone among attendees.
const knowsSomeone = (x: Attendee, attendees: Array<Attendee>) =>
  x.knows.some(k => attendees.map(a => a.id).includes(k));

const isACelebrity = (x: Attendee, attendees: Array<Attendee>) =>
  isKnownToAll(x, attendees) && !knowsSomeone(x, attendees);

const getCelebrity = (attendees: Array<Attendee>) =>
  attendees.find(a => isACelebrity(a, attendees));

Test

Let’s run the algorithm to demonstrate that it does do the job.

const tijl: Attendee = { id: 'Tijl', knows: ['Dragos', 'Dante'] };
const tom: Attendee = { id: 'Tom', knows: ['Dragos', 'Pat'] };
const pat: Attendee = { id: 'Pat', knows: ['Dragos'] };
const dragos: Attendee = { id: 'Dragos', knows: [] };
const dante: Attendee = { id: 'Dante', knows: ['Dragos', 'Barbara', 'Pat'] };
const barbara: Attendee = { id: 'Barbara', knows: ['Dragos'] };
const flora: Attendee = { id: 'Flora', knows: ['Dragos', 'Tom'] };

const atts:Array<Attendee> = [tijl, tom, pat, dragos, dante, barbara, flora];

console.log('The celebrity is:', getCelebrity(atts)?.id ); // Dragos

Takeaway

Expressiveness is a technical term — often misused — referring to the ability of a given programming language to express intent in, in a dense way (density = ideas / characters) leaving the implementation details to the compiler.

Functional programming languages tend to be more expressive because they provide abstractions (first-class function, higher-order function, anonymous function, currying, closure, monad, functor) allowing a better composition of functions. They also empower stateless code. No single variable has even been declared in the provided solution.

The provided solution shows that TS is quite an expressive programming language. TS expressiveness is due to the fact that JS — TS’s cousin — embraces a strong functional flavor from its conception. Indeed, the JS designer borrowed some concepts from Scheme, back in 1995. Feel free to check an entire article I wrote on that matter.