Minimal steps down to 1: Difference between revisions
Content added Content deleted
(Promote to full task status.) |
|||
Line 184: | Line 184: | ||
There is 1 number in the range 1-50000 that has maximum 'minimal steps' of 26: |
There is 1 number in the range 1-50000 that has maximum 'minimal steps' of 26: |
||
[45925] |
[45925] |
||
</pre> |
|||
=={{header|Java}}== |
|||
Algorithm works with any function that supports the <code>Function</code> interface in the code below. |
|||
<lang java> |
|||
import java.util.ArrayList; |
|||
import java.util.HashMap; |
|||
import java.util.List; |
|||
import java.util.Map; |
|||
public class MinimalStepsDownToOne { |
|||
public static void main(String[] args) { |
|||
runTasks(getFunctions1()); |
|||
runTasks(getFunctions2()); |
|||
runTasks(getFunctions3()); |
|||
} |
|||
private static void runTasks(List<Function> functions) { |
|||
Map<Integer,List<String>> minPath = getInitialMap(functions, 5); |
|||
// Task 1 |
|||
int max = 10; |
|||
populateMap(minPath, functions, max); |
|||
System.out.printf("%nWith functions: %s%n", functions); |
|||
System.out.printf(" Minimum steps to 1:%n"); |
|||
for ( int n = 2 ; n <= max ; n++ ) { |
|||
int steps = minPath.get(n).size(); |
|||
System.out.printf(" %2d: %d step%1s: %s%n", n, steps, steps == 1 ? "" : "s", minPath.get(n)); |
|||
} |
|||
// Task 2 |
|||
displayMaxMin(minPath, functions, 2000); |
|||
// Task 2a |
|||
displayMaxMin(minPath, functions, 20000); |
|||
// Task 2a + |
|||
displayMaxMin(minPath, functions, 100000); |
|||
} |
|||
private static void displayMaxMin(Map<Integer,List<String>> minPath, List<Function> functions, int max) { |
|||
populateMap(minPath, functions, max); |
|||
List<Integer> maxIntegers = getMaxMin(minPath, max); |
|||
int maxSteps = maxIntegers.remove(0); |
|||
int numCount = maxIntegers.size(); |
|||
System.out.printf(" There %s %d number%s in the range 1-%d that have maximum 'minimal steps' of %d:%n %s%n", numCount == 1 ? "is" : "are", numCount, numCount == 1 ? "" : "s", max, maxSteps, maxIntegers); |
|||
} |
|||
private static List<Integer> getMaxMin(Map<Integer,List<String>> minPath, int max) { |
|||
int maxSteps = Integer.MIN_VALUE; |
|||
List<Integer> maxIntegers = new ArrayList<Integer>(); |
|||
for ( int n = 2 ; n <= max ; n++ ) { |
|||
int len = minPath.get(n).size(); |
|||
if ( len > maxSteps ) { |
|||
maxSteps = len; |
|||
maxIntegers.clear(); |
|||
maxIntegers.add(n); |
|||
} |
|||
else if ( len == maxSteps ) { |
|||
maxIntegers.add(n); |
|||
} |
|||
} |
|||
maxIntegers.add(0, maxSteps); |
|||
return maxIntegers; |
|||
} |
|||
private static void populateMap(Map<Integer,List<String>> minPath, List<Function> functions, int max) { |
|||
for ( int n = 2 ; n <= max ; n++ ) { |
|||
if ( minPath.containsKey(n) ) { |
|||
continue; |
|||
} |
|||
Function minFunction = null; |
|||
int minSteps = Integer.MAX_VALUE; |
|||
for ( Function f : functions ) { |
|||
if ( f.actionOk(n) ) { |
|||
int result = f.action(n); |
|||
int steps = 1 + minPath.get(result).size(); |
|||
if ( steps < minSteps ) { |
|||
minFunction = f; |
|||
minSteps = steps; |
|||
} |
|||
} |
|||
} |
|||
int result = minFunction.action(n); |
|||
List<String> path = new ArrayList<String>(); |
|||
path.add(minFunction.toString(n)); |
|||
path.addAll(minPath.get(result)); |
|||
minPath.put(n, path); |
|||
} |
|||
} |
|||
private static Map<Integer,List<String>> getInitialMap(List<Function> functions, int max) { |
|||
Map<Integer,List<String>> minPath = new HashMap<>(); |
|||
for ( int i = 2 ; i <= max ; i++ ) { |
|||
for ( Function f : functions ) { |
|||
if ( f.actionOk(i) ) { |
|||
int result = f.action(i); |
|||
if ( result == 1 ) { |
|||
List<String> path = new ArrayList<String>(); |
|||
path.add(f.toString(i)); |
|||
minPath.put(i, path); |
|||
} |
|||
} |
|||
} |
|||
} |
|||
return minPath; |
|||
} |
|||
private static List<Function> getFunctions3() { |
|||
List<Function> functions = new ArrayList<>(); |
|||
functions.add(new Divide2Function()); |
|||
functions.add(new Divide3Function()); |
|||
functions.add(new Subtract2Function()); |
|||
functions.add(new Subtract1Function()); |
|||
return functions; |
|||
} |
|||
private static List<Function> getFunctions2() { |
|||
List<Function> functions = new ArrayList<>(); |
|||
functions.add(new Divide3Function()); |
|||
functions.add(new Divide2Function()); |
|||
functions.add(new Subtract2Function()); |
|||
return functions; |
|||
} |
|||
private static List<Function> getFunctions1() { |
|||
List<Function> functions = new ArrayList<>(); |
|||
functions.add(new Divide3Function()); |
|||
functions.add(new Divide2Function()); |
|||
functions.add(new Subtract1Function()); |
|||
return functions; |
|||
} |
|||
public abstract static class Function { |
|||
abstract public int action(int n); |
|||
abstract public boolean actionOk(int n); |
|||
abstract public String toString(int n); |
|||
} |
|||
public static class Divide2Function extends Function { |
|||
@Override public int action(int n) { |
|||
return n/2; |
|||
} |
|||
@Override public boolean actionOk(int n) { |
|||
return n % 2 == 0; |
|||
} |
|||
@Override public String toString(int n) { |
|||
return "/2 -> " + n/2; |
|||
} |
|||
@Override public String toString() { |
|||
return "Divisor 2"; |
|||
} |
|||
} |
|||
public static class Divide3Function extends Function { |
|||
@Override public int action(int n) { |
|||
return n/3; |
|||
} |
|||
@Override public boolean actionOk(int n) { |
|||
return n % 3 == 0; |
|||
} |
|||
@Override public String toString(int n) { |
|||
return "/3 -> " + n/3; |
|||
} |
|||
@Override public String toString() { |
|||
return "Divisor 3"; |
|||
} |
|||
} |
|||
public static class Subtract1Function extends Function { |
|||
@Override public int action(int n) { |
|||
return n-1; |
|||
} |
|||
@Override public boolean actionOk(int n) { |
|||
return true; |
|||
} |
|||
@Override public String toString(int n) { |
|||
return "-1 -> " + (n-1); |
|||
} |
|||
@Override public String toString() { |
|||
return "Subtractor 1"; |
|||
} |
|||
} |
|||
public static class Subtract2Function extends Function { |
|||
@Override public int action(int n) { |
|||
return n-2; |
|||
} |
|||
@Override public boolean actionOk(int n) { |
|||
return n > 2; |
|||
} |
|||
@Override public String toString(int n) { |
|||
return "-2 -> " + (n-2); |
|||
} |
|||
@Override public String toString() { |
|||
return "Subtractor 2"; |
|||
} |
|||
} |
|||
} |
|||
</lang> |
|||
{{out}} |
|||
<pre> |
|||
With functions: [Divisor 3, Divisor 2, Subtractor 1] |
|||
Minimum steps to 1: |
|||
2: 1 step : [-1 -> 1] |
|||
3: 1 step : [/3 -> 1] |
|||
4: 2 steps: [/2 -> 2, -1 -> 1] |
|||
5: 3 steps: [-1 -> 4, /2 -> 2, -1 -> 1] |
|||
6: 2 steps: [/3 -> 2, -1 -> 1] |
|||
7: 3 steps: [-1 -> 6, /3 -> 2, -1 -> 1] |
|||
8: 3 steps: [/2 -> 4, /2 -> 2, -1 -> 1] |
|||
9: 2 steps: [/3 -> 3, /3 -> 1] |
|||
10: 3 steps: [-1 -> 9, /3 -> 3, /3 -> 1] |
|||
There are 16 numbers in the range 1-2000 that have maximum 'minimal steps' of 14: |
|||
[863, 1079, 1295, 1439, 1511, 1583, 1607, 1619, 1691, 1727, 1823, 1871, 1895, 1907, 1919, 1943] |
|||
There are 5 numbers in the range 1-20000 that have maximum 'minimal steps' of 20: |
|||
[12959, 15551, 17279, 18143, 19439] |
|||
There is 1 number in the range 1-100000 that have maximum 'minimal steps' of 24: |
|||
[77759] |
|||
With functions: [Divisor 3, Divisor 2, Subtractor 2] |
|||
Minimum steps to 1: |
|||
2: 1 step : [/2 -> 1] |
|||
3: 1 step : [-2 -> 1] |
|||
4: 2 steps: [/2 -> 2, /2 -> 1] |
|||
5: 2 steps: [-2 -> 3, -2 -> 1] |
|||
6: 2 steps: [/3 -> 2, /2 -> 1] |
|||
7: 3 steps: [-2 -> 5, -2 -> 3, -2 -> 1] |
|||
8: 3 steps: [/2 -> 4, /2 -> 2, /2 -> 1] |
|||
9: 2 steps: [/3 -> 3, -2 -> 1] |
|||
10: 3 steps: [/2 -> 5, -2 -> 3, -2 -> 1] |
|||
There is 1 number in the range 1-2000 that have maximum 'minimal steps' of 17: |
|||
[1699] |
|||
There is 1 number in the range 1-20000 that have maximum 'minimal steps' of 24: |
|||
[19681] |
|||
There is 1 number in the range 1-100000 that have maximum 'minimal steps' of 28: |
|||
[98413] |
|||
With functions: [Divisor 2, Divisor 3, Subtractor 2, Subtractor 1] |
|||
Minimum steps to 1: |
|||
2: 1 step : [-1 -> 1] |
|||
3: 1 step : [-2 -> 1] |
|||
4: 2 steps: [/2 -> 2, -1 -> 1] |
|||
5: 2 steps: [-2 -> 3, -2 -> 1] |
|||
6: 2 steps: [/2 -> 3, -2 -> 1] |
|||
7: 3 steps: [-2 -> 5, -2 -> 3, -2 -> 1] |
|||
8: 3 steps: [/2 -> 4, /2 -> 2, -1 -> 1] |
|||
9: 2 steps: [/3 -> 3, -2 -> 1] |
|||
10: 3 steps: [/2 -> 5, -2 -> 3, -2 -> 1] |
|||
There is 1 number in the range 1-2000 that have maximum 'minimal steps' of 13: |
|||
[1943] |
|||
There are 2 numbers in the range 1-20000 that have maximum 'minimal steps' of 17: |
|||
[17495, 19439] |
|||
There are 22 numbers in the range 1-100000 that have maximum 'minimal steps' of 19: |
|||
[58319, 69983, 76463, 77759, 78623, 87479, 89423, 90071, 90287, 90359, 90383, 90395, 91259, 91355, 91367, 93311, 95255, 95471, 95903, 96119, 96191, 98171] |
|||
</pre> |
</pre> |
||