Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Calculation for a map with a bigger number gives invalid solution #1

Open
g1eng opened this issue Nov 20, 2021 · 1 comment
Open

Calculation for a map with a bigger number gives invalid solution #1

g1eng opened this issue Nov 20, 2021 · 1 comment
Labels
bug Something isn't working

Comments

@g1eng
Copy link
Owner

g1eng commented Nov 20, 2021

Problem

Input with a bigger number may give invalid solution for the map (and its length).

Example

echo 35182823158192831295815581123193910002 | cola2 
35182823158192831295815581123193910002 767 # <-- invalid

echo 35182823158192831295815581123193910002 | cola2 -d 
35182823158192831295815581123193910002 -> 17591411579096415647907790561596955001 -> 52774234737289246943723371684790865004 -> 26387117368644623471861685842395432502 -> 13193558684322311735930842921197716251 -> 39580676052966935207792528763593148754 -> 19790338026483467603896264381796574377 -> 59371014079450402811688793145389723132 -> 29685507039725201405844396572694861566 -> 14842753519862600702922198286347430783 -> 44528260559587802108766594859042292350 -> 22264130279793901054383297429521146175 -> 66792390839381703163149892288563438526 -> 33396195419690851581574946144281719263 -> 100188586259072554744724838432845157790 -> 50094293129536277372362419216422578895 -> 150282879388608832117087257649267736686 -> 75141439694304416058543628824633868343 -> 225424319082913248175630886473901605030 -> 112712159541456624087815443236950802515 -> 338136478624369872263446329710852407546 -> 169068239312184936131723164855426203773 -> ### **_166922351015616344931794887134510399864_** -> ...
...
 20 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1 [len=767]   ##<- invalid  (real: 1084)

Request

  • This seems to overflow at hop 23 calculation of the map, and results invalid path for the conversion.
  • Detect overflow and do not allow to show overflowed result.
@g1eng g1eng added the bug Something isn't working label Nov 20, 2021
@g1eng g1eng changed the title Calculated length for a map with bigger numbers are invalid for a solution Calculated length for a map with a bigger number gives invalid solution Nov 20, 2021
@g1eng
Copy link
Owner Author

g1eng commented Nov 20, 2021

Another approach is under preparation to avoid this type of overflow at around 2^128. (451f2ee).
This commit includes bigint for the uint stack and it can successfully calculate map over 2^128 (but so slow at now).

u128 maybe should be a main type of the default solver but bigint can be optional way to calculate upper domain of maps.

@g1eng g1eng changed the title Calculated length for a map with a bigger number gives invalid solution Calculation for a map with a bigger number gives invalid solution Nov 20, 2021
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
bug Something isn't working
Projects
None yet
Development

No branches or pull requests

1 participant