RogerBW's Blog

Perl Weekly Challenge 76: prime sum and word search 03 September 2020

I’ve been doing the Perl Weekly Challenges. The latest involved summing primes and performing a word search.

TASK #1 › Prime Sum

You are given a number $N. Write a script to find the minimum number of prime numbers required, whose summation gives you $N.

For the sake of this task, please assume 1 is not a prime number.

Er, yes, well, since literally by definition it isn't…

Anyway, back to the FIFO buffer mine. I assume that one can't re-use a single prime.

sub psum {
  my $n=shift;

Generate a bunch of prime numbers.

  my %pr=map {$_ => 1} (2..$n);
  foreach my $m (2..$n) {
    foreach my $mi (2..$n) {
      delete $pr{$m*$mi};
    }
  }

Give myself forward and reverse mapped lists of them (largest first).

  my @p=sort {$b <=> $a} keys %pr;
  my %pi=map {$p[$_] => $_} (0..$#p);

Now do the FIFO buffer thing, pushing all the possible candidate numbers onto the end of the list if we haven't reached the target yet.

  my @c=([]);
  my @o;
  while (my $r=shift @c) {
    my $s=$n;
    if (@{$r}) {
      $s-=sum(map {$p[$_]} @{$r});
    }
    if ($s>0) {
      my %ru=map {$_ => 1} @{$r};
      foreach my $ci (grep {!exists $ru{$_}} map {$pi{$_}} grep {$_ <= $s} @p) {
        push @c,[@{$r},$ci];
      }

The first solution found has the minimum number of values. (There can be multiple solutions; for example, 20 = 17+3 = 13+7.)

    } elsif ($s==0) {
      @o=map {$p[$_]} @{$r};
      last;
    }
  }
  return scalar @o;
}

I tried implementing this algorithm in Raku, but gave up because of it ongoing problem with lists of lists. @c is a list; each element of it is also a list. I pull a list off it, then want to push onto it a bunch of new lists, each consisting of a copy of the one I pulled plus one new element. I have found no formulation that doesn't instead end up pushing (old-list-object-copy, new-element). I'm sure it's terribly helpful for whoever Raku's intended users are, but this is one of my two huge frustrations with the language.

So instead I used combinations: generate the list of primes, generate each possible selection of primes from the list, then choose only the ones that have the right sum. Since I start with the largest numbers, the shortest lists should come first.

sub psum($n) {
  my @p=reverse grep {is-prime($_)}, (2..$n);
  my @s=grep {sum(@($_))==$n}, @p.combinations(1..@p.elems);
  return @s[0].elems;
}

On to Python. Looks as if its lists are a bit closer to the raw C, because there's a special object type if you want to pull stuff off the front of a list with some efficiency. And the prime number generation uses a set, because I was frustrated after not being able to use a SetHash in Raku. The code is otherwise the same as Perl, though given that the addition of new elements was the bit in Raku that didn't work I laid out it out with a temporary variable just to be sure.

(Python also has a combinations but I didn't use it.)

from collections import deque

def psum(n):
    pr=set(range(2,n+1))
    for m in range(2,n+1):
        for mi in range(2,n+1):
            pr.discard(m*mi)
    p=list(pr)
    p.sort(reverse=True)
    pi=dict()
    for i in range(0,len(p)):
        pi[p[i]]=i
    c=deque()
    o=list()
    while True:
        r=list()
        s=n
        if len(c)>0:
            r=c.popleft()
            s-=sum(p[i] for i in r)
        if (s>0):
            ru=set(r)
            ca=set(pi[i] for i in p if i<=s)
            ca-=ru
            for i in ca:
                q=r.copy()
                q.append(i)
                c.append(q)
        elif (s==0):
            o=[p[i] for i in r]
            break
    return len(o)

TASK #2 › Word Search

Write a script that takes two file names. The first file would contain word search grid as shown below. The second file contains list of words, one word per line. You could even use local dictionary file.

Print out a list of all words seen on the grid, looking both orthogonally and diagonally, backwards as well as forwards.

There's a bit more meat to this one. The approach I took was to break down the puzzle grid into lists of search strings: horizontal, vertical, downward-right diagonal, downward-left diagonal, each in forward and reverse. Then I test each candidate word against each of those search strings.

use List::Util qw(max);

my $minlen=5;

my $y;
my @grid;
my @searchspaces;
open I,'<',$ARGV[0] or die "Can't open puzzle file\n";
while (<I>) {
  chomp;
  s/ +//g;
  $_=lc($_);
  if (defined $y) {
    if ($y != length($_)) {
      die "Not a rectangular grid\n";
    }
  } else {
    $y = length($_);
  }
  push @searchspaces,$_;
  push @grid,[split '',$_];
  push @searchspaces,join('',reverse(@{$grid[-1]}));
}
close I;
my $x=scalar @grid;

@grid now contains the puzzle as individual letters, and we've added the horizontal components to the search space. Now the verticals:

foreach my $i (0..$y-1) {
  my @q=map {$grid[$_][$i]} (0..$x-1);
  push @searchspaces,join('',@q);
  push @searchspaces,join('',reverse @q);
}

And the diagonals, down-right and down-left. This is probably more complicated than it needs to be.

{
  my $mxy=max($x,$y)-1;
  foreach my $xi (-$y+$minlen-1..$x-$minlen+1) {
    my @seq=map {[$xi+$_,$_]} grep {$xi+$_>=0 && $xi+$_<$x && $_<$y} (0..$mxy);
    if (scalar @seq >= $minlen) {
      my @q=map {$grid[$_->[0]][$_->[1]]} @seq;
      push @searchspaces,join('',@q);
      push @searchspaces,join('',reverse @q);
    }
  }
  foreach my $xi (-$y+$minlen-1..$x-$minlen+1) {
    my @seq=map {[$xi+$_,$y-$_]} grep {$xi+$_>=0 && $y-$_>=0 && $xi+$_<$x} (1..$mxy);
    if (scalar @seq >= $minlen) {
      my @q=map {$grid[$_->[0]][$_->[1]]} @seq;
      push @searchspaces,join('',@q);
      push @searchspaces,join('',reverse @q);
    }
  }
}

Now we just go through the word list looking for each word's presence in the search space.

my @found;
open I,'<',$ARGV[1] or die "Can't open wordlist file\n";
while (<I>) {
  chomp;
  if (length($_) >= $minlen) {
    my $w=lc($_);
    foreach my $ss (@searchspaces) {
      if (index($ss,$w) > -1) {
        push @found,$w;
        last;
      }
    }
  }
}
close I;

print join(', ',sort @found),"\n";

Raku is similar; lists of strings are within its capabilities, and even (in @grid) lists of lists that don't change. length turns to chars, and various small details differ, but nothing serious.

In Python I discovered the lovely argparse library.

import argparse
import sys

minlen=5
grid=list()
searchspaces=list()
y=0

parser = argparse.ArgumentParser(description='Process some integers.')
parser.add_argument('puzzle', type=argparse.FileType('r'),
                    help='the puzzle file')
parser.add_argument('wordlist', type=argparse.FileType('r'),
                    help='the wordlist file')
args = parser.parse_args()

And that checks for file existence and gives me back two readable handles. (Granted, I'm cargo-culting how to read them rather than looking it up properly.) Rather than squashing all the spaces and splitting on characters, this time I split on "words" (i.e. spaces).

for lino, line in enumerate(args.puzzle, start=1):
    q=line.rstrip().lower().split()
    if (y>0):
        if (y != len(q)):
            sys.exit("Not a rectangular grid")
    else:
        y=len(q)
    grid.append(q)
    searchspaces.append(''.join(q))
    searchspaces.append(''.join(reversed(q)))
x=len(grid)

Vertical search elements.

for i in range(0,y):
    q=[grid[j][i] for j in range(0,x)]
    searchspaces.append(''.join(q))
    searchspaces.append(''.join(reversed(q)))

Diagonal search elements. As usual, list comprehension replaces Perl's map and grep. (Python has those too, but they don't seem to be used much.)

mxy=max(x,y)
for xi in range(-y+minlen-1,x-minlen+1):
    seq=[[xi+i,i] for i in range(0,mxy) if xi+i>=0 and xi+i<x and i<y]
    if (len(seq) >= minlen):
        q=[grid[i[0]][i[1]] for i in seq]
        searchspaces.append(''.join(q))
        searchspaces.append(''.join(reversed(q)))
for xi in range(-y+minlen-1,x-minlen+1):
    seq=[[xi+i,y-i] for i in range(1,mxy) if xi+i>=0 and y-i>=0 and xi+i<x]
    if (len(seq) >= minlen):
        q=[grid[i[0]][i[1]] for i in seq]
        searchspaces.append(''.join(q))
        searchspaces.append(''.join(reversed(q)))

And check the individual words.

found=list()

for lino, line in enumerate(args.wordlist, start=1):
    w=line.rstrip().lower()
    if (len(w) >= minlen):
        for ss in searchspaces:
            if (w in ss):
                found.append(w)
                break

found.sort()
print(', '.join(found))

All that's left is timing. On the example 16×19 puzzle, with the SOWPODS word list of 267,751 entries (260,881 of them five or more characters), running each program twice on an unloaded machine and timing the second run:

  • Perl took 4.069 seconds.
  • Python took 4.098 seconds.
  • Raku took 25.485 seconds.

Yeah. That's the other huge frustration with Raku.


  1. Posted by RogerBW at 01:28pm on 03 September 2020

    A friend told me that some Raku enthusiast on Twitter thinks I'm "only trying to solve the challenges in Raku to be able to moan about it". Thanks for the insult, and it's so nice of you to say this in a medium which I don't read and in which I cannot reply rather than, say, here.

    When I started doing these challenges in Raku it was still calling itself Perl 6 and I really liked what the language was doing. I still like what the language is doing. But it's still got this weirdness about lists of lists that I genuinely do not understand (maybe it's in a book somewhere? Or on someone's web page? It's not in the documentation, I've had no luck searching for it, and no Raku user has ever bothered to engage with any of the posts here except to tell me not to call it Perl6 any more), and it's still desperately slow.

    (I will be fair and admit a mistake: I've just tried to build a minimal example to file a bug report, and what I thought was the inability of the interpreter to break out of an inner loop turns out to be an objection to using the word "OUTER" as a label, because OUTER is a reserved word. Clearly it's my fault that I did not immediately understand this from the error message.)

    Cannot resolve caller last(OUTER:U); none of these signatures match:
        ( --> Nil)
        (Label:D \x --> Nil)
    

    Apart from those problems it's a very nice language. It lets me do Perlish things while I'm increasing my fluency with its native forms, and has really interesting operators (like classify/categorize, pick, or indeed combinations – just look at the length and ease of comprehension of that Raku code in this week's #1 compared with the Perl).

    If you want to see a moan, though, try this: other than these tasks which invite specifically Raku solutions, there's currently no compelling reason for me to reach for Raku to solve a problem. What's the language for? Rust has safety and compilability, though it does my head in; Perl has CPAN and the advantage of my knowing it very well; Python has a standard library at least as good as Raku's, PyPI, and most of the language sophistication; and all of them have speed. Is there some problem domain in which Raku is better? I wanted to love this language, but it doesn't seem to have much to offer except "you're doing it wrong", and apparently that's the attitude of its enthusiasts too.

    (Just be aware that when you read "The entries for Challenge 75 that have Raku solutions" on the Rakudo blog that actually means "The entries for Challenge 75 that have Raku solutions written by people who can see no flaws in the language".)

  2. Posted by Owen Smith at 07:06pm on 04 September 2020

    This is the first I'd heard of Perl 6 being renamed Raku. And if they're so up themselves all they do is complain about your misnaming it then that tells you the value of the language.

    I have similar issues with Python. Enthusiasts for it go on about needing to use Pythonic solutions while failing to explain what that sort of thing is, and complaining at any use of Python 2 because that is now deprecated. Given that Python 3 has move further away from C I'm more likely to use Python 2 when I have a need.

  3. Posted by RogerBW at 07:32pm on 04 September 2020

    There are many interesting things about Raku, but it's not meaningfully a development of Perl 5 any more and I assume this is why the name was changed. (The formal proposal for that change seems to be here.)

    If I had to do things with C-like speed (which I very rarely do) but wanted a better language for it, I'd be looking at Rust. I've done a bit with it, but I'm not at all fluent yet.

    So far I'm very much enjoying solving these problems in Python. Even though it doesn't look much like Perl, it flows easily to my Perl-using mind. (More so than Raku? Hard to say; my early Raku programs tended to fail because I assumed a Perl-like syntax would work, while in Python I know I'll need to look it up.)

  4. Posted by Owen Smith at 12:19am on 05 September 2020

    My experience is all of these interpreted languages drive me nuts. It is infuriating that a syntax error in one part of the code is only exposed when that part finally gets executed, whenever that may be.

    At work our test system is written in Python, now a bastardised hybrid that will run under Python 2 or 3. I've spent the past 5 years mostly avoiding writing any tests precisely because it is in Python. I know this is bad but every time I try I get so badly bitten I slink off and hide from the test system for another 6 months. Python just works in a way that is orthogonal to my mental processes. I find writing assembler easy frankly.

  5. Posted by RogerBW at 11:17am on 07 September 2020

    Quick review of other people's solutions to these tasks:

    The primes problem didn't specify whether repetition of numbers was allowed; I assumed it wasn't, while others disagreed. Some people used recursion to build the list rather than a FIFO. Some also pointed out that Goldbach's Conjecture allows you to answer "at most 2 if even, 3 if odd".

    There are definitely prettier versions of the word search code than mine. Many of them load the entire dictionary into memory, and loop over the search space comparing what's found with all possible dictionary words rather than the other way round. (I started programming on machines with nothing like enough memory for that, and my tendency if not otherwise constrained is to treat things as streams.)

    Some solutions start separately on each grid square and set off in each direction one character at a time, checking the dictionary as they go; I took the approach that determining whether a shorter string is contained in a longer one is a language primitive and reasonably fast.

Add A Comment

Your Name
Your Email
Your Comment

Your submission will be ignored if any field is left blank, but your email address will not be displayed. Comments will be processed through markdown.

Search
Archive
Tags 1920s 1930s 1940s 1950s 1960s 1970s 1980s 1990s 2000s 2010s 3d printing action aeronautics aikakirja anecdote animation anime army astronomy audio audio tech base commerce battletech beer boardgaming book of the week bookmonth chain of command children chronicle church of no redeeming virtues cold war comedy computing contemporary cornish smuggler cosmic encounter coup covid-19 cycling dead of winter doctor who documentary drama driving drone ecchi economics espionage essen 2015 essen 2016 essen 2017 essen 2018 essen 2019 existential risk falklands war fandom fanfic fantasy feminism film firefly first world war flash point flight simulation food garmin drive gazebo geodata gin gurps gurps 101 harpoon historical history horror hugo 2014 hugo 2015 hugo 2016 hugo 2017 hugo 2018 hugo 2019 hugo 2020 hugo-nebula reread humour in brief avoid instrumented life kickstarter learn to play leaving earth linux lovecraftiana mecha men with beards museum mystery naval non-fiction one for the brow opera perl perl weekly challenge photography podcast politics powers prediction privacy project woolsack pyracantha python quantum rail raku ranting raspberry pi reading reading boardgames social real life restaurant reviews romance rpg a day rpgs science fiction scythe second world war security shipwreck simutrans smartphone south atlantic war squaddies stationery steampunk stuarts suburbia superheroes suspense television the resistance thirsty meeples thriller tin soldier torg toys trailers travel type 26 type 31 type 45 vietnam war war wargaming weather wives and sweethearts writing about writing x-wing young adult
Special All book reviews, All film reviews
Produced by aikakirja v0.1