Well we already know much about the Friedman number at my sister blog (tellmehow.co). If you want to know about this number then check the given blog.
Let’s move to recipe of Friedman number
What is the concept behind the Friedman number?
This number is little bit complex in first time hearing. But today I am going to share the real concept/logic which we are using to find the given number is Friedman number or not.
Let’s take an example: 125 is a Friedman number or not.
Step 1: Find the permutation for given number
In the beginning, We have to find the permutation of given number . So in this case permutation of 125 would be [125, 215, 512]. So how to find the permutation of given string? This is the first hurdle of our logic.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
public static Set<String> getPermutation(String str) { // create a set to avoid duplicate permutation Set<String> permutations = new HashSet<String>(); // check if string is null if (str == null) { return null; } else if (str.length() == 0) { // terminating condition for recursion permutations.add(""); return permutations; } // get the first character char first = str.charAt(0); // get the remaining substring String sub = str.substring(1); // make recursive call to getPermutation() Set<String> words = getPermutation(sub); // access each element from words for (String strNew : words) { for (int i = 0;i<=strNew.length();i++){ // insert the permutation to the set permutations.add(strNew.substring(0, i) + first + strNew.substring(i)); } } return permutations; } } |
Output of above program for number 125 would be:
[125, 521, 215, 512, 251, 152]
Step 2: Create expression for Friedman number and evalute them
In the next step we have to Iterate the Set data and find the expression and evaluate that.
Don’t worry about it this is the important logic part to find the Friedman number. In this step you have to create expression with given permutated number.
(expression1 symbol expression2) i.e (1+25), (12-5), (12^5) etc. and evaluate that expression. So what would we do next?
We are going to find the expression1 and expression 2 firstly. As we know that length of 125 is 3. So for the first expression, we are going to substring the given string from 0 to length-1. And for second expression substring the given data 1 to length.
From the above statement, expression1 would be from 12 i.e. 1, 2, 12, 21 and expression 2 would be from 25 i.e. 2, 5 , 25, 52.
For making a proper expression, we have to add symbols (+, -, *, /, ^) between the the above expression1 and expression2. For that we creating a array of symbol.
|
1 |
static String symb[] = {"+","-","*","/","^"}; |
Step 3: Club and generate valid expression
Now club the all our discussion in Step 2.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
public static HashMap<String, Object> findExpression(String str) { HashMap<String, Object> ls = new HashMap<String, Object>(); ls.put(str, Integer.parseInt(str)); for(int i =1; i < str.length(); i++) { HashMap<String, Object> e11 = findExpression(str.substring(0,i)); for (Map.Entry<String, Object> e1 : e11.entrySet()) { HashMap<String, Object> e22 = findExpression(str.substring(i)); for (Map.Entry<String, Object> e2 : e22.entrySet()) { for(int x=0; x<symb.length; x++) { String d = "("+e1.getKey()+symb[x]+e2.getKey()+")"; if(FindValidExpression.isValidExpression(d)) { ls.put(d, FindValidExpression.eval(d)); } } } } } return ls; } |
At the line number 5 and 7, we find the expression1 and expression 2 respectively. Then another loop for symbol array at line number 9.
See the line 10, for the expression which generating by these three recursive loop. Now we have to find the generated expression is valid or not.
Step 4: Find expression is valid or not
Now we are going to find the generated expression is valid or not in Java.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 |
public static boolean isValidExpression(String expression) { // TEST 1 if (isAnOperator(expression.charAt(0)) || isAnOperator(expression.charAt(expression.length() - 1))) { return false; } int openParenthCount = 0; boolean lastWasOp = false; boolean lastWasOpen = false; for (char c : expression.toCharArray()) { if(c == ' ') continue; if (c == '(') { openParenthCount++; lastWasOpen = true; continue; } else if (c == ')') { if (openParenthCount <= 0 || lastWasOp) { return false; } openParenthCount--; }else if (isAnOperator(c)){ if (lastWasOp || lastWasOpen) return false; lastWasOp = true; continue; }else if(!isANumber(c)){ return false; } lastWasOp = false; lastWasOpen = false; } if(openParenthCount != 0) return false; if(lastWasOp || lastWasOpen) return false; return true; } |
Output:
(1+25)
If it return true then we will evaluate the given expression.
Step 5: Evaluate the generated expression
Find the output of given expression string in Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 |
public static double eval(final String str) { return new Object() { int pos = -1, ch; void nextChar() { ch = (++pos < str.length()) ? str.charAt(pos) : -1; } boolean eat(int charToEat) { while (ch == ' ') nextChar(); if (ch == charToEat) { nextChar(); return true; } return false; } double parse() { nextChar(); double x = parseExpression(); if (pos < str.length()) throw new RuntimeException("Unexpected: " + (char)ch); return x; } // Grammar: // expression = term | expression `+` term | expression `-` term // term = factor | term `*` factor | term `/` factor // factor = `+` factor | `-` factor | `(` expression `)` // | number | functionName factor | factor `^` factor double parseExpression() { double x = parseTerm(); for (;;) { if (eat('+')) x += parseTerm(); // addition else if (eat('-')) x -= parseTerm(); // subtraction else return x; } } double parseTerm() { double x = parseFactor(); for (;;) { if (eat('*')) x *= parseFactor(); // multiplication else if (eat('/')) x /= parseFactor(); // division else return x; } } double parseFactor() { if (eat('+')) return parseFactor(); // unary plus if (eat('-')) return -parseFactor(); // unary minus double x; int startPos = this.pos; if (eat('(')) { // parentheses x = parseExpression(); eat(')'); } else if ((ch >= '0' && ch <= '9') || ch == '.') { // numbers while ((ch >= '0' && ch <= '9') || ch == '.') nextChar(); x = Double.parseDouble(str.substring(startPos, this.pos)); } else if (ch >= 'a' && ch <= 'z') { // functions while (ch >= 'a' && ch <= 'z') nextChar(); String func = str.substring(startPos, this.pos); x = parseFactor(); if (func.equals("sqrt")) x = Math.sqrt(x); else if (func.equals("sin")) x = Math.sin(Math.toRadians(x)); else if (func.equals("cos")) x = Math.cos(Math.toRadians(x)); else if (func.equals("tan")) x = Math.tan(Math.toRadians(x)); else throw new RuntimeException("Unknown function: " + func); } else { throw new RuntimeException("Unexpected: " + (char)ch); } if (eat('^')) x = Math.pow(x, parseFactor()); // exponentiation return x; } }.parse(); } |
Output
(1+25) – 26
Step 6: Finally check the given number and evaluate number is same or not
Now check the given string i.e 125 with the output of above evaluation of expression. If both are same then that number is friedman number and generated expression is correct for that number.
If you want full working source code for find the number is Friedman number or not then fork me at given link.
Welcome for new coder who can optimize the code and run for 10 digit. Are you accepting my challenge? Comment me what you think.