今更感たっぷりなうえに、途中から趣旨違ってきた・・・
けどせっかく書いたので晒そう。
問題
感想
長いので先に。
- Stream API 使ってたら楽しくなってきたので、for 文禁止でやってみた。
-
.stream()
って書くの飽きそう。Collection → Stream の変換くらいは自動でやって欲しい - flatMap 地味に導入しづらい
- これ後からメンテとか無理そう
-
- 総当りにならないように経路末尾の候補を事前に抽出したけど、結局メモ化とかできてないからオーダーは・・・orz
回答
Kunekune.java
package heignamerican;
import static org.hamcrest.CoreMatchers.*;
import static org.junit.Assert.*;
import java.util.Arrays;
import java.util.List;
import java.util.Map.Entry;
import java.util.function.Function;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
import java.util.stream.Stream;
import org.junit.Test;
public class Kunekune {
@Test
public void testAll() {
/*0*/test("01224/82925/69076/32298/21065", "6");
/*1*/test("03478/12569/03478/12569/03478", "10");
/*2*/test("09900/28127/87036/76545/87650", "10");
/*3*/test("77777/77777/77777/77777/77777", "1");
/*4*/test("00000/11111/22222/33333/44444", "5");
/*5*/test("01234/12345/23456/34567/45678", "9");
/*6*/test("10135/21245/43456/55567/77789", "8");
/*7*/test("33333/33333/55555/55555/77777", "2");
/*8*/test("01234/11234/22234/33334/44444", "5");
/*9*/test("98765/88765/77765/66665/55555", "5");
/*10*/test("01234/10325/23016/32107/45670", "8");
/*11*/test("34343/43434/34343/43434/34343", "2");
/*12*/test("14714/41177/71141/17414/47141", "3");
/*13*/test("13891/31983/89138/98319/13891", "4");
/*14*/test("01369/36901/90136/13690/69013", "5");
/*15*/test("02468/24689/46898/68986/89864", "6");
/*16*/test("86420/68642/46864/24686/02468", "5");
/*17*/test("77777/75557/75357/75557/77777", "3");
/*18*/test("53135/33133/11111/33133/53135", "3");
/*19*/test("01356/23501/45024/61246/13461", "5");
/*20*/test("46803/68025/91358/34792/78136", "4");
/*21*/test("66788/56789/55799/43210/33211", "9");
/*22*/test("40000/94321/96433/97644/98654", "9");
/*23*/test("58950/01769/24524/24779/17069", "6");
/*24*/test("97691/01883/98736/51934/81403", "4");
/*25*/test("92049/27798/69377/45936/80277", "5");
/*26*/test("97308/77113/08645/62578/44774", "5");
/*27*/test("90207/17984/01982/31272/60926", "6");
/*28*/test("62770/65146/06512/15407/89570", "4");
/*29*/test("93914/46889/27554/58581/18703", "5");
/*30*/test("42035/12430/60728/30842/90381", "5");
/*31*/test("90347/53880/67954/95256/68777", "6");
/*32*/test("05986/60473/01606/16425/46292", "5");
/*33*/test("18053/90486/24320/04250/03853", "5");
/*34*/test("36865/13263/67280/18600/12774", "5");
/*35*/test("72456/72052/79971/14656/41151", "5");
/*36*/test("94888/28649/05561/76571/97567", "5");
/*37*/test("50214/94693/88718/78922/55359", "5");
/*38*/test("76502/99325/17987/31737/93874", "7");
/*39*/test("87142/14764/13014/00248/73105", "6");
/*40*/test("24573/71679/48704/19786/91834", "7");
/*41*/test("20347/61889/06074/61263/20519", "7");
/*42*/test("74344/97459/97302/14439/35689", "6");
/*43*/test("04794/52198/50294/09340/24160", "5");
/*44*/test("41065/69344/64698/54167/43348", "7");
/*45*/test("39947/15696/03482/19574/70235", "7");
/*46*/test("92767/16790/84897/69765/75734", "7");
/*47*/test("09654/79610/05070/23456/74687", "8");
/*48*/test("73998/98799/98707/05633/23915", "8");
/*49*/test("35661/17480/89723/64335/27217", "7");
/*50*/test("02489/77571/84873/03879/84460", "7");
}
private void test(String input, String expected) {
assertThat(Program.solve(input).getKey(), is(Integer.parseInt(expected, 10)));
}
public static Entry<Integer, List<List<Pos>>> solve(final String input) {
final List<List<Integer>> table = Arrays.asList(input.split("/")).stream()
.map(line -> line.chars()
.map(c -> c - '0')
.boxed()
.collect(Collectors.toList())
)
.collect(Collectors.toList());
final int rowSize = table.size();
final int colSize = table.get(0).size();
final Function<Pos, Integer> toCell = (final Pos pos) -> table.get(pos.row).get(pos.col);
final Function<? super Pos, Stream<Pos>> toArround = pos -> Stream.of(
new Pos(pos.col, pos.row - 1),
new Pos(pos.col - 1, pos.row),
new Pos(pos.col + 1, pos.row),
new Pos(pos.col, pos.row + 1)
)
.filter(x -> (0 <= x.row && x.row < rowSize && 0 <= x.col && x.col < colSize));
final Function<List<List<Pos>>, List<List<Pos>>> search = new Function<List<List<Pos>>, List<List<Pos>>>() {
@Override
public List<List<Pos>> apply(final List<List<Pos>> paths) { //末尾からの探索
final List<List<Pos>> nexts = paths.stream()
.flatMap(path -> (Stream<List<Pos>>) toArround.apply(path.get(0))
.filter(x -> toCell.apply(x) < toCell.apply(path.get(0)))
.map(x -> Stream.concat(Stream.of(x), path.stream()).collect(Collectors.toList()))
).collect(Collectors.toList());
return nexts.size() == 0 ? paths : apply(nexts);
}
};
return IntStream.range(0, rowSize).boxed()
.flatMap(row -> IntStream.range(0, colSize).boxed()
.map((Function<Integer, Pos>) col -> new Pos(col, row))
) // 全座標
.filter(pos -> toArround.apply(pos)
.noneMatch(neighbor -> toCell.apply(pos) < toCell.apply(neighbor))
) // 末尾候補
.map(tail -> Arrays.asList(Arrays.asList(tail)))
.map(search) //末尾からの探索
.flatMap(x -> x.stream()) // flatten
.collect(Collectors.groupingBy(keiro -> keiro.size())) // 経路長でグループ化
.entrySet().stream().sorted((x, y) -> y.getKey() - x.getKey()).findFirst().get() // 経路最長のみ
;
}
public static class Pos {
public final int row;
public final int col;
public Pos(final int col, final int row) {
this.row = row;
this.col = col;
}
@Override
public String toString() {
return String.format("(%d,%d)", col, row);
}
}
}