diff options
| -rwxr-xr-x | challenge-062/sangeet-kar/python/ch-2-brute.py | 27 | ||||
| -rwxr-xr-x | challenge-062/sangeet-kar/python/ch-2.py | 39 | ||||
| -rwxr-xr-x | challenge-062/sangeet-kar/python/ch-2a.py | 50 | ||||
| -rwxr-xr-x | challenge-062/sangeet-kar/raku/ch-2-brute.raku | 35 | ||||
| -rwxr-xr-x | challenge-062/sangeet-kar/raku/ch-2.raku | 41 | ||||
| -rwxr-xr-x | challenge-062/sangeet-kar/raku/ch-2a.raku | 58 |
6 files changed, 125 insertions, 125 deletions
diff --git a/challenge-062/sangeet-kar/python/ch-2-brute.py b/challenge-062/sangeet-kar/python/ch-2-brute.py new file mode 100755 index 0000000000..e243087412 --- /dev/null +++ b/challenge-062/sangeet-kar/python/ch-2-brute.py @@ -0,0 +1,27 @@ +#!/usr/bin/env python + +import sys + +def n_queens_3d (n = 2): + solutions = [] + place_queen ([(i, j, k) for i in range(n) for j in range(n) for k in range(n)], [], solutions) + return indices_to_array(max(solutions, key=len), n); + +def place_queen (indices, queens, solutions): + if not indices: solutions.append(queens) + for pos in indices: + place_queen ([index for index in indices if is_available(pos, index)], [*queens, pos], solutions) + +def is_available(ref, pos): + diff = {abs(i - j) for i, j in zip (ref, pos)} + return not ( len(diff) < 2 or (len(diff) == 2 and 0 in diff)) + +def indices_to_array (indices, n): + array = [[[0 for _ in range(n)] for _ in range(n)] for _ in range(n)] + for i, j, k in indices: + array[i][j][k] = 1 + return array + +n = int(sys.argv[1]) if len(sys.argv) > 1 else 2 +print(n_queens_3d (n)) + diff --git a/challenge-062/sangeet-kar/python/ch-2.py b/challenge-062/sangeet-kar/python/ch-2.py index e243087412..e7d8772294 100755 --- a/challenge-062/sangeet-kar/python/ch-2.py +++ b/challenge-062/sangeet-kar/python/ch-2.py @@ -1,16 +1,37 @@ #!/usr/bin/env python import sys +import heapq -def n_queens_3d (n = 2): +# 1. n_queens_3d finds the solution using beam search +# 2. the higher the beam_width, the better is the solution. +# 3. with beam_width=1, it's very fast but the solution may not be optimal maximising the number of queens. +# 4. with beam_width=-1, it searches the entire search space. Ensures best solution but slow as hell for high n +# 5. I think one can find the best solution with beam_width 2-3 for n-values less than 8 + + +def n_queens_3d (n = 2, beam_width = 2): solutions = [] - place_queen ([(i, j, k) for i in range(n) for j in range(n) for k in range(n)], [], solutions) - return indices_to_array(max(solutions, key=len), n); + place_queen ([(i, j, k) for i in range(n) for j in range(n) for k in range(n)], + [], + solutions, + beam_width=beam_width) + best = max(solutions, key=len) + print(f"queens: {len(best)}") + return indices_to_array( best, n) -def place_queen (indices, queens, solutions): - if not indices: solutions.append(queens) - for pos in indices: - place_queen ([index for index in indices if is_available(pos, index)], [*queens, pos], solutions) +def place_queen (indices, queens, solutions, beam_width=2): + if not indices: + solutions.append(queens) + return + if beam_width == -1: + best = ((index, [i for i in indices if is_available(index, i)]) for index in indices) + else: + best = heapq.nlargest(beam_width, + ((index, [i for i in indices if is_available(index, i)]) for index in indices), + key=lambda pair: len(pair[1])) + for pos, available in best: + place_queen (available, [*queens, pos], solutions, beam_width=beam_width) def is_available(ref, pos): diff = {abs(i - j) for i, j in zip (ref, pos)} @@ -23,5 +44,7 @@ def indices_to_array (indices, n): return array n = int(sys.argv[1]) if len(sys.argv) > 1 else 2 -print(n_queens_3d (n)) +beam_width = int(sys.argv[2]) if len(sys.argv) > 2 else 2 + +print(n_queens_3d (n, beam_width)) diff --git a/challenge-062/sangeet-kar/python/ch-2a.py b/challenge-062/sangeet-kar/python/ch-2a.py deleted file mode 100755 index 21ed5b6898..0000000000 --- a/challenge-062/sangeet-kar/python/ch-2a.py +++ /dev/null @@ -1,50 +0,0 @@ -#!/usr/bin/env python - -import sys -import heapq - -# 1. n_queens_3d finds the solution using beam search -# 2. the higher the beam_width, the better is the solution. -# 3. with beam_width=1, it's very fast but the solution may not be optimal maximising the number of queens. -# 4. with beam-width=-1, it searches the entire search space. Ensures best solution but slow as hell for high n -# 5. I think one can find the best solution with beam-width 2-3 for n-values less than 8 - - -def n_queens_3d (n = 2, beam_width = 2): - solutions = [] - place_queen ([(i, j, k) for i in range(n) for j in range(n) for k in range(n)], - [], - solutions, - beam_width=beam_width) - best = max(solutions, key=len) - print(f"queens: {len(best)}") - return indices_to_array( best, n) - -def place_queen (indices, queens, solutions, beam_width=2): - if not indices: - solutions.append(queens) - return - if beam_width == -1: - best = ((index, [i for i in indices if is_available(index, i)]) for index in indices) - else: - best = heapq.nlargest(beam_width, - ((index, [i for i in indices if is_available(index, i)]) for index in indices), - key=lambda pair: len(pair[1])) - for pos, available in best: - place_queen (available, [*queens, pos], solutions, beam_width=beam_width) - -def is_available(ref, pos): - diff = {abs(i - j) for i, j in zip (ref, pos)} - return not ( len(diff) < 2 or (len(diff) == 2 and 0 in diff)) - -def indices_to_array (indices, n): - array = [[[0 for _ in range(n)] for _ in range(n)] for _ in range(n)] - for i, j, k in indices: - array[i][j][k] = 1 - return array - -n = int(sys.argv[1]) if len(sys.argv) > 1 else 2 -beam_width = int(sys.argv[2]) if len(sys.argv) > 2 else 2 - -print(n_queens_3d (n, beam_width)) - diff --git a/challenge-062/sangeet-kar/raku/ch-2-brute.raku b/challenge-062/sangeet-kar/raku/ch-2-brute.raku new file mode 100755 index 0000000000..3d973dab62 --- /dev/null +++ b/challenge-062/sangeet-kar/raku/ch-2-brute.raku @@ -0,0 +1,35 @@ +#!/usr/bin/env raku + +sub n-queens-threeD($n = 2) { + my @solutions = []; + place-queen [^$n X ^$n X ^$n], [], @solutions; + return indices-to-array @solutions.max(+*), $n; +} + + +sub place-queen(@indices, @queens, @solutions) { + @solutions.push([@queens]) if not @indices; + for @indices -> $pos { + place-queen(@indices.grep({is-available($pos, $_)}), (|@queens, $pos), @solutions); + } +} + + +sub is-available($ref, $pos) { + my $diff = ($ref »-« $pos)».abs.Set; + not (+$diff == 1 || (+$diff == 2 && 0 ∈ $diff)) +} + + +sub indices-to-array(@indices, $n) { + my @array = [[[ 0 xx $n] xx $n] xx $n]; + for @indices -> ($x, $y, $z) { + @array[$x; $y; $z] = 1; + } + return @array; +} + + +sub MAIN (Int :$n=2) { + say n-queens-threeD $n; +} diff --git a/challenge-062/sangeet-kar/raku/ch-2.raku b/challenge-062/sangeet-kar/raku/ch-2.raku index 3d973dab62..a1a9e78560 100755 --- a/challenge-062/sangeet-kar/raku/ch-2.raku +++ b/challenge-062/sangeet-kar/raku/ch-2.raku @@ -1,16 +1,31 @@ #!/usr/bin/env raku -sub n-queens-threeD($n = 2) { +# 1. n-queens-d3 finds the solution using beam search +# 2. the higher the beamr-width, the better is the solution. +# 3. with beam-width=1, it's very fast but the solution may not be optimal maximising the number of queens. +# 4. with beam-width=-1, it searches the entire search space. Ensures best solution but slow as hell for high n +# 5. I think one can find the best solution with beam-width 2-3 for n-values less than 8 + +sub n-queens-d3($n = 2, $beam-width=2) { my @solutions = []; - place-queen [^$n X ^$n X ^$n], [], @solutions; - return indices-to-array @solutions.max(+*), $n; + place-queen [^$n X ^$n X ^$n], [], @solutions, $beam-width; + my $best = @solutions.max(+*); + say "Queens placed : ", +$best; + return indices-to-array $best, $n; } -sub place-queen(@indices, @queens, @solutions) { - @solutions.push([@queens]) if not @indices; - for @indices -> $pos { - place-queen(@indices.grep({is-available($pos, $_)}), (|@queens, $pos), @solutions); +sub place-queen(@indices, @queens, @solutions, $beam-width=2) { + if not @indices { + @solutions.push(@queens); + return; + } + my @best = (for @indices -> $pos {($pos, @indices.grep({is-available($pos, $_)}))}); + if $beam-width ≠ -1 { + @best = find-best($beam-width, @best, {+$^b[1] cmp +$^a[1]}); + } + for @best -> ($pos, @available) { + place-queen(@available, (|@queens, $pos), @solutions, $beam-width); } } @@ -30,6 +45,14 @@ sub indices-to-array(@indices, $n) { } -sub MAIN (Int :$n=2) { - say n-queens-threeD $n; +#| ideally this routine should use a priority queue for better efficiency +sub find-best($n, @elems, &key){ + my @sorted = @elems.sort(&key); + return @sorted[^$n] if +@sorted > $n; + return @sorted; +} + + +sub MAIN (Int :$n=2, Int :$beam=2) { + say n-queens-d3 $n, $beam; } diff --git a/challenge-062/sangeet-kar/raku/ch-2a.raku b/challenge-062/sangeet-kar/raku/ch-2a.raku deleted file mode 100755 index a1a9e78560..0000000000 --- a/challenge-062/sangeet-kar/raku/ch-2a.raku +++ /dev/null @@ -1,58 +0,0 @@ -#!/usr/bin/env raku - -# 1. n-queens-d3 finds the solution using beam search -# 2. the higher the beamr-width, the better is the solution. -# 3. with beam-width=1, it's very fast but the solution may not be optimal maximising the number of queens. -# 4. with beam-width=-1, it searches the entire search space. Ensures best solution but slow as hell for high n -# 5. I think one can find the best solution with beam-width 2-3 for n-values less than 8 - -sub n-queens-d3($n = 2, $beam-width=2) { - my @solutions = []; - place-queen [^$n X ^$n X ^$n], [], @solutions, $beam-width; - my $best = @solutions.max(+*); - say "Queens placed : ", +$best; - return indices-to-array $best, $n; -} - - -sub place-queen(@indices, @queens, @solutions, $beam-width=2) { - if not @indices { - @solutions.push(@queens); - return; - } - my @best = (for @indices -> $pos {($pos, @indices.grep({is-available($pos, $_)}))}); - if $beam-width ≠ -1 { - @best = find-best($beam-width, @best, {+$^b[1] cmp +$^a[1]}); - } - for @best -> ($pos, @available) { - place-queen(@available, (|@queens, $pos), @solutions, $beam-width); - } -} - - -sub is-available($ref, $pos) { - my $diff = ($ref »-« $pos)».abs.Set; - not (+$diff == 1 || (+$diff == 2 && 0 ∈ $diff)) -} - - -sub indices-to-array(@indices, $n) { - my @array = [[[ 0 xx $n] xx $n] xx $n]; - for @indices -> ($x, $y, $z) { - @array[$x; $y; $z] = 1; - } - return @array; -} - - -#| ideally this routine should use a priority queue for better efficiency -sub find-best($n, @elems, &key){ - my @sorted = @elems.sort(&key); - return @sorted[^$n] if +@sorted > $n; - return @sorted; -} - - -sub MAIN (Int :$n=2, Int :$beam=2) { - say n-queens-d3 $n, $beam; -} |