## 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:

Task 2: Square Points

- 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

Links

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.

#### Task 2: Square Points

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

TASK #2 › Square Points

Submitted by: Mohammad S Anwar

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 `p m` and

`p`can be either an edge or a diagonal. We have 6 segments to consider. And we know from high school math that

*n*`sqrt(2)*`is the length of the diagonal.

*a*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); subis_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

subnorm{ 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 10^{2} 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:

subis_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; }

subvec_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; }

subvec_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.

subis_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; } }

subis_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`:

subvec_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; } subvec_prod_f{ return sprintf("%f", vec_prod($_[0],$_[1])); } subnorm{ my$p=$_[0]; my$sum= 0;$sum+= ($p->[$_])**2 for (0..$p->$#*); return$sum; } subnorm_f{ return sprintf("%f", norm($_[0])); }

subvec_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; } subvec_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

self made

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 2^{N}-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
2^{N-1} × (2^{N}-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

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

Stay alert and healthy! □

##### Acknowledgement

Thank Simon Proctor for discussion.

#### Links

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

- La quatrième dimension #1 - Définition - Micmaths

Discussion of what dimension is through the concept of objects moving parallel to an axis

(Terminology in Math: a set of pairwise non-parallel vectors spanning space?)

briefly introduce why we can see only 2D but familiar with (or say, the brain can process) 3D objects

- La quatrième dimension #2 - Représenter la 4D - Micmaths

A hypercube appears from 10 min 24 sec to 12 min 48 sec.

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
*

Contact on twitter: @e7_87.

Discuss via GitHub issues: here.

Created Date: 28th July, 2021. Last Modified: 1st Aug, 2021.