3n + 1 문제

README.md

문제

• 이론 설명 : 콜라츠 추측
• 문제 설명 :
  • 한글 : http://codingdojang.com/scode/409
  • 영어 : http://www.programming-challenges.com/pg.php?page=downloadproblem&probid=110101&format=html
• 평가
  • http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=36
  • http://www.spoj.com/problems/PROBTNPO/

build.gradle

apply plugin: 'java'
apply plugin: 'eclipse'
apply plugin: 'idea'

compileJava {
	sourceCompatibility = 1.8
	targetCompatibility = 1.8
}
repositories {
	mavenCentral()
}
 
dependencies {
	testCompile('org.easytesting:fest-assert-core:2.0M10')
	testCompile("org.springframework.boot:spring-boot:1.1.2.RELEASE")
	testCompile("commons-io:commons-io:2.4")
	testCompile("junit:junit:4.11")
}

input.txt

1 10
100 200
201 210
900 1000

ouput.txt

1 10 20
100 200 125
201 210 89
900 1000 174

ThreedNPlusOne.java

package issue1;

import java.util.PrimitiveIterator;
import java.util.Scanner;
import java.util.Spliterator;
import java.util.Spliterators;
import java.util.function.IntUnaryOperator;
import java.util.stream.IntStream;
import java.util.stream.LongStream;
import java.util.stream.StreamSupport;

/**
 * java8, if/for 문 없이 구현
 *
 */
public class ThreeNPlusOne {
	private static final IntUnaryOperator[] evenOddFunc = {
			(n -> n / 2), 
			(n -> n*3 + 1)
	}; // if분기가 더 무난한 방법이지만 람다를 일부러 써보기 위해서 함수배열을 만들어봄

	private static class DownToOneIterator implements PrimitiveIterator.OfInt {
		private int comingValue;;
		private int currentValue;
		
		public DownToOneIterator(int seed) {
			this.comingValue = seed;
		}
		
		@Override
		public boolean hasNext() {
			return currentValue != 1;
		}
		@Override
		public int nextInt() {
			currentValue = comingValue;
			comingValue = evenOddFunc[comingValue %2].applyAsInt(comingValue);
			return currentValue;
		}
	};
	
	public static IntStream downToOneStream(int seed) {
		return StreamSupport.intStream (
					Spliterators.spliteratorUnknownSize(
						new DownToOneIterator(seed),
						Spliterator.ORDERED | Spliterator.IMMUTABLE | Spliterator.NONNULL
					), 
					false
				);
	}

	public static LongStream countsOfRange(int start, int end) {
		return IntStream.rangeClosed(start, end).parallel()
							.mapToLong(n -> downToOneStream(n).count());
	}
	
	public static long maxInRange(int i, int j) {
		int start = Integer.min(i, j);
		int end = Integer.max(i, j);		
		LongStream countStream = countsOfRange(start, end);
		return countStream.max().getAsLong();
	}
	
	public static void main(String[] args) {
		try (Scanner sc = new Scanner(System.in)) {
			while (sc.hasNext()) {
				int i = sc.nextInt();
				int j = sc.nextInt();
				long max = maxInRange(i, j);
				System.out.printf("%d %d %d\n", i, j, max);
			}
		}
	}
}

ThreedNPlusOneTest.java

package issue1;

import static org.fest.assertions.api.Assertions.*;

import java.io.IOException;
import java.io.InputStream;

import org.apache.commons.io.IOUtils;
import org.fest.util.Arrays;
import org.junit.Rule;
import org.junit.Test;
import org.springframework.boot.test.OutputCapture;

public class ThreeNPlusOneIntegrationTest {
	@Rule
	public OutputCapture stdout = new OutputCapture();
	
	@Test
	public void testSampleCases() throws IOException{
		assertStdout("/issue1/input.txt", "/issue1/output.txt");
	}

	private void assertStdout(String input, String output) throws IOException {
		// given
		System.setIn(readFromClasspath(input));
		// when
		ThreeNPlusOne.main(Arrays.array());
		// then
		String expected = IOUtils.toString(readFromClasspath(output));
		assertThat(stdout.toString()).isEqualTo(expected);
	}

	private InputStream readFromClasspath(String output) {
		return ThreeNPlusOneIntegrationTest.class.getResourceAsStream(output);
	}
}

ThreeNPlusOneIntegrationTest.java

package issue1;

import static org.fest.assertions.api.Assertions.*;

import java.io.IOException;
import java.io.InputStream;

import org.apache.commons.io.IOUtils;
import org.fest.util.Arrays;
import org.junit.Rule;
import org.junit.Test;
import org.springframework.boot.test.OutputCapture;

public class ThreeNPlugOneIntegrationTest {
	@Rule
	public OutputCapture stdout = new OutputCapture();
	
	@Test
	public void testSampleCases() throws IOException{
		assertStdout("/issue1/input.txt", "/issue1/output.txt");
	}

	private void assertStdout(String input, String output) throws IOException {
		// given
		System.setIn(readFromClasspath(input));
		// when
		ThreedNPlusOne.main(Arrays.array());
		// then
		String expected = IOUtils.toString(readFromClasspath(output));
		assertThat(stdout.toString()).isEqualTo(expected);
	}

	private InputStream readFromClasspath(String output) {
		return ThreeNPlugOneIntegrationTest.class.getResourceAsStream(output);
	}
}