commit 3f820224c03a92d3675e43d11da5772304b8977c
parent 5c07fe3d134bd5082ca0268c4abf1f26fe87cf69
Author: mpizzzle <michael.770211@gmail.com>
Date: Mon, 27 Jun 2016 00:54:49 +0100
Euler 81 Complete. done in Go!
Diffstat:
| A | Euler_81.go | | | 78 | ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | Makefile | | | 46 | ++++++++++++++++++++++++++++++++++++++++++++++ |
| M | main.cpp | | | 9 | ++++----- |
3 files changed, 128 insertions(+), 5 deletions(-)
diff --git a/Euler_81.go b/Euler_81.go
@@ -0,0 +1,78 @@
+package main
+
+import (
+ "fmt"
+ "io/ioutil"
+ "strings"
+ "strconv"
+)
+
+type Node struct {
+ cost int
+ distance int
+ included bool
+}
+
+func dijkstra(matrix [][]Node) int {
+ for count := 0; count < (80 * 80) - 1; count++ {
+ min := 1<<31 - 1
+ var min_x int
+ var min_y int
+
+ for x := 0; x < 80; x++ {
+ for y := 0; y < 80; y++ {
+ if matrix[x][y].included == false && matrix[x][y].distance <= min {
+ min = matrix[x][y].distance
+ min_x = x
+ min_y = y
+ }
+ }
+ }
+
+ matrix[min_x][min_y].included = true
+
+ for x := 0; x < 80; x++ {
+ for y := 0; y < 80; y++ {
+ if x + 1 < 80 {
+ if (!matrix[x + 1][y].included) && matrix[x][y].distance != 1<<31 - 1 && matrix[x][y].distance + matrix[x + 1][y].cost < matrix[x + 1][y].distance {
+ matrix[x + 1][y].distance = matrix[x][y].distance + matrix[x + 1][y].cost
+ }
+ }
+
+
+ if y + 1 < 80 {
+ if (!matrix[x][y + 1].included) && matrix[x][y].distance != 1<<31 - 1 && matrix[x][y].distance + matrix[x][y + 1].cost < matrix[x][y + 1].distance {
+ matrix[x][y + 1].distance = matrix[x][y].distance + matrix[x][y + 1].cost
+ }
+ }
+ }
+ }
+ }
+
+ return matrix[79][79].distance
+}
+
+func main() {
+ dat, _ := ioutil.ReadFile("matrix.txt")
+
+ var matrix [][]Node
+
+ for _, r := range strings.Split(string(dat), "\n") {
+ var int_row []Node
+
+ for _, r2 := range strings.Split(r, ",") {
+ var n Node
+ cost, _ := strconv.Atoi(r2)
+ n.cost = cost
+ n.distance = 1<<31 - 1
+ n.included = false
+ int_row = append(int_row, n)
+ }
+
+ matrix = append(matrix, int_row)
+ }
+
+ matrix[0][0].distance = matrix[0][0].cost
+ fmt.Println(dijkstra(matrix))
+ fmt.Println(len(matrix))
+}
diff --git a/Makefile b/Makefile
@@ -0,0 +1,46 @@
+# Mention default target.
+all:
+
+%.o: %.cpp
+ clang++ -O2 -Wall -Wextra -pedantic -std=c++11 $<
+
+program =euler
+
+euler-objects = \
+ main.o \
+ EulerUtility.o \
+ Euler_15.o \
+
+euler-headers = \
+ EulerUtility.h \
+ Euler.h \
+
+bigint-objects = \
+ BigUnsigned.o \
+ BigInteger.o \
+ BigIntegerAlgorithms.o \
+ BigUnsignedInABase.o \
+ BigIntegerUtils.o \
+
+bigint-headers = \
+ NumberlikeArray.hh \
+ BigUnsigned.hh \
+ BigInteger.hh \
+ BigIntegerAlgorithms.hh \
+ BigUnsignedInABase.hh \
+ BigIntegerLibrary.hh \
+
+bigint: $(bigint-objects)
+
+$(bigint-objects): $(bigint-headers)
+
+$(euler-objects): $(euler-headers) $(bigint-headers)
+
+$(program) : $(euler-objects) $(bigint-objects)
+ g++ $^ -o $@
+
+clean :
+ rm -f $(bigint-objects) $(program-objects) $(program)
+
+all:
+ make $(program)
diff --git a/main.cpp b/main.cpp
@@ -3,7 +3,7 @@
#include "Euler.h"
-void main() {
+int main() {
Euler e;
std::clock_t start = std::clock();
@@ -21,7 +21,7 @@ void main() {
//std::cout << e.TriangleNoWithGreaterThan500Divisors() << std::endl;
//std::cout << e.LargeSum() << std::endl;
//std::cout << e.CollatzConjecture() << std::endl;
- //std::cout << e.LatticePaths() << std::endl;
+ std::cout << e.LatticePaths() << std::endl;
//std::cout << e.DigitSum() << std::endl;
//std::cout << e.LetterCounter() << std::endl;
//std::cout << e.MaximumPathSum() << std::endl;
@@ -85,9 +85,9 @@ void main() {
//std::cout << e.PrimeSummations() << std::endl;
//std::cout << e.CoinPartitions() << std::endl;
//std::cout << e.PasscodeDerivation() << std::endl;
- std::cout << e.SquareRootDigitalExpansion() << std::endl;
+ //std::cout << e.SquareRootDigitalExpansion() << std::endl;
std::cout << "duration: " << std::clock() - start << "ms" << std::endl;
std::cin.get();
-}-
\ No newline at end of file
+}
