Weekly Challenge 102

Challenge 102
My solutions

TASK #1 › Rare Numbers

Task

You are given a positive integer $N.

Write a script to generate all Rare numbers of size $N if exists. Please checkout the page for more information about it.

My solution

I could have just scraped the page that has a list of rare numbers, but that's not the spirit of the challenge, is it? :P

It's also clear I don't have the most optimal solution. The original author states "the program has been made so powerful that all numbers up to 10¹⁴ can be just checked for Rare numbers in less than a minute on [a] Pentium III PC". My code took 3 minutes for 9 digit numbers and 42m for 10 digit numbers. For that reason, I'll be interested to see how other Team PWC members tackled this.

My solution involves two steps. Generate a hash where the key is square numbers from 1 .. 2 * 10ⁿ. Then I brute force my way through all numbers to see if there are any matches.

Examples

» ./ch-1.pl 2
65

» ./ch-1.pl 6
621770

» time ./ch-1.pl 9
281089082

real    3m15.319s

» time ./ch-1.pl 10
2022652202 2042832002

real    42m4.669s

TASK #2 › Hash-counting String

Task

You are given a positive integer $N.

Write a script to produce Hash-counting string of that length.

The definition of a hash-counting string is as follows:

• the string consists only of digits 0-9 and hashes, ‘#’
• there are no two consecutive hashes: ‘##’ does not appear in your string
• the last character is a hash
• the number immediately preceding each hash (if it exists) is the position of that hash in the string, with the position being counted up from 1

My solution

I actually completed this task first as it seems easier than task one. Took me less than 10 minutes to code. The basic idea behind my solution is to create a $string containing the required number of hash characters.

I then move back by the characters of the position in the hash (for example position '14' has 2 characters), and insert the number. I keep doing this until the are no more numbers to insert.

Examples

» ./ch-2.pl 1
#

» ./ch-2.pl 2
2#

» ./ch-2.pl 3
#3#

» ./ch-2.pl 10
#3#5#7#10#

» ./ch-2.pl 14
2#4#6#8#11#14#