Price list behind API

Price list behind API is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

There is a list of around 100_000 prices in the range £0 to £100_000, expressed in whole £, (no pence); and prices may be duplicated.
The API allows access to the maximum item price via function get_max_price(); and the number of items equal-to and between two given price points via function get_prange_count(pricemin, pricemax).
Assume that for the purposes of testing, you have access to the actual number of priced items to split.

Task

1. Write functions to randomly generate around 100K prices and provide the get_prange_count and get_max_price API calls.
2. Write functions to provide non-overlapping min and max price ranges that provide product counts where most are close to, but no more than, 5_000.
3. Ensure that all priced items are covered by all the ranges of prices shown
4. Show ascending price ranges and the number of items covered by each range.
5. Show output from a sample run here.

Go

Translation of: Wren

<lang go>package main

import (

   "fmt"
   "math"
   "math/rand"
   "time"

)

var minDelta = 1.0

func getMaxPrice(prices []float64) float64 {

   max := prices[0]
   for i := 1; i < len(prices); i++ {
       if prices[i] > max {
           max = prices[i]
       }
   }
   return max

}

func getPRangeCount(prices []float64, min, max float64) int {

   count := 0
   for _, price := range prices {
       if price >= min && price <= max {
           count++
       }
   }
   return count

}

func get5000(prices []float64, min, max float64, n int) (float64, int) {

   count := getPRangeCount(prices, min, max)
   delta := (max - min) / 2
   for count != n && delta >= minDelta/2 {
       if count > n {
           max -= delta
       } else {
           max += delta
       }
       max = math.Floor(max)
       count = getPRangeCount(prices, min, max)
       delta /= 2
   }
   return max, count

}

func getAll5000(prices []float64, min, max float64, n int) [][3]float64 {

   pmax, pcount := get5000(prices, min, max, n)
   res := [][3]float64Template:Min, pmax, float64(pcount)
   for pmax < max {
       pmin := pmax + 1
       pmax, pcount = get5000(prices, pmin, max, n)
       res = append(res, [3]float64{pmin, pmax, float64(pcount)})
   }
   return res

}

func main() {

   rand.Seed(time.Now().UnixNano())
   numPrices := 99000 + rand.Intn(2001)
   maxPrice := 1e5
   prices := make([]float64, numPrices) // list of prices
   for i := 0; i < numPrices; i++ {
       prices[i] = float64(rand.Intn(int(maxPrice) + 1))
   }
   actualMax := getMaxPrice(prices)
   fmt.Println("Using", numPrices, "items with prices from 0 to", actualMax, "\b:")
   res := getAll5000(prices, 0, actualMax, 5000)
   fmt.Println("Split into", len(res), "bins of approx 5000 elements:")
   total := 0
   for _, r := range res {
       min := int(r[0])
       tmx := r[1]
       if tmx > actualMax {
           tmx = actualMax
       }
       max := int(tmx)
       cnt := int(r[2])
       total += cnt
       fmt.Printf("   From %6d to %6d with %4d items\n", min, max, cnt)
   }
   if total != numPrices {
       fmt.Println("Something went wrong - grand total of", total, "doesn't equal", numPrices, "\b!")
   }

}</lang>

Output:

Using 99784 items with prices from 0 to 99999 :
Split into 20 bins of approx 5000 elements:
   From      0 to   5061 with 4997 items
   From   5062 to  10031 with 5000 items
   From  10032 to  15091 with 5000 items
   From  15092 to  20114 with 5000 items
   From  20115 to  25141 with 5000 items
   From  25142 to  30206 with 4997 items
   From  30207 to  35291 with 5000 items
   From  35292 to  40333 with 4999 items
   From  40334 to  45451 with 4999 items
   From  45452 to  50422 with 4998 items
   From  50423 to  55355 with 4997 items
   From  55356 to  60268 with 4997 items
   From  60269 to  65240 with 5000 items
   From  65241 to  70193 with 4999 items
   From  70194 to  75272 with 4998 items
   From  75273 to  80154 with 5000 items
   From  80155 to  85218 with 5000 items
   From  85219 to  90120 with 4996 items
   From  90121 to  95102 with 4998 items
   From  95103 to  99999 with 4809 items

Phix

Translation of: Python

Note that defaulted arguments of the form mx=get_max_price() are not currently supported, hence a slightly hacky workaround.
If you defined constant mp = get_max_price(), then mx=mp style parameter defaulting would be fine. <lang Phix>constant price_list_size = 99_000 + rand(2_001) - 1,

        price_list = sq_sub(sq_rand(repeat(100_000,price_list_size)),1),
        delta_price = 1 -- Minimum difference between any two different prices.

function get_prange_count(integer startp, endp)

   return length(filter(price_list,"in",{startp,endp},"[]"))

end function

function get_max_price()

   return max(price_list)

end function

function get_5k(integer mn=0, mx=-1, num=5_000)

   if mx=-1 then mx = get_max_price() end if
   -- Binary search for num items between mn and mx, adjusting mx
   integer count = get_prange_count(mn, mx)
   atom delta_mx = (mx - mn) / 2
   while count != num and delta_mx >= delta_price / 2 do
       mx = floor(mx + iff(count > num ? -delta_mx : +delta_mx))
       {count, delta_mx} = {get_prange_count(mn, mx), delta_mx / 2}
   end while
   return {mx, count}

end function

function get_all_5k(integer mn=0, mx=-1, num=5_000)

   if mx=-1 then mx = get_max_price() end if
   -- Get all non-overlapping ranges
   integer {partmax, partcount} = get_5k(mn, mx, num)
   sequence result = Template:Mn, partmax, partcount
   while partmax < mx do
       integer partmin = partmax + delta_price 
       {partmax, partcount} = get_5k(partmin, mx, num)
       result = append(result,{partmin, partmax, partcount})
   end while
   return result

end function

printf(1,"Using %d random prices from 0 to %d\n",{price_list_size,get_max_price()}) sequence result = get_all_5k() printf(1,"Splits into %d bins of approx 5000 elements\n",{length(result)}) for i=1 to length(result) do

   printf(1,"  From %8.1f ... %8.1f with %d items.\n",result[i])

end for if length(price_list) != sum(vslice(result,3)) then

   printf(1,"\nWhoops! Some items missing:\n")

end if</lang>

Output:

Using 99714 random prices from 0 to 99999
Splits into 20 bins of approx 5000 elements
  From      0.0 ...   4977.0 with 5000 items.
  From   4978.0 ...  10019.0 with 4999 items.
  From  10020.0 ...  15114.0 with 4999 items.
  From  15115.0 ...  19987.0 with 4998 items.
  From  19988.0 ...  25088.0 with 4996 items.
  From  25089.0 ...  30080.0 with 4995 items.
  From  30081.0 ...  35117.0 with 5000 items.
  From  35118.0 ...  40081.0 with 4999 items.
  From  40082.0 ...  45080.0 with 5000 items.
  From  45081.0 ...  50181.0 with 5000 items.
  From  50182.0 ...  55223.0 with 5000 items.
  From  55224.0 ...  60271.0 with 5000 items.
  From  60272.0 ...  65102.0 with 4999 items.
  From  65103.0 ...  70140.0 with 5000 items.
  From  70141.0 ...  75195.0 with 4997 items.
  From  75196.0 ...  80203.0 with 4998 items.
  From  80204.0 ...  85210.0 with 4999 items.
  From  85211.0 ...  90182.0 with 5000 items.
  From  90183.0 ...  95268.0 with 4999 items.
  From  95269.0 ... 104722.0 with 4736 items.

Python

<lang python>import random

1. %%Sample price generation

price_list_size = random.choice(range(99_000, 101_000)) price_list = random.choices(range(100_000), k=price_list_size)

delta_price = 1 # Minimum difference between any two different prices.

1. %% API

def get_prange_count(startp, endp):

   return len([r for r in price_list if startp <= r <= endp])

def get_max_price():

   return max(price_list)

1. %% Solution

def get_5k(mn=0, mx=get_max_price(), num=5_000):

   "Binary search for num items between mn and mx, adjusting mx"
   count = get_prange_count(mn, mx)
   delta_mx = (mx - mn) / 2
   while count != num and delta_mx >= delta_price / 2:
       mx += -delta_mx if count > num else +delta_mx
       mx = mx // 1    # Floor
       count, delta_mx = get_prange_count(mn, mx), delta_mx / 2
   return mx, count

def get_all_5k(mn=0, mx=get_max_price(), num=5_000):

   "Get all non-overlapping ranges"
   partmax, partcount = get_5k(mn, mx, num)
   result = [(mn, partmax, partcount)]
   while partmax < mx:
       partmin = partmax + delta_price 
       partmax, partcount = get_5k(partmin, mx, num)
       result.append((partmin, partmax, partcount))
   return result

if __name__ == '__main__':

   print(f"Using {price_list_size} random prices from 0 to {get_max_price()}")
   result = get_all_5k()
   print(f"Splits into {len(result)} bins of approx 5000 elements")
   for mn, mx, count in result:
       print(f"  From {mn:8.1f} ... {mx:8.1f} with {count} items.")

   if len(price_list) != sum(count for mn, mx, count in result):
       print("\nWhoops! Some items missing:")</lang>

Output:

Using 99838 random prices from 0 to 99999
Splits into 20 bins of approx 5000 elements
  From      0.0 ...   4876.0 with 4999 items.
  From   4877.0 ...   9973.0 with 4997 items.
  From   9974.0 ...  14954.0 with 4999 items.
  From  14955.0 ...  20041.0 with 4997 items.
  From  20042.0 ...  25132.0 with 4999 items.
  From  25133.0 ...  30221.0 with 5000 items.
  From  30222.0 ...  35313.0 with 5000 items.
  From  35314.0 ...  40263.0 with 5000 items.
  From  40264.0 ...  45249.0 with 4997 items.
  From  45250.0 ...  50264.0 with 5000 items.
  From  50265.0 ...  55251.0 with 5000 items.
  From  55252.0 ...  60301.0 with 4997 items.
  From  60302.0 ...  65239.0 with 5000 items.
  From  65240.0 ...  70220.0 with 4998 items.
  From  70221.0 ...  75193.0 with 4999 items.
  From  75194.0 ...  80229.0 with 4996 items.
  From  80230.0 ...  85191.0 with 4997 items.
  From  85192.0 ...  90214.0 with 5000 items.
  From  90215.0 ...  95249.0 with 4999 items.
  From  95250.0 ... 104742.0 with 4864 items.

Wren

Translation of: Python

Library: Wren-math

Library: Wren-fmt

<lang ecmascript>import "random" for Random import "/math" for Nums import "/fmt" for Fmt

var rand = Random.new() var minDelta = 1

var getMaxPrice = Fn.new { |prices| Nums.max(prices) }

var getPrangeCount = Fn.new { |prices, min, max| prices.count { |p| p >= min && p <= max } }

var get5000 = Fn.new { |prices, min, max, n|

   var count = getPrangeCount.call(prices, min, max)
   var delta = (max - min) / 2
   while (count != n && delta >= minDelta/2) {
       max = ((count > n) ? max-delta : max+delta).floor
       count = getPrangeCount.call(prices, min, max)
       delta = delta / 2
   }
   return [max, count]

}

var getAll5000 = Fn.new { |prices, min, max, n|

   var mc = get5000.call(prices, min, max, n)
   var pmax = mc[0]
   var pcount = mc[1]
   var res = min, pmax, pcount
   while (pmax < max) {
       var pmin = pmax + 1
       mc = get5000.call(prices, pmin, max, n)
       pmax = mc[0]
       pcount = mc[1]
       res.add([pmin, pmax, pcount])
   }
   return res

} var numPrices = rand.int(99000, 101001) var maxPrice = 1e5 var prices = List.filled(numPrices, 0) // list of prices for (i in 1..numPrices) prices[i-1] = rand.int(maxPrice + 1) var actualMax = getMaxPrice.call(prices) System.print("Using %(numPrices) items with prices from 0 to %(actualMax):") var res = getAll5000.call(prices, 0, actualMax, 5000) System.print("Split into %(res.count) bins of approx 5000 elements:") var total = 0 for (r in res) {

   var min = r[0]
   var max = r[1]
   if (max > actualMax) max = actualMax
   var cnt = r[2]
   total = total + cnt
   Fmt.print("   From $6d to $6d with $4d items", min, max, cnt)

} if (total != numPrices) {

   System.print("Something went wrong - grand total of %(total) doesn't equal %(numPrices)!")

}</lang>

Output:

Sample run:

Using 99756 items with prices from 0 to 99998:
Split into 20 bins of approx 5000 elements:
   From      0 to   4964 with 5000 items
   From   4965 to   9992 with 5000 items
   From   9993 to  15063 with 5000 items
   From  15064 to  20130 with 5000 items
   From  20131 to  25063 with 4998 items
   From  25064 to  30014 with 4998 items
   From  30015 to  35002 with 5000 items
   From  35003 to  40030 with 5000 items
   From  40031 to  45058 with 5000 items
   From  45059 to  50199 with 4999 items
   From  50200 to  55133 with 4999 items
   From  55134 to  60139 with 4997 items
   From  60140 to  65097 with 5000 items
   From  65098 to  69972 with 4999 items
   From  69973 to  74932 with 5000 items
   From  74933 to  80041 with 5000 items
   From  80042 to  85214 with 5000 items
   From  85215 to  90241 with 4999 items
   From  90242 to  95353 with 5000 items
   From  95354 to  99998 with 4767 items