Re: [FWP] Love & Hate shenanigans

[Ilmari Karonen <iltzu@sci.fi>]

On Wed, 28 Mar 2001, Philip Newton wrote:
> Ilmari Karonen wrote:
> > 
> >   ($a & $b) eq $b
> 
> Here is where I disagree. I didn't use that definition; rather, I have (($a
> & $b) eq $b) || (($a & $b) eq $a) .

But that doesn't match Jasvir Nagra's original code:

  perl -e'chomp(@_=<>);map{$c=$_;map{print"$c $_\n"if!($_ eq$c)&&(($_&$c)eq$_)}@_}@_'
                                                      ^^^^^^^^^^^^^^^^^^^^^^^^

> Especially since Jasvir Nagra, in the original post, stated:
> 
> > An interesting aside: 
> > 1. Bulleans are commutative.

I think he meant "transitive".  In fact, they define a partial ordering
among the set of words.  See below.


> So 'good' & 'bad' is the same as 'bad' & 'good'. Is only one of
> ('good','bad') and ('bad','good') a Bullean pair? Who decides which one?

Um.. perl does, or at least Jasvir Nagra did:

: For some very special words and order, however, the two respective
: operators "||" and "|", and "&&" and "&" give the same result.  I call
: these special pairs of words, "Bulleans" for the obvious reason.
: 
: Fr'instance, 
: 
: print "love" & "hate";  # Hate if you want both
: print "love" | "hate";  # Love if you have a choice
: print "good" & "bad";   # Badness overwhelms

Obviously ("love" & "hate") eq ("love" && "hate"), but ("hate" & "love")
ne ("hate" && "love").  So only ("love", "hate") is a Bullean pair as
defined above.


I realized, however, that I was talking nonsense about limiting the
choice of Bulleans listed.  As Bullean pairs form a partial ordering,
the proper way to limit the list is to choose the minimum set of
Bulleans that define this ordering.  That means only those Bullean pairs
($a, $b) for which no such $c exists that both ($a, $c) and ($c, $b)
would be Bulleans, since the other pairs can be generated by applying
the transitivity rule.

A relatively efficient solution is included below.  It relies on the
fact that the partial ordering defined by Bullians is a subset of the
full ordering defined by counting the 1-bits in the strings.

  #!/usr/bin/perl -w
  use strict;

  chomp(my @words = <>);

  @words = map unpack("xxa*", $_), sort
      map {my $b = unpack("B*",$_); pack("na*", $b =~ tr/1//, $_)} @words;

  my %pairs;
  for (my $i = 0; $i < @words; $i++) {
      my $a = $words[$i];
      for (my $j = $i-1 ; $j >= 0; $j--) {
          next if exists $pairs{$i}{$j};
          my $b = $words[$j];
          next if ($a & $b) ne $b;
          print "$a $b\n" unless $a =~ /^\Q$b/;
          @{$pairs{$i}}{$j, keys %{$pairs{$j}}} = ();
      }
  }

Yes, you can run that on /usr/dict/words.  The "unless" modifier on the
print() omits pairs of the form ($b.$c, $b) from the output.

  print "wild" & "sad";

-- 
Ilmari Karonen - http://www.sci.fi/~iltzu/
"Of course, the service life of the car to which such an engine is attached
 will be measured in seconds..."   -- John Schilling in rec.arts.sf.science





==== Want to unsubscribe from Fun With Perl?  Well, if you insist...
==== Send email to <fwp-request@technofile.org> with message _body_
====   unsubscribe