RogerBW's Blog

I’ve been doing the Weekly Challenges. The latest involved an unusual sort and a pathfinding problem. (Note that this is open until 23 April 2023.)

Task 1: Fun Sort

You are given a list of positive integers.

Write a script to sort the all even integers first then all odds in ascending order.

Normally for something like this I'd use a filter, grep or similar structure, but in this case I need to build two separate lists.

Raku shows off its rich core library:

sub funsort(@l0) {
    my %h = classify { $_ %% 2 ?? 'even' !! 'odd' }, @l0.sort();
    my @a;
    for ("even", "odd") -> $mode {
        if (%h{$mode}) {
            @a.append(%h{$mode}.List);
        }
    }
    return @a;
}

while in the other languages it was easier to be explicit, as in Python:

def funsort(l0):
  l = l0
  l.sort()
  a = []
  b = []
  for k in l:
    if k % 2 == 0:
      a.append(k)
    else:
      b.append(k)
  a.extend(b)
  return a

Task 2: Shortest Route

You are given a list of bidirectional routes defining a network of nodes, as well as source and destination node numbers.

Write a script to find the route from source to destination that passes through fewest nodes.

I've done Dijkstra before, but this time I did a simple exhaustive search without repetition. Using a breadth-first search guarantees that the first path found is a shortest path (because all length N paths are tested before any length N+1 paths), so we exit at that point.

Sets (which I think of as contentless hashes) are great. But Lua, Perl and PostScript don't have them, so I ended up using a hash and ignoring the value part.

Python, Rust and Ruby have set difference operators and I was able to use them. Raku does too, but I didn't manage to get that one to work.

In Rust and Python I carried a set of unused nodes along with the path-to-date, trading off memory to get a little more speed. In the other languages this was trickier, and I just worked it up on the fly. Here's the Rust.

fn shortestroute(r0: Vec<Vec<u32>>, origin: u32, destination: u32) -> Vec<u32> {

This goes in two stages. First, break down the input into a list of possible exits from each node. (Specifically, a map from each node to a set of exits.)

    let mut r: HashMap<u32, HashSet<u32>> = HashMap::new();
    for rt in r0 {
        for rp in rt.windows(2) {
            r.entry(rp[0])
                .and_modify(|s| {
                    (*s).insert(rp[1]);
                })
                .or_insert(HashSet::from([rp[1]]));
            r.entry(rp[1])
                .and_modify(|s| {
                    (*s).insert(rp[0]);
                })
                .or_insert(HashSet::from([rp[0]]));
        }
    }

Then, starting at the origin, build paths that go to to each exit, and do this repeatedly until we reach the destination. This is a fairly standard breadth-first search framework as I've used in many previous PWC entries.

    let mut out = Vec::new();
    let mut stack = VecDeque::new();
    stack.push_back((vec![origin], HashSet::from([origin])));
    while stack.len() > 0 {
        let s = stack.pop_front().unwrap();
        let l = s.0.last().unwrap();
        if *l == destination {
            out = s.0;
            break;
        } else {
            for pd in r.get(&l).unwrap().difference(&s.1) {
                let mut q = s.clone();
                q.0.push(*pd);
                q.1.remove(pd);
                stack.push_back(q);
            }
        }
    }
    out
}

Full code on github.