### Author Topic: Find all = 150 ?  (Read 5456 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.                     (mapcar '(lambda ( x ) (cons (car l) x)) (nCr (cdr l) (1- r)))
20.                     (nCr (cdr l) r)
21.                 )
22.             )
23.         )
24.     )
25.     (defun nCr< ( l r )
26.         (if (< 0 r)
27.             (append (nCr l r) (nCr< l (1- r)))
28.         )
29.     )
30.     (nCr< l (length l))
31. )
32.
33.

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

#### It's Alive!

• Retired
• Needs a day job
• Posts: 8580
• 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: 12892
• 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: 8580
• 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
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: 12892
• 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: 12892
• 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.                     (foreach n
7.                                 (lambda ( a b / x y )
8.                                         (and
9.                                             (setq x (car a))
10.                                             (setq y (car b))
11.                                             (= x y)
12.                                         )
13.                                         (setq a (cdr a)
14.                                               b (cdr b)
15.                                         )
16.                                     )
17.                                     (< x y)
18.                                 )
19.                             )
20.                         )
21.                         (print (nth n l) d)
22.                     )
23.                     (close d)
25.                 )
26.             )
27.         )
28.         (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))
29.     )
30.     (princ)
31. )
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: 2071
• 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

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}"
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

Sometimes the question is more important than the answer.

#### kdub_nz

• Mesozoic keyThumper
• SuperMod
• Water Moccasin
• Posts: 2071
• 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

Sometimes the question is more important than the answer.

#### It's Alive!

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

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 5031 32 50 3731 37 32 5031 37 50 3231 50 32 3731 50 37 3232 31 37 5032 31 50 3732 37 31 5032 37 50 3132 50 31 3732 50 37 3137 31 32 5037 31 50 3237 32 31 5037 32 50 3137 50 31 3237 50 32 3150 31 32 3750 31 37 3250 32 31 3750 32 37 3150 37 31 3250 37 32 31`

#### kdub_nz

• Mesozoic keyThumper
• SuperMod
• Water Moccasin
• Posts: 2071
• 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.

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.
« 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

Sometimes the question is more important than the answer.

#### It's Alive!

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

#### It's Alive!

• Retired
• Needs a day job
• Posts: 8580
• 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: 12892
• 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

#### 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: 12892
• 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
« 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: 8580
• 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

• Seagull
• Posts: 10552
##### 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

• Seagull
• Posts: 10552
##### 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: 8580
• 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 536 37 3729 31 32 32 124 24 25 28 2914 14 17 18 21 21 23`

#### It's Alive!

• Retired
• Needs a day job
• Posts: 8580
• 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 =13437 36 33 32 =13850 50 39 =13925 25 24 24 23 21 =14232 31 29 29 28 =149num bins = 5`
« Last Edit: January 02, 2022, 05:13:01 AM by It's Alive! »

#### gile

• Water Moccasin
• Posts: 2493
• 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: 8580
• 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
« Last Edit: January 02, 2022, 04:21:05 AM by It's Alive! »

#### It's Alive!

• Retired
• Needs a day job
• Posts: 8580
• 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: 8580
• 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 =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`

#### Lee Mac

• Seagull
• Posts: 12892
• 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: 8580
• 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

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`

#### 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.          '(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

#### It's Alive!

• Retired
• Needs a day job
• Posts: 8580
• 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 =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! »