Tony Mannatt

Greenhorn

Posts: 1

posted 4 weeks ago

I have to solve a puzzle with a algorithm

The puzzle is:

A + B + C = XY

D + E + C = XY

F + E + B = XY

G + C + B + Y = XY

X + E + G + C = XY

G + A + C + D = XY

E + D + G + F = XY

Every letter represents always the same number.

XY is a two digit number.

Need to find out the value of XY

Im quite lost atm. All hints would be awesome.

I think i need to somehow loop through numbers 0 to 9 and check the equations, but cant think of a way to increment the values so that every option would be checked

The puzzle is:

A + B + C = XY

D + E + C = XY

F + E + B = XY

G + C + B + Y = XY

X + E + G + C = XY

G + A + C + D = XY

E + D + G + F = XY

Every letter represents always the same number.

XY is a two digit number.

Need to find out the value of XY

Im quite lost atm. All hints would be awesome.

I think i need to somehow loop through numbers 0 to 9 and check the equations, but cant think of a way to increment the values so that every option would be checked

posted 4 weeks ago

This one has my brain churning too, what a fun puzzle.

Now, instinctively I would be reaching for a declarative programming language such as Prolog or ASP, but I assume you're looking at solving this using Java? If so then you'll be needing some loops and loops within loops to generate all the permutations of A to G. Also you'll need somewhere to store the results of adding up all those permutations. And lastly you'll need some way of splitting those results into the character parts of the resulting number.

It sounds like there's a lot there but start at the beginning and tackle it bit by bit. Come back, show us what you've got, and explain what you're stuck on.

Now, instinctively I would be reaching for a declarative programming language such as Prolog or ASP, but I assume you're looking at solving this using Java? If so then you'll be needing some loops and loops within loops to generate all the permutations of A to G. Also you'll need somewhere to store the results of adding up all those permutations. And lastly you'll need some way of splitting those results into the character parts of the resulting number.

It sounds like there's a lot there but start at the beginning and tackle it bit by bit. Come back, show us what you've got, and explain what you're stuck on.

Tim Driven Development

Campbell Ritchie

Sheriff

Posts: 54495

150

Campbell Ritchie

Sheriff

Posts: 54495

150

posted 4 weeks ago

Assuming that two‑digit numbers don't start with 0, X = 1 ∨ X = 2, because you cannot add three different one‑digit numbers and get a result > 24.

Line 1 and line 3 ⊢ A + C = F + E.

Now, if A + B = D + E, that sets minima and maxima for those four numbers. If A is 1, then then minimum for B is 4, but you would then constrain X to be 2, so those figures won't add up. So we can see that each of those letters is constrained by its potential values. Keep going through those numbers and you will be able to reduce the possibilities you have to consider.

Note you have nine different numbers, out of the potential ten.

Line1 and Line 2 ⊢ A + B = D + E.Tony Mannatt wrote:. . .. . .

Assuming that two‑digit numbers don't start with 0, X = 1 ∨ X = 2, because you cannot add three different one‑digit numbers and get a result > 24.

Line 1 and line 3 ⊢ A + C = F + E.

Now, if A + B = D + E, that sets minima and maxima for those four numbers. If A is 1, then then minimum for B is 4, but you would then constrain X to be 2, so those figures won't add up. So we can see that each of those letters is constrained by its potential values. Keep going through those numbers and you will be able to reduce the possibilities you have to consider.

Note you have nine different numbers, out of the potential ten.

Piet Souris

Rancher

Posts: 1885

64

posted 4 weeks ago

X can only be 1 (as Campbell wrote, but X = 0 and X = 2 are impossible). If you do not see why this is so, then let us not take any risk and let X either be 1 or 2.

It is handy to think of XY as: 10 * X + Y.

That will allow you to simplify the equations 4 and 5.

Now for any tips:

1) you can let X vary from 1 to 2 and Y from 0 to 9, or let XY vary from 10 to 24.

2) you can write all the equation in a matrix form, where the first row is equal to 1, 1, 1, 0, 0, 0, 0, the second to 0, 0, 1, 1, 1, 0, 0 et cetera. If you use the Apache Math library, you can get the inverse of this matrix, and then the solution is easily found

3) but I presume that that is not what this assignment is about. So another well known option is to manipulate all the rows (subtracting one from another et cetera) untill you have a unity matrix. But this is not so easy to implement.

4) then there is good old brute force. Assuming that A...G are all different digits, and that X and Y are not necessarily different from the other digits, then the number of tries is 9! / 2 * 15 (15 from XY going from 10 to 24).

That is do-able, but there are many optimizations. If you try a digit for, say, C, then if that digit is already used for A or B, you can continue with the next digit. And if A + B + C fails to equal XY, then et cetera.

It is handy to think of XY as: 10 * X + Y.

That will allow you to simplify the equations 4 and 5.

Now for any tips:

1) you can let X vary from 1 to 2 and Y from 0 to 9, or let XY vary from 10 to 24.

2) you can write all the equation in a matrix form, where the first row is equal to 1, 1, 1, 0, 0, 0, 0, the second to 0, 0, 1, 1, 1, 0, 0 et cetera. If you use the Apache Math library, you can get the inverse of this matrix, and then the solution is easily found

3) but I presume that that is not what this assignment is about. So another well known option is to manipulate all the rows (subtracting one from another et cetera) untill you have a unity matrix. But this is not so easy to implement.

4) then there is good old brute force. Assuming that A...G are all different digits, and that X and Y are not necessarily different from the other digits, then the number of tries is 9! / 2 * 15 (15 from XY going from 10 to 24).

That is do-able, but there are many optimizations. If you try a digit for, say, C, then if that digit is already used for A or B, you can continue with the next digit. And if A + B + C fails to equal XY, then et cetera.

posted 4 weeks ago

Taking this Piet's hint, we can conclude something about E, G and C (looking to 5th equation). Which means that sum of all three numbers are equal to Y, meaning each individual of those numbers is less than Y.

From earlier we knew, that Y theoretically can be between 0 and 9, but from the whole and latest knowledge, we know, that X is 1, so Y can't be 1 as well as E or G or C cannot be 1, that means, they need to be 2 or 3 or 4 or more. But think again, their sum can be more than 9? Nope, because Y is 9. Now need to find out which one is which:

E = 2 or 3 or 4

G = 2 or 3 or 4

C = 2 or 3 or 4

Piet Souris wrote:It is handy to think of XY as: 10 * X + Y.

That will allow you to simplify the equations 4 and 5.

Taking this Piet's hint, we can conclude something about E, G and C (looking to 5th equation). Which means that sum of all three numbers are equal to Y, meaning each individual of those numbers is less than Y.

From earlier we knew, that Y theoretically can be between 0 and 9, but from the whole and latest knowledge, we know, that X is 1, so Y can't be 1 as well as E or G or C cannot be 1, that means, they need to be 2 or 3 or 4 or more. But think again, their sum can be more than 9? Nope, because Y is 9. Now need to find out which one is which:

E = 2 or 3 or 4

G = 2 or 3 or 4

C = 2 or 3 or 4

Piet Souris

Rancher

Posts: 1885

64

posted 4 weeks ago

hi Liutauras,

I am a little doubtfull about this. Equation 5 becomes: G + E + C = 9 * X + Y, and I do not see how you can draw the conclusion that Y > 6. But probably I'm overlooking something? Of course, since X > 0 it follows that G, C and E cannot be 1, 2 and 3. But incorporating all these conclusions makes a brute force implementation not easier.

I am a little doubtfull about this. Equation 5 becomes: G + E + C = 9 * X + Y, and I do not see how you can draw the conclusion that Y > 6. But probably I'm overlooking something? Of course, since X > 0 it follows that G, C and E cannot be 1, 2 and 3. But incorporating all these conclusions makes a brute force implementation not easier.

Piet Souris

Rancher

Posts: 1885

64

posted 4 weeks ago

I'm sorry because I was distracted and had to edit my post multiple times.

X + E + G + C = XY

Based on your hint, X is 10. Y can be 0 to 9 in theory. But since on the left we have X, that means E + G + C need to be <= 9 in theory. But since we know that X is 1, that means Y nor E nor G nor C cannot be 1, that means E, G, C need to be 2, 3 and 4 respectively, because 2 + 3 + 4 = 9.

So I can conclude Y = 9. Unless I overlooking.

X + E + G + C = XY

Based on your hint, X is 10. Y can be 0 to 9 in theory. But since on the left we have X, that means E + G + C need to be <= 9 in theory. But since we know that X is 1, that means Y nor E nor G nor C cannot be 1, that means E, G, C need to be 2, 3 and 4 respectively, because 2 + 3 + 4 = 9.

So I can conclude Y = 9. Unless I overlooking.

Piet Souris

Rancher

Posts: 1885

64

Tobias Bachert

Ranch Hand

Posts: 77

15

posted 4 weeks ago

I would use simple backtracking as there are not that many permutations to test (quite inefficient approach (written in ~3 minutes) took <1 sec to solve it) - Overthinking may result in incorrect conclusions (i.e. is the conclusion that X has to be 1 not necessarily true).

Zachary Griggs

Ranch Hand

Posts: 80

10

posted 4 weeks ago

Plan for solving the problem:

Make those 9 variables

Make nested for loops which iterate each possible value (0-9). It's important that they be nested to get every possible permutation.

Check the numbers with each formula

Check for uniqueness

Note: Nesting 9 levels of for loops is not a good thing to do unless you're solving a puzzle like this. This one runs pretty quickly, but that's only because it's only 0-9.

This problem is quite easy to brute force, but it might not be if it can go higher than 9.

You can solve it mathematically but it's very hard.

SPOILER ALERT! Solution: https://pastebin.com/neL3y48E

Make those 9 variables

Make nested for loops which iterate each possible value (0-9). It's important that they be nested to get every possible permutation.

Check the numbers with each formula

Check for uniqueness

Note: Nesting 9 levels of for loops is not a good thing to do unless you're solving a puzzle like this. This one runs pretty quickly, but that's only because it's only 0-9.

This problem is quite easy to brute force, but it might not be if it can go higher than 9.

You can solve it mathematically but it's very hard.

SPOILER ALERT! Solution: https://pastebin.com/neL3y48E

posted 4 weeks ago

Alright, this is what I thought too, that all digits need to be unique, including X and Y values too. Instructions are confusing a bit, because says same letter always represent same number, but doesn't say nothing about uniqueness.

I was solving on a piece of paper today by writing equations and and then constraints which letters cannot be what digit, which letters have higher value digits, and which letters can hold values within ranges 5-8, 6-9 and 1-4.

Now, I don't have my notes at home, but I remember I came up to 3 possible 2-digit numbers as a sum instead XY: 21, 23 or 24 and got rough digits within small bounds for the rest and didn't finish.

0 I remember was impossible to be a digit, because that would make one letter value to be equal to another, and then got a doubt if indeed all values need to be unique - hence asked OP to clarify that.

I was solving on a piece of paper today by writing equations and and then constraints which letters cannot be what digit, which letters have higher value digits, and which letters can hold values within ranges 5-8, 6-9 and 1-4.

Now, I don't have my notes at home, but I remember I came up to 3 possible 2-digit numbers as a sum instead XY: 21, 23 or 24 and got rough digits within small bounds for the rest and didn't finish.

0 I remember was impossible to be a digit, because that would make one letter value to be equal to another, and then got a doubt if indeed all values need to be unique - hence asked OP to clarify that.

Piet Souris

Rancher

Posts: 1885

64

posted 4 weeks ago

My hasty conclusion that X had to be 1 was based on these equations: A + B + C = XY, D + E + F = XY,

but looking more closely, I see that these two equations together are not present. So indeed X could be 2 as well (I'm not saying that it is!).

I got a four times-nested loop in XY, A, B and D, running in 0.4 seconds on my laptop with verry fresh Java 1.8.131 and NetBeans 8.2.

I hope that with all our remarks so far, with Tobias's backtracking, Campbells and Liutauras' clever deductions, and with Zachary's tips and mine on manipulating the rows and invertion of a Matrix ( ) that Tony has enough clues to make progress.

And o ja: all digits are different!

but looking more closely, I see that these two equations together are not present. So indeed X could be 2 as well (I'm not saying that it is!).

I got a four times-nested loop in XY, A, B and D, running in 0.4 seconds on my laptop with verry fresh Java 1.8.131 and NetBeans 8.2.

I hope that with all our remarks so far, with Tobias's backtracking, Campbells and Liutauras' clever deductions, and with Zachary's tips and mine on manipulating the rows and invertion of a Matrix ( ) that Tony has enough clues to make progress.

And o ja: all digits are different!

Campbell Ritchie

Sheriff

Posts: 54495

150

posted 3 weeks ago

Create an array that holds 10 ints where each int is one of A, B, C..., and the 10th one is unused except to hold whichever digit is not currently in play.

Initialize the array to hold the values zero through nine.

With a recursive method go through all permutations of the array, checking each permutation against the formulas.

I had most of the recursive method written but was struggling with the last bit of logic. I ended up googling "permutations". The whole program was very compact except for the verbose check() and print() methods.

Initialize the array to hold the values zero through nine.

With a recursive method go through all permutations of the array, checking each permutation against the formulas.

I had most of the recursive method written but was struggling with the last bit of logic. I ended up googling "permutations". The whole program was very compact except for the verbose check() and print() methods.

Some people, when confronted with a problem, think "I know, I'll use regular expressions." Now they have two problems.