• Post Reply Bookmark Topic Watch Topic
  • New Topic

Programming puzzle  RSS feed

 
Tony Mannatt
Greenhorn
Posts: 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
 
Tim Cooke
Marshal
Posts: 4051
239
Clojure IntelliJ IDE Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
Campbell Ritchie
Marshal
Posts: 56584
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Welcome to the Ranch

As an alternative, we have reversible languages which can try all sorts of permutations and backtrack whenever they encounter an error. But you want something which works in Java®?
 
Campbell Ritchie
Marshal
Posts: 56584
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Tony Mannatt wrote:. . .. . .
Line1 and Line 2 ⊢ A + B = D + E.
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
Master Rancher
Posts: 2044
75
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
Liutauras Vilda
Sheriff
Posts: 4928
334
BSD
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Master Rancher
Posts: 2044
75
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
Piet Souris
Master Rancher
Posts: 2044
75
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Oops: your additions might make my reply invalid. If so, I apologize!
 
Liutauras Vilda
Sheriff
Posts: 4928
334
BSD
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
Liutauras Vilda
Sheriff
Posts: 4928
334
BSD
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Please ignore my previous posts. I was wrong. X cannot represent 10. So it is simply 1. I am sorry, was too hurry.
 
Piet Souris
Master Rancher
Posts: 2044
75
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
It was a very interesting reasoning nevertheless      
 
Liutauras Vilda
Sheriff
Posts: 4928
334
BSD
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Piet Souris wrote:It is handy to think of XY as: 10 * X + Y.

I slipped on this and don't know where my minds started running..
 
Tobias Bachert
Ranch Hand
Posts: 86
18
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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).
 
fred rosenberger
lowercase baba
Bartender
Posts: 12565
49
Chrome Java Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Tony Mannatt wrote:
Every letter represents always the same number.

I think you mean every letter always represents the same digit
 
Liutauras Vilda
Sheriff
Posts: 4928
334
BSD
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Please clarify if all digits in all equations must be unique? For example, X or Y can be same or can not as one of A, B, C, D, E, F, G ?
 
Zachary Griggs
Ranch Hand
Posts: 83
10
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
 
Liutauras Vilda
Sheriff
Posts: 4928
334
BSD
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.

 
Piet Souris
Master Rancher
Posts: 2044
75
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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!
 
Campbell Ritchie
Marshal
Posts: 56584
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Liutauras Vilda wrote:Please clarify if all digits in all equations must be unique . . .
For this sort of exercise, yes, the letters represent different digits from one another (=unique).
 
Carey Brown
Saloon Keeper
Posts: 3329
46
Eclipse IDE Firefox Browser Java MySQL Database VI Editor Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!