LINQ - najdłuższy podciąg spełniający warunki

Odpowiedz Nowy wątek
2019-05-14 12:09
0

Na tegorocznej maturce było takie zadanko:

W pliku liczby.txt znajdź najdłuższy ciąg liczb występujących kolejno po sobie i taki, że największy wspólny dzielnik ich wszystkich jest większy od 1 (innymi słowy: istnieje taka liczba całkowita większa od 1, która jest dzielnikiem każdej z tych liczb). Jako odpowiedź podaj wartość pierwszej liczby w takim ciągu, długość ciągu oraz największą liczbę całkowitą, która jest dzielnikiem każdej liczby w tym ciągu. W pliku z danymi jest tylko jeden taki ciąg o największej długości.

Dałoby się to zrobić w sposób funkcyjny przy użyciu LINQ? Dane są tu: https://www.cke.gov.pl/

Pozostało 580 znaków

2019-05-14 18:48

Pewnie istnieją rozwiązania bardziej eleganckie od mojego. Funkcja GetGcd zwraca największy wspólny dzielnik (greatest common divisor) i powinna działać iteracyjnie, a nie rekurencyjnie, żeby uniknąć przepełnienia stosu. Kolekcja input jest typu IEnumerable<int> lub pochodnego od niego. Wynikiem jest obiekt, który ma właściwości Start, Count i Gcd typu int.

var result = input.Select((x, i) => input.Skip(i).TakeWhile((y, j) => input.Skip(i).Take(j + 1).Aggregate((a, b) => GetGcd(a, b)) > 1))
    .Where(x => x.Count() > 1)
    .Select(x => new
    {
        Start = x.ElementAt(0),
        Count = x.Count(),
        Gcd = x.Aggregate((a, b) => GetGcd(a, b))
    })
    .Where(x => x.Gcd > 1)
    .OrderByDescending(x => x.Count)
    .First();
}
edytowany 2x, ostatnio: Burmistrz, 2019-05-14 18:55

Pozostało 580 znaków

2019-05-15 00:20
2

Takie proste zadania na tej maturze? widać, że system edukacji w Polsce to porażka.

Takie zadania rozwiązuje się 1 linq chainem, no ale aby nie być gołosłownym to wrzucam rozwiązanie:

trochę długo liczy, bo było to optymalizowane pod 100rdzeniowe procesory

Wynik:

150
31968
74

private static bool Predicate(int? a, int? b)
{
    while (a != 0 && b != 0)
    {
        if (a > b)
            a %= b;
        else
            b %= a;
    }

    return (a == 0 ? b : a) != 1;
}

public static void Main(string[] Args)
{
    var path = @"C:\liczby.txt";

    var numbers = File
        .ReadAllLines(path)
        .Select(x => (int?)Convert.ToInt32(x))
        .ToList();

    var _ =
        Enumerable
        .Range
        (0,
            numbers
            .Select
            (
                (z, i) =>
                (i == numbers.Count() - 1) ?
                z :
                Predicate(z, numbers[i + 1]) ?
                z :
                null
            )
            .Select((z, i) => new { z, i = i + 1 })
            .Where(z => z.z.HasValue)
            .Select(z => z.i)
            .ToList()
            .Select((x, i) => new { x, i })
            .Where(x => x.i < numbers
            .Select
            (
                (z, i) =>
                (i == numbers.Count() - 1) ?
                z :
                Predicate(z, numbers[i + 1]) ?
                z :
                null
            )
            .Select((z, i) => new { z, i = i + 1 })
            .Where(z => z.z.HasValue)
            .Select(z => z.i)
            .ToList().Count() - 1 && numbers
            .Select
            (
                (z, i) =>
                (i == numbers.Count() - 1) ?
                z :
                Predicate(z, numbers[i + 1]) ?
                z :
                null
            )
            .Select((z, i) => new { z, i = i + 1 })
            .Where(z => z.z.HasValue)
            .Select(z => z.i)
            .ToList()[x.i] + 1 != numbers
            .Select
            (
                (z, i) =>
                (i == numbers.Count() - 1) ?
                z :
                Predicate(z, numbers[i + 1]) ?
                z :
                null
            )
            .Select((z, i) => new { z, i = i + 1 })
            .Where(z => z.z.HasValue)
            .Select(z => z.i)
            .ToList()[x.i + 1])
        .Select(x => x.i)
        .Count()
        )
        .Select
        (
            x =>
            new
            {
                ctr = x,
                val = numbers
                .Select
                (
                    (z, i) =>
                    (i == numbers.Count() - 1) ?
                    z :
                    Predicate(z, numbers[i + 1]) ?
                    z :
                    null
                )
                .Select((z, i) => new { z, i = i + 1 })
                .Where(z => z.z.HasValue)
                .Select(z => z.i)
                .ToList()
                .Select((a, i) => new { x, i })
                .Where(a => a.i < 
                numbers
                .Select
                (
                    (z, i) =>
                    (i == numbers.Count() - 1) ?
                        z :
                    Predicate(z, numbers[i + 1]) ?
                    z :
                    null
                )
                .Select((z, i) => new { z, i = i + 1 })
                .Where(z => z.z.HasValue)
                .Select(z => z.i)
                .ToList().Count() - 1

                &&

                numbers
                .Select
                (
                    (z, i) =>
                    (i == numbers.Count() - 1) ?
                    z :
                    Predicate(z, numbers[i + 1]) ?
                    z :
                    null
                )
                .Select((z, i) => new { z, i = i + 1 })
                .Where(z => z.z.HasValue)
                .Select(z => z.i)
                .ToList()
                [a.i] + 1 !=
                numbers
                .Select
                (
                    (z, i) =>
                    (i == numbers.Count() - 1) ?
                    z :
                    Predicate(z, numbers[i + 1]) ?
                    z :
                    null
                )
                .Select((z, i) => new { z, i = i + 1 })
                .Where(z => z.z.HasValue)
                .Select(z => z.i)
                .ToList()[a.i + 1])
                .Select(a => a.i)
                .ToList()[x],

                prev = numbers
                .Select
                (
                    (z, i) =>
                    (i == numbers.Count() - 1) ?
                    z :
                    Predicate(z, numbers[i + 1]) ?
                    z :
                    null
                )
                .Select((z, i) => new { z, i = i + 1 })
                .Where(z => z.z.HasValue)
                .Select(z => z.i)
                .ToList()
                .Select((a, i) => new { x, i })
                .Where(a => a.i < numbers
                .Select
                (
                    (z, i) =>
                    (i == numbers.Count() - 1) ?
                    z :
                    Predicate(z, numbers[i + 1]) ?
                    z :
                    null
                )
                .Select((z, i) => new { z, i = i + 1 })
                .Where(z => z.z.HasValue)
                .Select(z => z.i)
                .ToList().Count() - 1 && numbers
                .Select
                (
                    (z, i) =>
                    (i == numbers.Count() - 1) ?
                    z :
                    Predicate(z, numbers[i + 1]) ?
                    z :
                    null
                )
                .Select((z, i) => new { z, i = i + 1 })
                .Where(z => z.z.HasValue)
                .Select(z => z.i)
                .ToList()[a.i] + 1 != numbers
                .Select
                (
                    (z, i) =>
                    (i == numbers.Count() - 1) ?
                    z :
                    Predicate(z, numbers[i + 1]) ?
                    z :
                    null
                )
                .Select((z, i) => new { z, i = i + 1 })
                .Where(z => z.z.HasValue)
                .Select(z => z.i)
                .ToList()[a.i + 1])
                .Select(a => a.i)
                .ToList()
                .ElementAtOrDefault(x - 1)
            }
        )
        .Select
        (
            x =>
            new List<int>
            (
                numbers
                .Select
                (
                    (z, i) =>
                    (i == numbers.Count() - 1) ?
                    z :
                    Predicate(z, numbers[i + 1]) ?
                    z :
                    null
                )
                .Select((z, i) => new { z, i = i + 1 })
                .Where(z => z.z.HasValue)
                .Select(z => z.i)
                .Where((c, i) => x.ctr == 0 ? i <= x.val : i <= x.val && i > x.prev).
                ToList()
            )
        )
        .OrderByDescending(x => x.Count)
        .First();

    Console.WriteLine(_.Count);
    Console.WriteLine(numbers[_.First()]);
    Console.WriteLine(_.Select(x => numbers[x]).Min());
}

:D

edytowany 8x, ostatnio: WeiXiao, 2019-05-15 00:41
Mam nadzieję, że na maturze nie trzeba programować na kartce i można użyć komputer - Burmistrz 2019-05-15 07:25
Powodzenia z debugowaniem ;-) - Deltech 2019-05-15 09:48

Pozostało 580 znaków

2019-05-15 08:48
1

Na początku myślałem, ze kto napisze najdłuższe wyrażenie w LINQ..... wchodzę w wątek, nie zawiodłem się :D :X

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0