mborm.net

Problem 27 auf projecteuler.netHier meine Lösung zu Problem 27 auf projecteuler.net in der Programmiersprache Java.
Bei der Lösung habe ich auf brute force gesetzt. Trotzdem berechnet sich das Ergebnis recht schnell:


Result: -59231

real    0m0.316s

user    0m0.325s

sys     0m0.008s

Java
package net.mborm.euler.problems;

public class Problem27 {
    private static boolean is_prime(int n) {
        if(n == 1)
            return false;

        if(n == 2)
            return true;

        int r = (int) Math.floor(Math.sqrt(n));
        int i;

        for(i = 2; i <= r; ++i)
            if(n % i == 0)
                break;

        return (r == i - 1);
    }

    public static void main(String[] args) {
        int[] sequence = new int[2];
        int result = 0;

        for(int a = -1000; a <= 1000; a++) {
            for(int b = -1000; b <= 1000; b++) {
                int n = 0;

                while(is_prime(Math.abs(n * n + a * n + b)))
                    n++;

                if(n > result) {
                    result = n;
                    sequence[0] = a;
                    sequence[1] = b;
                }
            }
        }

        System.out.println("Result: "+sequence[0] * sequence[1]);

    }
}

				
					
				1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

						package net.mborm.euler.problems;
 
public class Problem27 {
    private static boolean is_prime(int n) {
        if(n == 1)
            return false;
 
        if(n == 2)
            return true;
 
        int r = (int) Math.floor(Math.sqrt(n));
        int i;
 
        for(i = 2; i <= r; ++i)
            if(n % i == 0)
                break;
 
        return (r == i - 1);
    }
 
    public static void main(String[] args) {
        int[] sequence = new int[2];
        int result = 0;
 
        for(int a = -1000; a <= 1000; a++) {
            for(int b = -1000; b <= 1000; b++) {
                int n = 0;
 
                while(is_prime(Math.abs(n * n + a * n + b)))
                    n++;
 
                if(n > result) {
                    result = n;
                    sequence[0] = a;
                    sequence[1] = b;
                }
            }
        }
 
        System.out.println("Result: "+sequence[0] * sequence[1]);
 
    }
}

					

			
 
Veröffentlicht am 30. April 2015 von admin in Java, Programmierung, projecteuler
Problem 11 auf projecteuler.netDie Lösung zu Problem 11 habe ich ebenfalls in PHP umgesetzt.
Meiner Meinung nach war das Schwierigste an der Aufgabe sich in verschiedene Richtungen im Array zu bewegen. Wenn das klappt, berechnet sich die Lösung allerdings sehr schnell:


Result: 70600674

real	0m0.012s

user	0m0.008s

sys	0m0.004s

PHP
<?php

$p = 0;

$grid = "08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08 
49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00 
81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65 
52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91 
22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80 
24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50 
32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70 
67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21 
24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72 
21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95 
78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92 
16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57 
86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58 
19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40 
04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66 
88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69 
04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36 
20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16 
20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54 
01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48 ";


$grid = preg_replace('/0(\d)/', " $1", $grid);
$grid = explode("\n", $grid);

for ($i = 0; $i < count($grid); $i++)
  $grid[$i] = preg_split('/[ ]+/', trim($grid[$i]));

for($n = 0; $n <= 19; $n++) {
    for($k = 0; $k <= 16; $k++) {
        $p = max($p, $grid[$n][$k+0] * $grid[$n][$k+1] * $grid[$n][$k+2] * $grid[$n][$k+3]);
        $p = max($p, $grid[$k+0][$n] * $grid[$k+1][$n] * $grid[$k+2][$n] * $grid[$k+3][$n]);
    }
}

for($n = 0; $n <= 16; $n++) {
    for($k = 0; $k <= 16; $k++) {
        $p = max($p, $grid[$n+0][$k+0] * $grid[$n+1][$k+1] * $grid[$n+2][$k+2] * $grid[$n+3][$k+3]);
        $p = max($p, $grid[$n+0][$k+3] * $grid[$n+1][$k+2] * $grid[$n+2][$k+1] * $grid[$n+3][$k+0]);
    }
}

echo "Result: ".$p."\n";

?>

				
					
				1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

						<?php
 
$p = 0;
 
$grid = "08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08 
49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00 
81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65 
52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91 
22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80 
24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50 
32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70 
67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21 
24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72 
21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95 
78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92 
16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57 
86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58 
19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40 
04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66 
88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69 
04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36 
20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16 
20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54 
01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48 ";
 
 
$grid = preg_replace('/0(\d)/', " $1", $grid);
$grid = explode("\n", $grid);
 
for ($i = 0; $i < count($grid); $i++)
  $grid[$i] = preg_split('/[ ]+/', trim($grid[$i]));
 
for($n = 0; $n <= 19; $n++) {
    for($k = 0; $k <= 16; $k++) {
        $p = max($p, $grid[$n][$k+0] * $grid[$n][$k+1] * $grid[$n][$k+2] * $grid[$n][$k+3]);
        $p = max($p, $grid[$k+0][$n] * $grid[$k+1][$n] * $grid[$k+2][$n] * $grid[$k+3][$n]);
    }
}
 
for($n = 0; $n <= 16; $n++) {
    for($k = 0; $k <= 16; $k++) {
        $p = max($p, $grid[$n+0][$k+0] * $grid[$n+1][$k+1] * $grid[$n+2][$k+2] * $grid[$n+3][$k+3]);
        $p = max($p, $grid[$n+0][$k+3] * $grid[$n+1][$k+2] * $grid[$n+2][$k+1] * $grid[$n+3][$k+0]);
    }
}
 
echo "Result: ".$p."\n";
 
?>

					

			
 
Veröffentlicht am 28. April 2015 von admin in PHP, Programmierung, projecteuler
Problem 36 auf projecteuler.netHier meine Lösung zu Problem 36 auf projecteuler.net
Die Lösung für dieses Problem ließ sich extrem einfach in PHP bauen – und das Ganze läuft innerhalb von ~ 1 Sekunde:


872187

real	0m1.049s

user	0m1.048s

sys	0m0.000s

PHP
<?php

$result = 0;

for($i = 0; $i <= 1000000; $i++)
    if(decbin($i) == strrev(decbin($i)) && $i == strrev($i))
        $result += $i;

print $result;

?>

				
					
				1
2
3
4
5
6
7
8
9
10
11

						<?php
 
$result = 0;
 
for($i = 0; $i <= 1000000; $i++)
    if(decbin($i) == strrev(decbin($i)) && $i == strrev($i))
        $result += $i;
 
print $result;
 
?>

					

			
 
Veröffentlicht am 28. April 2015 von admin in PHP, Programmierung, projecteuler
Problem 96 auf projecteuler.netHier meine Lösung zu Problem 96 auf projecteuler.net.
Für die Lösung des Problems habe ich das Perl-Module „Games::Sudoku::Solver“ benutzt, welches hier heruntergeladen werden kann.
Die schnellste Lösung ist es nicht, aber immerhin löst sie das Problem:


Result: 24702 !

real    0m9.220s

user    0m9.214s

sys     0m0.000s

So schaut die Lösung aus:
Perl
#!/usr/bin/env perl

use strict;
use warnings;
use Games::Sudoku::Solver qw(:Minimal set_solution_max);

my $fh;
my $sudokus = {};
my $current_idx;
my $solution;

open $fh, "sudoku.txt" or die($!);

while(my $line = <$fh>) {
    chomp($line);
    if($line =~ m/^Grid (\d+)/) {
        $current_idx = $1;
        $sudokus->{$current_idx} = [];
        next;
    }
    push $sudokus->{$current_idx}, split '', $line;
}

print "Calculate ...\n";

foreach my $idx (keys $sudokus) {
    my @temp;
    my @result;

    sudoku_set \@temp, \@{$sudokus->{$idx}};
    set_solution_max 1;
    sudoku_solve \@temp, \@result;

    $solution += 100 * $result[0][0][0] + 10 * $result[0][0][1] + $result[0][0][2];
}

print "Result: $solution !\n";

				
					
				1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

						#!/usr/bin/env perl
 
use strict;
use warnings;
use Games::Sudoku::Solver qw(:Minimal set_solution_max);
 
my $fh;
my $sudokus = {};
my $current_idx;
my $solution;
 
open $fh, "sudoku.txt" or die($!);
 
while(my $line = <$fh>) {
    chomp($line);
    if($line =~ m/^Grid (\d+)/) {
        $current_idx = $1;
        $sudokus->{$current_idx} = [];
        next;
    }
    push $sudokus->{$current_idx}, split '', $line;
}
 
print "Calculate ...\n";
 
foreach my $idx (keys $sudokus) {
    my @temp;
    my @result;
 
    sudoku_set \@temp, \@{$sudokus->{$idx}};
    set_solution_max 1;
    sudoku_solve \@temp, \@result;
 
    $solution += 100 * $result[0][0][0] + 10 * $result[0][0][1] + $result[0][0][2];
}
 
print "Result: $solution !\n";

					

			
 
Veröffentlicht am 19. April 2015 von admin in Perl, Programmierung, projecteuler
Problem 29 auf projecteuler.netDie Lösung zu Problem 29 war extrem einfach.
Diese Lösung habe ich in der Skriptsprache Perl erstellt – die Rechengeschwindigkeit ist da allerdings etwas niedriger aber auch nicht schlecht:


real	0m1.817s

user	0m1.812s

sys	0m0.004s

Hier der Code:
Perl
#!/usr/bin/env perl

use strict;
use warnings;

my @nums = ();

foreach my $a (2..100) {
    foreach my $b (2..100) {
        my $num = $a ** $b;
        push @nums, $num if !grep {$num == $_} @nums;
    }
}

print "Result: ", scalar @nums, "\n";

				
					
				1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

						#!/usr/bin/env perl
 
use strict;
use warnings;
 
my @nums = ();
 
foreach my $a (2..100) {
    foreach my $b (2..100) {
        my $num = $a ** $b;
        push @nums, $num if !grep {$num == $_} @nums;
    }
}
 
print "Result: ", scalar @nums, "\n";

					

			
 
Veröffentlicht am 14. April 2015 von admin in Perl, Programmierung, projecteuler
Problem 92 auf projecteuler.netHier ist meine Lösung zu Problem 92 auf projecteuler.net. Die Lösung ist mittels der Programmiersprache C umgesetzt und kann mittels des gcc mit diesem Befehl kompiliert werden:


gcc -O3 -Wall Problem92.c -lm -o Problem92

Auf meinem Rechner braucht das Skript nur eine sehr kurze Zeit zum Berechnen:



real	0m0.639s

user	0m0.638s

sys	0m0.000s

Der Code schaut so aus:
C
#include <stdio.h>

typedef unsigned int uint;

__inline static uint square(uint x) {
    return x * x;
}

__inline static uint solve(uint num) {
    register uint res = 0, val = num;

    while(val > 0) {
        res += square(val % 10);
        val /= 10;
    }

    return res;
}

int main() {
    typedef enum { false, true } bool;
    uint result = 0, i = 0, tmp = 0;

    for(i = 10000000; i != 0; i--) {
        tmp = solve(i);
        bool run = true;

        while(run) {
            switch(tmp) {
                case 1: run = false; break;
                case 89: result++; run = false; break;
                default: tmp = solve(tmp);
            }
        }
    }
    printf("Result: %i", result);
    return 0;
}

				
					
				1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

						#include <stdio.h>
 
typedef unsigned int uint;
 
__inline static uint square(uint x) {
    return x * x;
}
 
__inline static uint solve(uint num) {
    register uint res = 0, val = num;
 
    while(val > 0) {
        res += square(val % 10);
        val /= 10;
    }
 
    return res;
}
 
int main() {
    typedef enum { false, true } bool;
    uint result = 0, i = 0, tmp = 0;
 
    for(i = 10000000; i != 0; i--) {
        tmp = solve(i);
        bool run = true;
 
        while(run) {
            switch(tmp) {
                case 1: run = false; break;
                case 89: result++; run = false; break;
                default: tmp = solve(tmp);
            }
        }
    }
    printf("Result: %i", result);
    return 0;
}

					

			
 
Veröffentlicht am 14. April 2015 von admin in C, Programmierung, projecteuler

		Neueste Beiträge
		
					apache2 TLS-Config für Qualys Lab Bestnote mit Server Hardening
									

					TEDP – The Energy Data Project
									

					GPU Benchmark integriert
									

					Neue Benchmark Version
									

					Eigene API für die luftdaten.info Wetterstation
									


		
KategorienAllgemein
Bash
C
Hardware
IT-Sicherheit
Java
Netzwerk
Perl
PHP
Programmierung
projecteuler
Python
Server
ArchivJanuar 2021
November 2020
Oktober 2019
September 2019
März 2019
Juli 2018
Juni 2018
August 2017
Mai 2016
Dezember 2015
Oktober 2015
August 2015
Juli 2015
Juni 2015
Mai 2015
April 2015
mborm.net

Ein Computerprogramm tut was Du schreibst, nicht was Du willst.

Problem 27 auf projecteuler.net

Problem 11 auf projecteuler.net

Problem 36 auf projecteuler.net

Problem 96 auf projecteuler.net

Problem 29 auf projecteuler.net

Problem 92 auf projecteuler.net

Neueste Beiträge

Kategorien

Archiv
