Last active
February 26, 2026 00:00
-
-
Save alexose/49955500d6ec33d36ea797df638e40f1 to your computer and use it in GitHub Desktop.
Dinner group rotation optimizer
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| <!DOCTYPE html> | |
| <html lang="en"> | |
| <head> | |
| <meta charset="UTF-8"> | |
| <meta name="viewport" content="width=device-width, initial-scale=1.0"> | |
| <title>Dinner Groups</title> | |
| <style> | |
| *, *::before, *::after { box-sizing: border-box; margin: 0; padding: 0; } | |
| body { | |
| font-family: system-ui, -apple-system, BlinkMacSystemFont, 'Segoe UI', sans-serif; | |
| background: #f8f5f1; color: #3d2c22; line-height: 1.5; | |
| } | |
| .container { max-width: 1200px; margin: 0 auto; padding: 1.5rem 1rem; } | |
| h1 { text-align: center; margin-bottom: 1.25rem; color: #5c3d2e; font-size: 1.75rem; } | |
| .panels { display: grid; grid-template-columns: 280px 1fr; gap: 1.5rem; align-items: start; } | |
| @media (max-width: 768px) { .panels { grid-template-columns: 1fr; } } | |
| /* Input panel */ | |
| .input-panel { | |
| background: white; border-radius: 12px; padding: 1.25rem; | |
| box-shadow: 0 2px 8px rgba(0,0,0,0.07); position: sticky; top: 1rem; | |
| } | |
| .input-panel label { display: block; font-weight: 600; margin-bottom: 0.25rem; color: #5c3d2e; font-size: 14px; } | |
| .input-panel textarea { | |
| width: 100%; min-height: 260px; border: 1px solid #ddd; border-radius: 8px; | |
| padding: 0.6rem; font-size: 13px; font-family: inherit; resize: vertical; line-height: 1.4; | |
| } | |
| .input-panel textarea:focus, .input-panel input:focus { | |
| outline: none; border-color: #c17f59; box-shadow: 0 0 0 2px rgba(193,127,89,0.15); | |
| } | |
| .input-panel input[type="number"] { | |
| width: 100%; border: 1px solid #ddd; border-radius: 8px; | |
| padding: 0.5rem 0.6rem; font-size: 14px; font-family: inherit; | |
| } | |
| .field { margin-bottom: 1rem; } | |
| .row { display: grid; grid-template-columns: 1fr 1fr; gap: 0.75rem; } | |
| .buttons { display: flex; gap: 0.5rem; margin-top: 0.25rem; } | |
| .btn { | |
| flex: 1; padding: 0.65rem; border: none; border-radius: 8px; | |
| font-size: 14px; font-weight: 600; cursor: pointer; transition: all 0.15s; | |
| } | |
| .btn-primary { background: #c17f59; color: white; } | |
| .btn-primary:hover { background: #a86c49; } | |
| .btn-secondary { background: #ece4dc; color: #5c3d2e; } | |
| .btn-secondary:hover { background: #ddd3c9; } | |
| .btn:disabled { opacity: 0.5; cursor: not-allowed; } | |
| /* Output */ | |
| .output-panel { min-height: 200px; } | |
| .placeholder { color: #aaa; text-align: center; padding: 3rem 1rem; font-size: 15px; } | |
| .error { | |
| background: #fef2f2; border: 1px solid #fecaca; border-radius: 10px; | |
| padding: 1rem 1.25rem; color: #b91c1c; font-size: 14px; | |
| } | |
| .timing { text-align: right; color: #b0a090; font-size: 12px; margin-bottom: 0.75rem; } | |
| /* Spinner */ | |
| .computing { | |
| display: flex; flex-direction: column; align-items: center; justify-content: center; | |
| padding: 3rem 1rem; gap: 1rem; color: #5c3d2e; | |
| } | |
| .spinner { | |
| width: 32px; height: 32px; | |
| border: 3px solid #e8ddd4; border-top-color: #c17f59; | |
| border-radius: 50%; animation: spin 0.7s linear infinite; | |
| } | |
| @keyframes spin { to { transform: rotate(360deg); } } | |
| .computing-text { font-size: 14px; color: #8b6b56; } | |
| .computing-detail { font-size: 12px; color: #b0a090; } | |
| /* Schedule grid */ | |
| .schedule-grid { | |
| display: grid; grid-template-columns: repeat(auto-fit, minmax(230px, 1fr)); | |
| gap: 1rem; margin-bottom: 1.25rem; | |
| } | |
| .night-card { | |
| background: white; border-radius: 12px; padding: 1.1rem 1.25rem; | |
| box-shadow: 0 2px 8px rgba(0,0,0,0.07); | |
| } | |
| .night-card h3 { | |
| color: #5c3d2e; margin-bottom: 0.7rem; font-size: 15px; | |
| border-bottom: 2px solid #f0ebe6; padding-bottom: 0.4rem; | |
| } | |
| .restaurant-group { margin-bottom: 0.6rem; } | |
| .restaurant-group:last-child { margin-bottom: 0; } | |
| .restaurant-group h4 { font-size: 12px; color: #8b6b56; margin-bottom: 0.15rem; display: flex; align-items: center; gap: 0.4rem; } | |
| .restaurant-group ul { list-style: none; padding-left: 0.25rem; } | |
| .restaurant-group li { font-size: 13px; padding: 1px 0; color: #555; } | |
| /* Per-person table */ | |
| .person-table-wrap { | |
| background: white; border-radius: 12px; padding: 1.1rem 1.25rem; | |
| box-shadow: 0 2px 8px rgba(0,0,0,0.07); margin-bottom: 1.25rem; overflow-x: auto; | |
| } | |
| .person-table-wrap h3 { color: #5c3d2e; margin-bottom: 0.6rem; font-size: 15px; } | |
| .person-table { width: 100%; border-collapse: collapse; font-size: 13px; } | |
| .person-table th { | |
| text-align: left; padding: 0.45rem 0.6rem; border-bottom: 2px solid #f0ebe6; | |
| color: #5c3d2e; font-size: 12px; font-weight: 600; white-space: nowrap; | |
| } | |
| .person-table td { padding: 0.35rem 0.6rem; border-bottom: 1px solid #f5f0eb; } | |
| .person-table tr:hover td { background: #fdfbf9; } | |
| .person-table .rc { text-align: center; } | |
| /* Badge */ | |
| .badge { | |
| display: inline-block; width: 24px; height: 24px; line-height: 24px; | |
| text-align: center; border-radius: 5px; color: white; | |
| font-weight: 700; font-size: 12px; vertical-align: middle; | |
| } | |
| .badge-sm { width: 20px; height: 20px; line-height: 20px; font-size: 11px; border-radius: 4px; } | |
| /* Stats bar */ | |
| .stats-bar { | |
| background: white; border-radius: 12px; padding: 1.1rem 1.25rem; | |
| box-shadow: 0 2px 8px rgba(0,0,0,0.07); | |
| display: grid; grid-template-columns: repeat(auto-fit, minmax(140px, 1fr)); gap: 0.75rem; | |
| } | |
| .stat { text-align: center; } | |
| .stat-value { font-size: 1.3rem; font-weight: 700; color: #c17f59; line-height: 1.2; } | |
| .stat-label { font-size: 11px; color: #999; margin-top: 2px; } | |
| </style> | |
| </head> | |
| <body> | |
| <div class="container"> | |
| <h1>Dinner Groups</h1> | |
| <div class="panels"> | |
| <div class="input-panel"> | |
| <div class="field"> | |
| <label for="names">Names (one per line)</label> | |
| <textarea id="names" placeholder="Alice Bob Charlie Diana ..."></textarea> | |
| </div> | |
| <div class="row"> | |
| <div class="field"> | |
| <label for="restaurants">Restaurants</label> | |
| <input type="number" id="restaurants" value="6" min="2" max="26"> | |
| </div> | |
| <div class="field"> | |
| <label for="nights">Nights</label> | |
| <input type="number" id="nights" value="4" min="2" max="8"> | |
| </div> | |
| </div> | |
| <div class="row"> | |
| <div class="field"> | |
| <label for="min-group">Min group</label> | |
| <input type="number" id="min-group" placeholder="auto" min="1"> | |
| </div> | |
| <div class="field"> | |
| <label for="max-group">Max group</label> | |
| <input type="number" id="max-group" placeholder="auto" min="1"> | |
| </div> | |
| </div> | |
| <div class="field" style="margin-bottom:0.75rem"> | |
| <label style="display:flex;align-items:center;gap:0.4rem;cursor:pointer;font-weight:400"> | |
| <input type="checkbox" id="no-repeats" checked> No repeat restaurants | |
| </label> | |
| </div> | |
| <div class="buttons"> | |
| <button class="btn btn-primary" id="btn-generate">Generate</button> | |
| <button class="btn btn-secondary" id="btn-shuffle">Shuffle</button> | |
| </div> | |
| </div> | |
| <div class="output-panel" id="output"> | |
| <p class="placeholder">Click "Generate" to create a dinner rotation schedule.</p> | |
| </div> | |
| </div> | |
| </div> | |
| <script> | |
| // ============================================================ | |
| // Utilities (main thread) | |
| // ============================================================ | |
| function combinations(arr, k) { | |
| if (k === 0) return [[]]; | |
| if (k > arr.length) return []; | |
| const res = []; | |
| for (let i = 0; i <= arr.length - k; i++) | |
| for (const rest of combinations(arr.slice(i + 1), k - 1)) | |
| res.push([arr[i], ...rest]); | |
| return res; | |
| } | |
| function shuffleArray(a) { | |
| a = [...a]; for (let i = a.length - 1; i > 0; i--) { | |
| const j = Math.floor(Math.random() * (i + 1)); [a[i], a[j]] = [a[j], a[i]]; | |
| } return a; | |
| } | |
| function esc(s) { return s.replace(/&/g,'&').replace(/</g,'<').replace(/>/g,'>'); } | |
| const PALETTE = [ | |
| '#e74c3c','#3498db','#27ae60','#e8960c','#8e44ad', | |
| '#16a085','#d35400','#2c3e50','#c0392b','#2980b9', | |
| '#1abc9c','#7d6608','#6c3483','#117a65','#ba4a00','#1c2833' | |
| ]; | |
| function rColor(letter) { | |
| const idx = letter.charCodeAt(0) - 65; | |
| return idx < PALETTE.length ? PALETTE[idx] : `hsl(${(idx*137.5)%360},60%,42%)`; | |
| } | |
| function badge(letter, sm) { | |
| return `<span class="badge${sm?' badge-sm':''}" style="background:${rColor(letter)}">${letter}</span>`; | |
| } | |
| // ============================================================ | |
| // Pattern search (main thread — fast) | |
| // ============================================================ | |
| function findValidSequences(nightSets, noRepeats) { | |
| const N = nightSets.length, results = []; | |
| if (noRepeats) { | |
| function bt(n, ch, u) { | |
| if (n === N) { results.push([...ch]); return; } | |
| for (const r of nightSets[n]) if (!u.has(r)) { | |
| ch.push(r); u.add(r); bt(n+1, ch, u); ch.pop(); u.delete(r); | |
| } | |
| } | |
| bt(0, [], new Set()); | |
| } else { | |
| function bt2(n, ch) { | |
| if (n === N) { results.push([...ch]); return; } | |
| for (const r of nightSets[n]) { ch.push(r); bt2(n+1, ch); ch.pop(); } | |
| } | |
| bt2(0, []); | |
| } | |
| return results; | |
| } | |
| function generateCoveringNightSets(restaurants, G, N) { | |
| const R = restaurants.length, ts = N * G; | |
| if (ts < R) return null; | |
| const base = Math.floor(ts / R), extra = ts - base * R; | |
| const sr = shuffleArray(restaurants), pool = []; | |
| for (let i = 0; i < R; i++) { const c = base + (i < extra ? 1 : 0); for (let j = 0; j < c; j++) pool.push(sr[i]); } | |
| const sp = shuffleArray(pool), ns = []; | |
| for (let n = 0; n < N; n++) { const s = sp.slice(n*G, (n+1)*G); if (new Set(s).size !== G) return null; ns.push(s.sort()); } | |
| const u = new Set(); for (const s of ns) for (const r of s) u.add(r); | |
| return u.size >= R ? ns : null; | |
| } | |
| function findBestPattern(restaurants, G, N, minSeqs, noRepeats) { | |
| const choices = combinations(restaurants, G), nc = choices.length; | |
| const total = Math.pow(nc, N), R = restaurants.length; | |
| let best = null, bestCount = 0; | |
| if (total <= 500000) { | |
| for (let iter = 0; iter < total; iter++) { | |
| const indices = new Array(N); let v = iter; | |
| for (let n = N-1; n >= 0; n--) { indices[n] = v % nc; v = Math.floor(v / nc); } | |
| const ns = indices.map(i => choices[i]); | |
| const used = new Set(); for (const s of ns) for (const r of s) used.add(r); | |
| if (used.size < R) continue; | |
| const seqs = findValidSequences(ns, noRepeats); | |
| if (seqs.length >= minSeqs && seqs.length > bestCount) { | |
| bestCount = seqs.length; | |
| best = { nightSets: ns.map(s => [...s]), sequences: seqs }; | |
| if (bestCount >= minSeqs * 4) break; | |
| } | |
| } | |
| } else { | |
| for (let iter = 0; iter < 10000; iter++) { | |
| const ns = generateCoveringNightSets(restaurants, G, N); | |
| if (!ns) continue; | |
| const seqs = findValidSequences(ns, noRepeats); | |
| if (seqs.length >= minSeqs && seqs.length > bestCount) { | |
| bestCount = seqs.length; | |
| best = { nightSets: ns, sequences: seqs }; | |
| if (bestCount >= minSeqs * 4) break; | |
| } | |
| } | |
| } | |
| return best; | |
| } | |
| function nightGroupSizes(seqs, N) { | |
| const res = []; | |
| for (let n = 0; n < N; n++) { | |
| const c = {}; for (const s of seqs) c[s[n]] = (c[s[n]]||0)+1; | |
| res.push(Object.values(c).sort((a,b) => a-b)); | |
| } | |
| return res; | |
| } | |
| function findSequences(nameList, R, N, minGroup, maxGroup, noRepeats) { | |
| if (nameList.length < 2) return { error: 'Need at least 2 people.' }; | |
| if (R > 26) return { error: 'Maximum 26 restaurants (A\u2013Z).' }; | |
| if (minGroup && maxGroup && minGroup > maxGroup) return { error: 'Min group cannot exceed max group.' }; | |
| const numPeople = nameList.length; | |
| const restaurants = Array.from({length: R}, (_, i) => String.fromCharCode(65 + i)); | |
| if (noRepeats) { | |
| if (R < N) return { error: `Need at least ${N} restaurants for ${N} nights with no repeats (got ${R}). Uncheck "No repeat restaurants" or add more.` }; | |
| let maxSeqs = 1; for (let i = 0; i < N; i++) maxSeqs *= (R - i); | |
| } else { | |
| if (R < 2) return { error: 'Need at least 2 restaurants.' }; | |
| } | |
| // G = restaurants per night. Compute valid range. | |
| // loG: must cover all R restaurants across N nights, and groups can't exceed maxGroup | |
| // hiG: groups can't be smaller than minGroup, and G can't exceed R | |
| let loG = Math.max(2, Math.ceil(R / N)); | |
| let hiG = R; | |
| if (maxGroup) loG = Math.max(loG, Math.ceil(numPeople / maxGroup)); | |
| if (minGroup) hiG = Math.min(hiG, Math.floor(numPeople / minGroup)); | |
| if (loG > hiG) { | |
| const details = []; | |
| if (maxGroup) details.push(`max group ${maxGroup} requires ≥${Math.ceil(numPeople/maxGroup)} restaurants/night`); | |
| if (minGroup) details.push(`min group ${minGroup} requires ≤${Math.floor(numPeople/minGroup)} restaurants/night`); | |
| details.push(`${R} restaurants over ${N} nights needs ≥${Math.ceil(R/N)} restaurants/night`); | |
| return { error: `Constraints conflict for ${numPeople} people: ${details.join('; ')}. Clear the min/max group fields or adjust restaurants.` }; | |
| } | |
| for (let G = loG; G <= hiG; G++) { | |
| let result; | |
| if (G === R) { | |
| const ns = Array.from({length: N}, () => [...restaurants]); | |
| result = { nightSets: ns, sequences: findValidSequences(ns, noRepeats) }; | |
| } else { | |
| result = findBestPattern(restaurants, G, N, 2, noRepeats); | |
| } | |
| if (result && result.sequences.length >= 2) | |
| return { nightSets: result.nightSets, sequences: result.sequences, G, R, N }; | |
| } | |
| const paramDesc = `${numPeople} people, ${R} restaurants, ${N} nights` + | |
| (minGroup ? `, min group ${minGroup}` : '') + (maxGroup ? `, max group ${maxGroup}` : ''); | |
| return { error: `No valid configuration found for ${paramDesc}. Try adding more restaurants or clearing min/max group constraints.` }; | |
| } | |
| // ============================================================ | |
| // Stats (main thread) | |
| // ============================================================ | |
| function computeStats(assignment, N) { | |
| const np = assignment.length; | |
| const schedule = []; | |
| for (let n = 0; n < N; n++) { | |
| const groups = {}; | |
| for (let p = 0; p < np; p++) { | |
| const r = assignment[p].sequence[n]; | |
| (groups[r] || (groups[r] = [])).push(p); | |
| } | |
| schedule.push(groups); | |
| } | |
| const pairCount = new Map(); | |
| for (const ng of schedule) | |
| for (const members of Object.values(ng)) | |
| for (let i = 0; i < members.length; i++) | |
| for (let j = i + 1; j < members.length; j++) { | |
| const key = members[i] * np + members[j]; | |
| pairCount.set(key, (pairCount.get(key)||0) + 1); | |
| } | |
| const companions = []; | |
| for (let p = 0; p < np; p++) { | |
| const c = new Set(); | |
| for (const ng of schedule) | |
| for (const members of Object.values(ng)) | |
| if (members.includes(p)) for (const m of members) if (m !== p) c.add(m); | |
| companions.push(c.size); | |
| } | |
| const vals = [...pairCount.values()]; | |
| const maxTogether = vals.length ? Math.max(...vals) : 0; | |
| const pairsAtMax = vals.filter(v => v === maxTogether).length; | |
| const totalPairs = np * (np - 1) / 2; | |
| const pairsWhoMeet = pairCount.size; | |
| return { | |
| schedule, pairCount, maxTogether, pairsAtMax, | |
| neverMet: totalPairs - pairsWhoMeet, totalPairs, | |
| minCompanions: Math.min(...companions), maxCompanions: Math.max(...companions), | |
| mixing: totalPairs > 0 ? pairsWhoMeet / totalPairs * 100 : 100 | |
| }; | |
| } | |
| // ============================================================ | |
| // Web Worker — Simulated Annealing solver | |
| // ============================================================ | |
| const WORKER_CODE = ` | |
| 'use strict'; | |
| function buildState(seqs, assignment, N, numPeople, minG, maxG) { | |
| // Night groups: nightGroups[n] = Map<restaurant, Set<person>> | |
| const nightGroups = []; | |
| for (let n = 0; n < N; n++) { | |
| const g = new Map(); | |
| for (let p = 0; p < numPeople; p++) { | |
| const r = seqs[assignment[p]][n]; | |
| if (!g.has(r)) g.set(r, new Set()); | |
| g.get(r).add(p); | |
| } | |
| nightGroups.push(g); | |
| } | |
| // Pair counts + histogram of pair counts | |
| const pairCount = new Map(); | |
| let uniquePairs = 0; | |
| const hist = new Int32Array(N + 1); // hist[c] = number of pairs with count c | |
| for (let n = 0; n < N; n++) { | |
| for (const members of nightGroups[n].values()) { | |
| const arr = [...members]; | |
| for (let i = 0; i < arr.length; i++) | |
| for (let j = i + 1; j < arr.length; j++) { | |
| const key = arr[i] * numPeople + arr[j]; | |
| const old = pairCount.get(key) || 0; | |
| const nw = old + 1; | |
| pairCount.set(key, nw); | |
| if (old > 0) hist[old]--; | |
| hist[nw]++; | |
| if (nw === 1) uniquePairs++; | |
| } | |
| } | |
| } | |
| let maxPair = N; | |
| while (maxPair > 0 && hist[maxPair] === 0) maxPair--; | |
| // Count violations | |
| let violations = 0; | |
| if (minG || maxG) { | |
| for (let n = 0; n < N; n++) { | |
| for (const members of nightGroups[n].values()) { | |
| const sz = members.size; | |
| if (minG && sz < minG) violations += (minG - sz); | |
| if (maxG && sz > maxG) violations += (sz - maxG); | |
| } | |
| } | |
| } | |
| return { assignment: assignment.slice(), nightGroups, pairCount, uniquePairs, hist, maxPair, seqs, N, numPeople, violations }; | |
| } | |
| function initState(seqs, numPeople, N, minG, maxG) { | |
| // Randomly assign each person a sequence (sequences can be shared) | |
| const nSeqs = seqs.length; | |
| const assignment = new Array(numPeople); | |
| for (let p = 0; p < numPeople; p++) { | |
| assignment[p] = Math.floor(Math.random() * nSeqs); | |
| } | |
| return buildState(seqs, assignment, N, numPeople, minG, maxG); | |
| } | |
| function trySwap(st, p, newSeqIdx, minG, maxG) { | |
| if (newSeqIdx === st.assignment[p]) return null; | |
| const oldSeq = st.seqs[st.assignment[p]]; | |
| const newSeq = st.seqs[newSeqIdx]; | |
| // Compute violation delta | |
| let deltaViolation = 0; | |
| if (minG || maxG) { | |
| for (let n = 0; n < st.N; n++) { | |
| const oR = oldSeq[n], nR = newSeq[n]; | |
| if (oR === nR) continue; | |
| const oSz = st.nightGroups[n].get(oR).size; | |
| const nGrp = st.nightGroups[n].get(nR); | |
| const nSz = nGrp ? nGrp.size : 0; | |
| if (minG) { | |
| deltaViolation += Math.max(0, minG - (oSz - 1)) - Math.max(0, minG - oSz); | |
| deltaViolation += Math.max(0, minG - (nSz + 1)) - Math.max(0, minG - nSz); | |
| } | |
| if (maxG) { | |
| deltaViolation += Math.max(0, (oSz - 1) - maxG) - Math.max(0, oSz - maxG); | |
| deltaViolation += Math.max(0, (nSz + 1) - maxG) - Math.max(0, nSz - maxG); | |
| } | |
| } | |
| } | |
| // Compute delta in unique pairs | |
| const deltaMap = new Map(); | |
| for (let n = 0; n < st.N; n++) { | |
| const oR = oldSeq[n], nR = newSeq[n]; | |
| if (oR === nR) continue; | |
| for (const m of st.nightGroups[n].get(oR)) { | |
| if (m === p) continue; | |
| deltaMap.set(m, (deltaMap.get(m)||0) - 1); | |
| } | |
| const nGrp = st.nightGroups[n].get(nR); | |
| if (nGrp) for (const m of nGrp) { | |
| if (m === p) continue; | |
| deltaMap.set(m, (deltaMap.get(m)||0) + 1); | |
| } | |
| } | |
| let deltaPairs = 0; | |
| // Simulate histogram changes to find new maxPair | |
| const histDelta = new Map(); // count -> change in hist[count] | |
| for (const [m, d] of deltaMap) { | |
| const key = Math.min(p,m) * st.numPeople + Math.max(p,m); | |
| const old = st.pairCount.get(key) || 0; | |
| const nw = old + d; | |
| if (old > 0) histDelta.set(old, (histDelta.get(old)||0) - 1); | |
| if (nw > 0) histDelta.set(nw, (histDelta.get(nw)||0) + 1); | |
| if (old > 0 && nw <= 0) deltaPairs--; | |
| if (old <= 0 && nw > 0) deltaPairs++; | |
| } | |
| // Compute new maxPair | |
| let newMaxPair = st.maxPair; | |
| for (const [c, d] of histDelta) { | |
| if (c > newMaxPair && d > 0) newMaxPair = c; | |
| } | |
| // Check if maxPair decreased | |
| if (newMaxPair === st.maxPair) { | |
| const topChange = histDelta.get(st.maxPair) || 0; | |
| if (st.hist[st.maxPair] + topChange <= 0) { | |
| newMaxPair = st.maxPair - 1; | |
| while (newMaxPair > 0) { | |
| const c = st.hist[newMaxPair] + (histDelta.get(newMaxPair) || 0); | |
| if (c > 0) break; | |
| newMaxPair--; | |
| } | |
| } | |
| } | |
| const newPairsAtMax = newMaxPair > 0 ? st.hist[newMaxPair] + (histDelta.get(newMaxPair) || 0) : 0; | |
| return { deltaPairs, deltaViolation, deltaMap, histDelta, newMaxPair, newPairsAtMax, newSeqIdx }; | |
| } | |
| function applySwap(st, p, deltaMap, newSeqIdx, deltaViolation, histDelta, newMaxPair) { | |
| const oldSeq = st.seqs[st.assignment[p]]; | |
| const newSeq = st.seqs[newSeqIdx]; | |
| // Update pair counts and histogram | |
| for (const [m, d] of deltaMap) { | |
| const key = Math.min(p,m) * st.numPeople + Math.max(p,m); | |
| const old = st.pairCount.get(key) || 0; | |
| const nw = old + d; | |
| if (old > 0 && nw <= 0) { st.pairCount.delete(key); st.uniquePairs--; } | |
| else if (old <= 0 && nw > 0) { st.pairCount.set(key, nw); st.uniquePairs++; } | |
| else if (nw > 0) st.pairCount.set(key, nw); | |
| else st.pairCount.delete(key); | |
| } | |
| for (const [c, d] of histDelta) st.hist[c] += d; | |
| st.maxPair = newMaxPair; | |
| // Update night groups | |
| for (let n = 0; n < st.N; n++) { | |
| const oR = oldSeq[n], nR = newSeq[n]; | |
| if (oR === nR) continue; | |
| st.nightGroups[n].get(oR).delete(p); | |
| if (st.nightGroups[n].get(oR).size === 0) st.nightGroups[n].delete(oR); | |
| if (!st.nightGroups[n].has(nR)) st.nightGroups[n].set(nR, new Set()); | |
| st.nightGroups[n].get(nR).add(p); | |
| } | |
| st.assignment[p] = newSeqIdx; | |
| st.violations += deltaViolation; | |
| } | |
| // Primary: eliminate violations, then minimize max pair count, then maximize mixing | |
| function score(st) { | |
| const pairsAtMax = st.maxPair > 0 ? st.hist[st.maxPair] : 0; | |
| return -st.violations * 100 - st.maxPair * 5 + st.uniquePairs * 0.1 - pairsAtMax * 0.001; | |
| } | |
| function solve(seqs, numPeople, N, minG, maxG, maxTime) { | |
| const totalPairs = numPeople * (numPeople - 1) / 2; | |
| const nSeqs = seqs.length; | |
| let st = initState(seqs, numPeople, N, minG, maxG); | |
| let bestScore = score(st); | |
| let bestAssignment = st.assignment.slice(); | |
| let bestPairs = st.uniquePairs; | |
| let bestViolations = st.violations; | |
| // Track best valid (0 violations) solution by score | |
| let bestValidScore = st.violations === 0 ? score(st) : -Infinity; | |
| let bestValidAssignment = st.violations === 0 ? st.assignment.slice() : null; | |
| let bestValidPairs = st.violations === 0 ? st.uniquePairs : 0; | |
| let lastImprove = Date.now(); | |
| const t0 = Date.now(); | |
| let iter = 0; | |
| const T0 = 5.0; | |
| while (Date.now() - t0 < maxTime) { | |
| const elapsed = Date.now() - t0; | |
| const T = Math.max(0.01, T0 * (1 - elapsed / maxTime)); | |
| const p = Math.floor(Math.random() * numPeople); | |
| const newSeqIdx = Math.floor(Math.random() * nSeqs); | |
| const result = trySwap(st, p, newSeqIdx, minG, maxG); | |
| if (result) { | |
| const { deltaPairs, deltaViolation, deltaMap, histDelta, newMaxPair, newPairsAtMax } = result; | |
| const oldPairsAtMax = st.maxPair > 0 ? st.hist[st.maxPair] : 0; | |
| const deltaScore = -deltaViolation * 100 | |
| - (newMaxPair - st.maxPair) * 5 | |
| + deltaPairs * 0.1 | |
| - (newPairsAtMax - oldPairsAtMax) * 0.001; | |
| if (deltaScore > 0 || Math.random() < Math.exp(deltaScore / T)) { | |
| applySwap(st, p, deltaMap, newSeqIdx, deltaViolation, histDelta, newMaxPair); | |
| const sc = score(st); | |
| if (sc > bestScore) { | |
| bestScore = sc; | |
| bestAssignment = st.assignment.slice(); | |
| bestPairs = st.uniquePairs; | |
| bestViolations = st.violations; | |
| lastImprove = Date.now(); | |
| } | |
| if (st.violations === 0 && sc > bestValidScore) { | |
| bestValidScore = sc; | |
| bestValidPairs = st.uniquePairs; | |
| bestValidAssignment = st.assignment.slice(); | |
| } | |
| } | |
| } | |
| iter++; | |
| // Restart if stuck | |
| if (Date.now() - lastImprove > 800 && Date.now() - t0 < maxTime - 500) { | |
| st = initState(seqs, numPeople, N, minG, maxG); | |
| const sc = score(st); | |
| if (sc > bestScore) { | |
| bestScore = sc; | |
| bestAssignment = st.assignment.slice(); | |
| bestPairs = st.uniquePairs; | |
| bestViolations = st.violations; | |
| } | |
| if (st.violations === 0 && sc > bestValidScore) { | |
| bestValidScore = sc; | |
| bestValidPairs = st.uniquePairs; | |
| bestValidAssignment = st.assignment.slice(); | |
| } | |
| lastImprove = Date.now(); | |
| } | |
| // Progress | |
| if (iter % 20000 === 0) { | |
| const currentMixing = (st.uniquePairs / totalPairs * 100).toFixed(1); | |
| const bestMix = bestValidAssignment ? bestValidPairs : bestPairs; | |
| self.postMessage({ | |
| type: 'progress', | |
| mixing: currentMixing, | |
| bestMixing: (bestMix / totalPairs * 100).toFixed(1), | |
| maxPair: st.maxPair, | |
| uniquePairs: st.uniquePairs, totalPairs, iter, | |
| violations: st.violations, | |
| elapsed: Date.now() - t0 | |
| }); | |
| } | |
| } | |
| const finalAssignment = bestValidAssignment || bestAssignment; | |
| const finalPairs = bestValidAssignment ? bestValidPairs : bestPairs; | |
| const finalViolations = bestValidAssignment ? 0 : bestViolations; | |
| self.postMessage({ | |
| type: 'done', assignment: finalAssignment, | |
| uniquePairs: finalPairs, totalPairs, iter, | |
| violations: finalViolations | |
| }); | |
| } | |
| self.onmessage = function(e) { | |
| if (e.data.type === 'solve') { | |
| solve(e.data.sequences, e.data.numPeople, e.data.N, | |
| e.data.minGroup, e.data.maxGroup, e.data.maxTime || 3000); | |
| } | |
| }; | |
| `; | |
| let worker = null; | |
| const workerBlob = new Blob([WORKER_CODE], { type: 'application/javascript' }); | |
| const workerUrl = URL.createObjectURL(workerBlob); | |
| function killWorker() { | |
| if (worker) { worker.terminate(); worker = null; } | |
| } | |
| // ============================================================ | |
| // UI | |
| // ============================================================ | |
| let cache = {}; | |
| function getNames() { return document.getElementById('names').value.split('\n').map(s=>s.trim()).filter(Boolean); } | |
| function getR() { return Math.max(2, Math.min(26, parseInt(document.getElementById('restaurants').value)||6)); } | |
| function getN() { return Math.max(2, Math.min(8, parseInt(document.getElementById('nights').value)||4)); } | |
| function getMinGroup() { const v = parseInt(document.getElementById('min-group').value); return v > 0 ? v : null; } | |
| function getMaxGroup() { const v = parseInt(document.getElementById('max-group').value); return v > 0 ? v : null; } | |
| function getNoRepeats() { return document.getElementById('no-repeats').checked; } | |
| function setButtons(disabled) { | |
| document.getElementById('btn-generate').disabled = disabled; | |
| document.getElementById('btn-shuffle').disabled = disabled; | |
| } | |
| function showSpinner(detail) { | |
| document.getElementById('output').innerHTML = | |
| `<div class="computing"><div class="spinner"></div><div class="computing-text">Optimizing schedule...</div><div class="computing-detail" id="progress">${detail||''}</div></div>`; | |
| } | |
| function launchSolver(names, seqResult, minGroup, maxGroup) { | |
| const { sequences, nightSets, G, R, N } = seqResult; | |
| showSpinner('Starting...'); | |
| setButtons(true); | |
| killWorker(); | |
| worker = new Worker(workerUrl); | |
| worker.onerror = function(err) { | |
| setButtons(false); | |
| document.getElementById('output').innerHTML = `<div class="error">Worker error: ${esc(err.message || 'Unknown error')}</div>`; | |
| worker = null; | |
| }; | |
| worker.onmessage = function(e) { | |
| if (e.data.type === 'progress') { | |
| const el = document.getElementById('progress'); | |
| if (el) { | |
| let txt = `Max pair: ${e.data.maxPair} | Mixing: ${e.data.mixing}% | ${(e.data.elapsed/1000).toFixed(1)}s`; | |
| if (e.data.violations > 0) txt += ` | ${e.data.violations} group violations`; | |
| el.textContent = txt; | |
| } | |
| } | |
| if (e.data.type === 'done') { | |
| setButtons(false); | |
| const assignmentIndices = e.data.assignment; | |
| const shuffled = assignmentIndices.map(i => sequences[i]); | |
| const assignment = names.map((name, i) => ({ name, sequence: shuffled[i] })); | |
| const stats = computeStats(assignment, N); | |
| const gs = nightGroupSizes(shuffled, N)[0]; | |
| let timingNote = (e.data.iter / 1000).toFixed(0) + 'K iterations'; | |
| if (e.data.violations > 0) timingNote += ` (${e.data.violations} group constraint violations remain)`; | |
| renderOutput({ nightSets, sequences, assignment, stats, groupSizes: gs, G, R, N }, timingNote); | |
| worker = null; | |
| } | |
| }; | |
| worker.postMessage({ | |
| type: 'solve', sequences, numPeople: names.length, N, | |
| minGroup, maxGroup, | |
| maxTime: sequences.length > 200 ? 4000 : 3000 | |
| }); | |
| } | |
| function onGenerate() { | |
| killWorker(); | |
| const names = getNames(); | |
| const R = getR(), N = getN(); | |
| const minGroup = getMinGroup(), maxGroup = getMaxGroup(); | |
| const noRepeats = getNoRepeats(); | |
| const result = findSequences(names, R, N, minGroup, maxGroup, noRepeats); | |
| if (result.error) { | |
| document.getElementById('output').innerHTML = `<div class="error">${esc(result.error)}</div>`; | |
| return; | |
| } | |
| cache = { sequences: result.sequences, nightSets: result.nightSets, names, R, N, minGroup, maxGroup, noRepeats }; | |
| launchSolver(names, result, minGroup, maxGroup); | |
| } | |
| function onShuffle() { | |
| killWorker(); | |
| const names = getNames(); | |
| const R = getR(), N = getN(); | |
| const minGroup = getMinGroup(), maxGroup = getMaxGroup(); | |
| const noRepeats = getNoRepeats(); | |
| if (!cache.sequences || cache.R !== R || cache.N !== N || | |
| cache.minGroup !== minGroup || cache.maxGroup !== maxGroup || | |
| cache.noRepeats !== noRepeats || | |
| names.length !== (cache.names && cache.names.length)) { | |
| onGenerate(); return; | |
| } | |
| launchSolver(names, { sequences: cache.sequences, nightSets: cache.nightSets, G: null, R, N }, minGroup, maxGroup); | |
| } | |
| function renderOutput(result, timingLabel) { | |
| const el = document.getElementById('output'); | |
| if (result.error) { el.innerHTML = `<div class="error">${esc(result.error)}</div>`; return; } | |
| const { assignment, stats, N } = result; | |
| let h = ''; | |
| h += `<div class="timing">${esc(timingLabel)}</div>`; | |
| h += '<div class="schedule-grid">'; | |
| for (let n = 0; n < N; n++) { | |
| h += '<div class="night-card">'; | |
| h += `<h3>Night ${n+1}</h3>`; | |
| const groups = stats.schedule[n]; | |
| for (const r of Object.keys(groups).sort()) { | |
| const members = groups[r].map(i => esc(assignment[i].name)); | |
| h += `<div class="restaurant-group"><h4>${badge(r,true)} Restaurant ${r} <span style="font-weight:400">(${members.length})</span></h4>`; | |
| h += `<ul>${members.map(m=>`<li>${m}</li>`).join('')}</ul></div>`; | |
| } | |
| h += '</div>'; | |
| } | |
| h += '</div>'; | |
| h += '<div class="person-table-wrap"><h3>Per-Person Schedule</h3>'; | |
| h += '<table class="person-table"><thead><tr><th>Name</th>'; | |
| for (let n = 0; n < N; n++) h += `<th style="text-align:center">Night ${n+1}</th>`; | |
| h += '</tr></thead><tbody>'; | |
| for (const a of assignment) { | |
| h += `<tr><td>${esc(a.name)}</td>`; | |
| for (const r of a.sequence) h += `<td class="rc">${badge(r,true)}</td>`; | |
| h += '</tr>'; | |
| } | |
| h += '</tbody></table></div>'; | |
| h += '<div class="stats-bar">'; | |
| h += stat(result.R, 'Restaurants'); | |
| h += stat(result.groupSizes.join(', '), 'Group sizes'); | |
| h += stat(stats.maxTogether + ` <span style="font-size:11px;color:#999">(${stats.pairsAtMax} pairs)</span>`, 'Max pair together'); | |
| h += stat(stats.mixing.toFixed(1) + '%', 'Mixing'); | |
| h += stat(stats.neverMet + ' / ' + stats.totalPairs, 'Pairs never meet'); | |
| h += stat(stats.minCompanions + '–' + stats.maxCompanions + ` / ${assignment.length-1}`, 'Unique companions'); | |
| h += '</div>'; | |
| // Most common pairings | |
| const np = assignment.length; | |
| const pairList = []; | |
| for (const [key, count] of stats.pairCount) { | |
| const i = Math.floor(key / np), j = key % np; | |
| pairList.push({ a: assignment[i].name, b: assignment[j].name, count }); | |
| } | |
| pairList.sort((a, b) => b.count - a.count || a.a.localeCompare(b.a)); | |
| if (pairList.length > 0) { | |
| h += '<div class="person-table-wrap" style="margin-top:1.25rem"><h3>Most Common Pairings</h3>'; | |
| h += '<table class="person-table"><thead><tr><th>Person A</th><th>Person B</th><th style="text-align:center">Nights Together</th></tr></thead><tbody>'; | |
| const maxShow = Math.min(pairList.length, 20); | |
| for (let i = 0; i < maxShow; i++) { | |
| const p = pairList[i]; | |
| h += `<tr><td>${esc(p.a)}</td><td>${esc(p.b)}</td><td class="rc">${p.count}</td></tr>`; | |
| } | |
| if (pairList.length > 20) { | |
| h += `<tr><td colspan="3" style="text-align:center;color:#999;font-size:12px">${pairList.length - 20} more pairs not shown</td></tr>`; | |
| } | |
| h += '</tbody></table></div>'; | |
| } | |
| el.innerHTML = h; | |
| } | |
| function stat(value, label) { | |
| return `<div class="stat"><div class="stat-value">${value}</div><div class="stat-label">${label}</div></div>`; | |
| } | |
| document.getElementById('btn-generate').addEventListener('click', onGenerate); | |
| document.getElementById('btn-shuffle').addEventListener('click', onShuffle); | |
| // Clear min/max group when restaurant or night count changes, since old values likely don't apply | |
| document.getElementById('restaurants').addEventListener('change', function() { | |
| document.getElementById('min-group').value = ''; | |
| document.getElementById('max-group').value = ''; | |
| }); | |
| document.getElementById('nights').addEventListener('change', function() { | |
| document.getElementById('min-group').value = ''; | |
| document.getElementById('max-group').value = ''; | |
| }); | |
| </script> | |
| </body> | |
| </html> |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment