Expand one into two - CY's Take on TWC#077

By C.-Y. Fung on

If you want to challenge yourself on programming, especially on Perl and/or Raku, go to https://perlweeklychallenge.org, code the latest challenges, submit codes on-time (by GitHub or email).

I found that I gained unnecessary promotion due to being in a GMT+8.00 timezone - my blogpost appears on the top of https://blogs.perl.org for longer hours.

---

Task 1 Fibonacci Sum

Another dish for math geek!

Really??

Coding Process

I spent a whole day on the Perl script on Fib Sum task. I worked on it until night. Then I have a rest. In the morning next day, finally I gave up a subroutine for cases like "7, 5, 3" => "6, 5, 4, 3, 2, 1" or "11, 9" => "10, 9, 8, 7". The hard time made me recall what I learnt after Challenge #055 Task 2 Wave Array, using a hash to remove any duplicates occurred -- instead of crazy handling of exception cases again and again.

Task Explanation

For the sake of discussion, here we will use F0 = 1 and F1 = 1.

What pop up on my mind after examining the task statements was:

Fk+2 - 2 = Fk + Fk-1 + Fk-2 + ... + F1 (EQUATION I)

The second thought is the term "Fib base". I guess I heard of this jargon on Wikipedia or Online Encyclopedia of Integer Sequences. However, I hadn't studied the resources in details. Twist now. I could figure out there is always a summation of Fib number for all positive integers. It can be proved rigorously by mathematical induction with a construction from the greedy algorithm; assume all positive integers less than N can be written as a summation by Fib sum without repetitions, consider Fr+1 > N ≥ Fr: N - Fr < N and N - Fr can be contructed by Fib numbers from the set {Fr-2, ..., F2, F1} by the induction assumption, except N = Fr.

By greedy algorithm, we can get a summation in which every term is seperated by at least one term in the Fib sequence.

sub get_fibfundsum_index {
    my $target = $_[0];
    my @fans = ();
    my $s = $#FIBSEQ;
    while ($target != 0) {
        if ($target >= $FIBSEQ[$s]) {
            $target = $target - $FIBSEQ[$s];
            push @fans, $s;
        }
        $s--;
    }
    return @fans;
}

I called it "the fundamental Fib summation of N". For example,

  • 8 = 8
  • 1 + 8 + 21 = 30
  • 1 + 3 + 21 + 55 = 80
  • 2 + 5 + 21 + 987 = 1015
  • 8 + 55 + 987 = 1050

Given N, are there more than one Fib summations which each term is seperated by at least one term in the Fib sequence?

No.

Why?

(Thanks for combinatorics textbook again.) Similar to Equation I, we have

  • Fk - 1 = Fk-1 + Fk-3 + Fk-5 + ... + F2 for odd k (EQUATION II).
  • Fk' - 1 = Fk'-1 + Fk'-3 + Fk'-5 + ... + F1 for even k' (EQUATION III).

(One can verify the three equations by mathematical induction.)

Since these sums are smaller than N, which is larger or equal to Fk or Fk', we know from the greedy algorithm that a "reduced" Fib summation # of N must involved the largest Fib number which is smaller or equal to N.

As a feedback for the beginning sentence: This dish is not easy to be digested!

Now we have the one and only one reduced Fib summation for N. How do we get all other Fib summations (under the rule of no repetitions; omit this note starting from here)?

Lemma: Every Fib summations of N can be constructed by some steps of "decomposing"/"expanding"(used in my scripts) the fundamental Fib summation of N.

Proof of the lemma: Proof by contradiction. Assume that there is a Fib summation of N which is unable to be decomposed from the fundamental Fib summation of N. As it is not a reduced Fib summation of N, then it must be able to be composed as a reduced Fib summation of N. (I skipped some details for this statement.) However, it exists one and only one reduced Fib summation of N, which is the fundamental Fib summation of N. !!!

Lots of math have been discussed. Here my Perl code comes as:

For each summation:

while ($bool_expandable) {
    splice(@newarr, $index, 1,
           ($arr[$index]-1, $arr[$index]-2 ) ) ; 
    is_it_new_discovery(@newarr);
    @arr = @newarr;
    $index = $index+1;
    $bool_expandable = ( ( $index == $#arr and $arr[$index] >= 3) or
                      ( defined($arr[$index+1]) 
                              and ($arr[$index]-$arr[$index+1] >= 3)) );
}   #...


For the "kernel":

sub fibsum {
    while ($count > 0) {
        $count = 0;
        my @oldlist = @mainlist;
        my $size_of_oldlist = scalar @oldlist;
        for my $i (0..$size_of_oldlist-1) {
            for my $p (0..scalar @{$oldlist[$i]}) {
                expand( $p , $oldlist[$i] );
            } 
        }
    }


Lastly, my script outputs summation by this line:

print join " + ", map {$FIBSEQ[$_]} @{$array_k};

Note: @mainlist stores lists, i.e. @mainlist is a list of lists; each list which stores the indices of the terms in a Fib summations.

Due to time concern, I did not work independently (not making a brute-force script to check the reliablity of my code). I verify my code against this calculator by Dr Ron Knott: http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/fibrep.html#section3.2 .

Remarks:
# borrowed the term "reduced" from Linear Algebra. (/reduced echelon form/)

Task 2 Lonely X

It looks very simple. For a skeptical programmer, one will look for tricks. The characters of the trick are exactly "Y" and "P" (for vim users) from Challenge #076 Task 2 (the Grid). Trace: The idea is inspired by the tricks used by some other team members on Challenge #068 Task 2 Zero Matrix.

Here is the logic. My script goes through the columns, the rows, the diagonals and the anti-diagonals. If consecutive "X"s have been discovered, I name them as "I"s. If "XI" or "IX" has been discovered, turn the "X" into "I". Finally the script goes through the matrix once and count how many "X"s are left.

Questions to be asked: how much does my code optimize generally (or for what conditions)? Would this approach still behave nice in 3D grid or 4D grid?

Experience on Other Programming Languages

As said, unintentionally being occupied by Fib Sum task, I can only code Lisp and Python solution for Fib Sum task. (Lonely X is heavy for me: 155 lines.)

I tried to tidy my codes more.

For Lisp: I need a throughout review of the Common Lisp textbook before I progress. Some syntax issues had dominated my time left.

For Python: It is easy to translate the ideas from the Perl script into the Python script. Although there is no spare learning time, I still note that I want to know unit testing and commandline arguments for Python.

So many times I have ended blogposts with what to learn! I did an interview for being last month's lucky coder in The Weekly Challenge; learning is again mentioned:

Learning has been mentioned many times above. There are more than one ways to learn a programming language. Competitive programming is a way but it can be too stressful. Reading books is a way but it can be too lonely. Having the weekly challenges gets the balance.

The COVID-19 is being controlled in Hong Kong and social life is active again.

Near the closing of this blogpost, I admit that I cannot spell "Fibonacci" properly.

Do tell or correct me, if you have oppositions, want to discuss or give me advice!

Stay alert and healthy! □

link for codes: ch-1.pl, ch-2.pl, ch-1.lsp, ch-1.py

Tagged as:

Leave a comment

About C.-Y. Fung

user-pic This blog is inactive and replaced by https://e7-87-83.github.io/coding/blog.html ; but I post highly Perl-related posts here.

More info »