I wanted to figure out how to divide a large number of things (such as
http://cgi.ebay.com/_W0QQitemZ170371530405 ) into several smaller groups
that could each be formed into a cube, and I had the bright idea that this
would be suited to a recursive program. So I whipped up this script. Its
syntax is like so:
/tmp/ball-recurse 1728 8
# objects --^ ^-- parts
and it finds the first hit (8 cubes of side 6) in about 3.5s and all 13
possibilities in 17-18s. The results come out sorted and uniq-ed
automatically. Let me know where I have some inefficiency, please. I'm
eyeing that "if" structure on lines 18-23 suspiciously, but I don't
immediately see a problem. Is there a way to invoke sh quicker?
1 #! /bin/sh
2 balls=$1
3 parts=$2
4 parts_so_far=$3
5
6 if [ "z$parts_so_far" = z ] ; then # if parts_so_far is empty,
7 upper_bound=$balls # Way too big, but it'll do.
8 else
9 upper_bound=${parts_so_far##*\ } # last number in the list
10 fi
11
12 try_cubesize=1
13 while : ; do
14 balls_left=$((balls - try_cubesize * try_cubesize * try_cubesize))
15 if [ $balls_left -lt 0 -o $parts -lt 1 -o $try_cubesize -gt $upper_bound ] ; then
16 exit
17 fi
18 if [ $balls_left -eq 0 -a $parts -eq 1 ] ; then # balls=0 && parts=1
19 echo "${parts_so_far#\ } $try_cubesize"
20 exit
21 else
22 "$0" $balls_left $((parts - 1)) "$parts_so_far $try_cubesize"
23 fi
24 try_cubesize=$(( try_cubesize + 1 ))
25 done
-- -eben QebWenE01R@vTerYizUonI.nOetP royalty.mine.nu:81He who will not reason is a bigot; he who cannot is a fool; and he who dares not is a slave. -Sir William Drummond ----------------------------------------------------------------------- This list is provided as an unmoderated internet service by Networked Knowledge Systems (NKS). Views and opinions expressed in messages posted are those of the author and do not necessarily reflect the official policy or position of NKS or any of its employees.
This archive was generated by hypermail 2.1.3 : Fri Aug 01 2014 - 13:47:05 EDT