Path: csiph.com!eternal-september.org!feeder.eternal-september.org!nntp.eternal-september.org!.POSTED!not-for-mail From: Tim Rentsch Newsgroups: comp.lang.c Subject: Re: Cookies in boxes - algorithmic challenge Date: Wed, 29 Apr 2026 06:55:04 -0700 Organization: A noiseless patient Spider Lines: 154 Message-ID: <86fr4d27nr.fsf@linuxsc.com> References: <20260401163447.000052de@yahoo.com> <86tstlwjak.fsf@linuxsc.com> <20260408222330.00005cf8@yahoo.com> <865x5zbg10.fsf@linuxsc.com> <20260411225637.0000632e@yahoo.com> <865x5x9kbw.fsf@linuxsc.com> <20260413171129.0000003d@yahoo.com> <86a4v26pup.fsf@linuxsc.com> <20260417144410.00006d46@yahoo.com> <865x5p7ir6.fsf@linuxsc.com> <20260420004318.000007dd@yahoo.com> <86tst36b6t.fsf@linuxsc.com> <20260422120530.00002e04@yahoo.com> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Injection-Date: Wed, 29 Apr 2026 13:55:07 +0000 (UTC) Injection-Info: dont-email.me; posting-host="43c851be6dd2938b63d54cae32dcc1b4"; logging-data="4158844"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX19RGUE7XH8sS9VCU1738zQWpaJRHNkSgDk=" User-Agent: Gnus/5.11 (Gnus v5.11) Emacs/22.4 (gnu/linux) Cancel-Lock: sha1:k7gXxp6d1Kxe9AYPFlTYcT9ZM2Q= sha1:UOLT++zM59E4tf/74U4zniVbsOw= Xref: csiph.com comp.lang.c:398094 Michael S writes: > On Tue, 21 Apr 2026 18:22:34 -0700 > Tim Rentsch wrote: > >> Michael S writes: >> >>> On Fri, 17 Apr 2026 07:40:13 -0700 >>> Tim Rentsch 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 >>> #include >>> #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.