Puzzles: floors, boxes and schedules

// The lesson's five solved examples: the intern grid solved by marking ticks and crosses the way a person does on
// paper (and checked against all 518,400 assignments), the hostel floors, a stack of boxes, a team selection with
// conditions, and a five-team league table.

/** Calls visit(order) for every order of 0..n-1 (Heap's method; the array is reused between calls). */
function eachOrder(n, visit) {
  const a = Array.from({ length: n }, (_, i) => i);
  const c = new Array(n).fill(0);
  visit(a);
  let i = 1;
  while (i < n) {
    if (c[i] < i) {
      const j = i % 2 === 0 ? 0 : c[i];
      const t = a[j];
      a[j] = a[i];
      a[i] = t;
      visit(a);
      c[i]++;
      i = 1;
    } else {
      c[i] = 0;
      i++;
    }
  }
}

// 1. Six interns, six cities, six languages.
const P = ['Aarav', 'Bhumi', 'Chirag', 'Dia', 'Eshan', 'Fatima'];
const C = ['Bengaluru', 'Chennai', 'Hyderabad', 'Jaipur', 'Kochi', 'Pune'];
const L = ['Go', 'Java', 'Kotlin', 'Python', 'Rust', 'TypeScript'];
const p = (x) => P.indexOf(x);
const c = (x) => C.indexOf(x);
const l = (x) => L.indexOf(x);

// Three grids of ticks (1), crosses (-1) and blanks (0): intern-city, intern-language and city-language.
const grid = (n) => Array.from({ length: n }, () => new Array(n).fill(0));
const PC = grid(6);
const PL = grid(6);
const CL = grid(6);
const trace = [];
let contradiction = false;
let marks = 0;
function mark(g, i, j, v, why) {
  if (g[i][j] === v) return false;
  if (g[i][j] !== 0) contradiction = true;
  g[i][j] = v;
  marks++;
  if (v === 1) trace.push(why);
  return true;
}
// The clues, as the ticks and crosses they give directly.
mark(CL, c('Kochi'), l('Java'), 1, 'clue 1: Kochi writes Java');
for (const x of ['Python', 'Java']) mark(PL, p('Bhumi'), l(x), -1);
mark(PC, p('Bhumi'), c('Pune'), -1);
for (const x of C) if (x !== 'Bengaluru' && x !== 'Hyderabad') mark(PC, p('Dia'), c(x), -1);
mark(PL, p('Dia'), l('TypeScript'), -1);
mark(CL, c('Pune'), l('Python'), 1, 'clue 4: Pune writes Python');
mark(PL, p('Fatima'), l('TypeScript'), 1, 'clue 5: Fatima writes TypeScript');
for (const x of ['Kochi', 'Pune', 'Chennai']) mark(PC, p('Aarav'), c(x), -1);
mark(CL, c('Chennai'), l('Go'), 1, 'clue 7: Chennai writes Go');
mark(PC, p('Eshan'), c('Pune'), -1);
mark(CL, c('Hyderabad'), l('Rust'), -1);
mark(CL, c('Jaipur'), l('Kotlin'), 1, 'clue 10: Jaipur writes Kotlin');

/** One pass of the paper rules; returns true when it changed anything. */
function pass() {
  let changed = false;
  const names = [[PC, P, C], [PL, P, L], [CL, C, L]];
  for (const [g, rows, cols] of names) {
    for (let i = 0; i < 6; i++) {
      for (let j = 0; j < 6; j++) {
        if (g[i][j] !== 1) continue;
        for (let k = 0; k < 6; k++) {
          if (k !== j) changed = mark(g, i, k, -1) || changed;
          if (k !== i) changed = mark(g, k, j, -1) || changed;
        }
      }
      const rowOpen = [0, 1, 2, 3, 4, 5].filter((j) => g[i][j] !== -1);
      if (rowOpen.length === 0) contradiction = true;
      if (rowOpen.length === 1) changed = mark(g, i, rowOpen[0], 1, `only ${cols[rowOpen[0]]} is left for ${rows[i]}`) || changed;
      const colOpen = [0, 1, 2, 3, 4, 5].filter((k) => g[k][i] !== -1);
      if (colOpen.length === 0) contradiction = true;
      if (colOpen.length === 1) changed = mark(g, colOpen[0], i, 1, `only ${rows[colOpen[0]]} is left for ${cols[i]}`) || changed;
    }
  }
  // Ticks and crosses carried between the grids: an intern's city and the city's language give the intern's language.
  for (let i = 0; i < 6; i++) {
    for (let j = 0; j < 6; j++) {
      for (let k = 0; k < 6; k++) {
        if (PC[i][j] === 1 && CL[j][k] !== 0) changed = mark(PL, i, k, CL[j][k], `${P[i]} is from ${C[j]}, which writes ${L[k]}`) || changed;
        if (PC[i][j] === 1 && PL[i][k] !== 0) changed = mark(CL, j, k, PL[i][k], `${C[j]} is ${P[i]}'s city`) || changed;
        if (PL[i][k] === 1 && CL[j][k] !== 0) changed = mark(PC, i, j, CL[j][k], `${P[i]} writes ${L[k]}, which goes with ${C[j]}`) || changed;
        if (PL[i][k] === 1 && PC[i][j] === -1) changed = mark(CL, j, k, -1) || changed;
        if (CL[j][k] === 1 && PC[i][j] === -1) changed = mark(PL, i, k, -1) || changed;
        if (CL[j][k] === 1 && PL[i][k] === -1) changed = mark(PC, i, j, -1) || changed;
      }
    }
  }
  return changed;
}
let passes = 0;
while (pass()) passes++;
const solved = PC.every((row) => row.filter((v) => v === 1).length === 1) && PL.every((row) => row.filter((v) => v === 1).length === 1);
console.log(`1. The intern grid: ${solved && !contradiction ? 'solved' : 'not solved'} by ticks and crosses alone, ${passes} passes, ${marks} marks, no guess`);
console.log(`   The ticks, in the order they appear: ${trace.join('; ')}`);
for (let i = 0; i < 6; i++) console.log(`   ${P[i]}: ${C[PC[i].indexOf(1)]}, ${L[PL[i].indexOf(1)]}`);

// The same puzzle the slow way: every city order times every language order.
const clues = [
  (city, lang) => lang[city.indexOf(c('Kochi'))] === l('Java'),
  (city, lang) => lang[p('Bhumi')] !== l('Python') && lang[p('Bhumi')] !== l('Java') && city[p('Bhumi')] !== c('Pune'),
  (city, lang) => (city[p('Dia')] === c('Bengaluru') || city[p('Dia')] === c('Hyderabad')) && lang[p('Dia')] !== l('TypeScript'),
  (city, lang) => city[lang.indexOf(l('Python'))] === c('Pune'),
  (city, lang) => lang[p('Fatima')] === l('TypeScript'),
  (city) => ![c('Kochi'), c('Pune'), c('Chennai')].includes(city[p('Aarav')]),
  (city, lang) => city[lang.indexOf(l('Go'))] === c('Chennai'),
  (city) => city[p('Eshan')] !== c('Pune'),
  (city, lang) => city[lang.indexOf(l('Rust'))] !== c('Hyderabad'),
  (city, lang) => city[lang.indexOf(l('Kotlin'))] === c('Jaipur'),
];
const cityOrders = [];
eachOrder(6, (o) => cityOrders.push(o.slice()));
let assignments = 0;
let fits = 0;
for (const city of cityOrders) {
  for (const lang of cityOrders) {
    assignments++;
    if (clues.every((ok) => ok(city, lang))) fits++;
  }
}
console.log(`   Checked against all ${assignments} assignments: ${fits} fits`);

// 2. Seven students on floors 1 (bottom) to 7.
const S = ['P', 'Q', 'R', 'S', 'T', 'U', 'V'];
const floorClues = [
  ['Exactly two floors lie between Q and T', (f) => Math.abs(f.Q - f.T) === 3],
  ['R lives immediately above T', (f) => f.R === f.T + 1],
  ['S lives above P but below U', (f) => f.P < f.S && f.S < f.U],
  ['P does not live on floor 1', (f) => f.P !== 1],
  ['Q lives immediately below U', (f) => f.Q === f.U - 1],
];
let floors = [];
eachOrder(7, (o) => floors.push(Object.fromEntries(S.map((x, i) => [x, o[i] + 1]))));
const start = floors.length;
for (const [, ok] of floorClues) floors = floors.filter(ok);
const upwards = (f) => S.slice().sort((a, b) => f[a] - f[b]).join(' ');
console.log(`2. The hostel: ${start} orders; ${floors.length} fits all five clues; floors 1 to 7: ${floors.map(upwards).join(' / ')}`);

// 3. Five boxes stacked from 1 (bottom) to 5.
const boxes = [];
eachOrder(5, (o) => {
  const b = Object.fromEntries(['P', 'Q', 'R', 'S', 'T'].map((x, i) => [x, o[i] + 1]));
  if (b.T === 1 && b.Q === b.P + 1 && Math.abs(b.Q - b.S) === 2 && b.R > b.S) boxes.push(b);
});
console.log(`3. The boxes: ${boxes.length} stack fits; bottom to top: ${boxes.map((b) => Object.keys(b).sort((x, y) => b[x] - b[y]).join(' ')).join(' / ')}`);

// 4. A team of three from five, with three rules.
const people = ['Aman', 'Bina', 'Chetan', 'Diya', 'Eshwar'];
const teams = [];
for (let mask = 0; mask < 32; mask++) {
  const team = people.filter((_, i) => (mask >> i) & 1);
  if (team.length !== 3) continue;
  const has = (x) => team.includes(x);
  if (has('Aman') && !has('Bina')) continue; // if Aman, then Bina
  if (has('Chetan') && has('Diya')) continue; // not both Chetan and Diya
  if (has('Eshwar') && !has('Chetan')) continue; // Eshwar only if Chetan
  teams.push(team.join(', '));
}
const inAll = people.filter((x) => teams.every((t) => t.includes(x)));
console.log(`4. The selection: 10 teams of three, ${teams.length} allowed: ${teams.join(' / ')}; in every one: ${inAll.join(', ')}`);

// 5. Five teams play each other once: 10 matches, 2 points a win, no draws. Try all 2^10 ways the matches can go.
const teamsAtoE = ['A', 'B', 'C', 'D', 'E'];
const matches = [];
for (let i = 0; i < 5; i++) for (let j = i + 1; j < 5; j++) matches.push([i, j]);
let tables = 0;
const fitting = [];
for (let mask = 0; mask < 1 << matches.length; mask++) {
  const points = [0, 0, 0, 0, 0];
  matches.forEach(([i, j], k) => { points[(mask >> k) & 1 ? i : j] += 2; });
  tables++;
  if (points[0] === 8 && points[4] === 0 && points[1] === 4 && points[2] === 4 && points[3] === 4) {
    // The three matches among B, C and D (A and E won and lost everything).
    const among = matches.map(([i, j], k) => [i, j, k]).filter(([i, j]) => i >= 1 && j <= 3);
    fitting.push(among.map(([i, j, k]) => ((mask >> k) & 1 ? `${teamsAtoE[i]} beat ${teamsAtoE[j]}` : `${teamsAtoE[j]} beat ${teamsAtoE[i]}`)).join(', '));
  }
}
console.log(`5. The league: ${matches.length} matches, ${tables} ways they can go; A 8, B 4, C 4, D 4, E 0 fits ${fitting.length}: ${fitting.join(' / ')}`);

1. The intern grid: solved by ticks and crosses alone, 4 passes, 108 marks, no guess
   The ticks, in the order they appear: clue 1: Kochi writes Java; clue 4: Pune writes Python; clue 5: Fatima writes TypeScript; clue 7: Chennai writes Go; clue 10: Jaipur writes Kotlin; only Chirag is left for Pune; only Rust is left for Dia; only Chirag is left for Python; only TypeScript is left for Hyderabad; only Bengaluru is left for Rust; Dia writes Rust, which goes with Bengaluru; Fatima writes TypeScript, which goes with Hyderabad; only Eshan is left for Kochi; only Eshan is left for Java; only Jaipur is left for Aarav; only Bhumi is left for Chennai; only Kotlin is left for Aarav; only Bhumi is left for Go
   Aarav: Jaipur, Kotlin
   Bhumi: Chennai, Go
   Chirag: Pune, Python
   Dia: Bengaluru, Rust
   Eshan: Kochi, Java
   Fatima: Hyderabad, TypeScript
   Checked against all 518400 assignments: 1 fits
2. The hostel: 5040 orders; 1 fits all five clues; floors 1 to 7: V P T R S Q U
3. The boxes: 1 stack fits; bottom to top: T S P Q R
4. The selection: 10 teams of three, 3 allowed: Aman, Bina, Chetan / Aman, Bina, Diya / Bina, Chetan, Eshwar; in every one: Bina
5. The league: 10 matches, 1024 ways they can go; A 8, B 4, C 4, D 4, E 0 fits 2: C beat B, B beat D, D beat C / B beat C, D beat B, C beat D