Month: October 2021

Wherein we learn the value of being truthful to ourselves and the social nets that surround us. Be kind — rewind.

THE WEEKLY CHALLENGE – PERL & RAKU #136

---

episode one:
“Don’t Gimme No Lines, and Keep Your Hands to Yourself”

---

Task 1

Two Friendly

Submitted by: Mohammad S Anwar

You are given 2 positive numbers, $m and $n.

Write a script to find out if the given two numbers are Two Friendly.

Two positive numbers, m and n are two friendly when gcd(m, n) = 2 ^ p where p > 0. The greatest common divisor (gcd) of a set of numbers is the largest positive number that divides all the numbers in the set without remainder.

Example 1

    Input: $m = 8, $n = 24
    Output: 1

    Reason: gcd(8,24) = 8 => 2 ^ 3

Example 2

    Input: $m = 26, $n = 39
    Output: 0

    Reason: gcd(26,39) = 13

Example 3

    Input: $m = 4, $n = 10
    Output: 1

    Reason: gcd(4,10) = 2 => 2 ^ 1

Method

Being nice is nice. I strive for it every day — it makes my day better, as seemingly it does for those around me, and generally we can say the world is a better place with more kindness in it. In some circumstances, though, niceness may express an inappropriate level of informality to an otherwise more serious, or formal, situation. Telling jokes at a funeral, for instance, or discussing the attractiveness of a Judge at court, are examples of transgressions that test these unwritten boundaries. No matter the factuality of such statements, there are protocols to observe and some things are simply not done in polite society.

Such social cues are commonly referred to as “reading the room”. Not all actions, however well meaning, are appropriate in all situations, and the rules governing this behavior are difficult to codify, often relying on non-verbal communication to transmit necessary information on the correct level of informality to act with among a specific social group at a specific time. The interplay of this social interaction is learned behavior and can even be subject to change between contexts even among the same individuals. Informality normally leads to more relaxed interactions, with generally positive outcomes, and is hence desirable. Fortunately informality itself by definition leads to a softening of the rules for interaction, causing the social tensions set up by the rules of correctness to self-dissipate as familiarity rises. We can thus sidestep the complexity by actually becoming friends, providing a nice escape from all these rules and requirements.

However a failure to accurately navigate the mores of interpersonal behavior within a group can lead to social awkwardness when conventional patterns are broken; this is known as a faux pas, or literally, mis-step.

This is commonly realized when the subject expresses excessive affection and informality towards either an object of attraction or a socially structured superior, seeming to reference a social or emotional commonality that has not yet formed between the parties.

This conduct is likely to form a repulsive counter-reaction from the object in the exchange, in an effort to clarify the situation, which, again subject to the rules of acceptable social mores, may be largely unspoken: such as a lack of response, or turning away without engagement. Repeated failure at this point to “read the room” indicates a lack of social awareness that touches the core of the social contract and will near-universally produce a sense of unease in the object of the unwanted informality. This is sometimes even expressed physically, through the activation by the amygdala and the sympathetic nervous system, and experienced as a tingling of the skin, or one’s hair standing up, often said of the back of the neck. These are real physical manifestations of the fight-or-flight response, brought on by the newly-noticed unpredictability of the subject’s behavior.

This behavior, of acting outside the range of predictability within the social contract, is commonly referred to as “creepy”.

Being too friendly, before such interactions are socially confirmed, is creepy.

Which brings us to today’s lesson:

1. Be nice.
2. Don’t be creepy.

PERL 5 SOLUTION

The real activity here is wrapped up into one short routine — the others are provided as works-in-progress, to help the reader follow along. After writing them I decided to make one single combined form, inlining the necessary functionality into a single procedure.

For the GCD we implement Euclid’s algorithm. That’s pretty straightforward.

Deciding on whether a given value was a power of two gave me some pause however, and in the end I came up with no less than three completely different ways of going about it. In the first, we divide down by 2 until we can’t any more, and if the remained is 1 we’ve divided our last 2. With any other number we will end up with some prime factor instead.

Alternately, we could uses some math to take the logarithm of the result, and see whether it’s a whole number. How to do that you ask? A very Perlish way would be to look for a decimal point in the result. Float or not (I’m actually unsure about how this is stored without using Devel::Peek), if the result is whole Perl will output it as the whole number only, as 4 and not 4.0 or similar. I have to say I’m a little suspect of this but it does appear to work in all cases. YMMV. I decided it was cool but ultimately vetoed it.

In the third method we use a method not unlike popcount, which Perl does not natively provide. We convert the number to a binary string using sprintf "%b" and the count the 1s. The only way to have exactly one 1 will be for the number be a power of 2. This too is quite cool, and surely correct, but seems a lot of computational work, translating and breaking up and summing the binary representation. I ended up going with my first instincts in the end.

use warnings;
use strict;
use utf8;
use feature ":5.26";
use feature qw(signatures);
no warnings 'experimental::signatures';


sub is_creepy ( $m, $n ) {
## is $m too friendly towards $n? Does it need to BTFO? Boundaries, people!
    ( $m, $n ) = ( $n, $m % $n ) while $n > 0;      ## gcd
    $m /= 2 until $m % 2;                           ## power of 2?
    return $m == 1 ? 1 : 0;
}



## some extra, relevant functions that we don't actually use directly, 
## as their required functionality is inlined in is_creepy()
sub gcd ( $m, $n ) {
    ( $m, $n ) = ( $n, $m % $n ) while $n > 0;
    return $m;
}

sub power_of_2_div ( $num ) {
    $num /= 2 until $num % 2;
    return $num == 1 ? 1 : 0;
}

sub power_of_2_log ( $num ) {
    return ((log($n) / log(2)) =~ /\./ ? 0 : 1);
}

sub power_of_2_popcount ( $num ) {
    use List::Util qw(sum);
    sum( split //, sprintf "%b", $num ) == 1 ? 1 : 0;
}

raku solution

In Raku we end up with one of those beautifully laid-out flows of code that just seem to happen in that language. We can get the GCD just by asking nicely, and then we can divide down by 2, using the divisibility operator as a guide. Finally a ternary operation tells us what to return.

sub is_creepy ( $m is copy, $n is copy ) {
## is $m too friendly towards $n? Does it need to BTFO? Boundaries, people!
    my $g = $m gcd $n;
    $g /= 2 while $g %% 2;                          
    $g > 1  ?? 0 
            !! 1;
}

---

episode two:
“Pull the Other One — It’s Got Bells on It”

---

task 2

Fibonacci Sequence

Submitted by: Mohammad S Anwar

You are given a positive number $n.

Write a script to find how many different sequences you can create using Fibonacci numbers where the sum of unique numbers in each sequence are the same as the given number.

Fibonacci Numbers: 1,2,3,5,8,13,21,34,55,89, …

Example 1

Input:  $n = 16
Output: 4

Reason: There are 4 possible sequences that can be created using Fibonacci numbers
i.e. (3 + 13), (1 + 2 + 13), (3 + 5 + 8) and (1 + 2 + 5 + 8).

Example 2

Input:  $n = 9
Output: 2

Reason: There are 2 possible sequences that can be created using Fibonacci numbers
i.e. (1 + 3 + 5) and (1 + 8).

Example 3

Input:  $n = 15
Output: 2

Reason: There are 2 possible sequences that can be created using Fibonacci numbers
i.e. (2 + 5 + 8) and (2 + 13).

Method

This is a very interesting challenge because individual Fibonacci numbers can themselves be decomposed into a sequence of the previous two values, which can themselves further recursively decomposed.

The caveat to this deconstruction is the criterium that the elements of the sequence be unique.

Consider the number 34. This is itself a Fibonacci number so I see no reason not to assign it a sequence of one value, itself: (34)

This value, 34, can be decomposed into the two previous values, according to the recursive relation that defines the sequence:

F(n) = F(n-1) + F(n-2)

Thus we add the sequence

(13, 21).

Now 21 cannot be immediately broken down because of a conflict with 13, so we will start by breaking down that position instead. So the sequence

(5, 8, 21)

can now be added, and from that sequence the 5 can be further broken down as well:

(2, 3, 8, 21)

Now the 8 cannot be broken down into (5, 3), nor the 21 into (8, 13) so we are done:

(34)

(13, 21)

(5, 8, 21)

(2, 3, 8, 21)

Well that’s a mess, if I say so. I can see performing this process through a sequence of recursive steps on a given kernal solution, but after doing this how can we be sure that we have found all solutions? How do we find our initial top-level solution, and may there also, with larger numbers, be multiple top-level solutions that each can be independently deconstructed into their own solution sets? The answer is not obvious to me, and any logical proof of its correctness or completeness even less so.

I think further study is necessary, and to to that we need a more expansive base of targets and solutions to examine to infer patterns. So we end up needing a solver to perfect our solver, which is problematic to say the least.

Obviously we will need another approach.

With that in mind another sure-fire way to find all solutions is to consider a list of all unique Fibonacci numbers less than or equal to the target and try all combinations, keeping those that sum correctly.

It’s certainly a computationally-intensive way to go about things: for a complete set of combinations from an input set, where each element is either present or not, we double the solution count for each new element, producting 2ⁿ combinations for n elements. It does, however, get the job done. Because we have in the end tried all combinations, we can be assured that all successful summations will also be arrived at.

I do feel number theory may reveal a procedure for easily producing top-level solution kernals that can be further reduced. I dare say again that logic is not obvious, though. And as I’m running out of time, I think for today we’ll have to leave things there.

PERL 5 SOLUTION

Oct 30, 2021 at 8:51:41 PM
~/PWC/136-2-a-series-of-lies.pl

input: 1234

found 15 Fibonacci numbers less than 1234
there are 32767 combinations to be examined
calculating...

found 22 solutions:
( 1 + 13 + 233 + 987 )
( 1 + 13 + 233 + 377 + 610 )
( 1 + 13 + 89 + 144 + 987 )
( 1 + 13 + 89 + 144 + 377 + 610 )
( 1 + 13 + 34 + 55 + 144 + 987 )
( 1 + 13 + 34 + 55 + 144 + 377 + 610 )
( 1 + 5 + 8 + 233 + 987 )
( 1 + 5 + 8 + 233 + 377 + 610 )
( 1 + 5 + 8 + 89 + 144 + 987 )
( 1 + 5 + 8 + 89 + 144 + 377 + 610 )
( 1 + 5 + 8 + 34 + 55 + 144 + 987 )
( 1 + 5 + 8 + 34 + 55 + 144 + 377 + 610 )
( 1 + 5 + 8 + 13 + 21 + 55 + 144 + 987 )
( 1 + 5 + 8 + 13 + 21 + 55 + 144 + 377 + 610 )
( 1 + 2 + 3 + 8 + 233 + 987 )
( 1 + 2 + 3 + 8 + 233 + 377 + 610 )
( 1 + 2 + 3 + 8 + 89 + 144 + 987 )
( 1 + 2 + 3 + 8 + 89 + 144 + 377 + 610 )
( 1 + 2 + 3 + 8 + 34 + 55 + 144 + 987 )
( 1 + 2 + 3 + 8 + 34 + 55 + 144 + 377 + 610 )
( 1 + 2 + 3 + 8 + 13 + 21 + 55 + 144 + 987 )
( 1 + 2 + 3 + 8 + 13 + 21 + 55 + 144 + 377 + 610 )

To derive the combinations, we need to construct a list of unique Fibonacci numbers less than or equal to our target value. The unique qualification is not difficult, as the sequence always grows after the first two values; all we need to do is shift off the first 1 from the list to satisfy this requirement. To get our combinations we’ll use a little trick that involves printing a list of binary numbers from 1 up to 2 raised to the power of the number of Fibonacci numbers represented. Each number, printed in binary, will express a unique pattern of 1s and 0s that can assigned to “turn on” or “turn off” each position in the sequence, constituting a unique combination selected. We use another trick to pair every number to its corresponding binary digit, multiplying them out before summing the total, Only those paired with a 1 will add to the sum, as the other values will be zero.

use warnings;
use strict;
use utf8;
use feature ":5.26";
use feature qw(signatures);
no warnings 'experimental::signatures';
use List::Util qw(sum zip);

my $target = shift @ARGV || 1234;

my @fibs = (1,1);
my @sols;

sub generate_unique_fibs ( $limit ) {
## generates sequence of Fibonacci numbers up to and not greater than limit
    push @fibs, $fibs[-1]+$fibs[-2] while $fibs[-1]+$fibs[-2] <= $limit;
    shift @fibs;                                ## remove duplicate 1 at start
}

generate_unique_fibs( $target );
my $len = scalar @fibs;

say "input: ", $target, "\n";
say "found $len Fibonacci numbers less than $target";
say "there are ", 2 ** $len - 1, " combinations to be examined";
say "calculating...\n";

for my $num (1 .. 2 ** $len - 1) {
    my @bits = split //, sprintf "%0${len}b", $num;
    my @candidate = map { $_->[0] * $_->[1] } zip( \@fibs, \@bits);
    push @sols, [ grep { $_ } @candidate ] if sum( @candidate ) == $target;
}

say "found ", scalar @sols, " solutions:";
local $" = ' + ';
say "( $_->@* )" for @sols;

Raku Solution

In Raku we can do things a little differently, as we have lots of built-in functionality to play with. First, to build the Fibonacci sequence we can define a pattern for a lazy list and leave it at that. From this template, if you will, we can extract a working array of real values by slicing from index 1 up to but not including the index of the first value exceeding the target. Oh, right, and return the index, not the matched value. How’s that for a succinct definition?

To construct our combinations we can do this directly using the .combinations() method inside two nested for statements, the inner selecting each group of combinations of each available length up to every element used, and the outer loop selecting individual final combinations from those sets. To be clear, I don’t think I’ve ever even thought to nest a pair of for loop control structures quite like this before, and had no idea whether it would work until I tried it. You certainly can’t do that in Perl.

unit sub MAIN ( $target = 30034 ) ;

## generate list of Fib numbers from second index up to but not including the index
## of the first value exceeding the target
my @fibs        = (1, 1, * + * ... *);
my @unique_fibs = @fibs[1..^@fibs.first(* > $target, :k)];

say qq:to/END/;
    found {@unique_fibs.elems} Fibonacci numbers less than $target
    there are { 2 ** @unique_fibs.elems - 1 } comnbinations to be processed
    calculating...
    END
 
## compute all combinations for all lengths
my @out;
for (@unique_fibs.combinations($_) for 1..@unique_fibs.elems) {
    for $_ -> $c {
        push @out, $c.join( ' + ') if $c.sum == $target;
    }
}
    
say "found {@out.elems} solutions";
.say for @out;