# RabbitFarm

### 2022-08-07

#### Permuted Reversibly

*The examples used here are from the weekly challenge problem statement and demonstrate
the working solution.*

## Part 1

*Write a script to find the smallest integer x such that x, 2x, 3x, 4x, 5x and 6x are
permuted multiples of each other.*

### Solution

```
use strict;
use warnings;
use boolean;
sub is_permuted{
my($x, $y) = @_;
my(@x, @y);
map {$x[$_]++} split(//, $x);
map {$y[$_]++} split(//, $y);
return false if $#x != $#y;
my @matched = grep {(!$x[$_] && !$y[$_]) || ($x[$_] && $y[$_] && $x[$_] == $y[$_])} 0 .. @y - 1;
return true if @matched == @x;
return false;
}
sub smallest_permuted{
my $x = 0;
{
$x++;
redo unless is_permuted($x, 2 * $x) && is_permuted(2 * $x, 3 * $x) &&
is_permuted(3 * $x, 4 * $x) && is_permuted(4 * $x, 5 * $x) &&
is_permuted(5 * $x, 6 * $x);
}
return $x;
}
MAIN:{
print smallest_permuted . "\n";
}
```

### Sample Run

```
$ perl perl/ch-1.pl
142857
```

### Notes

The approach here is to check if any two numbers are permutations of each other by
counting up the digits for each and comparing the counts. A fun use of `map`

and `grep`

but I will admit it is a bit unnecessary. I implemented solutions to this problem in
multiple languages and in doing so just sorted the lists of digits and compared them. Much
easier, but less fun!

## Part 2

*Write a script to find out all Reversible Numbers below 100.*

### Solution

```
use strict;
use warnings;
sub is_reversible{
my($x) = @_;
my @even_digits = grep { $_ % 2 == 0 } split(//, ($x + reverse($x)));
return @even_digits == 0;
}
sub reversibles_under_n{
my($n) = @_;
my @reversibles;
do{
$n--;
unshift @reversibles, $n if is_reversible($n);
}while($n > 0);
return @reversibles;
}
MAIN:{
print join(", ", reversibles_under_n(100)) . "\n";
}
```

### Sample Run

```
$ perl perl/ch-2.pl
10, 12, 14, 16, 18, 21, 23, 25, 27, 30, 32, 34, 36, 41, 43, 45, 50, 52, 54, 61, 63, 70, 72, 81, 90
```

### Notes

My favorite use of Perl is to prototype algorithms. I'll get an idea for how to solve a problem and then quickly prove out the idea in Perl. Once demonstrated to be effective the same approach can be implemented in another language if required, usually for business reasons but also sometimes simply for performance.

The code here is concise, easy to read, and works well. It's also 3 times slower than a Fortran equivalent.

```
$ time perl perl/ch-2.pl
10, 12, 14, 16, 18, 21, 23, 25, 27, 30, 32, 34, 36, 41, 43, 45, 50, 52, 54, 61, 63, 70, 72, 81, 90
real 0m0.069s
user 0m0.048s
sys 0m0.020s
-bash-5.0$ time fortran/ch-2
10
12
14
16
18
21
23
25
27
30
32
34
36
41
43
45
50
52
54
61
63
70
72
81
90
real 0m0.021s
user 0m0.001s
sys 0m0.016s
```

That said, the Fortran took at least 3x longer to write. These are the tradeoffs that get considered on a daily basis!

## References

posted at: 12:16 by: Adam Russell | path: /perl | permanent link to this entry

The Weekly Challenge 176 (Prolog Solutions)

*The examples used here are from the weekly challenge problem statement and demonstrate
the working solution.*

## Part 1

*Write a script to find the smallest integer x such that x, 2x, 3x, 4x, 5x and 6x are
permuted multiples of each other.*

### Solution

```
permuted(X, Y):-
number_chars(X, XChars),
number_chars(Y, YChars),
msort(XChars, XCharsSorted),
msort(YChars, YCharsSorted),
XCharsSorted == YCharsSorted.
permuted_multiple(Permuted):-
current_prolog_flag(max_integer, MAX_INTEGER),
between(1, MAX_INTEGER, X),
X2 is 2 * X,
X3 is 3 * X,
X4 is 4 * X,
X5 is 5 * X,
X6 is 6 * X,
permuted(X, X2), permuted(X2, X3),
permuted(X3, X4), permuted(X4, X5), permuted(X5, X6),
Permuted = X.
```

### Sample Run

```
| ?- permuted_multiple(Permuted).
Permuted = 142857 ?
(2150 ms) yes
```

### Notes

I implemented solutions for this problem in multiple languages and compared side by side on the same system this Prolog solution ran the fastest. I think that's because in Prolog the logic can be (naturally!) expressed very succinctly and so the underlying instructions getting executed are most efficient. Other implementations seem to require a bit more overhead, such as when deconstructing an integer into a list of digits for example.

The task here is for us to generate the smallest integer with this permutable property.
Technically the code here will generate all such numbers, however in search of other
solutions it seems there is just the one found before we exceed the bounds of
`MAX_INTEGER`

.

## Part 2

*Write a script to find out all Reversible Numbers below 100.*

### Solution

```
all_odd([]).
all_odd([H|T]):-
number_chars(Digit, [H]),
M is mod(Digit, 2),
M == 1,
all_odd(T).
reversible(X):-
number_chars(X, XChars),
reverse(XChars, XCharsReversed),
number_chars(R, XCharsReversed),
Sum is X + R,
number_chars(Sum, SumChars),
all_odd(SumChars).
reversible_under_n(N, Reversible):-
between(1, N, X),
reversible(X),
Reversible = X.
```

### Sample Run

```
$ gprolog --consult-file prolog/ch-2.p
| ?- reversible_under_n(100, Reversibles).
Reversibles = 10 ? a
Reversibles = 12
Reversibles = 14
Reversibles = 16
Reversibles = 18
Reversibles = 21
Reversibles = 23
Reversibles = 25
Reversibles = 27
Reversibles = 30
Reversibles = 32
Reversibles = 34
Reversibles = 36
Reversibles = 41
Reversibles = 43
Reversibles = 45
Reversibles = 50
Reversibles = 52
Reversibles = 54
Reversibles = 61
Reversibles = 63
Reversibles = 70
Reversibles = 72
Reversibles = 81
Reversibles = 90
(10 ms) no
```

### Notes

Here we also use Prolog's ability to identify multiple solutions to generate all solutions
less than `100`

, as required.

## References

posted at: 11:54 by: Adam Russell | path: /prolog | permanent link to this entry