#!/usr/bin/perl
use strict;
use warnings;

my $val=45;

my @peg=(1..45);

#Karten mischen
for(@peg)
{
  my $p=int(rand(scalar @peg));
  my $k=$_;
  $_=$peg[$p];
  $peg[$p]=$k;
}

# erste Hand abheben
my @hand=splice(@peg,0,4);

# sicherheitshalber einen Counter
# damit das Script nach 1000 Durchläufen terminiert
my $cnt=0;
while(@hand && $cnt++<1000)
{
  # Alle Kombinationen in der Hand Testen
  my @result=test_values($val,@hand);
  # etwas gefunden?
  if(@result)
  {
    # Sortieren und doppelte Einträge entfernen
    my %found=();
    @result=sort{@$b <=> @$a}map{$found{join(',', sort @$_)}++?():$_}@result;

    for my $card (@{$result[0]})
    {
      # Karte ablegen
      @hand=map{$card==$_?():$_}@hand;

      # und in den Stapel
      push(@peg,$card);
    }

    print "Eine Kombination gefunden!(".join('+',sort(@{$result[0]})).")\n";
  }
  else
  {
    # eine Karte aus dem Stapel ziehen
    # habe ich gemacht, damit das Programm auch mal ein Ende findet.
    push(@hand,shift(@peg));
    print "Keine Kombination gefunden!\n";
  }

  print "Die Hand ist: ".join(', ',sort @hand)."\n\n";
  print "Nächste Runde!\n\n";
}

if(@hand)
{ print "Verloren!\n"; }
else
{ print "Gewonnen! ($cnt Rounds)\n"; }

########################################################################

sub test_values
{
  # der gesuchte wert
  my $val=shift;
  # die Karten
  my @cards=@_;

  # wenn alle Karten größer als der Suchwert,
  # dann Abbruch.
  return () unless(grep{$_<=$val}@cards);

  # wenn nur noch eine Karte
  # und diese nicht gleich dem gesuchten Wert,
  # dann Abbruch!
  return () if(@cards==1 && $cards[0] != $val);

  # summe aller Karten
  my $sum=0;
  map{$sum+=$_}@cards;
  # wenn die summe kleiner als der Suchwert abbrechen!
  return () if($sum<$val);
  # wenn die Summe der Suchwert ist,
  # dann diese Liste zurück
  return \@cards if($sum==$val);

  my @ret=();

  # wenn eine Karte dem Suchwert entspricht
  if(grep{$val==$_}@cards)
  {
    push(@ret,[$val]);
    push(@ret,test_values($val,map{$_==$val?():$_}@cards));
  }
  else
  {
    # alle Karten durch gehen
    for my $card (@cards)
    {
      # mit einer Karte weniger
      # und kleinerem Suchwert in die nächste Rekursion
      my @r=test_values($val-$card,map{$_==$card?():$_}@cards);
      if(@r)
      {
        push(@$_,$card) for(@r);
        push(@ret,@r);
      }
    }
  }

  return @ret;
}