Maximum Budget Problem

maximum_budget.ts

// Task 2.  Maximum Budget Problem.

// We want to find out the most expensive trip combinations that can be purchased with a given budget. Given the price lists for two cities and a budget, find the total cost to buy them.
// Return maximum budget that can be spent, or -1 if it is not possible to buy both trips.
// Example 1
// Total trip budget = 10
// Paris trips = [3, 1]
// Barcelona trips = [5, 2, 8]

// Sample Output: 9
// Explanation: 8 (Barcelona third trip) + 1 (Paris second trip) = 9 (total budget)
// Example 2
// Total trip budget = 5
// Paris trips = [4]
// Barcelona trips = [5]

// Sample Output: -1
// Explanation: 4+5>5 so return -1 


// interface Trip {
//   [key: string]: number[];
// }
// const trips1 = {
//   Paris: [3, 1],
//   Barcelona: [5, 2, 8],
// };

// const trips2 = {
//   Paris: [4],
//   Barcelona: [5],
// };


// const findTotalCost = (trips: Trip, budget: number): number => {
//   const numbers = Object.keys(trips).map((key: string) =>
//     trips[key].length !== 0 ? trips[key] : null
//   );
//   const allCombinations = combine(numbers);
//   const closestMaxValue = findClosest(budget, allCombinations);

//   return closestMaxValue <= budget ? closestMaxValue : -1;
// }

// const findClosest = (x: number, arr: number[]): number => {
//   return arr.reduce((a, b) => {
//     let aDiff = Math.abs(a - x);
//     let bDiff = Math.abs(b - x);

//     if (aDiff === bDiff) {
//       return a < b ? a : b;
//     } else {
//       return bDiff < aDiff ? b : a;
//     }
//   });
// };

// const combine = ([head, ...[headTail, ...tailTail]]) => {
//   if (!headTail) {
//     return head;
//   }

//   const combined = headTail.reduce((acc, x) => {
//     return acc.concat(head.map((h) => h + x));
//   }, []);

//   return combine([combined, ...tailTail]);
// };



interface Trip {
  [key: string]: number[];
}
const trips1 = {
  Paris: [3, 1],
  Barcelona: [5, 2, 8],
};

const trips2 = {
  Paris: [4],
  Barcelona: [5],
};

const findTotalCost = (trip: Trip, budget: number): number => {


let res = -1;
    trip.Paris.forEach((a1) => {
        trip.Barcelona.forEach((a2) => {
            if(a1 + a2 <= budget) {
                res = a1 + a2;
            }
        });
    });

  return res;
};

console.log("findTotalCost trip1", findTotalCost(trips1, 10));
console.log("findTotalCost trip2", findTotalCost(trips2, 5));