# RogerBW's Blog

The Weekly Challenge 284: Lucky Relative 01 September 2024

I’ve been doing the Weekly Challenges. The latest involved a list search and an unusual sort. (Note that this ends today.)

You are given an array of integers, `@ints`.

Write a script to find the lucky integer if found otherwise return `-1`. If there are more than one then return the largest.

A lucky integer is an integer that has a frequency in the array equal to its value.

I got lazy with this. In Perl:

``````sub luckyinteger(\$a) {
``````

Build a freqency count.

``````  my %c;
map {\$c{\$_}++} @{\$a};
``````

Get descending-sorted lists of keys and values.

``````  my @c1 = reverse sort values %c;
my @c2 = reverse sort keys %c;
``````

For each value starting with the largest,

``````  foreach my \$v1 (@c1) {
``````

For each key starting with the largest,

``````    foreach my \$v2 (@c2) {
``````

If the key's lookup equals the value, and the key equals the value, this is the one we want.

``````      if (\$c{\$v2} == \$v1 && \$v1 == \$v2) {
return \$v2;
}
}
}
return -1;
}
``````

Would have been better, in retrospect, to pull out only those values where `k == v` and take the largest, but I didn't think of it. Never mind. Rust's `counter` crate is easiest:

``````use counter::Counter;

fn luckyinteger(a: Vec<usize>) -> i32 {
let c = a.into_iter().collect::<Counter<_>>();
for pair in c.most_common_tiebreaker(|&a, &b| b.cmp(&a)) {
if pair.0 == pair.1 {
return pair.0 as i32;
}
}
-1
}
``````

You are given two list of integers, `@list1` and `@list2`. The elements in the `@list2` are distinct and also in the `@list1`.

Write a script to sort the elements in the `@list1` such that the relative order of items in `@list1` is same as in the `@list2`. Elements that is missing in `@list2` should be placed at the end of `@list1` in ascending order.

I used a counter for this one too. Python:

``````from collections import defaultdict

def relativesort(list1, list2):
``````

Build a frequency count of `list1`.

``````  c = defaultdict(lambda: 0)
for n in list1:
c[n] += 1
``````

Set up the output list.

``````  out = []
``````

Push into it a number of copies of the item in `list2` equal to its count in `list1`. Remove that item from the counter. (Which is a reason to use a defaultdict, other than simplifying the counter code; if the item doesn't appear in list1, the counter value will be zero and nothing will be added.)

``````  for i in list2:
out.extend([i] * c[i])
del c[i]
``````

What's left is the counts of items in `list1` that weren't in `list2`. Sort them and do the same thing.

``````  d = sorted(c.keys())
for i in d:
out.extend([i] * c[i])
return out
``````

Full code on github.