Updated 2017-01-16 18:23:42 by gold

## Introduction edit

gold Here is some eTCL starter code for packing pennies in a rectangular surface area. The impetus for these calculations was round barrels in a rectangular storage area like a ship deck or storage room. This area of mathematics is called circle packing. Most of the testcases involve replicas or models, using assumptions and rules of thumb.

For a rectangle, the maximum packing of pennies is considered to be alternate rows of N and N-1 pennies, where N > 5 and N= even. The diameter of a USA penny is 1.905 centimeters. The USA zinc penny is 0.155 cm and weighs 2.5 grams. Since the diameter of pennies and other coins differ as well as rectangles, we will try to make the algorithm as generic as possible.

In planning any software, it is advisable to gather a number of testcases to check the results of the program. For testcases, the following is recommended. Get three 50-rolls of clean mint pennies, a metric ruler, and clean typing paper. Mark perpendicular lines on the left and bottom of the typing paper. An old textbook usually gives as good a penciled perpendicular line as a drafting triangle. Lay pennies out touching the penciled lines and each other. Mark out a square of N pennies.

A square of [* 6 6] or 36 pennies will do for a start, meaning 6 rows of 6 pennies. Use a ruler to herd the pennies to overlay the former penciled lines and mark out the boundaries for the top and right side of the square. Pin the ruler rigidly on the paper and mark the remaining sides. Some pennies may have to be knocked out of the pencil track to get a true line. Measure all four sides with the ruler and average the sides. For example, my four sides averaged [/ [+ 11.4 11.3 11.5 11.3] 4.] or 11.375 cm.

For the first testcase, there should be N*N, 6*6, or 36 pennies in the square field marked by the pencil. In the field measured by the pencil marks, set out alternating rows of 6/5/6/5/6/5/6 pennies touching each other, with the outer rows of 6 in a line touching the pencil lines. 4 rows of 6 pennies and 3 rows of 5 pennies should total [+ [* 4 6 ] [* 3 5 ]] or 39 pennies. Alternating rows allowed [- 39 [* 6 6]] or three extra pennies in the old 6*6 space. The eTCL calculator returns 4 rows of N (6) and 3 rows of N-1 (5), also returning total 39 coins. While the algorithm is not perfectly certain at this point, this testcase seems agree that 3 extra coins can be packed into the old 6*6 (coin diameter) space.

The second testcase was N*N, 8*8, or 64 pennies in a square. Set up by 64 pennies, the four sides averaged [/ [+ 15.3 15.3 15.3 15.1] 4.] or 15.25 cm. After laying out the alternating coin rows on the old 8*8 square, there were 5 rows of 8 and 4 rows of 7 giving [+ [* 5 8 ] [* 4 7 ]] or 68 coins. The alternating rows gave [- [+ [* 5 8 ] [* 4 7 ]] [* 8 8]] or 4 more coins. The eTCL calculator returns 5 rows of N (8) and 4 rows of N-1(7), giving total coins as 68.

The third testcase was N*N, 10*10, or 100 pennies in a square. Laying 10 touching coins on each of four sides averaged [/ [+ 19.3 19.2 19.4 19.2] 4.] or 19.275 cm. For the alternate rows, an estimate was tried. A first layer of 10 coins and a second layer of 9 coins had a width of 19.3 and a height of 3.6 cm. There appears room for 5 layers of 19 coins (2 alternating rows) and a top layer of 10 coins. The total estimate would be [+ [* 5 19] 10] or 105 coins. The eTCL calculator returns 6 rows of N (10) and 4 rows of N-1(9), giving total coins as 105. From the eTCL calculator, the alternating rows gave [- 105 100] or 5 extra coins over the old 10*10 square.

The fourth testcase was N1*N2, 6*12, or 72 pennies in a rectangle. On the two perpendicular lines, lay 6 touching coins on the left side and 12 touching coins for bottom. Mark the end coins from 6 pennies high and 12 pennies wide on the perpendicular lines as definding the sides of a rectangle. As an estimate, there would be 6*12 or 72 pennies in the completed rectangle of nonoverlapping rows. For a rectangle of alternating pennies, leave the 12 pennies marking the first row and fill the marked figure as 12/11/12/11/12/11/12 rows. There appears room for 4 layers of 12 coins and 3 layers of 11 coins. The total estimate for alternating rows would be [+ [* 4 12] [* 3 11]] or 81 coins. Internally for the report, the eTCL calculator calculates 4 rows of N (12) and 3 rows of N-1(11), giving total coins as 81. From the eTCL calculator, the optimized alternating rows gave [- 81 72] or 9 extra coins over the old 6*12 rectangle of nonoverlapping rows.

An experiment was tried for placing pennies in a equilateral triangle with sides of 20 cm and a height of 17.32 cm. The eTCL calculator and its algorithm was based on pennies in squares and rectangles, but one wanted to see how triangles could be handled in an additional subroutine for the eTCL calculator. Draw a line of 23 cm at the bottom of the typing paper and measure points at 0,10, and 20 cm. At the 10 cm mark on the original line, use an old textbook to draw a perpendicular for about 18 cm. The points at 0, 20, and the vertical line (at ~17.32 cm ) define an equilateral triangle. For a triangle of alternating rows, leave the [int [/ 20 1.905]] or 10 pennies marking the first row at the base of the triangle and fill the marked figure in alternating rows. The total estimate for alternating rows was [+ 10 9 8 7 6 5 4 3 2 1], [* 10 [+ 10 1] .5 ] , or 55 coins, but 55 coins slightly overshoot the right side of the triangle.

In generic terms, filling an equilateral triangle would require estimating coins for the base side as N1= [int [/ side coin_width]] and with overlapping rows, each successive layer would be N2=N1-1. As an interim step for triangles, we could mooch the subroutine proc sumitup n {[*\$n[+\$n1].5]} for adding positive integers to N1, from the One Liners page. Then load a subroutine for an equilateral triangle into the eTCL as a reportable function of \$side1 in the eTCL report, accessible in the eTCL console. Possibly, \$side2 could be used as a truncation height for the equilateral triangle.

An experiment was tried for placing pennies in a circle with a diameter of 15.8 cm. The eTCL calculator and its algorithm was based on pennies in squares and rectangles, but one wanted to see how circles could be handled in an additional subroutine for the eTCL calculator. Draw a line of 23 cm at the bottom of the typing paper and measure points at 0,10, and 20 cm. At the 10 cm mark on the original line, use an old textbook to draw a perpendicular for about 18 cm. Circle a turned down cereal bowl with tangent point at 10 cm on the bottom line and use the vertical line as the centerline of the circle. The maximum number of pennies that can placed on the centerline inside the circle is [int [/ 15.8 1.905]] or 8 pennies marking the first row. Try to place the pennies as alternating to the first row, but probably many pennies will not fit at the edges of the circle. In the first try, 53 pennies were placed inside the 15.8 cm circle. In the second try, 52 pennies were placed inside the 15.8 cm circle.

For coins inside each geometric figure, each coin borrows or wastes some fraction of area from the overall total area. Overlapping coins waste less space, but the waste fraction is still there with each coin. An circle inside a square enabled one to estimate the possible waste with each individual circle. In generic form, the waste for the inscribed circle would be area of square minus area of the circle. The side of the square is the diameter of the circle and area of the square would be [* \$diameter \$diameter]. For the area of the circle, the calculator uses [/ [* [pi] \$diameter \$diameter] 4]. For non-overlapping coins in the concept figures below, the loss per coin was about [* \$faction(1) [- [* \$diameter \$diameter] [/ [* [ pi ] \$diameter \$diameter ] 4. ]] for coins in a square. For mostly overlapping coins in a circle, the eTCL calculator has an approximate function using the length as circle diameter and \$fraction(0.75). For a subroutine on the measured circle in the testcase, the waste area would be area of circle minus the area of the coin times N1, number of coins.

The interior space between touching coins produce geometric figures. Non-alternating layers of touching coins create four pointed stars called concave squares. Alternating layers of touching coins produce three pointed stars called concave triangles. The clay tablets, charts, palace decorations, and coefficient lists show the Babylonian mathematicians were studying concave squares and triangles. In some instances, the Babylonians were computing the remaining area from touching circles within squares. In some measure, the interior spaces between touching coins is a waste of space and it might be conjectured that a concave triangle has less wasted space than a concave square.

The eTCL penny packing calculator was exercised over the expected range of use, 5>N<18 and N=even. The total coins for the optimised square or rectangle is shown in the calculator window. The coins for the nonoverlapping squares and rectangles are calculated and included in the report. First, the internal calulations estimate the alternating rows for an optimised square of the entered length (\$side1). Second, then the number of alternating rows from \$side1 are used the calculate the fill of an optimised rectangle. For now, use the longest dimension of the rectangle as the width.

### Pseudocode Section

```    pseudocode can be developed from rules of thumb.
pseudocode: enter rectangle length , width , penny or coin diameter
pseudocode: output rows of N and N-1 coins, total number of coins
pseudocode: rules of thumb can be 3 to 15 percent off, partly since g..in g..out.
pseudocode: packing pennies in square.
pseudocode: base of square 6 pennies wide.
pseudocode: height of square 6 pennies tall
pseudocode: pennies will be paced in layers equal to width of diameters, non optimal spacing
find width of every stack  for each  stack layers
length of touching coins equals  N*diameters of coin
foreach layer {1 2 3 ... N coins high} {add to total coins}
foreach alternating layer {1 2 3 ... N coins high} {add to total coins}
pack number of circles in each layer,  short of sides,
pseudocode: need test cases > small,medium, giant
testcases within range of expected operation.
pseudocode: are there any cases too small or large to be solved?
pseudocode: Could this be problem similar to placing grains on chessboard?
pseudocode: Could this be problem similar to putting oil barrels on deck of ship? ```

### Testcases Section

In planning any software, it is advisable to gather a number of testcases to check the results of the program. The math for the testcases can be checked by pasting statements in the TCL console. Aside from the TCL calculator display, when one presses the report button on the calculator, one will have console show access to the capacity functions (subroutines).

#### Testcase 1

6*6 pennies table printed in tcl wiki format
quantity value comment, if any
testcase number 1
length centimeters: 6.
width centimeters: 6.
diameter coins : 1.0
answers: rows of alternating coins : 7
number of N rows: 4
number of N-1 rows: 3
total number of coins : 39.0

#### Testcase 2

8*8 pennies table printed in tcl wiki format
quantity value comment, if any
testcase number 2
length centimeters: 8.
width centimeters: 8.
diameter coins : 1.0
answers: rows of alternating coins : 9
number of N rows: 5
number of N-1 rows: 4
total number of coins : 68.0

#### Testcase 3

10*10 pennies table printed in tcl wiki format
quantity value comment, if any
testcase number 3
length centimeters: 10.
width centimeters: 10.0
diameter coins : 1.0
answers: rows of alternating coins : 11
number of N rows: 6
number of N-1 rows: 5
total number of coins : 105.0

#### Testcase 4

6*12 coins rectangle table printed in tcl wiki format
quantity value comment, if any
testcase number 4
length centimeters: 6.
width centimeters: 12.
diameter coins : 1.0
answers: rows of alternating coins : 7
number of N rows: 4
number of N-1 rows: 3
total number of coins,alt. rows : 81
total nonoptimum coins, nonoverlapping : 72
difference coins 9
merged rectangle, alt. rows 81

#### Testcase5

12*12 pennies table printed in tcl wiki format
quantity value comment, if any
testcase number 4
length centimeters: 12.
width centimeters: 12.0
diameter coins : 1.0
answers: rows of alternating coins : 13
number of N rows: 7
number of N-1 rows: 6
total number of coins : 150.0

#### Testcase 6

18*18 pennies table printed in tcl wiki format
quantity value comment, if any
testcase number 5
length centimeters: 18.
width centimeters: 18.0
diameter coins : 1.0
answers: rows of alternating coins : 21
number of N rows: 11
number of N-1 rows: 10
total number of coins : 368.0

#### Testcase 7

 testcase number 7 length centimeters: 20. width centimeters: 20. diameter coins : 1.905 testing extra functions for alternate geo figures below total coins of equilateral triangle from length 55

### Screenshots Section

#### figure 10.

test for retrieve of offsite images

### References:

• Ask Doctor Math, Dr. Greenie, 01/23/2001, Circle packing
• Ask Doctor Math, Doctor Peterson, 08/16/99, Spheres and spaces
• Mathematics Stack Exchange, circles in box [1]
• Math Magic, circles packed [2]
• Packing Center, circles packed more [3]
• Packing Center, many problems [4]
• Wikipedia, USA Penny [5]
• google <Pennies in a Tray, By Ivars Peterson, December 10, 2004 >

## Appendix Code edit

### appendix TCL programs and scripts

```        # pretty print from autoindent and ased editor
# penny packing calculator
# written on Windows XP on eTCL
# working under TCL version 8.5.6 and eTCL 1.0.1
# gold on TCL WIKI , 2may2014
package require Tk
namespace path {::tcl::mathop ::tcl::mathfunc}
frame .frame -relief flat -bg aquamarine4
pack .frame -side top -fill y -anchor center
set names {{} { length centimeters:} }
lappend names { width (longest dimension) centimeters::}
lappend names { diameter coin centimeters: }
lappend names { answers:rows of alternating coins:}
lappend names { number of N  rows:}
lappend names { number of N-1 rows:}
lappend names { total number of coins :}
foreach i {1 2 3 4 5 6 7} {
label .frame.label\$i -text [lindex \$names \$i] -anchor e
entry .frame.entry\$i -width 35 -textvariable side\$i
set msg "Calculator for Pennies and Rectangles
from TCL WIKI,
written on eTCL "
tk_messageBox -title "About" -message \$msg }
proc pi {} {expr acos(-1)}
proc sumitup n { expr \$n * (\$n + 1) / 2}
proc equilat_triangle {base truncation diameter} {
set basecoins [int [/ \$base \$diameter] ]
set equilat_triangle [ sumitup \$basecoins ]
}
proc  circle_same_coins {base width diameter} {
set base [* [int [/ \$base \$diameter]] \$diameter]
set area [/ [* [ pi ]  \$base  \$base  ] 4. ]
set coinarea [/ [* [ pi ]  \$diameter  \$diameter  ] 4. ]
set fraction 0.75
set coinarealoss [* \$fraction [- [* \$diameter  \$diameter] \$coinarea]]
set coins [int [/ \$area  [+ \$coinarea \$coinarealoss ]]]
return \$coins
}
proc alternaterows {i limit xside} {
#console show
while {\$i <= \$limit} {
set upper [+ 1. [/ [* [- \$i 1. ] [sqrt 3. ]] 2. ]]
set upper [expr int(\$upper)]
if { \$upper == [expr { int(\$xside)-1 }]} break;
#puts " are used to check algorithm working"
#puts " upper \$upper "
#puts " i \$i "
incr i
}
set alternaterows \$i
return \$alternaterows
}
proc nonoptimum {l w d } {
set numrows [int [/ \$l \$d ] ]
set coinwidth [int [/ \$w \$d ] ]
set totalcoin [* \$numrows \$coinwidth  ]
return \$totalcoin
}
proc merged {l w d N N_1} {
set coinwidth [int [/ \$w \$d ] ]
set Nrows [* \$N \$coinwidth ]
set N_1rows [* \$N_1 [- \$coinwidth 1]]
set totalcoin [+ \$Nrows \$N_1rows  ]
return \$totalcoin
}
proc calculate { } {
global side1 side2 side3 side4 side5
global side6 side7 testcase_number
global length width diameter
global nonopttotal mergedx
incr testcase_number
set length   \$side1
set width  \$side2
set diameter \$side3
set initial 2
set limit 300
set xside [int [/ \$length \$diameter ]]
set altrows [ alternaterows \$initial \$limit \$xside]
set side4 \$altrows
set side5 [int [+ [/ \$altrows 2. ] 1.]]
set side6 [int [/ \$altrows 2. ]]
set Nrow \$side5
set N_1row \$side6
set coins [+ [* \$side5 \$side1] [* \$side6 [- \$side1 1 ]] ]
set nonopttotal [nonoptimum \$length \$width \$diameter]
set mergedx [merged \$length \$width \$diameter \$Nrow \$N_1row]
set side7 \$mergedx
}
proc fillup {aa bb cc dd ee ff gg} {
.frame.entry1 insert 0 "\$aa"
.frame.entry2 insert 0 "\$bb"
.frame.entry3 insert 0 "\$cc"
.frame.entry4 insert 0 "\$dd"
.frame.entry5 insert 0 "\$ee"
.frame.entry6 insert 0 "\$ff"
.frame.entry7 insert 0 "\$gg"}
proc clearx {} {
foreach i {1 2 3 4 5 6 7} {
.frame.entry\$i delete 0 end } }
proc reportx {} {
global side1 side2 side3 side4 side5
global side6 side7 testcase_number
global nonopttotal mergedx
global length width diameter
console show;
puts "%| table |printed in| tcl wiki format|% "
puts "&| quantity| value| comment, if any|& "
puts "&| testcase number| \$testcase_number ||& "
puts "&| length centimeters:| \$side1 ||&"
puts "&| width centimeters:| \$side2 ||& "
puts "&| diameter coins :| \$side3 ||& "
puts "&| answers: rows of alternating coins :| \$side4 ||&"
puts "&| number of N rows:| \$side5 ||& "
puts "&| number of N-1 rows:| \$side6 ||&"
puts "&| total number of coins,alt. rows  :| \$side7 ||&"
puts "&| total nonoptimum coins, nonoverlapping  :| \$nonopttotal ||&"
set rem [- \$side7 \$nonopttotal ]
puts "&| difference coins   | \$rem ||&"
puts "&| merged rectangle, alt. rows   | \$mergedx ||&"
puts "&| testing extra functions | for alternate geo figures| below|&"
set extratri [ equilat_triangle \$length \$width \$diameter ]
puts "&| total coins of equilateral triangle from length as side | \$extratri ||&"
set extracircle [circle_same_coins \$length \$width \$diameter ]

puts "&| total coins of circle from length as diameter | \$extracircle ||&"
}
frame .buttons -bg aquamarine4
::ttk::button .calculator -text "Solve" -command { calculate   }
::ttk::button .test2 -text "Testcase1" -command {clearx;fillup 6. 6. 1.0  7.1 4.01 3.01  39.0 }
::ttk::button .test3 -text "Testcase2" -command {clearx;fillup 8. 8. 1.0  9.1 5.1 4.1 68.0 }
::ttk::button .test4 -text "Testcase3" -command {clearx;fillup 10. 10.0 1.0 11.1 6.01 5.01  105.}
::ttk::button .clearallx -text clear -command {clearx }
::ttk::button .cons -text report -command { reportx }
::ttk::button .exit -text exit -command {exit}
pack  .clearallx .cons .about .exit .test4 .test3 .test2   -side bottom -in .buttons
grid .frame .buttons -sticky ns -pady {0 10}
. configure -background aquamarine4 -highlightcolor brown -relief raised -border 30
wm title . "Penny Packing Calculator"       ```

### Pushbutton Operation

For the push buttons, the recommended procedure is push testcase and fill frame, change first three entries etc, push solve, and then push report. Report allows copy and paste from console.

For testcases in a computer session, the eTCL calculator increments a new testcase number internally, eg. TC(1), TC(2) , TC(3) , TC(N). The testcase number is internal to the calculator and will not be printed until the report button is pushed for the current result numbers (which numbers will be cleared on the next solve button.) The command { calculate; reportx } or { calculate ; reportx; clearx } can be added or changed to report automatically. Another wrinkle would be to print out the current text, delimiters, and numbers in a TCL wiki style table as
```  puts " %| testcase \$testcase_number | value| units |comment |%"
puts " &| volume| \$volume| cubic meters |based on length \$side1 and width \$side2   |&"  ```

### Console program for coins inside circle experiment

```        # Pretty print version from autoindent
# and ased editor
# estimating wastage from (same d.) coins inside circle experiment
# written on Windows XP on eTCL
# code from TCL WIKI, eTCL console script
# 8may2014, [gold]
namespace path {::tcl::mathop ::tcl::mathfunc}
console show
proc pi {} {
expr { acos(-1) }
}
set counter 1
proc circling { diameter1 diameter2 coins fraction } {
global counter past
set circlearea1 [/ [* [ pi ] \$diameter1 \$diameter1 ] 4. ]
set circlearea2 [/ [* [ pi ] \$diameter2 \$diameter2 ] 4. ]
set totwaste [- \$circlearea1 [* \$circlearea2 53. ] ]
set wastepercoin [/ \$totwaste \$coins ]
incr counter
puts " waste space for (same d.) coins inside circle, coin diameter<<< circle diameter"
puts " inputs diameter1 \$diameter1 diameter2 \$diameter2 "
puts " inputs coins \$coins  fraction \$fraction "
puts " area1 \$circlearea1 area2 \$circlearea2"
puts " entered fraction \$fraction"
puts " total waste \$totwaste waste per coin \$wastepercoin"
}
circling 15.8 1.905 53. 1.```

### Output from console program, coins inside circle experiment

``` waste space for (same d.) coins inside circle, coin diameter<<< circle diameter
inputs diameter1 15.8 diameter2 1.905
inputs coins 53.  fraction 1.
area1 196.066 area2 2.850
entered fraction 1.
total waste 45.004 waste per coin 0.849```