Groups | Search | Server Info | Login | Register

Groups > comp.lang.c > #398094

Re: Cookies in boxes - algorithmic challenge

Show all headers | View raw

Michael S <already5chosen@yahoo.com> writes:

> On Tue, 21 Apr 2026 18:22:34 -0700
> Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:
>
>> Michael S <already5chosen@yahoo.com> writes:
>>
>>> On Fri, 17 Apr 2026 07:40:13 -0700
>>> Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:
>>>
>>>> My questions are these.  One, could you understand what the code is
>>>> doing and how it works?  And two, if given an appropriate choice of
>>>> what permutation is done in best_next_ctype(), does this code do
>>>> the same thing as your code?  I was trying to match the behavior
>>>> of your code but I wasn't able to figure out how it decided where
>>>> to go next.
>>>
>>> Here is the simplest form of the algorithm that I can come with.
>>> Essentially, it is a serial non-recursive variant of the code of
>>> your friend with no algorithmic or technical enhancements.
>>> Even in this form it is not slow and hopefully makes the key idea
>>> more obvious.
>>
>> I have difficulty reading code written in the style used below.  I
>> might describe it broadly as too many trees and not enough forest.
>> That comment is not meant as criticism but given just for
>> informational value.
>>
>> My hope has been that my explanations, given first in prose and then
>> in code, would let you understand how I approached the problem, so
>> you could see how your approach differs from mine and then explain
>> what the differences are.  As things stand I don't know what are the
>> common points of reference, or even whether there are any important
>> ones.
>>
>> Having said that, let me ask this.  What is your goal?  I find
>> myself wondering if we are talking past each other.
>
> My general goal is to show that while this challenge may look like
> variant of travelling salesman problem, it actually is not.
> It is not NP complete and has many solutions with mean complexity of
> little above M*N and worst case complexity still below M*N*N.

For me, neither the "mathematical" outlines nor the various code
solutions are helpful in showing the problem isn't NP complete.

On the other hand, I don't worry about whether the problem might
be NP complete.  For me the nature of the problem is enough to
show that this isn't an NP-complete kind of problem.  It doesn't
have the right feel.

> My 2nd goal is to outline common characteristics of various robust
> solutions ignoring as much as possible technical details:
>  - N progressive steps
>  - within each step, forward progress due to recording of failed
> attempts ('seen' bit array).
>
>>> #include <stdint.h>
>>> #include <stdbool.h>
>>> #include "solver.h"
>>>
>>> peek_t
>>> solver( boxes_t boxes ){
>>>   uint8_t box_of_cookie[N_BOXES];  // valid for selected sorts
>>>   for (int i = 0; i < N_BOXES; i++)
>>>     box_of_cookie[i] = N_BOXES; // value N_BOXES marks unselected
>>> sort
>>>
>>>   // Selection proceeds in progressive steps.
>>>   // At each step we select one new box and one new sort.
>>>   // A box and a sort selected at step i are never unselected later
>>>   // although association between selected boxes and sorts
>>>   // can be changed
>>>   for (int step = 0;  step < N_BOXES;  ++step) {
>>>     typedef struct {
>>>       uint8_t box, sort;
>>>     } trace_t;
>>>     trace_t levels[N_BOXES];
>>>     bool seen[N_BOXES] = {0};
>>>     for (int lvl = 0, box = step; ;) {
>>>       // look for unseen sort in box
>>>       int sort;
>>>       for (int ci = 0; ci < BOX_SIZE; ++ci) {
>>>         sort = boxes.b[box][ci];
>>>         if (!seen[sort])
>>>           break;
>>>       }
>>>       if (seen[sort]) { // no unseen sorts in box
>>>         box = levels[--lvl].box; // return to previous level
>>>         continue;
>>>       }
>>>       // Unseen sort found
>>>       // It will become a new selection for box
>>>       int selected_box = box_of_cookie[sort];
>>>       if (selected_box == N_BOXES) {
>>>         // sort unselected.
>>>         // it means that search at step i succeed
>>>         // commit preserved assignments
>>>         for (int k = 0; k < lvl; ++k)
>>>           box_of_cookie[levels[k].sort] = levels[k].box;
>>>         // assign new sort
>>>         box_of_cookie[sort] = box;
>>>         break;
>>>       }
>>>
>>>       // sort already selected
>>>       // Save new assignment for sort.
>>>       // Saved box also serves us if we return
>>>       // to the current level from above
>>>       levels[lvl++] = (trace_t){ .sort=sort, .box=box};
>>>       // Mark sort as seen.
>>>       // That mark guarantees forward progress of the search
>>>       seen[sort] = true;
>>>       // Continue search.
>>>       // At the next level we will look for new selection
>>>       // for old box of sort
>>>       box = selected_box;
>>>     }
>>>   }
>>>
>>>   // translate result from box_of_cookie[] to index of cookie in box
>>>   peek_t res;
>>>   for (int c = 0;  c < N_BOXES;  ++c) {
>>>     int b = box_of_cookie[c];
>>>     for (int k = 0; k < BOX_SIZE; ++k) {
>>>       if (boxes.b[b][k] == c) {
>>>         res.b[b] = k;
>>>         break;
>>>       }
>>>     }
>>>   }
>>>   return res;
>>> }
>>
>> Another question:  is the above typical of how you usually write
>> code, or are you writing it like that for my benefit?
>
> Do you mean, relatively long comments distributed through the code vs
> concentrated at the beginning?

I didn't mean that specifically.  There are several aspects I might
ask about.  If you're interested I can try to be be more specific.
And if you're not interested, no worries. :)

> I don't know, because I don't try to remember such things.  I'd have to
> read a sizable corpus of my own production code in order to give an
> answer.

I'm willing to trust your memory and your judgment.  If you wanted
to look at a small sample (or several samples) that you think is
representative, I think that would be fine;  no need to be
exhaustive, especially since what I'm asking is about your thoughts
and preferences rather than what code you may happen to have written
in the past.

Back to comp.lang.c | Previous | Next — Previous in thread | Next in thread | Find similar

Thread

Cookies in boxes - algorithmic challenge Michael S <already5chosen@yahoo.com> - 2026-04-01 16:34 +0300
  Re: Cookies in boxes - algorithmic challenge DFS <nospam@dfs.com> - 2026-04-01 10:02 -0400
    Re: Cookies in boxes - algorithmic challenge Michael S <already5chosen@yahoo.com> - 2026-04-01 17:15 +0300
      Re: Cookies in boxes - algorithmic challenge DFS <nospam@dfs.com> - 2026-04-01 10:28 -0400
        Re: Cookies in boxes - algorithmic challenge Michael S <already5chosen@yahoo.com> - 2026-04-01 17:58 +0300
  Re: Cookies in boxes - algorithmic challenge Bart <bc@freeuk.com> - 2026-04-01 15:20 +0100
    Re: Cookies in boxes - algorithmic challenge Michael S <already5chosen@yahoo.com> - 2026-04-01 17:56 +0300
      Re: Cookies in boxes - algorithmic challenge Bart <bc@freeuk.com> - 2026-04-01 19:50 +0100
        Re: Cookies in boxes - algorithmic challenge DFS <nospam@dfs.com> - 2026-04-01 15:56 -0400
          Re: Cookies in boxes - algorithmic challenge Bart <bc@freeuk.com> - 2026-04-01 23:33 +0100
        Re: Cookies in boxes - algorithmic challenge Richard Harnden <richard.nospam@gmail.invalid> - 2026-04-04 07:43 +0100
          Re: Cookies in boxes - algorithmic challenge Bart <bc@freeuk.com> - 2026-04-04 11:54 +0100
  Re: Cookies in boxes - algorithmic challenge DFS <nospam@dfs.com> - 2026-04-01 15:24 -0400
  Re: Cookies in boxes - algorithmic challenge DFS <nospam@dfs.com> - 2026-04-01 17:24 -0400
    Re: Cookies in boxes - algorithmic challenge Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2026-04-02 16:25 +0100
      Re: Cookies in boxes - algorithmic challenge Bart <bc@freeuk.com> - 2026-04-02 17:10 +0100
        Re: Cookies in boxes - algorithmic challenge Michael S <already5chosen@yahoo.com> - 2026-04-02 22:19 +0300
      Re: Cookies in boxes - algorithmic challenge DFS <nospam@dfs.com> - 2026-04-02 13:03 -0400
        Re: Cookies in boxes - algorithmic challenge Richard Harnden <richard.nospam@gmail.invalid> - 2026-04-02 18:52 +0100
        Re: Cookies in boxes - algorithmic challenge Bart <bc@freeuk.com> - 2026-04-02 19:50 +0100
          Re: Cookies in boxes - algorithmic challenge Michael S <already5chosen@yahoo.com> - 2026-04-02 22:24 +0300
        Re: Cookies in boxes - algorithmic challenge Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2026-04-02 20:13 +0100
          Re: Cookies in boxes - algorithmic challenge Michael S <already5chosen@yahoo.com> - 2026-04-02 22:36 +0300
      Re: Cookies in boxes - algorithmic challenge Michael S <already5chosen@yahoo.com> - 2026-04-02 22:14 +0300
    Re: Cookies in boxes - algorithmic challenge Michael S <already5chosen@yahoo.com> - 2026-04-02 22:10 +0300
      Re: Cookies in boxes - algorithmic challenge Tristan Wibberley <tristan.wibberley+netnews2@alumni.manchester.ac.uk> - 2026-04-06 22:36 +0100
        Re: Cookies in boxes - algorithmic challenge Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-04-06 15:42 -0700
        Re: Cookies in boxes - algorithmic challenge Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2026-04-06 15:44 -0700
  Re: Cookies in boxes - algorithmic challenge DFS <nospam@dfs.com> - 2026-04-04 13:33 -0400
    Re: Cookies in boxes - algorithmic challenge Michael S <already5chosen@yahoo.com> - 2026-04-04 21:03 +0300
      Re: Cookies in boxes - algorithmic challenge DFS <nospam@dfs.com> - 2026-04-04 14:19 -0400
      Re: Cookies in boxes - algorithmic challenge Bart <bc@freeuk.com> - 2026-04-04 20:22 +0100
        Re: Cookies in boxes - algorithmic challenge Michael S <already5chosen@yahoo.com> - 2026-04-04 22:40 +0300
  Re: Cookies in boxes - algorithmic challenge Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-04-04 17:08 -0700
  Re: Cookies in boxes - algorithmic challenge Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-04-08 08:42 -0700
    Re: Cookies in boxes - algorithmic challenge Michael S <already5chosen@yahoo.com> - 2026-04-08 22:23 +0300
      Re: Cookies in boxes - algorithmic challenge Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-04-09 21:22 -0700
        Re: Cookies in boxes - algorithmic challenge Michael S <already5chosen@yahoo.com> - 2026-04-10 12:23 +0300
          Re: Cookies in boxes - algorithmic challenge Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-04-10 22:41 -0700
        Re: Cookies in boxes - algorithmic challenge Michael S <already5chosen@yahoo.com> - 2026-04-10 16:16 +0300
          Re: Cookies in boxes - algorithmic challenge Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-04-11 04:27 -0700
        Re: Cookies in boxes - algorithmic challenge Michael S <already5chosen@yahoo.com> - 2026-04-11 22:56 +0300
          Re: Cookies in boxes - algorithmic challenge Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-04-11 15:57 -0700
            Re: Cookies in boxes - algorithmic challenge Michael S <already5chosen@yahoo.com> - 2026-04-12 02:15 +0300
            Re: Cookies in boxes - algorithmic challenge Michael S <already5chosen@yahoo.com> - 2026-04-13 02:03 +0300
            Re: Cookies in boxes - algorithmic challenge Michael S <already5chosen@yahoo.com> - 2026-04-13 17:11 +0300
              Re: Cookies in boxes - algorithmic challenge Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-04-16 23:52 -0700
                Re: Cookies in boxes - algorithmic challenge Michael S <already5chosen@yahoo.com> - 2026-04-17 14:44 +0300
                Re: Cookies in boxes - algorithmic challenge Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-04-17 07:40 -0700
                Re: Cookies in boxes - algorithmic challenge Michael S <already5chosen@yahoo.com> - 2026-04-17 18:30 +0300
                Re: Cookies in boxes - algorithmic challenge Michael S <already5chosen@yahoo.com> - 2026-04-20 00:43 +0300
                Re: Cookies in boxes - algorithmic challenge Michael S <already5chosen@yahoo.com> - 2026-04-21 20:37 +0300
                Re: Cookies in boxes - algorithmic challenge Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-04-21 18:22 -0700
                Re: Cookies in boxes - algorithmic challenge Michael S <already5chosen@yahoo.com> - 2026-04-22 12:05 +0300
                Re: Cookies in boxes - algorithmic challenge Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-04-29 06:55 -0700
    Re: Cookies in boxes - algorithmic challenge Michael S <already5chosen@yahoo.com> - 2026-04-15 02:15 +0300
      Re: Cookies in boxes - algorithmic challenge Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-04-16 02:57 -0700
        Re: Cookies in boxes - algorithmic challenge Michael S <already5chosen@yahoo.com> - 2026-04-17 17:04 +0300
  Re: Cookies in boxes - algorithmic challenge Michael S <already5chosen@yahoo.com> - 2026-04-08 23:45 +0300
    Re: Cookies in boxes - algorithmic challenge Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-04-09 16:37 -0700
      Re: Cookies in boxes - algorithmic challenge Michael S <already5chosen@yahoo.com> - 2026-04-10 17:02 +0300
        Re: Cookies in boxes - algorithmic challenge Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-04-11 03:45 -0700
  Re: Cookies in boxes - algorithmic challenge Michael S <already5chosen@yahoo.com> - 2026-04-09 00:01 +0300
    Re: Cookies in boxes - algorithmic challenge Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-04-09 17:07 -0700
      Re: Cookies in boxes - algorithmic challenge Michael S <already5chosen@yahoo.com> - 2026-04-10 18:06 +0300
        Re: Cookies in boxes - algorithmic challenge Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-04-11 04:31 -0700
        Re: Cookies in boxes - algorithmic challenge Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-04-16 03:22 -0700
  Re: Cookies in boxes - algorithmic challenge Bonita Montero <Bonita.Montero@gmail.com> - 2026-04-17 17:58 +0200
    Re: Cookies in boxes - algorithmic challenge Bonita Montero <Bonita.Montero@gmail.com> - 2026-04-17 18:08 +0200
    Re: Cookies in boxes - algorithmic challenge Bart <bc@freeuk.com> - 2026-04-17 17:47 +0100
      Re: Cookies in boxes - algorithmic challenge Bonita Montero <Bonita.Montero@gmail.com> - 2026-04-17 19:24 +0200
    Re: Cookies in boxes - algorithmic challenge scott@slp53.sl.home (Scott Lurndal) - 2026-04-17 19:58 +0000
      Re: Cookies in boxes - algorithmic challenge Bonita Montero <Bonita.Montero@gmail.com> - 2026-04-18 05:52 +0200
        Re: Cookies in boxes - algorithmic challenge Bart <bc@freeuk.com> - 2026-04-18 11:53 +0100
          Re: Cookies in boxes - algorithmic challenge Bart <bc@freeuk.com> - 2026-04-18 12:04 +0100
        Re: Cookies in boxes - algorithmic challenge Michael S <already5chosen@yahoo.com> - 2026-04-18 20:35 +0300
  Re: Cookies in boxes - algorithmic challenge Bonita Montero <Bonita.Montero@gmail.com> - 2026-04-17 19:52 +0200
    Re: Cookies in boxes - algorithmic challenge Bonita Montero <Bonita.Montero@gmail.com> - 2026-04-17 20:17 +0200

csiph-web