[Closed] Challenge! and Fun 🙂

Here is another version, a mix of heuristic and brute force.

As far as I could test it produces 100% perfect results.

finditem() and amax() are heavily reduced so the times are considerably faster than the brute force alone.

fn DistributePointsInShapes5 splines points:0 =
(
	fn SortBySegment a b = if a[4]>b[4] then -1 else if a[4]<b[4] then 1 else if a[3]>b[3] then -1 else if a[3]<b[3] then 1 else 0
	fn SortByLength a b = if b[3]<a[3] then -1 else if b[3]>a[3] then 1 else 0

	d = 0.0
	r = for j in splines collect
	(
		l = (curvelength j) as double
		d += l
		#(j, 0, l)
	)
	
	if points <= r.count do
	(
		qsort r SortByLength
		for j = 1 to points do r[j][2] = 1
		return r
	)
	
	avg = d / points
	missed = points
	for j in r do
	(
		if (j[3] / avg) < 1 do
		(
			d -= j[3]
			points -= 1
		)
	)
	
	avg = d / points
	for j in r do
	(
		j[2] = amax 1 (int (j[3] / avg))
		j[4] = j[3] / (j[2]+1)
		missed -= j[2]
	)
	
	qsort r SortBySegment

	l = for j = 1 to missed collect r[j][4]

	for j = 1 to missed do
	(
		idx = finditem l (amax l)
		r[idx][2] += 1
		l[idx] = r[idx][3] / (r[idx][2]+1)
	)
	return r
)

beads:10000000 >> threads:10000 >> time:472ms heap:3375880L

Why not? If we ever find a solution for this.
Although we have 2 working approaches, this is still unsolved for me.

I would think someone must have done some work in this area, but I could not find any literature. Perhaps not specific for splines, but it would be the same for areas or buckets and balls.