### Author Topic: Find all = 150 ?  (Read 4394 times)

0 Members and 1 Guest are viewing this topic.

#### El Jefe ##### Re: [challenge] Find all = 150 in the table?
« Reply #30 on: January 02, 2022, 04:34:16 AM »
It is a worthy cause! Industry & governments spend zillions on material optimizations, I figure if we can chop off some tiny percent of waste, that adds up to zillions of tons of greenhouse gasses and industrial waste, its worthy of a challenge.

Also, optimizing computations, how many tons of greenhouse gasses would be saved if FB were 0.05% faster? In fact, how much is wasted with slow computer languages? Yes, thats right, moving your source to C or assembly might just save the planet
Retired

#### El Jefe ##### Re: [challenge] Find all = 150 in the table?
« Reply #31 on: January 02, 2022, 05:18:59 AM »
note, the bigger the data, it seems the better the optimization (C++ test with 420 nums)
Code: [Select]
`12 12 12 12 12 12 12 12 12 12 5 5 5 5 5 =14524 24 24 24 24 24 1 =14524 24 24 24 24 24 1 =14524 24 24 24 24 24 1 =14524 24 24 24 24 24 1 =14518 18 18 18 18 18 18 18 1 =14517 17 17 17 17 17 14 14 14 1 =14529 28 28 28 28 5 =14613 13 13 13 13 13 13 13 13 12 12 5 =14629 29 29 29 29 1 =14629 29 29 29 29 1 =14629 29 29 29 29 1 =14629 29 29 29 29 1 =14629 29 29 29 29 1 =14628 28 28 28 28 5 1 =14628 28 28 28 28 5 1 =14614 14 14 14 14 14 14 14 14 14 5 1 =14614 14 14 14 14 14 14 14 14 14 5 1 =14637 37 37 36 =14731 29 29 29 29 =14721 21 21 21 21 21 21 =14721 21 21 21 21 21 21 =14719 19 19 18 18 18 18 18 =14724 24 24 24 23 23 5 =14737 37 37 37 =14837 37 37 37 =14837 37 37 37 =14831 31 31 31 25 =14931 31 31 31 25 =14931 31 31 31 25 =14925 25 25 25 25 24 =14932 32 32 32 21 =14932 32 32 32 21 =14932 32 32 32 21 =14932 32 32 32 21 =14932 32 32 32 21 =14932 32 32 32 21 =14932 32 32 32 21 =14928 25 25 25 25 21 =14923 21 21 21 21 21 21 =14914 14 14 14 14 14 13 13 13 13 13 =14936 36 36 36 5 =14936 36 36 36 5 =14936 36 36 36 5 =14950 50 50 =15050 50 50 =15050 50 50 =15050 50 50 =15050 50 50 =15050 50 50 =15050 50 50 =15050 50 50 =15050 50 50 =15050 50 50 =15039 39 39 33 =15039 39 39 33 =15039 39 39 33 =15039 39 39 33 =15039 39 39 33 =15025 25 25 25 25 25 =15025 25 25 25 25 25 =15025 25 25 25 25 25 =15032 32 31 31 24 =15033 33 33 33 18 =15033 33 33 33 18 =15019 19 19 19 19 19 19 17 =15017 17 17 17 17 17 17 17 14 =15021 21 19 19 19 19 19 13 =15036 36 33 33 12 =15023 23 23 23 23 23 12 =15023 23 23 23 23 23 12 =150num bins = 71`
Retired ##### Re: [challenge] Find all = 150 in the table?
« Reply #32 on: January 02, 2022, 06:04:01 AM »
Bin packing was explored here too -

https://www.theswamp.org/index.php?topic=48361.0

#### El Jefe ##### Re: [challenge] Find all = 150 in the table?
« Reply #33 on: January 02, 2022, 06:43:46 AM »
ouch, I've regressed, still used a multi-map though Code: [Select]
`37 36 33 32 12 =15032 31 29 29 28 1 =15025 25 24 24 23 21 5 =14750 50 39 =13921 19 18 17 14 14 13 =116num bins = 5`
Retired

#### Stefan

• Bull Frog
• Posts: 311 ##### Re: [challenge] Find all = 150 in the table?
« Reply #34 on: January 02, 2022, 07:45:59 AM »
Greedy algorithm

Code - Auto/Visual Lisp: [Select]
1. ;1D CUTTING STOCK
2. (defun cutting (n l / sum o p lst r)
3.   (defun sum (s p r)
4.     (cond
5.       ((= s 0) (list (reverse r) p))
6.       ((not p)  nil)
7.       ((< s 0)  nil)
8.       (T
9.          '(lambda (x)
10.             (sum
11.               (- s (car x))
12.               (subst (cons (car x) (1- (cdr x))) x p)
13.               (cons (car x) r)
14.             )
15.           )
16.           (vl-remove-if
17.            '(lambda (x)
18.               (or
19.                 (< s (car x))
20.                 (= (cdr x) 0)
21.                 (if r (< (car r) (car x)))
22.               )
23.             )
24.             p
25.           )
26.         )
27.       )
28.     )
29.   )
30.
31.   (if
32.     (numberp (car l))
33.     (foreach x l
34.       (if
35.         (setq o (assoc x p))
36.         (setq p (subst (cons x (1+ (cdr o))) o p))
37.         (setq p (cons (cons x 1) p))
38.       )
39.     )
40.     (setq p l)
41.   )
42.
43.   (setq p (vl-sort p '(lambda (a b) (> (car a) (car b)))))
44.
45.   (while p
46.     (if
47.        (<= (apply '+
48.               '(lambda (x)
49.                  (* (car x) (cdr x))
50.                )
51.               p
52.              )
53.            )
54.            n
55.        )
56.        (setq r (apply 'append
57.                   '(lambda (x / l)
58.                      (repeat (cdr x)
59.                        (setq l (cons (car x) l))
60.                      )
61.                    )
62.                    p
63.                  )
64.                )
65.              lst (cons r lst)
66.              p nil
67.        )
68.        (if
69.          (setq r (sum n p nil))
70.            (mapcar 'set '(r p) r)
71.            (setq lst (cons r lst))
72.          )
73.          (setq n (1- n))
74.        )
75.     )
76.   )
77.   (reverse lst)
78. )

Test function. For the first list, the result is not optimal, there are solutions with 150 all the way and only the last one 120
Edit: note that the input list can be a list of numbers or a list of pairs, (length . quantity)
Code: [Select]
`(defun test_cutt (n l / m r)  (setq m (getvar 'millisecs))  (if    (setq r (cutting n l))    (progn      (setq m (- (getvar 'millisecs) m))      (foreach x r        (print x)        (princ "= ")        (princ (apply '+ x))      )      (princ "\nDome in " )      (princ m)      (princ " milliseconds.")    )  )  (princ))(setq l '((50 . 20) (39 . 10) (37 . 10) (36 . 10) (33 . 10) (32 . 20) (31 . 10) (29 . 20) (28 . 10) (25 . 20) (24 . 20) (23 . 10) (21 . 20) (19 . 10) (18 . 10) (17 . 10) (14 . 20) (13 . 10) (12 . 10) (5 . 10) (1 . 10)))(test _cutt 150 l)(50 50 50) = 150(50 50 50) = 150(50 50 50) = 150(50 50 50) = 150(50 50 50) = 150(50 50 50) = 150(50 50 39 5 5 1) = 150(39 39 39 33) = 150(39 39 39 33) = 150(39 39 39 33) = 150(37 37 37 37 1 1) = 150(37 37 37 37 1 1) = 150(37 37 36 36 1 1 1 1) = 150(36 36 36 36 5 1) = 150(36 36 36 32 5 5) = 150(36 33 33 33 5 5 5) = 150(33 33 33 33 18) = 150(32 32 32 32 17 5) = 150(32 32 32 32 17 5) = 150(32 32 32 31 23) = 150(32 32 32 31 23) = 150(32 32 32 31 23) = 150(32 32 31 31 24) = 150(31 31 31 31 14 12) = 150(31 29 29 29 19 13) = 150(29 29 29 29 21 13) = 150(29 29 29 29 21 13) = 150(29 29 29 29 21 13) = 150(29 29 29 29 21 13) = 150(29 28 28 28 25 12) = 150(28 28 28 28 25 13) = 150(28 28 28 25 24 17) = 150(25 25 25 25 25 25) = 150(25 25 25 25 25 25) = 150(25 25 25 25 25 13 12) = 150(24 24 24 24 24 18 12) = 150(24 24 24 24 24 18 12) = 150(24 24 24 24 24 18 12) = 150(24 24 24 23 23 19 13) = 150(23 23 23 23 23 21 14) = 150(21 21 21 21 21 21 12 12) = 150(21 21 21 21 21 21 12 12) = 150(21 21 21 19 19 19 17 13) = 150(19 19 19 19 19 14 14 14 13) = 150(18 18 18 18 18 18 14 14 14) = 150(17 17 17 14 14 14 14 14 14 14) = 149(17 17 17 14 14 14 14 14) = 121Dome in 62 milliseconds.(setq l' (50 50 39 37 36 33 32 32 31 29 29 28 25 25 24 24 23 21 21 19 18 17 14 14 13 12 5 1))(test_cutt 150 l)(50 50 37 13) = 150(39 36 33 29 12 1) = 150(32 32 31 29 21 5) = 150(28 25 25 23 21 14 14) = 150(24 24 19 18 17) = 102Dome in 16 milliseconds.`
Has anyone tried the list from wikipedia?

Code: [Select]
`(setq n 5600 l '((1380 . 22) (1520 . 25) (1560 . 12) (1710 . 14) (1820 . 18) (1880 . 18) (1930 . 20) (2000 . 10) (2050 . 12) (2100 . 14) (2140 . 16) (2150 . 18) (2200 . 20)))`
« Last Edit: January 02, 2022, 07:54:56 AM by Stefan »

#### well20152016

• Newt
• Posts: 130 ##### Re: [challenge] Find all = 150 in the table?
« Reply #35 on: January 02, 2022, 08:32:45 AM »

#### well20152016

• Newt
• Posts: 130 ##### Re: [challenge] Find all = 150 in the table?
« Reply #36 on: January 03, 2022, 10:40:19 PM »
Serial    len   quantity  rate       surplus             combination

1       150      6    100.0%        0                       3x50

2       150      1    100.0%        0                       2x50 +  1x37 +  1x13

3       150      3    100.0%        0                       3x39 +  1x33

4       150      1    100.0%        0                       1x39 +  3x37

5       150      2    100.0%        0                       3x37 +  1x25 +  1x14

6       150      3    100.0%        0                       3x36 +  1x29 +  1x13

7       150      1    100.0%        0                       1x36 +  2x33 +  1x31 +  1x17

8       150      1    100.0%        0                       4x33 +  1x18

9       150      1    100.0%        0                       1x33 +  3x32 +  1x21

10       150      5    100.0%        0                       3x32 +  1x31 +  1x23

11       150      1    100.0%        0                       2x32 +  2x31 +  1x24

12       150      1    100.0%        0                       2x31 +  3x29 +  1x1

13       150      2    100.0%        0                       5x29 +  1x5

14       150      1    100.0%        0                       4x29 +  1x21 +  1x13

15       150      2    100.0%        0                       4x28 +  1x25 +  1x13

16       150      1    100.0%        0                       2x28 +  3x25 +  1x19

17       150      2    100.0%        0                       6x25

18       150      1    100.0%        0                       1x25 +  5x24 +  1x5

19       150      2    100.0%        0                       5x24 +  1x18 +  1x12

20       150      1    100.0%        0                       4x24 +  1x23 +  1x19 +  1x12

21       150      1    100.0%        0                       4x23 +  1x21 +  1x19 +  1x18

22       150      2    100.0%        0                       6x21 +  1x19 +  1x5

23       150      1    100.0%        0                       5x21 +  1x19 +  1x14 +  1x12

24       150      1    100.0%        0                       4x19 +  2x18 +  1x14 +  2x12

25       150      1    100.0%        0                       4x18 +  3x17 +  1x14 +  1x13

26       150      1    100.0%        0                       6x17 +  4x12

27       150      1    100.0%        0                      10x14 +  2x5

28       150      1     80.0%       30                       5x14 +  2x13 +  3x5 +  9x1

#### El Jefe ##### Re: [challenge] Find all = 150 in the table?
« Reply #37 on: January 04, 2022, 12:36:13 AM »

Has anyone tried the list from wikipedia?

Code: [Select]
`(setq n 5600 l '((1380 . 22) (1520 . 25) (1560 . 12) (1710 . 14) (1820 . 18) (1880 . 18) (1930 . 20) (2000 . 10) (2050 . 12) (2100 . 14) (2140 . 16) (2150 . 18) (2200 . 20)))`

I'm pretty far off, both of my c++ routines had about the same output (time in milliseconds 0.0559 & 0.0864)
Code: [Select]
`1880 1880 1820 =55801880 1880 1820 =55801880 1880 1820 =55801880 1880 1820 =55801880 1880 1820 =55801880 1880 1820 =55801880 1880 1820 =55801880 1880 1820 =55801880 1880 1820 =55802100 2100 1380 =55802100 2100 1380 =55802100 2100 1380 =55802100 2100 1380 =55802100 2100 1380 =55802100 2100 1380 =55802100 2100 1380 =55801930 1930 1710 =55701930 1930 1710 =55701930 1930 1710 =55701930 1930 1710 =55701930 1930 1710 =55701930 1930 1710 =55701930 1930 1710 =55701930 1930 1710 =55701930 1930 1710 =55701930 1930 1710 =55702050 2000 1520 =55702000 2000 1560 =55602000 2000 1560 =55602000 2000 1560 =55602000 2000 1560 =55602000 2000 1560 =55601930 1880 1710 =55201380 1380 1380 1380 =55201380 1380 1380 1380 =55202050 2050 1380 =54802050 2050 1380 =54802050 2050 1380 =54802050 2050 1380 =54802050 2050 1380 =54802050 2050 1380 =54801820 1820 1820 =54601820 1820 1820 =54601820 1820 1820 =54601820 1710 1710 =52401710 1710 1560 =49801560 1560 1560 =46801560 1560 1560 =46801560 1520 1520 =46001520 1520 1520 =45601520 1520 1520 =45601520 1520 1520 =45601520 1520 1520 =45601520 1520 1520 =45601520 1520 1520 =45601520 1520 1520 =45601520 1520 1380 =44202200 2200 =44002200 2200 =44002200 2200 =44002200 2200 =44002200 2200 =44002200 2200 =44002200 2200 =44002200 2200 =44002200 2200 =44002200 2200 =44002200 2150 =43502150 2150 =43002150 2150 =43002150 2150 =43002150 2150 =43002150 2150 =43002150 2150 =43002150 2150 =43002150 2150 =43002150 2150 =43002140 2140 =42802140 2140 =42802140 2140 =42802140 2140 =42802140 2140 =42802140 2140 =42802140 2140 =42802140 2140 =42802140 2100 =42401380 =1380num bins = 87`
« Last Edit: January 04, 2022, 01:08:49 AM by It's Alive! »
Retired