Ciao!
I hope you haven’t missed me too much. Today, our boutique is offering you a wide range of perfumes!
Exercism currently lacks exercises exploring Boolean function simplification, digital logic, and switching theory. General Boolean minimization can produce multiple non-unique minimal covers (e.g. cyclic charts in Petrick’s method), making automated cross-track testing difficult.
Essential Accords resolves this by focusing on identifying Essential Prime Implicants (EPIs) with support for don’t-care conditions. Because the set of Essential Prime Implicants is mathematically unique for any Boolean function, inputs and outputs are 100% deterministic.
The problem is wrapped in an artisanal perfumery narrative, where binary variables are fragrance notes, minterms are bespoke client recipes, and essential prime implicants are indispensable base accords that the atelier must prepare.
Introduction
Nestled in the sun-drenched hills of Grasse, the historic perfume capital, stands the venerable atelier of Maison l’Essence.
As the junior apprentice to the atelier’s renowned Nez (Master Perfumer), you spend your days in front of the perfumer’s organ—a tiered semi-circular console holding hundreds of amber crystal flacons of precious aromatic extracts.
For the upcoming Grand Solstice Gala, the atelier has been commissioned to produce a collection of bespoke perfumes.
Each creation in the commission is defined by a precise harmony of fragrance notes—such as Bergamot, Jasmine, Cedarwood, and Amber.
An ingredient is either present (1) or omitted (0).
The master ledger lists every approved formula as a unique recipe.
The gala is only days away, and the workshop is in crisis.
Mixing every bespoke perfume individually from scratch would require dozens of custom vials, quickly overwhelming the atelier’s limited bench space and glassware.
Fortunately, the master perfumer knows a trade secret: perfumers rarely mix every recipe from scratch.
Instead, they pre-blend versatile base accords—foundational combinations that leave certain notes open, allowing multiple client perfumes to be crafted from a single shared decanter.
The Master opens a grid ledger and begins sketching a geometric map of the scents:
“Observe! When recipes differ by only a single note, they blend together into a larger accord.
But beware: some rare, fragile perfumes can only ever be produced by a single, specific accord.
These are our Essential Accords.
If you fail to prepare even one of them, those signature fragrances cannot be bottled!”
Before the distillation alembics are lit, you must examine the commission’s scent ledger, map out the fragrance combinations, and identify every essential accord that the atelier must prepare.
Instructions
Your task is to identify all essential base accords needed to satisfy a commission of bespoke perfumes.
The Fragrance Ledger
Each perfume formula is defined by N binary fragrance notes.
A formula is represented as an integer minterm whose binary representation indicates which notes are present:
- Bit
1: Note is included. - Bit
0: Note is omitted.
Notes are ordered from most significant bit to least significant bit.
For example, with N = 4 notes ordered A, B, C, D:
- Formula
13(1101_2) contains notes A, B, and D, but omits note C. - Formula
3(0011_2) contains notes C and D, but omits notes A and B.
Commission Types
You will be given two sets of formulas:
- Mandatory Perfumes (
minterms): The official client requests for the gala.
Every single one of these formulas must be covered by at least one base accord. - Optional Formulas (
dontCares): Experimental or seasonal variations known to the atelier.
You may freely use these formulas to expand and simplify base accords, but they do not require coverage.
The Accord Map
To find which formulas can be blended together, place all possible formulas on a grid arranged in Gray code order (where adjacent rows and columns differ by exactly one note):
CD
\ 00 01 11 10
AB +---+---+---+---+
00 | | 1 | 1 | |
+---+---+---+---+
01 | 1 | 1 | | |
+---+---+---+---+
11 | 1 | 1 | | |
+---+---+---+---+
10 | | | | |
+---+---+---+---+
The grid wraps around in all directions:
- The top edge is adjacent to the bottom edge.
- The left edge is adjacent to the right edge.
- The four corners are adjacent to one another.
Building Accords
Formulas that are adjacent can be grouped into rectangular accords whose dimensions are powers of two (1, 2, 4, 8, \dots).
Merging adjacent cells eliminates the note that differs:
An accord is represented as a string of length N using cube notation:
'0': The note is omitted in this accord.'1': The note is present in this accord.'-': The note was eliminated (it can be present or absent).
A prime accord is an accord that has been expanded as large as possible—it cannot be doubled in size without including an invalid (unapproved) cell.
Both mandatory perfumes and optional formulas can be included when forming prime accords.
Identifying Essential Accords
Some perfumes might be covered by multiple overlapping prime accords.
However, if a mandatory perfume is covered by only one prime accord, that accord is essential (indispensable): without it, that client perfume cannot be crafted!
Optional formulas do not make an accord essential; only mandatory perfumes can do so.
Step-by-Step Example
Suppose N = 4 notes (A, B, C, D) with:
minterms = [1, 3, 4, 5, 12, 13]dontCares = []
1. Find Prime Accords
- Formulas 1 (0001) and 3 (0011) merge into accord
"00-1". - Formulas 1 (0001) and 5 (0101) merge into accord
"0-01". - Formulas 4 (0100), 5 (0101), 12 (1100), and 13 (1101) merge into accord
"-10-".
2. Check Coverage of Mandatory Perfumes
- Perfume 3 is only covered by
"00-1": therefore,"00-1"is essential. - Perfumes 4, 12, and 13 are only covered by
"-10-": therefore,"-10-"is essential. - Accord
"0-01"covers perfumes 1 and 5.
However, perfume 1 is already covered by"00-1", and perfume 5 is already covered by"-10-".
Therefore,"0-01"is not essential.
3. Result
The essential accords are:
["-10-", "00-1"]
Output Requirements
Return an array containing all essential accords as strings in cube notation.
The strings must be sorted in lexicographical order (ASCII order: '-' < '0' < '1').
If no essential accords exist, return an empty array [].
Canonical Data Structure
{
"uuid": "8f8b8098-ff25-4b00-8451-b062ca3f31cf",
"description": "instructions example walkthrough",
"property": "essentialAccords",
"input": {
"variableCount": 4,
"minterms": [1, 3, 4, 5, 12, 13],
"dontCares": []
},
"expected": ["-10-", "00-1"]
}
