Bruce's email about his t1 solution

01-bruce

Carl,

  First, I want to thank you for reviewing all of the code and running the contest.  That is a lot of work and it must have taken many hours through unfamiliar and strange code.  Some of my code (especially the first problem) was likely the hardest to read and longest as well.  

  I am not asking you to take any action.  I would just like to summarize the logic because I believe the algorithm is O(n) and not exponential.

========= Deciding who is a knight and who is a knave
There are two types of actions, declaring and comparing:

  Declarations:
   X is a knight => they are the same, so put them in the same affiliation
   X is a knave => they are different, so put them in opposite affiliations
   Afterwards, see if any previous comparisons exist referencing the affiliations they belong to.  If so, mark the speaker of the comparison as a knave or knight, then treat each statement by the now known islander as fact or fiction, affiliating as necessary.

  Comparisons
   X and Y are (different|the same) => check the validity of the statement
       if the comparison can be proven, mark as knave or knight and do the resulting actions (same as above)
       otherwise, store the comparison for future declarations

========= Post Processing of results for when type could not be determined and multiple lines(possibilities) need to be printed

  Start with an array containing the empty set
  For each affiliation:
    If the affiliation is known as knights or knaves
      Add each islander in the affiliation's set to each existing possibility with its marked type
    otherwise
      clone all possibilities, add affiliated islanders as knights to the original set, and as knaves to the cloned.

=========

Please do not feel obligated to revisit my code.  My intent was just to explain myself and apologize for not cleaning up the code after getting it working.  Thank you again for your time.

--Bruce

02-masak

Thank you for giving feedback about the review. I was kinda hoping to get a bit of that.

I will read your explanation carefully and ponder whether it actually proves that the algorithm runs faster
than I thought. If it does I will definitely revisit my review. Before looking closely at it though, I kinda
doubt it'd be O(n), since even Gaussian elimination is O(n**3).

Regards,
// Carl

03-masak

Bruce,

I have now checked your argument. Correct me if I'm wrong, but you are
arguing that since a finite, fixed number of O(1) operations are
performed for each line of input, the algorithm (excluding the
post-processing step, which might have to handle exponential branching
of possibilities) runs in O(n) time.

Your summary of the algorithm is very helpful. I almost wish it had
been included in the original source code. :) But I don't believe your
operations are O(1). Specifically, an operation such as "put them in
the same affiliation" translates to O(n) code currently in Rakudo and
Niecza. Even with very generous assumptions it wouldn't be a constant
operation. Similarly with "see if any previous comparisons exist
referencing the affiliations they belong to", which doesn't seem O(1)
to me.

Your algorithm is interesting, and as far as I can see it takes some
very sensible shortcuts considering the problem domain. (The one in
"assert-no-islanders-playing-both-sides", for example.) I'm unable to
analyze it further without putting in lots more work, but it would
surprise me a lot *more* if I ended up finding it faster than Gaussian
elimination ( O(n**3) ), than if I ended up finding cases it simply
doesn't handle. The fact that it's difficult to tell which one is the
case makes me still rate it lower than edgar's solution, where it's
easy to tell.

Regards,
Carl