[SOLVED] New Year Puzzle and fun programming challenge

Beryllos · 01-09-2019, 12:56 PM

Here is my latest program:

the whole-number test is corrected (exact match, no margin)
the power operation has new limits on both operands
the year must be entered as a command-line argument

newyear-v3.py.txt

dogpatch · 01-09-2019, 07:02 PM

First noticed this thread late Monday; this is great fun!
I wrote my logic in C, a bit over 300 lines w/ comments, about 11k Linux binary.

I get 49 results for 2019. My matrix:

Code:

 
     0 1 2 3 4 5 6 7 8 9
   |--------------------
 0 | X X X X X X X X X X
 1 | X X X X X - X X X X
 2 | X X X - - - - X X X
 3 | X - - - - - - - X X
 4 | - - - - X X X - - -
 5 | - - - - - - - - - -
 6 | - - - - X - - - - X
 7 | X X X - - - - - X -
 8 | X X X - - - - X X X
 9 | X X X X - X - - - -
10 | X

Also get 53 results for 2029
and 95 for 1972!
(as Sinatra would say, "When I was 21, it was a very good year")

Algebraic formulae and code upon request. I will keep trying to improve on that 49 as well.

What would you say to applying other operations as well? I remember back in the 1970s a similar calculator puzzle entitled '4x4' in which you were allowed to press only the '4' key exactly four times to get results from 0 to 100. Almost the same as this, but in '4x4', you could also use the square, square root, factorial, and reciprocate keys, with parentheses as needed. It took me a good while, but i was eventually able to generate all 101 values (not with a program).

Beryllos · 01-09-2019, 09:42 PM

I played the 4x4 game in the 70s too. I didn't make it to 100 though.

I did it on paper, which unlike a calculator allowed me to write .4 with a bar over it. That represents a repeating digit to make .4444444444..., which is 4/9, and the square root of that is 2/3. I got some mileage out of that. Yeah, good times!

igadoter · 01-10-2019, 05:39 AM

This is my although not a program itself. Idea is to use RPN (or PRN): reverse polish notation. Notation which allows to avoid completely use of parentheses, say:

Code:

2*3

is written as

Code:

2 3 *

in rpn any possible expression would be something like that

Code:

d1 d2 op1 d3 op2 d4 op3

just d1,d2,d3,d4 are all different digits, every each is one of 0,1,2,9, and op1,op2,op3 are one operators as in the first post, all of such sequences is 24*6^3 - quite a lot - not of them are however allowed - but decision is being made during computation, say ( | - denotes concatenation)

Code:

0 1 | 2 * 9 +

evaluates to

Code:

 
((01)*2)+9

which is wrong, so exception NaN is raised - as early as possible. However

Code:

1 0 | 2 * 9 -

is OK - it evaluates to

Code:

10*2-9 = 11

in summary: some sequences will eval to NaN, others to < 0 or > 100, another example

Code:

1 0 | 2 | 9 | -

gives

Code:

102 -9 = 93

dogpatch · 01-10-2019, 06:55 AM

Yeah, my first programmable calculator, an HP11, used RPN. Much more intuitive than parentheses, once you get used to the concept. Also, a co-worker in the 90s wrote a compiler, using RPN to evaluate algebraic expressions.

dogpatch · 01-10-2019, 07:14 AM

Quote:

Originally Posted by Beryllos

I played the 4x4 game in the 70s too. I didn't make it to 100 though.

I did it on paper, which unlike a calculator allowed me to write .4 with a bar over it. That represents a repeating digit to make .4444444444..., which is 4/9, and the square root of that is 2/3. I got some mileage out of that. Yeah, good times!

The toughest one (took me over a year of background cogitation) was 93. Turns out, needed both the factorial and reciprocate keys to do it:

Code:

4 * (4! + 1/4) - 4

or, in RPN:

Code:

4 ! 4 1/x +  4 * 4 -

Kudos on starting this great thread!

Beryllos · 01-10-2019, 08:16 AM

Quote:

Originally Posted by dogpatch

The toughest one (took me over a year of background cogitation) was 93. Turns out, needed both the factorial and reciprocate keys to do it:

Code:

4 * (4! + 1/4) - 4

or, in RPN:

Code:

4 ! 4 1/x +  4 * 4 -

Nice work!

igadoter · 01-10-2019, 09:02 AM

Just correction, it is also necessary to take sequences of the form

Code:

d d o d d o o

say

Code:

90 -12

reads

Code:

9 0 | 1 2 | -

but that's all.

astrogeek · 01-10-2019, 02:55 PM

My HP48GX has seen much use exploring potential expressions for this exercise!*

*It sees much use every day

Beryllos · 01-10-2019, 11:31 PM

I have been investigating the perils of floating point division. To explain: Computers can add, subtract, and multiply whole numbers exactly, provided they don't exceed the number of available bits. Division is different. No matter how many bits are available, division often use every last bit, and still the result is inexact.

For example, on many calculators, 1/3 evaluates to something like 0.33333333. We all know that 3*(1/3) should be 1, but the calculator yields 0.99999999. Call it roundoff error, or truncation error. For most purposes, the difference is negligible, but in the New Year Puzzle, it is a huge problem because we need to know whether the result is or is not a whole number.

When I try that calculation in python, at first it doesn't look so bad:

Code:

>>> 1/3
0.3333333333333333
>>> (1/3)*3
1.0

Wow! It gets the right answer. How does it do that? I am guessing that it calculates it to a few extra places (actually bits), and then rounds it to the required precision. That's actually how the floating-point unit (FPU) in almost every computer works. Most of them do the calculations in 64-bit precision and output the result after rounding down to 53 bits (for double precision). In the above case, that gives the right answer.

Let's try introducing another step:

Code:

>>> (1/3)*3*7
7.0

So far, so good. Now change the order of operations:

Code:

>>> (1/3)*7*3
6.999999999999999

Whaaaat? I am not sure how to explain that in detail, but it warns us that the order of operations makes a small difference in the way truncation errors accumulate. Let the programmer beware!

Here is some good news: If I do those same two calculations in C, I get perfect answers regardless of the order of operations. I don't know why. There must be a small difference in the implementation.

Code:

(1/3)*3*7 =  7.0000000000000000
(1/3)*7*3 =  7.0000000000000000

However, C still gives some inaccurate results for other sets of numbers:

Code:

((7/6)*6)*9 = 63.0000000000000071
((7/6)*9)*6 = 63.0000000000000071
(7/6)*(6*9) = 63.0000000000000071

In C it is possible to declare variables as long double, which is (or so I believe) the native format of the FPU, with 64-bit precision. I experimented with it and found that I can get better results by doing all the calculations in long double, and then casting it to regular double (thereby rounding to 53 bits) before testing whether the result is a whole number.

Let me share two programs with you, one in python3 and the other in C, which do the same thing, except C has the option of long double. In the C program, feel free to change the long double declaration and cast to double, or even float, and see what happens.
equality-test-for-fractions.py.txt
equality-test-for-fractions.c.txt

l0f4r0 · 01-11-2019, 02:56 AM

^ Very interesting. It shows how things can get more complicated from an apparent simple assignment

dugan · 01-11-2019, 09:59 AM

Unless I missed the point:

Code:

#!/usr/bin/env python3

def check(n):
    digits = set(d for d in n)

    if len(digits) < len(n):
        return False
    if digits - set(['2', '0', '1', '9']):
        return False

    return True

for i in range(101):
    if check((str(i))):
        print(i)

That prints out:

Code:

l0f4r0 · 01-11-2019, 10:11 AM

^ I don't know Python but you processed only all the possible concatenations based on [2,0,1,9] digits whose results range from 0 to 100, didn't you?

dugan · 01-11-2019, 10:53 AM

Yes.

Generate all integers from 0 to 100. Filter out the ones that have the same digit more than once. Filter out the ones that have digits that aren't 2, 0, 1, or 9. Print what's left.

Beryllos · 01-11-2019, 12:00 PM

Interesting. I didn't know such things can be done with python's set() function. Someday I should learn how, and when, to use set().

There is more to the New Year Puzzle. It requires each digit of the year to be used once and only once, and certain arithmetic operations are allowed. Sorry if the original post didn't make that clear.