PWC 050 › Merge Intervals

This post is part of a series on Mohammad Anwar’s excellent Perl Weekly Challenge, where Perl and Raku hackers submit solutions to two different challenges every week. (It’s a lot of fun, if you’re into that sort of thing.)

Task #1 this week asks us to merge integer ranges. Here is the task description:

Write a script to merge the given intervals where ever possible.

[2,7], [3,9], [10,12], [15,19], [18,22]

The script should merge [2, 7] and [3, 9] together to return [2, 9]. Similarly it should also merge [15, 19] and [18, 22] together to return [15, 22]. The final result should be something like below:

[2, 9], [10, 12], [15, 22]


Of course, we could brute force it by comparing every interval with every other interval for an O(n²) solution. But there is a relatively straightforward algorithm to solve this in O(n log n) time.

Continue reading “PWC 050 › Merge Intervals”

PWC 049 › LRU Cache

This post is part of a series on Mohammad Anwar’s excellent Perl Weekly Challenge, where Perl and Raku hackers submit solutions to two different challenges every week. (It’s a lot of fun, if you’re into that sort of thing.)

Task #2 this week has us build an LRU cache, which is a cache of fixed capacity, whereby when it is full but a new item needs to be added, the item that was least-recently accessed is evicted from the cache.


For example, if a cache of capacity = 3 contains [a b c] (where a was accessed most recently), elements are evicted off the right side of the list. Adding element d, the list would contain [d a b], for example.

Of course, [d a b] are just the keys of the items in the cache. We’ll take an arbitrary scalar (which could itself be a reference) as a value.

Continue reading “PWC 049 › LRU Cache”

PWC 049 › Smallest multiple containing only 1 and 0

This post is part of a series on Mohammad Anwar’s excellent Perl Weekly Challenge, where Perl and Raku hackers submit solutions to two different challenges every week. (It’s a lot of fun, if you’re into that sort of thing.)

Task #1 this week is as follows:

Write a script to accept a positive number as command line argument and print the smallest multiple of the given number consists of digits 0 and 1.


Brute Force

It’s easy enough to brute force this problem, by checking every multiple in order:

$_ += $_[0] while /[^10]/;

$_ now contains the answer. Unfortunately, some numbers—particularly multiples of 9—require extremely large multiples. For example, 99 × 1122334455667789 = 111111111111111111 takes several minutes to discover via this method.

We can do better, though.

Continue reading “PWC 049 › Smallest multiple containing only 1 and 0”

PWC 048 › Survivor (Josepheus problem)

This post is part of a series on Mohammad Anwar’s excellent Perl Weekly Challenge, where Perl and Raku hackers submit solutions to two different challenges every week. (It’s a lot of fun, if you’re into that sort of thing.)

Task #1 this week is described as follows:

There are 50 people standing in a circle in position 1 to 50. The person standing at position 1 has a sword. He kills the next person i.e. standing at position 2 and pass on the sword to the immediate next i.e. person standing at position 3. Now the person at position 3 does the same and it goes on until only one survives.

Write a script to find out the survivor.


This is a well known theoretical exercise in computer science, by the name of the Josepheus problem, based on the story of Flavius Josephus, a Jewish historian in the first century.

Algorithm

To me, the most natural way to solve this problem is with a circular linked list. As a very quick review, a linked list is a list of items where each item also contains a pointer, reference, index, whatever to the next item in the list. A single element is usually drawn like this:

Continue reading “PWC 048 › Survivor (Josepheus problem)”

PWC 048 › Palindrome Dates (mm/dd/yyyy)

This post is part of a series on Mohammad Anwar’s excellent Perl Weekly Challenge, where Perl and Raku hackers submit solutions to two different challenges every week. (It’s a lot of fun, if you’re into that sort of thing.)

Task #2 this week asks us to (and I quote): print all Palindrome Dates between 2000 and 2999. The format of date is mmddyyyy. For example, the first one was on October 2, 2001 as it is represented as 10022001.


It’s pretty easy to avoid using any sort of date library with a couple of key observations about the problem domain. First, we’ll split it up into month (mm), day (dd), century (cc), and 2-digit year (yy). Thus our “baseline” date format is mm dd cc yy.

If we use R[xx] as shorthand for “string reverse of xx“, we can rewrite the date in a couple of different ways:

  mm    dd    cc    yy     # Original
R[yy] R[cc]   cc    yy     # Start with year
  mm    dd  R[dd] R[mm]    # Start with mm/dd
R[yy]   dd  R[dd]   yy     # Start with yy and dd
Continue reading “PWC 048 › Palindrome Dates (mm/dd/yyyy)”

PWC 047 › Roman Calculator

This post is part of a series on Mohammad Anwar’s excellent Perl Weekly Challenge, where Perl and Raku hackers submit solutions to two different challenges every week. (It’s a lot of fun, if you’re into that sort of thing.)

The first challenge this week tasks us with evaluating arithmetic operations using Roman numerals. The description seems to indicate that only one operation will be given (for example, II + IV), but I have elected to support arbitrary arithmetic expressions.

First, I needed a way to convert to and from Roman and Arabic numerals. I had coded this up years ago, and adapted the code I used. Here is the Roman to Arabic converter:

Continue reading “PWC 047 › Roman Calculator”

PWC 047 › Gapful Numbers

This post is part of a series on Mohammad Anwar’s excellent Perl Weekly Challenge, where Perl and Raku hackers submit solutions to two different challenges every week. (It’s a lot of fun, if you’re into that sort of thing.)

Task 2 this week has us print the first 20 “gapful numbers,” as described by OEIS sequence A108343. Gapful numbers are numbers greater than 99 that are evenly divisible by their first and last digits combined. For example, 132 is a gapful number because 132 ÷ 12 = 11.

This is certainly the easier of the two tasks, as both Perl and Raku have convenient ways to index and concatenate string fragments.

Continue reading “PWC 047 › Gapful Numbers”

PWC 046 › Cryptic Message

Can you hear me now? Good.

This post is part of a series on Mohammad Anwar’s excellent Perl Weekly Challenge, where Perl and Raku hackers submit solutions to two different challenges every week. (It’s a lot of fun, if you’re into that sort of thing.)

Challenge #1 this week is the following:

The communication system of an office is broken and message received are not completely reliable. To send message Hello, it ended up sending these following:

H x l 4 !
c e - l o
z e 6 l g
H W l v R
q 9 m # o
Continue reading “PWC 046 › Cryptic Message”

PWC 046 › Is the Room Open? (500 Doors)

Partial result of flipping every 2nd, then every 3rd, and so on

This post is part of a series on Mohammad Anwar’s excellent Perl Weekly Challenge, where Perl and Raku hackers submit solutions to two different challenges every week. (It’s a lot of fun, if you’re into that sort of thing.)

The second of the challenges this week poses the following question (paraphrased):

Suppose we have 500 doors, and 500 employees. The first employee opens all the doors. The second employee closes every 2nd door (doors 2, 4, 6, … 500). The third employee closes every third door if it is open, or opens it if closed. And so on. Which doors are open after all 500 employees have been through?

I remembered toying with a very similar problem a few years ago. At the time, I actually wrote a terminal-based visualizer for it, which you can see in action below (the animated GIF is 1.7MiB, so it may take a few seconds to load on slower connections):

Continue reading “PWC 046 › Is the Room Open? (500 Doors)”

Quine

This post is part of a series on Mohammad Anwar’s excellent Perl Weekly Challenge, where Perl and Raku hackers submit solutions to two different challenges every week. (It’s a lot of fun, if you’re into that sort of thing.)

Challenge #2 this week asks for “a script that dumps its own source code”. This is almost a quine, although Mohammad did not name it as such. Specifically, we are given the constraint that perl ch-2.pl | diff - ch-2.pl must return nothing.

What’s a Quine?

A quine, otherwise known as a self-replicating program, is a program that accepts no input, and produces a copy of its source code as its only output.

This is a stronger definition than what Mohammad has asked for this week: specifically, Mohammad did not add any restrictions on input. So, programs that simply read their own source file would be acceptable this week. Since I felt that was too easy, I have decided to go with the stronger definition of an actual quine, not allowing any input. Still, I’ll include a few solutions to show the various options:

Continue reading “Quine”