<?php
$input = file('input.txt');

$initial_state = str_replace("\n",'',str_replace('initial state: ','',array_shift($input)));
$charmaps = array();

for($i=1;$i<count($input);$i++)
{
    list($key, $value) = explode(' => ', $input[$i]);
    $charmaps[$key] = $value[0];
}

function get_generation($generation, $initial_state, $charmaps, $search_diff = false)
{
    $padding = $generation*2;

    $padding_string = implode('',array_fill(0,$padding,'.'));

    $search_string = $padding_string . $initial_state . $padding_string;

    $generations = $generation;
    $last_sum = 0;
    $diff = 0;
    $trend = array();

    for($i=0;$i<$generations;$i++)
    {
        $new_generation = substr($search_string,0,2);

        for($j=2;$j<strlen($search_string);$j++)
        {
            $searchkey = substr($search_string,$j-2,5);
            if(isset($charmaps[$searchkey]))
            {
                $new_generation .= $charmaps[$searchkey];
            } else {
                $new_generation .= '.';//$search_string[$j];
            }
        }
        $search_string = $new_generation;

        $sum =0;

        for($x=0;$x<strlen($search_string);$x++)
        {
            if($search_string[$x] == '#')
            {
                $sum += $x - $padding;
            }
        }

        $diff = $sum - $last_sum;

        $last_sum = $sum;

        if($search_diff)
        {
            $trend[] = $diff;
            $vals = array_count_values($trend);

            //assume we have a trend when the diff is the most common diff count > 8
            $check_diff = array_search(8, $vals);
            if($check_diff && $check_diff == $diff) {
                return array('sum' => $sum, 'diff' => $check_diff, 'gen' => $i+1);
            }
        }

    }


    return array('sum'=>$sum, 'diff'=>$diff, 'gen'=>$i);
}

printf('Part 1: %d', get_generation(20, $initial_state, $charmaps)['sum']);
echo PHP_EOL;

$gen_search = 500;

$result = get_generation($gen_search, $initial_state, $charmaps, true);
$sum = $result['sum'] + $result['diff'] * (50000000000 -  $result['gen']);
printf('Part 2: %d', $sum);
echo PHP_EOL;