# The Weekly Challenge ‐ Perl and Raku

## CY's Take on The Weekly Challenge #123 ‐ N-cube

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

Do tell me, if I am wrong or you strongly oppose my statements!

It's time for challenges in Week #123 !

about 1500 words, so a brief content:

Prelude

• Math Fun: On the Geometry of 3D and 4D space
• Properties of Squares (and Cubes) and a Primitive Algorithm
• Math Fun: Properties of n-hypercube
• Vector Sum Approach
• Adventure to Cube and Hypercube
• Numerical Inaccuracy
• Discussion for the Norm-ONLY Approach
• Summary
• Acknowledgement

Snapshots of Recent Life
External Image Credits
links to full codes: ch-1.pl, ch-2.pl, ch-2-cube-hypercube.pl

#### Prelude

I often wrote my blogpost for TWC in a storytelling style, but I feel that its my time to put it more "coding-ly" as my knowledge on programming increases. Arrrrrrr... Sometimes I have shared my offline life in these blogposts, I decide to put it in the bottom of the blogpost if it wants.

As noted in the Wikipedia, the generation of ugly numbers is "often used to demonstrate the power of a lazy functional programming language", and I haven't known what functional programming is (find some interesting resources like here or here recently, however I guess, for me, it is better to learn Haskell, a purely functional programming language, /*with Category theory in math, */ in order to grasp the idea of FP throughfully; I need discipline to learn skills OR I WILL STRAY TOO FAR LIKE FOR TASK TWO THIS WEEK).

I have used brute-force ideas to solve the task one. Not nice to share.

Oh, I like the task too much and decide for me to unusually quote the original task statements here:

You are given coordinates of four points i.e. (x1, y1), (x2, y2), (x3, y3) and (x4, y4).

Write a script to find out if the given four points form a square.

After seeing the task statements I immediately decided to extend it as a square+cube+hypercube task in arbitary dimensions!

##### Math Fun: On the Geometry of 3D and 4D space

Hey, do allow me introduce two cool terms I recently learnt: "ana" and "kata". In an Euclidean 3D space, which most of us believe ourselves are familiar with, we can have Up/Down/North/East/South/West (or Up/Down/Back/Left/Front/Right, esp. if you have played Rubik's Cube). In 4D, there is one more axis, thus two more directions we can have, and some mathematicians assign "ana" and "kata" as the names for those directions.

[Need not to fancy too much about "time as the fourth dimension"... The "metric" for measuring distance used by physicists for the dimension of time is called Minkowski metric (generalized: Lorentzian metric). And that "4D world" is called Minkowski spacetime.]

In my submitted codes, A/K/U/D/N/E/S/W are used; the South-East-Down point is picked to be the initial point for vector calculation in 3D and the Kata-South-East-Down point is picked for the same purpose in 4D.

##### Properties of Squares (and Cubes) and a Primitive Algorithm

A quadrilateral with 4 sides equal can be a rhombus but not a square.

A polyhedron with its 12 sides equal can be a parallelepiped but not a cube.

To conclude, we have to get more details besides calculations of the lengths of edges.

Before jumping to the next section about cube-check and hypercube-check, we may have to consider checking for the square first.

Let a be the length of an edge of the regular "cube-like" polytope.

Though edges are not sufficient conditions for proving/disproving whether a polytope(the umbrella term for polygon, polyhedron, ...) is a "cube-like" polytope, it seems that we must know their lengths and check whether they are equal. All we have on hand is the coordinates of vertices, without given their "order" in the plane/space.

Discuss the case of a square. We name the vertices are p0, p1, p2, and p3. We have the segment between pm and pn can be either an edge or a diagonal. We have 6 segments to consider. And we know from high school math that sqrt(2)*a is the length of the diagonal.

As mentioned, an edge-equal quadrilaternal can be a rhombus. But if we additionally consider the length of diagonals, the square has equal-length diagonals and an arbitarily constructed rhombus usually does not. Hence we can have a simple algorithm:

```say is_square(\$pt0, \$pt1, \$pt2, \$pt3);

sub is_square {
my (\$p0,\$p1,\$p2,\$p3) = (\$_[0], \$_[1], \$_[2], \$_[3]);
```

... code block calculate the vectors pairwisely
```    my @n_vector = map { norm(\$_) } (\$v0, \$v1, \$v2, ... );
@n_vector = sort {\$a<=>\$b} @n_vector;
```

if the first four items of @n_vector are equal
and the last two items of @n_vector are equal
then return 1
else return 0

}
```sub norm {
my \$p = \$_[0];
my \$sum = 0;
\$sum+= (\$p->[\$_])**2 for (0..\$p->\$#*);
return \$sum;
}
```

```ok is_square( [10,20], [20,20], [20, 10], [10, 10] ) == 1, "Example 1";
ok is_square( [12,24], [16,10], [20, 12], [18, 16] ) == 0, "Example 2";
ok is_square( [1, 2] , [4,3], [3,1], [2,4] ) == 1, "Knight's square";
ok is_square( [1, 1] , [-1, 1], [ 1,-1], [-1,-1] ) == 1, "centre at origin";
```
##### Math Fun: Properties of n-hypercube

Shouldn't we investigate some basic stuff about the cube in order to understand the hypercube?

Cube:
Number of vertices: 8
Number of edges: 12
Number of faces: 6
Number of cubes: 1

Especially for the segments between pairs of vertices:
Number of edges: 12
Number of face diagonals: 12
Number of body diagonals: 4
Total Number of Segments: 28

Calculate again for the properties of a cube from those of a square:
Cube:
Number of vertices: num of vertices in a square × 2 = 4 × 2 = 8
Number of edges: num of edges in a square × 2 + 4 edges from the self replicating process (black and red in the diagram) = 4 × 2 + 4 = 12
Number of faces: 6
Number of cubes: 1

See a supporting diagram.

Look at the diagram of the hypercube on right in order to get some sensation on it.

Now we proceed (can be counted from looking at the diagram):
Hypercube:
Number of vertices: 8 × 2 = 16
Number of edges: num of edges in a cube × 2 + 8 edges from the self replicating process = 12×2 + 8 = 32
Number of faces: num of faces in a cube × 2 + 12 faces new = 6×2 + 4×6÷2 = 24
Number of cubes: 2 + 6 = 8

Especially for the segments between pairs of vertices:
Number of edges: 32
Number of face diagonals: 2×24 = 48
Number of body diagonals: 4×8 = 32
Number of "hyperdiagonals": 8
Total Number of Segments: 120

I have circled the four body-diagonal points with respect to the bigger bottom right point in red colour as I think it might be the most difficult for us to catch them by intuition.

Though we are not going to code for the 5-hypercube, we may try some calculations based on above.

5-hypercube. Yup, disclamier: I cannot "sense" how the 5-hypercube looks like. Here are just calculations (number of edges verified on OEIS sequence A001787) :
Number of vertices: 32
Number of edges: 32×2 + 16 = 80
Number of faces: 20×2 + ? × ? ÷ ? = ??

Oh, I resign, I fail to continue to count the remaining! But we can see there are already 80 edges, we can expect an order of magnitude of 102 or above for the totol number of concerned segments in 5-hypercube.

##### Vector Sum Approach

As said, we cannot solely rely on the length of edges. And the section "Properties of Squares (and Cubes) and a Primitive Algorithm" has already provided an algorithm and codes, what am I going to talk about?

If you read the optional section "Properties of n-hypercube", you will find there would be a huge number of length of segments we are going to calculate if we follow the primitive algorithm.

Another side of the primitive algorithm we need to consider is: are there any polytope with same various diagonals which are the same? Intuitively the answer is yes, but... I haven't proved it. So it remains a "conjecture" in our context. So... I don't think it is a safe approach for extending to cube or hypercube. A safer approach under the condition that "the diagonal conjecture is not yet proved" is checking the norm of a diagonal against the norm of an edge.

OK let us see the code now:

```sub is_square {
my (\$p0,\$p1,\$p2,\$p3) = (\$_[0], \$_[1], \$_[2], \$_[3]);
my \$v0 = vec_subtract(\$p0, \$p1);
my \$v1 = vec_subtract(\$p0, \$p2);
my \$v2 = vec_subtract(\$p0, \$p3);
# "dot product test";
# return 0 unless (vec_prod_f(\$v1, \$v2) == 0) xor
#                (vec_prod_f(\$v0, \$v2) == 0) xor
#                (vec_prod_f(\$v0, \$v1) == 0);
my @n_vector = map { norm(\$_) } (\$v0, \$v1, \$v2);
@n_vector = sort {\$a<=>\$b} @n_vector;
# "norm test"
#if ( \$n_vector[0] == \$n_vector[1] ) {
#   the above conditional is fit for integter coordinates
#   the below is special arrangement starting from the 5th test case
#   or floating point number in general
if ( sprintf("%f",\$n_vector[0]) == sprintf("%f", \$n_vector[1])
&& 2*sprintf("%f", \$n_vector[0]) == sprintf("%f", \$n_vector[2])
#       the above line concerning length of diagonal is sqrt(2)
#       times the edge length would not be a necessary check
#       if we preserve the dot product test, because in
#       Euclidean space, if two vectors are orthogonal and in equal length,
#       we can apply the Pythagorean theorem for the norm of the vector sum.
#       For DEMOSTRATION PURPOSE,
#       the test of orthogonality (the dot product test) is commented out by brace,
#       but the dot product test will be used both for cube and hypercube.
) {
return 1;
}
return 0;
}
```
```sub vec_prod {
my \$first = \$_[0];
my \$second = \$_[1];
warn "Not the same dimension in vec_prod \n" if \$first->\$#* != \$second->\$#*;
my \$sum = 0;
\$sum+= (\$first->[\$_]*\$second->[\$_]) for (0..\$first->\$#*);
return \$sum;
}
```
```sub vec_subtract {
my \$first = \$_[0];
my \$second = \$_[1];
my \$ans = [];
warn "Not the same dimension in vec_subtract\n" if \$first->\$#* != \$second->\$#*;
for my \$s (0..\$first->\$#*) {
push \$ans->@*, \$second->[\$s] - \$first->[\$s];
}
return \$ans;
}

```

By the properties of vectors, the diagonal vector is the vector sum of two vectors representing the edge while we are keeping the direction correctly.

I will discuss the ugly &sprintf() (gonna be replaced by &norm_f ) on the later section "Numerical Inaccuracy". See also the reason of not using dot product test; honestly I am not sure which (dot product test or checking the norms) is a better combat against numerical inaccuracy; therefore they are being "comment out" via =pod.

##### Adventure to Cube and Hypercube

I intentionally avoid using permutations in the &is_cube here but using permtutations in &is_hypercube for DEMOSTRATING the logic more explicitly for some potential audience. Three nested conditionals, acceptable (?). You can get the link for finalized, more concise code at the bottom of the page.

```sub is_cube {
my @p = @_;
my %v;
\$v{\$_} = vec_subtract(\$p[0], \$p[\$_]) for (1..7);
my @ind = sort { norm(\$v{\$a}) <=> norm(\$v{\$b}) } keys %v;
my (\$N, \$W, \$U) = (\$v{\$ind[0]} , \$v{\$ind[1]} , \$v{\$ind[2]}) ;
return 0 unless norm_f(\$N) == norm_f(\$W) && norm_f(\$N) == norm_f(\$U);
return 0 unless vec_prod_f(\$N,\$W) == 0 && vec_prod_f(\$W,\$U) == 0
&& vec_prod_f(\$U,\$N) == 0;
my \$NW = vec_sum(\$N, \$W);
my \$WU = vec_sum(\$W, \$U);
my \$UN = vec_sum(\$U, \$N);
my \$bool = undef;
if (vec_same_f(\$NW, \$v{\$ind[3]})) {
if   (  vec_same_f(\$WU, \$v{\$ind[4]})
&&  vec_same_f(\$UN, \$v{\$ind[5]}) ) { \$bool = 1;
} elsif ( vec_same_f(\$WU, \$v{\$ind[5]})
&&   vec_same_f(\$UN, \$v{\$ind[4]}) ) { \$bool = 1;
}
}
if (!\$bool && vec_same_f(\$NW, \$v{\$ind[4]})) {
if   (  vec_same_f(\$WU, \$v{\$ind[3]})
&&  vec_same_f(\$UN, \$v{\$ind[5]}) ) { \$bool = 1;
} elsif ( vec_same_f(\$WU, \$v{\$ind[5]})
&&   vec_same_f(\$UN, \$v{\$ind[3]}) ) { \$bool = 1;
}
}
if (!\$bool && vec_same_f(\$NW, \$v{\$ind[5]})) {
if   (  vec_same_f(\$WU, \$v{\$ind[4]})
&&  vec_same_f(\$UN, \$v{\$ind[3]}) ) { \$bool = 1;
} elsif ( vec_same_f(\$WU, \$v{\$ind[3]})
&&   vec_same_f(\$UN, \$v{\$ind[4]}) ) { \$bool = 1;
} else {
return 0;
}
}
return 0 if !\$bool;

my \$NWU = vec_sum( \$N, \$WU);
if ( vec_same_f( \$v{\$ind[6]} , \$NWU ) ) {
=pod
return 0 unless
2*norm_f(\$N) == norm_f(\$NW) &&
norm_f(\$NW) == norm_f(\$WU) &&
norm_f(\$WU) == norm_f(\$UN) &&
3*norm_f(\$N) == norm_f(\$NWU);
=cut
return 1;
}
else {
return 0;
}
}
```
```sub is_hypercube {
my @p = @_;
my %v;
\$v{\$_} = vec_subtract(\$p[0], \$p[\$_]) for (1..15);
my @ind = sort { norm(\$v{\$a}) <=> norm(\$v{\$b}) } keys %v;
my (\$N, \$W, \$U, \$A) = ( \$v{\$ind[0]}, \$v{\$ind[1]} ,
\$v{\$ind[2]}, \$v{\$ind[3]} );
return 0 unless
norm_f(\$N) == norm_f(\$W) && norm_f(\$W) == norm_f(\$U)
&& norm_f(\$U) == norm_f(\$A);
return 0 unless
vec_prod_f(\$N, \$W) == 0 &&
vec_prod_f(\$N, \$U) == 0 &&
vec_prod_f(\$N, \$A) == 0 &&
vec_prod_f(\$A, \$W) == 0 &&
vec_prod_f(\$A, \$U) == 0 &&
vec_prod_f(\$W, \$U) == 0 ;

my \$AU = vec_sum(\$A, \$U);
my \$AW = vec_sum(\$A, \$W);
my \$AN = vec_sum(\$A, \$N);
my \$NW = vec_sum(\$N, \$W);
my \$WU = vec_sum(\$W, \$U);
my \$UN = vec_sum(\$U, \$N);
my \$bool_face = undef;
my \$iter_face = permutations([\$AU, \$UN, \$NW, \$WU, \$AW, \$AN]);
while (!\$bool_face && (my \$p = \$iter_face->next)) {
\$bool_face =
vec_same_f(\$v{\$ind[4]}, \$p->[0]) &&
vec_same_f(\$v{\$ind[5]}, \$p->[1]) &&
vec_same_f(\$v{\$ind[6]}, \$p->[2]) &&
vec_same_f(\$v{\$ind[7]}, \$p->[3]) &&
vec_same_f(\$v{\$ind[8]}, \$p->[4]) &&
vec_same_f(\$v{\$ind[9]}, \$p->[5]) ;
}
return 0 if !\$bool_face;

my \$UNW = vec_sum(\$UN, \$W);
my \$ANW = vec_sum(\$NW, \$A);
my \$AWU = vec_sum(\$WU, \$A);
my \$AUN = vec_sum(\$UN, \$A);
my \$bool_cube = undef;
my \$iter_cube = permutations([\$UNW, \$ANW, \$AWU, \$AUN]);
while (!\$bool_cube && (my \$p = \$iter_cube->next)) {
\$bool_cube =
vec_same_f(\$v{\$ind[10]}, \$p->[0]) &&
vec_same_f(\$v{\$ind[11]}, \$p->[1]) &&
vec_same_f(\$v{\$ind[12]}, \$p->[2]) &&
vec_same_f(\$v{\$ind[13]}, \$p->[3]);
}
return 0 if !\$bool_cube;

my \$AUNW = vec_sum(\$AU,\$NW);
if ( vec_same_f(\$v{\$ind[14]}, \$AUNW) ) {```
```=pod
return 0 unless
2*norm_f(\$N) == norm_f(\$NW) &&
norm_f(\$NW) == norm_f(\$AU) &&
norm_f(\$NW) == norm_f(\$UN) &&
norm_f(\$NW) == norm_f(\$WU) &&
norm_f(\$NW) == norm_f(\$AW) &&
norm_f(\$NW) == norm_f(\$AN) &&
3*norm_f(\$N) == norm_f(\$UNW) &&
3*norm_f(\$N) == norm_f(\$ANW) &&
3*norm_f(\$N) == norm_f(\$AWU) &&
3*norm_f(\$N) == norm_f(\$AUN) &&
4*norm_f(\$N) == norm_f(\$AUNW);
=cut
return 1;
}
else {
return 0;
}
}
```
##### Numerical Inaccuracy

When all the coordinates are integers, there will not be any problems. What if we supply sqrt(\$INT) or sin(\$ANGLE)? It was found that Perl 5 (maybe many other programming language which are not built-in radical or "good sin function"). does not work well. Luckily a rouadabout is found:
sprintf("%f", \$non-integer-value).

Here are code excepts from ch-2-cube-hypercube.pl:

```sub vec_prod {
my \$first = \$_[0];
my \$second = \$_[1];
warn "Not the same dimension in vec_prod \n" if \$first->\$#* != \$second->\$#*;
my \$sum = 0;
\$sum+= (\$first->[\$_]*\$second->[\$_]) for (0..\$first->\$#*);
return \$sum;
}

sub vec_prod_f {
return sprintf("%f", vec_prod(\$_[0], \$_[1]));
}

sub norm {
my \$p = \$_[0];
my \$sum = 0;
\$sum+= (\$p->[\$_])**2 for (0..\$p->\$#*);
return \$sum;
}

sub norm_f {
return sprintf("%f", norm(\$_[0]));
}

```
```sub vec_same {
my \$first = \$_[0];
my \$second = \$_[1];
warn "Not the same dimension in vec_same\n" if \$first->\$#* != \$second->\$#*;
for my \$s (0..\$first->\$#*) {
return undef if \$first->[\$s] != \$second->[\$s];
}
return 1;
}

sub vec_same_f {
my \$first = \$_[0];
my \$second = \$_[1];
warn "Not the same dimension in vec_same_f\n" if \$first->\$#* != \$second->\$#*;
for my \$s (0..\$first->\$#*) {
return undef if sprintf("%f",\$first->[\$s]) != sprintf("%f",\$second->[\$s]);
}
return 1;
}
```
##### Discussion for the Norm-ONLY Approach

It is possible to calculate all the lengths between points, sort them, and compare whether a cluster of them is equally valued (or whether they are correct multiples of the length of the edges). However, the number of total segments exponentially increases as the dimension increases. And I don't know yet what the minimum number of segment length to be checked is (except for squares).

Another mathematical point is, if we fix a point as "reference origin", we only need to calculate and sort 2N-1 vectors. Not out of surprise is that the distribution of lengths of the vectors follow the Pascal triangle:

For N = 2, check (1) diagonal;
For N = 3, check (2, 1) diagonals;
For N = 4, check (3, 3, 1) diagonals;
For N = 5, check (4, 6, 4, 1) diagonals;
...

If we calculate all the segments, there are 2N-1 × (2N-1) segments, and the distribution of the lengths is a bit more unpleasant to be calculated:

For N = 2, check (2) diagonals;
For N = 3, check (12, 4) diagonals;
For N = 4, check (48, 32, 8) diagonals;
...

##### Summary

Replication of a square makes a cube; self made

I don't do the &is_5-hypercube. But you can see it will be about checking the orthogonality of the set of 31 vectors origined from one of the vertices, sorting their norms; just bear in mind that the distribution of the lengths of the vectors is (5, 10, 10, 5, 1), check whether the vector sums of the edges are same as diagonals...

##### Acknowledgement

Thank Simon Proctor for discussion.

I watched them with help of the auto-translated functionality on YouTube.

Some details on the mathematics of n-hypercubes:

##### Snapshots of Recent Life

Talking about my growth on various directions is a great side-effect of TWC posts to keep track on my effort, especially in programming and IT.

1. I feel I learnt enough bash so I stop coding the tasks by it. However, bash, as a shell, is not only about scripting. It also provides some features like "press tab and then available choices are given" or "!\$". I learnt these from a Kindle Book Bash Command Line Pro Tips, by Jason Cannon. The next language to learn should be C (start for TWC tasks only), after I complete the CPAN targets Games::Cards::Bridge and extend Map::Tube::[cities in PRC]. ...

2. I finally made it how to automate the git push through the SSH keys. However, I still found the concepts of SSH foreign. Maybe I need to read its Definitive Guide(?).

3. I often felt I might be a target of black-hat hackers because of abnormal cursor movements, strange typos and buzz on audio output. Finally I bought a USB mouse and stopped using the touchpad. Things have worked well. Okay, it is highly probable that the typos are my responsibility...

4. Previously I drafted two programming tasks on geometry of surfaces. but confused with how to handle the numerical errors and/or significant figures. And as said above, I confused with the numerical stuff on Task 2 this week. There are some floating-point arithmetic computing books around but I am more concerned with the mathematical side rather than the computing side. The life partner of one of my physicist friends (more precisely, my friend is an astronomist), is an applied mathematician. He is kind and shares his lecture videos on the topic with me! Hope that I can learn the material well.

The original image of the tesseract (4-hypercube) is made by Tom Ruen using Stella ‐ a software coded by Robert Webb. The Wikimedia Commons page of the image is here. It is licensed under the Creative Commons Attribution-Share Alike 3.0 Unported license.

The image of the cube with a face diagonal and a body diagonal marked is made by Ervinpospisil and R. A. Nonenmacher. Its Wikimedia Commons page is here. eleased under CC-BY-SA 4.0/3.0/2.5/2.0/1.0 and GNU Free Documentation License.

Except from images and codes from other personnels (including derived works), the content of this blogpost is released under a copyleft spirit. One may share (full or partial) content of this blogpost on other platform if you share it under the free and open content spirit.

links for CY's full codes: ch-1.pl, ch-2.pl, ch-2-cube-hypercube.pl