# RabbitFarm

### 2022-11-20

#### Twice Largest Once Cute

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

## Part 1

You are given list of integers, @list. Write a script to find out whether the largest item in the list is at least twice as large as each of the other items.

### Solution

``````
use v5.36;
use strict;
use warnings;

sub twice_largest{
my(@list_integers) = @_;
my @sorted_integers = sort {\$a <=> \$b} @list_integers;
for my \$i (@sorted_integers[0 .. @sorted_integers - 1]){
unless(\$sorted_integers[@sorted_integers - 1] == \$i){
return -1 unless \$sorted_integers[@sorted_integers - 1] >= 2 * \$i;
}
}
return 1;
}

MAIN:{
say twice_largest(1, 2, 3, 4);
say twice_largest(1, 2, 0, 5);
say twice_largest(2, 6, 3, 1);
say twice_largest(4, 5, 2, 3);
}
``````

### Sample Run

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

### Notes

For Part 1 I at first couldn't see how to avoid a basic O(n^2) nested for loop. After I took a nap I think the best approach is what I have here:

1. sort the list O(n log n)

2. get the max element from the sorted list O(1)

3. iterate over the sorted list, stop and return false if at any point an element times two is not less then max. return true if all elements (other than \$max itself) pass the test. O(n)

So total worst case dominated by the sort O(n log n).

(And the nap was required because I was on an overnight camping trip with my son's Cub Scout pack the previous day and barely slept at all!)

## Part 2

You are given an integer, 0 < \$n <= 15. Write a script to find the number of orderings of numbers that form a cute list.

### Solution

``````
use v5.36;
use strict;
use warnings;

use Hash::MultiKey;

sub cute_list{
my(\$n) = @_;
my %cute;
tie %cute, "Hash::MultiKey";
for my \$i (1 .. \$n){
\$cute{[\$i]} = undef;
}
my \$i = 1;
{
\$i++;
my %cute_temp;
tie %cute_temp, "Hash::MultiKey";
for my \$j (1 .. \$n){
for my \$cute (keys %cute){
if(0 == grep {\$j == \$_} @{\$cute}){
if(0 == \$j % \$i || 0 == \$i % \$j){
\$cute_temp{[@{\$cute}, \$j]} = undef;
}
}
}
}
%cute = %cute_temp;
untie %cute_temp;
redo unless \$i == \$n;
}
return keys %cute;
}

MAIN:{
say cute_list(2) . q//;
say cute_list(3) . q//;
say cute_list(5) . q//;
say cute_list(10) . q//;
say cute_list(11) . q//;
say cute_list(15) . q//;
}
``````

### Sample Run

``````
\$ perl perl/ch-2.pl
2
3
10
700
750
24679
``````

### Notes

This solution with a dynamic programming style approach seems to work pretty well. cute(11) runs in less than a second (perl 5.34.0, M1 Mac Mini 2020) which is pretty good compared to some other reported run times that have been posted to social media this week.

Some may notice that the solution here bears a striking resemblance to the one for TWC 117! The logic there was a bit more complicated, since multiple paths could be chosen. The overall idea is the same though: as we grow the possible lists we are able to branch and create new lists (paths).

## References

Challenge 191

posted at: 21:50 by: Adam Russell | path: /perl | permanent link to this entry

#### The Weekly Challenge 191 (Prolog Solutions)

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

## Part 1

You are given an encoded string consisting of a sequence \$s of numeric characters: 0..9. Write a script to find the all valid different decodings in sorted order.

### Solution

``````
twice_greater(X, Y, TwiceGreater):-
X \== Y,
TwiceY is 2 * Y,
X >= TwiceY,
TwiceGreater = -1.
twice_greater(X, Y, TwiceGreater):-
TwiceY is 2 * Y,
X < TwiceY,
TwiceGreater = 1.

twice_largest(List):-
max_list(List, Max),
maplist(twice_greater(Max), List, TwiceGreater),
delete(TwiceGreater, -1, TwiceGreaterOneDeleted),
length(TwiceGreaterOneDeleted, TwiceGreaterOneDeletedLength),
TwiceGreaterOneDeletedLength == 1, !.
``````

### Sample Run

``````
\$ gprolog --consult-file prolog/ch-2.p
| ?- twice_largest([1, 2, 3, 4]).

no
| ?- twice_largest([1, 2, 0, 5]).

yes
| ?- twice_largest([2, 6, 3, 1]).

yes
| ?- twice_largest([4, 5, 2, 3]).

no
``````

### Notes

There are a few ways one could approach this problem. I thought this implementation was nice and concise, albeit unconventional. `maplist/3` is used to generate a list with entries corresponding to whether or not the respective element, times two, in the original List was more or less than the List Max. If we find only one element fails this, the List Max itself, then `twice_largest/1` is true.

## Part 2

You are given an integer, 0 < \$n <= 15. Write a script to find the number of orderings of numbers that form a cute list.

### Solution

``````
cute(_, _) --> [].
cute(N, CuteList) --> [X], {between(1, N, X), \+ member(X, CuteList),
length(CuteList, CuteListLength),
succ(CuteListLength, I),
(0 is mod(X, I); 0 is mod(I, X)),
append(CuteList, [X], CuteListUpdated)},
cute(N, CuteListUpdated).

main:-
N = 15,
findall(Cute, (length(Cute, N), phrase(cute(N, []), Cute)), C),
sort(C, CuteList),
length(CuteList, NumberCuteList),
write(NumberCuteList), nl.
``````

### Sample Run

``````
\$ gprolog --consult-file prolog/ch-2.p
| ?- main.
24679
``````

### Notes

This is a somewhat convoluted use of a DCG and, in turn, the DCG code itself might be a bit convoluted. Here the DCG will generate all lists which conform to the given rules. There ends up being some duplication which is natural given the condition. To remove the duplicates I `sort/2` the results.

## References

Challenge 191

posted at: 16:05 by: Adam Russell | path: /prolog | permanent link to this entry