Class: Menuconform::Solver

Inherits:
Object
  • Object
show all
Defined in:
lib/menuconform/solver.rb

Overview

Cart solver: answers, per item, whether a valid cart exists (CART-001), whether the item's own defaults violate its constraints (CART-002), whether any valid cart totals above zero (CART-003), and whether equivalent carts can price differently (CART-004).

Exactness notes:

  • Satisfiability is exact for groups of up to 14 options (subset enumeration over distinct-count and total-unit constraints, with recursive option selectability); beyond 14 it falls back to greedy bounds, which can only over-report satisfiability (no false CART-001).
  • Max-total is a greedy upper approximation using each option's highest resolvable price: CART-003 (max <= 0) therefore never false-positives.
  • CART-004 is a deterministic reachability scan, not a random fuzzer: it is complete for the same-modifier-different-price class of ambiguity.
  • Items whose nesting is cyclic (STRUCT-005) are skipped entirely.
  • Groups a rule can't reason about (dangling refs) are skipped — STRUCT-002 owns those.

Constant Summary collapse

EXACT_ENUM_LIMIT = 
14
IDENTITY =

--- CART-003 -----------------------------------------------------------

->(p) { p }

Instance Method Summary collapse

Constructor Details

#initialize(menu) ⇒ Solver

Returns a new instance of Solver.



26
27
28
 
# File 'lib/menuconform/solver.rb', line 26

def initialize(menu)
  @menu = menu
end

Instance Method Details

#ambiguities ⇒ Object

Two carts selecting the same (modifier, quantity) multiset must price identically. They can't when one modifier is reachable on the same item through links with different price signatures.



224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
 
# File 'lib/menuconform/solver.rb', line 224

def ambiguities
  out = []
  @menu.items_by_id.each_value do |item|
    signatures = Hash.new { |h, k| h[k] = Set.new }
    @menu.reachable_group_ids(item).sort.each do |gid|
      g = @menu.groups_by_id[gid]
      existing_options(g).each do |o|
        m = @menu.modifiers_by_id[o["modifier_id"]]
        base = o.key?("price_override") ? o["price_override"] : m["price"]
        cond = (o["conditional_prices"] || []).map { |c| [c["when_modifier_id"], c["price"]] }.sort
        signatures[o["modifier_id"]] << [base, cond]
      end
    end
    signatures.each do |mid, sigs|
      next if sigs.size <= 1
      out << Finding.new("CART-004", "item", item["id"],
                         "modifier #{mid} is reachable at #{sigs.size} different prices on this item — " \
                         "equivalent carts price differently")
    end
  end
  out
end

#defaults_valid?(item) ⇒ Boolean

Defaults are invalid only when they VIOLATE constraints (exceed maxima or per-option quantity bounds). A required group with no default is normal: the agent completes the selection.

Returns:

  • (Boolean) 


109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
 
# File 'lib/menuconform/solver.rb', line 109

def defaults_valid?(item)
  queue = @menu.attached_group_ids(item).dup
  seen = Set.new
  until queue.empty?
    gid = queue.shift
    next if seen.include?(gid)
    seen << gid
    g = @menu.groups_by_id[gid]
    next unless g
    defaults = existing_options(g).select { |o| (o["default_quantity"] || 0).positive? }
    max_sel = g["max_select"]
    return false if !max_sel.nil? && defaults.size > max_sel
    max_tu = g["max_total_units"]
    return false if !max_tu.nil? && defaults.sum { |o| o["default_quantity"] } > max_tu
    defaults.each do |o|
      return false if o["default_quantity"] > (o["max_quantity"] || 1)
      min_q = o["min_quantity"] || 0
      return false if min_q.positive? && o["default_quantity"] < min_q
      queue.concat(o["child_modifier_group_ids"] || [])
    end
  end
  true
end

#feasible_selection_exists?(g, selectable) ⇒ Boolean

Returns:

  • (Boolean) 


69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
 
# File 'lib/menuconform/solver.rb', line 69

def feasible_selection_exists?(g, selectable)
  min_sel = [g["min_select"] || 0, 0].max
  max_sel = g["max_select"] || selectable.size
  min_tu = g["min_total_units"]
  max_tu = g["max_total_units"]

  return false if min_sel > max_sel
  # Empty selection is a valid answer for an optional group.
  return true if min_sel.zero? && (min_tu.nil? || min_tu <= 0)
  return false if selectable.empty? || min_sel > selectable.size

  ranges = selectable.map { |o| unit_range(o) }
  if ranges.size <= EXACT_ENUM_LIMIT
    (1..(2**ranges.size - 1)).any? do |mask|
      k = mask.digits(2).sum
      next false if k < min_sel || k > max_sel
      lo = 0
      hi = 0
      ranges.each_with_index do |r, i|
        next if mask[i].zero?
        lo += r[0]
        hi += r[1]
      end
      (max_tu.nil? || lo <= max_tu) && (min_tu.nil? || hi >= min_tu)
    end
  else
    # Greedy bounds: can only over-report satisfiability.
    (min_sel..[max_sel, ranges.size].min).any? do |k|
      lo = ranges.map(&:first).min(k).sum
      hi = ranges.map(&:last).max(k).sum
      (max_tu.nil? || lo <= max_tu) && (min_tu.nil? || hi >= min_tu)
    end
  end
end

#findings ⇒ Object 



30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
 
# File 'lib/menuconform/solver.rb', line 30

def findings
  out = []
  @menu.items_by_id.each_value do |item|
    next if @menu.depth_info(item)[:cyclic]
    unless item_satisfiable?(item)
      out << Finding.new("CART-001", "item", item["id"],
                         "no selection satisfies this item's modifier constraints — it cannot be ordered")
      next
    end
    unless defaults_valid?(item)
      out << Finding.new("CART-002", "item", item["id"],
                         "the pre-selected defaults violate this item's own group constraints")
    end
    max = max_total(item)
    if max <= 0
      out << Finding.new("CART-003", "item", item["id"],
                         "no valid cart totals above zero (maximum reachable total: #{max})")
    end
  end
  out + ambiguities
end

#group_satisfiable?(gid, stack) ⇒ Boolean

Returns:

  • (Boolean) 


58
59
60
61
62
63
64
65
66
67
 
# File 'lib/menuconform/solver.rb', line 58

def group_satisfiable?(gid, stack)
  g = @menu.groups_by_id[gid]
  return true if g.nil?          # dangling ref: STRUCT-002 owns it
  return false if stack.include?(gid) # cycle: conservatively uncompletable

  selectable = existing_options(g).select do |o|
    (o["child_modifier_group_ids"] || []).all? { |c| group_satisfiable?(c, stack + [gid]) }
  end
  feasible_selection_exists?(g, selectable)
end

#included_discount(g, chosen) ⇒ Object

Free-quantity discount applied to a chosen selection (pricing semantics, not choice): included_counting units = free units by allocation order; options = whole cheapest/most-expensive selected options free. Negative unit prices never benefit from a free slot.



204
205
206
207
208
209
210
211
212
213
214
215
216
217
 
# File 'lib/menuconform/solver.rb', line 204

def included_discount(g, chosen)
  inc = g["included_quantity"] || 0
  return 0 unless inc.positive?
  allocation = g["included_allocation"] || "cheapest_first"
  if (g["included_counting"] || "units") == "options"
    ordered = chosen.sort_by { |c| c[:unit] }
    ordered.reverse! if allocation == "most_expensive_first"
    ordered.first(inc).sum { |c| [c[:unit], 0].max * c[:units] }
  else
    units = chosen.flat_map { |c| Array.new(c[:units]) { c[:unit] } }.sort
    units.reverse! if allocation == "most_expensive_first"
    units.first(inc).sum { |u| [u, 0].max }
  end
end

#item_satisfiable?(item) ⇒ Boolean

--- CART-001 -----------------------------------------------------------

Returns:

  • (Boolean) 


54
55
56
 
# File 'lib/menuconform/solver.rb', line 54

def item_satisfiable?(item)
  @menu.attached_group_ids(item).uniq.all? { |gid| group_satisfiable?(gid, []) }
end

#max_contribution(gid, stack, transform) ⇒ Object 



164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
 
# File 'lib/menuconform/solver.rb', line 164

def max_contribution(gid, stack, transform)
  g = @menu.groups_by_id[gid]
  return 0 if g.nil? || stack.include?(gid)

  selectable = existing_options(g).select do |o|
    (o["child_modifier_group_ids"] || []).all? { |c| group_satisfiable?(c, stack + [gid]) }
  end
  min_sel = [g["min_select"] || 0, 0].max
  max_sel = g["max_select"] || selectable.size
  return 0 if selectable.empty? || min_sel > max_sel || min_sel > selectable.size

  budget = g["max_total_units"] || Float::INFINITY
  candidates = selectable.map do |o|
    unit = transform.call(max_unit_price(o))
    range = unit_range(o)
    units = unit.positive? ? range[1] : range[0]
    kids = (o["child_modifier_group_ids"] || []).sum { |c| max_contribution(c, stack + [gid], transform) }
    { unit: unit, units: units, kids: kids, value: (unit * units) + kids }
  end.sort_by { |c| -c[:value] }

  chosen = []
  used = 0
  candidates.each do |c|
    forced = chosen.size < min_sel
    break if !forced && chosen.size >= max_sel
    next unless forced || c[:value].positive?
    units = [c[:units], budget - used].min
    units = 1 if forced && units < 1
    next if units < 1
    chosen << { unit: c[:unit], units: units, kids: c[:kids] }
    used += units
  end

  chosen.sum { |c| (c[:unit] * c[:units]) + c[:kids] } - included_discount(g, chosen)
end

#max_total(item) ⇒ Object 



137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
 
# File 'lib/menuconform/solver.rb', line 137

def max_total(item)
  total = item["price"]
  (item["modifier_group_ids"] || []).uniq.each { |gid| total += max_contribution(gid, [], IDENTITY) }
  slots = item["slots"] || []
  unless slots.empty?
    case item["slot_pricing"]
    when "proportional"
      slots.each do |s|
        # Rounded half away from zero, per unit — the pinned IR semantics.
        scale = ->(p) { (p * s["fraction"]).round }
        (s["modifier_group_ids"] || []).uniq.each { |gid| total += max_contribution(gid, [], scale) }
      end
    when "max_slot"
      # Charged as if the most expensive slot's selections applied to the
      # whole item: each distinct group counts once, unscaled.
      slots.flat_map { |s| s["modifier_group_ids"] || [] }.uniq.each do |gid|
        total += max_contribution(gid, [], IDENTITY)
      end
    else # full_price
      slots.each do |s|
        (s["modifier_group_ids"] || []).uniq.each { |gid| total += max_contribution(gid, [], IDENTITY) }
      end
    end
  end
  total
end