Anonymous user
Minimal steps down to 1: Difference between revisions
→{{header|Go}}
(Promote to full task status.) |
|||
Line 184:
There is 1 number in the range 1-50000 that has maximum 'minimal steps' of 26:
[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>
| |||