Skip to content
May 20, 2011 / oop123

Project Euler #191 – Java

You can see the problem here: Problem #191.

This one is pretty easy. I used some dynamic programming to solve this (see Wikipedia if you don’t).

A Prize String can be grouped base on the number of consecutive As at the end of the string and whether it contains a late or not. For example, the string AAOOLOAOOOAA contains 2 consecutive A at the end and 1 L in it, or (2A, 1L). I constructed a table using these definitions; each cell of the table would contain the number of Price Strings that fits a particular definition.

0A 1A 2A
1L A B C
0L D E F

A table for today’s Prize Strings can be transform next day’s Prize Strings with a few rules. For example, a Price String of (0A, 1L) can remain in (0A, 1L) by adding an O to the end or become (1A, 1L) by adding an A to the end. The following are all the rules (found with some simple logic):

  1. A (0A, 1L)
    • + 1 Absent -> B (1A, 1L)
    • + 1 Ontime -> A (0A, 1L)
  2. B (1A, 1L)
    • + 1 Absent -> C (2A, 1L)
    • + 1 Ontime -> A (0A, 1L)
  3. C (2A, 1L)
    • + 1 Ontime -> A (0A, 1L)
  4. D (0A, 0L)
    • + 1 Late -> A (0A, 1L)
    • + 1 Absent -> E (1A, 0L)
    • + 1 Ontime -> D (0A, 0L)
  5. E (1A, 0L)
    • + 1 Late -> A (0A, 1L)
    • + 1 Absent -> F (2A, 0L)
    • + 1 Ontime -> D (0A, 0L)
  6. F (2A, 0L)
    • + 1 Late -> A (0A, 1L)
    • + 1 Ontime -> D (0A, 0L)

With these rules, you can create next day’s table from today’s table.

0A 1A 2A
1L A + B + C + D + E + F A B
0L D + E + F D E

The first day’s table will look like this with 1 absent, 1 late, and 1 on-time:

0A 1A 2A
1L 1 0 0
0L 1 1 0

We can then just repeatedly apply the transformation rules to get the 30th day’s table. The answer would be the sum of the numbers inside the table.

int A = 1, B = 0, C = 0,
     D = 1, E = 1, F = 0;
int tA, tB, tC, tD, tE, tF; //temporary variables

for (int i = 2; i     tA = A;
    tB = B;
    tC = C;
    tD = D;
    tE = E;
    tF = F;

    //all the transformations I described above
    A = tA + tB + tC + tD + tE + tF;
    B = tA;
    C = tB;
    D = tD + tE + tF;
    E = tD;
    F = tE;
}

System.out.println(A + B + C + D + E + F);

Runs in ~1 millisecond. A simple question. Dynamic Programming for the win! CU

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: