# 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):

- A (0A, 1L)
- + 1 Absent -> B (1A, 1L)
- + 1 Ontime -> A (0A, 1L)
- B (1A, 1L)
- + 1 Absent -> C (2A, 1L)
- + 1 Ontime -> A (0A, 1L)
- C (2A, 1L)
- + 1 Ontime -> A (0A, 1L)
- D (0A, 0L)
- + 1 Late -> A (0A, 1L)
- + 1 Absent -> E (1A, 0L)
- + 1 Ontime -> D (0A, 0L)
- E (1A, 0L)
- + 1 Late -> A (0A, 1L)
- + 1 Absent -> F (2A, 0L)
- + 1 Ontime -> D (0A, 0L)
- 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

## Leave a Reply