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

0 Members and 1 Guest are viewing this topic.

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: 12905
  • 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: 8659
  • 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: 10604
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: 10604
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: 8659
  • 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: 8659
  • 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: 8659
  • 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! »