I am doing this project on Oracles, here are the specifications of the project:
Objective: developing an oracle to test (possibly broken) solutions to the Stable Matching Problem.
Specifications: Only working on Part B for now:
An oracle is a function that answers a yes or no question. In this case, we are writing an oracle to decide if the supplied function correctly solves the Stable Matching Problem.
Our oracle’s job is to generate and feed test inputs to a given “solution” (possibly incorrect) then test the correctness of the output.
(Anyone who doesn’t know can read over the Stable Matching Problem on wikipedia)
Companies and Candidates
For this assignment, our groups will consist of companies and candidates. Each company has a ranking of all candidates, in order of preference. And each candidate has a ranking of all companies. Preference lists will be represented as arrays, with the first preference at index 0 and the last preference at index n-1
Companies and candidates are each assigned a number between 0 and n−1. Thus, a two-dimensional array can represent the preferences of a single group:
// n = 3 = There are three companies. = There are three candidates.
[
[0, 1, 2], // Index 0: Company 0's preference list
[1, 2, 0], // Index 1: Company 1's preference list
[0, 2, 1], // Index 2: Company 2's preference list
];
Each element of this 2D array is a preference list. Each element of a preference list is a candidate’s number. Company 0’s first preference is Candidate 0, then Candidate 1, then lastly Candidate 2. Candidate preference lists are structured the same way. However, each number corresponds to a company rather than a candidate.
Inside of stableMatching.d.ts, we can find the following type definitions:
interface Hire {
company: number;
candidate: number;
}
type StableMatcher = (companies: number[][], candidates: number[][]) => Hire[];
A Hire is an object with two fields that represents a matching between a company and candidate. A StableMatcher is a function that takes in two 2D arrays of numbers, specifically the preferences of the companies and candidates, and returns an array of Hire objects (Hire[]).
Along with these type definitions, there are two relevant exported members (functions), both of type StableMatcher. They are: STABLE_MATCHING_SOLUTION_1 and FLAWED_STABLE_MATCHING_SOLUTION_1. They are used inside the provided tests (oracle.test.ts) to check against our solution. Their implementations are obfuscated inside of stableMatching.js.
ACTUAL PROGRAMMING TASK:
write an oracle that determines if a function follows the specified algorithm:
Algorithm: We assume the following non-standard variant: At any step, any unmatched company or candidate may propose. Every party always proposes to the next potential partner on their preference list, starting with the top choice. Proposals are not repeated. Any unmatched party that receives a proposal accepts unconditionally. If the receiving party is already matched, but they receive a better offer (higher in their preference list), they accept, and their current partner becomes unmatched; otherwise, the offer is rejected. The algorithm ends when all parties are either matched or have made offers to the entire preference list. The algorithm is under-specified/nondeterministic: it doesn’t state whether a company or a candidate proposes at a given step, nor which one does, as long as the given rules are observed.
the other members inside stableMatching.d.ts are:
interface Offer {
from: number;
to: number;
fromCo: boolean; // If the offer is from a company
}
interface Run {
trace: Offer[];
out: Hire[];
}
type StableMatcherWithTrace = (companies: number[][], candidates: number[][]) => Run;
An Offer is an object with three fields that represents a proposal from one party member to a member of another party (company -> candidate or candidate -> company). A Run is an object that represents the series of steps an algorithm took (trace) to produce a solution (out). A StableMatcherWithTrace is just like a StableMatcher, but it returns a Run.
Implement stableMatchingRunOracle inside of oracles.ts.
export function stableMatchingRunOracle(f: (companies: number[][], candidates: number[][]) => Run): void {
// TODO
}
This function should test the provided implementation of stable matching. It should check that:
The offer sequence in the trace is valid, made according to the given algorithm, starting with all parties unmatched
The trace need not be a complete algorithm run, it may stop at any point
The produced matching (out) is indeed the result of the offers in the trace
EXAMPLES:
Assume that we have candidates Alice, Bob, and Charles, and companies Amazon, Boeing, and Cisco. The candidate preference matrix could look like this:
First Preference Second Preference Third Preference
Alice (0) 0 (Amazon) 1 (Boeing) 2 (Cisco)
Bob (1) 0 (Amazon) 2 (Cisco) 1 (Boeing)
Charles (2) 2 (Cisco) 1 (Boeing) 0 (Amazon)
This means that Alice’s preferences are Amazon, Boeing, and Cisco, in that order. Bob’s preferences are Amazon, Cisco, and Boeing, in that order. Charles’ preferences are Cisco, Boeing, and Amazon, in that order. The corresponding number[][] would look like this:
[
[0, 1, 2],
[0, 2, 1],
[2, 1, 0],
];
The company preference matrix could look like this:
First Preference Second Preference Third Preference
Amazon (0) 0 (Alice) 2 (Charles) 1 (Bob)
Boeing (1) 0 (Alice) 1 (Bob) 2 (Charles)
Cisco (2) 0 (Alice) 2 (Charles) 1 (Bob)
This means that Amazon’s preferences are Alice, Charles, and Bob, in that order. Boeing’s preferences are Alice Bob, and Charles, in that order. Cisco preferences are Alice, Charles, and Bob, in that order. The corresponding number[][] would look like this:
[
[0, 2, 1],
[0, 1, 2],
[0, 2, 1],
];
A possible trace could look like this: [{from:1, to:1, fromCo:false}]. This means that Bob makes an offer to Boeing. This offer is invalid, since Bob’s top choice is Amazon, and Bob did not previously offer to Amazon in this run.
Another possible trace could be [{from:2, to:0, fromCo:true}]. This means that Cisco makes an offer to Alice. This is a valid offer, since Cisco’s top choice is Alice, and Cisco is unmatched. Alice’s top choice is Amazon, but being unmatched, they has to accept the offer. The result is that Alice and Cisco are now marked as matched. If later in the run Alice receives an offer from Amazon, Alice accepts and is matched to Amazon, and Cisco becomes unmatched.
Here is a longer trace:
[
// Cisco -> Alice (accept - Alice is unmatched, both become matched)
{ from: 2, to: 0, fromCo: true },
// Amazon -> Alice (accept - Alice prefers Amazon over their current match, both become matched, Cisco becomes unmatched)
{ from: 0, to: 0, fromCo: true },
// Cisco -> Charles (accept - Charles is unmatched, both become matched)
{ from: 2, to: 2, fromCo: true },
];
This is a valid run. A valid resulting Hire array would be:
[
{ company: 0, candidate: 0 }, // Amazon and Alice
{ company: 2, candidate: 2 }, // Cisco and Charles
];
as those are the results of the trace
ACTUAL PROBLEM: I have written the following tests:
describe("Part B: stableMatchingRunOracle", () => {
// Given an correct solution, no assertion should fail, and no errors should be thrown
it("should accept STABLE_MATCHING_SOLUTION_1_TRACE", () => {
expect(() => stableMatchingRunOracle(STABLE_MATCHING_SOLUTION_1_TRACE)).not.toThrow();
});
// Given an incorrect solution, some assertion should fail
it("should reject FLAWED_STABLE_MATCHING_SOLUTION_1", () => {
expect(() => stableMatchingRunOracle(FLAWED_STABLE_MATCHING_SOLUTION_1_TRACE)).toThrow(AssertionError);
});
});
my code is passing the second one, but for the first one, theres an error in the trace function. specifically, its this error message:
● Part B: stableMatchingRunOracle › should accept STABLE_MATCHING_SOLUTION_1_TRACE
expect(received).not.toThrow()
Error name: "AssertionError"
Error message: "Final matching does not align with trace for company."`
I have gone over my code multiple times and I cant find what is wrong with the logic, and I dont have any Linter warnings also (im working on vscode). What is the problem here, and how can I solve it?
This is my code that I wrote:
import assert from "assert";
import type { Offer, StableMatcherWithTrace } from "../include/stableMatching.js";
export function generateInput(n: number): number[][] {
// Helper function to shuffle an array
function shuffle(array: number[]): void {
for (let i = array.length - 1; i > 0; i--) {
const j = Math.floor(Math.random() * (i + 1));
[array[i], array[j]] = [array[j], array[i]]; // Swap elements
}
}
// Generate a 2D array of preferences
const preferences = [];
for (let i = 0; i < n; i++) {
const preference = Array.from({ length: n }, (_, index) => index);
shuffle(preference);
preferences.push(preference);
}
return preferences;
}
const NUM_TESTS = 100; // Change this to some reasonably large value
const N = 10; // Change this to some reasonable size
/**
* Tests whether or not the supplied function is a solution to the stable matching problem.
* @param makeStableMatching A possible solution to the stable matching problem
* @throws An `AssertionError` if `makeStableMatching` in not a solution to the stable matching problem
*/
type Hire = { company: number; candidate: number };
type PreferenceList = number[][];
function existsBlockingPair(companies: PreferenceList, candidates: PreferenceList, hires: Hire[]): boolean {
const companyToCandidate = new Map(hires.map(h => [h.company, h.candidate]));
const candidateToCompany = new Map(hires.map(h => [h.candidate, h.company]));
for (let company = 0; company < companies.length; company++) {
const hiredCandidate = companyToCandidate.get(company);
const companyPrefs = companies[company];
for (const preferredCandidate of companyPrefs) {
if (preferredCandidate === hiredCandidate) break; // No more preferred candidates
const preferredCandidateCompany = candidateToCompany.get(preferredCandidate);
// Check if preferredCandidateCompany is not undefined before proceeding
if (preferredCandidateCompany !== undefined) {
const preferredCandidatePrefs = candidates[preferredCandidate];
if (preferredCandidatePrefs.indexOf(company) < preferredCandidatePrefs.indexOf(preferredCandidateCompany)) {
// preferredCandidate prefers this company over their current one
return true;
}
}
}
}
return false;
}
type StableMatcher = (companies: number[][], candidates: number[][]) => Hire[];
export function stableMatchingOracle(makeStableMatching: StableMatcher) {
for (let test = 0; test < NUM_TESTS; ++test) {
const companies = generateInput(N);
const candidates = generateInput(N);
const hires = makeStableMatching(companies, candidates);
assert.strictEqual(
hires.length,
N,
"Each company must hire exactly one candidate, and each candidate must be hired by exactly one company."
);
const uniqueHires = new Set(hires.map(hire => `${hire.company}-${hire.candidate}`));
assert.strictEqual(uniqueHires.size, hires.length, "There should be no duplicate hires.");
const hasBlockingPair = existsBlockingPair(companies, candidates, hires);
assert(!hasBlockingPair, "There should be no blocking pairs in the matching.");
}
}
// Part B
/**
* Tests whether or not the supplied function follows the supplied algorithm.
* @param makeStableMatchingTrace A possible solution to the stable matching problem and its possible steps
* @throws An `AssertionError` if `makeStableMatchingTrace` does not follow the specified algorithm, or its steps (trace)
* do not match with the result (out).
*/
export function stableMatchingRunOracle(makeStableMatchingTrace: StableMatcherWithTrace): void {
for (let i = 0; i < NUM_TESTS; ++i) {
const companies = generateInput(N);
const candidates = generateInput(N);
const { trace, out } = makeStableMatchingTrace(companies, candidates);
// Initialize tracking for matches and proposals made
const companyMatches: (number | null)[] = new Array(N).fill(null) as (number | null)[];
const candidateMatches: (number | null)[] = new Array(N).fill(null) as (number | null)[];
const companyProposals: Set<string>[] = new Array(N).fill(null).map(() => new Set());
const candidateProposals: Set<string>[] = new Array(N).fill(null).map(() => new Set());
trace.forEach((offer: Offer) => {
const { from, to, fromCo } = offer;
const proposalSet = fromCo ? companyProposals[from] : candidateProposals[from];
// Ensure the offer has not been made before and is in correct order
assert(!proposalSet.has(to.toString()), "Duplicate or out-of-order offer detected.");
proposalSet.add(to.toString());
if (fromCo) {
// Company to candidate offer
const currentMatch = candidateMatches[to];
if (currentMatch === null || companies[from].indexOf(to) < companies[currentMatch].indexOf(to)) {
// Accept the offer
if (currentMatch !== null) companyMatches[currentMatch] = null;
companyMatches[from] = to;
candidateMatches[to] = from;
}
} else {
// Candidate to company offer
const currentMatch = companyMatches[to];
if (currentMatch === null || candidates[from].indexOf(to) < candidates[currentMatch].indexOf(to)) {
// Accept the offer
if (currentMatch !== null) candidateMatches[currentMatch] = null;
companyMatches[to] = from;
candidateMatches[from] = to;
}
}
});
// Validate the final matching
out.forEach((hire: Hire) => {
const { company, candidate } = hire;
assert(companyMatches[company] === candidate, "Final matching does not align with trace for company.");
assert(candidateMatches[candidate] === company, "Final matching does not align with trace for candidate.");
});
// Ensure every match in `out` was reached through the trace
assert(out.every(hire => companyMatches[hire.company] === hire.candidate), "Mismatch in the number of hires and company matches.");
assert(out.every(hire => candidateMatches[hire.candidate] === hire.company), "Mismatch in the number of hires and candidate matches.");
}
}
i expected it to pass the tests described above. It keeps on failing despite multiple attempts to solve. I have gone over my code multiple times and I cant find what is wrong with the logic, and I dont have any Linter warnings also (im working on vscode). What is the problem here, and how can I solve it?
