Re: 1. Go compare! Guardian's algortithm riddle and mathematical proof

Before revealing your spoiler or following the link in the original post, here is my attempt to solve the puzzle.

I cannot prove this being optimal and I don't even have an idea about how to prove it. Tough stuff.

My solution needs 148 comparisons in any case.

#!/usr/bin/perl

use v5.24;
use warnings;
use experimental qw(signatures);

package HiddenDeck;

use List::Util 'shuffle';

sub new ($class, $size) {
    bless {cards => [shuffle 1 .. $size], numcmp => 0, revealed => 0},
+ $class;
}

sub cmp ($self, $i, $k) {
    die if $self->{revealed};
    $self->{numcmp}++;
    $self->{cards}[$i] <=> $self->{cards}[$k];
}

sub numcmp ($self) {
    $self->{numcmp};
} 

sub reveal($self, @i) {
    $self->{revealed} = 1;
    [$self->{cards}->@[@i]];
}

package main;

sub pair_join ($hd, $a, $b) {
      [$hd->cmp($a->[0], $b->[0]) > 0 ?
            $b->[0] :
            $a->[0],
       $hd->cmp($a->[1], $b->[1]) > 0 ?
            $a->[1] :
            $b->[1]];
}

use constant N => 100;

my $hd = HiddenDeck->new(N);

my @pairs;
for my $i (0 .. N/2 - 1) {
    push @pairs, $hd->cmp(2 * $i, 2 * $i + 1) > 0 ?
    [2 * $i + 1, 2 * $i] :
    [2 * $i, 2 * $i + 1];
}

while (@pairs > 1) {
    my @pairs1;
    for my $i (0 .. @pairs/2 - 1) {
        push @pairs1, pair_join($hd, $pairs[2 * $i], $pairs[2 * $i + 1
+]);
    }
    if (@pairs % 2) {
        $pairs1[-1] = pair_join($hd, $pairs[-1], $pairs1[-1]);
    }
    @pairs = @pairs1;
}

say "@{$hd->reveal($pairs[0]->@*)}";
say "count = ", $hd->numcmp;
[download]

I'm curious to look at the hidden/linked resources.

Update: I had expected more information from following the link. Waiting for lanx's proof 😀.

Greetings,
🐻

$gryYup$d0ylprbpriprrYpkJl2xyl~rzg??P~5lp2hyl0p$

Comment on Re: 1. Go compare! Guardian's algortithm riddle and mathematical proof Download Code

Replies are listed 'Best First'.
Re^2: 1. Go compare! Guardian's algortithm riddle and mathematical proof by LanX (Saint) on Jun 08, 2025 at 16:09 UTC
My spoiler has only the task, I didn't want to show it verbatim because of the authors copyright. If you follow the links you'll see that your solution is optimal. But I would hide your number behind spoiler tags too. :) I'll wait some days before showing my proof. Cheers Rolf _{(addicted to the Perl Programming Language :) see Wikisyntax for the Monastery}	[reply]
Re^2: 1. Go compare! Guardian's algortithm riddle and mathematical proof by LanX (Saint) on Jun 08, 2025 at 16:50 UTC
> Update: I had expected more information from following the link Behind the link is another link to the "solution", with another comment section. With various so called proofs, which I didn't find understandable or convincing. Ignore the comments about "less vs fewer" Except the one saying there should be a special hell for people nagging about grammar in a math blog. > Waiting for lanx's proof Please remind me next weekend. :) Cheers Rolf _{(addicted to the Perl Programming Language :) see Wikisyntax for the Monastery}	[reply]
Re^3: 1. Go compare! Guardian's algortithm riddle and mathematical proof by tybalt89 (Monsignor) on Jun 08, 2025 at 19:03 UTC
For those involved with computers, just remember: "less" is analog, "fewer" is digital.	[reply]
Re^4: 1. Go compare! Guardian's algortithm riddle and mathematical proof by Discipulus (Canon) on Jun 09, 2025 at 13:40 UTC
Oh thanks! ...`export PAGER="fewer"` :D L* There are no rules, there are no thumbs.. Reinvent the wheel, then learn The Wheel; may be one day you reinvent one of THE WHEELS.	[reply] [d/l]
Re^5: 1. Go compare! Guardian's algortithm riddle and mathematical proof by LanX (Saint) on Jun 09, 2025 at 14:25 UTC
Re^4: 1. Go compare! Guardian's algortithm riddle and mathematical proof by pryrt (Abbot) on Jun 08, 2025 at 22:54 UTC
That's the way I used to think of it, despite the fact that it doesn't hold up in a plethora of real life, real English situations. And since you specifically invoked "For those involved with computers", my first exception will be an example familiar to any Monk here: In Perl, `$a < $b` would be said "scalar a is less than scalar b", despite the fact that, whether the scalar is an IV or NV or Math::BigRat, scalars a and b are always digital. In mathematics, `a < b` is said "a is less than b", whether "a,b ∈ ℝ" (a and b are elements of the set of real numbers: analog) or "a,b ∈ ℤ" (a and b are elements of the set of integers: digital) In science, light comes in discrete (digital) packets called photons, but "there is less light in the dark cave then outside in the bright sunshine". "The count of the fingers I am holding up on my right hand (2) is less than the count of the fingers I am holding up on my left hand (4)", despite the fact that my fingers are quite obviously digital. (Sorry, I had to make that pun.) (I was going to originally use "quantity" rather than "count" in that example, but "quantity" isn't as restricted to digital as "count" is, so I switched to "count" to emphasize the digital nature of the values involved.) As far as I can think of, "fewer" is only used for digital items (though I'd love to learn exceptions in that direction, too, to annoy the pedants), but "less" isn't as restricted to analog as some people claim. There are many places where I think "less" sounds better to my ears than "fewer", but phrases like "10 items or less" doesn't bother me anymore, because there are too many exceptions for the rule ''"less" is always analog'' to carry the weight that I used to think it did.	[reply] [d/l] [select]
Re^4: 1. Go compare! Guardian's algortithm riddle and mathematical proof by jdporter (Paladin) on Jun 08, 2025 at 21:05 UTC
"less" is analog, "fewer" is digital. The problem is that many people — I mean sophomoric pedants — believe many quantities are discrete when in fact they are continuous. Take age, for example. A pedant might insist that "Bobby is less than ten years old" is incorrect, and must be phrased as "Bobby is fewer than ten years old". But a person's age is not really an integer number of years, it is a float amount of time. :-) "Ten years old" is a watermark; if one has not yet reached that watermark in age, then they are less than that. You see people making this ridiculous "correction" all the time.	[reply]
Re^5: 1. Go compare! Guardian's algortithm riddle and mathematical proof by hippo (Archbishop) on Jun 08, 2025 at 22:01 UTC
Re^5: 1. Go compare! Guardian's algortithm riddle and mathematical proof by GrandFather (Saint) on Jun 08, 2025 at 22:27 UTC
Re^6: 1. Go compare! Guardian's algortithm riddle and mathematical proof by jdporter (Paladin) on Jun 09, 2025 at 14:33 UTC
Re^5: 1. Go compare! Guardian's algortithm riddle and mathematical proof by jdporter (Paladin) on Jun 17, 2025 at 16:05 UTC
Re^3: 1. Go compare! Guardian's algortithm riddle and mathematical proof (Waiting?) by LanX (Saint) on Jun 10, 2025 at 11:10 UTC
Hey > > Waiting for lanx's proof > Please remind me next weekend. :) I got messages asking me when I'm posting the proof. I wanted everybody interested to have a chance to see the task and attempt to find a(nother) proof. Please /msg [lanx] if you want me to wait till the weekend. Otherwise I'll post it tomorrow. Cheers Rolf _{(addicted to the Perl Programming Language :) see Wikisyntax for the Monastery}	[reply]