From c832f51587b689fc12ee0a5943d581b095a6dabf Mon Sep 17 00:00:00 2001 From: Lubos Kolouch Date: Sun, 15 Nov 2020 09:16:45 +0100 Subject: Task 1 Challenge 086 LK refactor --- challenge-086/lubos-kolouch/perl/ch-1.pl | 11 ++++------- challenge-086/lubos-kolouch/python/ch-1.py | 6 ++---- 2 files changed, 6 insertions(+), 11 deletions(-) diff --git a/challenge-086/lubos-kolouch/perl/ch-1.pl b/challenge-086/lubos-kolouch/perl/ch-1.pl index 0603c9b929..232ff30037 100644 --- a/challenge-086/lubos-kolouch/perl/ch-1.pl +++ b/challenge-086/lubos-kolouch/perl/ch-1.pl @@ -22,18 +22,15 @@ sub is_pair_difference { # to avoid sorting and/or scanning through all pairs in the array # or double nested loop, - # I will convert the array to a hash, then check if the - # corresponding key exists + # I will convert the array to a hash and check while creating it my $arr = $$data{n}; my %h; for (@$arr) { - $h{$_} = 1; - } + $h{$_} = 1; - for my $x (keys %h) { - return 1 if $h{$x + $$data{a}}; - } + return 1 if ($h{$_ + $$data{a}}) or ($h{$_ - $$data{a}}); + } return 0; } diff --git a/challenge-086/lubos-kolouch/python/ch-1.py b/challenge-086/lubos-kolouch/python/ch-1.py index 0f284bf4c6..ffeda9b648 100644 --- a/challenge-086/lubos-kolouch/python/ch-1.py +++ b/challenge-086/lubos-kolouch/python/ch-1.py @@ -20,16 +20,14 @@ def is_pair_difference(n: list, a: int): """ # to avoid sorting and/or scanning through all pairs in the array # or double nested loop, - # I will convert the array to a hash, then check if the - # corresponding key exists + # I will convert the array to a hash and check it on the fly """ hash_keys = {} for number in n: hash_keys[number] = 1 - for x in hash_keys: - if hash_keys.get(x+a, 0): + if hash_keys.get(number+a, 0) or hash_keys.get(number-a, 0): return 1 return 0 -- cgit From 511eb99576ca0a476fb3a06aad049929ba04f601 Mon Sep 17 00:00:00 2001 From: Lubos Kolouch Date: Sun, 15 Nov 2020 14:39:35 +0100 Subject: Challenge 086 Task 2 Perl Pyton LK --- challenge-086/lubos-kolouch/perl/ch-2.pl | 193 +++++++++++++++++++++++++++++ challenge-086/lubos-kolouch/python/ch-2.py | 145 ++++++++++++++++++++++ 2 files changed, 338 insertions(+) create mode 100644 challenge-086/lubos-kolouch/perl/ch-2.pl create mode 100644 challenge-086/lubos-kolouch/python/ch-2.py diff --git a/challenge-086/lubos-kolouch/perl/ch-2.pl b/challenge-086/lubos-kolouch/perl/ch-2.pl new file mode 100644 index 0000000000..0ae85439ba --- /dev/null +++ b/challenge-086/lubos-kolouch/perl/ch-2.pl @@ -0,0 +1,193 @@ +#!/usr/bin/perl +#=============================================================================== +# +# FILE: ch-2.pl +# +# USAGE: ./ch-2.pl +# +# DESCRIPTION: Perl Weekly Challenge 086 +# Task 2 +# Sudoku Puzzle +# +# Uses backtrack algorithm +# +# AUTHOR: Lubos Kolouch +# CREATED: 11/15/2020 01:27:06 PM +#=============================================================================== + +use strict; +use warnings; +use Storable qw/dclone/; # for deep copy of the puzzle... + +sub load_puzzle { + # load the puzzle from the input + + my $data = shift; + + my @puzzle; + my $i=0; + for (@$data) { + + my $j = 0; + for (split(' ', @$data[$i])) { + if ($_ eq '_') { + $puzzle[$i][$j] = 0 ; + } else { + $puzzle[$i][$j] = $_ + 0; + } + $j++; + } + $i++; + } + + return \@puzzle; +} + +sub get_valid_options { + # eliminate numbers 1-9 that are already taken + + my $param = shift; + + my %valid_options; + + $valid_options{$_} = 1 for (1..9); + + # eliminate already taken numbers + for (0..8) { + next unless $param->{puzzle}[ $param->{row} ][$_]; + delete $valid_options{ $param->{puzzle}[ $param->{row} ][$_]}; + } + + for (0..8) { + next unless $param->{puzzle}[ $_ ][ $param->{col}]; + delete $valid_options{ $param->{puzzle}[ $_ ][$param->{col}]}; + } + + return unless keys %valid_options; + + # eliminate quadrant + + my $row_q = int($param->{row} / 3); + my $col_q = int($param->{col} / 3); + + for my $row (0..2) { + for my $col (0..2) { + my $row_pos = $row_q * 3 + $row; + my $col_pos = $col_q * 3 + $col; + + delete $valid_options{ $param->{puzzle}[$row_pos][$col_pos] } if $param->{puzzle}[$row_pos][$col_pos]; + + } + } + return unless keys %valid_options; + return \%valid_options; + +} + +sub is_complete { + my $puzzle = shift; + + for my $i (0..scalar @$puzzle -1) { + for my $j (0..scalar @$puzzle -1) { + return unless $$puzzle[$i][$j]; + } + } + + return 1; +} +sub solve_position { + # backtrack recursively to find the solution + + my $puzzle = shift; + + # i was struggling to get a deep copy of the ref-ed array, so... + my $next_puzzle = dclone( $puzzle ); + + for my $row (0..scalar @$next_puzzle -1) { + for my $col (0..scalar @$next_puzzle -1) { + + # find the next empty position + next if $$next_puzzle[$row][$col]; + + my $valid_options = get_valid_options( { puzzle => $next_puzzle, row => $row, col => $col } ); + + unless (keys %$valid_options) { + # nothing left to try, check if the solution is complete + + return unless is_complete($next_puzzle); + + + return $next_puzzle; + } + + my @hash_keys = keys %$valid_options; + + # iterate through the candidate numbers + + for my $next_key (@hash_keys) { + $$next_puzzle[$row][$col] = $next_key; + + my $next_iteration = solve_position($next_puzzle); + return $next_iteration if $next_iteration; + } + } + + } + # great, we could fill all empty positions! + return $next_puzzle; + +} + +sub print_puzzle { + my $puzzle = shift; + + for my $row (0..scalar @$puzzle -1) { + for my $col (0..scalar @$puzzle -1) { + print $$puzzle[$row][$col]." "; + } + print "\n"; + } + print "\n"; +} + +sub solve_sudoku { + my $data = shift; + + my $puzzle = load_puzzle($data); + + my $position; + + $position = solve_position($puzzle); + print_puzzle($position); + + return $position; +} + +use Test::More; + +is_deeply(solve_sudoku( [ +'_ _ _ 2 6 _ 7 _ 1', +'6 8 _ _ 7 _ _ 9 _', +'1 9 _ _ _ 4 5 _ _', +'8 2 _ 1 _ _ _ 4 _', +'_ _ 4 6 _ 2 9 _ _', +'_ 5 _ _ _ 3 _ 2 8', +'_ _ 9 3 _ _ _ 7 4', +'_ 4 _ _ 5 _ _ 3 6', +'7 _ 3 _ 1 8 _ _ _' ] ), + +[ +[4,3,5,2,6,9,7,8,1], +[6,8,2,5,7,1,4,9,3], +[1,9,7,8,3,4,5,6,2], +[8,2,6,1,9,5,3,4,7], +[3,7,4,6,8,2,9,1,5], +[9,5,1,7,4,3,6,2,8], +[5,1,9,3,2,6,8,7,4], +[2,4,8,9,5,7,1,3,6], +[7,6,3,4,1,8,2,5,9], +] +); + +done_testing; + diff --git a/challenge-086/lubos-kolouch/python/ch-2.py b/challenge-086/lubos-kolouch/python/ch-2.py new file mode 100644 index 0000000000..f827eec8d6 --- /dev/null +++ b/challenge-086/lubos-kolouch/python/ch-2.py @@ -0,0 +1,145 @@ +#!env python +""" +#=============================================================================== +# +# FILE: ch-2.py +# +# USAGE: ./ch-2.py +# +# DESCRIPTION: Perl Weekly Challenge 086 +# Task 2 +# Sudoku Puzzle +# +# Uses backtrack algorithm +# +# AUTHOR: Lubos Kolouch +# CREATED: 11/15/2020 01:27:06 PM +#=============================================================================== +""" + +import re +from copy import deepcopy + + +def load_puzzle(puzzle_input): + """ load the puzzle from the input """ + + puzzle = [] + for row in puzzle_input: + row = re.sub("_", "0", row) + + puzzle.append(list(map(int, row.split(' ')))) + + return puzzle + + +def get_valid_options(puzzle, row, col): + """ eliminate numbers 1-9 that are already taken """ + + valid_options = {} + + for i in range(10): + valid_options[i] = 1 + + # eliminate already taken numbers + for i in range(9): + try: + del valid_options[puzzle[row][i]] + except: + pass + + for i in range(9): + try: + del valid_options[puzzle[i][col]] + except: + pass + + if not valid_options: + return + + # eliminate quadrant + + for row_shift in range(3): + for col_shift in range(3): + row_pos = row // 3 * 3 + row_shift + col_pos = col // 3 * 3 + col_shift + + try: + del valid_options[puzzle[row_pos][col_pos]] + except: + pass + + return valid_options + + +def solve_position(puzzle_input): + # backtrack recursively to find the solution + + next_puzzle = deepcopy(puzzle_input) + + for row, row_data in enumerate(next_puzzle): + for col, item in enumerate(row_data): + + if item != 0: + continue + + valid_options = get_valid_options(puzzle=next_puzzle, row=row, col=col) + + if not valid_options: + # nothing left to try, check if the solution is complete + + for test_row in next_puzzle: + for test_item in test_row: + if item == 0: + return + + return next_puzzle + + for next_key in valid_options: + next_puzzle[row][col] = next_key + + next_iteration = solve_position(deepcopy(next_puzzle)) + + if next_iteration: + return next_iteration + + # great, we could fill all empty positions! + return next_puzzle + + +def print_puzzle(puzzle): + """ print the puzzle """ + + for row in puzzle: + print(' '.join(list(map(str, row)))) + print() + + +def solve_sudoku(puzzle): + """ let's solve the puzzle! """ + + puzzle = load_puzzle(puzzle) + print_puzzle(puzzle) + solution = solve_position(puzzle) + print_puzzle(solution) + return solution + + +assert solve_sudoku(['_ _ _ 2 6 _ 7 _ 1', + '6 8 _ _ 7 _ _ 9 _', + '1 9 _ _ _ 4 5 _ _', + '8 2 _ 1 _ _ _ 4 _', + '_ _ 4 6 _ 2 9 _ _', + '_ 5 _ _ _ 3 _ 2 8', + '_ _ 9 3 _ _ _ 7 4', + '_ 4 _ _ 5 _ _ 3 6', + '7 _ 3 _ 1 8 _ _ _']) == [ + [4, 3, 5, 2, 6, 9, 7, 8, 1], + [6, 8, 2, 5, 7, 1, 4, 9, 3], + [1, 9, 7, 8, 3, 4, 5, 6, 2], + [8, 2, 6, 1, 9, 5, 3, 4, 7], + [3, 7, 4, 6, 8, 2, 9, 1, 5], + [9, 5, 1, 7, 4, 3, 6, 2, 8], + [5, 1, 9, 3, 2, 6, 8, 7, 4], + [2, 4, 8, 9, 5, 7, 1, 3, 6], + [7, 6, 3, 4, 1, 8, 2, 5, 9], ] -- cgit