Ein auf Bitoperatoren basierter Algorithmus der das Rechnen mit Zutaten beschreibt
Wenn anhand eines gegebenen Kochrezeptes berechnet werden soll welche Zutaten dafür benötigt werden, ist das allein mit der Rezeptbezeichnung wie Erbsensuppe oder Bratkartoffeln natürlich nicht möglich, denn Rechnen geht bekanntlich nur mit Zahlen. Der vorliegende Artikel beschreibt, welche Überlegungen nötig sind, damit eine solche Rechnung möglich wird.
Jeder verfügbare Zutat wird der Wert einer Potenz von 2 zugeordnet, diese Zuordnung muss eineindeutig sein damit sie umkehrbar ist. Aneinandergereiht ergeben die Zutaten zum Beispiel folgendes Bild:
1 0 1 1 | | |_ Kartoffeln 2**0 | |___ Wasser 2**1 |_______ Speck 2**3
Was einer 4-Bit-Zahl entspricht. Wie zu sehen ist, gibt es eine Lücke für die Position 2**2, was soviel heißt daß eine Zutat mit diesem Basiswert fürs Gesamtgericht nicht benötigt wird. Für das oben dargestellte Gericht ergibt sich somit der numerische Wert 11. Um auf diesen Wert zu kommen, werden die Werte der Zutaten bitweise UND-verknüpft: 2**0|2**1|2**3 was praktisch einer Addition gleichkommt.
Ebenfalls mit Bitoperatoren ist es nun möglich herauszukriegen welche Zutaten im Rezept mit der Wertigkeit 11 stecken. Um auf Speck zu testen, werden in der Elf drei Bits nach rechts geschoben und eine Maske darübergelegt:
print 11 >> 3 & 1; # 1
Auf diese Art und Weise lassen sich sämtliche für das Rezpt benötigten Zutaten ermitteln.
Dazu benötigen wir ein Array mit allen Gerichten die auf diese Art und Weise zusammengestellt wurden und gehen diese Liste durch. Vorher wurde über den Logarithmus die Zweierpotenz der Zutat emittelt, das ist genau die Anzahl der Bits die im numerischen Wert des Gerichts nach rechts verschoben werden müssen. Wird dann mit der Maske & 1 eine Eins ermittelt, heißt das daß die angegebene Zutat im betreffenden Gericht enthalten ist.
use strict;
use warnings;
# Schöner Ersatz für print
sub puts{
local $, = "\n";
local $\ = "\n";
print @_;
}
# Logarithmus zur Basis 2
sub log2 {
my $n = shift;
return log($n)/log(2);
}
# Rechner Architektur
use constant ARC => 32;
# Die Basiszutaten im Dualen System
# d.h., jeder Wert ist eine Potenz von 2
my %bas = (
'Wasser' => 2**0,
'Salz' => 2**1,
'Pfeffer' => 2**2,
'Speck' => 2**3,
'Kartoffeln' => 2**4,
'Zwiebeln' => 2**5,
'Kümmel' => 2**6,
'Majoran' => 2**7,
'Petersilie' => 2**8,
'Erbsen' => 2**9,
);
# Nun wird gekocht, 2 Rezepte
my $Bratkartoffeln =
$bas{'Kartoffeln'}
| $bas{'Speck'}
| $bas{'Zwiebeln'}
| $bas{'Kümmel'}
| $bas{'Majoran'}
| $bas{'Salz'}
| $bas{'Pfeffer'};
my $Erbsensuppe =
$bas{'Kartoffeln'}
| $bas{'Speck'}
| $bas{'Zwiebeln'}
| $bas{'Kümmel'}
| $bas{'Majoran'}
| $bas{'Salz'}
| $bas{'Pfeffer'}
| $bas{'Wasser'}
| $bas{'Erbsen'};
# Wir sehen unterschiedliche Ergebnisse
# nun schauen wir mal was drin ist
# Bnötigt wird die Basis auch genau andersherum
my %rbas = reverse %bas;
puts "Erbsensuppe";
puts "============";
puts map{ $_->[1] } sort{ $a->[1] cmp $b->[1] } map{ [$_, $rbas{$_}] } contents( $Erbsensuppe );
puts " ";
puts "Bratkartoffeln";
puts "============";
puts map{ $_->[1] } sort{ $a->[1] cmp $b->[1] } map{ [$_, $rbas{$_}] } contents( $Bratkartoffeln );
# nun schauen wir mal was drin ist
# angenommen werden 16 Bit
sub contents{
my $num = shift;
#puts sprintf "%b", $num;
my @raw = ();
for my $pot( 0 .. ARC - 1 ){
my $kbit = $num >> $pot & 1;
my $zk = $kbit**$pot;
#puts $kbit;
if( $kbit ){
push @raw, 2**$pot;
}
}
return @raw;
}
my %Gerichte = (
$Erbsensuppe => 'Erbsensuppe',
$Bratkartoffeln => 'Bratkartoffeln'
);
# Nun wollen wir mal schauen in welchen Gerichten eine bestimmte Zutat ist
puts "\n====== Gerichte mit Erbsen =====";
puts map { $Gerichte{$_} } lookup( $bas{Erbsen} );
puts "\n====== Gerichte mit Speck =====";
puts map { $Gerichte{$_} } lookup( $bas{Speck} );
sub lookup{
my $znr = shift; # Nummer der Zutat
my $bits = log2 $znr; # Bits to shift
my @res = ();
foreach my $gericht( keys %Gerichte ){
if($gericht >> $bits & 1){
push @res, $gericht;
}
}
return @res;
}
# Auf mehrere Zutaten prüfen
puts "\n======== Gerichte mit Speck und Kartoffeln ====";
puts map { $Gerichte{$_} } and_lookup( $bas{Speck}, $bas{Kartoffeln} );
puts "\n======== Gerichte mit Erbsen und Kartoffeln ====";
puts map { $Gerichte{$_} } and_lookup( $bas{Erbsen}, $bas{Kartoffeln} );
# Beide Zutaten müssen enthalten sein
sub and_lookup{
# Nummern der Zutaten in @_
my %res = ();
my @bits = map{ log2 $_ } @_;
foreach my $gericht( keys %Gerichte ){
foreach my $xbit (@bits){
if( $gericht >> $xbit & 1 ){
$res{$gericht}++;
}
}
}
# Anzahl der Zutaten gleich Anzahl derer im Gericht
return grep { $res{$_} == scalar @_ } keys %res;
}
puts "\n===== Gerichte mit Erbsen oder Kartoffeln ======";
puts map { $Gerichte{$_} } or_lookup( $bas{Erbsen}, $bas{Kartoffeln} );
# Eine der Zutaten muss drin sein
sub or_lookup{
# Nummern der Zutaten in @_
my %res = ();
my @bits = map{ log2 $_ } @_;
foreach my $gericht( keys %Gerichte ){
foreach my $xbit (@bits){
if( $gericht >> $xbit & 1 ){
$res{$gericht}++;
}
}
}
return keys %res;
}
# Das Perlscript erzeugt untenstehende Ausgabe
__END__
Erbsensuppe
============
Erbsen
Kartoffeln
Kümmel
Majoran
Pfeffer
Salz
Speck
Wasser
Zwiebeln
Bratkartoffeln
===========
Kartoffeln
Kümmel
Majoran
Pfeffer
Salz
Speck
Zwiebeln
====== Gerichte mit Erbsen =====
Erbsensuppe
====== Gerichte mit Speck =====
Bratkartoffeln
Erbsensuppe
======== Gerichte mit Speck und Kartoffeln ====
Bratkartoffeln
Erbsensuppe
======== Gerichte mit Erbsen und Kartoffeln ====
Erbsensuppe
===== Gerichte mit Erbsen oder Kartoffeln ======
Bratkartoffeln
Erbsensuppe
Datenschutzerklärung: Diese Seite dient rein privaten Zwecken. Auf den für diese Domäne installierten Seiten werden grundsätzlich keine personenbezogenen Daten erhoben. Das Loggen der Zugriffe mit Ihrer Remote Adresse erfolgt beim Provider soweit das technisch erforderlich ist. sos@rolfrost.de.