LoginSignup
1

More than 5 years have passed since last update.

くねくねstream

Posted at

今更感たっぷりなうえに、途中から趣旨違ってきた・・・
けどせっかく書いたので晒そう。

問題

感想

長いので先に。

  • 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);
        }
    }
}

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
1