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

0 Members and 1 Guest are viewing this topic.

It's Alive!

  • Retired
  • Needs a day job
  • Posts: 8662
  • AKA Daniel
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

It's Alive!

  • Retired
  • Needs a day job
  • Posts: 8662
  • AKA Daniel
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 =145
24 24 24 24 24 24 1 =145
24 24 24 24 24 24 1 =145
24 24 24 24 24 24 1 =145
24 24 24 24 24 24 1 =145
18 18 18 18 18 18 18 18 1 =145
17 17 17 17 17 17 14 14 14 1 =145
29 28 28 28 28 5 =146
13 13 13 13 13 13 13 13 13 12 12 5 =146
29 29 29 29 29 1 =146
29 29 29 29 29 1 =146
29 29 29 29 29 1 =146
29 29 29 29 29 1 =146
29 29 29 29 29 1 =146
28 28 28 28 28 5 1 =146
28 28 28 28 28 5 1 =146
14 14 14 14 14 14 14 14 14 14 5 1 =146
14 14 14 14 14 14 14 14 14 14 5 1 =146
37 37 37 36 =147
31 29 29 29 29 =147
21 21 21 21 21 21 21 =147
21 21 21 21 21 21 21 =147
19 19 19 18 18 18 18 18 =147
24 24 24 24 23 23 5 =147
37 37 37 37 =148
37 37 37 37 =148
37 37 37 37 =148
31 31 31 31 25 =149
31 31 31 31 25 =149
31 31 31 31 25 =149
25 25 25 25 25 24 =149
32 32 32 32 21 =149
32 32 32 32 21 =149
32 32 32 32 21 =149
32 32 32 32 21 =149
32 32 32 32 21 =149
32 32 32 32 21 =149
32 32 32 32 21 =149
28 25 25 25 25 21 =149
23 21 21 21 21 21 21 =149
14 14 14 14 14 14 13 13 13 13 13 =149
36 36 36 36 5 =149
36 36 36 36 5 =149
36 36 36 36 5 =149
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 50 =150
50 50 50 =150
50 50 50 =150
50 50 50 =150
39 39 39 33 =150
39 39 39 33 =150
39 39 39 33 =150
39 39 39 33 =150
39 39 39 33 =150
25 25 25 25 25 25 =150
25 25 25 25 25 25 =150
25 25 25 25 25 25 =150
32 32 31 31 24 =150
33 33 33 33 18 =150
33 33 33 33 18 =150
19 19 19 19 19 19 19 17 =150
17 17 17 17 17 17 17 17 14 =150
21 21 19 19 19 19 19 13 =150
36 36 33 33 12 =150
23 23 23 23 23 23 12 =150
23 23 23 23 23 23 12 =150
num bins = 71

Lee Mac

  • Seagull
  • Posts: 12906
  • London, England
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

It's Alive!

  • Retired
  • Needs a day job
  • Posts: 8662
  • AKA Daniel
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 :laugh:

Code: [Select]
37 36 33 32 12 =150
32 31 29 29 28 1 =150
25 25 24 24 23 21 5 =147
50 50 39 =139
21 19 18 17 14 14 13 =116
num bins = 5

Stefan

  • Bull Frog
  • Posts: 319
  • The most I miss IRL is the Undo button
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.         (vl-some
  10.          '(lambda (x)
  11.             (sum
  12.               (- s (car x))
  13.               (subst (cons (car x) (1- (cdr x))) x p)
  14.               (cons (car x) r)
  15.             )
  16.           )
  17.           (vl-remove-if
  18.            '(lambda (x)
  19.               (or
  20.                 (< s (car x))
  21.                 (= (cdr x) 0)
  22.                 (if r (< (car r) (car x)))
  23.               )
  24.             )
  25.             p
  26.           )
  27.         )
  28.       )
  29.     )
  30.   )
  31.  
  32.   (if
  33.     (numberp (car l))
  34.     (foreach x l
  35.       (if
  36.         (setq o (assoc x p))
  37.         (setq p (subst (cons x (1+ (cdr o))) o p))
  38.         (setq p (cons (cons x 1) p))
  39.       )
  40.     )
  41.     (setq p l)
  42.   )
  43.  
  44.   (setq p (vl-sort p '(lambda (a b) (> (car a) (car b)))))
  45.  
  46.   (while p
  47.     (if
  48.        (<= (apply '+
  49.              (mapcar
  50.               '(lambda (x)
  51.                  (* (car x) (cdr x))
  52.                )
  53.               p
  54.              )
  55.            )
  56.            n
  57.        )
  58.        (setq r (apply 'append
  59.                  (mapcar
  60.                   '(lambda (x / l)
  61.                      (repeat (cdr x)
  62.                        (setq l (cons (car x) l))
  63.                      )
  64.                    )
  65.                    p
  66.                  )
  67.                )
  68.              lst (cons r lst)
  69.              p nil
  70.        )
  71.        (if
  72.          (setq r (sum n p nil))
  73.          (progn
  74.            (mapcar 'set '(r p) r)
  75.            (setq lst (cons r lst))
  76.          )
  77.          (setq n (1- n))
  78.        )
  79.     )
  80.   )
  81.   (reverse lst)
  82. )

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) = 121
Dome 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) = 102
Dome 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

It's Alive!

  • Retired
  • Needs a day job
  • Posts: 8662
  • AKA Daniel
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 =5580
1880 1880 1820 =5580
1880 1880 1820 =5580
1880 1880 1820 =5580
1880 1880 1820 =5580
1880 1880 1820 =5580
1880 1880 1820 =5580
1880 1880 1820 =5580
1880 1880 1820 =5580
2100 2100 1380 =5580
2100 2100 1380 =5580
2100 2100 1380 =5580
2100 2100 1380 =5580
2100 2100 1380 =5580
2100 2100 1380 =5580
2100 2100 1380 =5580
1930 1930 1710 =5570
1930 1930 1710 =5570
1930 1930 1710 =5570
1930 1930 1710 =5570
1930 1930 1710 =5570
1930 1930 1710 =5570
1930 1930 1710 =5570
1930 1930 1710 =5570
1930 1930 1710 =5570
1930 1930 1710 =5570
2050 2000 1520 =5570
2000 2000 1560 =5560
2000 2000 1560 =5560
2000 2000 1560 =5560
2000 2000 1560 =5560
2000 2000 1560 =5560
1930 1880 1710 =5520
1380 1380 1380 1380 =5520
1380 1380 1380 1380 =5520
2050 2050 1380 =5480
2050 2050 1380 =5480
2050 2050 1380 =5480
2050 2050 1380 =5480
2050 2050 1380 =5480
2050 2050 1380 =5480
1820 1820 1820 =5460
1820 1820 1820 =5460
1820 1820 1820 =5460
1820 1710 1710 =5240
1710 1710 1560 =4980
1560 1560 1560 =4680
1560 1560 1560 =4680
1560 1520 1520 =4600
1520 1520 1520 =4560
1520 1520 1520 =4560
1520 1520 1520 =4560
1520 1520 1520 =4560
1520 1520 1520 =4560
1520 1520 1520 =4560
1520 1520 1520 =4560
1520 1520 1380 =4420
2200 2200 =4400
2200 2200 =4400
2200 2200 =4400
2200 2200 =4400
2200 2200 =4400
2200 2200 =4400
2200 2200 =4400
2200 2200 =4400
2200 2200 =4400
2200 2200 =4400
2200 2150 =4350
2150 2150 =4300
2150 2150 =4300
2150 2150 =4300
2150 2150 =4300
2150 2150 =4300
2150 2150 =4300
2150 2150 =4300
2150 2150 =4300
2150 2150 =4300
2140 2140 =4280
2140 2140 =4280
2140 2140 =4280
2140 2140 =4280
2140 2140 =4280
2140 2140 =4280
2140 2140 =4280
2140 2140 =4280
2140 2100 =4240
1380 =1380
num bins = 87
« Last Edit: January 04, 2022, 01:08:49 AM by It's Alive! »