Java - 2,610,797 steps

This is my basic reference algorithm submission, simply makes a histogram of the squares on the edges of the painted area, and paints with the most common color. Runs the 100k in just over a minute.

import java.io.*; import java.util.*; public class PainterAI { public static void main(String[] args) throws IOException { int totalSteps = 0, numSolved = 0; char[] board = new char[361]; Scanner s = new Scanner(new File("floodtest")); long startTime = System.nanoTime(); caseloop: while (s.hasNextLine()) { for (int l = 0; l < 19; l++) { String line = s.nextLine(); if (line.isEmpty()) continue caseloop; System.arraycopy(line.toCharArray(), 0, board, l * 19, 19); } List<Character> colorsUsed = new ArrayList<>(); Stack<Integer> nodes = new Stack<>(); for (;; totalSteps++) { char p = board[180]; int[] occurrences = new int[7]; nodes.add(180); int numToPaint = 0; while (!nodes.empty()) { int n = nodes.pop(); if (n < 0 || n > 360) continue; if (board[n] == p) { board[n] = 48; numToPaint++; nodes.push(n - 1); nodes.push(n + 1); nodes.push(n - 19); nodes.push(n + 19); } else occurrences[board[n] - 48]++; } if (numToPaint == 361) break; char mostFrequent = 0; int times = -1; for (int i = 1; i < 7; i++) if (occurrences[i] > times) { times = occurrences[i]; mostFrequent = (char) (i + 48); } for (int i = 0; i < 361; i++) if (board[i] == 48) board[i] = mostFrequent; //colorsUsed.add(mostFrequent); } numSolved++; /*String out = ""; for (Character c : colorsUsed) out += c; System.out.println(out); //print output*/ } s.close(); System.out.println("Total steps to solve all cases: " + totalSteps); System.out.printf("\nSolved %d test cases in %.2f seconds", numSolved, (System.nanoTime() - startTime) / 1000000000.); } } 

Golfs to 822 chars (not including the newlines for formatting), but could be shrunk more if I felt like trying:

import java.io.*;import java.util.*;class P{ public static void main(String[]a)throws Exception{int t=0;char[]b=new char[361]; Scanner s=new Scanner(new File("floodtest"));c:while(s.hasNextLine()){ for(int l=0;l<19;l++){String L=s.nextLine();if(L.isEmpty())continue c; System.arraycopy(L.toCharArray(),0,b,l*19,19);}List<Character>u=new ArrayList<>(); Stack<Integer>q=new Stack<>();for(int[]o=new int[7];;t++){char p=b[180];q.add(180); int m=0;while(!q.empty()){int n=q.pop();if(n<0|n>360)continue;if(b[n]==p){b[n]=48;m++; q.push(n-1);q.push(n+1);q.push(n-19);q.push(n+19);}else o[b[n]-48]++;}if(m==361)break; char f=0;int h=0;for(int i=1;i<7;i++)if(o[i]>h){h=o[i];f=(char)(i+48);} for(int i=0;i<361;i++)if(b[i]==48)b[i]=f;u.add(f);}String y="";for(char c:u)y+=c; System.out.println(y);}s.close();System.out.println("Steps: "+t);}} 

Java - 2,610,797 4,780,841 steps

(Fill-Bug fixed, score is now dramatically worse -_- )

This is my basic reference algorithm submission, simply makes a histogram of the squares on the edges of the painted area, and paints with the most common color. Runs the 100k in a couple minutes.

import java.io.*; import java.util.*; public class PainterAI { public static void main(String[] args) throws IOException { int totalSteps = 0, numSolved = 0; char[] board = new char[361]; Scanner s = new Scanner(new File("floodtest")); long startTime = System.nanoTime(); caseloop: while (s.hasNextLine()) { for (int l = 0; l < 19; l++) { String line = s.nextLine(); if (line.isEmpty()) continue caseloop; System.arraycopy(line.toCharArray(), 0, board, l * 19, 19); } List<Character> colorsUsed = new ArrayList<>(); Stack<Integer> nodes = new Stack<>(); for (;; totalSteps++) { char p = board[180]; int[] occurrences = new int[7]; nodes.add(180); int numToPaint = 0; while (!nodes.empty()) { int n = nodes.pop(); if (n < 0 || n > 360) continue; if (board[n] == p) { board[n] = 48; numToPaint++; if (n % 19 > 0) nodes.push(n - 1); if(n%19<18)   nodes.push(n + 1); if(n/19>0)   nodes.push(n - 19); if(n/19<18)   nodes.push(n + 19); } else occurrences[board[n] - 48]++; } if (numToPaint == 361) break; char mostFrequent = 0; int times = -1; for (int i = 1; i < 7; i++) if (occurrences[i] > times) { times = occurrences[i]; mostFrequent = (char) (i + 48); } for (int i = 0; i < 361; i++) if (board[i] == 48) board[i] = mostFrequent; //colorsUsed.add(mostFrequent); } numSolved++; /*String out = ""; for (Character c : colorsUsed) out += c; System.out.println(out); //print output*/ } s.close(); System.out.println("Total steps to solve all cases: " + totalSteps); System.out.printf("\nSolved %d test cases in %.2f seconds", numSolved, (System.nanoTime() - startTime) / 1000000000.); } } 

Golfs to 860 chars (not including the newlines for formatting), but could be shrunk more if I felt like trying:

import java.io.*;import java.util.*;class P{ public static void main(String[]a)throws Exception{int t=0;char[]b=new char[361]; Scanner s=new Scanner(new File("floodtest"));c:while(s.hasNextLine()){ for(int l=0;l<19;l++){String L=s.nextLine();if(L.isEmpty())continue c; System.arraycopy(L.toCharArray(),0,b,l*19,19);}List<Character>u=new ArrayList<>(); Stack<Integer>q=new Stack<>();for(int[]o=new int[7];;t++){char p=b[180];q.add(180); int m=0;while(!q.empty()){int n=q.pop();if(n<0|n>360)continue;if(b[n]==p){b[n]=48;m++; if(n%19>0)q.add(n-1);if(n%19<18)q.add(n+1);if(n/19>0)q.add(n-19);if(n/19<18) q.add(n+19);}else o[b[n]-48]++;}if(m==361)break; char f=0;int h=0;for(int i=1;i<7;i++)if(o[i]>h){h=o[i];f=(char)(i+48);} for(int i=0;i<361;i++)if(b[i]==48)b[i]=f;u.add(f);}String y="";for(char c:u)y+=c; System.out.println(y);}s.close();System.out.println("Steps: "+t);}}