7
\$\begingroup\$

(Inspired by this question)

The digits of the cube, 41063625 (3453), can be permuted to produce two other cubes:

56623104 (3843) and 66430125 (4053). In fact, 41063625 is the smallest cube which has exactly three permutations of its digits which are also cube.

Find the smallest cube for which exactly five permutations of its digits are cube.

My attempt at #62 using Java 8 streams. I use a custom implementation of Spliterator.OfLong (uncreatively named Generator) that can be programmatically stopped when the Map it is collect()-ing to has the desired results. I also chose a custom Result class to store related information about the generation. For example, the desired result for this challenge is:

----------
Size: 5
Map size: 7772
Last value: 8384
Ratio: 1.0787442099845599
Elapsed time (ms): 16
Result: 127035954683
Values: [5027, 7061, 7202, 8288, 8384]
----------

(This is after one "warm-up" round as shown in the main() method)

  • Is this a feasible approach, or does it really smell 'hack-ish'?
  • Any other room for improvement?

My toKey() method is based on my answer to this question.

public final class EulerSixtyTwo {
    private static final ToLongFunction<Long> CUBE =
            i -> (long) Math.pow(i.doubleValue(), 3);

    private static Long toKey(Long input) {
        int[] numbers = new int[10];
        for (long i = CUBE.applyAsLong(input); i != 0; i /= 10) {
            numbers[(int) (i % 10)]++;
        }
        int counter = 0;
        long result = 0;
        for (int i = 0; i < 10; counter += numbers[i++]) {
            result += (int) ((Math.pow(10, numbers[i]) * i - 1) / 9)
                    * Math.pow(10, counter);
        }
        return Long.valueOf(result);
    }

    private static List<Long> toValue(Long input) {
        return new ArrayList<>(Collections.singleton(input));
    }

    private static Result testFor(int limit) {
        if (limit < 2) {
            throw new IllegalArgumentException("Limit cannot be less than 2.");
        }
        Generator generator = new Generator();
        long startTime = System.currentTimeMillis();
        Map<Long, List<Long>> map = generator.longStream().boxed()
                .collect(Collectors.toMap(EulerSixtyTwo::toKey, EulerSixtyTwo::toValue,
                            (a, b) -> {
                                generator.shouldStop(a.addAll(b) && a.size() == limit);
                                return a;
                            }));
        long elapsedTime = System.currentTimeMillis() - startTime;
        return new Result(toKey(generator.getLastValue()), map, elapsedTime);
    }

    private static final int START = 2;
    private static final int END = 21;

    public static void main(String[] args) {
        // "warm-up"
        IntStream.range(START, END).mapToObj(EulerSixtyTwo::testFor)
                .forEach(v -> {});
        IntStream.range(START, END).mapToObj(EulerSixtyTwo::testFor)
                .forEach(System.out::println);
    }

    public static class Generator implements Spliterator.OfLong {

        private boolean stop = false;
        private long current = 1;

        @Override
        public long estimateSize() {
            return Long.MAX_VALUE;
        }

        @Override
        public int characteristics() {
            return Spliterator.ORDERED + Spliterator.DISTINCT;
        }

        @Override
        public java.util.Spliterator.OfLong trySplit() {
            return null;
        }

        @Override
        public boolean tryAdvance(LongConsumer action) {
            action.accept(current++);
            return !stop;
        }

        public void shouldStop(boolean shouldStop) {
            stop = shouldStop;
        }

        public Long getLastValue() {
            return Long.valueOf(current - 1);
        }

        public LongStream longStream() {
            return StreamSupport.longStream(this, false);
        }
    }

    public static class Result {
        private static final String WRAPPER = "\n----------\n";

        private final long answer;
        private final Map<Long, List<Long>> map;
        private final List<Long> values;
        private final long elapsedTime;
        private final String toString;

        public Result(Long key, Map<Long, List<Long>> map, long elapsedTime) {
            this.map = Collections.unmodifiableMap(map);
            this.values = map.get(key);
            this.answer = CUBE.applyAsLong(values.get(0));
            this.elapsedTime = elapsedTime;
            this.toString = getStatistics();
        }

        public long getAnswer() {
            return answer;
        }

        public List<Long> getValues() {
            return values;
        }

        private String getStatistics() {
            int mapSize = map.size();
            long lastValue = values.get(values.size() - 1).longValue();
            double ratio = lastValue / (double) mapSize;
            return Stream.of("Size: " + values.size(), "Map size: " + mapSize,
                            "Last value: " + lastValue, "Ratio: " + ratio,
                            "Elapsed time (ms): " + elapsedTime,
                            "Result: " + getAnswer(),
                            "Values: " + getValues()).map(Object::toString)
                    .collect(Collectors.joining("\n", WRAPPER, WRAPPER));
        }

        @Override
        public String toString() {
            return toString;
        }
    }
}
\$\endgroup\$
  • 2
    \$\begingroup\$ well, I am very happy, my question inspired someone. \$\endgroup\$ – RE60K Jun 5 '15 at 17:49
2
\$\begingroup\$

I guess, I'll sound rather negative and that's mostly caused by my lack of experience with Java 8.

private static final ToLongFunction<Long> CUBE =
        i -> (long) Math.pow(i.doubleValue(), 3);

While this works fine for small values, you'd get round-off errors when they get bigger (presumably somewhere near 1e16, which is a lot, but much lower than Long.MAX_VALUE; and there are many Euler problem needing 1e18). And there's no need to take a chance as

        i -> i * i * i;

is both shorter and cleaner. And faster, too.

private static Long toKey(Long input) {
    int[] numbers = new int[10];
    for (long i = CUBE.applyAsLong(input); i != 0; i /= 10) {
        numbers[(int) (i % 10)]++;
    }

Wouldn't "digits" be a better name?

    int counter = 0;
    long result = 0;
    for (int i = 0; i < 10; counter += numbers[i++]) {
        result += (int) ((Math.pow(10, numbers[i]) * i - 1) / 9)
                * Math.pow(10, counter);
    }
    return Long.valueOf(result);
}

That was a mystery to me for a few minutes. I guessed, it should do the same as my below method does (I've solved the problem some time ago)

private Multiset<Long> toKey(long x) {
    final Multiset<Long> result = HashMultiset.create();
    for (; x > 0; x /= 10) result.add(x%10);
    return result;
}

namely create a key based on the digits while ignoring their order. How I understand it, but it could use quite some comments. I'd simply go for this

    for (int i = 0; i < 10; ++i) {
         for (j = numbers[i]; j > 0; --j) {
              result = 10 * result + i;
    }
    return Long.valueOf(result);

The following looks like you could use Guava's Multimap, which allows multiple values per key without such strain:

private static List<Long> toValue(Long input) {
    return new ArrayList<>(Collections.singleton(input));
}

This is fine here, but shouldn't be used for any serious benchmark

long startTime = System.currentTimeMillis();

The precision is much worse than for nanoTime and mainly: There's no monotonicity guarantee.

    Map<Long, List<Long>> map = generator.longStream().boxed()
            .collect(Collectors.toMap(EulerSixtyTwo::toKey, EulerSixtyTwo::toValue,
                        (a, b) -> {
                            generator.shouldStop(a.addAll(b) && a.size() == limit);
                            return a;
                        }));

I see, you're adding the second value to the first and keeping the first, i.e. computing set union. That's fine, but after generator.shouldStop it's the second side-effect in this snippet.

What's worse: You should "find the smallest cube for which exactly five permutations of its digits are cube" and you're finding one having at least five such permutations (AFAIK using == doesn't matter as you stop immediately).

    return new Result(toKey(generator.getLastValue()), map, elapsedTime);

I see, extracting the result from the map would be way more complicated.

    public void shouldStop(boolean shouldStop) {
        stop = shouldStop;
    }

It's actually a setter, and I'd strongly prefer

    public void shouldStop(boolean shouldStop) {
        this.shouldStop = shouldStop;
    }

so I don't have to relate the field, the variable, and the setter names.

Is this a feasible approach, or does it really smell 'hack-ish'?

To me it partly looks like using functional syntax for a not so functional style (I'm not claiming pure functional programming could work for this). I guess, there simply isn't much room for advantageous use of Java 8 features in this problem and that's not your fault.

\$\endgroup\$
  • \$\begingroup\$ No worries about sounding negative, I'm glad that I've learned something from your answer! :) Extracting the result from the Map is actually straightforward: once the List (as the Map's value) has the desired size, just cube the first element inside my merge function. As mentioned in my question, I have the Result class just to store some additional information. \$\endgroup\$ – h.j.k. Jun 6 '15 at 2:45
  • \$\begingroup\$ I also forgot to mention this in my question originally (have edited to included this info), the toKey() method is from my answer to this other question about rearranging numbers to get the largest number. I figured using math will be good enough for the usage here. \$\endgroup\$ – h.j.k. Jun 6 '15 at 2:51
  • 1
    \$\begingroup\$ @h.j.k. Good! I also forget to say that I'd avoid Math.pow as the problems are not worth it. Use new int[] {1, 10, 100, ...} and you'll get more speed and an exception as a bonus if you do anything wrong. \$\endgroup\$ – maaartinus Jun 6 '15 at 15:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.