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”

Square Secret Code

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 a simple cipher, described as follows:

The square secret code mechanism first removes any space from the original message. Then it lays down the message in a row of 8 columns. The coded message is then obtained by reading down the columns going left to right.

Given “The quick brown fox jumps over the lazy dog”, the expected result is “tbjrd hruto eomhg qwpe unsl ifoa covz kxey”.

Continue reading “Square Secret Code”

Make it $200

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.)

For challenge #2 this week, the task is to start with $1, and by either adding $1 or doubling the amount, reach $200 in the smallest possible number of steps.

“Greedy never works”

In a 75-minute lecture some decades ago, my Advanced Algorithms professor said, over and over, “greedy never works,” while all the while showing us exceptions to that mantra. Greedy algorithms operate by always making the locally optimal choice, which might be the biggest/smallest, closest to the goal, etc., depending on the problem. However, for a great many problems, the locally optimal choice is not always the best. For example, suppose you’re trying to climb the following mountain range (The ASCIIHorn):

        B  
       /\
  /\A /  \
 /  \/    \
/    C     \

Let’s say you’re at position (A), and your goal is to find the highest point. A greedy algorithm would always choose to go higher, never lower (even temporarily), so you’d reach the smaller left peak, and be stuck there. This is known as a hill climbing problem, for which greedy doesn’t work, because you have to go down through the valley (C) before you go up to the goal (B).

Continue reading “Make it $200”

Only 100, please

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 as follows:

You are given a string “123456789”. Write a script that would insert ”+” or ”-” in between digits so that when you evaluate, the result should be 100.

I am going to add the additional constraint that we want all possible solutions, because that is a much stronger statement, and not that difficult to do. There are a few ways we could go about it, but one way that will ensure we traverse the entire search tree is to try every permutation of +, -, and ” (i.e., nothing) in between each decimal digit. As a minimal example, given the string 12, we would have the following expressions:

+1      +1-2    -1+2    +12
+1+2    -1      -1-2    -12

Recursion gives us a search tree for free, so we’ll use that.

Continue reading “Only 100, please”

Self-descriptive 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.)

Challenge #2 this week (43) is to generate Self-descriptive Numbers in arbitrary bases. A self-descriptive number, as described by Wikipedia, is an integer m that in a given base b is b digits long in which each digit d at position n (the most significant digit being at position 0 and the least significant at position b – 1) counts how many instances of digit n are in m.

Continue reading “Self-descriptive Numbers”

Olympic Rings

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 (43) is a number puzzle. In short, the task is to fill in the numbers 1, 2, 3, 4, and 6 into the spaces within the intersecting Olympic rings, so that the numbers in each ring sum to 11. Some of the spaces are already filled in (given). Here is the starting point:

I was able to solve this just by staring at it for a few seconds, so I knew this wasn’t going to be a computationally intensive task. And so instead I wrote a console program that draws the rings and animates every step of the recursive backtracking algorithm I used, because why not.

Continue reading “Olympic Rings”