[SPOILER] My Solution to Medium QOTW - Tournament Schedule

My solution to medium QOTW - tournament schedule is included below. I proposed 
this quiz because I thought I had a really good solution to this problem, but 
when I implemented it in the computer and tested it, I found it had a major 
flaw, which prevented it from working for most numbers.

So I had to think of a different solution, which always works. It took me 
several days to think of it, and all of today to implement it. (it's quite 
tricky).

The solution works recursively in a Divide and Conquer method. If it 
encounters a number which is N = 2 ** e, it allocates the first N/2-1 days 
for the competitions inside the two halves of N/2 teams, and then the other 
N/2 days are filled using a cyclical allocation: at the first day, 0 plays 
against N/2, 1 against N/2+1, 2 against N/2+2, etc.; at the second day 0 
plays against N/2+1, 1 against N/2+2, 2 against N/2+3, and so on cyclically, 
until N/2-1 which plays against N/2+0; at the third day the teams are shifted 
by 2 according to their indexes, and so forth.

If, on the other hand it encounters a number that has a prime even divisor 
(call it p), it works by splittling the teams among p sets, and assigning the 
first N/p-1 days to competitions inside these sets. The rest of the days, are 
allocated based on the algorithm in alloc_2_times_p (explained in the next 
paragraph), where individual sets are also rotated cyclically to produce 
enough sets.

Now, the alloc_2_times_p algorithm basically works on a 2*p number of sets, 
where p is a prime number larger than 2. It competes the teams within the p 
pairs, by the following scheme:

1. For each step between 1 and p-1/2 (inclusive), generate the chain (0, step, 
step*2 mod p, step *3 mod p, step *4 mod p...). This eventually enumerates 
all possible connections between the pairs.

2. In each chain, one goes over 4 different permutations of connecting each 
half of the pair either the next or previous in the chain , so that each half 
will be connected with each of the four halfs before it and after it, once 
and only once.

3. The function performs the team assignment for each of the halfs allocations 
like that.

And without further ado, here's the code:

<<<<<<<<<<<<<<<<<<<<<<<<

use strict;
use warnings;

sub factor
{
    my $n = shift;

    my @ret;
    my $factor = 2;
    my $times = 0;

    my $process_factor = sub {
        if ($times)
        {
            push @ret, [$factor, $times];
        }
        $times = 0;
        $factor++;
    };
    while ($n != 1)
    {
        if (($n % $factor) == 0)
        {
            $n /= $factor;
            $times++;
        }
        else
        {
            $process_factor->();
        }
    }
    $process_factor->();
    return \@ret;
}

sub factor_flat
{
    my $n = shift;
    my $factors = factor($n);
    return [ map { ($_->[0]) x $_->[1] } @$factors ];
}

sub cyclical_assignment
{
    my %args = (@_);
    my $schedule_ptr = $args{'schedule_ptr'};
    my $day_offset = $args{'day_offset'};
    my $team_offset = $args{'team_offset'};
    my $team_steps = $args{'team_steps'};
    my $team = $args{'team'};
    my $other_team = $args{'other_team'};
    
    for my $offset (0 .. ($team_steps-1))
    {
        my $dir = ($team < $other_team) ? 1 : (-1);
        for my $team_idx (0 .. ($team_steps-1))
        {
            $schedule_ptr->
                [$day_offset+$offset]->
                [$team_offset+$team*$team_steps+$team_idx] =
                ($team_offset + 
                    $other_team*$team_steps+
                    (($team_idx+$dir*$offset)%$team_steps)
                );
        }
    }
}

# Planning:
# Parameters that all the functions of allocation accept:
# schedule_ptr - a pointer to the schedule (a (N-1) * N matrix of cells.
# day_offset - an offset for the days.
# team_offset - an offset for the teams.
# team_steps - a step in the teams, to be filled using cyclical allocation.
sub alloc_2_times_p
{
    my (%args) = (@_);

    my $schedule_ptr = $args{'schedule_ptr'};
    my $day_offset = $args{'day_offset'};
    my $team_offset = $args{'team_offset'};
    my $team_steps = $args{'team_steps'};
    my $p = $args{'p'};

    my $n = 2*$p;

    my @bits_base = ([0,0,1,1],[0,1,0,1],[0,1,1,0]);
    my @alloc = (((0,1) x (($p-1)/2)), 2);

    my $day = 0;
    my $team = 0;
    
    my $assign = sub {
        my ($other_team) = (@_);
        cyclical_assignment(
            'schedule_ptr' => $schedule_ptr,
            'day_offset' => ($day_offset+$day*$team_steps),
            'team_offset' => $team_offset,
            'team_steps' => $team_steps,
            'team' => $team,
            'other_team' => $other_team,
        );
        $team++;
    };
    
    my $next_day = sub {
        $day++;
        $team = 0;
    };

    # $n-2 days - compete between the pairs.
    for my $step (1 .. (($p-1)/2))
    {
        my %step_place = (map { ((($step * $_) % $p) => $_) } (0 .. ($p-1)));
        # 4 Permutations for each step
        for my $perm (0 .. 3)
        {
            my @d;
            for my $pair_idx (0 .. ($p-1))
            {
                my $perm_parity =
                    $bits_base[$alloc[$step_place{$pair_idx}]]->[$perm];
                for my $parity (0 .. 1)
                {
                    my $other_pair_idx;
                    if ($perm_parity == $parity)
                    {
                        $other_pair_idx = $pair_idx + $step;
                    }
                    else
                    {
                        $other_pair_idx = $pair_idx - $step;
                    }
                    $other_pair_idx %= $p;
                    my $other_pair_perm_parity =
                        $bits_base[$alloc
                            [$step_place{$other_pair_idx}]
                            ]->[$perm];
                    my $other_team =
                        $other_pair_idx*2 + $other_pair_perm_parity;
                    if ($perm_parity == $parity)
                    {
                        $other_team ^= 1;
                    }
                    $assign->($other_team);
                }
            }
            $next_day->();
        }
    }
}

sub allocate_schedule_helper
{
    my (%args) = (@_);

    my $n = $args{'n'};
    my $schedule_ptr = $args{'schedule_ptr'};
    my $day_offset = $args{'day_offset'};
    my $team_offset = $args{'team_offset'};

    my $factors = factor($n);

    if ($factors->[0]->[0] != 2)
    {
        die "Cannot create schedule for odd number of teams";
    }
    if ((@$factors == 1) && ($factors->[0]->[1] == 1))
    {
        $schedule_ptr->[$day_offset]->[$team_offset] = $team_offset+1;
        $schedule_ptr->[$day_offset]->[$team_offset+1] = $team_offset;
        return;
    }
    # Check for 2*p where p is prime.
    {
        my $power_of_2 = ((@$factors) == 1);
        my $p = $power_of_2 ? 2 : $factors->[1]->[0];
        
        my $sub_tournaments_size = $n / $p;
        for my $i (0 .. ($p-1))
        {
            allocate_schedule_helper(
                'schedule_ptr' => $schedule_ptr,
                'n' => $sub_tournaments_size,
                'day_offset' => $day_offset,
                'team_offset' => $team_offset+($sub_tournaments_size * $i),
            );
        }
        my $new_day_offset = $day_offset + $sub_tournaments_size - 1;
        if ($power_of_2)
        {
            cyclical_assignment(
                'schedule_ptr' => $schedule_ptr,
                'day_offset' => $new_day_offset,
                'team_offset' => $team_offset,
                'team_steps' => $sub_tournaments_size,
                'team' => 0,
                'other_team' => 1,
            );
            cyclical_assignment(
                'schedule_ptr' => $schedule_ptr,
                'day_offset' => $new_day_offset,
                'team_offset' => $team_offset,
                'team_steps' => $sub_tournaments_size,
                'team' => 1,
                'other_team' => 0,
            );
            
        }
        else
        {
            alloc_2_times_p(
                'p' => $p,
                'schedule_ptr' => $schedule_ptr,
                'day_offset' => $new_day_offset,
                'team_offset' => $team_offset,
                'team_steps' => ($n / (2*$p)),
            );
        }
        return;
    }
}

sub allocate_schedule
{
    my $n = shift;
    my $sched = [ map { [(-1) x $n] } (1 .. ($n-1)) ];
    allocate_schedule_helper(
        'schedule_ptr' => $sched,
        'n' => $n,
        'day_offset' => 0,
        'team_offset' => 0,
    );
    return $sched;
}

1;
>>>>>>>>>>

Regards,

        Shlomi Fish

---------------------------------------------------------------------
Shlomi Fish      shlomif-ik1l9ssToec+JF/nGntIXQ@xxxxxxxxxxxxxxxx
Homepage:        http://www.shlomifish.org/

Knuth is not God! It took him two days to build the Roman Empire.