DEV Community

loading...

Weekly Challenge 102

simongreennet profile image Simon Green ・2 min read

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 1014 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 * 10n. 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

Enter fullscreen mode Exit fullscreen mode

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#
Enter fullscreen mode Exit fullscreen mode

Discussion (0)

Forem Open with the Forem app