## solve stauf painting puzzle
get.move = function(val){
 move = c(0,0,0,0,0,0,0,0,0)
 if(val == 1) move = c(1,1,0,1,1,0,0,0,0)
 if(val == 2) move = c(1,1,1,0,0,0,0,0,0)
 if(val == 3) move = c(0,1,1,0,1,1,0,0,0)
 if(val == 4) move = c(1,0,0,1,0,0,1,0,0)
 if(val == 5) move = c(0,1,0,1,1,1,0,1,0)
 if(val == 6) move = c(0,0,1,0,0,1,0,0,1)
 if(val == 7) move = c(0,0,0,1,1,0,1,1,0)
 if(val == 8) move = c(0,0,0,0,0,0,1,1,1)
 if(val == 9) move = c(0,0,0,0,1,1,0,1,1)
 return(move)
}

compose.vectors = function(v1,v2){
  return((v1+v2) %% 3)
}

compose = function(puz,vals){
  for(val in vals){ puz = compose.vectors(puz,get.move(val)) }
  return(puz)
}

solve.puz = function(init){
  puzzle = init
  moves = c()
  while(!all(puzzle == rep(0,9))){
    new.move = sample(1:9,1)
    moves = c(moves,new.move)
    moves = remove.dupes(moves)
    puzzle = compose(puzzle,new.move)
  }
  return(moves)
}

remove.dupes = function(moves){
  t = table(moves)
  if(any(t > 2)){
    moves.to.delete = names(which(t > 2))
    ind = moves %in% moves.to.delete
    moves = moves[!ind]
  }
  return(moves)
}

##

init = c(0,1,1,0,0,1,0,0,0)
init = c(2,2,0,2,2,0,0,0,0)
solution = solve.puz(init)
print(sort(solution))

# can use compose to specify moves
compose(init,1)
compose(init,c(1,1,3,4,2,8))

############

## Much faster solution
move.one.pos = function(position){
  ret.moves = rep(0,9)
  if(position == 1) ret.moves = c(1,3,5,6,6,7,8,8,9,9)
  if(position == 2) ret.moves = c(1,2,3,4,5,6,8,8)
  if(position == 3) ret.moves = c(1,3,4,4,5,7,7,8,8,9)
  if(position == 4) ret.moves = c(1,2,4,5,6,6,7,8)
  if(position == 5) ret.moves = c(1,2,3,4,6,7,8,9)
  if(position == 6) ret.moves = c(2,3,4,4,5,6,8,9)
  if(position == 7) ret.moves = c(1,2,2,3,3,5,6,6,7,9)
  if(position == 8) ret.moves = c(2,2,4,5,6,7,8,9)
  if(position == 9) ret.moves = c(1,1,2,2,3,4,4,5,7,9)
  return(ret.moves)
}

remove.all.dupes = function(prev.moves){
  moves = c()
  for(i in 1:9){
    if(!(i %in% prev.moves)) next
    n_vals = length(which(prev.moves == i))
    n.rep = n_vals %% 3
    if(n.rep == 0) next
    moves = c(moves,rep(i,n.rep))
  }
  return(moves)
}

solve.puz.2 = function(puz){
  moves = c()
  for(i in seq_along(puz)){
    how.many.to.press = (3 - puz[i]) %% 3
    if(how.many.to.press > 0){
      for(j in 1:how.many.to.press) moves = c(moves,move.one.pos(i))
    }
  }
  moves = sort(remove.all.dupes(moves))
  return(moves)
}

init = c(2,1,0,2,2,1,0,1,0)
solve.puz.2(init)