in reply to Challenge: Optimal Bagels Strategy

Please post solutions under here. I have included a framework....

sub yoursubhere { my $p = shift; my $v = shift; my $check = shift; my @lastresults = (0, 0); my $try; while ($lastresults[1] < $p) { #... @lastresults = $check->($try); } $try; }

I have a harness here as well that you can use to test.

use strict; use warnings; { my $solution = ''; my $p = 0; my $v = 0; my $counter = 0; sub reset_counter { $counter = 0; } sub inc_counter { $counter++; } sub get_counter { $counter; } sub setup_game { $p = shift; $v = shift; $solution = shift; } sub get_places { return $p; } sub get_dictsize { return $v; } # Very simple check function # # In particular, this does not check if characters are repeated, # characters are in the proper alphabet, nor does it handle any # timing of results. sub check_solution { my $try = shift; my ($pico, $fermi) = (0,0); inc_counter(); foreach my $i (0 .. $p-1) { foreach my $j (0 .. $p-1) { if (substr($try,$i,1) eq substr($solution,$j,1)) { if ($i == $j) { $fermi++; } else { $pico++; } } } } ($pico, $fermi); } } sub yoursubhere { my $p = shift; my $v = shift; my $check = shift; my @lastresults = (0, 0); my $try; while ($lastresults[1] < $p) { # ... @lastresults = $check->($try); } $try; } my $solutions = { yoursubhere => sub { yoursubhere(@_) }, }; my @games = ( { p => 2, v => 36, sol => 'PM' }, { p => 4, v => 36, sol => 'JAPH' }, ); foreach my $game (@games) { setup_game($game->{p}, $game->{v}, $game->{sol}); foreach my $solutionname (sort keys %$solutions) { my $solution = $solutions->{$solutionname}; reset_counter; print join(":", $solutionname, get_places, get_dictsize, $solution->(get_places, get_dictsize, sub { check_solution(@_) }, ), get_counter, ), "\n"; } }

--MidLifeXis

Please consider supporting my wife as she walks in the 2009 Alzheimer's Walk.

Replies are listed 'Best First'.
Re^2: Challenge: Optimal Bagels Strategy (Solutions)
by MidLifeXis (Monsignor) on Sep 26, 2009 at 13:26 UTC
Re^2: Challenge: Optimal Bagels Strategy (Solutions)
by MidLifeXis (Monsignor) on Sep 29, 2009 at 15:14 UTC

    Brute force solution. I wanted to have it near the top (along with my random solution) to show how an inefficient, but obvious solution would work. I would hope that solutions down the line would have much better performance and more creativity. :-)

    Note: I have seen someone (cannot remember who) calling Knuth's algorithm for mastermind a brute force algorithm. If it is the one I am thinking of, it is not a brute force algorithm, but (1) trims impossible solutions, and (2) orders guesses by highest potential of helping do (1) on the next pass.

    --MidLifeXis

    Please consider supporting my wife as she walks in the 2009 Alzheimer's Walk.