Last active
April 13, 2016 10:16
-
-
Save jmeirow/62dcfce4229f8c548ad034dfba7191cf to your computer and use it in GitHub Desktop.
Project 11 - Greatest Product
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
using System; | |
using System.Collections.Generic; | |
using System.Linq; | |
using System.Text; | |
namespace Project11 | |
{ | |
public class Point | |
{ | |
public int x; | |
public int y; | |
public override string ToString() | |
{ | |
return string.Format("({0},{1})", y, x); | |
} | |
} | |
// A sequence of four Points | |
public class Segment : List<Point> | |
{ | |
public override string ToString() | |
{ | |
StringBuilder sb = new StringBuilder(); | |
foreach (Point pt in this) | |
{ | |
sb.Append(pt.ToString()); | |
sb.Append(" "); | |
} | |
return sb.ToString(); | |
} | |
public string ShowGridValues(int[,] grid) | |
{ | |
StringBuilder sb = new StringBuilder(); | |
sb.Append("[ "); | |
foreach (Point pt in this) | |
{ | |
sb.Append(grid[pt.x, pt.y]); | |
sb.Append(" "); | |
} | |
sb.Append(" ]"); | |
return sb.ToString(); | |
} | |
} | |
// This is where the work gets done. | |
public class Program | |
{ | |
int[,] grid = new int[,] | |
{{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}}; | |
List<Point> points = new List<Point>(); | |
Dictionary<string, List<Segment>> segments = new Dictionary<string, List<Segment>>(); | |
private Segment topSegment = new Segment(); | |
private int topProduct = 0; | |
private int computations = 0; | |
static void Main(string[] args) | |
{ | |
new Program().Run(); | |
} | |
public void Run() | |
{ | |
DateTime start = DateTime.Now; | |
ComputePoints(); | |
foreach (Point pt in points) | |
{ | |
ComputeSegments(pt); | |
} | |
foreach (Point pt in points) | |
{ | |
foreach (Segment seg in segments[pt.ToString()]) | |
{ | |
int product = ComputeProduct(seg, grid); | |
if (product > topProduct) | |
{ | |
topProduct = product; | |
topSegment = seg; | |
} | |
} | |
} | |
DateTime end = DateTime.Now; | |
Console.WriteLine("Segment {0} - {1} has total of {2}", topSegment, topSegment.ShowGridValues(grid), topProduct); | |
Console.WriteLine("Performed {0} computations in {1} milliseconds.", computations, end.Subtract(start).TotalMilliseconds); | |
Console.ReadLine(); | |
} | |
public void ComputePoints() | |
{ | |
for (int x = 0; x < 20; x++) | |
{ | |
for (int y = 0; y < 20; y++) | |
{ | |
points.Add(new Point { x = x, y = y }); | |
} | |
} | |
} | |
public void ComputeSegments(Point pt) | |
{ | |
List<Segment> result = new List<Segment>(); | |
result.Add(ComputeUp(pt)); | |
result.Add(ComputeUpRight(pt)); | |
result.Add(ComputeRight(pt)); | |
result.Add(ComputeDownRight(pt)); | |
result.Add(ComputeDown(pt)); | |
result.Add(ComputeDownLeft(pt)); | |
result.Add(ComputeLeft(pt)); | |
result.Add(ComputeUpLeft(pt)); | |
segments[pt.ToString()] = result; | |
} | |
public int ComputeProduct(Segment seg, int[,] grid) | |
{ | |
if (seg.Count != 4) | |
return 0; | |
int idx = 0; | |
int[] vals = new int[4]; | |
foreach (Point pt in seg) | |
{ | |
vals[idx++] = grid[pt.x, pt.y]; | |
} | |
computations++; | |
return vals[0] * vals[1] * vals[2] * vals[3]; | |
} | |
public Segment ComputeUp(Point pt) | |
{ | |
var result = new Segment(); | |
if (pt.y >= 3) | |
{ | |
result.Add(new Point { x = pt.x, y = pt.y }); | |
result.Add(new Point { x = pt.x, y = pt.y - 1 }); | |
result.Add(new Point { x = pt.x, y = pt.y - 2 }); | |
result.Add(new Point { x = pt.x, y = pt.y - 3 }); | |
} | |
return result; | |
} | |
public Segment ComputeUpRight(Point pt) | |
{ | |
var result = new Segment(); | |
if (pt.y >= 3 && pt.x <= 16) | |
{ | |
result.Add(new Point { x = pt.x, y = pt.y }); | |
result.Add(new Point { x = pt.x + 1, y = pt.y - 1 }); | |
result.Add(new Point { x = pt.x + 2, y = pt.y - 2 }); | |
result.Add(new Point { x = pt.x + 3, y = pt.y - 3 }); | |
} | |
return result; | |
} | |
public Segment ComputeRight(Point pt) | |
{ | |
var result = new Segment(); | |
if (pt.x <= 16) | |
{ | |
result.Add(new Point { x = pt.x, y = pt.y }); | |
result.Add(new Point { x = pt.x + 1, y = pt.y }); | |
result.Add(new Point { x = pt.x + 2, y = pt.y }); | |
result.Add(new Point { x = pt.x + 3, y = pt.y }); | |
} | |
return result; | |
} | |
public Segment ComputeDownRight(Point pt) | |
{ | |
var result = new Segment(); | |
if (pt.x <= 16 && pt.y <= 16) | |
{ | |
result.Add(new Point { x = pt.x, y = pt.y }); | |
result.Add(new Point { x = pt.x + 1, y = pt.y + 1 }); | |
result.Add(new Point { x = pt.x + 2, y = pt.y + 2 }); | |
result.Add(new Point { x = pt.x + 3, y = pt.y + 3 }); | |
} | |
return result; | |
} | |
public Segment ComputeDown(Point pt) | |
{ | |
var result = new Segment(); | |
if (pt.y <= 16) | |
{ | |
result.Add(new Point { x = pt.x, y = pt.y }); | |
result.Add(new Point { x = pt.x, y = pt.y + 1 }); | |
result.Add(new Point { x = pt.x, y = pt.y + 2 }); | |
result.Add(new Point { x = pt.x, y = pt.y + 3 }); | |
} | |
return result; | |
} | |
public Segment ComputeDownLeft(Point pt) | |
{ | |
var result = new Segment(); | |
if (pt.x >= 3 && pt.y <= 16) | |
{ | |
result.Add(new Point { x = pt.x, y = pt.y }); | |
result.Add(new Point { x = pt.x - 1, y = pt.y + 1 }); | |
result.Add(new Point { x = pt.x - 2, y = pt.y + 2 }); | |
result.Add(new Point { x = pt.x - 3, y = pt.y + 3 }); | |
} | |
return result; | |
} | |
public Segment ComputeLeft(Point pt) | |
{ | |
var result = new Segment(); | |
if (pt.x >= 3) | |
{ | |
result.Add(new Point { x = pt.x, y = pt.y }); | |
result.Add(new Point { x = pt.x - 1, y = pt.y }); | |
result.Add(new Point { x = pt.x - 2, y = pt.y }); | |
result.Add(new Point { x = pt.x - 3, y = pt.y }); | |
} | |
return result; | |
} | |
public Segment ComputeUpLeft(Point pt) | |
{ | |
var result = new Segment(); | |
if (pt.x >= 3 && pt.y >= 3) | |
{ | |
result.Add(new Point { x = pt.x, y = pt.y }); | |
result.Add(new Point { x = pt.x - 1, y = pt.y - 1 }); | |
result.Add(new Point { x = pt.x - 2, y = pt.y - 2 }); | |
result.Add(new Point { x = pt.x - 3, y = pt.y - 3 }); | |
} | |
return result; | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment