text:
States and Capitals
Given a string as input, output the US state whose capital it is if it is a state capital, the capital of the state if it is a state, or Arstotzka if it is neither.
Examples:
Austin -> Texas
Alaska -> Juneau
The Nineteenth Byte -> Arstotzka

All the capitals and their respective states:
Baton Rouge, Louisiana
Indianapolis, Indiana
Columbus, Ohio
Montgomery, Alabama
Helena, Montana
Denver, Colorado
Boise, Idaho
Austin, Texas
Boston, Massachusetts
Albany, New York
Tallahassee, Florida
Santa Fe, New Mexico
Nashville, Tennessee
Trenton, New Jersey
Jefferson, Missouri
Richmond, Virginia
Pierre, South Dakota
Harrisburg, Pennsylvania
Augusta, Maine
Providence, Rhode Island
Dover, Delaware
Concord, New Hampshire
Montpelier, Vermont
Hartford, Connecticut
Topeka, Kansas
Saint Paul, Minnesota
Juneau, Alaska
Lincoln, Nebraska
Raleigh, North Carolina
Madison, Wisconsin
Olympia, Washington
Phoenix, Arizona
Lansing, Michigan
Honolulu, Hawaii
Jackson, Mississippi
Springfield, Illinois
Columbia, South Carolina
Annapolis, Maryland
Cheyenne, Wyoming
Salt Lake City, Utah
Atlanta, Georgia
Bismarck, North Dakota
Frankfort, Kentucky
Salem, Oregon
Little Rock, Arkansas
Des Moines, Iowa
Sacramento, California
Oklahoma City, Oklahoma
Charleston, West Virginia
Carson City, Nevada

Rules

No built-ins or libraries/modules that provide a mapping from states to capitals or capitals to states, or lists of capitals and/or states (for example, Mathematica's CityData built-in)
Standard loopholes apply
This is code-golf, so shortest answer in bytes wins!

Leaderboard
The Stack Snippet at the bottom of this post generates the leaderboard from the answers a) as a list of shortest solution per language and b) as an overall leaderboard.
To make sure that your answer shows up, please start your answer with a headline, using the following Markdown template:
## Language Name, N bytes

where N is the size of your submission. If you improve your score, you can keep old scores in the headline, by striking them through. For instance:
## Ruby, <s>104</s> <s>101</s> 96 bytes

If there you want to include multiple numbers in your header (e.g. because your score is the sum of two files or you want to list interpreter flag penalties separately), make sure that the actual score is the last number in the header:
## Perl, 43 + 2 (-p flag) = 45 bytes

You can also make the language name a link which will then show up in the snippet:
## [><>](http://esolangs.org/wiki/Fish), 121 bytes

 <link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b">

Shortest Solution by Language

Language	User	Score

Leaderboard

	Author	Language	Size

{{PLACE}}	{{NAME}}	{{LANGUAGE}}	{{SIZE}}	Link

{{LANGUAGE}}	{{NAME}}	{{SIZE}}	Link

Related

Please provide a full list of states and their capitals in their proper spelling in plain text.

any specification about case? also, should "United States" return "Washington, D.C"?

if the input is Arstotzka, should it be treated like any other junk input?

@sysreq The spelling and case must exactly match the list provided. As "United States" is neither a US state nor a US state capital, it should return "Arstotzka".

@sysreq "Arstotzka" is neither a US state nor a US state capital, so it should return "Arstotzka".

Would you consider allowing us to subtract the length of the dictionary (in whichever format we choose to encode it) from our score? That seems to happen a lot in kolmogorov-complexity challenges...

@sysreq That doesn't sound like a very good idea to me.

Waiting for a mathematica builtin answer

@FarazMasroor Builtins are banned

Your example outputs "Anchorage" for Alaska, but the capital is Juneau.  You should probably fix that.

@DarrelHoffman Thanks, that one slipped by me. I blame Fallout.

Too late now, I guess, since it would invalidate existing answers, but the capital of Missouri is Jefferson City, not Jefferson.

@msh210 - I believe that list comes from the Animaniacs song? (Based on the somewhat random order)  They probably shortened it to fit the meter.  A small error on their part I suppose; certainly it's more accurate than the countries of the world song...

@msh210 I pulled the list from this related question. Blame Timmy.

Out of curiosity, why Arstotzka?

@cairdcoinheringaahing https://en.wikipedia.org/wiki/Papers,_Please

Pyth, 597 596 590
00000000: 40 4a 63 72 58 73 40 4c 2b 62 47 6a 43 22 05 77 c6  @JcrXs@L+bGjC".w.
00000011: fa 94 29 be 77 9b 88 35 9b e0 86 05 86 8a d3 cd 53  ..).w..5........S
00000022: e6 97 c1 20 f4 bd b5 76 f3 f7 14 ab 4b fa 8e 4d 2c  ... ...v....K..M,
00000033: be 71 4d 13 ca 9c 67 3e 35 21 76 6b 74 f8 88 8b c1  .qM...g>5!vkt....
00000044: bc 2a ab da 6b ba 1f 2b a3 2c 12 bc d1 b8 c3 b6 7c  .*..k..+.,......|
00000055: b0 4d 0f 11 a2 dc 15 a2 94 45 39 1c 20 12 08 03 a3  .M.......E9. ....
00000066: 5c 71 d9 11 1c 56 f5 c2 2d cb 63 64 b3 c0 d8 e7 e3  \q...V..-.cd.....
00000077: 9b 82 28 85 57 2b e4 28 ea 8f 17 02 1d a8 8f f3 0e  ..(.W+.(.........
00000088: 31 5f 8e c4 2b b3 8f 7e b2 64 fc d2 99 dc 9d 98 e5  1_..+..~.d.......
00000099: 3a b3 8b 59 52 5f 63 5a ae c9 3d 8a 7a b6 a2 0a 8a  :..YR_cZ..=.z....
000000aa: 2f 4c 43 78 fa 56 9b 07 ce 21 3a 2f 50 5e d3 f3 a9  /LCx.V...!:/P^...
000000bb: 90 ad 21 85 75 cd 9e 07 29 a3 3d b7 c2 cd f4 b8 5f  ..!.u...).=....._
000000cc: 60 b4 72 cd 47 93 17 14 28 3e da b1 65 90 ec 5f 35  `.r.G...(>..e.._5
000000dd: 4d c6 0e b1 66 40 af 8a 67 95 47 f8 8f fd 38 66 c8  M...f@..g.G...8f.
000000ee: df fd 51 6c 5f 06 06 35 a1 77 ae 93 84 73 33 63 be  ..Ql_..5.w...s3c.
000000ff: 98 3e 1c f3 43 de ca 0a 13 6d e9 64 52 96 b8 41 e8  .>..C....m.dR..A.
00000110: db 23 a6 01 c5 60 38 db 63 9c 2a d9 5d 03 fc 38 c8  .#...`8.c.*.]..8.
00000121: 94 1e 2f 70 8e 4d 0f 93 44 4a 6c 57 e8 af cc e7 e2  ../p.M..DJlW.....
00000132: 70 82 84 a3 06 d3 2a 4f cd 8b b6 68 a5 80 98 9e 49  p.....*O...h....I
00000143: 4f bc fd 91 20 55 a6 66 12 1d c0 49 f2 3e 9e ef 5d  O... U.f...I.>..]
00000154: 89 bc b3 30 ef dd cc ca 93 70 27 2c 14 03 6a 53 32  ...0.....p',..jS2
00000165: ef af e1 b5 d3 5a cc 3e fd 1d 78 a5 b3 06 ae 67 58  .....Z.>..x....gX
00000176: ec e4 7a 99 16 f5 da a7 1e 51 0a 94 fc cd e9 e8 fe  ..z......Q.......
00000187: 5a d1 bc 0f bb 24 9d 45 9a ac 97 58 a7 9b ea f0 77  Z....$.E...X....w
00000198: 89 e8 a1 fa e7 83 2c b9 ea 5c a7 f1 b3 76 ba 97 fb  ......,..\...v...
000001a9: 41 b7 74 9a 09 2d 96 97 73 80 13 17 7a fe 15 5f c6  A.t..-..s...z.._.
000001ba: cf 89 3d 7f df 54 cd 16 fe 8a ea d7 0a 91 84 54 61  ..=..T.........Ta
000001cb: 4f 03 87 a6 d2 1c c8 a9 b8 0f 52 2e 39 13 2e 48 8b  O.........R.9..H.
000001dc: 04 ce 2d 35 5e 02 96 63 11 a7 f8 75 6d 8a e2 13 e2  ..-5^..c...um....
000001ed: d6 1b f9 43 07 3e 99 29 a9 69 7f f5 6a 72 15 7b 92  ...C.>.).i..jr.{.
000001fe: 5b 26 cb 74 48 1b c0 fc fb 64 45 05 2d 37 d6 21 6a  [&.tH....dE.-7.!j
0000020f: d9 83 88 13 fb e7 e8 f2 17 c7 54 de 48 f6 23 1e bf  ..........T.H.#..
00000220: b0 34 f5 4f 63 ce 46 40 a9 16 e7 4a 60 71 ce a3 d3  .4.Oc.F@...J`q...
00000231: 6a 15 4c 8b 52 d6 3f cb 53 dd 96 97 10 f6 e5 22 32  j.L.R.?.S......"2
00000242: 37 5c 71 64 33 62 5f 68 68 78 4a 7a                 7\qd3b_hhxJz

The above hexdump can be reversed with xxd -r -c 17. Try it online in the Pyth Compiler.
Idea
We encode the required information as follows:
columbia
columbus
frankfort
⋮
kentucky
ohio
southqcarolina
arstotzka

All the names have been cast to lowercase, spaces have been replaced with q's, and names are separated by linefeeds.
All capitals are listed first (in an order that managed to minimize the byte count). Then the corresponding states are listed in reverse order. Finally, Arstotzka is appended.
This way, the capital/state at index i corresponds to the state/capital at index -(x+2). Also, an invalid input will either have index 100 (Arstotzka) or -1 (not found), and -(100+2) ≡ -1 ≡ -(-1+2) mod 101. This layout prevents Arstotzka from being a special case, without prepending or appending anything to the list.
To compress the information, we find each character's index in "\nabc...xyz" and convert the result from base 27 to base 256.
Decoding is straightforward: we go back from base 256 to base 27, retrieve the corresponding elements from "\nabc…xyz", replace q's with spaces, and capitalize the first letter of each resulting word.
Code
@JcrXs@L+bGjC"…"27\qd3b_hhxJz

            C"…"               Convert the 562-character from base 256 to integer.
           j    27             Convert the result from integer to base 27.
        +bG                    Compute "\n" + "abc…xyz".
      @L                       Retrieve the corresponding characters.
     s                         Flatten the resulting array of strings.
    X             \qd          Replace each q with a space.
   r                 3         Apply title casing.
 Jc                   b        Split at linefeeds and save in J.
                          xJz  Compute the index of the input (z) in J.
                       _hh     Increment twice and negate.
@                              Retrieve the element at that index from J.

Python3, 997 bytes
i=input()
s="Baton Rouge,Louisiana,Indianapolis,Indiana,Columbus,Ohio,Montgomery,Alabama,Helena,Montana,Denver,Colorado,Boise,Idaho,Austin,Texas,Boston,Massachusetts,Albany,New York,Tallahassee,Florida,Santa Fe,New Mexico,Nashville,Tennessee,Trenton,New Jersey,Jefferson,Missouri,Richmond,Virginia,Pierre,South Dakota,Harrisburg,Pennsylvania,Augusta,Maine,Providence,Rhode Island,Dover,Delaware,Concord,New Hampshire,Montpelier,Vermont,Hartford,Connecticut,Topeka,Kansas,Saint Paul,Minnesota,Juneau,Alaska,Lincoln,Nebraska,Raleigh,North Carolina,Madison,Wisconsin,Olympia,Washington,Phoenix,Arizona,Lansing,Michigan,Honolulu,Hawaii,Jackson,Mississippi,Springfield,Illinois,Columbia,South Carolina,Annapolis,Maryland,Cheyenne,Wyoming,Salt Lake City,Utah,Atlanta,Georgia,Bismarck,North Dakota,Frankfort,Kentucky,Salem,Oregon,Little Rock,Arkansas,Des Moines,Iowa,Sacramento,California,Oklahoma City,Oklahoma,Charleston,West Virginia,Carson City,Nevada,Arstotzka".split(",")+[i]
print(s[1^s.index(i)])

I can not be bothered to do the base-conversion or binary packing that the winning version will undoubtly do, but I do want to post this to show a really cool trick.
XOR'ing a number by 1 is equivalent to adding 1 if the number is even, or subtracting 1 if the number is odd. You can make really easy and golfy bi-directional maps using this trick.

Same trick as mine, different language. You beat me by 1 minute!

aah, this is what I wanted to do with mine but I had no idea how. nice golfing, though!

If you switch to 2.7 you can eliminate parens in print() and everything else should still work

@sysreq Nope, then you need raw_input.

You could just require the input have quotations (when using raw_input). @orlp

I was wondering how to add or subtract based on the parity.  That XORing is quite ingenious.

You can use 0 for separating the countries and capitals. For example "...Nevada0Arstotzka".split(0)+[i] This saves two bytes.

@ΚριτικσιΛίθος That is a TypeError.

@ΚριτικσιΛίθος I think you meant '0'. That doesn't save any bytes. In addition, the split method for strings requires a string as input.

@rayryeng I was referring to http://codegolf.stackexchange.com/a/11699/41805

@ΚριτικσιΛίθος The main page says... "Tips for golfing in JavaScript".  This isn't JavaScript.  You get a TypeError as @orlp stated.  Try it yourself: http://ideone.com/IIYVUG

@rayryeng It says "Tips for JavaScript" for me. If you still can't access it, then search for "Tips for golfing in JavaScript" and scroll down to the second-ish answer.

I updated my comment.  It doesn't work.  Try it yourself online: http://ideone.com/IIYVUG - You get a TypeError.  This is a Python answer, not JavaScript.  Only by inserting quotations in between the 0 will it work.

@rayryeng I am terribly sorry for getting confused with JS and Python.

@ΚριτικσιΛίθος It's fine.  Just wanted to make sure that what I know of Python isn't being contradicted :)  FWIW, that JS trick is quite useful.

And I thought add 50 modulo 100 to a list of states and state capitals was math intensive. :3

CJam, 625 609 603 599 bytes
00000000: 22 05 77 c6 fa 94 29 be 77 9b 88 35 9b e0 86 05 86  ".w...).w..5.....
00000011: 8a d3 cd 53 e6 97 c1 20 f4 bd b5 76 f3 f7 14 ab 4b  ...S... ...v....K
00000022: fa 8e 4d 2c be 71 4d 13 ca 9c 67 3e 35 21 76 6b 74  ..M,.qM...g>5!vkt
00000033: f8 88 8b c1 bc 2a ab da 6b ba 1f 2b a3 2c 12 bc d1  .....*..k..+.,...
00000044: b8 c3 b6 7c b0 4d 0f 11 a2 dc 15 a2 94 45 39 1c 20  ...|.M.......E9.
00000055: 12 08 03 a3 5c 71 d9 11 1c 56 f5 c2 2d cb 63 64 b3  ....\q...V..-.cd.
00000066: c0 d8 e7 e3 9b 82 28 85 57 2b e4 28 ea 8f 17 02 1d  ......(.W+.(.....
00000077: a8 8f f3 0e 31 5f 8e c4 2b b3 8f 7e b2 64 fc d2 99  ....1_..+..~.d...
00000088: dc 9d 98 e5 3a b3 8b 59 52 5f 63 5a ae c9 3d 8a 7a  ....:..YR_cZ..=.z
00000099: b6 a2 0a 8a 2f 4c 43 78 fa 56 9b 07 ce 21 3a 2f 50  ..../LCx.V...!:/P
000000aa: 5e d3 f3 a9 90 ad 21 85 75 cd 9e 07 29 a3 3d b7 c2  ^.....!.u...).=..
000000bb: cd f4 b8 5f 60 b4 72 cd 47 93 17 14 28 3e da b1 65  ..._`.r.G...(>..e
000000cc: 90 ec 5f 35 4d c6 0e b1 66 40 af 8a 67 95 47 f8 8f  .._5M...f@..g.G..
000000dd: fd 38 66 c8 df fd 51 6c 5f 06 06 35 a1 77 ae 93 84  .8f...Ql_..5.w...
000000ee: 73 33 63 be 98 3e 1c f3 43 de ca 0a 13 6d e9 64 52  s3c..>..C....m.dR
000000ff: 96 b8 41 e8 db 23 a6 01 c5 60 38 db 63 9c 2a d9 5d  ..A..#...`8.c.*.]
00000110: 03 fc 38 c8 94 1e 2f 70 8e 4d 0f 93 44 4a 6c 57 e8  ..8.../p.M..DJlW.
00000121: af cc e7 e2 70 82 84 a3 06 d3 2a 4f cd 8b b6 68 a5  ....p.....*O...h.
00000132: 80 98 9e 49 4f bc fd 91 20 55 a6 66 12 1d c0 49 f2  ...IO... U.f...I.
00000143: 3e 9e ef 5d 89 bc b3 30 ef dd cc ca 93 70 27 2c 14  >..]...0.....p',.
00000154: 03 6a 53 32 ef af e1 b5 d3 5a cc 3e fd 1d 78 a5 b3  .jS2.....Z.>..x..
00000165: 06 ae 67 58 ec e4 7a 99 16 f5 da a7 1e 51 0a 94 fc  ..gX..z......Q...
00000176: cd e9 e8 fe 5a d1 bc 0f bb 24 9d 45 9a ac 97 58 a7  ....Z....$.E...X.
00000187: 9b ea f0 77 89 e8 a1 fa e7 83 2c b9 ea 5c a7 f1 b3  ...w......,..\...
00000198: 76 ba 97 fb 41 b7 74 9a 09 2d 96 97 73 80 13 17 7a  v...A.t..-..s...z
000001a9: fe 15 5f c6 cf 89 3d 7f df 54 cd 16 fe 8a ea d7 0a  .._...=..T.......
000001ba: 91 84 54 61 4f 03 87 a6 d2 1c c8 a9 b8 0f 52 2e 39  ..TaO.........R.9
000001cb: 13 2e 48 8b 04 ce 2d 35 5e 02 96 63 11 a7 f8 75 6d  ..H...-5^..c...um
000001dc: 8a e2 13 e2 d6 1b f9 43 07 3e 99 29 a9 69 7f f5 6a  .......C.>.).i..j
000001ed: 72 15 7b 92 5b 26 cb 74 48 1b c0 fc fb 64 45 05 2d  r.{.[&.tH....dE.-
000001fe: 37 d6 21 6a d9 83 88 13 fb e7 e8 f2 17 c7 54 de 48  7.!j..........T.H
0000020f: f6 23 1e bf b0 34 f5 4f 63 ce 46 40 a9 16 e7 4a 60  .#...4.Oc.F@...J`
00000220: 71 ce a3 d3 6a 15 4c 8b 52 d6 3f cb 53 dd 96 97 10  q...j.L.R.?.S....
00000231: f6 e5 22 32 35 36 62 32 37 62 27 60 66 2b 27 60 2f  .."256b27b'`f+'`/
00000242: 7b 27 71 2f 33 32 61 66 2e 5e 53 2a 7d 25 5f 71 61  {'q/32af.^S*}%_qa
00000253: 23 7e 28 3d                                         #~(=

The above hexdump can be reversed with xxd -r -c 17. Try it online in the CJam interpreter.
Idea
We encode the required information as follows:
columbia`columbus`frankfort`olympia`desqmoines`jefferson`springfield`carsonqcity`topeka`sacramento`littleqrock`saltqlakeqcity`boston`trenton`batonqrouge`indianapolis`madison`charleston`austin`denver`hartford`santaqfe`atlanta`augusta`boise`oklahomaqcity`dover`helena`tallahassee`richmond`lansing`honolulu`saintqpaul`salem`providence`raleigh`cheyenne`nashville`concord`albany`bismarck`phoenix`jackson`montpelier`montgomery`harrisburg`juneau`pierre`annapolis`lincoln`nebraska`maryland`southqdakota`alaska`pennsylvania`alabama`vermont`mississippi`arizona`northqdakota`newqyork`newqhampshire`tennessee`wyoming`northqcarolina`rhodeqisland`oregon`minnesota`hawaii`michigan`virginia`florida`montana`delaware`oklahoma`idaho`maine`georgia`newqmexico`connecticut`colorado`texas`westqvirginia`wisconsin`indiana`louisiana`newqjersey`massachusetts`utah`arkansas`california`kansas`nevada`illinois`missouri`iowa`washington`kentucky`ohio`southqcarolina`arstotzka

All the names have been cast to lowercase, spaces have been replaced with q's, and names are separated by backticks.
All capitals are listed first (in an order that managed to minimize the byte count). Then the corresponding states are listed in reverse order. Finally, Arstotzka is appended.
This way, the capital/state at index i corresponds to the state/capital at index -(x+2). Also, an invalid input will either have index 100 (Arstotzka) or -1 (not found), and -(100+2) ≡ -1 ≡ -(-1+2) mod 101. This layout prevents Arstotzka from being a special case, without prepending or appending anything to the list.
To compress the information, we subtract 97 (code point of `) from each character in the string and convert the result from base 27 to base 256.
Decoding is straightforward: we go back from base 256 to base 27, add the resulting base-27 digits to the backtick character, replace q's with spaces, and capitalize the first letter of each resulting word.
Code
"…"          e# Push a string of 562 characters.
256b27b      e# Convert it from base 256 to base 27.
'`f+         e# Add each base-27 digit to the character '`'.
'`/          e# Split at occurrences of '`'.
{            e#   For each resulting chunk:
  'q/        e#   Split at occurrences of 'q'.
  32a        e#   Push [32].
  f.^        e#   For each chunk, perform vectorized XOR with 32.
             e#   This capitalizes the first character of the chunk.
  S*         e#   Join the chunks, separating by spaces.
}%           e#
_            e# Push a copy of the resulting array.
qa           e# Read all user input and wrap it in an array.
#            e# Find its index (i) in the copy.
~(           e# Apply bitwise NOT and decrements to calculate
             e# ~i - 1 = -(i + 1) - 1 = -(i + 2).
=            e# Retrieve element at the corresponding index.

Which encoding is this?

ISO 8559-1, so each char is one byte.

It is amazing what you can do with CJam...

I think this is the largest CJam program I've seen.

JavaScript (ES6), 821 806 bytes
Uses Base64 decode to compress strings. Live demo
s=>(S=(r=x=>btoa(x).replace(/\+/g," ").split`/`)`.¢²&§kò'v&§kó¡À¦Ú¯Ì¢{Z¯Â¢Z+iÚ?!Ö¡£ôÞÅ«?1«,iÈn±ëm³ó^Ãæ(®OÅâu¯Í{{£ôÞw¬±ç¿5ì>%êì{/ÌË(º¸¿V*àxý*.¶jJ-kóÞ{2ö§¯Ìj)Þýhuï²V§wðÞ¬ïÍ{jjl*ÞýW«íü*'ç-Ëü¦§±«?2)çzÊ-kð%jÉü×«$kóh®Ø~    ªè)Úýh¬rìÖjÈbhð+:'kó"r jÇk¢ó"²È¬²*iò%)èÏÒ¢ëaø&«¢X§kó¯)ZßÖÊ¢Ôµ¨ê+&¿6íàÚZü§§¶ç$Ëó«z
'ü
äj{³ò(Á¯ÂjX¢¹âkó¤¨h¯ÖzË~V*àxü×¯iÖ¿`,C=r`«hähº¿"wbjv©¢X¬ü*%ºfî³ó(Ø(êòüw¥zv¿
éïz¿Á¢+ü¬¶)ÿ-¢À¶§ËôÚV¡jË{ôÖ¾ïÍjÈoY^ý:ÞÚ'ü}êì¢ÑÈf¢w>'«ïÇjºâ±»«ð.ë-kóë¢øzwü:/z¿Â¢w(ßÌ¢{izX¯ñÚ®×èßÓ¢¤kô{~=«¥ü§y«¿.)Ü¢YÿE©^1§b²ÿ:\\¦¦&¿>,-©ìx?èénüÊ'ý*kxé]ü*%ºfâkð'ªh+?
²zyÞý&¥·âÚïÜ¿ÙZÖ¿+&j·$üZÚGè®ßÒjW¦ü¸¶W¾F$ü7¬øÊ"ë?I§+jg§¶ÎV¡¢f¾
+rü(Z®W¬¶ÿ  ªì¢Ü¿`,S[C.indexOf(s)]||C[S.indexOf(s)]||"Arstotzka")

Here is a hexdump; use xxd -r filename to reverse.
00000000: 733d 3e28 533d 2872 3d78 3d3e 6274 6f61  s=>(S=(r=x=>btoa
00000010: 2878 292e 7265 706c 6163 6528 2f5c 2b2f  (x).replace(/\+/
00000020: 672c 2220 2229 2e73 706c 6974 602f 6029  g," ").split`/`)
00000030: 602e 3fa2 b226 a76b f227 7626 a76b f3a1  `.?..&.k.'v&.k..
00000040: 3f8f c03f a6da 3faf cca2 7b5a 9daf c2a2  ?..?..?...{Z....
00000050: 5a2b 69da 3f21 d6a1 a3f4 dec5 ab3f 31ab  Z+i.?!.......?1.
00000060: 2c69 c86e b1eb 6db3 f35e c3e6 28ae 4fc5  ,i.n..m..^..(.O.
00000070: 3f3f e275 afcd 7b0f 3f7b 183f a3f4 de3f  ??.u..{.?{.?...?
00000080: 77ac b1e7 bf35 ec3e 25ea ec7b 2fcc 3fcb  w....5.>%..{/.?.
00000090: 28ba b8bf 562a e03f 783f fd2a 2eb6 1f3f  (...V*.?x?.*...?
000000a0: 6a4a 2d6b f3de 3f7b 323f f6a7 3faf cc6a  jJ-k..?{2?..?..j
000000b0: 29de fd18 6875 ef3f b256 a777 f0de 3fac  )...hu.?.V.w..?.
000000c0: 1aad efcd 7b0f 3f6a 6a6c 3f2a defd 57ab  ....{.?jjl?*..W.
000000d0: 3f3f edfc 2a27 9de7 2d3f cbad fca6 a7b1  ??..*'..-?......
000000e0: ab3f 3229 e77a ca2d 6bf0 256a c91a fcd7  .?2).z.-k.%j....
000000f0: 3fad ab24 6bf3 68ae d87e 09aa e83f 29da  ?..$k.h..~...?).
00000100: fd68 ac72 3fec 3f7f d66a c862 3f0b 683f  .h.r?.?..j.b?.h?
00000110: f02b 3f3a 276b f322 7218 206a 7fc7 6b06  .+?:'k."r. j..k.
00000120: a23f f322 b2c8 acb2 2a69 3ff2 253f 29e8  .?."....*i?.%?).
00000130: 3fcf d2a2 eb61 f826 aba2 58a7 6bf3 1aaf  ?....a.&..X.k...
00000140: 295a 9ddf d6ca 3fa2 3f0f d4b5 a87f 19ea  )Z....?.?.......
00000150: 2b3f 26bf 363f ed3f e0da 3f3f 5afc a7a7  +?&.6?.?..??Z...
00000160: b6e7 24cb f3ab 7a0a 27fc 0ae4 6a7b 1ab3  ..$...z.'...j{..
00000170: f228 c1af c26a 583f a2b9 e26b f3a4 3fa8  .(...jX?...k..?.
00000180: 683f afd6 7acb 7e56 2ae0 3f78 3ffc d7af  h?..z.~V*.?x?...
00000190: 69d6 bf60 2c43 3d72 6005 ab68 3fe4 68ba  i..`,C=r`..h?.h.
000001a0: 07bf 2277 626a 76a9 a258 acfc 2a25 ba66  .."wbjv..X..*%.f
000001b0: eeb3 f328 3fd8 283f eaf2 fc77 a57a 76bf  ...(?.(?...w.zv.
000001c0: 0ae9 ef7a bfc1 a22b 1efc 0bac b629 ff06  ...z...+.....)..
000001d0: 3f2d a27f c03f b6a7 cbf4 da3f 56a1 6acb  ?-...?.....?V.j.
000001e0: 1e7b f43f 3fd6 be15 efcd 6ac8 6f3f 595e  .{.??.....j.o?Y^
000001f0: fd3a de3f da27 fc3f 3f7d eaec a27f d13f  .:.?.'.??}.....?
00000200: c866 a277 7f3e 27ab adef c76a bae2 b1bb  .f.w.>'....j....
00000210: ab3f f02e 3feb 2d6b f3eb a2f8 9d7a 771e  .?..?.-k.....zw.
00000220: fc3a 2f7a bfc2 a277 28ad dfcc a27b 697a  .:/z...w(....{iz
00000230: 583f aff1 daae d7e8 addf d3a2 3fa4 6bf4  X?..........?.k.
00000240: 3f3f 7b7e 3dab a5fc 3fa7 79ab bf2e 29dc  ??{~=...?.y...).
00000250: a259 ff45 a95e 3f08 7f31 a762 b23f ff3a  .Y.E.^?..1.b.?.:
00000260: 5c5c a6a6 26bf 3e1a 1e3f 2c7f 2da9 ec3f  \\..&.>..?,.-..?
00000270: 783f 1e3f e83f e96e fc3f 3f3f ca27 fd2a  x?.?.?.n.???.'.*
00000280: 6b3f 781f 3fe9 5dfc 2a25 ba66 e26b f027  k?x.?.].*%.f.k.'
00000290: 9daa 683f 2b3f 0a17 b27a 79de fd26 a5b7  ..h?+?...zy..&..
000002a0: e2da 3fef 3f3f dcbf 02d9 5a3f d6bf 062b  ..?.??....Z?...+
000002b0: 266a b724 fc5a da3f 47e8 aedf d26a 57a6  &j.$.Z.?G....jW.
000002c0: fcb8 adb6 57be 463f 24fc 37ac f8ca 229d  ....W.F?$.7...".
000002d0: eb3f 49a7 2b6a 67a7 b68f ce3f 56a1 a266  .?I.+jg....?V..f
000002e0: be0a 2b72 fc28 5aae 57ac b63f ff09 aaec  ..+r.(Z.W..?....
000002f0: a27f 3f3f dcbf 602c 535b 432e 696e 6465  ..??..`,S[C.inde
00000300: 784f 6628 7329 5d7c 7c43 5b53 2e69 6e64  xOf(s)]||C[S.ind
00000310: 6578 4f66 2873 295d 7c7c 2241 7273 746f  exOf(s)]||"Arsto
00000320: 747a 6b61 2229                           tzka")

Is the r= necessary?

@CᴏɴᴏʀO'Bʀɪᴇɴ Yep, it's reused to decode both the state and capital strings.

PHP, 1272 1239 bytes
Make sure you have enabled short_open_tag in php.ini:
This code uses argv[1] as the input.
<?$c=json_decode('{"Baton Rouge":"Louisiana","Indianapolis":"Indiana","Columbus":"Ohio","Montgomery":"Alabama","Helena":"Montana","Denver":"Colorado","Boise":"Idaho","Austin":"Texas","Boston":"Massachusetts","Albany":"New York","Tallahassee":"Florida","Santa Fe":"New Mexico","Nashville":"Tennessee","Trenton":"New Jersey","Jefferson":"Missouri","Richmond":"Virginia","Pierre":"South Dakota","Harrisburg":"Pennsylvania","Augusta":"Maine","Providence":"Rhode Island","Dover":"Delaware","Concord":"New Hampshire","Montpelier":"Vermont","Hartford":"Connecticut","Topeka":"Kansas","Saint Paul":"Minnesota","Juneau":"Alaska","Lincoln":"Nebraska","Raleigh":"North Carolina","Madison":"Wisconsin","Olympia":"Washington","Phoenix":"Arizona","Lansing":"Michigan","Honolulu":"Hawaii","Jackson":"Mississippi","Springfield":"Illinois","Columbia":"South Carolina","Annapolis":"Maryland","Cheyenne":"Wyoming","Salt Lake City":"Utah","Atlanta":"Georgia","Bismarck":"North Dakota","Frankfort":"Kentucky","Salem":"Oregon","Little Rock":"Arkansas","Des Moines":"Iowa","Sacramento":"California","Oklahoma City":"Oklahoma","Charleston":"West Virginia","Carson City":"Nevada"}',1);$s=array_flip($c);$z=$argv[1];echo @$c[$z]?$c[$z]:(@$s[$z]?$s[$z]:'Arstotzka');

Your entire code will be WAY shorter if you do like this: <?$c=['Baton Rouge'=>Louisiana,$I=Indiana=>$I.polis, ... ];echo$c[$z=$argv[1]]?:(array_flip($c)[$z]?:Arstotzka);. You just need to fill the array. Ignore all warnings

Java, 1062 964 bytes
s->{String t="Arstotzka",a[]="AlabamaMontgomeryAlaskaJuneauArizonaPhoenixArkansasLittle RockCaliforniaSacrementoColoradoDenverConecticutHartfordDelawareDoverFloridaTallahasseeGeorgiaAtlantaHawaiiHonoluluIdahoBoiseIllinoisSpringfieldIndianaIndianapolisIowaDes MoinesKansasTopekaKentuckyFrankfortLouisianaBaton RougeMaineAugustaMarylandAnnapolisMassachusettsBostonMichiganLansingMinnesotaSaint PaulMississippiJacksonMissouriJefferson CityMontanaHelenaNebraskaLincolnNevadaCarson CityNew HampshireConcordNew JerseyTrentonNew MexicoSanta FeNew YorkAlbanyNorth CarolinaRaleighNorth DakotaBismarckOhioColumbusOklahomaOklahoma CityOregonSalemPennsylvaniaHarrisburgRhode IslandProvidenceSouth CarolinaColumbiaSouth DakotaPierreTennesseeNashvilleTexasAustinUtahSalt Lake CityVermontMontpelierVirginiaRichmondWashingtonOlympiaWest VirginiaCharlestonWisconsinMadisonWyomingCheyenne".split("(?<=[a-z])(?=[A-Z])");for(int k=-1;k++<99;t=s.equals(a[k])?a[k%2*-2-~k]:t);return t;}

-17 bytes thanks to @KevinCruijssen.
Try it online!
Pretty straightforward; if a match is found, then add to or subtract from the current index of the array depending on whether it is even or odd. Otherwise print "Arstotzka".
The majority of bytes saved was due to removing the 99 :s and splitting the string based on the regex (?<=[a-z])(?=[A-Z]), which uses a positive lookbehind and lookahead to check for a difference in casing.

Thanks for the suggestion. Funny thing is that I was thinking about improvements I could make to this answer last night. I'll get around to implementing them soon. :)

R, 1023  985 bytes
function(s){g=strsplit
y="Bat9 Rouge,Indi2apol3,Columbus,M9tgomery,Hel6a,D6ver,Bo3e,Aust1,Bost9,Alb2y,Tallah5s4,S2ta Fe,N5hville,Tr6t9,Jeffers9,Richm9d,Pierre,H7r3burg,Augusta,Provid6ce,Dover,C9c0d,M9tpelier,H7tf0d,Topeka,Sa1t Paul,Juneau,L1coln,Raleigh,Mad39,Olympia,Pho6ix,L2s1g,H9olulu,Jacks9,Spr1gfield,Columbia,Annapol3,Chey6ne,Salt Lake8,Atl2ta,B3m7ck,Fr2kf0t,Salem,Little Rock,Des Mo1es,Sacram6to,Oklahoma8,Ch7lest9,C7s98,Nevada,West Virg1ia,Oklahoma,Calif0nia,Iowa,Ark2s5,Oreg9,K6tucky,N0th Dakota,Ge0gia,Utah,Wyom1g,M7yl2d,South C7ol1a,Ill1o3,M3s3sippi,Hawaii,Michig2,Ariz9a,W5h1gt9,W3c9s1,N0th C7ol1a,Nebr5ka,Al5ka,M1nesota,K2s5,C9necticut,Verm9t,New Hampshire,Delaw7e,Rhode Isl2d,Ma1e,P6nsylv2ia,South Dakota,Virg1ia,M3souri,New Jersey,T6ness4,New Mexico,Fl0ida,New Y0k,M5sachusetts,Tex5,Idaho,Col0ado,M9t2a,Alabama,Ohio,Indi2a,Lou3i2a"
for(i in 0:9)y=gsub(i,g("or,in,an,is,ee,as,en,ar, City,on",",")[[1]][i+1],y)
x=g(y,",")[[1]]
'if'({y=match(s,x,0)},x[101-y],'Arstotzka')}

Try it online!
Different from the other R submission.
The code puts the capitals and states in the same vector. The states are in reverse order so that, given the index of either the state or the capital, the matching entry's index is length(data)-index+1, where length(data)=100, 50 (states) + 50 (capitals)
Also, the input data is packed as a single string and then split. The string could be compressed to golf it further.
Edit: added some unoptimized substitution of pairs of characters.

Javascript, 1057 1042 bytes
Answer 1: 1042
(()=>{for(i=0,b=prompt(),c='Baton Rouge,Louisiana,Indianapolis,Indiana,Columbus,Ohio,Montgomery,Alabama,Helena,Montana,Denver,Colorado,Boise,Idaho,Austin,Texas,Boston,Massachusetts,Albany,New York,Tallahassee,Florida,Santa Fe,New Mexico,Nashville,Tennessee,Trenton,New Jersey,Jefferson,Missouri,Richmond,Virginia,Pierre,South Dakota,Harrisburg,Pennsylvania,Augusta,Maine,Providence,Rhode Island,Dover,Delaware,Concord,New Hampshire,Montpelier,Vermont,Hartford,Connecticut,Topeka,Kansas,Saint Paul,Minnesota,Juneau,Alaska,Lincoln,Nebraska,Raleigh,North Carolina,Madison,Wisconsin,Olympia,Washington,Phoenix,Arizona,Lansing,Michigan,Honolulu,Hawaii,Jackson,Mississippi,Springfield,Illinois,Columbia,South Carolina,Annapolis,Maryland,Cheyenne,Wyoming,Salt Lake City,Utah,Atlanta,Georgia,Bismarck,North Dakota,Frankfort,Kentucky,Salem,Oregon,Little Rock,Arkansas,Des Moines,Iowa,Sacramento,California,Oklahoma City,Oklahoma,Charleston,West Virginia,Carson City,Nevada'.split(","),q="Arstotzka";i<100;i++){if(c[i]==b)q=c[i%2?i-1:i+1];}return q})()

Updated Answer 1 missed a zero :S, Also fixed general incorrectness
Updated Answer 1 + 2 re-arranged structure a bit.
Answer 1 is recommended to be run in a Javascript console (your browser's, for example) an unnamed function that returns to the console. You can also test it here.
Answer 2 1049

alert((()=>{for(i=0,b=prompt(),c='Baton Rouge,Louisiana,Indianapolis,Indiana,Columbus,Ohio,Montgomery,Alabama,Helena,Montana,Denver,Colorado,Boise,Idaho,Austin,Texas,Boston,Massachusetts,Albany,New York,Tallahassee,Florida,Santa Fe,New Mexico,Nashville,Tennessee,Trenton,New Jersey,Jefferson,Missouri,Richmond,Virginia,Pierre,South Dakota,Harrisburg,Pennsylvania,Augusta,Maine,Providence,Rhode Island,Dover,Delaware,Concord,New Hampshire,Montpelier,Vermont,Hartford,Connecticut,Topeka,Kansas,Saint Paul,Minnesota,Juneau,Alaska,Lincoln,Nebraska,Raleigh,North Carolina,Madison,Wisconsin,Olympia,Washington,Phoenix,Arizona,Lansing,Michigan,Honolulu,Hawaii,Jackson,Mississippi,Springfield,Illinois,Columbia,South Carolina,Annapolis,Maryland,Cheyenne,Wyoming,Salt Lake City,Utah,Atlanta,Georgia,Bismarck,North Dakota,Frankfort,Kentucky,Salem,Oregon,Little Rock,Arkansas,Des Moines,Iowa,Sacramento,California,Oklahoma City,Oklahoma,Charleston,West Virginia,Carson City,Nevada'.split(","),q="Arstotzka";i<100;i++){if(c[i]==b)q=c[i%2?i-1:i+1];}return q})())

Answer 2 will work with the code snippet button

I totally put the wrong piece of code up...zzz fixing

@GamrCorps all fixed :) sorry about that

Is answer one an acceptable answer in that it must work in console?

I would say yes. However. meta may disagree, although I doubt that people will.

I just specified your console line a bit more and added a testing link, just so you know.

Ok cheers :) Ill make sure i do that next time.

I don't think it's needed to create a closure. You can drop the outside (() => ... ()) and simply alert the result instead of returning. Also, if(cond)q=... can be shortened to cond&&q=...

Instead of commas, you can use zeros (...Carson City0Nevada) to save 2 bytes on the split command

Ruby, 989 bytes
->s{a="Baton Rouge|Louisiana|Indianapolis|Indiana|Columbus|Ohio|Montgomery|Alabama|Helena|Montana|Denver|Colorado|Boise|Idaho|Austin|Texas|Boston|Massachusetts|Albany|New York|Tallahassee|Florida|Santa Fe|New Mexico|Nashville|Tennessee|Trenton|New Jersey|Jefferson|Missouri|Richmond|Virginia|Pierre|South Dakota|Harrisburg|Pennsylvania|Augusta|Maine|Providence|Rhode Island|Dover|Delaware|Concord|New Hampshire|Montpelier|Vermont|Hartford|Connecticut|Topeka|Kansas|Saint Paul|Minnesota|Juneau|Alaska|Lincoln|Nebraska|Raleigh|North Carolina|Madison|Wisconsin|Olympia|Washington|Phoenix|Arizona|Lansing|Michigan|Honolulu|Hawaii|Jackson|Mississippi|Springfield|Illinois|Columbia|South Carolina|Annapolis|Maryland|Cheyenne|Wyoming|Salt Lake City|Utah|Atlanta|Georgia|Bismarck|North Dakota|Frankfort|Kentucky|Salem|Oregon|Little Rock|Arkansas|Des Moines|Iowa|Sacramento|California|Oklahoma City|Oklahoma|Charleston|West Virginia|Carson City|Nevada".split(?|)
i=a.index(s)
i ?a[i^1]:"Arstotzka"}

Split the data into a single array.
Find the index of the input in the array (index returns a falsy value of nil if the input is not there)
If falsy, return "Arstotzka" otherwise XOR the index with 1 to find the other member of the pair
In test program:
f=->s{a="Baton Rouge|Louisiana|Indianapolis|Indiana|Columbus|Ohio|Montgomery|Alabama|Helena|Montana|Denver|Colorado|Boise|Idaho|Austin|Texas|Boston|Massachusetts|Albany|New York|Tallahassee|Florida|Santa Fe|New Mexico|Nashville|Tennessee|Trenton|New Jersey|Jefferson|Missouri|Richmond|Virginia|Pierre|South Dakota|Harrisburg|Pennsylvania|Augusta|Maine|Providence|Rhode Island|Dover|Delaware|Concord|New Hampshire|Montpelier|Vermont|Hartford|Connecticut|Topeka|Kansas|Saint Paul|Minnesota|Juneau|Alaska|Lincoln|Nebraska|Raleigh|North Carolina|Madison|Wisconsin|Olympia|Washington|Phoenix|Arizona|Lansing|Michigan|Honolulu|Hawaii|Jackson|Mississippi|Springfield|Illinois|Columbia|South Carolina|Annapolis|Maryland|Cheyenne|Wyoming|Salt Lake City|Utah|Atlanta|Georgia|Bismarck|North Dakota|Frankfort|Kentucky|Salem|Oregon|Little Rock|Arkansas|Des Moines|Iowa|Sacramento|California|Oklahoma City|Oklahoma|Charleston|West Virginia|Carson City|Nevada".split(?|)
i=a.index(s)
i ?a[i^1]:"Arstotzka"}

puts f[gets.chop]

I wonder if you could save space by using ~a.index(s) and making the states and capitals relate that way (e.g., ["New York", "New Jersey", "California",..., "Sacramento", "Trenton", "Albany"])

PHP, 674 bytes
<?php $a=explode("\n",gzinflate('=SÛŽê0.|÷WôWº =Àr.p..GÓšÆj.WN.ÛýúãÀ²R¥ÞÆžñxRkL’¾{„7L.ªƒäŽ`-™#c@X†¶ÜGñ._/0.Ÿ‡KŽ°s,°‘.:.H\'¨=^p@X.\'Ã•?.?§p#-e¢Ø.¼.G‚e‹N Î1q€.}a´.¦&À.cÄÆåH)EkzÁ0Á–îÕ?Ñ.Nè=:ƒ.Á»uä.áˆÆT½Ó.µ¡/n.¶.Ý.½\'k..=ð\'¥P..lE.i‚.]¯öTh9FÉÊpàÆ..Zødí80ÂžI•à(9¹jŽ½$..U9^²v°7‚8ù..l.;›É¦G..{•.·..‚ƒ“–ªeôh.çR,™“Ç;Zç™„F´}.[à0FÇöµ.8’7rø$5I©°¦kAZE &q“.œd$[á.†h...8U{ÌÞF*“.µ«..sÙP4äš.Î...úøp@OÜ9ØŠÚ„3T[xÙ ¶\¬9sl$D[ÔÎOÃhSžÍ].]1sï„..A.ü-V´Æ‚ìŒ¼qÜa€….KŒÏ&þŽÌ°Â¦..^®qd8Žj5W&ßÂÒ.¹eä\'hÆö4þWV.^‘Ü N.?gŽ¦²f8O2.ö#úT.±§jÆi‚¿..ÔÉ— À..[¬ežã€Úô?cÿ,ö]1ôæq‚.KKnú©4£.vJ.É^sJžì¨Xa.ýÓô9Åj#¶q;&r/‰l.‡’6˜¡gkW²±ë-º2àSÓëÍÄ£zzdÿl·ê7w6±.õDoé†-þ.'));$b=array_search($argv[1],$a);echo $a[$b?$b%2?$b+1:$b-1:0];

Hex:
00000000: 3C 3F 70 68 70 20 24 61 - 3D 65 78 70 6C 6F 64 65 |<?php $a=explode|
00000010: 28 22 5C 6E 22 2C 67 7A - 69 6E 66 6C 61 74 65 28 |("\n",gzinflate(|
00000020: 27 3D 53 DB 8E EA 30 0C - 7C F7 57 F4 57 BA A0 3D |'=S   0 | W W  =|
00000030: C0 72 13 70 16 9D 47 D3 - 9A C6 6A 1A 57 4E 02 DB | r p  G   j WN  |
00000040: FD FA E3 C0 B2 52 A5 DE - C6 9E F1 78 52 6B 4C 92 |     R     xRkL |
00000050: BE 7B 84 37 4C 12 AA 83 - E4 8E 60 2D 99 23 63 40 | { 7L     `- #c@|
00000060: 58 86 B6 DC 47 F1 1C 5F - 2F 30 13 9F 87 4B 8E B0 |X   G  _/0   K  |
00000070: 73 2C B0 91 90 3A 19 48 - 5C 27 A8 3D 5E 70 40 58 |s,   : H\' =^p@X|
00000080: 90 5C 27 C3 95 3F 05 3F - A7 70 23 2D 65 A2 D8 0A | \'  ? ? p#-e   |
00000090: BC 09 47 82 65 8B 4E A0 - CE 31 71 80 13 7D 61 B4 |  G e N  1q  }a |
000000a0: 1F A6 26 C0 06 63 C4 C6 - E5 48 29 45 6B 7A C1 30 |  &  c   H)Ekz 0|
000000b0: C1 96 EE D5 3F D1 1E 4E - E8 3D 3A 83 10 C1 BB 75 |    ?  N =:    u|
000000c0: E4 16 E1 88 C6 54 BD D3 - 03 B5 A1 2F 6E 04 B6 18 |     T     /n   |
000000d0: DD 8D BD 5C 27 6B 1E 02 - 3D F0 5C 27 A5 50 18 0A |   \'k  = \' P  |
000000e0: 6C 45 1A 69 82 15 5D AF - F6 54 68 39 46 C9 CA 70 |lE i  ]  Th9F  p|
000000f0: E0 C6 0D 12 5A F8 64 ED - 38 30 C2 9E 49 95 E0 28 |    Z d 80  I  (|
00000100: 39 B9 6A 8E BD 24 1B 12 - 55 39 5E B2 76 B0 37 82 |9 j  $  U9^ v 7 |
00000110: 38 F9 1B 16 6C 9D 3B 9B - C9 A6 47 0E 04 7B 95 1B |8   l ;   G  {  |
00000120: B7 14 1A 82 83 93 96 AA - 65 F4 68 AD E7 52 2C 99 |        e h  R, |
00000130: 93 C7 3B 5A E7 99 84 46 - B4 7D 08 5B E0 30 46 C7 |  ;Z   F } [ 0F |
00000140: F6 B5 18 38 92 37 72 F8 - 24 35 49 A9 B0 A6 6B 41 |   8 7r $5I   kA|
00000150: 5A 45 A0 26 71 93 13 9C - 64 24 5B E1 07 86 68 2E |ZE &q   d$[   h.|
00000160: 1E 8D 38 55 7B CC DE 46 - 2A 93 17 B5 AB 1C 08 73 |  8U{  F*      s|
00000170: D9 50 34 E4 9A 8D CE 17 - 1F 2E FA F8 70 40 4F DC | P4      .  p@O |
00000180: 39 D8 8A DA 84 33 54 5B - 78 D9 20 B6 5C AC 39 73 |9    3T[x   \ 9s|
00000190: 6C 24 44 5B D4 CE 4F C3 - 68 53 9E CD 5D 0E 5D 31 |l$D[  O hS  ] ]1|
000001a0: 73 EF 84 02 7F 41 AD FC - 2D 56 B4 C6 82 EC 8C BC |s    A  -V      |
000001b0: 71 DC 61 80 85 04 4B 8C - CF 26 FE 8E CC B0 C2 A6 |q a   K  &      |
000001c0: 7F 19 5E AE 71 64 38 8E - 6A 35 57 26 DF C2 D2 1B |  ^ qd8 j5W&    |
000001d0: B9 65 E4 5C 27 68 C6 F6 - 34 FE 57 56 1D 5E 91 DC | e \'h  4 WV ^  |
000001e0: A0 4E 0F 3F 67 8E A6 B2 - 66 38 4F 32 14 F6 23 FA | N ?g   f8O2  # |
000001f0: 54 AD B1 A7 6A C6 69 82 - BF 09 1D D4 C9 97 A0 C0 |T   j i         |
00000200: 1F 12 5B AC 65 9E E3 80 - DA F4 3F 63 FF 2C F6 5D |  [ e     ?c , ]|
00000210: 31 F4 E6 71 82 0F 4B 4B - 6E FA A9 34 A3 01 76 4A |1  q  KKn  4  vJ|
00000220: 9D C9 5E 73 4A 9E EC A8 - 58 61 AD FD D3 F4 39 C5 |  ^sJ   Xa    9 |
00000230: 6A 23 B6 71 3B 26 72 2F - 89 6C 14 87 92 36 98 A1 |j# q;&r/ l   6  |
00000240: 67 6B 57 B2 B1 EB 2D BA - 32 E0 53 D3 EB CD C4 A3 |gkW   - 2 S     |
00000250: 7A 7A 64 FF 6C B7 EA 37 - 77 36 B1 19 F5 44 6F E9 |zzd l  7w6   Do |
00000260: 86 2D FE 07 27 29 29 3B - 24 62 3D 61 72 72 61 79 | -  '));$b=array|
00000270: 5F 73 65 61 72 63 68 28 - 24 61 72 67 76 5B 31 5D |_search($argv[1]|
00000280: 2C 24 61 29 3B 65 63 68 - 6F 20 24 61 5B 24 62 3F |,$a);echo $a[$b?|
00000290: 24 62 25 32 3F 24 62 2B - 31 3A 24 62 2D 31 3A 30 |$b%2?$b+1:$b-1:0|
000002a0: 5D 3B                   -                         |];|
000002a2;

Explanation
<?php
// create array of capitals and states
$a = explode("\n", gzinflate(/* Arstotzka
                                Baton Rouge
                                Louisiana
                                Indianapolis
                                Indiana
                                ...
                             */));
$b = array_search($argv[1], $a); // find user input in list
echo $a[
  $b          // if $b is nonzero, the match succeded
    ?$b % 2   // checks if $b is odd, indicating a capital
      ?$b + 1 // $b points to capital; return the next item, the state
      :$b - 1 // $b points to state; return the previous item, the capital
    :0        // select "Arstotzka" otherwise
];

Python 2.7, 1271 1232 1054 bytes
y='Little Rock,Boise,Richmond,Denver,Olympia,Sacramento,Springfield,Baton Rouge,Tallahassee,Austin,Trenton,Lansing,Annapolis,Dover,Phoenix,Pierre,Charleston,Salt Lake City,Montpelier,Indianapolis,Concord,Providence,Madison,Oklahoma City,Santa Fe,Frankfort,Columbia,Atlanta,Boston,Salem,Juneau,Bismarck,Helena,Montgomery,Des Moines,Saint Paul,Jefferson,Lincoln,Hartford,Augusta,Carson City,Albany,Cheyenne,Columbus,Harrisburg,Honolulu,Raleigh,Nashville,Jackson,Topeka'.split(',')
z='Arkansas,Idaho,Virginia,Colorado,Washington,California,Illinois,Louisiana,Florida,Texas,New Jersey,Michigan,Maryland,Delaware,Arizona,South Dakota,West Virginia,Utah,Vermont,Indiana,New Hampshire,Rhode Island,Wisconsin,Oklahoma,New Mexico,Kentucky,South Carolina,Georgia,Massachusetts,Oregon,Alaska,North Dakota,Montana,Alabama,Iowa,Minnesota,Missouri,Nebraska,Connecticut,Maine,Nevada,New York,Wyoming,Ohio,Pennsylvania,Hawaii,North Carolina,Tennessee,Mississippi,Kansas'.split(',')
def a(b):
 m='Arstotzka'
 if b in y:m=z[y.index(b)]
 if b in z:m=y[z.index(b)]
 print m

Example I/O:
>>> a('Baton Rouge')
Louisiana
>>> a('Montana')
Helena
>>> a('asdfghjkl;')
Arstotzka

Edit: way improved

I wish there was some way I could compress the dictionary...

@Sp3000 oh, no, not zip(), anything but that! (also I think trying to use string interpolation/concatenation on this will just make the code way longer while marginally shortening the dictionary, but i don't know how to try)

Python2 is actually the exact same length because even though you can eliminate parens in print, you can't bind print to a letter.

Perl 5 , 1029 bytes
$h{$h{$_}}=$_ for keys{%h=(Indianapolis,Indiana,Columbus,Ohio,Montgomery,Alabama,Helena,Montana,Denver,Colorado,Boise,Idaho,Austin,Texas,Boston,Massachusetts,Tallahassee,Florida,Nashville,Tennessee,Jefferson,Missouri,Richmond,Virginia,Harrisburg,Pennsylvania,Augusta,Maine,Dover,Delaware,Montpelier,Vermont,Hartford,Connecticut,Topeka,Kansas,Juneau,Alaska,Lincoln,Nebraska,Madison,Wisconsin,Olympia,Washington,Phoenix,Arizona,Lansing,Michigan,Honolulu,Hawaii,Jackson,Mississippi,Springfield,Illinois,Annapolis,Maryland,Cheyenne,Wyoming,Atlanta,Georgia,Frankfort,Kentucky,Salem,Oregon,Sacramento,California,Charleston,'West Virginia','Carson City',Nevada,'Baton Rouge',Louisiana,Albany,'New York','Santa Fe','New Mexico','Trenton','New Jersey',Pierre,'South Dakota',Providence,'Rhode Island',Concord,'New Hampshire','Saint Paul',Minnesota,Raleigh,'North Carolina',Columbia,'South Carolina','Salt Lake City',Utah,Bismarck,'North Dakota','Little Rock',Arkansas,'Des Moines',Iowa,'Oklahoma City',Oklahoma)};say$h{$ARGV[0]}//Arstotzka

This is why I love Perl.  Good job.

T-SQL, 1402 bytes (counting size of .sql file)
create table t(s varchar(99),c varchar(99))insert into t values('Baton Rouge','Louisiana'),('Indianapolis','Indiana'),('Columbus','Ohio'),('Montgomery','Alabama'),('Helena','Montana'),('Denver','Colorado'),('Boise','Idaho'),('Austin','Texas'),('Boston','Massachusetts'),('Albany','New York'),('Tallahassee','Florida'),('Santa Fe','New Mexico'),('Nashville','Tennessee'),('Trenton','New Jersey'),('Jefferson','Missouri'),('Richmond','Virginia'),('Pierre','South Dakota'),('Harrisburg','Pennsylvania'),('Augusta','Maine'),('Providence','Rhode Island'),('Dover','Delaware'),('Concord','New Hampshire'),('Montpelier','Vermont'),('Hartford','Connecticut'),('Topeka','Kansas'),('Saint Paul','Minnesota'),('Juneau','Alaska'),('Lincoln','Nebraska'),('Raleigh','North Carolina'),('Madison','Wisconsin'),('Olympia','Washington'),('Phoenix','Arizona'),('Lansing','Michigan'),('Honolulu','Hawaii'),('Jackson','Mississippi'),('Springfield','Illinois'),('Columbia','South Carolina'),('Annapolis','Maryland'),('Cheyenne','Wyoming'),('Salt Lake City','Utah'),('Atlanta','Georgia'),('Bismarck','North Dakota'),('Frankfort','Kentucky'),('Salem','Oregon'),('Little Rock','Arkansas'),('Des Moines','Iowa'),('Sacramento','California'),('Oklahoma City','Oklahoma'),('Charleston','West Virginia'),('Carson City','Nevada') declare @i varchar(99) = 'Austin' select coalesce((select s from t where c = @i union select c from t where s = @i),(select 'Arstotzka'))

Fort this kind of task set logic trumps procedural logic making easy and fast to solve it on a relational DB.
Below the ungolfed code.
Note we can just run the create/populate part once in a separate batch
create table t
(
     s varchar(99)
    ,c varchar(99)
)

insert into t
 values
 ('Baton Rouge','Louisiana')
,('Indianapolis','Indiana')
,('Columbus','Ohio')
,('Montgomery','Alabama')
,('Helena','Montana')
,('Denver','Colorado')
,('Boise','Idaho')
,('Austin','Texas')
,('Boston','Massachusetts')
,('Albany','New York')
,('Tallahassee','Florida')
,('Santa Fe','New Mexico')
,('Nashville','Tennessee')
,('Trenton','New Jersey')
,('Jefferson','Missouri')
,('Richmond','Virginia')
,('Pierre','South Dakota')
,('Harrisburg','Pennsylvania')
,('Augusta','Maine')
,('Providence','Rhode Island')
,('Dover','Delaware')
,('Concord','New Hampshire')
,('Montpelier','Vermont')
,('Hartford','Connecticut')
,('Topeka','Kansas')
,('Saint Paul','Minnesota')
,('Juneau','Alaska')
,('Lincoln','Nebraska')
,('Raleigh','North Carolina')
,('Madison','Wisconsin')
,('Olympia','Washington')
,('Phoenix','Arizona')
,('Lansing','Michigan')
,('Honolulu','Hawaii')
,('Jackson','Mississippi')
,('Springfield','Illinois')
,('Columbia','South Carolina')
,('Annapolis','Maryland')
,('Cheyenne','Wyoming')
,('Salt Lake City','Utah')
,('Atlanta','Georgia')
,('Bismarck','North Dakota')
,('Frankfort','Kentucky')
,('Salem','Oregon')
,('Little Rock','Arkansas')
,('Des Moines','Iowa')
,('Sacramento','California')
,('Oklahoma City','Oklahoma')
,('Charleston','West Virginia')
,('Carson City','Nevada')

And with that data persisted only use this query
declare @i varchar(99) = 'Austin'

select coalesce(
    (
       select s from t
       where c = @i

       union

       select c from t where s = @i
    ),
    (select 'Arstotzka')
)

The variable declaration is not mandatory, of course you can just put the input directly in the query and spare 10 bytes but I prefer my queries parametized.

387 Bytes? What did you count? The long line in the first part of the answer is 1437 Bytes.

Sorry @matz posted the wrong file size

Is this Oracle PL*SQL? You might wanna specify that in the title. Also might be able to save bytes using sqlldr format rather than direct insert - sqlldr doesn't need quotes everywhere, example

Perl 5, 999 bytes
My first post in codegolf.
%m;@r=qw/la ol ia nt en or is an in on/;map{$x=$_;$x=~s/$_/$r[$_]/eg for(0..9);$x=~s/\b(\w)/\U$1/g;($c,$s)=split'\|',$x;$m{$c}=$s;$m{$s}=$c}qw(bat9_rouge|lou62na 8d2nap16|8d2na c1umbus|ohio mo3gomery|a0bama hel4a|mo37a d4ver|c15ado bo6e|idaho aust8|texas bost9|massachusetts alb7y|new_y5k tal0hassee|fl5ida sa3a_fe|new_mexico nashville|t4nessee tre39|new_jersey jeffers9|m6souri richm9d|virg82 pierre|south_dakota harr6burg|p4nsylv72 augusta|ma8e provid4ce|rhode_60nd dover|de0ware c9c5d|new_hampshire mo3pelier|vermo3 hartf5d|c9necticut topeka|k7sas sai3_paul|m8nesota juneau|a0ska l8c1n|nebraska raleigh|n5th_car18a mad69|w6c9s8 1ymp2|wash8gt9 pho4ix|ariz9a 0ns8g|michig7 h91ulu|hawaii jacks9|m6s6sippi spr8gfield|ill8o6 c1umb2|south_car18a 7nap16|mary0nd chey4ne|wyom8g salt_0ke_city|utah at03a|ge5g2 b6marck|n5th_dakota fr7kf5t|ke3ucky salem|5eg9 little_rock|ark7sas des_mo8es|iowa sacrame3o|calif5n2 ok0homa_city|ok0homa charlest9|west_virg82 cars9_city|nevada);print $m{$ARGV[0]}||"Arstotzka"

Ungolfed:
%m;
@r=qw/la ol ia nt en or is an in on/; # Top 10 bigrams
map{
    $x=$_;
    $x=~s/$_/$r[$_]/eg for(0..9); # Resolve bigram placeholders
    $x=~s/\b(\w)/\U$1/g;          # ucfirst each word
    ($c,$s)=split'\|',$x;         # split city and state
    $m{$c}=$s;                    # key on both city and state
    $m{$s}=$c
} qw(
    bat9_rouge|lou62na
    8d2nap16|8d2na
    c1umbus|ohio
    mo3gomery|a0bama
    hel4a|mo37a
    d4ver|c15ado
    bo6e|idaho
    aust8|texas
    bost9|massachusetts
    alb7y|new_y5k
    tal0hassee|fl5ida
    sa3a_fe|new_mexico
    nashville|t4nessee
    tre39|new_jersey
    jeffers9|m6souri
    richm9d|virg82
    pierre|south_dakota
    harr6burg|p4nsylv72
    augusta|ma8e
    provid4ce|rhode_60nd
    dover|de0ware
    c9c5d|new_hampshire
    mo3pelier|vermo3
    hartf5d|c9necticut
    topeka|k7sas
    sai3_paul|m8nesota
    juneau|a0ska
    l8c1n|nebraska
    raleigh|n5th_car18a
    mad69|w6c9s8
    1ymp2|wash8gt9
    pho4ix|ariz9a
    0ns8g|michig7
    h91ulu|hawaii
    jacks9|m6s6sippi
    spr8gfield|ill8o6
    c1umb2|south_car18a
    7nap16|mary0nd
    chey4ne|wyom8g
    salt_0ke_city|utah
    at03a|ge5g2
    b6marck|n5th_dakota
    fr7kf5t|ke3ucky
    salem|5eg9
    little_rock|ark7sas
    des_mo8es|iowa
    sacrame3o|calif5n2
    ok0homa_city|ok0homa
    charlest9|west_virg82
    cars9_city|nevada
);
print $m{$ARGV[0]}||"Arstotzka"

Haskell, 1077 1069 1068 1063 bytes
z s=last$"Arstotzka":[last$l:[r|s==l]|(l,_:r)<-span(<'~')<$>lines"Baton Rouge~Louisiana\nIndianapolis~Indiana\nColumbus~Ohio\nMontgomery~Alabama\nHelena~Montana\nDenver~Colorado\nBoise~Idaho\nAustin~Texas\nBoston~Massachusetts\nAlbany~New York\nTallahassee~Florida\nSanta Fe~New Mexico\nNashville~Tennessee\nTrenton~New Jersey\nJefferson~Missouri\nRichmond~Virginia\nPierre~South Dakota\nHarrisburg~Pennsylvania\nAugusta~Maine\nProvidence~Rhode Island\nDover~Delaware\nConcord~New Hampshire\nMontpelier~Vermont\nHartford~Connecticut\nTopeka~Kansas\nSaint Paul~Minnesota\nJuneau~Alaska\nLincoln~Nebraska\nRaleigh~North Carolina\nMadison~Wisconsin\nOlympia~Washington\nPhoenix~Arizona\nLansing~Michigan\nHonolulu~Hawaii\nJackson~Mississippi\nSpringfield~Illinois\nColumbia~South Carolina\nAnnapolis~Maryland\nCheyenne~Wyoming\nSalt Lake City~Utah\nAtlanta~Georgia\nBismarck~North Dakota\nFrankfort~Kentucky\nSalem~Oregon\nLittle Rock~Arkansas\nDes Moines~Iowa\nSacramento~California\nOklahoma City~Oklahoma\nCharleston~West Virginia\nCarson City~Nevada",s==l||s==r]

Try it online!
After wasting a lot of time trying to golf an implementation of Huffman coding I realized the straightforward approach is probably shorter. Ah, well.
EDIT: Thanks to @Laikoni for taking off 8 bytes!
EDIT: Thanks again Laikoni for that additional byte. Good idea to use '~'
EDIT: Thanks to Laikoni for taking off those 5 bytes!

You can use pattern matching instead of fmap tail: (l,_:r)<-span(/=',').

Finally span(>',') should also work.

@Laikoni span(>',') doesn't work if there's a space in the name of the capital (e.g. Baton Rouge) since ' '<','

I see, but you could use ~ instead of ,, which is larger than all other characters used.

last$l:[r|s==l] is shorter than filter(/=s)[l,r]!!0 and s==l||s==r beats elem s[l,r] by one byte.

Zsh, 993 928 924 bytes
-4 bytes thanks to @spuck's Bash answer, replacing th Dakota and th Carolina
a=(_ Bat4\ Rouge Lou7i5a Indi5apol7 Indi5a Columbus Ohio M4tgomery Alabama Hel8a M4t5a D8ver Col9ado Bo7e Idaho Aust6 Texas Bost4 Massachusetts Alb5y New\ Y9k Tallahassee Fl9ida S5ta\ Fe New\ Mexico Nashville T8nessee Tr8t4 New\ Jersey Jeffers4 M7souri Richm4d Virg6ia Pierre Sou3 Harr7burg P8nsylv5ia Augusta Ma6e Provid8ce Rhode\ 7l5d Dover Delaware C4c9d New\ Hampshire M4tpelier Verm4t Hartf9d C4necticut Topeka K5sas Sa6t\ Paul M6nesota Juneau Alaska L6coln Nebraska Raleigh N92 Mad74 W7c4s6 Olympia Wash6gt4 Pho8ix Ariz4a L5s6g Michig5 H4olulu Hawaii Jacks4 M7s7sippi Spr6gfield Ill6o7 Columbia Sou2 5napol7 Maryl5d Chey8ne Wyom6g Salt\ Lake1 Utah Atl5ta Ge9gia B7marck N93 Fr5kf9t K8tucky Salem 9eg4 Little\ Rock Ark5sas Des\ Mo6es Iowa Sacram8to Calif9nia 01 0 Charlest4 West\ Virg6ia Cars41 Nevada)
for w (Oklahoma \ City th\ Carol6a th\ Dakota on an in is en or)a=(${a//$[i++]/$w})
<<<${a[$a[(ie)$1]^1]:-Arstotzka}

Try it online!
Try it online!

Try it online!
Manual compression by replacing numbers 0..9 in the array.
Because Zsh uses 1-indexed arrays, we have to add a dummy element at the start.
$a[(i)$1] gets the index of the matching array element. Adding the (e) flag disables pattern matching and uses plain string matching. If we don't do this, Ut* matches Utah and we will print Carson City. If the element is not found, this returns an index beyond the end of the array.
We then xor with 1 and get the corresponding paired element. If our dummy element at index 1 was matched, this will be $a[0], which substitutes the empty string. In any case, if this is empty, ${    :-Arstotzka} will substitute Arstotzka instead.

I like your pass to expand 0..9. Tempted to borrow it.

Bash, 927 978 1003 1051 976 bytes
One more edit, reducing bytes taken by spaces and newlines in $T.
Also re-ordered the substitution for 0..9, fixing a problem handling "Carol1a", since the substitution of 1->"in" would have already been accomplished before that point.
Editing my answer after @GammaFuntion's comment below; I was not meeting the original rules to handle all input; a string that partially matched a state or capital would give wrong output.
His/Her Zsh answer inspired me to also use the XOR rather than the modulo 100 indexing and to do some manual compression using numerals 0..9. I wrote a script to do some quick and dirty calculations on the input list to decide which ten strings would give the best byte reduction. Then used that script iteratively to reduce the strings. Check it out here:
Try it online!
T="Bat8.RougeLou3i2aIndi2apol3Indi2aColumbusOhioM8tgom9yAlabamaHel6aM8t2aD6v9Col5adoBo3eIdahoAust4Tex7Bost8M7sachusettsAlb2yNew.Y5kTallah7seeFl5idaS2ta.FeNew.MexicoN7hvilleT6nesseeTr6t8New.J9seyJeff9s8M3souriRichm8dVirg4iaPi9reSou0Harr3burgP6nsylv2iaAugustaMa4eProvid6ceRhode.Isl2dDov9DelawareC8c5dNew.HampshireM8tpeli9V9m8tHartf5dC8necticutTopekaK2s7Sa4t.PaulM4nesotaJuneauAl7kaL4colnNebr7kaRaleighN51Mad38W3c8s4OlympiaW7h4gt8Pho6ixAriz8aL2s4gMichig2H8oluluHawaiiJacks8M3s3sippiSpr4gfieldIll4o3ColumbiaSou1Annapol3Maryl2dChey6neWyom4gSalt.Lake.CityUtahAtl2taGe5giaB3marckN50Fr2kf5tK6tuckySalemOreg8Little.RockArk2s7Des.Mo4esIowaSacram6toCalif5niaOklahoma.CityOklahomaCharlest8West.Virg4iaCars8.CityNevada"
for t in th.Dakota th.Carol4a an is in or en as on er;{ T=${T//$[j++]/$t};}
for t in {A..Z};{ T=${T//$t/ $t};}
S=${T//. /.}
U=($S)
for s in $S;{ [ "${s//./ }" = "$1" ]&&echo ${U[i^1]//./ }&&exit;i=$[i+1];}
echo Arstotzka

Try it online!
Try it online!
Try it online!
Try it online!
Try it online!

Clever thought to use replacement that way, but if I give Rock as an input, the output is Little Arkansas instead of Arstotzka.

@GammaFunction, you are right. I'm editing my answer to handle this.

Feel free to rip-off my Zsh answer. The array expansions won't be as condensed, but you can take advantage of zero-indexing.

Got to 986: for t in on in an is th.Carol1a or en as th.Dakota er;{ S=${S//$[j++]/$t};}. Also, nice use of th., I'm adding it to my zsh answer.

Oh, and unset/empty variables are implicitly 0 in arithmetic contexts, you don't need to set i (or j) beforehand.

Nice catches. Making an edit.

Prolog, 1221 bytes
p(X):-L=['Baton Rouge','Louisiana','Indianapolis','Indiana','Columbus','Ohio','Montgomery','Alabama','Helena','Montana','Denver','Colorado','Boise','Idaho','Austin','Texas','Boston','Massachusetts','Albany','New York','Tallahassee','Florida','Santa Fe','New Mexico','Nashville','Tennessee','Trenton','New Jersey','Jefferson','Missouri','Richmond','Virginia','Pierre','South Dakota','Harrisburg','Pennsylvania','Augusta','Maine','Providence','Rhode Island','Dover','Delaware','Concord','New Hampshire','Montpelier','Vermont','Hartford','Connecticut','Topeka','Kansas','Saint Paul','Minnesota','Juneau','Alaska','Lincoln','Nebraska','Raleigh','North Carolina','Madison','Wisconsin','Olympia','Washington','Phoenix','Arizona','Lansing','Michigan','Honolulu','Hawaii','Jackson','Mississippi','Springfield','Illinois','Columbia','South Carolina','Annapolis','Maryland','Cheyenne','Wyoming','Salt Lake City','Utah','Atlanta','Georgia','Bismarck','North Dakota','Frankfort','Kentucky','Salem','Oregon','Little Rock','Arkansas','Des Moines','Iowa','Sacramento','California','Oklahoma City','Oklahoma','Charleston','West Virginia','Carson City','Nevada'],nth0(I,L,X),J is I xor 1,nth0(J,L,E),write(E),!.
p(X):-write('Arstotzka').

Most of the byte count comes from the list of states and capitals.
All names of states and capitals need to be quoted atoms since they begin with
upper case letters, costing us 202 bytes in 's alone.

How it works
 nth0(I,L,X)

Gets index I of element X in list L.
J is I xor 1

Xor index with 1 to get index of return value.
nth0(J,L,E)

Gets element E at index J of list L.
If any rule fails, print Arstotzka
Example
>p('Austin').
Texas

>p('Texas').
Austin

R, 1294 bytes
d=data.frame(a=c("Baton Rouge","Indianapolis","Columbus","Montgomery","Helena","Denver","Boise","Austin","Boston","Albany","Tallahassee","Santa Fe","Nashville","Trenton","Jefferson","Richmond","Pierre","Harrisburg","Augusta","Providence","Dover","Concord","Montpelier","Hartford","Topeka","Saint Paul","Juneau","Lincoln","Raleigh","Madison","Olympia","Phoenix","Lansing","Honolulu","Jackson","Springfield","Columbia","Annapolis","Cheyenne","Salt Lake City","Atlanta","Bismarck","Frankfort","Salem","Little Rock","Des Moines","Sacramento","Oklahoma City","Charleston","Carson City"),b=c("Louisiana","Indiana","Ohio","Alabama","Montana","Colorado","Idaho","Texas","Massachusetts","New York","Florida","New Mexico","Tennessee","New Jersey","Missouri","Virginia","South Dakota","Pennsylvania","Maine","Rhode Island","Delaware","New Hampshire","Vermont","Connecticut","Kansas","Minnesota","Alaska","Nebraska","North Carolina","Wisconsin","Washington","Arizona","Michigan","Hawaii","Mississippi","Illinois","South Carolina","Maryland","Wyoming","Utah","Georgia","North Dakota","Kentucky","Oregon","Arkansas","Iowa","California","Oklahoma","West Virginia","Nevada"),stringsAsFactors=F)
print(ifelse(any(e<-d[,1]%in%(n<-scan("","raw",sep='$'))),d[e,2],ifelse(any(f<-d[,2]%in%n),d[f,1],'Arstotzka')))

It is case senstive according to the input shown as example.
Ungolfed code (slightly different in the position of scan):
n<-scan("","raw",sep='$')
print(
  ifelse(
    any(e<-d[,1]%in%n), # test city
    d[e,2], # if yes return the state
    ifelse(
      any(f<-d[,2]%in%n), # test state
      d[f,1], # return city
      'Arstotzka'
    )
  )
)

Java, 1312
public class a{public static void main(String[]x){List<String>a=Arrays.asList("Baton Rouge","Louisiana","Indianapolis", "Indiana","Columbus","Ohio", "Montgomery","Alabama","Helena","Montana","Denver","Colorado","Boise","Idaho","Austin","Texas","Boston","Massachusetts","Albany","New York","Tallahassee","Florida","Santa Fe","New Mexico","Nashville","Tennessee","Trenton","New Jersey","Jefferson","Missouri","Richmond","Virginia","Pierre","South Dakota","Harrisburg","Pennsylvania","Augusta","Maine","Providence","Rhode Island","Dover","Delaware","Concord","New Hampshire","Montpelier","Vermont","Hartford","Connecticut","Topeka","Kansas","Saint Paul","Minnesota","Juneau","Alaska","Lincoln","Nebraska","Raleigh","North Carolina","Madison","Wisconsin","Olympia","Washington","Phoenix","Arizona","Lansing","Michigan","Honolulu","Hawaii","Jackson","Mississippi","Springfield","Illinois","Columbia","South Carolina","Annapolis","Maryland","Cheyenne","Wyoming","Salt Lake City","Utah","Atlanta","Georgia","Bismarck","North Dakota","Frankfort","Kentucky","Salem","Oregon","Little Rock","Arkansas","Des Moines","Iowa","Sacramento","California","Oklahoma City","Oklahoma","Charleston","West Virginia","Carson City","Nevada");int b=a.indexOf(x[0]);String s=b<0?s="Arstotzka":a.get(b/2*2+((b+1)%2));System.out.print(s);}}

Javascript, 1042
var x=prompt(),a="Baton Rouge,Louisiana,Indianapolis,Indiana,Columbus,Ohio,Montgomery,Alabama,Helena,Montana,Denver,Colorado,Boise,Idaho,Austin,Texas,Boston,Massachusetts,Albany,New York,Tallahassee,Florida,Santa Fe,New Mexico,Nashville,Tennessee,Trenton,New Jersey,Jefferson,Missouri,Richmond,Virginia,Pierre,South Dakota,Harrisburg,Pennsylvania,Augusta,Maine,Providence,Rhode Island,Dover,Delaware,Concord,New Hampshire,Montpelier,Vermont,Hartford,Connecticut,Topeka,Kansas,Saint Paul,Minnesota,Juneau,Alaska,Lincoln,Nebraska,Raleigh,North Carolina,Madison,Wisconsin,Olympia,Washington,Phoenix,Arizona,Lansing,Michigan,Honolulu,Hawaii,Jackson,Mississippi,Springfield,Illinois,Columbia,South Carolina,Annapolis,Maryland,Cheyenne,Wyoming,Salt Lake City,Utah,Atlanta,Georgia,Bismarck,North Dakota,Frankfort,Kentucky,Salem,Oregon,Little Rock,Arkansas,Des Moines,Iowa,Sacramento,California,Oklahoma City,Oklahoma,Charleston,West Virginia,Carson City,Nevada".split(","),b=a.indexOf(x),s=b<0?s="Arstotzka":a[Math.floor(b/2)*2+((b+1)%2)];alert(s);

AWK, 1009 bytes
{split("Baton Rouge,Louisiana,Indianapolis,Indiana,Columbus,Ohio,Montgomery,Alabama,Helena,Montana,Denver,Colorado,Boise,Idaho,Austin,Texas,Boston,Massachusetts,Albany,New York,Tallahassee,Florida,Santa Fe,New Mexico,Nashville,Tennessee,Trenton,New Jersey,Jefferson,Missouri,Richmond,Virginia,Pierre,South Dakota,Harrisburg,Pennsylvania,Augusta,Maine,Providence,Rhode Island,Dover,Delaware,Concord,New Hampshire,Montpelier,Vermont,Hartford,Connecticut,Topeka,Kansas,Saint Paul,Minnesota,Juneau,Alaska,Lincoln,Nebraska,Raleigh,North Carolina,Madison,Wisconsin,Olympia,Washington,Phoenix,Arizona,Lansing,Michigan,Honolulu,Hawaii,Jackson,Mississippi,Springfield,Illinois,Columbia,South Carolina,Annapolis,Maryland,Cheyenne,Wyoming,Salt Lake City,Utah,Atlanta,Georgia,Bismarck,North Dakota,Frankfort,Kentucky,Salem,Oregon,Little Rock,Arkansas,Des Moines,Iowa,Sacramento,California,Oklahoma City,Oklahoma,Charleston,West Virginia,Carson City,Nevada,Arstotzka,",S,",")
for(x in S)if(S[x]==$0)break
$0=S[x-1+x%2*2]}1

Try it online!
If there's a way to shrink this, I'd be happy to hear about it. :)

J, 843 829 bytes
-&.((<;._1'-rstotzk7Bat> Roug/Ind6?p@;5@umbus.o8gom4y,Hel97D9v4,Bo;e-ust=,Bost>-lb<y,Tal1h2se/Sa8a F/N2hvill/Tre8>,Jeff4s>,Richm>d,Pi4r/H3r;burg-ugust7Provid9c/Dov45>c:d.o8peli4,H3tf:d,Topek7Sai8 Paul,Juneau,L=c@n,Raleigh.ad;>,Olymp6,Pho9ix,L<s=g,H>@ulu,Jacks>Apr=gfield5@umb6-n?p@;5hey9n/Salt Lake City-t187B;m3ck,Fr<kf:tAalem,Little Rock,Des Mo=esAacrame8o,Ok1homa City5h3lest>53s> City0evad7West Virg=6,Ok1homa5alif:n6,Iowa-rk<s2,Oreg>,Ke8ucky0:th Dakot7Ge:g6,Utah,Wyom=g.3y1ndAouth C3@=7Ill=o;.;s;sippi,Hawaii.ichig<-riz>7W2h=gt>,W;c>s=0:th C3@=a0ebr2ka-1ska.=nesot7K<s25>necticut,V4mo80ew Hampshir/De1w3/Rhode Is1nd.a=/P9nsylv<6Aouth Dakot7Virg=6.;souri0ew J4sey,T9nesse/New Mexico,Fl:ida0ew Y:k.2sachusetts,Tex2,Idaho5@:ado.o8<a-1bam7Ohio,Ind6n7Lou;6?'rplc(45{21;/\a.),._2<\',A,Me,,Nlaasarer,Ciaa,ntenorisaninonnaol,S')i.<)

Try it online!


text:
Shortened words
My cell phone carrier charges a cent per character in a text! I need a program to shorten the words for me, while still being understandable. I will be texting this program to my friends, so it needs to be as short as possible.
Your program will take a String (a word is separated by a non-alphanumeric character) of words from STDIN (or closest alternative) reduce any similar (a and A are similar, b and a are not, 1 is similar only to itself) consecutive alphanumeric characters down to one character, and remove all the vowels (aeiou), and print it to STDOUT (or closest alternative), only letters, numbers, and spaces are kept: everything else is removed at the end. The first character of a word must remain the same, and only shorten the word if the resulting shortened word is 4 or more characters long.
Examples:
homework -> hmwrk
llamas -> llamas (lms<4 characters)
botany -> btny
y3333llow -> y3lw
shorten -> shrtn
aabcddde -> abcd
abb'bbc -> abbbbc (abb -> abb and bbc -> bbc = abb'bbc --(remove non-alphanumeric-space characters)-> abbbbc)
SHARRRKnado -> shrknd (or with capitalization bonus: SHrKnd)
abracadabra -> abrcdbr
everything is awesome! -> evrythng is awsm
you can't break what is already broken -> you cant break what is alrdy brkn
the person's cat's bed's blanket's poka-dots are orangy-yellow -> the prsns cats beds blnkts pokadots are orngyyellow

-5% bonus if kept a i o  or u at end of word
sharknado -> shrkndo
abracadabra -> abrcdbra

-10% bonus if kept capitalization of non-consecutive characters
aAbCDdDE -> abCd

This is code-golf so the shortest program in bytes wins.

What characters can the string contain? (Ex. can it contain spaces?) Why the restriction to STDIN/STDOUT instead of allowing, say, a function? Is y a vowel?

@Doorknob does this edit answer all your questions sufficiently?

If the input can contain multiple words, you should include some test cases that demonstrate this. Also, you still don't seem to allow functions that take input via arguments and output via return values; this is typically frowned upon as it's simply an unnecessary restriction.

All your non-bonus examples have words consisting solely of lowercase letters. Can we expect the input to be like this?

"a word is separated by a non-alphanumeric character", meaning a word contains A-Za-z0-9. Considering this, should ' be treated as a word character or should the program split on that?

① Will rrrrrremove remain as is since rmv is only 3 chars? Or ② Shouldn't SHARRRKnado be SHRKnd instead of SHrKnd?

@helix it seems the bonus only applies to non-repeated letters.

Ok, fixed yellow, everything and added y333llow

You say reduce any consecutive letters down to one letter, yet you reduce the digits in y3333llow (and don't remove the o). Should all consecutive equal characters get collapsed?

Fixed: I was in a rush and didn't notice my mistake. Also reworded to reducing alphanumeric.

It is recommended to use the Sandbox to get issues with challenges fixed before posting them to main :)

What happened to the o in orangy-yellow in the last test case? Were we not supposed to maintain the first letter? And could you also explain the behaviour of handling hyphens?

Surely "reduce any consecutive alphanumeric characters down to one character, and remove all the vowels (aeiou)" means that e.g. homework should be reduced to either one character or zero (depending on whether the one character left after the reduction is a vowel or not)?

@CᴏɴᴏʀO'Bʀɪᴇɴ The o was deleted by legion in an edit,  and hyphens act as a word separator, until the end, where it is removed, as a hyphen is not alphanumeric or a space.

@PeterTaylor I think that consecutive character refers to the same character, i.e. ll

What is the correct output for abcdedfgh? Is it abcddfgh because the reduction applies before the vowel removal, or abcdfgh because the vowel removal applies before the reduction?

Why does f.x. poka-dots get to keep its vowels?

poka and dots are two words, both when shortened are less than 4 characters pk and dts

CJam, 54 bytes
qelS/" ,"*__eu&S-A,s-NerN%{_(\"aeiou"-+e`1f=_S-Z>\@?}/

Try this fiddle or this test suite in the CJam interpreter.
How it works
qel        e# Read all input and cast to lowercase.
S/" ,"*    e# Replace spaces with " ,". This way, we don't have to consider
           e# spaces word delimiters, which will make them easier to preserve.
__eu       e# Push two copies and convert the second one to uppercase.
&          e# Intersect the copies. This will keep only non-letters.
S-A,s-     e# Remove spaces and digits from the non-letters.
Ner        e# Replace their occurrences in the input with linefeeds.
N%         e# Split at linefeeds.
{          e# For each resulting chunk:
  _(\      e#   Push a copy and shift out the first character.
  "aeiou"- e#   Remove all vowels from the tail.
  +        e#   Concatenate the result with the first character.
  e`       e#   Perform run-length encoding.
  1f=      e#   Select all characters.
  _S-      e#   Push a copy and remove spaces.
           e#   This is for the length check; spaces don't actually form part
           e#   of the word.
  Z>       e#   Discard the first three characters.
  \@?      e#   If there are characters left, pick the modified word; else
           e#   pick the unmodified one.
}/         e#

Japt, 57 bytes 58 80 88 90 95 98
Saved 6 bytes thanks to @ETHproductions
Japt is a shortened version of JavaScript. Interpreter
Uv qS m@(A=Xg0 +Xs1 r"(.)\\1+",@Y r"[aeiou]",P)g3 ?A:X)qS

Uses RegExp to do most of the work.
Try it online
Explanation
This explanation is old but the method used is still generally the same.
UqS       // Splits input
   m@     // Loops through words
     Xr"(.)\\1+","$1"     // Removes consecutive sequences
      r"[aeiouAEIOU]",P   // Removes vowels
   m@     // Loops again
     Xl >3?               // If length of word is greater than 3
           X[0]==UqS [Y][0]?  // If first letter is right, keep it
              X
           :UqS [Y][0]+X      // Otherwise, use the correct first letter
     :UqS [Y]  qS v       // Otherwise return the original word

Hey, my language is in use :D BTW, two spaces in a row can be replaced with a right-paren. I may have some more golfing tips tomorrow, but right now I'm tired and need some rest...

@ETHproductions Oh yeah, I remember reading that in the docs but I guess it slipped out of mind, thanks for the tip!

In response to your other question, you could use A-J (predefined to different numbers), since you aren't using them anywhere else.

Let's see... you can replace [Y] and the following space with gY). There is also a string remove function k, but it currently only removes the first occurance, and doesn't do regex anyway. I think "$1" could be replaced with @Y, too.

@ETHproductions thanks! With some more golfing, I'm down to 58 bytes. Hopefully I can beat 54

Holy cow, that's way shorter! Let me have a minute to look through it and figure out how my own language works... ;)

There's not much room for golfing that I can see, but I think l >3? could be replaced with [3]?.

@ETHproductions oh that's right, thanks yet again! I've used g4, but I think it means the same as [4].

Yep, it functions identically, except that you can't do Ug3 =7. It is usually the same length as well, unless you have another space afterward that you can combine into a right-paren. I think that for v0.2, <array><number> should compile to <array>[<number>]. This will save 1 byte in most scenarios, and even 2 in some.

Aww man, this would've been 50 bytes if we'd implemented String.prototype.e in the current version! Uv qS m@(A=Xe".(.)\\1+",@Y r"[aeiou]",P)g3 ?A:X)qS Wait, maybe that's not right... BTW, it should be g3, not g4. botany currently returns botany instead of btny.

TeaScript, 60 bytes 64 58 63 70
xL¡l»(b=l0+lS(1)g(/(.)\1+/,"$1")g`[aeiou]`)n>3?b:l,ø)O`a-z `

I should be able to use the unique function to get rid of repeated characters but for now I'm using a regex.
I believe this should work fine. I'll be heading off to sleep so notify me if anything is wrong and I'll address it next morning.
Ungolfed
xL()l(#(b=l0+lS(1)g(/(.)\1+/,"$1")g`[aeiou]`)n>3?b:l,` `)O`a-z `

@Dennis Pretty sure it's all good now, I've tested with the test cases and it seems to work.

The last test case should print pokadots and probably orngyyellow.

Doesn't seem to work with y3333llow. I think you need to add 0-9 at the O function.

C# - 404 bytes
using System;using System.Text;using System.Text.RegularExpressions;class j{static bool v(char l){return l=='e'||l=='a'||l=='o'||l=='i'||l=='u';}static void Main(){string a=Console.ReadLine();string z=Regex.Replace(a,"[^a-zA-Z ]","");string[]b=z.Split(' ');string c="";foreach(string d in b)    {if(d.Length>4){foreach(char e in d.ToCharArray()){if(!v(e))c+=e;}}else{c+=d;}c+=' ';}Console.WriteLine(c);}}

It takes input from Console.ReadLine(). I used a regex to find the non alphanumeric characters and spaces and I calculated if the size is less than 4. I tested using the final example.
C# - 279 bytes (from LegionMammal798)
using C=System.Console;class j{static void Main(){var c="";foreach(var d in System.Text.RegularExpressions.Regex.Replace(C.ReadLine(),"[^a-zA-Z0-9 ]",c).Split(' ')){if(d.Length>4){foreach(var e in d)if(!"aeiou".Contains(e.ToString()))c+=e;}else c+=d;c+=' ';}C.Write(c);}}

Thank you for the golfing tips!

Various golfs

Thank you! Is it alright if I edit my post with one of those golfs?

Hmm. This can be colfed by using C# 6.0. You can just do:    static bool v(char l)=>...    . No return statements have to be written

@Admin3X Sure, was providing suggestions.

, 57 chars / 97 bytes (noncompetitive)
Ɱ(ï,↪(a=$ù⬮ċ/⊙\1+⌿,`⑴”ċ/[ᶌ]⌿,⬯⸩Ꝉ>3?a⎖0≔$⎖0?a:$⎖0+a:$,⬭,⬭)

Try it here (Firefox only).
Uses regex aliasing and other syntax made after the challenge was posted.

Haskell, 187 176 bytes
Adhering to written description, not given examples:
import Data.List
import Data.Char
f=filter
d w@(_:_:_:_)=map head$groupBy(\a b->toLower a==toLower b)w
d w=w
s=unwords.map(f isAlphaNum.d.(\(h:t)->h:f(`notElem`"aeiou")t)).words

Call s.
Improved late after vote reminded me of its existence.

source: Stack Exchange

license: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/3.0/

sort: votes


text:
Digital Cellular Automata
Write a program or function that takes in an odd positive integer N and a string of decimal digits (0123456789). The string represents a ten-state one-dimensional cellular automaton. Each digit occupies one cell and the update rule from one generation to the next is that every cell becomes the digit resulting from the sum of the N cells centered on the cell, modulo 10.
The first and last cells wrap around as if neighbors, so cells can always have N cells centered on them. Note that N may be larger than the length of the string, which means it could wrap around multiple times and some digits will accordingly be in the sum multiple times.
As an example, if N is 7 and the string is 038, to visualize the cells to sum we can write 038 repeating infinitely in both directions
...038038038038038...

then the digit that the 0 will change into is the sum of the 7 digits centered around any 0, modulo 10:
...038038038038038...
      ^_____^
         |
    sum all these

This is (0+3+8+0+3+8+0)%10, which is 2.
Similarly the digits the 3 and 8 change into are defined by (3+8+0+3+8+0+3)%10 = 5 and (8+0+3+8+0+3+8)%10 = 0 respectively.
Thus, the generation after 038 is 250 when N is 7.
Your program or function needs to print or return the digit string of the very next generation of the input digit string. i.e. apply the update rule once to each cell and give the output. The shortest code in bytes wins.
Test Cases
[digit string] -> [N = 1], [N = 3], [N = 5], [N = 7], [N = 9], [N = 43]
0 -> 0, 0, 0, 0, 0, 0
1 -> 1, 3, 5, 7, 9, 3
2 -> 2, 6, 0, 4, 8, 6
3 -> 3, 9, 5, 1, 7, 9
4 -> 4, 2, 0, 8, 6, 2
5 -> 5, 5, 5, 5, 5, 5
6 -> 6, 8, 0, 2, 4, 8
7 -> 7, 1, 5, 9, 3, 1
8 -> 8, 4, 0, 6, 2, 4
9 -> 9, 7, 5, 3, 1, 7
00 -> 00, 00, 00, 00, 00, 00
07 -> 07, 47, 41, 81, 85, 47
10 -> 10, 12, 32, 34, 54, 12
11 -> 11, 33, 55, 77, 99, 33
12 -> 12, 54, 78, 10, 34, 54
34 -> 34, 10, 78, 54, 12, 10
66 -> 66, 88, 00, 22, 44, 88
80 -> 80, 86, 46, 42, 02, 86
038 -> 038, 111, 294, 250, 333, 472
101 -> 101, 222, 343, 545, 666, 989
987 -> 987, 444, 901, 765, 222, 543
1234 -> 1234, 7698, 3412, 9876, 1234, 7698
26697 -> 26697, 54128, 00000, 56982, 84413, 54128
001002 -> 001002, 211122, 331332, 335334, 455544, 113112
129577020 -> 129577020, 326194923, 474081605, 961120291, 333333333, 183342413
6023845292173530 -> 6023845292173530, 6853571632015189, 1197228291289874, 9238433109901549, 0110956118726779, 1982123699138828

@LegionMammal978 Lets keep it as a string.

@LegionMammal978 No. I admit I could have allowed it originally but doing so now would unfairly affect existing answers that use strings.

Well, thanks for nearly doubling the size of my answer...

Pyth, 20 19 bytes
1 byte thanks to @FryAmTheEggman.
sm`esmv@z-+dk/Q2Qlz

Try it online. Test suite.

e<num> is equivalent to %<num>T

CJam, 21 bytes
l~_,\2/f-l:~fm>:.+Af%

Test it here.
Explanation
l~   e# Read and evaluate N.
_,   e# Duplicate and turn into range [0 1 ... N-1]
\2/  e# Swap with other copy and (integer) divide by 2.
f-   e# Subtract this from each element in the range to get
     e# [-(N-1)/2 ... -1 0 1 ... (N-1)/2]
l:~  e# Read string and evaluate each digit separately.
fm>  e# Make one copy of the result for each element i in the range, shifting the array
     e# i cells to the right, cyclically.
:.+  e# Sum the columns of the resulting matrix.
Af%  e# Take each of those sums modulo 10.

Mathematica, 85 bytes
""<>ToString/@CellularAutomaton[{Tr@#~Mod~10&,{},#/2-1/2},FromDigits/@Characters@#2]&

Can you use .5 instead of 1/2?

@mbomb007 No, it needs to be an integer.

Python 3, 114 92 86 80 bytes
Took off 6 bytes thanks to Sp3000 and another 6 bytes thanks to xnor!
a=lambda N,D,i=0:D[i:]and str(int((D*N)[(i-N//2)%len(D):][:N],11)%10)+a(N,D,i+1)

Defines a named function a that takes N and D as parameters, the N and digit string defined in the challenge.
Explanation
In Python 3, and between two strings will end up being the latter. Hence, D[i:]and ... short-circuits once all center positions have been iterated over as D[i:] will be an empty string and therefore falsy. (D*N)[(i-N//2)%len(D):][:N] duplicates the digit string a bunch of times, then slices it in the right places to give the substring that has the correct digit as the center. Recall for a moment that the sum of the digits of a base 10 number modulo 9 is the same as the number itself modulo 9. str(int(...,10)%10) treats the resulting number-string as if it was base 11 and gets the remainder modulo 10, then converts back to string. Finally, a(N,D,i+1) moves on to the next center position. Because of the +, once the recursion is done, all of the resulting digits are lumped together and returned.

Haskell, 92 bytes
String conversion is really expensive in Haskell...
x!n=last.show.sum.map(read.pure).take n.(`drop`cycle x).fst<$>zip[div(1-n)2`mod`length x..]x

This defines an infix function !, used as follows:
> "1234"!3
"7698"

Explanation
On the right we have [div(1-n)2`mod`length x..], which is just the infinite list of integers starting from (1-n)/2 modulo length(x) (we take the modulus, since we want the first element to be non-negative). These correspond to the starting indices of the CA neighborhoods. We zip it with x just to obtain a list of the correct length.
The function <$> is the infix version of map, and its left argument is a function composition read from right to left. Thus for each integer in the above list (extracted with fst), we drop that many characters from cycle x (which is the concatenation of infinitely may copies of x), take n characters from the remainder, convert them to strings and then integers with read.pure, take their sum, convert that to string with show, and take the last character of that, which corresponds to the remainder mod 10.

NARS2000 APL, 37 characters (72 bytes)
⎕←10⊥10∣+⌿⊃({⍵..-⍵}⌊⎕÷2)∘.⌽⊂49-⍨⎕AV⍳⍞

Explanation:
  ⎕←10⊥10∣+⌿⊃({⍵..-⍵}⌊⎕÷2)∘.⌽⊂49-⍨⎕AV⍳⍞
⍝ ⎕←                                    output
⍝   10⊥                                 the base-10 digits in
⍝      10∣                              the modulo-10
⍝         +⌿                            column-wise sum of
⍝           ⊃                           the matrix version of
⍝                         ∘.⌽           the outer-product rotation of
⍝                            ⊂            the scalar version of
⍝                                 ⎕AV⍳    the index in the atomic vector of
⍝                                     ⍞   an input string
⍝                             49-⍨        minus 49 ('0' + 1)
⍝                                       by
⍝             {⍵..-⍵}                     the range ⍵ to -⍵, where ⍵ is
⍝                    ⌊                    the floor of
⍝                     ⎕                   an input integer
⍝                      ÷2                 divided by 2

Isn't APL one byte per character, since the encoding isn't UTF-8? APL uses the APL code page.

@mbomb007 NARS2000 does not support the APL code page as far as I know, and the .. primitive is nonstandard and thus not "portable".

Would it maybe be shorter to use Dyalog APL?

Octave, 64 bytes
@(s,n)["" mod(sum(bsxfun(@shift,s'-48,(1:n)-ceil(n/2))'),10)+48]

J, 41 bytes
"."0@]{~(1":10|+/@:)#@]|-:@<:@[-~(+/&i.#)

Turned out longer than I expected. Should be golfable.
We generate a matrix with elements in a row showing the positions whose values should be added (mod 10) to get sum for a position.
Usage:
   7 ("."0@]{~(1":10|+/@:)#@]|-:@<:@[-~(+/&i.#)) '038'
250

Try it online here.

all_licenses: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/3.0/


text:
A game of locks and keys
There are n boxes, numbered 1-n. Each box is locked, such that it can be opened by only one corresponding type of key (also numbered 1-n). These keys are randomly scattered in the boxes (one box may have any number of keys, one key may have any number of duplicates), and then all boxes are shut. A treasure (numbered 0) has also been locked in many of the boxes.
You have hired a locksmith to retrieve all the treasure. He charges for each box he cracks open. There is no charge for opening a box for which the key is already available.
Input is the contents of each box. You can decide the format of the input.
Output the minimum cost required to get the treasures.
Notes

Your algorithm may take a long time, but that is irrelevant.
Shortest code wins.
No need to bother about invalid input.

Sample data
Here line i represents the keys present in box i.
Input
2 0
3
4 0
5 6 0
6
0

Output
1

Input
2 0
3 0

4 0
6
5 0

Output
3

Input
2 4 0
3 0

1 0
6
5 0

Output
2

Input
1
3 4

2 6
5

Output
0

Is this perhaps related to this?

Also related: http://puzzling.stackexchange.com/questions/23150/how-to-beat-count-dracula

@VoteToClose Nice video. It is similar, except that it talks of a mathematical puzzle and specific algorithm, rather than a generalised one.

@VoteToClose, not really. That question is about permutations; this question is graph reachability plus smallest covering set.

This seems related to this puzzle about 100 locked boxes of wood and steel: http://puzzling.stackexchange.com/q/17852/4551

I'm not a fan of the specific input format. I expect I'd need a decent fraction of my code just to put it in a usable form. In the future, I suggest allowing more flexible forms of input for algorithmic style problems.

@xnor The input is simple only. How can I make it simpler than this?

@ghosts_in_the_code It's not about simplicity but about flexibility. Commonly, challenges that require structured input allow any convenient list format, as long as the data is not preprocessed. Depending on the language that could mean a whitespace separated file like you have, or it could mean [[1] [3 4] [] [] [2 6] [5]] or maybe {{1},{3,4},{},{},{2,6},{5}}. This way, most languages can reduce reading the input to something as trivial as i=eval(read()) and focus on the fun part of the challenge.

I am missing something to understand this puzzle. How does the last one work to zero if we don't start with any keys and locksmith charges to open a box we don't already have the key for?

@qumonio Only all the treasure (0s) need to be found. Since there are no 0s, we have already completed the challenge even before opening any box.

@xnor  @ MartinButtner Done.

CJam, 59 52 50 49 45 43 42 bytes
qN/ee::~e!{_0+{0a&}#>W%_{1$|(z@-},,\;}%:e<

Thanks to @MartinBüttner for golfing off 3 bytes and paving the way for 4 more!
Try it online in the CJam interpreter.
How it works
qN/      e# Read all input and split it at linefeeds.
ee       e# Enumerate the lines.
         e# STACK: [[0 "i0 i1 ..."] [1 "j0 j1 ..."] ...]
::~      e# Apply ~ (bitwise NOT/evaluate) to each item of the pairs.
         e# STACK: [[-1 i0 i1 ...] [-2 j0 j1 ...] ...]
e!       e# Push all unique permutations of the resulting array.
{        e# For each permutation:
  _0+    e#   Push a copy and append 0 to it.
  {0a&}# e#   Find the first index of an element that contains 0.
  >      e#   Discard all previous elements of the array.
  W%     e#   Reverse the resulting array.
         e#   We now have a (partial) permutation that contains
         e#   all treasures and ends with a treasure.
  _      e#   Push a copy. The original (which contains lists, but no
              numbers) will serve as accumulator.
  {      e#   Filter; for each list in the array:
    1$|  e#     Push a copy of the accumulator and perform set union.
    (    e#     Shift out the first element (bitwise NOT of 0-based index).
    z    e#     Apply absolute value to push the 1-based index.
    @-   e#     Perform set difference with the former state of the
         e#     accumulator. This pushes an empty list iff the 1-based
         e#     index was already in the accumulator, i.e., iff we already
         e#     had a key.
  },     e#   Keep the element if we did not have the key.
  ,      e#   Count the kept elements.
  \;     e#   Discard the accumulator from the stack.
}%       e#
:e<      e# Get the minimum of all results.

Could you add an explanation for us without the gift of CJam understanding? :D I'd like to know how this works.

@VoteToClose Look at this CJAM101

array long & works, so you can remove the a from 0a&. Sadly this makes it slightly harder to catch you.

@PeterTaylor Unfortunately, if I replace 0a& with 0&, I also have to replace 0+ with 0aa+, since 0 0& is falsy.

@VoteToClose I've edited my answer.

I don't believe it's producing the right result here http://cjam.aditsu.net/#code=qN%2Fee%3A%3A~e!%7B_0%2B%7B0a%26%7D%23%3EW%25_%7B1%24%7C(z%40-%7D%2C%2C%5C%3B%7D%25%3Ae%3C&input=2%200%0A3%0A4%200%0A5%206%200%0A6%0A0

@qumonio Each box in your example contains the key for the next one, so you only have to pay to open the first.

@Dennis I am sorry, I had some linkage trouble and I meant to provide input similar to this JS array : [ [4,0], [1,3,4], [0], [6,0], [3,0], [5]] I think I got it set properly here http://cjam.aditsu.net/#code=qN%2Fee%3A%3A~e!%7B_0%2B%7B0a%26%7D%23%3EW%25_%7B1%24%7C(z%40-%7D%2C%2C%5C%3B%7D%25%3Ae%3C&input=4%200%0A1%203%204%0A0%0A6%200%0A3%200%0A5

@qumonio Paying for box 2 gives you keys to 1, 3, and 4. Box 4 contains a key to 6 which, in turn, contains a key to 5.

brilliant. I think this puzzle is too much for me. congrats on the win :)

CJam (53 bytes)
Nq+N/:a::~:A,_m*_.&{,}$_{{_Af=e_|}:PA,*A,,^0-P0&!}#=,

This is rather too slow for the online interpreter.
Dissection
Nq+N/:a::~:A      e# Parse the input into arrays and store in A
,_m*_.&           e# Generate (with duplicates) a powerset of [0 1 ... n]
{,}$              e# Sort by size
_{                e# Create a copy and search for first index satisfying...
  {_Af=e_|}:P     e#   Store in P a block which does a reachability expansion
  A,*             e#   Apply it n times (no path can be longer than n)
  A,,^0-          e#   Invert to get the unreached nodes (except 0)
  P               e#   Apply P again to see what's reached from the unreached nodes
  0&!             e#   Check that it doesn't include [0]
}#
=,                e# Look up the powerset element at that index and find length

I received java.lang.OutOfMemoryError: Java heap space with your program.

@qumonio, it's not particularly scalable. I haven't tested it with inputs larger than the test inputs in the question, so I'm not sure how far it can go on a standard 1GB heap.

I was trying the 6 line here shown as an array in JS: [ [4,0], [1,3,4], [0], [6,0], [3,0], [5]] of course with the input style as shown in the original post.

@qumonio, on my computer it handles that input fine with only 128MB of heap, which is less than it has by default.

Haskell, 173 bytes
l is the one you wanna call.
Not sure whether I shouldn't use a pseudo-Map instead ([(Int,[Int])] instead of [[Int]]).
l=o[].map(map read).map words.lines
o[]b|0`notElem`concat b=0|0<1=1+minimum[o[n]b|n<-[1..length b],b!!(n-1)/=[]]
o(n:k)b=o(filter(/=0)(k++b!!(n-1)))(take(n-1)b++[]:drop n b)