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

0 Members and 1 Guest are viewing this topic.

well20152016

  • Newt
  • Posts: 130
Find all = 150 ?
« on: December 28, 2021, 10:28:43 PM »
Exhaustively   Too slow


 (sol 150 (21.0 25.0 29.0 29.0 17.0 5.0 19.0 14.0 50.0 33.0 24.0 39.0 21.0 13.0 50.0 32.0 36.0 37.0 24.0 31.0 18.0 14.0 1.0 23.0 28.0 25.0 12.0 32.0))

(vl-sort l '>)
(50.0 50.0 39.0 37.0 36.0 33.0 32.0 32.0 31.0 29.0 29.0 28.0 25.0 25.0 24.0 24.0 23.0 21.0 21.0 19.0 18.0 17.0 14.0 14.0 13.0 12.0 5.0 1.0)
 
(1 (1 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0) 0.0)           50 +50+37+13 =150                    150-150=0
(1 (0 0 1 0 1 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0) 0.0)           39 +36+33+28+14 =150               150-150=0
(1 (0 0 0 0 0 0 1 1 1 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1) 0.0)           32 +32+31+29+25+1 =150           150-150=0
(1 (0 0 0 0 0 0 0 0 0 0 1 0 0 1 1 1 0 0 0 1 0 1 0 0 0 1 0 0) 0.0)           29 +25+24+24+19+17+12 =150    150-150=0
(1 (0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 1 0 0 1 0 0 1 0) 48.0)          23 +21+21+18+14+5 =102           150-102=48

Code - Auto/Visual Lisp: [Select]
  1. (defun c:ww()
  2. (foreach a (lst= 150 (list 21.0 25.0 29.0 29.0 17.0 5.0 19.0 14.0 50.0 33.0 24.0 39.0 21.0 13.0 50.0 32.0 36.0 37.0 24.0 31.0 18.0 14.0 1.0 23.0 28.0 25.0 12.0 32.0))
  3.   (princ a)(princ "\n"))
  4.   )
  5. (defun lst= (n l)
  6.    (vl-remove-if-not '(lambda ( x ) (= (sum x) n)) (combinations l))
  7. )
  8.  
  9. (defun sum ( l )
  10.     (apply '+ (mapcar '(lambda ( x ) (if (numberp x) x (sum x))) l))
  11. )
  12. (defun combinations ( l )
  13.     (defun nCr ( l r )
  14.         (cond
  15.             (   (< r 2)
  16.                 (mapcar 'list l)
  17.             )
  18.             (   l
  19.                 (append
  20.                     (mapcar '(lambda ( x ) (cons (car l) x)) (nCr (cdr l) (1- r)))
  21.                     (nCr (cdr l) r)
  22.                 )
  23.             )
  24.         )
  25.     )
  26.     (defun nCr< ( l r )
  27.         (if (< 0 r)
  28.             (append (nCr l r) (nCr< l (1- r)))
  29.         )
  30.     )
  31.     (nCr< l (length l))
  32. )
  33.  
  34.  

 
« Last Edit: January 12, 2022, 02:10:53 AM by well20152016 »

It's Alive!

  • Retired
  • Needs a day job
  • Posts: 8662
  • AKA Daniel
Re: [challenge] Find all combinations with 150 in the table?
« Reply #1 on: December 29, 2021, 05:33:49 AM »
unique combinations?

Lee Mac

  • Seagull
  • Posts: 12906
  • London, England
Re: [challenge] Find all combinations with 150 in the table?
« Reply #2 on: December 29, 2021, 07:10:32 AM »

It's Alive!

  • Retired
  • Needs a day job
  • Posts: 8662
  • AKA Daniel
Re: [challenge] Find all combinations with 150 in the table?
« Reply #3 on: December 29, 2021, 07:51:14 AM »
brute force might take years, found two in like 30 minutes  :crazy2:
24 21 25 29 29 17 5
37 1 5 12 13 14 14 17 18 19
« Last Edit: December 29, 2021, 07:59:49 AM by It's Alive! »

Lee Mac

  • Seagull
  • Posts: 12906
  • London, England
Re: [challenge] Find all combinations with 150 in the table?
« Reply #4 on: December 29, 2021, 08:13:19 AM »
Quickly written, using a similar method to this -
Code - Auto/Visual Lisp: [Select]
  1. (defun foo ( n l / r )
  2.     (defun bar ( n l a )
  3.         (cond
  4.             (   (zerop n)
  5.                 (setq r (cons a r))
  6.             )
  7.             (   (and (< 0 n) l)
  8.                 (bar (- n (car l)) (cdr l) (cons (car l) a))
  9.                 (bar n (cdr l) a)
  10.             )
  11.         )
  12.     )
  13.     (bar n l nil)
  14.     r
  15. )
Code - Auto/Visual Lisp: [Select]
  1. _$ (foo 10 '(1 2 3 4 5 6))
  2. ((6 4) (5 3 2) (5 4 1) (6 3 1) (4 3 2 1))

Lee Mac

  • Seagull
  • Posts: 12906
  • London, England
Re: [challenge] Find all combinations with 150 in the table?
« Reply #5 on: December 29, 2021, 08:28:25 AM »
To avoid duplicates in the output -
Code - Auto/Visual Lisp: [Select]
  1. (defun foo ( n l / r )
  2.     (defun bar ( n l a )
  3.         (cond
  4.             (   (zerop n)
  5.                 (or (member a r) (setq r (cons a r)))
  6.             )
  7.             (   (and (< 0 n) l)
  8.                 (bar (- n (car l)) (cdr l) (cons (car l) a))
  9.                 (bar n (cdr l) a)
  10.             )
  11.         )
  12.     )
  13.     (bar n (mapcar '(lambda ( n ) (nth n l)) (vl-sort-i l '>)) nil)
  14.     r
  15. )
Code - Auto/Visual Lisp: [Select]
  1. (defun c:test ( )
  2.     (   (lambda ( l / d f )
  3.             (if (and (setq f (vl-filename-mktemp "list" nil ".txt"))
  4.                      (setq d (open f "w"))
  5.                 )
  6.                 (progn
  7.                     (foreach n
  8.                         (vl-sort-i l
  9.                             (function
  10.                                 (lambda ( a b / x y )
  11.                                     (while
  12.                                         (and
  13.                                             (setq x (car a))
  14.                                             (setq y (car b))
  15.                                             (= x y)
  16.                                         )
  17.                                         (setq a (cdr a)
  18.                                               b (cdr b)
  19.                                         )
  20.                                     )
  21.                                     (< x y)
  22.                                 )
  23.                             )
  24.                         )
  25.                         (print (nth n l) d)
  26.                     )
  27.                     (close d)
  28.                     (startapp "notepad" f)
  29.                 )
  30.             )
  31.         )
  32.         (foo 150 '(21 25 29 29 17 5 19 14 50 33 24 39 21 13 50 32 36 37 24 31 18 14 1 23 28 25 12 32))
  33.     )
  34.     (princ)
  35. )
Yields 7,021 results.
« Last Edit: December 29, 2021, 08:58:23 AM by Lee Mac »

well20152016

  • Newt
  • Posts: 130
Re: [challenge] Find all combinations with 150 in the table?
« Reply #6 on: December 29, 2021, 10:35:39 AM »
Is there a faster way
Calculation from large to small
The result is not the best, but better

(21.0 25.0 29.0 29.0 17.0 5.0 19.0 14.0 50.0 33.0 24.0 39.0 21.0 13.0 50.0 32.0 36.0 37.0 24.0 31.0 18.0 14.0 1.0 23.0 28.0 25.0 12.0 32.0)

(13.0 37.0 50.0 50.0) = 150.0
(14.0 28.0 33.0 36.0 39.0) = 150.0
(1.0 25.0 29.0 31.0 32.0 32.0) = 150.0
(12.0 17.0 19.0 24.0 24.0 25.0 29.0) = 150.0
(5.0 14.0 18.0 21.0 21.0 23.0) = 102.0
« Last Edit: December 30, 2021, 06:59:08 AM by well20152016 »

well20152016

  • Newt
  • Posts: 130
Re: [challenge] Find all combinations with 150 in the table?
« Reply #7 on: December 30, 2021, 02:54:37 AM »
Thank you for your help! There is no need for exhaustive methods. A fast algorithm is needed.


« Last Edit: December 30, 2021, 06:14:17 AM by well20152016 »

kdub_nz

  • Mesozoic keyThumper
  • SuperMod
  • Water Moccasin
  • Posts: 2125
  • class keyThumper<T>:ILazy<T>
Re: [challenge] Find all combinations with 150 in the table?
« Reply #8 on: December 30, 2021, 02:58:07 AM »
Total permutations 270,379,074  :lmao:

Hi Dan,
I can't retire either , I keep getting dragged back :)

I have to question your permutation count.

Code - Python: [Select]
  1. data = "21.0 25.0 29.0 29.0 17.0 5.0 19.0 14.0 50.0 33.0 24.0 39.0 21.0 13.0 50.0 32.0 36.0 37.0 24.0 31.0 18.0 14.0 1.0 23.0 28.0 25.0 12.0 32.0"
  2. data_float_sorted = sorted([float(i) for i in data.split()], reverse=True)
  3. setsize = 150
  4. sets = (sum(data_float_sorted) // setsize)
  5. remainder = sum(data_float_sorted) % setsize
  6. answers = f"sets => {sets} : remainder => {remainder} : shortfall => {setsize - remainder}"
  7. print(answers)
  8. sets => 4.0 : remainder => 102.0 : shortfall => 48.0
  9.  
  10.  

. . . which tallies with the op's sample.

my understanding is that the combination sets can be any size ( summing to 150 ) and are removed from the initial set once selected.

ps Excuse my python, and I was too lazy to re-type the data set, hence the mapped copied data

 pps. I wasn't sure if the data was meant to be ints or floats. integers would be faster, but we dance with the one who brought us.


Best wishes for a safe new year . . to all.
« Last Edit: December 30, 2021, 03:21:26 AM by kdub »
Called Kerry in my other life
Retired; but they dragged me back in !

I live at UTC + 13.00

---
some people complain about loading the dishwasher.
Sometimes the question is more important than the answer.

kdub_nz

  • Mesozoic keyThumper
  • SuperMod
  • Water Moccasin
  • Posts: 2125
  • class keyThumper<T>:ILazy<T>
Re: [challenge] Find all combinations with 150 in the table?
« Reply #9 on: December 30, 2021, 03:07:45 AM »
Is there a faster way
Calculation from large to small
The result is not the best, but better


50 50 37 13                     =150
37 36 33 32 12                 =150
32 31 29 29 28 1              =150
25 25 24 24  21 18  13      =150
23 19  17 14 14 5             =92

This solution is invalid, it seems that 37 has been used twice, but is only in the data list once.
Called Kerry in my other life
Retired; but they dragged me back in !

I live at UTC + 13.00

---
some people complain about loading the dishwasher.
Sometimes the question is more important than the answer.

It's Alive!

  • Retired
  • Needs a day job
  • Posts: 8662
  • AKA Daniel
Re: [challenge] Find all combinations with 150 in the table?
« Reply #10 on: December 30, 2021, 03:55:45 AM »
Total permutations 270,379,074  :lmao:

Hi Dan,
I can't retire either , I keep getting dragged back :)

I have to question your permutation count.

lol, hard to get away.

Right, so I get 7021ish

But if I interpret “All Combinations” as all possible combinations, then for row
Code: [Select]
31 32 37 50
all possible combinations are:
Code: [Select]
31 32 37 50
31 32 50 37
31 37 32 50
31 37 50 32
31 50 32 37
31 50 37 32
32 31 37 50
32 31 50 37
32 37 31 50
32 37 50 31
32 50 31 37
32 50 37 31
37 31 32 50
37 31 50 32
37 32 31 50
37 32 50 31
37 50 31 32
37 50 32 31
50 31 32 37
50 31 37 32
50 32 31 37
50 32 37 31
50 37 31 32
50 37 32 31

kdub_nz

  • Mesozoic keyThumper
  • SuperMod
  • Water Moccasin
  • Posts: 2125
  • class keyThumper<T>:ILazy<T>
Re: [challenge] Find all combinations with 150 in the table?
« Reply #11 on: December 30, 2021, 04:03:56 AM »
Hi Dan,
Yeah, I saw the 'All' in the title and ignored it 'cause of the result matrix the OP showed.

Code: [Select]
(1 (1 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0) 0.0)           50 +50+37+13 =150                    150-150=0
(1 (0 0 1 0 1 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0) 0.0)           39 +36+33+28+14 =150               150-150=0
(1 (0 0 0 0 0 0 1 1 1 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1) 0.0)           32 +32+31+29+25+1 =150           150-150=0
(1 (0 0 0 0 0 0 0 0 0 0 1 0 0 1 1 1 0 0 0 1 0 1 0 0 0 1 0 0) 0.0)           29 +25+24+24+19+17+12 =150    150-150=0
(1 (0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 1 0 0 1 0 0 1 0) 48.0) 



words are a bitch sometimes.
I've always held that learning to express a problem is a more important skill than learning to hack code together.


added:
and regarding the permutation you show for 4 numbers if we only consider the possible arrangements,
I agree with your summary :  4 x 3 x 2 (x 1) = 24 sets.

but, I don't think that is what the OP meant. :)     BUT: I have been known to be wrong frequently with my mindreading.  :yes:
« Last Edit: December 30, 2021, 04:16:43 AM by kdub »
Called Kerry in my other life
Retired; but they dragged me back in !

I live at UTC + 13.00

---
some people complain about loading the dishwasher.
Sometimes the question is more important than the answer.

It's Alive!

  • Retired
  • Needs a day job
  • Posts: 8662
  • AKA Daniel
Re: [challenge] Find all combinations with 150 in the table?
« Reply #12 on: December 30, 2021, 04:11:19 AM »
Hi Dan,
Yeah, I saw the 'All' in the title and ignored it 'cause of the result matrix the OP showed.

Code: [Select]
(1 (1 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0) 0.0)           50 +50+37+13 =150                    150-150=0
(1 (0 0 1 0 1 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0) 0.0)           39 +36+33+28+14 =150               150-150=0
(1 (0 0 0 0 0 0 1 1 1 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1) 0.0)           32 +32+31+29+25+1 =150           150-150=0
(1 (0 0 0 0 0 0 0 0 0 0 1 0 0 1 1 1 0 0 0 1 0 1 0 0 0 1 0 0) 0.0)           29 +25+24+24+19+17+12 =150    150-150=0
(1 (0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 1 0 0 1 0 0 1 0) 48.0) 

words are a bitch sometimes.
I've always held that learning to express a problem is a more important skill than learning to hack code together.

The original post was edited a couple times, which helped, but I’ve been known to go off on a tangent, or just be wrong  :lmao:

It's Alive!

  • Retired
  • Needs a day job
  • Posts: 8662
  • AKA Daniel
Re: [challenge] Find all combinations with 150 in the table?
« Reply #13 on: December 30, 2021, 04:15:28 AM »
My first attempt was a monumental failure lol, I used std::next_permutation on the whole set!
Then I realized that’s 28^28 possibilities, luckily I was able to hit ctrl-alt-delete before the universe evaporated   
https://en.wikipedia.org/wiki/Proton_decay

Lee Mac

  • Seagull
  • Posts: 12906
  • London, England
Re: [challenge] Find all combinations with 150 in the table?
« Reply #14 on: December 31, 2021, 08:44:27 AM »
Ah, so it's actually the cutting stock problem / bin packing problem in disguise  :-D

well20152016

  • Newt
  • Posts: 130
Re: [challenge] Find all combinations with 150 in the table?
« Reply #15 on: December 31, 2021, 09:27:24 AM »
Yes, I hope to get the perfect balance between efficiency and speed!


Code - Auto/Visual Lisp: [Select]
  1.    (defun bar ( n l a )
  2.         (cond
  3.             (   (zerop n)
  4.                 (or (member a r) (setq r (cons a r)))     Get the first match target    Exit foo
  5.             )
  6.             (   (and (< 0 n) l)
  7.                 (bar (- n (car l)) (cdr l) (cons (car l) a))
  8.                 (bar n (cdr l) a)
  9.             )
  10.         )
  11.     )
  12.  

I don't know this function form
« Last Edit: December 31, 2021, 09:32:42 AM by well20152016 »

Lee Mac

  • Seagull
  • Posts: 12906
  • London, England
Re: [challenge] Find all combinations with 150 in the table?
« Reply #16 on: December 31, 2021, 10:32:48 AM »
This should perform as required -
Code - Auto/Visual Lisp: [Select]
  1. (defun foo ( ans lst )
  2.     (defun bar ( n l a )
  3.         (cond
  4.             (   (zerop n)
  5.                 (foreach n a (setq lst (baz n lst)))
  6.                 (cons a (foo ans lst))
  7.             )
  8.             (   (and (< 0 n) l)
  9.                 (cond
  10.                     (   (bar (- n (car l)) (cdr l) (cons (car l) a)))
  11.                     (   (bar n (cdr l) a))
  12.                 )
  13.             )
  14.         )
  15.     )
  16.     (defun baz ( x l )
  17.         (if l
  18.             (if (= x (car l))
  19.                 (cdr l)
  20.                 (cons (car l) (baz x (cdr l)))
  21.             )
  22.         )
  23.     )
  24.     (bar ans lst nil)
  25. )

Not pretty though...

The results will of course be sensitive to the order of the initial list, since the function is using the first solution found as opposed to the optimal solution -
Code - Auto/Visual Lisp: [Select]
  1. _$ (setq l '(21 25 29 29 17 5 19 14 50 33 24 39 21 13 50 32 36 37 24 31 18 14 1 23 28 25 12 32))
  2.  
  3. _$ (foo 150 l)
  4. (
  5.     (24  5 17 29 29 25 21)
  6.     (13 21 33 50 14 19)
  7.     (28  1 32 50 39)
  8.     (12 23 18 24 37 36)
  9. )
  10. _$ (foo 150 (mapcar '(lambda ( n ) (nth n l)) (vl-sort-i l '>)))
  11. (
  12.     (13 37 50 50)
  13.     ( 1 12 29 33 36 39)
  14.     ( 5 21 29 31 32 32)
  15.     (14 14 21 23 25 25 28)
  16. )
  17. _$ (foo 150 (mapcar '(lambda ( n ) (nth n l)) (vl-sort-i l '<)))
  18. (
  19.     (37 19 18 17 14 14 13 12  5  1)
  20.     (36 25 24 23 21 21)
  21.     (39 33 29 25 24)
  22. )
« Last Edit: December 31, 2021, 10:38:53 AM by Lee Mac »

well20152016

  • Newt
  • Posts: 130
Re: [challenge] Find all combinations with 150 in the table?
« Reply #17 on: December 31, 2021, 06:32:06 PM »

 Lee Mac  Thank you very much!
Completion time :0.02seconds   :smitten:
« Last Edit: December 31, 2021, 07:11:25 PM by well20152016 »

ssdd

  • Newt
  • Posts: 35
Re: [challenge] Find all = 150 in the table?
« Reply #18 on: January 01, 2022, 03:48:41 AM »
Looking forward to Lee mas masterpiece

It's Alive!

  • Retired
  • Needs a day job
  • Posts: 8662
  • AKA Daniel
Re: [challenge] Find all combinations with 150 in the table?
« Reply #19 on: January 01, 2022, 04:46:43 AM »
..
The number exceeds 500,Internal stack limit reached
...

This can happen with big data and recursion

well20152016

  • Newt
  • Posts: 130
Re: [challenge] Find all = 150 in the table?
« Reply #20 on: January 01, 2022, 04:57:05 AM »
So it's an optimization algorithm。Complete the task as much as possible!

Unfortunately, my LISP level is too poor,

« Last Edit: January 01, 2022, 05:01:01 AM by well20152016 »

well20152016

  • Newt
  • Posts: 130
Re: [challenge] Find all combinations with 150 in the table?
« Reply #21 on: January 01, 2022, 05:12:31 AM »
This can happen with big data and recursion

c++   Can you finish it better?

JohnK

  • Administrator
  • Seagull
  • Posts: 10605
Re: [challenge] Find all = 150 in the table?
« Reply #22 on: January 01, 2022, 09:51:40 AM »
What is this for?
TheSwamp.org (serving the CAD community since 2003)
Member location map - Add yourself

Donate to TheSwamp.org

Stefan

  • Bull Frog
  • Posts: 319
  • The most I miss IRL is the Undo button
Re: [challenge] Find all = 150 in the table?
« Reply #23 on: January 01, 2022, 11:28:08 AM »
What is this for?

Obviously, it's an assignment. You know, a challenge gets more attention, so why not use this advantage...

JohnK

  • Administrator
  • Seagull
  • Posts: 10605
Re: [challenge] Find all = 150 in the table?
« Reply #24 on: January 01, 2022, 11:35:18 AM »
What is this for?

Obviously, it's an assignment. You know, a challenge gets more attention, so why not use this advantage...
It's a very confusing thread. And I agree, it is sounding more and more like a "need" (not a "challenge").
TheSwamp.org (serving the CAD community since 2003)
Member location map - Add yourself

Donate to TheSwamp.org

Stefan

  • Bull Frog
  • Posts: 319
  • The most I miss IRL is the Undo button
Re: [challenge] Find all = 150 in the table?
« Reply #25 on: January 01, 2022, 12:09:17 PM »
What is this for?

Obviously, it's an assignment. You know, a challenge gets more attention, so why not use this advantage...
It's a very confusing thread. And I agree, it is sounding more and more like a "need" (not a "challenge").

Here is a description of the problem.

Following the OP input data, you have an unlimited stock of n=150 units bars from which you want to cut all the bars with length in the list (50 50 39 ... etc) with minimum waste.





It's Alive!

  • Retired
  • Needs a day job
  • Posts: 8662
  • AKA Daniel
Re: [challenge] Find all = 150 in the table?
« Reply #26 on: January 02, 2022, 02:40:52 AM »
(foo 150 '(39 50 50 5 33 36 37 37 25 29 31 32 32 1 19 24 24 25 28 29 13 14 14 17 18 21 21 23 12))
 returns ((23 33 5 50 39) (12 14 1 37 36 50) (28 31 29 25 37) (18 25 24 19 32 32))
 
but this is isn't a valid bin pack because there's values missing, that's why I'm confused at what this challenge is an about.

consider this sub-optimal fit first routine
Code: [Select]
(defun ff (c l / i r res)
  (princ "\n")
  (setq res 0)
  (setq r c)
  (foreach i l
    (if (> i r)
      (progn
        (setq res (1+ res))
        (setq r (- c i))
        (princ "\n")
      )
      (progn
        (setq r (- r i))
        (princ i)(princ " ")
      )
    )
  )
  (princ "Bins = ")
  res
)
(ff 150 '(39 50 50 5 33 36 37 37 25 29 31 32 32 1 19 24 24 25 28 29 13 14 14 17 18 21 21 23 12))

returns

Code: [Select]
39 50 50 5
36 37 37
29 31 32 32 1
24 24 25 28 29
14 14 17 18 21 21 23

It's Alive!

  • Retired
  • Needs a day job
  • Posts: 8662
  • AKA Daniel
Re: [challenge] Find all = 150 in the table?
« Reply #27 on: January 02, 2022, 02:57:18 AM »
It’s a NP-Hard problem and finding an exact minimum number of bins takes exponential time.
I would consider building a structure or list of lists, add numbers to the first list that has enough room, else append a new list

Code - C: [Select]
  1. int main()
  2. {
  3.     size_t num_bin = 0;
  4.     size_t target = 150;
  5.     vector<int> nums =
  6.     {
  7.       21, 25, 29, 29, 17, 5, 19,
  8.       14, 50, 33, 24, 39, 21, 13,
  9.       50, 32, 36, 37, 24, 31, 18,
  10.       14, 1, 23, 28, 25, 12, 32
  11.     };
  12.     sort(nums.begin(), nums.end(), greater());
  13.  
  14.     multimap<size_t, vector<int>> mm;
  15.     for (auto it : nums)
  16.     {
  17.         if (auto x = mm.find(it); x != mm.end() && x->first + it <= target)
  18.         {
  19.             x->second.push_back(it);
  20.             mm.insert(std::make_pair(x->first + it, x->second));
  21.             mm.erase(x);
  22.         }
  23.         else
  24.         {
  25.             if (auto ub = mm.upper_bound(it); ub != mm.end() && ub->first + it <= target)
  26.             {
  27.                 ub->second.push_back(it);
  28.                 mm.insert(std::make_pair(ub->first + it, ub->second));
  29.                 mm.erase(ub);
  30.             }
  31.             else
  32.             {
  33.                 num_bin++; //not enough room, f
  34.                 mm.insert(make_pair(it, vector<int>{it}));
  35.             }
  36.         }
  37.     }
  38.     printout(mm, num_bin);
  39.     return (int)num_bin;
  40. }
  41.  

output
Code: [Select]
21 19 18 17 14 14 13 12 5 1 =134
37 36 33 32 =138
50 50 39 =139
25 25 24 24 23 21 =142
32 31 29 29 28 =149
num bins = 5

« Last Edit: January 02, 2022, 05:13:01 AM by It's Alive! »

gile

  • Gator
  • Posts: 2507
  • Marseille, France
Re: [challenge] Find all = 150 in the table?
« Reply #28 on: January 02, 2022, 03:47:37 AM »
Hi,
Here's a naive bin packing.

Code - Auto/Visual Lisp: [Select]
  1. (defun bin-pack (lg lst / loop)
  2.  
  3.   (defun loop (lst remLg bar remLst)
  4.     (cond
  5.       ((null lst)
  6.         (cons (reverse bar)
  7.               (if remLst
  8.                 (loop (reverse remLst) lg nil nil)
  9.               )
  10.         )
  11.       )
  12.       ((<= (car lst) remLg)
  13.        (loop
  14.          (cdr lst)
  15.          (- remLg (car lst))
  16.          (cons (car lst) bar)
  17.          remLst
  18.        )
  19.       )
  20.       (T
  21.        (loop
  22.          (cdr lst)
  23.          remLg
  24.          bar
  25.          (cons (car lst) remLst)
  26.        )
  27.       )
  28.     )
  29.   )
  30.  
  31.   (loop (vl-sort (mapcar 'float lst) '>) lg nil nil)
  32. )

Code: [Select]
_$ (bin-pack 150 '(39 50 50 5 33 36 37 37 25 29 31 32 32 1 19 24 24 25 28 29 13 14 14 17 18 21 21 23 12))
((50.0 50.0 39.0 5.0 1.0) (37.0 37.0 36.0 33.0) (32.0 32.0 31.0 29.0 25.0) (29.0 28.0 25.0 24.0 24.0 19.0) (23.0 21.0 21.0 18.0 17.0 14.0 14.0 13.0) (12.0))
Speaking English as a French Frog

It's Alive!

  • Retired
  • Needs a day job
  • Posts: 8662
  • AKA Daniel
Re: [challenge] Find all = 150 in the table?
« Reply #29 on: January 02, 2022, 04:16:54 AM »
dang my lisp sucks lol
Code - Lisp: [Select]
  1. (defun ff (c l / i ll lll r res)
  2.   (setq ll '())
  3.   (setq lll '())
  4.   (setq r c)
  5.   (foreach i l
  6.     (if (> i r)
  7.       (progn
  8.         (setq r (- c i))
  9.         (setq ll (cons lll ll))
  10.         (setq lll '())
  11.       )
  12.       (progn
  13.         (setq r (- r i))
  14.         (setq lll (append lll (list i)))
  15.       )
  16.     )
  17.   )
  18.   ll
  19. )
  20.  

Code: [Select]
Command: (ff 150 '(39 50 50 5 33 36 37 37 25 29 31 32 32 1 19 24 24 25 28 29 13 14 14 17 18 21 21 23 12))
((14 14 17 18 21 21 23) (24 24 25 28 29) (29 31 32 32 1) (36 37 37) (39 50 50 5))

A best fit might revisit each node to check for room, but I don't know how to make a std::map in lisp  :laugh:
« Last Edit: January 02, 2022, 04:21:05 AM by It's Alive! »

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! »