On Sat, 10 Oct 2009, ronan wrote:
>> 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
> You could try making a "function" inside your script, and having that
> function call itself recursively. That way, you don't have the fork overhead.
Good idea. It appears, though, when a function (1) calls itself (2) in sh,
sh replaces (1) with (2). That seems silly and I'm not sure it's
happening but I can't see another bug. Should I try background + wait, or
is there a cleaner/faster way?
Here's the code as of now (the comments are mostly notes to myself but if
others benefit, great):
1 #! /bin/sh
2
3 divide () {
4 balls=$1
5 parts=$2
6 parts_so_far=$3
7 indent="$(echo "$parts_so_far" | sed 's/[^ ]//g')"
8 echo "$indent 1-start (balls=$balls parts=$parts size=$try_cubesize)"
9
10 if [ "z$parts_so_far" = z ] ; then # if parts_so_far is empty,
11 upper_bound=$balls # Way too big, but it'll do. It's guaranteed to be big enough.
12 else
13 upper_bound=${parts_so_far##*\ } # last number in the list
14 fi
15
16 try_cubesize=1 # If you want a minimum cube size, set it here.
17 while : ; do
18 echo "$indent 2-top of loop (balls=$balls parts=$parts size=$try_cubesize)"
19 balls_left=$((balls - try_cubesize * try_cubesize * try_cubesize))
20 [ $balls_left -lt 0 -o $try_cubesize -gt $upper_bound ] && break
21 echo "$indent 2.1-before if (balls=$balls parts=$parts size=$try_cubesize)"
22 if [ $parts -eq 1 ] ; then # parts=1
23 echo "$indent 2.1.1-before else (balls=$balls parts=$parts size=$try_cubesize)"
24 if [ $balls_left -eq 0 ] ; then # balls_left=0
25 echo "${parts_so_far#\ } $try_cubesize" # prints a "success"
26 break
27 fi
28 else # parts > 1, no idea what balls_left is
29 echo "$indent 2.1.2-after else (balls=$balls parts=$parts size=$try_cubesize)"
30 divide $balls_left $((parts - 1)) "$parts_so_far $try_cubesize" # divide the rest
31 # This prevents the child's "parts" from being <=0 (and everything's a child) --
32 # its "parts" comes from $((parts-1)) and here parts>1.
33 fi
34 echo "$indent 2.2-after if (balls=$balls parts=$parts size=$try_cubesize)"
35 try_cubesize=$(( try_cubesize + 1 )) # increment test cube size;
36 echo "$indent 3-bottom of loop (balls=$balls parts=$parts size=$try_cubesize)"
37 done
38 echo "$indent 4-end (balls=$balls parts=$parts size=$try_cubesize)"
39 }
40
41 #set -x
42 divide "$@"
43 echo exiting "$@"
and the output from "ball-recurse 1728 3 | grep parts=3":
1-start (balls=1728 parts=3 size=)
2-top of loop (balls=1728 parts=3 size=1)
2.1-before if (balls=1728 parts=3 size=1)
2.1.2-after else (balls=1728 parts=3 size=1)
and from "ball-recurse 1728 3":
1-start (balls=1728 parts=3 size=)
2-top of loop (balls=1728 parts=3 size=1)
2.1-before if (balls=1728 parts=3 size=1)
2.1.2-after else (balls=1728 parts=3 size=1)
1-start (balls=1727 parts=2 size=1)
2-top of loop (balls=1727 parts=2 size=1)
2.1-before if (balls=1727 parts=2 size=1)
2.1.2-after else (balls=1727 parts=2 size=1)
1-start (balls=1726 parts=1 size=1)
2-top of loop (balls=1726 parts=1 size=1)
2.1-before if (balls=1726 parts=1 size=1)
2.1.1-before else (balls=1726 parts=1 size=1)
2.2-after if (balls=1726 parts=1 size=1)
3-bottom of loop (balls=1726 parts=1 size=2)
2-top of loop (balls=1726 parts=1 size=2)
4-end (balls=1726 parts=1 size=2)
2.2-after if (balls=1726 parts=1 size=2)
3-bottom of loop (balls=1726 parts=1 size=3)
2-top of loop (balls=1726 parts=1 size=3)
4-end (balls=1726 parts=1 size=3)
2.2-after if (balls=1726 parts=1 size=3)
3-bottom of loop (balls=1726 parts=1 size=4)
2-top of loop (balls=1726 parts=1 size=4)
4-end (balls=1726 parts=1 size=4)
exiting 1728 3
--
-eben QebWenE01R@vTerYizUonI.nOetP royalty.mine.nu:81
If you need someone to blame
Throw a rock in the air
You'll hit someone guilty -- U2, _Zooropa_, "Dirty Day"
-----------------------------------------------------------------------
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:56 EDT