random thoughts on science and tech... yeah, it used to be about electronic lab notebooks but that was a decade ago

Google Code Jam 2012 Round 1A – Password problems

Have you ever been part way through typing your password and thought that maybe you messed up?

Is it better to delete and start over or just finish out and hope you didn’t mess up? Are you pretty sure, if you did mess up, it was in the last letter you typed – so maybe deleting one letter and retyping would be best?

Have no fear, if we record you every time you enter your password and get the percentage of time that you mess up for each letter in your password. We can then use the handy program that I wrote for Google Code Jam’s ‘Password Problem’  to tell you what the most efficient way to proceed is.

I only had about 45 minutes of the 2 and a half hours for this Round 1A (you know kids, work, stuff). So I decided to just do the first question (round 1b and 1c are at better times for me – middle of night/kids asleep). I did pretty good, I’m coming right along in C#. And I’m pretty sure that this time, on the large data set for the problem, C# may have actually helped. Python may have been too slow (with the way I wrote the algorithm), but C# blazed through in no time… Actually maybe Python would have been fine.

Here’s what I went with. Let me know if you have suggestions. This is only 4 weeks of C# – so I would love to get feedback in anyway.

using System;
using System.Collections.Generic;
using System.IO;

namespace GCJ2012 {
internal class R1Aa {
public static void Main() {
string filePath = @"C:Usersshawn.mcclellandDownloadsA−large.in";
var fileIn = new StreamReader(filePath);
filePath = filePath.Remove(filePath.Length − 2) + "out";
var fileOut = new StreamWriter(filePath);

int totalCase = Convert.ToInt32(fileIn.ReadLine());
for (int curCase = 0; curCase < totalCase; ++curCase) {
string[] str = fileIn.ReadLine().Split(new[] {' '}, StringSplitOptions.RemoveEmptyEntries);
string[] str2 = fileIn.ReadLine().Split(new[] { ' ' }, StringSplitOptions.RemoveEmptyEntries);
fileOut.WriteLine("Case #{0}: {1}", curCase + 1, _Solve(str, str2));
}
fileIn.Close();
fileOut.Close();
}

private static string _Solve(string[] str, string[] str2) {
int A = Convert.ToInt32(str[0]);
int B = Convert.ToInt32(str[1]);
var ps = new List();
double result = 2 + B;
if (result > A + B + 1) {
result = A + B + 1;
}
int count = 1;
foreach(string p in str2) {
ps.Add(Convert.ToDouble(p));
double tmp = _ExpectedKeystrokes(ps, count, B) + A − count;
count++;
if (result > tmp) {
result = tmp;
}

}
return result.ToString("0.000000");

}

private static double _ExpectedKeystrokes(List ps, int A, int B) {
double psum = 1;
foreach(double p in ps) {
psum *= (p);
}
return psum*(B − A+1) + (1 − psum)*(B − A + B + 2);
}
}
}

1 Comment

  1. April 30, 2012    

    can u explaing me
    solution??

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>