Problem 259

A place to air possible concerns or difficulties in understanding ProjectEuler problems. This forum is not meant to publish solutions. This forum is NOT meant to discuss solution methods or giving hints how a problem can be solved.
Forum rules
As your posts will be visible to the general public you
are requested to be thoughtful in not posting anything
that might explicitly give away how to solve a particular problem.

This forum is NOT meant to discuss solution methods for a problem.

In particular don't post any code fragments or results.

Don't start begging others to give partial answers to problems

Don't ask for hints how to solve a problem

Don't start a new topic for a problem if there already exists one


See also the topics:
Don't post any spoilers
Comments, questions and clarifications about PE problems.
Post Reply
ac336
Posts: 5
Joined: Fri Aug 07, 2009 10:08 pm

Problem 259

Post by ac336 »

Can anyone tell me what kind of magnitude I should be expecting for this one? Just wanted to check I'm not miles off before I go delving in to solve my accuracy problems.

Is 17 digits about right?

User avatar
daniel.is.fischer
Posts: 2400
Joined: Sun Sep 02, 2007 10:15 pm
Location: Bremen, Germany

Re: Problem 259

Post by daniel.is.fischer »

No, the sum is much smaller, between 1010 and 1012.
Il faut respecter la montagne -- c'est pourquoi les gypaètes sont là.

ac336
Posts: 5
Joined: Fri Aug 07, 2009 10:08 pm

Re: Problem 259

Post by ac336 »

Thanks, realised where i went wrong - i wasn't taking them in the right order.

macgupta
Posts: 3
Joined: Sun Apr 05, 2015 3:13 pm

Problem 259 - concatenation of digits

Post by macgupta »

"Any successive digits can be concatenated (for example, using the digits 2, 3 and 4 we obtain the number 234)."

It is not clear whether concatenation is allowed only before applying +,-,*,/ or is allowed with any positive numbers along the way.
E.g., is a series of steps like (4 5 6 7) --> (4+5 6+7) = (9 13) --> 913 allowed?

Thanks!

User avatar
mpiotte
Administrator
Posts: 1914
Joined: Tue May 08, 2012 4:40 pm
Location: Montréal, Canada

Re: Problem 259 - concatenation of digits

Post by mpiotte »

macgupta wrote:...It is not clear whether concatenation is allowed only before applying +,-,*,/ or is allowed with any positive numbers along the way.
E.g., is a series of steps like (4 5 6 7) --> (4+5 6+7) = (9 13) --> 913 allowed? ...
Only the original digits can be concatenated. The 913 example above would not be valid.
(Please don't create a new topic for a problem when one already exists).
Image

macgupta
Posts: 3
Joined: Sun Apr 05, 2015 3:13 pm

Re: Problem 259

Post by macgupta »

Thanks!

It was also not clear whether a "topic" meant a particular clarification for a problem, or all clarifications for a problem. So I had to test that out.

user202729
Posts: 4
Joined: Tue Dec 29, 2015 2:58 pm

Re: Problem 259

Post by user202729 »

Anyone check my result?
I have checked:
+ Do not concatenate results
+ Do not include negative and fractional values in the sum, but calculate them
+ Generate a list of
Expand
48858 (is this right?)
reachable numbers + expression and check some random expressions
+ Do not use floating point type
+ Use 4-byte numerator and denominator.
Am I forget anything?
Image

user202729
Posts: 4
Joined: Tue Dec 29, 2015 2:58 pm

Re: Problem 259

Post by user202729 »

Division by zero is not allowed, is it? (for example: 1/0/0 or 1/0*0)
I have no idea why my code can return wrong result because:
Expand
+ The largest reachable number is 123456789 (multiplication is smaller than concatenation - easy to prove), so 4 byte integer is enough. No integer overflow.
+ I use entirely fractions, so no accuracy loss.
+ There are 9 operands and 1 result (assume concatenation is a binary operator), so there are 8 operators.
+ The priority can be any, except for concatenation must be evaluate first.
Loop through 5^8 operator and 8! priority should return exact result but my result (14958918789) is wrong.
Image

User avatar
nicolas.patrois
Posts: 118
Joined: Fri Jul 26, 2013 3:54 pm
Contact:

Re: Problem 259

Post by nicolas.patrois »

user202729 wrote:
Expand
+ The largest reachable number is 123456789 (multiplication is smaller than concatenation - easy to prove), so 4 byte integer is enough. No integer overflow.
Are you sure? What about 12345*6789?
Image

TripleM
Posts: 382
Joined: Fri Sep 12, 2008 2:31 am

Re: Problem 259

Post by TripleM »

nicolas.patrois wrote:Are you sure? What about 12345*6789?
12345*6789 < 12345*10000 < 123456789.

User avatar
nicolas.patrois
Posts: 118
Joined: Fri Jul 26, 2013 3:54 pm
Contact:

Re: Problem 259

Post by nicolas.patrois »

Hm yes. :oops:
Image

user202729
Posts: 4
Joined: Tue Dec 29, 2015 2:58 pm

Re: Problem 259

Post by user202729 »

My error. Now I have solved it.
Image

User avatar
rmacheshire
Posts: 5
Joined: Wed Nov 04, 2015 6:26 pm
Location: Portugal

Re: Problem 259

Post by rmacheshire »

My problem is that I get the solution but it takes nearly 15 minutes. I took some measurements and I am evaluating 3,392,923,553 expressions, about 3,951,693 per second, which actually seems quite fast. I just don't see how it can be done in 1 minute.

An approximate calculation for the number of expressions to evaluate: there are 8 operators each of which can be +, -, multiply, divide or concatenate, which gives 5^8 possibilities i.e. 390625. Also, by using brackets, the operators can be executed in any order, giving 8! =40320 combinations.

390625 x 40320 = 15,750,000,000

However, this does not allow for concatenation always being done before the other operators, which significantly reduces the number of combinations.

User avatar
sjhillier
Administrator
Posts: 511
Joined: Sun Aug 17, 2014 3:59 pm
Location: Birmingham, UK
Contact:

Re: Problem 259

Post by sjhillier »

It is certainly possible in under a minute, the dedicated thread might have some useful ideas. I didn't get anywhere close to a minute on my first attempt.

On your calculation, yes, there are a lot of potential evaluations to make. But many will be duplicates, so it's an over-estimate of the number of distinct calculations that have to be made.

vamsikal3
Posts: 108
Joined: Sat Oct 01, 2016 8:25 am

Re: Problem 259

Post by vamsikal3 »

Is 123456789 a valid reachable number? I am thinking yes, but, just want to confirm.

Thanks.
my friend key --> 990813_OZPwQtCjkD6KlvxirOoTSZxccMFsuw1L
Image

traxex
Posts: 65
Joined: Thu Oct 19, 2017 12:30 pm

Re: Problem 259

Post by traxex »

vamsikal3 wrote:
Sat Mar 03, 2018 10:05 am
Is 123456789 a valid reachable number?
Yes, it is.
Technically, everyone is full of himself.

vamsikal3
Posts: 108
Joined: Sat Oct 01, 2016 8:25 am

Re: Problem 259

Post by vamsikal3 »

rmacheshire wrote:
Tue Sep 06, 2016 11:43 am
My problem is that I get the solution but it takes nearly 15 minutes. I took some measurements and I am evaluating 3,392,923,553 expressions, about 3,951,693 per second, which actually seems quite fast. I just don't see how it can be done in 1 minute.

An approximate calculation for the number of expressions to evaluate: there are 8 operators each of which can be +, -, multiply, divide or concatenate, which gives 5^8 possibilities i.e. 390625. Also, by using brackets, the operators can be executed in any order, giving 8! =40320 combinations.

390625 x 40320 = 15,750,000,000

However, this does not allow for concatenation always being done before the other operators, which significantly reduces the number of combinations.
Before solving any PE problem, I take a look at this forum to make sure I have as much information as possible. Now, for this problem I looked at this post and got a little scared about the amount of computation that might be needed to solve this problem. So, before solving the problem, I decided to accurately compute the number of expressions (of a length l, 1 <= l <= 9) that need to be computed to solve the problem. Without mentioning the details of my method of exhaustively enumerating the expressions to be evaluated, I get only 178913 different expressions (see below). Am I missing something or did I figure out a nice way to count/generate expressions so I don't have to do the kind of work suggested in the post above.

vamsi@vamsi-laptop:~/learn/project_euler/257_to_384/problem_259$ ../Downloads/kawa-3.0/bin/kawa
#|kawa:1|# (load "main.scm")
167763361

EDIT: I think the question might be answered, as the above post suggests, I am doing concatenation before any other operations.

EDIT2: My computation of the number of expressions that need to be evaluated was incorrect and I was getting a very low wrong value of about 180K expressions, after fixing the bug in computing that number, now I get 168 million expressions which is a big deal. I did find that there are enormous number of duplicates in the computed reachable numbers.
Last edited by vamsikal3 on Wed Mar 07, 2018 2:55 pm, edited 2 times in total.
my friend key --> 990813_OZPwQtCjkD6KlvxirOoTSZxccMFsuw1L
Image

traxex
Posts: 65
Joined: Thu Oct 19, 2017 12:30 pm

Re: Problem 259

Post by traxex »

The problem can be solved very comfortably in under 10 seconds. It doesn't require a scary amount of computation.

I think there are multiple reasonable ways to count distinct expressions that lead to different results. I saw only one count in the dedicated thread and it differs from yours, but you could both be right.
Technically, everyone is full of himself.

vamsikal3
Posts: 108
Joined: Sat Oct 01, 2016 8:25 am

Re: Problem 259

Post by vamsikal3 »

Thanks for your comment. I will know whether my number is correct or not in a few days when I am done implementing my algorithm. In my expression count, two different expressions could possibly result in the same reachable number, so I would expect my number to be higher.

EDIT: The number I came up with originally about 180K expressions is completely wrong, because of a logic bug, I wasn't counting all the expressions. Now, with the bug fixed, I get about 167 million expressions.
my friend key --> 990813_OZPwQtCjkD6KlvxirOoTSZxccMFsuw1L
Image

User avatar
youth4ever
Posts: 11
Joined: Sun Jan 08, 2017 8:34 pm
Contact:

Re: Problem 259

Post by youth4ever »

Hi Eulerians,

I really have frustration with this one. I get 72466 UNIQUE reachable numbers.
Is this even close to the total number of reachable numbers? Thanks.

Post Reply