まわせ! Bouwkamp!! に挑戦したが、惜敗。90分かかった。
正攻法で挑むと楽しい良問ではあったが、意外に手数が多い。
package Bouwkamp; use strict; use warnings; use Exporter qw(import); our @EXPORT_OK = qw(solve); sub decode_bouwkamp ($) { my @result; while ($_[0] =~ /\((\d+(?:,\d+)*)\)/g) { push @result, [split /,/, $1, -1]; } \@result; } sub sort_points (@) { sort { $a->[1] <=> $b->[1] or $a->[0] <=> $b->[0] } @_; } sub rotate_point ($$$) { my ($w, $h, $p) = @_; [$w - $p->[1] - $p->[2], $p->[0], $p->[2]]; } sub parse_bouwkamp ($) { my $bouwkamp = $_[0]; my @results; my ($w, $h) = (0,0); my @next_points = ([0, 0]); for my $edges (@$bouwkamp) { @next_points = sort_points @next_points; my $cur_point = shift @next_points; for my $edge (@$edges) { push @results, [$cur_point->[0], $cur_point->[1], $edge]; # ここで、 @next_points から上辺がかぶる点を消す @next_points = grep { ! ($_->[1] == $cur_point->[1] and $cur_point->[0] <= $_->[0] and $_->[0] <= $cur_point->[0] + $edge) } @next_points; push @next_points, [$cur_point->[0], $cur_point->[1] + $edge]; $cur_point = [$cur_point->[0] + $edge, $cur_point->[1]]; $w = $cur_point->[0] if $cur_point->[0] > $w; $h = $cur_point->[1] + $edge if $cur_point->[1] + $edge > $h; } } (\@results, $w, $h); } sub deparse_bouwkamp ($) { my @points = @{$_[0]}; my @results; while (@points) { my $point = shift @points; my @cur_group = $point->[2]; my $next_point = [$point->[0] + $point->[2], $point->[1]]; while (my ($x) = grep { $next_point->[0] == $_->[0] and $next_point->[1] == $_->[1] } @points) { push @cur_group, $x->[2]; @points = grep { $next_point->[0] != $_->[0] or $next_point->[1] != $_->[1] } @points; $next_point = [$next_point->[0] + $x->[2], $next_point->[1]]; } push @results, \@cur_group; } \@results; } sub solve ($) { my ($answer_num, $encoded_bouwkamp) = split /:/, $_[0], 2; my $bouwkamps = decode_bouwkamp $encoded_bouwkamp; my ($points, $w, $h) = parse_bouwkamp $bouwkamps; my @new_points = map { rotate_point $w, $h, $_ } @$points; @new_points = sort_points @new_points; my $new_bouwkamp = deparse_bouwkamp \@new_points; '(' . join(',', @{$new_bouwkamp->[$answer_num - 1] // []}) . ')'; } 1; __END__
use strict; use warnings; use Bouwkamp qw(solve); use Test::More import => [qw(is is_deeply done_testing)]; while (<DATA>) { tr/\r\n//d; my ($no, $input, $output, undef) = split /\s+/, $_; is solve $input, $output, "Test #$no"; } is_deeply Bouwkamp::decode_bouwkamp('(33,29,50)(4,25)(37)(15,35)(16,9)(7,2)(17)(42,18)(6,11)(8,27)(24)(19)'), [[33,29,50], [4,25], [37], [15,35], [16,9], [7,2], [17], [42,18], [6,11], [8,27], [24], [19]]; is_deeply [Bouwkamp::sort_points([3, 4, undef], [2, 3, undef])], [[2, 3, undef], [3, 4, undef]]; is_deeply [Bouwkamp::parse_bouwkamp [[2, 2, 2], [3, 3]]], [[[0, 0, 2], [2, 0, 2], [4, 0, 2], [0, 2, 3], [3, 2, 3]], 6, 5]; is_deeply Bouwkamp::deparse_bouwkamp [[0, 0, 2], [2, 0, 2], [4, 0, 2], [0, 2, 3], [3, 2, 3]], [[2, 2, 2], [3, 3]]; is_deeply Bouwkamp::rotate_point(6, 5, [0, 0, 3]), [3, 0, 3]; done_testing; __END__ 0 4:(55,44,48)(40,4)(52)(26,29)(23,3)(20,31,21)(5,47)(43)(9,17)(1,8)(32)(25) (32,31) リンク 1 6:(33,29,50)(4,25)(37)(15,35)(16,9)(7,2)(17)(42,18)(6,11)(8,27)(24)(19) (6,17,2) リンク 2 7:(60,50)(23,27)(24,22,14)(7,16)(8,6)(12,15)(13)(2,28)(26)(4,21,3)(18)(17) (4,16) リンク 3 6:(99,73,56)(17,39)(68,22)(36,25)(57,42)(9,16)(2,7)(10,28)(23)(15,87,18)(72)(69) (10,36,22) リンク 4 7:(79,49,66,63)(32,17)(3,60)(29,57)(55,22,2)(20,14)(15,28)(33,9)(24)(11,134)(123) (29,17) リンク 5 7:(159,129)(57,72)(56,39,25,16,23)(9,7)(2,28)(36)(42,15)(17,22)(87)(10,18)(73)(68)(60) (10,28) リンク 6 14:(113,71,68)(32,36)(42,29)(13,44,4)(40)(62,37,38,31)(7,108)(25,12)(11,34)(23)(77,10)(67) (36) リンク 7 8:(145,125)(53,72)(45,11,9,16,31,33)(2,7)(13)(8,15)(21)(14,32)(30,37,19)(80)(18,73)(62)(55) (31) リンク 8 1:(175,140,164)(35,29,52,24)(28,160)(6,23)(130,86)(43,60)(26,17)(77)(44,68)(174)(5,155)(150) (174,130,175) リンク 9 6:(240,168,187)(149,19)(206)(163,77)(86,82,58)(40,18)(22,202)(4,78)(192,61)(62)(48,13)(35,118)(83) (4,82) リンク 10 5:(100,73,59)(14,45)(56,31)(58,42)(25,51)(19,36,26)(16,18,8)(2,17)(10)(77)(74)(28)(23,30)(44,7)(37) (2,19,56,73) リンク 11 8:(100,88,76)(27,49)(12,19,39,18)(95,11,6)(3,24)(5,1)(21)(20)(16)(2,47)(77,45)(92)(69,26)(17,60)(43) (19) リンク 12 11:(262,196,203)(83,106,7)(210)(161,84,17)(36,41,23)(18,111)(31,5)(64)(77,38)(102)(73,248)(238)(175) (248) リンク 13 9:(117,79,74)(5,69)(84)(71,46)(20,49)(25,39,57,29)(82,14)(78)(35,18)(13,12,50)(1,11)(4,10)(33,6)(27) (1,12) リンク 14 7:(163,95,78)(17,61)(68,44)(24,81)(89,94,72)(15,66)(42,45)(84,5)(79,20)(59,3)(26,22)(16,50)(4,34)(30) (30,26,3) リンク 15 10:(100,95,69)(26,43)(11,16,77,17)(88,12)(6,5)(1,20)(19)(60)(39)(18,21)(45,92)(76,27,3)(24)(49,2)(47) (47,2) リンク 16 8:(120,78,102)(34,20,24)(14,6)(2,10,23,91)(8)(53,13)(75,45)(36)(4,32)(30,47,25)(22,3)(19,107)(105)(88) (4,36,13) リンク 17 13:(119,124,96)(28,68)(114,5)(117,40)(56,52)(4,48)(21,15,24)(106,8)(6,9)(98,38,16)(13,20)(22,7)(75)(60) (20) リンク 18 2:(302,277,246)(57,189)(25,117,109,26)(235,92)(83)(8,135,49)(90,127)(81,157)(53,37)(5,76)(304)(288)(233) (53,90,92) リンク 19 13:(158,109,240)(49,60)(114,82,11)(71)(126,267)(62,52)(10,42)(40,32)(8,51,141)(48)(14,37)(39,9)(23)(7,53)(46) (60) リンク 20 8:(132,113,251)(19,36,58)(107,27,17)(10,21,22)(25,12)(1,20)(13)(80)(32,6)(26)(23,35)(130)(121,245)(127,3)(124) (26,6) リンク 21 4:(187,127,194)(60,67)(131,76,40)(33,72,156)(44,29)(19,10)(55,21)(82)(13,27,4)(23)(34)(50)(190,30)(160,2)(158) (60,127) リンク 22 12:(239,245)(132,107)(124,121)(27,25,32,23)(3,118)(35,115)(113,19)(12,13)(17,10)(6,26)(21,1)(20)(36)(22,80)(58) (124,245) リンク 23 3:(176,152)(24,38,90)(80,63,43,14)(52)(20,23)(17,26,40)(37,42,86)(72,25)(16,10)(6,4)(49,19,8,5)(47)(3,44)(11)(30) (17,63) リンク 24 15:(171,181)(95,76)(93,88)(19,30,27)(42,40,32)(5,83)(3,15,29,78)(21,12)(9,18)(8,54)(4,25)(2,46)(22)(44)(1,24)(23) (93,181) リンク 25 13:(152,88,112)(64,24)(44,92)(200,12,4)(8,7,33)(1,6)(16,5)(11)(27)(18,15)(3,31,73)(29,19)(10,9)(40)(39)(77,2)(75) (3,15) リンク 26 13:(484,316,379)(108,145,63)(82,360)(42,66)(29,198)(18,24)(308,194)(119)(69,50)(168,80)(114,149)(440)(387,35)(352) (379) リンク 27 12:(181,191)(93,88)(24,23,54,46,44)(1,22)(25)(2,42)(4,18)(8,40)(29)(9,21,32)(15,12)(3,30)(5,103,27)(98)(19,95)(76) (21) リンク 28 18:(83,79,123)(35,44)(52,31)(21,36,9)(27,60,89)(48,25)(10,20,33)(23,12)(2,5,13)(11,3)(8)(102,49,45)(16,73)(4,57)(53) (123) リンク 29 4:(649,439,456)(214,208,17)(473)(6,55,147)(385,260,4)(175,49)(104)(12,135)(116)(81,94)(125,216)(203,7)(615)(510)(419) (81,175,4) リンク 30 17:(100,114,48,53)(43,5)(58)(23,20)(61,25,14)(3,75)(11,47,96)(36)(95,49)(24,51)(37,105,27)(78)(9,28)(59,26,19)(7,40)(33) (58,5) リンク
1時間経過次点で残ってしまった問題は以下。それぞれ15分くらいかかった。
- 左上の頂点のみ保持する方針だったが、90度回転すると左上の頂点も変わるのだった
- しかもその計算に辺の長さが必要なので、頂点と辺の長さを両方持つ必要があった
- 次のグループの座標候補
@next_pointsが、正方形の配置時に辺と重なったら消さねばならない- 気がついていたけど、放置してもテスト一個くらい通るだろうと思ったら、一個も通らず
テストを真面目に書いたせいで時間を費やしたってのもあるけど、テストで手を抜いていたら後半のリカバリ時にかなりきつかった気がする。
