Skip to content

Instantly share code, notes, and snippets.

@mlhaufe
Created May 5, 2022 01:42
Show Gist options
  • Save mlhaufe/3752a9df86f73bb26c44bdf55d69f291 to your computer and use it in GitHub Desktop.
Save mlhaufe/3752a9df86f73bb26c44bdf55d69f291 to your computer and use it in GitHub Desktop.
12 islanders balancing problem
// Random Integer from m to n excluding e
const randInt = (m: number, n: number, e?: number): number => {
const result = Math.floor(Math.random() * m) + n;
return e == undefined ? result :
result == e ? randInt(m, n, e) :
result
}
class Person { constructor(public weight: number) {} }
const weight = (ps: Person[]) => ps.reduce((sum, next) => next.weight + sum, 0)
function findDifferentPerson(population: Person[]): Person | undefined {
if(population.length != 12)
return undefined
// split the population into three even groups (generalized as an odd number of even membered groups?)
const group1 = population.slice(0,4),
group2 = population.slice(4,8),
group3 = population.slice(8,12);
// 1. Weigh the first two groups
const wg1 = weight(group1),
wg2 = weight(group2)
if(wg1 == wg2) {
// Then group3 contains the candidate and every person in group1, group2 have the same weight
// Comparing group3 in its entirety to group1 or group2 will not gain us any additional information
// as the individual could weigh more or less. By the same argument we can't split group 3 in half
// and weigh as we don't know if the candidate is heavier or lighter
const [p1,p2,p3, ] = group1,
[q1,q2,q3,q4] = group3
// 2. choose 3 from the known group1 and candidate group3 to weigh
const weightG1 = weight([p1,p2,p3]),
weightG3 = weight([q1,q2,q3])
if(weightG1 == weightG3) {
// since every member of group1 has the same weight, the odd man out must be the one not weighed from group3
return q4
} else {
// The candidate must be one of (q1, q2, q3) since we know everyone in group1 has equal weight
// and the scale is unbalanced with the exclusion of q4.
// 3. weigh two of the candidate group3 against each other
const w1 = q1.weight,
w2 = q2.weight
if(w1 == w2) {
return q3 // scales balance so it must be the unweighed person
} else {
if(weightG1 < weightG3) // If the candidate group weighs more than the known group
return w1 < w2 ? q2 : q1 // then the heavier of q1 and q2 is the individual
else // Inversely, if the candidate group weighs less than the known group
return w1 < w2 ? q1 : q2 // then the lighter of q1 and q2 is the individual
}
}
} else {
// We now know that the unmeasured group3 contains people of equal weight
// we'll shuffle 3 of the people in each group to see if we can get the scales to change
const [p1,p2,p3,p4] = group1,
[q1,q2,q3,q4] = group2,
[ ,r2,r3,r4] = group3
const newGroup1 = [p1,q2,q3,q4], // remove 3 people from group1 and add 3 people from group2
newGroup2 = [q1,r2,r3,r4] // Add 3 people from the known group3
// 2. weigh the new groups
const weightG1 = weight(newGroup1),
weightG2 = weight(newGroup2)
if(weightG1 == weightG2) {
// By making the scales equal, we know the candidate is in the removed group: (p2,p3,p4)
// 3. weigh two of the remaining against each other:
const w2 = p2.weight,
w3 = p3.weight
if(w2 == w3) {
return p4 // scales balance so it must be the unweighed person
} else {
if(wg1 < wg2) // if group1 is lighter than group2
return w2 < w3 ? p3 : p2; // The heavier person is the candidate
else // if group1 is heavier than group2
return w2 < w3 ? p2 : p3; // The lighter person is the candidate
}
} else {
if(wg1 > wg2 && weightG1 > weightG2) {
// if we shuffled the group and the weight didn't change then one of the unmoved people is the candidate (p1 or q1)
// 3. weigh the remaining two
const wp1 = p1.weight,
pq1 = q1.weight
if(weightG1 < weightG2) // If the candidate group weighs more than the known group
return wp1 < pq1 ? q1 : p1 // it's the heavier person
else // Inversely, if the candidate group weighs less than the known group
return wp1 < pq1 ? p1 : q1 // it's the lighter person
} else {
// we shuffled the groups and the weights swapped. The candidate must be in moved subgroup (q2,q3,q4)
// 3. weigh two of the candidate group3 against each other
const w2 = q2.weight,
w3 = q3.weight
if(w2 == w3) {
return q4 // scales balance so it must be the unweighed person
} else {
if(weightG1 < weightG2) // If the candidate group weighs more than the known group
return w2 < w3 ? q3 : q2 // then the heavier of q1 and q2 is the individual
else // Inversely, if the candidate group weighs less than the known group
return w2 < w3 ? q2 : q3 // then the lighter of q1 and q2 is the individual
}
}
}
}
}
// The population of the island
const population = Array.from({length: 12}, () => new Person(160));
// One person has a different weight
population[randInt(0,11)].weight = randInt(140,280, 160)
// Find the different person
console.log(findDifferentPerson(population))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment