#!/bin/bash

read line
read line
read line
read line2
column_1=( ${line:3:1} D D ${line2:1:1} )
column_2=( ${line:5:1} C B ${line2:3:1} )
column_3=( ${line:7:1} B A ${line2:5:1} )
column_4=( ${line:9:1} A C ${line2:7:1} )
column_len=4
declare -A energies
energies[A]=1
energies[B]=10
energies[C]=100
energies[D]=1000
min_energy=10000000000

declare -A encountered_configurations

function move() {
  local column_1=( ${1//_/ } )
  local column_2=( ${2//_/ } )
  local column_3=( ${3//_/ } )
  local column_4=( ${4//_/ } )
  local hallway=( ${5//_/ } )
  local energy=$6

  if [ ${encountered_configurations[1$12$23$34$4H$5$6]} ]; then
    return 0
  else
    encountered_configurations[1$12$23$34$4H$5$6]=1
  fi

  if ! [[ $5 == *[ABCD]* ]] && ! [[ $1 == *[BCD]* ]] && ! [[ $2 == *[ACD]* ]] && ! [[ $3 == *[ABD]* ]] \
          && ! [[ $4 == *[ABC]* ]]; then
    if [ $energy -lt $min_energy ]; then
      min_energy=$energy
    fi
  fi

  if ! [[ $1 == *[BCD]* ]]; then
    if [[ ${hallway[0]} == 'A' ]] && [[ ${hallway[1]} == "O" ]]; then
      move '_A'$1 $2 $3 $4 'O'${5:1} $((energy+2+column_len-${#column_1[@]}))
    fi
    if [[ ${hallway[1]} == 'A' ]]; then
      move '_A'$1 $2 $3 $4 ${5:0:2}'O'${5:3} $((energy+1+column_len-${#column_1[@]}))
    fi
    if [[ ${hallway[2]} == 'A' ]]; then
      move '_A'$1 $2 $3 $4 ${5:0:4}'O'${5:5} $((energy+1+column_len-${#column_1[@]}))
    fi
    if [[ ${hallway[3]} == 'A' ]] && [[ ${hallway[2]} == "O" ]]; then
      move '_A'$1 $2 $3 $4 ${5:0:6}'O'${5:7} $((energy+3+column_len-${#column_1[@]}))
    fi
    if [[ ${hallway[4]} == 'A' ]] && [[ ${hallway[3]} == "O" ]] && [[ ${hallway[2]} == "O" ]]; then
      move '_A'$1 $2 $3 $4 ${5:0:8}'O'${5:9} $((energy+5+column_len-${#column_1[@]}))
    fi
    if [[ ${hallway[5]} == 'A' ]] && [[ ${hallway[4]} == "O" ]] && [[ ${hallway[3]} == "O" ]] \
            && [[ ${hallway[2]} == "O" ]]; then
      move '_A'$1 $2 $3 $4 ${5:0:10}'O'${5:11} $((energy+7+column_len-${#column_1[@]}))
    fi
    if [[ ${hallway[6]} == 'A' ]] && [[ ${hallway[5]} == "O" ]] && [[ ${hallway[4]} == "O" ]] \
            && [[ ${hallway[3]} == "O" ]] && [[ ${hallway[2]} == "O" ]]; then
      move '_A'$1 $2 $3 $4 ${5:0:12}'O' $((energy+8+column_len-${#column_1[@]}))
    fi
  elif [ ${#column_1[@]} -gt 0 ]; then
    if [[ ${hallway[0]} == "O" ]] && [[ ${hallway[1]} == "O" ]]; then
      move ${1:2} $2 $3 $4 ${column_1[0]}${5:1} $((energy+(3+column_len-${#column_1[@]})*${energies[${column_1[0]}]}))
    fi
    if [[ ${hallway[1]} == "O" ]]; then
      move ${1:2} $2 $3 $4 ${5:0:2}${column_1[0]}${5:3} $((energy+(2+column_len-${#column_1[@]})*${energies[${column_1[0]}]}))
    fi
    if [[ ${hallway[2]} == "O" ]]; then
      move ${1:2} $2 $3 $4 ${5:0:4}${column_1[0]}${5:5} $((energy+(2+column_len-${#column_1[@]})*${energies[${column_1[0]}]}))
    fi
    if [[ ${hallway[2]} == "O" ]] && [[ ${hallway[3]} == "O" ]]; then
      move ${1:2} $2 $3 $4 ${5:0:6}${column_1[0]}${5:7} $((energy+(4+column_len-${#column_1[@]})*${energies[${column_1[0]}]}))
    fi
    if [[ ${hallway[2]} == "O" ]] && [[ ${hallway[3]} == "O" ]] && [[ ${hallway[4]} == "O" ]]; then
      move ${1:2} $2 $3 $4 ${5:0:8}${column_1[0]}${5:9} $((energy+(6+column_len-${#column_1[@]})*${energies[${column_1[0]}]}))
    fi
    if [[ ${hallway[2]} == "O" ]] && [[ ${hallway[3]} == "O" ]] && [[ ${hallway[4]} == "O" ]] \
            && [[ ${hallway[5]} == "O" ]]; then
      move ${1:2} $2 $3 $4 ${5:0:10}${column_1[0]}${5:11} $((energy+(8+column_len-${#column_1[@]})*${energies[${column_1[0]}]}))
    fi
    if [[ ${hallway[2]} == "O" ]] && [[ ${hallway[3]} == "O" ]] && [[ ${hallway[4]} == "O" ]] \
            && [[ ${hallway[5]} == "O" ]] && [[ ${hallway[6]} == "O" ]]; then
      move ${1:2} $2 $3 $4 ${5:0:12}${column_1[0]} $((energy+(9+column_len-${#column_1[@]})*${energies[${column_1[0]}]}))
    fi
  fi

  if ! [[ $2 == *[ACD]* ]]; then
    if [[ ${hallway[0]} == 'B' ]] && [[ ${hallway[1]} == "O" ]] && [[ ${hallway[2]} == "O" ]]; then
      move $1 '_B'$2 $3 $4 'O'${5:1} $((energy+(4+column_len-${#column_2[@]})*10))
    fi
    if [[ ${hallway[1]} == 'B' ]] && [[ ${hallway[2]} == "O" ]]; then
      move $1 '_B'$2 $3 $4 ${5:0:2}'O'${5:3} $((energy+(3+column_len-${#column_2[@]})*10))
    fi
    if [[ ${hallway[2]} == 'B' ]]; then
      move $1 '_B'$2 $3 $4 ${5:0:4}'O'${5:5} $((energy+(1+column_len-${#column_2[@]})*10))
    fi
    if [[ ${hallway[3]} == 'B' ]]; then
      move $1 '_B'$2 $3 $4 ${5:0:6}'O'${5:7} $((energy+(1+column_len-${#column_2[@]})*10))
    fi
    if [[ ${hallway[4]} == 'B' ]] && [[ ${hallway[3]} == "O" ]]; then
      move $1 '_B'$2 $3 $4 ${5:0:8}'O'${5:9} $((energy+(3+column_len-${#column_2[@]})*10))
    fi
    if [[ ${hallway[5]} == 'B' ]] && [[ ${hallway[4]} == "O" ]] && [[ ${hallway[3]} == "O" ]]; then
      move $1 '_B'$2 $3 $4 ${5:0:10}'O'${5:11} $((energy+(5+column_len-${#column_2[@]})*10))
    fi
    if [[ ${hallway[6]} == 'B' ]] && [[ ${hallway[5]} == "O" ]] && [[ ${hallway[4]} == "O" ]] \
            && [[ ${hallway[3]} == "O" ]]; then
      move $1 '_B'$2 $3 $4 ${5:0:12}'O' $((energy+(6+column_len-${#column_2[@]})*10))
    fi
  elif [ ${#column_2[@]} -gt 0 ]; then
    if [[ ${hallway[0]} == "O" ]] && [[ ${hallway[1]} == "O" ]] && [[ ${hallway[2]} == "O" ]]; then
      move $1 ${2:2} $3 $4 ${column_2[0]}${5:1} $((energy+(5+column_len-${#column_2[@]})*${energies[${column_2[0]}]}))
    fi
    if [[ ${hallway[1]} == "O" ]] && [[ ${hallway[2]} == "O" ]]; then
      move $1 ${2:2} $3 $4 ${5:0:2}${column_2[0]}${5:3} $((energy+(4+column_len-${#column_2[@]})*${energies[${column_2[0]}]}))
    fi
    if [[ ${hallway[2]} == "O" ]]; then
      move $1 ${2:2} $3 $4 ${5:0:4}${column_2[0]}${5:5} $((energy+(2+column_len-${#column_2[@]})*${energies[${column_2[0]}]}))
    fi
    if [[ ${hallway[3]} == "O" ]]; then
      move $1 ${2:2} $3 $4 ${5:0:6}${column_2[0]}${5:7} $((energy+(2+column_len-${#column_2[@]})*${energies[${column_2[0]}]}))
    fi
    if [[ ${hallway[3]} == "O" ]] && [[ ${hallway[4]} == "O" ]]; then
      move $1 ${2:2} $3 $4 ${5:0:8}${column_2[0]}${5:9} $((energy+(4+column_len-${#column_2[@]})*${energies[${column_2[0]}]}))
    fi
    if [[ ${hallway[3]} == "O" ]] && [[ ${hallway[4]} == "O" ]] && [[ ${hallway[5]} == "O" ]]; then
      move $1 ${2:2} $3 $4 ${5:0:10}${column_2[0]}${5:11} $((energy+(6+column_len-${#column_2[@]})*${energies[${column_2[0]}]}))
    fi
    if [[ ${hallway[3]} == "O" ]] && [[ ${hallway[4]} == "O" ]] && [[ ${hallway[5]} == "O" ]] \
            && [[ ${hallway[6]} == "O" ]]; then
      move $1 ${2:2} $3 $4 ${5:0:12}${column_2[0]} $((energy+(7+column_len-${#column_2[@]})*${energies[${column_2[0]}]}))
    fi
  fi

  if ! [[ $3 == *[ABD]* ]]; then
    if [[ ${hallway[0]} == 'C' ]] && [[ ${hallway[1]} == "O" ]] && [[ ${hallway[2]} == "O" ]] \
            && [[ ${hallway[3]} == "O" ]]; then
      move $1 $2 '_C'$3 $4 'O'${5:1} $((energy+(6+column_len-${#column_3[@]})*100))
    fi
    if [[ ${hallway[1]} == 'C' ]] && [[ ${hallway[2]} == "O" ]] && [[ ${hallway[3]} == "O" ]]; then
      move $1 $2 '_C'$3 $4 ${5:0:2}'O'${5:3} $((energy+(5+column_len-${#column_3[@]})*100))
    fi
    if [[ ${hallway[2]} == 'C' ]] && [[ ${hallway[3]} == "O" ]]; then
      move $1 $2 '_C'$3 $4 ${5:0:4}'O'${5:5} $((energy+(3+column_len-${#column_3[@]})*100))
    fi
    if [[ ${hallway[3]} == 'C' ]]; then
      move $1 $2 '_C'$3 $4 ${5:0:6}'O'${5:7} $((energy+(1+column_len-${#column_3[@]})*100))
    fi
    if [[ ${hallway[4]} == 'C' ]]; then
      move $1 $2 '_C'$3 $4 ${5:0:8}'O'${5:9} $((energy+(1+column_len-${#column_3[@]})*100))
    fi
    if [[ ${hallway[5]} == 'C' ]] && [[ ${hallway[4]} == "O" ]]; then
      move $1 $2 '_C'$3 $4 ${5:0:10}'O'${5:11} $((energy+(3+column_len-${#column_3[@]})*100))
    fi
    if [[ ${hallway[6]} == 'C' ]] && [[ ${hallway[5]} == "O" ]] && [[ ${hallway[4]} == "O" ]]; then
      move $1 $2 '_C'$3 $4 ${5:0:12}'O' $((energy+(4+column_len-${#column_3[@]})*100))
    fi
  elif [ ${#column_3[@]} -gt 0 ]; then
    if [[ ${hallway[0]} == "O" ]] && [[ ${hallway[1]} == "O" ]] && [[ ${hallway[2]} == "O" ]] \
            && [[ ${hallway[3]} == "O" ]]; then
      move $1 $2 ${3:2} $4 ${column_3[0]}${5:1} $((energy+(7+column_len-${#column_3[@]})*${energies[${column_3[0]}]}))
    fi
    if [[ ${hallway[1]} == "O" ]] && [[ ${hallway[2]} == "O" ]] && [[ ${hallway[3]} == "O" ]]; then
      move $1 $2 ${3:2} $4 ${5:0:2}${column_3[0]}${5:3} $((energy+(6+column_len-${#column_3[@]})*${energies[${column_3[0]}]}))
    fi
    if [[ ${hallway[2]} == "O" ]] && [[ ${hallway[3]} == "O" ]]; then
      move $1 $2 ${3:2} $4 ${5:0:4}${column_3[0]}${5:5} $((energy+(4+column_len-${#column_3[@]})*${energies[${column_3[0]}]}))
    fi
    if [[ ${hallway[3]} == "O" ]]; then
      move $1 $2 ${3:2} $4 ${5:0:6}${column_3[0]}${5:7} $((energy+(2+column_len-${#column_3[@]})*${energies[${column_3[0]}]}))
    fi
    if [[ ${hallway[4]} == "O" ]]; then
      move $1 $2 ${3:2} $4 ${5:0:8}${column_3[0]}${5:9} $((energy+(2+column_len-${#column_3[@]})*${energies[${column_3[0]}]}))
    fi
    if [[ ${hallway[4]} == "O" ]] && [[ ${hallway[5]} == "O" ]]; then
      move $1 $2 ${3:2} $4 ${5:0:10}${column_3[0]}${5:11} $((energy+(4+column_len-${#column_3[@]})*${energies[${column_3[0]}]}))
    fi
    if [[ ${hallway[4]} == "O" ]] && [[ ${hallway[5]} == "O" ]] && [[ ${hallway[6]} == "O" ]]; then
      move $1 $2 ${3:2} $4 ${5:0:12}${column_3[0]} $((energy+(5+column_len-${#column_3[@]})*${energies[${column_3[0]}]}))
    fi
  fi

  if ! [[ $4 == *[ABC]* ]]; then
    if [[ ${hallway[0]} == 'D' ]] && [[ ${hallway[1]} == "O" ]] && [[ ${hallway[2]} == "O" ]] \
            && [[ ${hallway[3]} == "O" ]] && [[ ${hallway[4]} == "O" ]]; then
      move $1 $2 $3 '_D'$4 'O'${5:1} $((energy+(8+column_len-${#column_4[@]})*1000))
    fi
    if [[ ${hallway[1]} == 'D' ]] && [[ ${hallway[2]} == "O" ]] && [[ ${hallway[3]} == "O" ]] \
            && [[ ${hallway[4]} == "O" ]]; then
      move $1 $2 $3 '_D'$4 ${5:0:2}'O'${5:3} $((energy+(7+column_len-${#column_4[@]})*1000))
    fi
    if [[ ${hallway[2]} == 'D' ]] && [[ ${hallway[3]} == "O" ]] && [[ ${hallway[4]} == "O" ]]; then
      move $1 $2 $3 '_D'$4 ${5:0:4}'O'${5:5} $((energy+(5+column_len-${#column_4[@]})*1000))
    fi
    if [[ ${hallway[3]} == 'D' ]] && [[ ${hallway[4]} == "O" ]]; then
      move $1 $2 $3 '_D'$4 ${5:0:6}'O'${5:7} $((energy+(3+column_len-${#column_4[@]})*1000))
    fi
    if [[ ${hallway[4]} == 'D' ]]; then
      move $1 $2 $3 '_D'$4 ${5:0:8}'O'${5:9} $((energy+(1+column_len-${#column_4[@]})*1000))
    fi
    if [[ ${hallway[5]} == 'D' ]]; then
      move $1 $2 $3 '_D'$4 ${5:0:10}'O'${5:11} $((energy+(1+column_len-${#column_4[@]})*1000))
    fi
    if [[ ${hallway[6]} == 'D' ]] && [[ ${hallway[5]} == "O" ]]; then
      move $1 $2 $3 '_D'$4 ${5:0:12}'O' $((energy+(2+column_len-${#column_4[@]})*1000))
    fi
  elif [ ${#column_4[@]} -gt 0 ]; then
    if [[ ${hallway[0]} == "O" ]] && [[ ${hallway[1]} == "O" ]] && [[ ${hallway[2]} == "O" ]] \
            && [[ ${hallway[3]} == "O" ]] && [[ ${hallway[4]} == "O" ]]; then
      move $1 $2 $3 ${4:2} ${column_4[0]}${5:1} $((energy+(9+column_len-${#column_4[@]})*${energies[${column_4[0]}]}))
    fi
    if [[ ${hallway[1]} == "O" ]] && [[ ${hallway[2]} == "O" ]] && [[ ${hallway[3]} == "O" ]] \
            && [[ ${hallway[4]} == "O" ]]; then
      move $1 $2 $3 ${4:2} ${5:0:2}${column_4[0]}${5:3} $((energy+(8+column_len-${#column_4[@]})*${energies[${column_4[0]}]}))
    fi
    if [[ ${hallway[2]} == "O" ]] && [[ ${hallway[3]} == "O" ]] && [[ ${hallway[4]} == "O" ]]; then
      move $1 $2 $3 ${4:2} ${5:0:4}${column_4[0]}${5:5} $((energy+(6+column_len-${#column_4[@]})*${energies[${column_4[0]}]}))
    fi
    if [[ ${hallway[3]} == "O" ]] && [[ ${hallway[4]} == "O" ]]; then
      move $1 $2 $3 ${4:2} ${5:0:6}${column_4[0]}${5:7} $((energy+(4+column_len-${#column_4[@]})*${energies[${column_4[0]}]}))
    fi
    if [[ ${hallway[4]} == "O" ]]; then
      move $1 $2 $3 ${4:2} ${5:0:8}${column_4[0]}${5:9} $((energy+(2+column_len-${#column_4[@]})*${energies[${column_4[0]}]}))
    fi
    if [[ ${hallway[5]} == "O" ]]; then
      move $1 $2 $3 ${4:2} ${5:0:10}${column_4[0]}${5:11} $((energy+(2+column_len-${#column_4[@]})*${energies[${column_4[0]}]}))
    fi
    if [[ ${hallway[5]} == "O" ]] && [[ ${hallway[6]} == "O" ]]; then
      move $1 $2 $3 ${4:2} ${5:0:12}${column_4[0]} $((energy+(3+column_len-${#column_4[@]})*${energies[${column_4[0]}]}))
    fi
  fi
}

column_1_str=${column_1[@]}
column_2_str=${column_2[@]}
column_3_str=${column_3[@]}
column_4_str=${column_4[@]}
move _${column_1_str// /_}_ _${column_2_str// /_}_ _${column_3_str// /_}_ _${column_4_str// /_}_ "O_O_O_O_O_O_O" 0
echo $min_energy