Geohash my positions

Question

About geohash

Geohash is one of many encoding systems for geographic positions. Geohash positions have some advantages. It provides a short code instead of the two usual numbers for latitude and longitude.

The challenge

Given two numbers, the latitude and longitude, compute and return or print the geohash string of length 8. A longer geohash would give more accurate positions, here we use length 8. Latitudes and longitudes are given as floating point numbers (degrees). Latitudes are between -90 and +90 (south to north) and longitudes between -180 and +180 (west to east).

Algorithm with example

A geohash code is a base32 encoded bitstring. In this example the conversion goes the other way than the challenge, we convert geohash ezs42 into latitude and longitude. Geohashes uses a set of 32 digits represented by 5 bits. The 32 digits are 0 – 9 for the first 10 and the lower case letters between b – z except i, l and o for the next 22. That is: 0123456789bcdefghjkmnpqrstuvwxyz.

The first char in ezs42 is e which is at the 0-indexed position 13, which has the 5 bits 01101. The chars have these bits:

• e → 13 → 01101
• z → 31 → 11111
• s → 24 → 11000
• 4 → 4 → 00100
• 2 → 2 → 00010

When joining the bits we get 0110111111110000010000010.

Starting from left, the even bits (2nd, 4th, 6th, ...) are for latitude (101111001001) and the odd bits (1st, 3rd, 5th, ...) are for longitude (0111110000000).

With each bit we go left or right to narrow down the number by halving the range. The first bit of the longitude bits (0) are used to decide if the longitude is between -180 – 0 or 0 – 180. Bit 0 means we go left, that is -180 – 0. The next bit of the longitude decides if we chose -180 – -90 or -90 – 0. Since it's 1 here we go right for the next range: -90 – 0. For every bit we go left(0) or right(1) halving the min-max range. When all bits are spent, we return the mid position (average) of the last min and max.

We repeat for latitude, except now we start at choosing between -90 – 0 and 0 – 90 with the first bit.

The latitude for 101111001001 becomes +42.605.

The longitude for 0111110000000 becomes -5.603.

This example is taken from https://en.wikipedia.org/wiki/Geohash#Algorithm_and_example which has a more visual walk-through.

When encoding 0° (equator or zero meridian) you can choose between 01111... and 10000... The http://geohash.co/ site have chosen 01111...

Test cases

(+48.8583, +2.2945)      → u09tunqu    # Eiffel Tower
(+40.68925, -74.04450)   → dr5r7p62    # Statue of Liberty
(+29.9753, +31.1377)     → stq4s8cf    # The Great Sphinx at Giza
(-22.95191, -43.21044)   → 75cm2txp    # Statue of Christ, Brazil
(+71.17094, +25.78302)   → usdkfsq8    # North Cape
(+90, +180)              → zzzzzzzz    # North Pole
(-90, -180)              → 00000000    # South Pole
(+42.605, -5.603)        → ezs42s00    # Léon, Spain from example above

More tests can be created or checked with http://geohash.co/ and Google Maps.

(GPS positions are also often written as degrees, arcminutes and arcseconds. The position of the Eiffel Tower is latitude 48° 51' 29.88" N, longitude 2° 17' 40.20" E. For north (N) and east (E) positive numbers are used so we get position [48 + 51/60 + 29.88/3600, 2 + 17/60 + 40.20/3600] = [+48.8583, +2.2945]. Geohash codes can be stored and indexed in databases for quick proximity searches. Nearby positions share the same code prefixes, but edge cases needs to be dealt with. A single index search on the geohash code on one or a small set of code prefixes is normally much quicker than using two indexes, i.e. one for latitude and one for longitude.)

Answer 1

Python 3, 250 bytes

lambda b,a:(lambda l:"".join("0123456789bcdefghjkmnpqrstuvwxyz"[int("".join(map(str,l[i*5:][:5])),2)]for i in range(8)))(sum(zip(f(a,180,-180),f(b,90,-90)),()))
f=lambda a,u,l,p=20:p and([1]+f(a,u,(u+l)/2,p-1)if u+l<a*2else[0]+f(a,(u+l)/2,l,p-1))or[]

Try it online!

I think using named functions would probably be better... anyway. I don't have time to golf this further yet, so just posting it here first.

Answer 2

Perl 5 (-ap -MList::Util+sum), 136 bytes

@a=([-90,90],[-180,180]);map{$y=0;$a[--$|][$,=$F[$|]<($m=.5*sum@{$a[$|]})]=$m,$y+=$y+!$,for 0..4;$\.=(0..9,grep!/[ilo]/,b..z)[$y]}0..7}{

Try it online!

Verify all test cases

Answer 3

05AB1E, 64 63 61 42 41 bytes

90x‚R/>19o*î<Dd*b20jð0:SÅ=5ôJCžhA«„ŠÙaмsè

-19 bytes by porting @Neil's Charcoal answer, so make sure to upvote him as well!
-1 byte by taking the input in reversed order.

Try it online or verify all test cases.

Original 64 63 61 60 bytes answer:

εd©ˆ¾ƵΔN>÷‚19FÐÆÄ;UÅmyÄ‹®Qˆε¯θ®QNÊiXNi-ë+]¯Å=5ôJCžhA«„ŠÙaмsè

Try it online or verify all test cases.

Both take the input as [longitude, latitude] and output as a list of characters.

Explanation:

90                # Push 90
  x               # Double it to 180 (without popping)
   ‚              # Pair them together: [90,180]
    R             # Reverse it: [180,90]
     /            # Divide the (implicit) input-pair by these
      >           # Increase both by 1
       19o        # Push 2^19: 524288
          *       # Multiply both decimals by this 524288
           î      # Ceil both to an integer
            <     # Then decrease them by 1
                  # (ceil + decrement cannot be floor, if they already are integers)
             Dd   # Create a copy, and check if it's >=0 (1 if >=0; 0 if <0)
               *  # Multiply this to the pair (-1 becomes 0, else it stays the same)
b                 # Convert both integers to a binary string
 20j              # Pad them with leading spaces up to a length of 20
    ð0:           # Replace all spaces with 0s
       S          # Convert it to a flattened list of digits
Å=                # Shuffle this list ([a,b,c,d,e,f] → [a,d,b,e,c,f])
  5ô              # Split this into parts of size 5
    J             # Join each inner list together to a string
     C            # Convert each binary string to a base-10 integer
žh                # Push builtin "0123456789"
  A«              # Append the lowercase alphabet
    „ŠÙa          # Push dictionary string "oila"
        м         # Remove those characters from the string
         s        # Swap to get the list of integers at the top again
          è       # And (0-based) index them into the string
                  # (after which the list of characters is output implicitly

ε                 # Map both values in the pair to:
 d                #  Pop and check if it's non-negative (1 if >=0; 0 if <0)
  ©               #  Store this in variable `®` (without popping)
   ˆ              #  And pop and add it to the global_array
 ¾                #  Push 0
  ƵΔ              #  Push compressed 180
    N             #  Push the 0-based map-index
     >            #  Increase it by 1 to make it 1-based
      ÷           #  Divide the 180 by this (longitude=180; latitude=90)
       ‚          #  Pair it together with the 0
 19F              #  Loop 19 times:
    Ð             #   Triplicate the current pair
     ÆÄ           #   Pop one, and get the absolute difference
       ;          #   Halve this
        U         #   Pop and store this halved difference in variable `X`
     Åm           #   Pop another copy, and take its average
         ‹        #   Check that it's smaller than
       yÄ         #   the absolute value of the current map value
                  #   (1 if truthy; 0 if falsey)
          ®Q      #   Check if this is equal to `®`
                  #   (this will invert the boolean for negative values)
            ˆ     #   Pop and add this to the global_array
     ε            #   Map over the third pair:
      ¯θ          #    Push the last value of the global_array
        ®Q        #    Check it this is equal to `®`
                  #    (to invert for negative values again)
          NÊi     #    If this is NOT equal to the 0-based inner map-index:
             X    #     Push variable `X`
              Ni  #     If the 0-based inner map-index is 1:
                - #      Subtract `X` from the current value we're mapping over
               ë  #     Else:
                + #      Add it instead
]                 # Close both if-statements, both maps, and the loop
 ¯                # Push the global_array
Å=5ôJCžhA«„ŠÙaмsè # Same as above

See this 05AB1E tip of mine (sections How to use the dictionary? and How to compress large integers?) to understand why „ŠÙa is "oila" and ƵΔ is 180.

Answer 4

Charcoal, 65 bytes

Ｆ²⊞υ⌈×Ｘ²¦¹⁹⊕∕Ｎ×⁹⁰⊕ιＵＭυ◧⎇‹ι²ω⍘⊖ι !²⁰⭆⪪⭆²⁰⭆⮌υ§λι⁵§⁺⭆χλΦβ¬№ailoλ⍘ι !

Try it online! Link is to verbose version of code. Explanation:

Ｆ²⊞υ⌈×Ｘ²¦¹⁹⊕∕Ｎ×⁹⁰⊕ι

Input both numbers. Divide the first by 90 and the second by 180, then increment both, then multiply by 524288, then round up.

ＵＭυ◧⎇‹ι²ω⍘⊖ι !²⁰

If the result is greater than 2, then decrement and convert to base 2 using a custom digit set, and pad to 20 "digits". (This doesn't work for 0 because it would become negative and it doesn't work for 1 because of a bug in the version of Charcoal on TIO.)

⭆⪪⭆²⁰⭆⮌υ§λι⁵§⁺⭆χλΦβ¬№ailoλ⍘ι !

Shuffle the bits, split into groups of five, decode each group from base 2 using the same digit set, then look up the digit in a table of digits and letters excluding ailo.

Answer 5

R, 149 147 144 128 bytes

Edit: -16 bytes thanks to Giuseppe, by using more code-efficient matrix operations (rbind, %*%)

function(l,m,d=function(x)((x+180)*5825.422)%/%2^(20:1)%%2)c(0:9,letters[-c(1,3:5*3)])[1+2^(4:0)%*%matrix(rbind(d(m),d(l*2)),5)]

Try it online!

Outputs vector of characters.

How? (before Giuseppe's golfing)

geohash=
function(l,m,               # l=latitude, m=longitude
d=function(x)               # d=helper function to calculate bits from lat or long
  ((x+180)*5825.422)        #   scale by 5825.422 == 2^20/180
  %/%2^(20:1)%%2            #   convert to binary bits
)
c(0:9,                      # encode using digits 0..9, joined to
letters[-c(1,9,12,15)])     # letters except a,i,l,o
[1+                         # 1-based indexing
  colSums(                  # sums of each column of matrix
                            # columns represent each 5-bit character
    matrix( ... ,5,8)       # format numbers into matrix with 5 rows & 8 columns
      t(                    # using transpose of
        matrix(             # matrix of
          c(d(m),d(l*2)),,2)# longitude bits, latitude bits x2, in rows
      )
    *2^(4:0))]              # times powers of 2 to convert sums to numbers

Answer 6

Python 3, 174 bytes

f=lambda a,b,c='',n=1,x=0,y=0,z=(-45,45):n<7**7and f(a,b,c+'%i%i'%(b>y,a>x),n*2,x+z[a>x]/n,y+z[b>y]/n*2)or c and'0123456789bcdefghjkmnpqrstuvwxyz'[int(c[:5],2)]+f(*z,c[5:],n)

Try it online!

Keeps track of the average values x and y for latitude and longitude, respectively. The function increases or decreases these values by steps of 45/n and 90/n, where n is equal to 2**(current cycle). The comparisons are stored in the bit-string c. This continues for 20 cycles, until n exceeds 2**19, which is approximated by 7**7. When this value is reached, it converts the c to the final result.