The Weekly Challenge 036

VIN Validation and Knapsack Problem

Solutions on GitHub

Task 1: VIN Validation

Write a program to validate a given Vehicle Identification Number (VIN).

Logic

Utilize modules like Data::Validate::VIN (in Perl) or vininfo (in Python) to cleanly validate the input VIN string according to standard check digit calculation rules.

Perl Solution

ch-1.pl

use Data::Validate::VIN; my $vin = $ARGV[0] // die 'Usage: ch-1.pl vin_code'; my $vv = Data::Validate::VIN->new($vin); if ( $vv->valid() ) { say 'valid'; } else { say "ERROR: $_" for @{ $vv->errors() }; }

Python Solution

ch-1.py

from vininfo import Vin try: vin = Vin(sys.argv[1]) pprint(vin.annotate()) except Exception as e: print('Error: %s' % e) sys.exit(1)

Task 2: Knapsack Problem

Write a program to solve the Knapsack Problem. Find the optimal combination of 5 boxes (R, B, G, Y, P) with varying weights and values to maximize value while keeping total weight under or equal to 15 kg.

Example Output

Best combination for 1 boxes is P with value 10 Best combination for 2 boxes is P B with value 12 Best combination for 3 boxes is G P B with value 14 Best combination for 4 boxes is G P B R with value 15 There is no possible combination for 5 boxes under or equal weight 15

Logic

Use combination helpers (like Math::Combinatorics in Perl or itertools.combinations in Python) to iterate over all possible box subsets. For each subset, compute the sum of weights and values. Keep track of the subset that maximizes the value without exceeding the 15 kg threshold.

Perl Solution

ch-2.pl

use Math::Combinatorics; my $combinat = Math::Combinatorics->new( count => $count, data => [@list], ); while ( my @combo = $combinat->next_combination ) { my $boxes = join( ' ', @combo ); my $val = calculate_value(\@combo); if ($val > $max_value) { $max_value = $val; $max_boxes = $boxes; } }

Python Solution

ch-2.py

from itertools import combinations for comb in combinations(list, count): val = calculate_value(comb) if (val > max_value): max_value = val max_boxes = str(comb)