[SOLVED] New Year Puzzle and fun programming challenge

ProgrammingThis forum is for all programming questions.
The question does not have to be directly related to Linux and any language is fair game.

Notices

Welcome to LinuxQuestions.org, a friendly and active Linux Community.

You are currently viewing LQ as a guest. By joining our community you will have the ability to post topics, receive our newsletter, use the advanced search, subscribe to threads and access many other special features. Registration is quick, simple and absolutely free. Join our community today!

Note that registered members see fewer ads, and ContentLink is completely disabled once you log in.

If you have any problems with the registration process or your account login, please contact us. If you need to reset your password, click here.

Having a problem logging in? Please visit this page to clear all LQ-related cookies.

Introduction to Linux - A Hands on Guide

This guide was created as an overview of the Linux Operating System, geared toward new users as an exploration tour and getting started guide, with exercises at the end of each chapter.
For more advanced trainees it can be a desktop reference, and a collection of the base knowledge needed to proceed with system and network administration. This book contains many real life examples derived from the author's experience as a Linux system and network administrator, trainer and consultant. They hope these examples will help you to get a better understanding of the Linux system and that you feel encouraged to try out things on your own.

Click Here to receive this Complete Guide absolutely free.

But it appears to me that your concat operation does not avoid use of leading zeroes. Is that correct, or is left_data[0] guaranteed to be non-zero by previous operations in a way I have not seen?

Yes, I forgot to check for leading zeroes, and realized it later when I added some print statements to look at a few of the results. Here is an update on that, with the new lines in bold:

Code:

# concatenation (with error check)
elif operation == 5:
if right_data[1] <= 0 or left_data[1] <= 0:
return 0, -1
# left_data[1], right_data[1], and status are number of digits
# only for concatenated digits, and 0 for all other operations
value = left_data[0]*10**right_data[1]+right_data[0]
status = left_data[1]+right_data[1]
# check for leading zero
if value < 10**(status-1):
return 0, -1
return value, status

Quote:

Originally Posted by astrogeek

I have tended to think of the problem in terms of minimizing the generating expressions (and using the current year digits), whereas your approach has been to exhaust every possible expression for any set of digits. The two are somewhat complementary in that I can now use your code which produces all possible solutions, to validate my minimal expression sets - thanks for that!

The exhaustive-search approach certainly has its problems. For example, it doesn't scale well. I tried it on 5-digit numbers, and it took roughly 100 times longer.

I don't have any great ideas (or insights) for reducing the number of expressions tried. I see room for small improvements. For example, if an expression works with +0 or *1, one doesn't have to try -0 or /1. Also I see that many power calculations go out of the 0-100 range; one could limit the range of numbers going into the power function.

Right now I am working on printing the arithmetic expressions in a human-friendly format, after reducing the number of results to be displayed. I hope to post that in the next day or two.

Oh, wait a second... The "correction" in my previous post was a bit hasty. It works, but it would make a lot more sense to check the input to the function rather than the output. Here is the better way:

Code:

# concatenation (with error check)
elif operation == 5:
# return error code if either operand is a calculation result
# or if the left operand is zero (leading zero not allowed)
if right_data[1] <= 0 or left_data[1] <= 0 or left_data[0] == 0:
return 0, -1
# left_data[1], right_data[1], and status are number of digits
# only for concatenated digits, and 0 for all other operations
value = left_data[0]*10**right_data[1]+right_data[0]
status = left_data[1]+right_data[1]
return value, status

Whew! I have just finished a version that constructs string expressions with arithmetic symbols and parentheses. At the moment, it outputs everything in the order it finds it, which is about 12,000 lines, a bit inconvenient. Next I'll work on printing only selected results.

Here is the program: newyear-v2.py.txt
The string manipulations are in the function that performs the basic calculations.

I changed the way the functions return data. In this program, all functions simply return 0 for success and -1 for failure, and all data is returned through one of the function arguments.

Last edited by Beryllos; 01-08-2019 at 10:50 AM.
Reason: 3 edits: corrections in comments and corrected bash uniq call

I have been thinking of printing expressions as they are evaluated, along with a few more stats such as how often an expression succeeds or fails, and how many different expressions evaluate to the same result. I thought that streaming out all the processing, well formatted, then piping it through a filter or two might be the best way to go - and yours reinforces that thought!

I haven't had time to work on my code the past couple of days, but it continues to occupy my thoughts when my brain cell is not otherwise occupied. The more I consider the "stratification" of expressions when viewed in terms of zero digits, the more I think that has great potential to minimize the required expressions and impose an order on their evaluation.

Thanks for continuing with your own approach and I hope that you are enjoying it as much as I have - an oddly pleasing diversion!

Very nice!
...
Thanks for continuing with your own approach and I hope that you are enjoying it as much as I have - an oddly pleasing diversion!

Yes, I am having fun with it. Getting the parentheses right was a good challenge for me. Order of operations and parentheses seem so obvious, but "teaching" a machine to do it wasn't very obvious. It required a bit of thought and some doodling on paper, and I wasn't sure my algorithm was correct until I ran it. Woo-hoo!

I have finished the core functionality that I intended to do, but I think I am good for at least one more round in order to refine the output. It might be nice to condense the list to one "good-looking" expression for each whole number that can be calculated. One possibility for narrowing it down is to take the digits in the same order as the year, like these examples:

@Beryllos/astrogeek: did you consider power with negative numbers?
E.g: 1 = 1^(-9)+2*0
I am not sure it will give you any new results but maybe it could be of interest for you if you want to print all possibilities...

I'm glad you brought that up. In my original post, I mentioned that a leading negative sign is allowed, but I didn't actually try it. With this year's digits, I think the only possible use of it is raising 1 to any power, as in your example. With other digits in other years, there are more possibilities.

I think I will work that into the next version of my program, probably restricting it to powers because that is where it can generate new values.

For example... Do you know the old song, In the Year 2525? It came to mind as I thought up these examples:

Code:

1 = 25*5^(-2)
10 = 2/5^(-2)/5 (digits in 2525 order!)

I think I will work that into the next version of my program, probably restricting it to powers because that is where it can generate new values.

Thinking more about this, I am not sure that we really can generate new numbers by using negative powers. For example, multiplication by a negative power (a*b^(-c)) gives the same number as dividing by a positive power (a/b^c). I don't see that it opens a way to numbers that are otherwise inaccessible. So I will continue to omit leading minus signs until it can be shown that it is necessary.

Just one have set containing 2,0,1,9 - now one generate sequences say: 2+0-9*1, such sequences has no meaning at all, some can be incorrect 2++0 - in fact it is exercise from lexical analysis - at first one has to define which sequences are allowed - like say what is identifier in C, then one defines semantic - one builds machine (computer) to evaluate such sequence to 'number', ie. element of 0-2019. Some different sequences have the same value. The only problem is to assure that space of allowed sequences is finite. Description of exercise has to be concise. Now one go through all sequences.

@Beryllos/astrogeek: did you consider power with negative numbers?
E.g: 1 = 1^(-9)+2*0
I am not sure it will give you any new results but maybe it could be of interest for you if you want to print all possibilities...

As already noted by Beryllos, taking a negative power is equivalent to dividing by a positive power. Some of the necessary expressions such as a^(b-c) may produce either positive or negative powers, or zero power. But in general intentionally taking a negative power turns out to be not very useful in this exercise because it will always produce a fractional result which is only useful if inverted - but inversion can only be done if you have an extra digit handy to do it, and if you do then you can always rewrite it as a positive power anyway.

Yes, I am having fun with it. Getting the parentheses right was a good challenge for me. Order of operations and parentheses seem so obvious, but "teaching" a machine to do it wasn't very obvious. It required a bit of thought and some doodling on paper, and I wasn't sure my algorithm was correct until I ran it. Woo-hoo!

I have finished the core functionality that I intended to do, but I think I am good for at least one more round in order to refine the output. It might be nice to condense the list to one "good-looking" expression for each whole number that can be calculated. One possibility for narrowing it down is to take the digits in the same order as the year, like these examples:

That order is possible for some but not all whole numbers in the target range.

Glad to hear you are having fun!

I had a little time to play today and have added shell argument handling for the year, plus some simple options to select output format. I also changed my expression ID to an integer which allows to provide a more useful reference the generating expressions. Finally I have put in place a mechanism for showing the expressions, althought I am not sure those are all correct at this time.

I have structured my expressions into groups as follows (pasted comment code):

Code:

First group only two expressions, always evaluated
/* Sum all, prod all always
No powers, may be 0^0
No division, may be x/0
a+b+c+d
a*b*c*d
*/
Second group assumes only one non-zero digit
/* Operations which make sense with at least one zero and one non-zero digit,
assume all others are zero
a + (b*c*d) - Each digit itself if any zero
a^(b*c*d) - 1 if any zero
(a+b+c)^d - 1 if any zero, else possible power of sum
(b+c+d)/a - 0 if any zeros, else possible quotient
ab+(c*d) - Tens power of a, ab if any other non-zero, ab+product
ab+c+d - Tens power of a plus any non-zero digits
abc-d - 100+ if a==1, only diff of d makes sense
*/
Third group assumes two non-zero digits, two zero
/* Operations which make sense with at least one zero and two non-zero digits,
assume all others are zero
a-b+c+d - Diff of two non-zero digits plus any others
a-b+(c*d) - Diff of all non-zero digits
(a*b)+(c*d) - Product of non-zero pairs
(a*b)+c+d - Product of non-zero pairs plus any non-zero digits
(a+c)*(b+d) - Products of all non-zero pairs and sums of pairs
(a-c)*(b+d) - Products of all non-zero pairs and difference of pairs
(a^c)+b+d - 1 plus all other terms
(a^(c*d))+b - 1 plus non-zero term
(a^b)+(c*d) - Powers of pairs
(a^b)+c+d - Powers of pairs plus any non-zero digits
(a^b)-c+d - Powers of pairs minus any non-zero digits
(ac+d)*b - Product of tens power of a plus others times b
ac+b^d - Tens power of a plus 1 or power
ac+(b*d) - Tens power of a plus product or zero
ac+bd - Tens power of a plus tens power of b
acd-b - Hundreds power of a minus b
acd/b - Hundreds power of a divided by b
(a+c+d)/b - Quotient of sums
(a+(c*d))/b - Quotient of pairs if any zero
*/
Fourth group assumes three non-zero digits
/* Operations which make sense with one zero and three non-zero digits,
assume other is zero
a-b-c+d - Diff of non-zero
a+b+(c*d) - Product of pairs
a*b+(c^d) - Product of non-zero plus 1
a*b-(c^d) - Product of non-zero minus 1
a*b*c+0
(a+(b^d))^c - a plus 1 to the power c (possibly 0^0)
(a-(b^d))^c - a minus 1 to power c (possibly 0^0)
a^b+c^d - Sum of powers of pairs
a^b-c^d - Difference of powers of pairs
a^b-cd - Power of pairs minus tens power of other
(a+b+d)^c - Sum to power
(a-b+d)^c - Diff to power
a^(b+c)+d - a to power of sum
a^(b-c)+d - a to power of difference
ab-c+d - Tens power of a plus b, minus c plus zero or more
ab+(c^d) - Tens power of a plus b plus 1
ab-(c^d) - Tens power of a plus b minus 1
ab+cd - Sum of tens powers
ab-cd - Difference of tens powers
(ab*c)+d - Tens power of a plus b times c, plus zero or more
(ab/c)+d - Tens power of a plus b, divided by c
ad-(b/c) - Tens power of a minus quotient b/c
(ad-c)/b - Tens power of a minus c divided by b
(ad-b)*c - Tens power of a minus b times c
*/
Fifth group assumes all four non-zero digits
/* Operations which make sense with four non-zero digits
Expressions not yet listed in comments
*/

Note that the above expressions in my comments may not agree exactly with what is in my code, but that is the model I am working towards.

In total I have 54 distinct expressions at this time and it produces results in agreement with your latest version in my selected test cases (2019, 2020, 2029, 1234, 2468, 5789, and a few others).

I do not know it it is complete, but evaluating by expression groups with same or fewer number of zeros as above imposes a very useful structure on the expressions which does seem to lead to a minimal number of expressions, and avoids evaluating expressions which will not produce solutions.

The three digit IDs which mark solutions have first digit as expression group minus one (0-4), next two digits are position within group of generating expression.

I found an error (actually a few) in my expressions which I have now resolved.

Fixing one of them caused me to get a different result than your code produces on my 5789 test case. When I tried to resolve that in my own expressions I was left scratching my head.

When I looked at the output of yours for that case I found that you produce zero as a solution while mine does not. Zero appears to be incorrect and results from each of these expressions:

I assume that results from python's precision and rounding. I saw in your code that you test for whole number solutions by a limit expression, but am not sure how python handles that, so maybe you just need to set a lower limit...?

Oh no! I am sorry to have made you chase down my error. You are right, it is related to rounding, but it's not python's fault.

In the main program, I have the following instruction to separate whole numbers from fractions. (The round function is the nearest integer.)

Code:

if abs(value-round(value)) < 1e-10:

The 1e-10 margin allowed all those false results for 0 as you noticed.

Of course the simple way to check for whole numbers it is to test for equality with the nearest integer:

Code:

if value == round(value):

but I decided to allow a margin of error because I expected some roundoff (truncation) error in floating-point division.

Truncation error is implementation-dependent. I can demonstrate it in C. However, in python, at least as it is implemented on my computer, truncation error is negligible, and the calculations involved in this New Year Puzzle seem to come out exact. I hadn't expected it to be so exact.

Therefore, I think the best solution is to use the strict equality test rather than the margin test.

I am also considering modifying the power calculation to skip high powers (say, greater than 100). This precaution is not needed for the four-digit New Year Puzzle, but with 5 or more digits, a small fraction taken to a high power, like (1/9)^340, can underflow to zero, and show up as a false result for 0.

Oh no! I am sorry to have made you chase down my error. You are right, it is related to rounding, but it's not python's fault.

In the main program, I have the following instruction to separate whole numbers from fractions. (The round function is the nearest integer.)

Code:

if abs(value-round(value)) < 1e-10:

The 1e-10 margin allowed all those false results for 0 as you noticed.

I remembered seeing that in your code but did not look for it again at the time (It was 3AM and I should have long been in bed!). If I had, and thought about it for a full second I would have understood the problem, I think.

I am not testing for those errors myself, but simply depending on the default behavior of C. My whole-number test is to compare the float to its integer cast, ignoring potential floating point limitations. But because my expressions are hard wired instead of permuted I may not see some of those expressions (but I will review them for such potential problems at some point.)

But if we are down to finding only precision limit problems, I'd say we are doing well!

LinuxQuestions.org is looking for people interested in writing
Editorials, Articles, Reviews, and more. If you'd like to contribute
content, let us know.