@entur/add-customers-to-offer-configurations - npm Package Compare versions

Comparing version 1.2.2 to 1.3.0

dist/index.d.ts

 import type { Offer } from './types/offersTypes';
-import { OfferConfiguration, Customer } from './types/reserveOfferTypes';
-/** This is a stripped down version of the Offer type, containing only the root keys that we need. The hope is that this will lead to fewer updates because the type has changed. */
+import { Customer, OfferConfiguration } from './types/reserveOfferTypes';
+/**
+ * This is a stripped down version of the Offer type,
+ * containing only the root keys that we need.
+ * The hope is that this will lead to fewer updates because
+ * the type has changed.
+ */
 declare type StrippedOffer = Pick<Offer, 'id' | 'travelerMapping' | 'salesPackageConfig'>;
@@ -13,2 +18,19 @@ /**
 export default function addCustomersToOfferConfigurations(customers: Customer[], offerConfigurations: OfferConfiguration[], offers: StrippedOffer[]): OfferConfiguration[];
+declare type SafeBetReturnType = {
+    solvedOfferConfigurations: OfferConfiguration[];
+    remainingOfferConfigurations: OfferConfiguration[];
+    remainingCustomers: Customer[];
+};
+/**
+ * If an offer has a minimum amount of travelers equal to the travellers it is
+ * meant for, assigning these customers to the offer's corresponding offer
+ * configuration is considered a safe bet.
+ *
+ * This algorithm was invented to cope with group tickets, in a single ticket
+ * and a single fare product covers multiple travellers. We could not come up
+ * with an elegant modification to assignCustomersUsingMinimumCostFlow,
+ * but this algorithm seems to remove all offer configurations that would
+ * warrant a modification from its input.
+ */
+export declare function assignUsingSafeBets(customers: Customer[], offerConfigurations: OfferConfiguration[], offers: StrippedOffer[]): SafeBetReturnType;
 export {};

dist/index.js

 "use strict";
 Object.defineProperty(exports, "__esModule", { value: true });
+exports.assignUsingSafeBets = void 0;
 const min_cost_flow_1 = require("min-cost-flow");
+const utilities_1 = require("./utilities");
 const NETEX_ID_SEPARATOR = '|';
@@ -13,8 +15,8 @@ /**
 function addCustomersToOfferConfigurations(customers, offerConfigurations, offers) {
-    const customersById = new Map(customers.map((customer) => [
-        customer.customerId,
-        customer
-    ]));
     /*
-     * Having N identical offerConfigurations with count 1 is the same thing as having 1 offerConfiguration with count N:
+     * In order for our algorithms to work, offers cannot have a count other than
+     * one.
+     *
+     * Having N identical offerConfigurations with count 1
+     * is the same thing as having 1 offerConfiguration with count N:
      * https://entur.slack.com/archives/C01BNGQ8LM6/p1601995996121000
@@ -27,2 +29,84 @@ */
     });
+    const configurationsGroupedByServiceJourney = getConfigurationsGroupedByServiceJourney(offerConfigurationsWithOnly1Counts, offers);
+    return configurationsGroupedByServiceJourney
+        .flatMap((offerConfigurationsForServiceJourney) => assignCustomersForOneServiceJourney(customers, offerConfigurationsForServiceJourney, offers))
+        .map((offerConfiguration) => {
+        var _a;
+        const offersUsed = offers.filter((offer) => offer.id === offerConfiguration.offerId);
+        return Object.assign(Object.assign({}, offerConfiguration), { customers: (_a = offerConfiguration.customers) === null || _a === void 0 ? void 0 : _a.map((customer) => {
+                var _a;
+                return getCustomerWithOnlyTheEntitlementsThatAreRequiredForPurchase(offersUsed, (_a = offerConfiguration.selectableProductIds) !== null && _a !== void 0 ? _a : [], customer);
+            }) });
+    })
+        .map((offerConfiguration) => makeEachEntitlementTypeOccurOnceInEachOfferConfiguration(offerConfiguration));
+}
+exports.default = addCustomersToOfferConfigurations;
+/**
+ * Assigns customers optimally to the offer configurations given the supplied
+ * offers. For the algorithms to work, the offers all have to be on the same
+ * service journey.
+ *
+ * @param customers The customers to be added
+ * @param offerConfigurations offerConfigurations belonging to the same service
+ * journey
+ * @param offers The offers used to generate the offerConfigurations
+ */
+function assignCustomersForOneServiceJourney(customers, offerConfigurations, offers) {
+    const { solvedOfferConfigurations, remainingOfferConfigurations, remainingCustomers } = assignUsingSafeBets(customers, offerConfigurations, offers);
+    return [
+        ...solvedOfferConfigurations,
+        ...assignCustomersUsingMinimumCostFlow(remainingCustomers, remainingOfferConfigurations, offers)
+    ];
+}
+/**
+ * If an offer has a minimum amount of travelers equal to the travellers it is
+ * meant for, assigning these customers to the offer's corresponding offer
+ * configuration is considered a safe bet.
+ *
+ * This algorithm was invented to cope with group tickets, in a single ticket
+ * and a single fare product covers multiple travellers. We could not come up
+ * with an elegant modification to assignCustomersUsingMinimumCostFlow,
+ * but this algorithm seems to remove all offer configurations that would
+ * warrant a modification from its input.
+ */
+function assignUsingSafeBets(customers, offerConfigurations, offers) {
+    return offerConfigurations.reduce((accumulator, nextOfferConfiguration) => {
+        const valueIfNoSafeBetCanBeMade = Object.assign(Object.assign({}, accumulator), { remainingOfferConfigurations: [
+                ...accumulator.remainingOfferConfigurations,
+                nextOfferConfiguration
+            ] });
+        const theOfferInQuestion = offers.find(({ id }) => nextOfferConfiguration.offerId === id);
+        if (theOfferInQuestion === undefined) {
+            return valueIfNoSafeBetCanBeMade;
+        }
+        const moreThanOneTravelerMapping = theOfferInQuestion.travelerMapping.length > 1;
+        if (moreThanOneTravelerMapping) {
+            return valueIfNoSafeBetCanBeMade;
+        }
+        const travelerValidityGroup = theOfferInQuestion.travelerMapping[0];
+        if (travelerValidityGroup === undefined) {
+            return valueIfNoSafeBetCanBeMade;
+        }
+        const { travelerIds, minNumberOfTravelers } = travelerValidityGroup;
+        const allSpecifiedTravelersMustUseThisOffer = travelerIds.length === minNumberOfTravelers;
+        if (allSpecifiedTravelersMustUseThisOffer) {
+            const [customersForThisOfferConfiguration, remainingCustomers] = (0, utilities_1.partition)(accumulator.remainingCustomers, (customer) => travelerIds.includes(customer.customerId));
+            return Object.assign(Object.assign({}, accumulator), { remainingCustomers, solvedOfferConfigurations: [
+                    ...accumulator.solvedOfferConfigurations,
+                    Object.assign(Object.assign({}, nextOfferConfiguration), { customers: customersForThisOfferConfiguration })
+                ] });
+        }
+        return valueIfNoSafeBetCanBeMade;
+    }, {
+        remainingCustomers: customers,
+        remainingOfferConfigurations: [],
+        solvedOfferConfigurations: []
+    });
+}
+exports.assignUsingSafeBets = assignUsingSafeBets;
+function assignCustomersUsingMinimumCostFlow(customers, offerConfigurations, offers) {
+    const customersById = new Map(customers.map((customer) => [
+        customer.customerId,
+        customer
+    ]));
     const offerWithId = new Map(offers.map((offer) => [offer.id, offer]));
@@ -33,3 +117,3 @@ const travellersForOfferId = new Map(offers.map((offer) => [
     ]));
-    const configurationsGroupedByServiceJourney = groupBy(offerConfigurationsWithOnly1Counts, (configuration) => {
+    const configurationsGroupedByServiceJourney = (0, utilities_1.groupBy)(offerConfigurations, (configuration) => {
         var _a;
@@ -40,3 +124,3 @@ const offer = offerWithId.get(configuration.offerId);
     return [...configurationsGroupedByServiceJourney.values()].flatMap((configurationsOnThisServiceJourney) => {
-        const allTravellerIds = uniq(compact(configurationsOnThisServiceJourney
+        const allTravellerIds = (0, utilities_1.uniq)((0, utilities_1.compact)(configurationsOnThisServiceJourney
             .map((configuration) => configuration.offerId)
@@ -54,3 +138,3 @@ .flatMap((offerId) => travellersForOfferId.get(offerId))));
             var _a;
-            return compact((_a = travellersForOfferId
+            return (0, utilities_1.compact)((_a = travellersForOfferId
                 .get(configuration.offerId)) === null || _a === void 0 ? void 0 : _a.map((travellerId) => {
@@ -62,9 +146,21 @@ const nodeNumber = travellerIdToNodeNumber.get(travellerId);
                 /*
-                 * Every offer received from the backend contains the IDs of the (possibly anonymous) travellers it is meant for, and
-                 * anonymous travellers are identified by a generated ID.
-                 * We have not seen examples of it yet, but it is technically possible for this set of generated IDs
-                 * to exceed the number of requested anonymous travellers. If the cost of assigning an anonymous and a named traveller
-                 * to an order was equal, there are many valid solutions to such a min-cost-max-flow problem that end up leaving out a named customer.
-                 * But by assigning a higher cost to picking an anonymous traveller for an offerConfiguration,
-                 * we can make sure that the named customers are preferred in such a case.
+                 * Every offer received from the backend contains
+                 * the IDs of the (possibly anonymous) travellers
+                 * it is meant for, and anonymous travellers
+                 * are identified by a generated ID.
+                 * We have not seen examples of it yet,
+                 * but it is technically possible
+                 * for this set of generated IDs
+                 * to exceed the number of requested anonymous travellers.
+                 *
+                 * If the cost of assigning an anonymous
+                 * and a named traveller to an order was equal,
+                 * there are many valid solutions to such
+                 * a min-cost-max-flow problem that end up leaving out a
+                 * named customer.
+                 *
+                 * By assigning a higher cost to picking an anonymous
+                 * traveller for an offerConfiguration,
+                 * we can make sure that the named customers
+                 * are preferred in such a case.
                  */
@@ -81,6 +177,15 @@ const cost = customersById.has(travellerId) ? 0 : 1;
         /*
-         * For the base case, allTravellerIds.length=1 and configurationsOnThisServiceJourney.length=1,
-         * 0 is the start node, 1 is the only traveller node, 2 is the only offer configuration node and 3 is the end node.
-         * It follows that endNode = allTravellerIds.length + configurationsOnThisServiceJourney.length + 1 will hold
-         * for any larger number of travellers or offerConfigurations.
+         * For the base case, allTravellerIds.length=1 and
+         * configurationsOnThisServiceJourney.length=1,
+         * 0 is the start node, 1 is the only traveller node,
+         * 2 is the only offer configuration node and 3 is the end node.
+         *
+         * It follows that
+         *
+         *     endNode =
+         *        allTravellerIds.length
+         *        + configurationsOnThisServiceJourney.length
+         *        + 1
+         *
+         * will hold for any larger number of travellers or offerConfigurations
          */
@@ -90,25 +195,25 @@ const endNode = allTravellerIds.length + configurationsOnThisServiceJourney.length + 1;
             ...[...nodeNumberToTravellerId.keys()].map((n) => ({
+                capacity: 1,
+                cost: 0,
                 from: startNode,
-                to: n,
-                capacity: 1,
-                cost: 0
+                to: n
             })),
             ...travellerToOfferEdgesAsTuples.map(([from, to, cost]) => ({
+                capacity: 1,
+                cost,
                 from,
-                to,
-                capacity: 1,
-                cost
+                to
             })),
-            ...compact(configurationsOnThisServiceJourney.map((configuration, configurationIndex) => {
+            ...(0, utilities_1.compact)(configurationsOnThisServiceJourney.map((configuration, configurationIndex) => {
                 const offer = offerWithId.get(configuration.offerId);
                 if (offer) {
-                    const kroneAmount = findPriceObjectByCurrency(offer.salesPackageConfig.prices);
+                    const kroneAmount = (0, utilities_1.findPriceObjectByCurrency)(offer.salesPackageConfig.prices);
                     const cost = kroneAmount
-                        ? convertFromTwoDecimalKroneStringToOreInteger(kroneAmount.amount)
+                        ? (0, utilities_1.convertFromTwoDecimalKroneStringToOreInteger)(kroneAmount.amount)
                         : 0;
                     return {
+                        capacity: 1,
+                        cost,
                         from: configurationIndex + allTravellerIds.length + 1,
-                        to: endNode,
-                        capacity: 1,
-                        cost
+                        to: endNode
                     };
@@ -119,3 +224,3 @@ }
         ];
-        const optimalAssignmentOfCustomersToConfigurationsAsFlowNetwork = min_cost_flow_1.minCostFlowForNumberNodes(edges, Number.POSITIVE_INFINITY);
+        const optimalAssignmentOfCustomersToConfigurationsAsFlowNetwork = (0, min_cost_flow_1.minCostFlowForNumberNodes)(edges, Number.POSITIVE_INFINITY);
         const edgesFromTravellersToOffer = optimalAssignmentOfCustomersToConfigurationsAsFlowNetwork
@@ -127,32 +232,29 @@ .filter((edge) => edge.flow > 0)
             const configurationNode = allTravellerIds.length + index + 1;
-            const customersAssignedToThisOffer = compact(edgesFromTravellersToOffer
+            const customersAssignedToThisOffer = (0, utilities_1.compact)(edgesFromTravellersToOffer
                 .filter(({ to }) => to === configurationNode)
                 .map(({ from }) => nodeNumberToTravellerId.get(from)));
-            return Object.assign(Object.assign({}, configuration), { customers: compact(customersAssignedToThisOffer.map((travellerId) => {
-                    var _a;
-                    const customer = customersById.get(travellerId);
-                    if (!customer) {
-                        return;
-                    }
-                    const offer = offerWithId.get(configuration.offerId);
-                    if (!offer) {
-                        // This should really never be the case, but if no matching offer is found, it seems more sensible to return the customer as-is rather than remove him/her
-                        return customer;
-                    }
-                    return getCustomerWithOnlyTheEntitlementsThatAreRequiredForPurchase(offer, (_a = configuration.selectableProductIds) !== null && _a !== void 0 ? _a : [], customer);
-                })) });
+            return Object.assign(Object.assign({}, configuration), { customers: (0, utilities_1.compact)(customersAssignedToThisOffer.map((travellerId) => customersById.get(travellerId))) });
         });
     });
 }
-exports.default = addCustomersToOfferConfigurations;
-function getCustomerWithOnlyTheEntitlementsThatAreRequiredForPurchase(offer, selectableProductIds, customer) {
+/**
+ * Removes any entitlements from the customer that are not required to purchase
+ * the offer.
+ *
+ * reserve-offers has been known to crash if entitlements other than the ones
+ * required to purchase the specified offer are found in the offer
+ * configuration.
+ */
+function getCustomerWithOnlyTheEntitlementsThatAreRequiredForPurchase(offers, selectableProductIds, customer) {
     var _a;
-    const idsOfEntitlementProductsRequiredForPurchase = extractIdsOfEntitlementProductsRequiredToPurchaseOffer(offer, selectableProductIds);
+    const idsOfEntitlementProductsRequiredForPurchase = extractIdsOfEntitlementProductsRequiredToPurchaseOffer(offers, selectableProductIds);
     const entitlementsThatReserveOffersWillAccept = (_a = customer.entitlements) === null || _a === void 0 ? void 0 : _a.filter(({ entitlementProductRef }) => idsOfEntitlementProductsRequiredForPurchase.has(entitlementProductRef.id));
     return Object.assign(Object.assign({}, customer), { entitlements: entitlementsThatReserveOffersWillAccept });
 }
-function extractIdsOfEntitlementProductsRequiredToPurchaseOffer(offer, selectableProductIds) {
+function extractIdsOfEntitlementProductsRequiredToPurchaseOffer(offers, selectableProductIds) {
     const selectableProductIdsAsSet = new Set(selectableProductIds);
-    const selectedFareProducts = offer.salesPackageConfig.fareProducts.filter((fareProduct) => isFareProductToBePurchased(selectableProductIdsAsSet, fareProduct));
-    return new Set(compact(selectedFareProducts.map((fareProduct) => { var _a; return (_a = fareProduct.discountRight) === null || _a === void 0 ? void 0 : _a.originatingFromProductId; })));
+    const selectedFareProducts = offers
+        .flatMap((offer) => offer.salesPackageConfig.fareProducts)
+        .filter((fareProduct) => isFareProductToBePurchased(selectableProductIdsAsSet, fareProduct));
+    return new Set((0, utilities_1.compact)(selectedFareProducts.map((fareProduct) => { var _a; return (_a = fareProduct.discountRight) === null || _a === void 0 ? void 0 : _a.originatingFromProductId; })));
 }
@@ -164,34 +266,43 @@ function isFareProductToBePurchased(selectableProductIds, fareProduct) {
 }
-function compact(array) {
-    if (!array)
-        return [];
-    return array.filter((item) => Boolean(item));
-}
-function uniq(array) {
-    if (!array)
-        return [];
-    return [...new Set(array)];
-}
-function groupBy(array, iteratee) {
-    return array.reduce((map, item, index, array_) => {
-        const key = iteratee(item, index, array_);
-        const existingGroup = map.get(key);
-        if (existingGroup) {
-            existingGroup.push(item);
-        }
-        else {
-            map.set(key, [item]);
-        }
-        return map;
-    }, new Map());
-}
 /**
- * Takes a list of prices with different currencies and returns the first that matches the provided currency
- * Defaults to 'NOK'
+ * Prevents two customers from having entitlements with the same IDs within the
+ * same offer configuration. If two or more entitlements with the same ID are
+ * found, only the first occurrence is kept.
+ *
+ * <h2>Background</h2>
+ * If two customers have supply same entitlement, they will <em>both</em> be
+ * taxed the same amount as if only one of them had supplied the entitlement.
+ * In effect, they will be doubly taxed.
+ *
+ * There is some hope that the benefits service may, at some point in the
+ * future, share the burden between the travellers.
+ *
+ * @see <a href="https://entur.slack.com/archives/C01BNGQ8LM6/p1632298229281100?thread_ts=1632293883.270800&cid=C01BNGQ8LM6">
+ *  The Slack message in which we were told that customers would be taxed doubly
+ * </a>
+ * @param offerConfiguration
  */
-function findPriceObjectByCurrency(prices, currency = 'NOK') {
-    return prices.find((price) => price.currency === currency);
+function makeEachEntitlementTypeOccurOnceInEachOfferConfiguration(offerConfiguration) {
+    var _a;
+    const updatedCustomers = (_a = offerConfiguration.customers) === null || _a === void 0 ? void 0 : _a.reduce((accumulator, nextCustomer) => {
+        var _a;
+        const alreadyUsedEntitlementIds = new Set(accumulator.flatMap((customer) => {
+            var _a, _b;
+            return (_b = (_a = customer.entitlements) === null || _a === void 0 ? void 0 : _a.map((otherCustomerEntitlement) => otherCustomerEntitlement.entitlementProductRef.id)) !== null && _b !== void 0 ? _b : [];
+        }));
+        const entitlements = (_a = nextCustomer.entitlements) === null || _a === void 0 ? void 0 : _a.filter((entitlement) => {
+            const somePreviousCustomerHasSameEntitlement = alreadyUsedEntitlementIds.has(entitlement.entitlementProductRef.id);
+            return !somePreviousCustomerHasSameEntitlement;
+        });
+        return [...accumulator, Object.assign(Object.assign({}, nextCustomer), { entitlements })];
+    }, []);
+    return Object.assign(Object.assign({}, offerConfiguration), { customers: updatedCustomers });
 }
-function convertFromTwoDecimalKroneStringToOreInteger(kroneAmount) {
-    return Math.floor(Number.parseFloat(kroneAmount) * 100);
+function getConfigurationsGroupedByServiceJourney(offerConfigurations, offers) {
+    return [
+        ...(0, utilities_1.groupBy)(offerConfigurations, (configuration) => offers
+            .filter((offer) => offer.id === configuration.offerId)
+            .flatMap((offer) => offer.salesPackageConfig.serviceJourneyIds)
+            .join(NETEX_ID_SEPARATOR)).values()
+    ];
 }

package.json

 {
   "name": "@entur/add-customers-to-offer-configurations",
-  "version": "1.2.2",
+  "version": "1.3.0",
   "description": "Adds customers to a group of offer configurations, given the offers used to generate them",
@@ -14,3 +14,3 @@ "main": "dist/index.js",
   "scripts": {
-    "build": "rm -rf dist && tsc",
+    "build": "rm -rf dist && npx tsc",
     "update-types": "npx swagger-typescript-api --path https://api.staging.entur.io/sales/v1/offers/api-docs/swagger.json --output source/types  -n offersTypes.ts --no-client && npx swagger-typescript-api --path https://api.staging.entur.io/api-docs/reserve-offer?group=public --output source/types  -n reserveOfferTypes.ts --no-client",
@@ -20,3 +20,3 @@ "test": "jest",
     "lint:fix": "npx prettier --write *.{md,json} .*.js; xo --fix",
-    "prepublishOnly": "tsc && npm run test",
+    "prepublishOnly": "npx tsc && npm run test",
     "prepare": "husky install"
@@ -39,2 +39,4 @@ },
     "eslint-plugin-prettier": "^3.4.0",
+    "eslint-plugin-simple-import-sort": "^7.0.0",
+    "eslint-plugin-sort-keys": "^2.3.5",
     "husky": "^7.0.1",
@@ -45,2 +47,3 @@ "jest": "^27.0.6",
     "prettier": "^2.3.2",
+    "typescript": "^4.4.3",
     "xo": "^0.42.0"
@@ -47,0 +50,0 @@ },

README.md

@@ -103,2 +103,10 @@ # @entur/add-customers-to-offer-configurations
 
+### Known shortcomings
+
+Due to
+[the way the assignment problem algorithm works](#transforming-the-problem-to-a-graph),
+the module's support for offer configurations that require multiple customers is
+limited. The algorithm is only guaranteed to work if such offers can be
+[pruned as safe bets](#pruning-safe-bets).
+
 ### You can only add customers that were present in the offers request
@@ -136,9 +144,2 @@
 
-Optimally assigning customers to offer configurations is an
-[assignment problem](https://en.wikipedia.org/wiki/Assignment_problem)
-(specifically, a _balanced_ assignment problem), which is solvable as a
-[minimum-cost flow problem](https://en.wikipedia.org/wiki/Minimum-cost_flow_problem).
-
-### Transforming the problem to a graph
-
 To solve the problem, we first assume that **each stretch in the journey (each
@@ -150,5 +151,27 @@ service journey) is independent of the others.** That is to say, there is no
 
-For each stretch (or _service journey_, as they're called in the Entur domain),
-we can then construct a problem graph in the following way:
+After making that assumption, the problem is solved by two algorithms in
+succession.
 
+### Pruning safe bets
+
+If an offer has a minimum amount of travelers equal to the travellers it is
+meant for, assigning these customers to the offer's corresponding offer
+configuration is considered a safe bet. The function assignUsingSafeBets handles
+this.
+
+This algorithm was invented to cope with group tickets, in a single ticket and a
+single fare product covers multiple travellers. We could not come up with an
+elegant modification to assignCustomersUsingMinimumCostFlow, but this algorithm
+seems to remove all offer configurations that would warrant a modification from
+its input.
+
+### Transforming the problem to a graph
+
+Optimally assigning customers to offer configurations is an
+[assignment problem](https://en.wikipedia.org/wiki/Assignment_problem)
+(specifically, a _balanced_ assignment problem), which is solvable as a
+[minimum-cost flow problem](https://en.wikipedia.org/wiki/Minimum-cost_flow_problem).
+
+We construct a flow network representing the problem in the following way:
+
 1. Every traveler and offer configuration on this service journey is considered
@@ -155,0 +178,0 @@ a node.

No alert changes

Improved metrics

Total package byte prevSize

128973

increased by9.14%

Number of package files

10

increased by25%

Lines of code

2583

increased by8.71%

Number of lines in readme file

197

increased by13.22%

Worsened metrics

Dev dependency count

23

increased by15%

No dependency changes