# Perl Weekly Challenge 195.

My solutions (task 1 and task 2 ) to the The Weekly Challenge - 195.

# Task 1: Special Integers

```
Submitted by: Mohammad S Anwar
You are given a positive integer, $n > 0.
Write a script to print the count of all special integers between 1 and $n.
An integer is special when all of its digits are unique.
Example 1:
Input: $n = 15
Output: 14 as except 11 all other integers between 1 and 15 are special.
Example 2:
Input: $n = 35
Output: 32 as except 11, 22, 33 all others are special.
```

For small numbers n the solution is simple. I generate all numbers, discard non-specials using a regular expression and count the remaining ones. This yields a oneliner

```
perl -E 'say "$_->", 0+grep {!/^.*(\d).*\1.*$/} (1..$_) for(@ARGV);' 15 35 10000000
```

Results:

```
15->14
35->32
10000000->712890
```

For 10000000 it took about 7s in my laptop and it grows approximately linearly.

For larger inputs I’d rather compute than enumerate the special numbers. Take, for example, the case n=3748. I can divide the problem as follows:

- I first count special numbers from 1 to 9 (9),
- then 10 to 99 (9×9!/(9-1)!=9*9=81),
- from 100 to 999 (9×9!/(9-2)!=9×9×8=648), that is, 648+81+9=738.
- from 1000 to 1999 (9!/(9-3)!=9×8×7=504)
- from 2000 to 2999 (another 504, that is 2×504+738=1746),
- from 3000 to 3099 ((9-1)!/(9-3)!=8×7=56),
- from 3100 to 3199, from 3200 to 3299, 3400 to 3499… 3600 to 3699 (56 each, 6×56=336, that is 336+1746=2082)
- from 3700 to 3709 (7),
- from 3710 to 3719 (another 7),
- from 3720 to 3729 (another 7),
- skip from 3730 to 3739 (that is 3×7+2082=2103),
- from 3740 to 3748 (9-3=6, that is 6+2103=2109).

I can confirm the result with the simplist oneliner,

```
perl -E 'say "$_->", 0+grep {!/^.*(\d).*\1.*$/} (1..$_) for(@ARGV);' 3748
```

Results:

```
3748->2109
```

The corresponding full code follows:

```
1 # Perl weekly challenge 195
2 # Task 1: Special Integers
3 #
4 # See https://wlmb.github.io/2022/12/12/PWC195/#task-1-special-integers
5 use v5.36;
6 use integer;
7 use POSIX qw(lround);
8 say(<<"FIN"), exit unless @ARGV;
9 Usage: $0 N1 [N2...]
10 to get the number of special numbers between 1 and Ni
11 FIN
12 say "$_->", special($_) for @ARGV;
13 sub fact($n){ # factorial
14 my $r=1;
15 $r*=$_ for (1..$n);
16 $r
17 }
18 sub special($n){
19 my $k=0;
20 my $count=0;
21 while($k<=9 && 10**($k+1) < $n){
22 # Count from 1 to 9, then from 10 to 99, then from 100 to 999, etc.
23 $count += 9*fact(9)/fact(9-$k);
24 ++$k;
25 }
26 return $count if $k>9; # Nothing else to do eleven digit numbers or larger
27 #Count from 100.. to q00..-1
28 my $q=lround($n/10**$k);
29 $count += ($q-1)*fact(9)/fact(9-$k);
30 $count += final($q, $k-1, $n); # count from q00... upto $n=qxy...
31 return $count;
32 }
33 sub final($left, $power, $n){ # final approach from left 0 0 0 to n=x y z
34 my $count=0;
35 my $fixed=length $left; # leftward fixed digits
36 my %fixed;
37 ++$fixed{$_} for my @fixed=split '', $left; # actual fixed digits.
38 $_>1 && return 0 for(values %fixed); # nothing to add if fixed part is not special
39 return 1 if $power < 0; # Found last string
40 my $target=substr($n, $fixed, 1); # Next digit
41 for(0..$target-1){ # count upwards to target
42 next if $fixed{$_}; # skip seen digits
43 $count += fact(9-$fixed)/fact(9-$fixed-$power); # add rightwards contribution
44 }
45 $count += final($left.$target, $power-1, $n); # add digit to leftmost and recurse.
46 return $count;
47 }
```

Example:

```
./ch-1.pl 15 35 3748 10000000 1.0e9 1.0e10 1.0e11
```

Results:

```
15->14
35->32
3748->2109
10000000->712890
```

I got the expected results, but much faster. The run above took 0.018s in my laptop and the runtime is almost constant (repeating all the inputs only incremented it by 0.001s).

# Task 2: Most Frequent Even

```
Submitted by: Mohammad S Anwar
You are given a list of numbers, @list.
Write a script to find most frequent even numbers in the list. In case you get more than
one even numbers then return the smallest even integer. For all other case, return -1.
Example 1
Input: @list = (1,1,2,6,2)
Output: 2 as there are only 2 even numbers 2 and 6 and of those 2 appears the most.
Example 2
Input: @list = (1,3,5,7)
Output: -1 since no even numbers found in the list
Example 3
Input: @list = (6,4,4,6,1)
Output: 4 since there are only two even numbers 4 and 6. They both appears the equal
number of times, so pick the smallest.
```

I can filter out even numbers, sort them and shift the most frequent or smaller in a single-liner

```
perl -E '$c{$_}++ for grep {!($_&1)} @ARGV; @e=sort {$c{$b} <=> $c{$a} || $a<=>$b} keys %c;
say join " ", @ARGV, " -> ", @e?shift @e:-1
' 1 1 2 6 2
perl -E '$c{$_}++ for grep {!($_&1)} @ARGV; @e=sort {$c{$b} <=> $c{$a} || $a<=>$b} keys %c;
say join " ", @ARGV, " -> ", @e?shift @e:-1
' 1 3 5 7
perl -E '$c{$_}++ for grep {!($_&1)} @ARGV; @e=sort {$c{$b} <=> $c{$a} || $a<=>$b} keys %c;
say join " ", @ARGV, " -> ", @e?shift @e:-1
' 6 4 4 6 1
```

Results:

```
1 1 2 6 2 -> 2
1 3 5 7 -> -1
6 4 4 6 1 -> 4
```

The full code is almost identical

```
1 # Perl weekly challenge 195
2 # Task 2: Most Frequent Even
3 #
4 # See https://wlmb.github.io/2022/12/12/PWC195/#task-2-most-frequent-even
5 use v5.36;
6 my %count;
7 $count{$_}++ for grep {!($_&1)} @ARGV; # Filter evens and count them
8 my @sorted=sort {$count{$b} <=> $count{$a} || $a<=>$b} keys %count;
9 say join " ", @ARGV, " -> ", @sorted?shift @sorted:-1
```

Example:

```
./ch-2.pl 1 1 2 6 2
./ch-2.pl 1 3 5 7
./ch-2.pl 6 4 4 6 1
```

Results:

```
1 1 2 6 2 -> 2
1 3 5 7 -> -1
6 4 4 6 1 -> 4
```