#!/usr/bin/perl
use strict;
use warnings;
use Data::Dumper;

my @peg=((1..12)x4,13..19);# qw /1 1 1 1 2 2 2 2 3 3 3 3 4 4 4 4 5 5 5 5 6 6 6 6 7 7 7 7 8 8 8 8 9 9 9 9 10 10 10 10 11 11 11 11 12 12 12 12 13 14 15 16 17 18 19/;
my @range=(1..26);

#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);

my $cnt=0;
while(@hand && $cnt++<1000)
{
  print "Hand ist nun: ".join(', ',sort @hand)."\n";

  my %result;
  my %found;
  for (combinations(@hand))
  {
    next if($found{"@$_"}++);
    push(@{$result{sum(@$_)}},$_);
  }

  # found
  if(%result)
  {
    my ($val,@best)=best_choice(\@range,\%result);
    # remove card from hand
    for my $card (@best)
    {
      # remove card from hand
      @hand=map{$card==$_?():$_}@hand;

      # put the Cards back
      push(@peg,$card);
    }

    print "Kombination gefunden!(".join(' + ',@best)." = $val)\n";
  }
  else
  {
    print "Keine Kombination gefunden!\n";
    # Spiel abbrechen, verloren...
    last;
  }

  # hand füllen
  push(@hand,shift(@peg)) while(@hand && @hand<4);
  print "\n";
}

if(@hand)
{ print "VERLOREN!\n"; }
else
{ print "GEWONNEN! ($cnt RUNDEN)\n"; }

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

sub combinations
{
  my @cards=@_;

  return [] unless (@cards);

  return \@cards if(@cards==1);

  my @ret;
  my %found;
  for my $cpos (0..$#cards)
  {
    my $card=$cards[$cpos];
    my @list=@cards;
    splice(@list,$cpos,1);
    push(@ret,[$card]);
    for my $r (combinations(@list))
    {
      my @rr=sort(@$r,$card);
      # übergehe schon gefundene Kombinationen...
      next if($found{"@rr"}++);
      push(@ret,\@rr);
    }
  }

  return @ret;
}

sub best_choice
{
  my $vals=shift;
  my $found=shift;

  my @best;
  my $val;

  for my $v (@$vals)
  {
    next unless($found->{$v});

    for my $cards (@{$found->{$v}})
    {
      # wenn noch nichts gesetzt,
      # dann nimm das Erstbeste
      unless(@best && $val)
      {
        @best=@$cards;
        $val=$v;
      }

      # die Längst Zahlenreihe,
      # oder wenn gleich lang,
      # die größte Summe
      if(@best<@$cards || (@best==@$cards && $val<$v) )
      {
        @best=@$cards;
        $val=$v;
      }
    }
  }

  #es wurde nichts gefunden ...
  return 0 unless($val && @best);

  # das Ergebnis
  return ($val,@best);
}

sub sum
{
  my $summ=0;
  $summ+=$_ for(@_);
  return $summ
}