# ETOOBUSY 🚀 minimal blogging for the impatient

# PWC102 - Hash-counting String

**TL;DR**

On with TASK #2 from the Perl Weekly Challenge #102. Enjoy!

# The challenge

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
It can be shown that for every positive integer N there is exactly one such length-N string.

# The questions

The formulation of the challenge contains everything that is needed,
*only* I would have re-added that the end string must be of length `$N`

in the list of characteristics that define what a hash-counting string
is.

Also… it would have been a plus to have a link to the demonstration that such a string can always be produced. I tried a very superficial search, but to no avail.

# The solution

The key to solving this challenge, for me, relies in these two characteristics:

- the last character is a hash
- there are no two consecutive hashes

The first one basically tells us what should appear at the end: a hash.
It’s a *start*! Ehr… it’s an *end*! 🙄

The other one tells us that we have to put the 1-starting position
number, expressed as a decimal integer, immediately before, with the
possible exception of `$N`

being 1 because in this case we would have
already exhausted the characters that we have to fill in.

So, if we have 123456789 as an input, we know that the hash-counting
string MUST end with the sequence `123456789#`

.

How long is this sequence? It’s 1 character for the `#`

, plus the
*length* of the input number, that is `length $N`

in Perl terms.

At this point, we are left to figure out what to put *before* this last
part of the string. It MUST be a string that is `$N - (1 + length $N)`

characters long, because we already filled in `1 + length $N`

characters
at the end of the final string.

Wait a minute… we now need to fill in a `$N_1 = $N - (1 + length $N)`

string with the rules for hash-counting strings, so we can just repeat
our reasoning!

This will land us with new values for `$N_x`

that are always decreasing,
so we have to stop when we hit 1 or less (which should only be 0, if the
demonstration is correct). That 1 case is a special one, because it’s
the only situation where we put a `#`

*without* puttting an integer
before.

All in all, here’s a possible solution:

```
#!/usr/bin/env perl
use 5.024;
use warnings;
use experimental qw< postderef signatures >;
no warnings qw< experimental::postderef experimental::signatures >;
sub hash_counting_string ($N) {
my $retval = '';
($retval, $N) = ("$N#$retval", $N - 1 - length $N) while $N > 1;
return $N == 1 ? "#$retval" : $retval;
}
my $n = shift || 10;
say hash_counting_string($n);
```

I opted for a more compact and admittedly less readable solution because it becomes so short that it’s not difficult to figure out… like leaving a small challenge for the casual reader 😅

Considering that I don’t need to keep `$N`

and all its “derivative”
values `$N_x`

around, I just use it over and over to keep track of how
many characters I still have to put in the string. This is why `$N`

is
updated at each loop, just like the `$retval`

string.

Have a good day everyone!

*Comments? Octodon, Twitter, GitHub, Reddit, or drop me a line!*