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

*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 `http://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 F_{0} = 1 and F_{1} = 1.

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

F_{k+2} - 2 = F_{k} + F_{k-1} + F_{k-2} + ... + F_{1} (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 F_{r+1} > N ≥ F_{r}: N - F_{r} < N and N - F_{r} can be contructed by Fib numbers from the set {F_{r-2}, ..., F_{2}, F_{1}} by the induction assumption, except N = F_{r}.

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

$target = $target - $FIBSEQ[$s];

push @fans, $s;

}

$s--;

}

}

**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

- F
_{k}- 1 = F_{k-1}+ F_{k-3}+ F_{k-5}+ ... + F_{2}for odd k (EQUATION II). - F
_{k'}- 1 = F_{k'-1}+ F_{k'-3}+ F_{k'-5}+ ... + F_{1}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 F_{k} or F_{k'}, 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"/"`expand`ing"(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:

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)) );

} #...

**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":

$count = 0;

expand( $p , $oldlist[$i] );

}

}

}

**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! □

## Leave a comment