Price list behind API: Difference between revisions
SqrtNegInf (talk | contribs) m (→{{header|Perl}}: oops) |
m (→{{header|Phix}}: added syntax colouring the hard way) |
||
Line 288: | Line 288: | ||
Note that defaulted arguments of the form mx=get_max_price() are not currently supported, hence a slightly hacky workaround, of -1 then -1==>get_max_price().<br> |
Note that defaulted arguments of the form mx=get_max_price() are not currently supported, hence a slightly hacky workaround, of -1 then -1==>get_max_price().<br> |
||
Were you (or I) to define constant mp = get_max_price(), then mx=mp style parameter defaulting would be fine. |
Were you (or I) to define constant mp = get_max_price(), then mx=mp style parameter defaulting would be fine. |
||
<lang Phix> |
<!--<lang Phix>(phixonline)--> |
||
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span> |
|||
constant price_list_size = 99_000 + rand(2_001) - 1, |
|||
<span style="color: #7060A8;">requires</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"0.8.3"</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- [assert() now accepts a 3rd param]</span> |
|||
price_list = sq_sub(sq_rand(repeat(100_000,price_list_size)),1), |
|||
<span style="color: #008080;">constant</span> <span style="color: #000000;">price_list_size</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">99_000</span> <span style="color: #0000FF;">+</span> <span style="color: #7060A8;">rand</span><span style="color: #0000FF;">(</span><span style="color: #000000;">2_001</span><span style="color: #0000FF;">)</span> <span style="color: #0000FF;">-</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> |
|||
delta_price = 1 -- Minimum difference between any two different prices. |
|||
<span style="color: #000000;">price_list</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">sq_sub</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">sq_rand</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">100_000</span><span style="color: #0000FF;">,</span><span style="color: #000000;">price_list_size</span><span style="color: #0000FF;">)),</span><span style="color: #000000;">1</span><span style="color: #0000FF;">),</span> |
|||
<span style="color: #000000;">delta_price</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span> <span style="color: #000080;font-style:italic;">-- Minimum difference between any two different prices.</span> |
|||
function get_prange_count(integer startp, endp) |
|||
return length(filter(price_list,"in",{startp,endp},"[]")) |
|||
<span style="color: #008080;">function</span> <span style="color: #000000;">get_prange_count</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">startp</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">endp</span><span style="color: #0000FF;">)</span> |
|||
end function |
|||
<span style="color: #008080;">return</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">filter</span><span style="color: #0000FF;">(</span><span style="color: #000000;">price_list</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"in"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">startp</span><span style="color: #0000FF;">,</span><span style="color: #000000;">endp</span><span style="color: #0000FF;">},</span><span style="color: #008000;">"[]"</span><span style="color: #0000FF;">))</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span> |
|||
function get_max_price() |
|||
return max(price_list) |
|||
<span style="color: #008080;">function</span> <span style="color: #000000;">get_max_price</span><span style="color: #0000FF;">()</span> |
|||
end function |
|||
<span style="color: #008080;">return</span> <span style="color: #7060A8;">max</span><span style="color: #0000FF;">(</span><span style="color: #000000;">price_list</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span> |
|||
function get_5k(integer mn=0, mx=-1, num=5_000) |
|||
if mx=-1 then mx = get_max_price() end if |
|||
<span style="color: #008080;">function</span> <span style="color: #000000;">get_5k</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">mn</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">mx</span><span style="color: #0000FF;">=-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">num</span><span style="color: #0000FF;">=</span><span style="color: #000000;">5_000</span><span style="color: #0000FF;">)</span> |
|||
⚫ | |||
<span style="color: #008080;">if</span> <span style="color: #000000;">mx</span><span style="color: #0000FF;">=-</span><span style="color: #000000;">1</span> <span style="color: #008080;">then</span> <span style="color: #000000;">mx</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">get_max_price</span><span style="color: #0000FF;">()</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
integer count = get_prange_count(mn, mx) |
|||
⚫ | |||
atom delta_mx = (mx - mn) / 2 |
|||
<span style="color: #004080;">integer</span> <span style="color: #000000;">count</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">get_prange_count</span><span style="color: #0000FF;">(</span><span style="color: #000000;">mn</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">mx</span><span style="color: #0000FF;">)</span> |
|||
while count != num and delta_mx >= delta_price / 2 do |
|||
<span style="color: #004080;">atom</span> <span style="color: #000000;">delta_mx</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">(</span><span style="color: #000000;">mx</span> <span style="color: #0000FF;">-</span> <span style="color: #000000;">mn</span><span style="color: #0000FF;">)</span> <span style="color: #0000FF;">/</span> <span style="color: #000000;">2</span> |
|||
mx = floor(mx + iff(count > num ? -delta_mx : +delta_mx)) |
|||
<span style="color: #008080;">while</span> <span style="color: #000000;">count</span> <span style="color: #0000FF;">!=</span> <span style="color: #000000;">num</span> <span style="color: #008080;">and</span> <span style="color: #000000;">delta_mx</span> <span style="color: #0000FF;">>=</span> <span style="color: #000000;">delta_price</span> <span style="color: #0000FF;">/</span> <span style="color: #000000;">2</span> <span style="color: #008080;">do</span> |
|||
{count, delta_mx} = {get_prange_count(mn, mx), delta_mx / 2} |
|||
<span style="color: #000000;">mx</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">floor</span><span style="color: #0000FF;">(</span><span style="color: #000000;">mx</span> <span style="color: #0000FF;">+</span> <span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #000000;">count</span> <span style="color: #0000FF;">></span> <span style="color: #000000;">num</span> <span style="color: #0000FF;">?</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">delta_mx</span> <span style="color: #0000FF;">:</span> <span style="color: #0000FF;">+</span><span style="color: #000000;">delta_mx</span><span style="color: #0000FF;">))</span> |
|||
end while |
|||
<span style="color: #0000FF;">{</span><span style="color: #000000;">count</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">delta_mx</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">get_prange_count</span><span style="color: #0000FF;">(</span><span style="color: #000000;">mn</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">mx</span><span style="color: #0000FF;">),</span> <span style="color: #000000;">delta_mx</span> <span style="color: #0000FF;">/</span> <span style="color: #000000;">2</span><span style="color: #0000FF;">}</span> |
|||
return {mx, count} |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span> |
|||
end function |
|||
<span style="color: #008080;">return</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">mx</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">count</span><span style="color: #0000FF;">}</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span> |
|||
function get_all_5k(integer mn=0, mx=-1, num=5_000) |
|||
if mx=-1 then mx = get_max_price() end if |
|||
<span style="color: #008080;">function</span> <span style="color: #000000;">get_all_5k</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">mn</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">mx</span><span style="color: #0000FF;">=-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">num</span><span style="color: #0000FF;">=</span><span style="color: #000000;">5_000</span><span style="color: #0000FF;">)</span> |
|||
-- Get all non-overlapping ranges |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">mx</span><span style="color: #0000FF;">=-</span><span style="color: #000000;">1</span> <span style="color: #008080;">then</span> <span style="color: #000000;">mx</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">get_max_price</span><span style="color: #0000FF;">()</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
integer {partmax, partcount} = get_5k(mn, mx, num) |
|||
<span style="color: #000080;font-style:italic;">-- Get all non-overlapping ranges</span> |
|||
sequence result = {{mn, partmax, partcount}} |
|||
<span style="color: #004080;">integer</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">partmax</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">partcount</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">get_5k</span><span style="color: #0000FF;">(</span><span style="color: #000000;">mn</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">mx</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">num</span><span style="color: #0000FF;">)</span> |
|||
while partmax < mx do |
|||
<span style="color: #004080;">sequence</span> <span style="color: #000000;">result</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{{</span><span style="color: #000000;">mn</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">partmax</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">partcount</span><span style="color: #0000FF;">}}</span> |
|||
integer partmin = partmax + delta_price |
|||
<span style="color: #008080;">while</span> <span style="color: #000000;">partmax</span> <span style="color: #0000FF;"><</span> <span style="color: #000000;">mx</span> <span style="color: #008080;">do</span> |
|||
{partmax, partcount} = get_5k(partmin, mx, num) |
|||
<span style="color: #004080;">integer</span> <span style="color: #000000;">partmin</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">partmax</span> <span style="color: #0000FF;">+</span> <span style="color: #000000;">delta_price</span> |
|||
assert(partcount>0,"Price list from %.2f has too many same price",{partmin}) |
|||
<span style="color: #0000FF;">{</span><span style="color: #000000;">partmax</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">partcount</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">get_5k</span><span style="color: #0000FF;">(</span><span style="color: #000000;">partmin</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">mx</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">num</span><span style="color: #0000FF;">)</span> |
|||
result = append(result,{partmin, partmax, partcount}) |
|||
<span style="color: #7060A8;">assert</span><span style="color: #0000FF;">(</span><span style="color: #000000;">partcount</span><span style="color: #0000FF;">></span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"Price list from %.2f has too many same price"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">partmin</span><span style="color: #0000FF;">})</span> |
|||
end while |
|||
<span style="color: #000000;">result</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">result</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">partmin</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">partmax</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">partcount</span><span style="color: #0000FF;">})</span> |
|||
return result |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span> |
|||
end function |
|||
<span style="color: #008080;">return</span> <span style="color: #000000;">result</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span> |
|||
printf(1,"Using %d random prices from 0 to %d\n",{price_list_size,get_max_price()}) |
|||
sequence result = get_all_5k() |
|||
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"Using %d random prices from 0 to %d\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">price_list_size</span><span style="color: #0000FF;">,</span><span style="color: #000000;">get_max_price</span><span style="color: #0000FF;">()})</span> |
|||
printf(1,"Splits into %d bins of approx 5000 elements\n",{length(result)}) |
|||
<span style="color: #004080;">sequence</span> <span style="color: #000000;">result</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">get_all_5k</span><span style="color: #0000FF;">()</span> |
|||
for i=1 to length(result) do |
|||
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"Splits into %d bins of approx 5000 elements\n"</span><span style="color: #0000FF;">,{</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">result</span><span style="color: #0000FF;">)})</span> |
|||
printf(1," From %8.2f ... %8.2f with %d items.\n",result[i]) |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">result</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span> |
|||
end for |
|||
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">" From %8.2f ... %8.2f with %d items.\n"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">result</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">])</span> |
|||
assert(length(price_list)==sum(vslice(result,3)),"Whoops! Some items missing!")</lang> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
<span style="color: #7060A8;">assert</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">price_list</span><span style="color: #0000FF;">)==</span><span style="color: #7060A8;">sum</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">vslice</span><span style="color: #0000FF;">(</span><span style="color: #000000;">result</span><span style="color: #0000FF;">,</span><span style="color: #000000;">3</span><span style="color: #0000FF;">)),</span><span style="color: #008000;">"Whoops! Some items missing!"</span><span style="color: #0000FF;">)</span> |
|||
<!--</lang>--> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
Revision as of 19:32, 6 June 2021
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
- Write functions to randomly generate around 100K prices and provide the
get_prange_count
andget_max_price
API calls. - 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.
- Ensure that all priced items are covered by all the ranges of prices shown
- Show ascending price ranges and the number of items covered by each range.
- Show output from a sample run here.
Go
<lang go>package main
import (
"fmt" "log" "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) if pcount == 0 { log.Fatal("Price list from", pmin, "has too many with same price.") } 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
Julia
<lang julia># Sample price generation const price_list_size = rand(99000:100999) const price_list = rand(0:99999, price_list_size) const delta_price = 1 # Minimum difference between any two different prices.
""" The API provides these two """ get_prange_count(startp, endp) = sum([startp <= r <= endp for r in price_list]) get_max_price() = maximum(price_list)
""" Binary search for num items between mn and mx, adjusting mx """ function get_5k(mn=0, mx=get_max_price(), num=5_000)
count = get_prange_count(mn, mx) delta_mx = (mx - mn) / 2 while count != num && delta_mx >= delta_price / 2 mx += (count > num ? -delta_mx : +delta_mx) mx = floor(mx) count, delta_mx = get_prange_count(mn, mx), delta_mx / 2 end return mx, count
end
""" Get all non-overlapping ranges """ function get_all_5k(mn=0, mx=get_max_price(), num=5_000)
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) @assert(partcount > 0, "pricelist from $partmin has too many same price") push!(result, (partmin, partmax, partcount)) end return result
end
function testpricelist()
println("Using $price_list_size random prices from 0 to $(get_max_price()).") result = get_all_5k() println("Splits into $(length(result)) bins of approximately 5000 elements.") for (mn, mx, count) in result println(" From $(Float32(mn)) ... $(Float32(mx)) with $count items.") end if length(price_list) != sum([x[3] for x in result]) print("\nWhoops! Some items missing.") end
end
testpricelist()
</lang>
- Output:
Using 100299 random prices from 0 to 99990. Splits into 21 bins of approximately 5000 elements. From 0.0 ... 4911.0 with 4998 items. From 4912.0 ... 9832.0 with 5000 items. From 9833.0 ... 14841.0 with 5000 items. From 14842.0 ... 19756.0 with 4999 items. From 19757.0 ... 24782.0 with 4994 items. From 24783.0 ... 29751.0 with 4999 items. From 29752.0 ... 34655.0 with 5000 items. From 34656.0 ... 39748.0 with 5000 items. From 39749.0 ... 44819.0 with 4999 items. From 44820.0 ... 49908.0 with 5000 items. From 49909.0 ... 54898.0 with 4999 items. From 54899.0 ... 59700.0 with 4999 items. From 59701.0 ... 64767.0 with 4999 items. From 64768.0 ... 69824.0 with 4999 items. From 69825.0 ... 74765.0 with 4999 items. From 74766.0 ... 79654.0 with 4999 items. From 79655.0 ... 84674.0 with 5000 items. From 84675.0 ... 89602.0 with 4999 items. From 89603.0 ... 94715.0 with 5000 items. From 94716.0 ... 99666.0 with 4997 items. From 99667.0 ... 100309.0 with 320 items.
Perl
<lang perl>use strict; use warnings; use List::Util <min max shuffle>;
sub getPRangeCount {
my($min,$max,@prices) = @_; grep { $min <= $_ <= $max } @prices;
}
sub get5000 {
my($min, $max, $n, @prices) = @_; my $count = getPRangeCount($min, $max, @prices); my $delta = ($max - $min) / 2; while ($count != $n and $delta >= 1/2) { $count > $n ? $max -= $delta : ($max += $delta); $count = getPRangeCount($min, $max, @prices); $delta /= 2; } $max, $count
}
sub getAll5000 {
my($min, $max, $n, @prices) = @_; my ( $pmax, $pcount ) = get5000($min, $max, $n, @prices); my @results = [ $min, $pmax, $pcount ]; while ($pmax < $max) { my $pmin = $pmax + 1; ( $pmax, $pcount ) = get5000($pmin, $max, $n, @prices); $pcount == 0 and print "Price list from $pmin has too many duplicates.\n"; push @results, [ $pmin, $pmax, $pcount ]; } @results
}
my @prices; push @prices, int rand 10_000+1 for 1 .. (my $numPrices = shuffle 99_990..100_050);
my $actualMax = max @prices; print "Using $numPrices items with prices from 0 to $actualMax:\n";
my @results = getAll5000(0, $actualMax, 5000, @prices); print "Split into " . @results . " bins of approx 5000 elements:\n";
for my $row (@results) {
my ($min,$max,$subtotal) = @$row; $max = $actualMax if $max > $actualMax; printf " From %6d to %6d with %4d items\n", $min, $max, $subtotal
}</lang>
- Output:
Using 100047 items with prices from 0 to 10000: Split into 20 bins of approx 5000 elements: From 0 to 496 with 5002 items From 497 to 991 with 4992 items From 992 to 1483 with 4996 items From 1484 to 1988 with 4998 items From 1989 to 2483 with 5002 items From 2484 to 2980 with 5009 items From 2981 to 3482 with 4996 items From 3483 to 3968 with 5000 items From 3969 to 4476 with 4998 items From 4477 to 4989 with 5009 items From 4990 to 5491 with 5005 items From 5492 to 5981 with 5005 items From 5982 to 6483 with 5002 items From 6484 to 6984 with 5005 items From 6985 to 7495 with 4992 items From 7496 to 8004 with 4991 items From 8005 to 8496 with 5000 items From 8497 to 9002 with 5000 items From 9003 to 9514 with 4995 items From 9515 to 10000 with 4850 items
Phix
Note that defaulted arguments of the form mx=get_max_price() are not currently supported, hence a slightly hacky workaround, of -1 then -1==>get_max_price().
Were you (or I) to define constant mp = get_max_price(), then mx=mp style parameter defaulting would be fine.
with javascript_semantics requires("0.8.3") -- [assert() now accepts a 3rd param] 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 = {{mn, partmax, partcount}} while partmax < mx do integer partmin = partmax + delta_price {partmax, partcount} = get_5k(partmin, mx, num) assert(partcount>0,"Price list from %.2f has too many same price",{partmin}) 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.2f ... %8.2f with %d items.\n",result[i]) end for assert(length(price_list)==sum(vslice(result,3)),"Whoops! Some items missing!")
- Output:
Using 100957 random prices from 0 to 99999 Splits into 21 bins of approx 5000 elements From 0.00 ... 4838.00 with 4998 items. From 4839.00 ... 9765.00 with 4999 items. From 9766.00 ... 14602.00 with 4999 items. From 14603.00 ... 19575.00 with 5000 items. From 19576.00 ... 24515.00 with 4998 items. From 24516.00 ... 29476.00 with 5000 items. From 29477.00 ... 34386.00 with 5000 items. From 34387.00 ... 39289.00 with 4999 items. From 39290.00 ... 44349.00 with 5000 items. From 44350.00 ... 49265.00 with 4992 items. From 49266.00 ... 54262.00 with 4998 items. From 54263.00 ... 59289.00 with 4999 items. From 59290.00 ... 64191.00 with 5000 items. From 64192.00 ... 69119.00 with 4999 items. From 69120.00 ... 74095.00 with 4996 items. From 74096.00 ... 79144.00 with 4999 items. From 79145.00 ... 84093.00 with 4998 items. From 84094.00 ... 88961.00 with 4996 items. From 88962.00 ... 94051.00 with 4999 items. From 94052.00 ... 99038.00 with 5000 items. From 99039.00 ... 100955.00 with 988 items.
Python
<lang python>import random
- %%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.
- %% 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)
- %% 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) assert partcount > 0, \ f"price_list from {partmin} with too many of the same price" 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.
Raku
<lang perl6># 20210208 Raku programming solution
my \minDelta = 1;
sub getMaxPrice { @_.max }
sub getPRangeCount(@prices,\min,\max) { +@prices.grep: min ≤ * ≤ max }
sub get5000(@prices, $min, $max is copy, \n) {
my $count = getPRangeCount(@prices, $min, $max); my $delta = ($max - $min) / 2; while $count != n && $delta ≥ minDelta/2 { $count > n ?? ($max -= $delta) !! ($max += $delta); $count = getPRangeCount(@prices, $min, $max); $delta /= 2; } $max, $count
}
sub getAll5000(@prices, \min, \max, \n) {
my ( $pmax, $pcount ) = get5000(@prices, min, max, n); my @res = [ min, $pmax, $pcount ] , ; while $pmax < max { my $pmin = $pmax + 1; ( $pmax, $pcount ) = get5000(@prices, $pmin, max, n); $pcount == 0 and note "Price list from $pmin has too many duplicates."; @res.push: [ $pmin, $pmax, $pcount ]; } @res
}
my $numPrices = (99000..101001).roll; my \maxPrice = 1e5; my @prices = (1..$numPrices+1).roll xx $numPrices ;
my $actualMax = getMaxPrice(@prices); say "Using $numPrices items with prices from 0 to $actualMax:";
my @res = getAll5000(@prices, 0, $actualMax, 5000); say "Split into ", +@res, " bins of approx 5000 elements:";
for @res -> @row {
my ($min,$max,$subtotal) = @row; $max = $actualMax if $max > $actualMax ; printf " From %6d to %6d with %4d items\n", $min, $max, $subtotal
} </lang>
- Output:
Using 99506 items with prices from 0 to 99507: Split into 20 bins of approx 5000 elements: From 0 to 4983 with 5000 items From 4984 to 10034 with 5003 items From 10035 to 15043 with 4998 items From 15044 to 20043 with 5001 items From 20044 to 24987 with 5001 items From 24988 to 30000 with 4998 items From 30001 to 34954 with 5000 items From 34955 to 40018 with 5000 items From 40019 to 45016 with 5000 items From 45017 to 49950 with 5000 items From 49951 to 54877 with 4999 items From 54878 to 59880 with 5002 items From 59881 to 64807 with 5001 items From 64808 to 69800 with 5000 items From 69801 to 74897 with 5000 items From 74898 to 79956 with 5002 items From 79957 to 85037 with 5000 items From 85038 to 90118 with 5001 items From 90119 to 95169 with 5001 items From 95170 to 99507 with 4470 items
Wren
<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] if (pcount == 0) Fiber.abort("Price list from %(pmin) has too many with same price.") 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