「結城浩のディーペスト問題」の解答に使用したコードを公開します。

はじめに

おかげさまで評価5をいただきました。
というわけで、解答に使用したコードを公開します。(公開に際し一部修正しています。)
今後ともシェル芸に精進してゆきます。

問題はこちら

星間飛行ルートを作ろう！(受け付け終了)
https://codeiq.jp/ace/yuki_hiroshi/q411

コードの説明

1. シェル芸を磨くため、あえてシェルスクリプト(Bash)を使用する。→シェル芸については、ここをチェック！
2. 経路は幅優先で探索する。
3. シェルスクリプトでも再帰呼び出しぐらい出来るよね。→ローカル変数と自前のスタックで対応。
4. API呼び出しの結果は保存し、同じAPIは何度も呼び出さない。→サーバーに優しい。
5. 新しいルートが以前に見つけたルートより短く無ければそれ以上探索しない。→時間の節約。
6. 意地悪なinfty星(通称Black hole)は華麗にスルー。

以下コード

bash

# !/bin/bash
#
# Get a route to deepest star.
#

# API URL
api_url="http://133.242.134.37/deepest.cgi"

# API call counter
api_count=0

# Get shortest route if this flag is 1.
# Get the route found in the first if this flag is not 1.
shortest_route=1

# Stack pointer and a variable.
sp=0
stack_route=()

# Get routes from here to each star.
# Input : here, goal, route[]
# Output: routes[], nexts[], api_count
# Status: 1 - Found goal
#
get_routes() {
  local -i here=$1
  local -i next
  #echo "DEBUG: get_routes: here=$here, goal=$goal, route=${route[@]}."

  # If here passed.
  if [[ -n "${routes[$here]}" ]]; then

    # Search stopped if the current route is longer than the previous route.
    r=(${routes[$here]})
    [[ ${#route[@]} -ge ${#r[@]} ]] && return 0
  fi

  # Set a route to return variable.
  routes[$here]=${route[@]}

  # Terminate recursive call if here is the goal.
  (( $here == $goal )) && return 1

  # If did not get next paths.
  if [[ -z "${nexts[$here]}" ]]; then

    # Skip a black hole. :)
    next=`curl -s "$api_url?id=$here&nth=9999999999"|tr -d '\n'`
    ((++api_count))
    if (( $next != 0 )); then
      echo "DEBUG: Skipped $here."
      return 0
    fi

    # Get next paths.
    for (( i=0; ; ++i ))
    do
      # Get a next path.
      echo -n "DEBUG: curl -s \"$api_url?id=$here&nth=$i\""
      next=`curl -s "$api_url?id=$here&nth=$i"|tr -d '\n'`
      echo " -> $next"
      ((++api_count))
      (( $next == 0 )) && break
  
      # Set next paths to return variable.
      nexts[$here]="${nexts[$here]} $next"
    done
  fi

  # Set a route to return variable.
  routes[$here]=${route[@]}

  # Search next paths.
  for next in ${nexts[$here]}
  do
    # Push a variable to stack.
    stack_route[$sp]=${route[@]}
    ((++sp))

    # Recursive call get_routes.
    route=(${route[@]} $next)
    get_routes $next; rc=$?

    # Pop a variable from stack.
    ((--sp))
    route=(${stack_route[$sp]})

    # If the goal found.
    if (( $rc == 1 )); then
      # Set next path that only goal to return variable.
      nexts[$here]=$next

      # Search Stopped if this flag is not 1.
      (( $shortest_route != 1 )) && return 1

      break
    fi
  done

  return 0
}

# Get a route from here to goal star.
# Input : here, goal
# Output: route_goal
# Status: None
#
get_route() {
  here=$1
  goal=$2
  echo "DEBUG: get_route: here=$here, goal=$goal."

  route=()
  routes=()
  nexts=()
  get_routes $here
  route_goal=${routes[$goal]}
}

# main
#
star_start=5426528869786
star_deep=4363616111476
star_deeper=5092488161056
star_deepest=8838746292440

# Start to Deep.
get_route $star_start $star_deep
route_deep=$route_goal
echo "Start to Deep: $route_deep"
echo "DEBUG: api_count=$api_count."

# Deep to Deeper.
get_route $star_deep $star_deeper
route_deeper=$route_goal
echo "Deep to Deeper: $route_deeper"
echo "DEBUG: api_count=$api_count."

# Deeper to Deepest.
get_route $star_deeper $star_deepest
route_deepest=$route_goal
echo "Deeper to Deepest: $route_deepest"
echo "DEBUG: api_count=$api_count."

# Answer
echo -n "Answer: "
echo "$star_start $route_deep $route_deeper $route_deepest"|tr ' ' ','

exit 0