Problem #86 says:
A spider, S, sits in one corner of a cuboid room, measuring 6 by 5 by 3, and a fly, F, sits in the opposite corner. By travelling on the surfaces of the room the shortest “straight line” distance from S to F is 10 and the path is shown on the diagram.
However, there are up to three “shortest” path candidates for any given cuboid and the shortest route is not always integer.
By considering all cuboid rooms with integer dimensions, up to a maximum size of M by M by M, there are exactly 2060 cuboids for which the shortest distance is integer when M=100, and this is the least value of M for which the number of solutions first exceeds two thousand; the number of solutions is 1975 when M=99.
Find the least value of M such that the number of solutions first exceeds one million.
I thought this problem was going to be more interesting than it turned out being. Basically we’re looking for triplets (a,b,M) where 1<=a<=b<=M that make the equation \((a+b)^{2}+n^{2}\) a perfect square. We just do this for every value M=1-?? and count the number of solutions for that M value until the sum of all previous solution counts equals one million. Basically we take M = 3 which has a solution count of 3 and is the first none zero solution count and M = 4 with a solution count of 1; We add the solutions counts for M = 1-4 which are {0,0,2,1} and check to see if the sum of that series is greater than one million. If that sum isn’t one million we calculate the next value of M and add that to the series and check the series sum again; wash, rinse, repeat.
This problem became a lot less interesting when I found the formula for the shortest point and googled it and came back with two OEIS sequences (A143714,A143715) which made the solution trivial to write because it showed the method of building on the previous M values. On the other hand trivial to program solutions mean a lot less time spent frustrated trying to get the program to work.
Solution provided in c#/mono and runs in ~30ish seconds. Not the fastest but it works.
using System;
using System.Linq;
using System.Collections.Generic;
namespace Problem86
{
class MainClass
{
public static List<int> A143714 = new List<int>();
public static void Main (string[] args)
{
A143714.Add(0);
A143714.Add(0);
while(A143714.Sum() < 1000000)
{
int n = A143714.Count+1;
int count = 0;
for (int b = 1;b<=n;b++)
{
for (int a = 1;a<=b;a++)
{
if (IsPerfectSquare(((a+b)*(a+b))+(n*n)))
count++;
}
}
A143714.Add(count);
}
Console.WriteLine(A143714.Count);
}
public static bool IsPerfectSquare(int input)
{
var sqrt = Math.Sqrt((double)input);
return Math.Ceiling(sqrt) == Math.Floor(sqrt);
}
}
}
With this solution I have only 11 problems left between 1-100 and only 39 left until I hit level 4!
Tags: c#, mono, project euler
Posted in General | Comments (0)
Problem #68 boils down to:
… By concatenating each group it is possible to form 9-digit strings; the maximum string for a 3-gon ring is 432621513.
Using the numbers 1 to 10, and depending on arrangements, it is possible to form 16- and 17-digit strings. What is the maximum 16-digit string for a “magic” 5-gon ring?
Some rules apply. First all of the spars must add up to the same number and you need to pay close attention to how you build the final answer to put into the answer box or you’ll get told your correct polygon is wrong. (See the Project Euler page for details and an example)
This is a question that is easier solved on paper with a pencil than any program. Just a few simple assumptions will make solving this problem easier: 1) The outer ring has a higher place value compared to it’s inner ring counterparts. 2) You want a large number so it’s easy see you want the numbers 6-10 on the outer rings. 3) We want a 16 digit number which means that the 10 must be on the outer ring else it gets counted twice and you’ll end up with a 17 digit polygon.
There is no solution presented for this problem; however with the above hints it’s very easy to build the answer.
Tags: Math, pen and paper, project euler
Posted in General | Comments (0)
Problem #85 says:
By counting carefully it can be seen that a rectangular grid measuring 3 by 2 contains eighteen rectangles; Although there exists no rectangular grid that contains exactly two million rectangles, find the area of the grid with the nearest solution.
The project euler site has a nifty picture showing an example. This solution is really simple; in fact I would be willing to bet that anybody who has taken high school algebra should be able to solve this with an efficient formula. The formula we’ll use is based off of the formula for adding the numbers from one to x which looks like this ((x*x)+x)/2 so what do we do when we have two dimensions? Simply multiply to obtain (((x*x)+x)/2)(((y*y)+y)/2) which becomes (((x*x)+x)((y*y)+y))/4 since this grows pretty fast we can cap the endpoints of our search to 100 for both x and y. Another thing to note is the below solution will give us the same rectangle rotated 90 degrees which I simply ignore.
Solution provided in f# and runs in under a second. Written using mono and the f# mono-develop plug-in!
open System
open System.Collections
open System.Diagnostics
open Microsoft.FSharp.Collections
let RectInRect target =
seq{
for x = 1 to 100 do
for y = 1 to 100 do
let rectangles = (((x*x)+x)/2)*(((y*y)+y)/2)
if (float rectangles) > (float target) * 0.9995 && (float rectangles) < (float target) * 1.0005 then
yield (x,y)
}
|> Seq.toList
[<EntryPoint>]
let main args =
let sw = new Stopwatch()
sw.Start()
let r = RectInRect 2000000
for x in r do
Console.WriteLine ((fst x) * (snd x))
Console.WriteLine (Convert.ToString(fst x)+ " " + Convert.ToString(snd x))
sw.Stop()
Console.WriteLine(sw.Elapsed)
0
Tags: f#, Math, mono, project euler, tuples
Posted in General | Comments (0)
So I was wandering the internet when I found an article about steganography, which is the art of hiding something in plain sight. Such as hiding a message inside a picture. Specifically the least significant bit method where you take the RGB color values of the pixel and set them based off a message in binary your encoding. So I figured I’d work something up and see if I could do that. This is a first attempt and it only encodes the message, right now it’ll truncate it if it doesn’t have enough pixels to work with or if the message length in binary isn’t divisible by three. Obviously this is a first attempt and a very simple one at that.
So basically you give it a picture and a text file and it reads the text file as a single string, converts it to binary then for each pixel it sets each of the RGB values based off the binary message value for that position. In this example if the binary message is odd for this position we set the color to an odd number (in effect setting the least significant bit to 1) else we make sure its an even number.
I have a few plans for expanding this project. It would be nice to decode the messages first of all, it would also be nice to have some options for encoding such as skipping a certain number of pixels between parts of the message, Only using certain color channels etc. But for now this is what I have.
using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.IO;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Windows.Forms;
namespace Steganography
{
public partial class Form1 : Form
{
public Form1()
{
InitializeComponent();
}
private void btnBrowse_Click(object sender, EventArgs e)
{
OpenFileDialog op = new OpenFileDialog();
op.CheckPathExists = true;
op.CheckFileExists = true;
op.Filter = "JPG image |*.jpg";
op.ShowDialog();
textBox1.Text = op.FileName;
}
private void textBox1_TextChanged(object sender, EventArgs e)
{
try
{
Preview.ImageLocation = textBox1.Text ;
}
catch
{
}
}
private void BrowseMessage_Click(object sender, EventArgs e)
{
OpenFileDialog op = new OpenFileDialog();
op.CheckPathExists = true;
op.CheckFileExists = true;
op.ShowDialog();
textBox2.Text = op.FileName;
}
private void button1_Click(object sender, EventArgs e)
{
MessageBox.Show("Your image will be saved as " + textBox1.Text +".new");
//Get message as a binary string;
string message = LoadMessage(textBox2.Text);
string binmessage = "";
foreach (char letter in message.ToCharArray())
{
binmessage += Convert.ToString(letter, 2);
}
//get bitmap of image.
Bitmap bitm = (Bitmap)Preview.Image.Clone();
int mPosition = 0;
//Embed message
#region embed
for (int height = 0; height < bitm.Height; height++)
{
for (int width = 0; width < bitm.Width; width++)
{
if (mPosition + 3 <= binmessage.Length)
{
Color pixelColor = bitm.GetPixel(width, height);
int R = int.Parse(pixelColor.R.ToString());
int G = int.Parse(pixelColor.G.ToString());
int B = int.Parse(pixelColor.B.ToString());
int m1 = int.Parse(binmessage[mPosition].ToString());
mPosition++;
int m2 = int.Parse(binmessage[mPosition].ToString());
mPosition++;
int m3 = int.Parse(binmessage[mPosition].ToString());
mPosition++;
if (m1 % 2 == 0)
{
if (R % 2 != 0 && R > 0)
{
R -= 1;
}
else
{
R += 1;
}
}
else
{
if (R % 2 != 1 && R > 0)
{
R -= 1;
}
else
{
R += 1;
}
}
if (m2 % 2 == 0)
{
if (G % 2 != 0 && G > 0)
{
G -= 1;
}
else
{
G += 1;
}
}
else
{
if (G % 2 != 1 && G > 0)
{
G -= 1;
}
else
{
G += 1;
}
}
if (m3 % 2 == 0)
{
if (B % 2 != 0 && B > 0)
{
B -= 1;
}
else
{
B += 1;
}
}
else
{
if (B % 2 != 1 && B > 0)
{
B -= 1;
}
else
{
B += 1;
}
}
Color pc = Color.FromArgb(R, G, B);
bitm.SetPixel(width, height, pc);
}
else
{
}
}
}
#endregion embed
bitm.Save(textBox1.Text + ".new");
}
private string LoadMessage(string p)
{
string RetValue = "";
StreamReader sr;
sr = File.OpenText(p);
RetValue = sr.ReadToEnd();
sr.Close();
return RetValue;
}
}
}
Tags: c#, csharp, programming
Posted in General, Software | Comments (0)
Because there’s nothing like running through a town with a sledgehammer destroying anything that moves…
Definitely one of the most entertaining games, the vehicles handle well, and there is a lot of weapons to choose from when planning how your going to attack the EDF. Plus you get a rifle that eats people alive!
Posted in General, Software | Comments (0)