# Question
Title: Test if a given number is a Vampire Number
*EDIT:* In the interest of increasing the complexity, i've added more to the challenge.

> In mathematics, a vampire number (or true vampire number) is a composite natural number v, with an even number of digits n, that can be factored into two integers x and y each with n/2 digits and not both with trailing zeroes, where v contains precisely all the digits from x and from y, in any order, counting multiplicity. x and y are called the fangs.

More about Vampire Number

Pseudovampire numbers

> Pseudovampire numbers are similar to vampire numbers, except that the fangs of an n-digit pseudovampire number need not be of length n/2 digits. Pseudovampire numbers can have an odd number of digits, for example 126 = 6×21.

### Input

Accept Numbers from command line or stdin

### Output

* "1260 = 21 * 60" *(smaller fang first if the number is a Vampire.)*
* "1261 is not a Vampire Number." *(if the number is not a Vampire number)*
* "126 = 6 * 21". *(if the number is a Pseudovampire number)*

EDIT: If the number has multiple fangs, display it so.

```
x = fang1a * fang1b = fang2a * fang2b

```

# Answer
> 5 votes
# Python - 188 chars

Doesn't do Pseudovampire numbers

```
from itertools import*
n=input()
a=[]
for i in map("".join,permutations(`n`)):x,y=int(i[::2]),int(i[::-2]);a+=[(x,y)]*(x*y==n)
print n,a and"=%s*%s"%min(a)or"is not a Vampire Number"

```

# Answer
> 4 votes
# Ruby, 190 chars

```
o=[]
[*x.chars].permutation{|r|a=r.pop(x.size/2).join.to_i
r=r.join.to_i
o|=[[a,r]]if a<=r&&a*r==x.to_i}
puts x+(o.any? ? o.map{|i|" = "+i*" * "}*"":" is not a Vampire Number.")

```

---
Tags: code-golf, math
---


title: Nokia mystery puzzle

text:
# Question
Title: Nokia mystery puzzle
A friend sent me this puzzle. I'm pretty sure solving it will require some programming. Can anyone crack it? The original is here in case of encoding issues in the past below.

```
Did you know that...
List of prime numbers include 2 as only even number, but not 1 which is equally not divisible by any other number than itself and 1?
Indexes in most of the programming languages start from 0?
Random mess is often considered as just "life"?
Prime bits of life include open position in Nokia?
Start here:
QnšmzFyN\�Li�B§TJ�vhgUEg�XbDMb¯o�ag�wUF�Iv¶u²nGTbf�vFc�]n¡vbD^Q@utJjMthn wŸ�B�CiŸ`yuftlyF]^Qvfh¹ºK[fF�wXuHdojG�YftvTP�OwmU�gzF�zuYQ�Z[gEn�wjU�MmŽ`FDtœPC�Sw`�Raw^»DuFlVvUdEa@uiluigJQhgtc[ŒGVcBSUL�OtnouŠ�KwGTI hEtwžgtEAtl§wuZoE�Qvvc[wZ@¢Pu\T�fo[RXtGVU¶wCdySwU[{w��wGX\�\v^ŽBFS_v^^@yXPmctvPcoWvHlfBwI�FJGu�AbWcnuªOv@[j�tu@GwBNB[tX�USioimTC¶KQŸbv\iiYK£DQ�[Ich`Oš[vcwaOyJ\RoŸP�tMQvtEvLKºWbwBvtvQžf�kXv°A\TA¬�PPwU�eTT[NAIAFhvti{WOga{`H�tRJ{a`BMHUI[ZI`lIDb\BA�fa`mtd€gK\@BwCTeR�³ww�NFDCGvfQSz£t`FBZ¬wMevA^Rv¢^iSct¢Bk�\zjNBv¢tRbIwNv\¹E³tiBHxwCH«\mtt`xgNBu@hJŸkeZbQŠaaF^o_YEcLii£F`tKjU_wHt��w®wDvO^²¶[DDvAvP�uk»gAOtx]JHRuWvcu�dQmŠn_\guZD]DlHh[€DGvfb@_X¬TMt^Xun@F«twOMTIv�]ZjvKSTwdRicvxG\K�¯mStILhUvOjwb^t�xi_VJUuRwh§v`Wg]W{JoŽh]uvIdw�@QXZ]«ŽinWJ�R_ZtwB¶Vu_JStI@UUMxT`²VYyuV�l\eW]lOghv]²NP\i�xySiuJvZG±ut�`\jMEtVZuv�twv±o_Awu�vn�oŽzYTM^fEt\bWH�M�lGilw�BI²tPgTvaE`h±e�x\aafvBNmt[RŠn£hjOBEUtmhNHtAuVHP�va_uOn�\UKnuBAHW_waFwH{WLu\ZRvT[nmvv«B]Yj�JbF¹BgyDNcv^`@iAwwlweFYlwe�§fk@mnPNh�Fg\`Di[�{j¬enk�Jw{Wh^[�cYO]`MWu®�oclQTg`X�VbnXlK\\ŠMuvAw]_^®SvTA�ZSmwB`PUwYw�»\utCnl[JGcuWVTXo€¬M¡aoPuvjR[jvV[�C_zM�nUn�wP«t¿IMVtuhwFJXvº@t^UEtIhGbCXt]bVSE€CMuZktmH_uvtwuIt¹vtKy{wNC«YivUM[BG�ntCJ^aBBFdhfNlPoBE@kuTe�VC�kRwwhZdTtfnt�^v^mg�cPeh�§Au°^BtND�Jd[f\th§`jNwRvFHLu@MNwvuSR`CdSE]vaaw_wPIvRjw^HXDi°fQ�wIfNTS`ttSA¢jv XX�EP@lbDALWdzkuG€_VQvmjIX�EkTummeC³iuZokw�]uQfMcBu�SXH_Whtuv^SjyejxoEtœwStoD�xVeaOA�jtJBa_KDPwtK^\ounwfZKDDuL@[vhIDI»tvvJc\cµvWe�FPvv�beWKUtaOtvA�DMTLcPh]nDD[Qfc�R�vwštAvhfWEv^hEZPuvaCNDBQtwdvuaw@�D@dPCG�wIdttYMKvau²wQnm^mOuvaZNB�viKBvkuDj¶BuVb_§hGtkEZvSc�tttµ_GxwvGwŒ]U�[{KJcv�h�ŒKv¯vRQIPHOivFG©LtXvtljuIB\^v�zDiPBgtcm�@tUdetwYhQuvK§¥t[�HONFwcXDxH�w`t_J`�tcHXM`vO°wkQQttw§@t£uvI[TTRgvŠbf¡AJoWoRfT�dP�g�wi�S{wYYh¢uleHR@\�KnK³u\vNcx{FHkvwTMEwP�gngEvutdGOE[teWDµwKOdG�G^�wEGARcNYutf�tvmdutv@TvvF�QHkX�]tPbvšlwvVJwuKu�So@o©]LNLx�btvXGDdlLz@eVzCltvwvt�Vb£L²wPXh_viyOw[XEkSvEJdIvmVJuw�@VGTw�tjKhjv�uWmEUhI®TtwRiuŒFZ�lYtuH\\F�Ufšn®YSu�dšOk�xuVdDgmOIEBUdw@]kvtEYAt^�NutW®®ebtMhv\kfljk@±nLgEB[�fImIKt[[�jo¯OnMtwcfgKcŒuEEªvvN\�tEw`GvNQ[gUK_euho�oY[�WTKMBatvl^twJ¿cK^lAaHw�M_uFK�DvtfNªKw€šKnIv@FiI�vj°S±Ru@wid»Qt\uRvZDvZjkwuFQVH\�zW[�hMUUkNe^�famV�TGw[hJovbtugIw`t`BDwl�tlVwQmtQ^YnOA¡StuCiv�]µ€BJj`n�]BeYi[PLtY@mAoPxHxI�SwIiJ�LA±uMhPm[oPG¯OUHuKvlIbwNttX�w_k]gwmL_`m�Ef]AVvwuPiwNT±Œfw¢`XAAKuwBvkLVXNix®]lVGSo�b]XS�[foSn�]Hu®md[Lf�QJcY�ZtkŸBtjtvPH�MfYBFnLYty_dBTQzdwT@W�[uvFwama[oj@Zh�IBmYtPJEie¹�Bw]\wOwŠNdfNul^zSwwYuOu^u]`nm¬vBBvmDP^ZGRgtIxcZYbn�Dn\D¥`otŽi^E_BvD]_w u\w�EvimvuPGwH�ST^otQ¥u]�KU¥W[CR¯l@vjt€^ATNu¥HVªTvC�ifzwteG[[`gtFJŠK¡tjt�MNbkuSuMDU£lt^[E�tiLc{ZhFu`RX]tdXvYuXuTdAKvuaxPXfi[Wg]wAeukeQkuP�utvvVBExOjgi{ad`HtaiŒuvo^u@lN©Awbub\kDWµ\»WYuRYZFHR{QvojtyNbtvwDOIv_YnAu^wttunyu[VCOQWE^dTuwtuYUwl^�VXlGž�NNFk��``KQV\NWHG] ^RNkRVQw\JAO@@wdV�ev«tc[vLAZNMoYZQk�H�uFBOdt]c]ADKDfvfC[�u`®\tSX�vUDE^vu_e�JwOhmd]EMwiRHmUH]\W°vtHzWµ\@j]^mh{MAxnAPu\QuvQuekthoµRTwNX`uTcŸS_Bc�SZwJJwe_cye^ªNtwv�Wuu�ev�IQ¹B�Xt]Q_gbVkmXwh_XUL±»tvvId`wAgX�]bžmVumB«DlJ_G�D@egUoPtu�@i[S¥e\ŽFIMFweI`ut_wIOD«vZ[_wiGuVZKFk±PDG�Aw@^`vAoS{nvw``kXUSuuZWù

```

# Answer
> 4 votes
## Python - 132 chars

Data is read from stdin, starting from the "Qn..."

```
I=raw_input()
print("%X"%int("".join(`ord(I[x/8])>>(7-x%8)&1`*all(x%f for f in range(2,x))for x in range(2,24024)),2)).decode('hex')

```

---
Tags: binary, puzzle-solver
---


# Question
Title: Freely available books for code golfing?
Can you recommend any freely available books about code golfing in general and especially in Java and C++?

# Answer
There are at least two books about golfing:

* "Short Coding" by Ozy (only available in Japanese I think, search for it on www.amazon.co.jp)
* The Perlgolf History book, available here.

Other recommended reading:

* Andrew Savige's (eyepopslikeamosquito) articles on golf, accessible from his node on perlmonks
* The language specific forums over on codegolf.com
* The solutions to finished challenges on golf.shinh.org (look for "post-mortem").
> 9 votes

# Answer
Mark Byers maintains a golfing tips site. It's not a book per se, but, you may find some gems there!
> 7 votes

# Answer
When it comes to golfing in Java, it's not to be recommended.

Actually, I would go so far as to say (paraphrasing E. W. Dijkstra) that it cripples the mind, and therefore should be regarded as a criminal offense.

If you insist on doing codegolf in Java, all the basic stuff you need is found in java.util.Scanner (parsing input), java.math.BigInteger, and java.lang.String. In addition, the syntax for regexes and print formatting will come in handy.
> 7 votes

# Answer
"the zen of optimization" by Michael Abrash has a few sections on optimizing assembly code for size. I remember there was a chapter where he squeezed every spare byte out of a ridiculously small sort function.
> 4 votes

---
Tags: code-golf, tips
---


title: Decryption by pattern analysis

text:
# Question
Title: Decryption by pattern analysis
You are given an encrypted string, encrypted using a very simple substitution cipher.

**Problem**

You do not know what the cipher is but you do know the ciphertext is English and that the most frequent letters in English are *etaoinshrdlucmfwypvbgkqjxz* in that order. The only allowed characters are uppercase letters and spaces. You can do basic analysis - starting from single letters, but you can migrate onto more complex multi-letter analysis - for example, U almost always follows Q, and only certain letters can come twice in a row.

**Examples**

```
clear : SUBMARINE TO ATTACK THE DOVER WAREHOUSE AND PORT ON TUESDAY SUNRISE
cipher: ZOQ DUPAEYSRYDSSDXVYSHEYNRBEUYLDUEHROZEYDANYKRUSYRAYSOEZNDMYZOAUPZE

clear : THE QUICK BROWN FOX BEING QUITE FAST JUMPED OVER THE LAZY DOG QUITE NICELY
cipher: TNAEPDHIGEMZQJLEVQBEMAHL EPDHTAEVXWTEODYUASEQKAZETNAERXFCESQ EPDHTAELHIARC

clear : BUFFALO BUFFALO BUFFALO BUFFALO BUFFALO BUFFALO BUFFALO
cipher: HV  WRPDHV  WRPDHV  WRPDHV  WRPDHV  WRPDHV  WRPDHV  WRP

```

**Challenges**

See if you can decrypt the text in each of these ciphers:

* `SVNXIFCXYCFSXKVVZXIHXHERDXEIYRAKXZCOFSWHCZXHERDXBNRHCXZR RONQHXORWECFHCUH`
* `SOFPTGFIFBOKJPHLBFPKHZUGLSOJPLIPKBPKHZUGLSOJPMOLEOPWFSFGJLBFIPMOLEOPXULBSIPLBP` `KBPBPWLIJFBILUBKHPGKISFG`
* `TMBWFYAQFAZYCUOYJOBOHATMCYNIAOQW Q JAXOYCOCYCHAACOCYCAHGOVYLAOEGOTMBWFYAOBFF` `ACOBHOKBZYKOYCHAUWBHAXOQW XITHJOV WOXWYLYCU`
* `FTRMKRGVRFMHSZVRWHRSFMFLMBNGKMGTHGBRSMKROKLSHSZMHKMMMMMRVVLVMPRKKOZRMFVDSGOFRW`

I have the substitution matrices and cleartext for each, but I will only reveal them if it becomes too difficult or someone doesn't figure it out.

**The solution which can decrypt the most messages successfully is the winner. If two solutions are equally good, they will be decided by vote counts.**

# Answer
## Python

I've figured out all the secret phrases, but I won't post them here. Run the code if you care.

The code works by picking a space character, enumerating all possible substitutions for each word, then searching for compatible substitutions. It also allows for some out-of-lexicon words to deal with misspellings in the cleartext :)

I used a large lexicon (~500K words) from http://wordlist.sourceforge.net/.

```
import sys,re

# get input
message = sys.argv[1]

# read in lexicon of words
# download scowl version 7.1
# mk-list english 95 > wordlist
lexicon = set()
roman_only = re.compile('^[A-Z]*$')
for word in open('wordlist').read().upper().split():
  word=word.replace("'",'')
  if roman_only.match(word): lexicon.add(word)

histogram={}
for c in message: histogram[c]=0
for c in message: histogram[c]+=1
frequency_order = map(lambda x:x[1], sorted([(f,c) for c,f in histogram.items()])[::-1])

# returns true if the two maps are compatible.
# they are compatible if the mappings agree wherever they are defined,
# and no two different args map to the same value.
def mergeable_maps(map1, map2):
  agreements = 0
  for c in map1:
    if c in map2:
      if map1[c] != map2[c]: return False
      agreements += 1
  return len(set(map1.values() + map2.values())) == len(map1) + len(map2) - agreements

def merge_maps(map1, map2):
  m = {}
  for (c,d) in map1.items(): m[c]=d
  for (c,d) in map2.items(): m[c]=d
  return m

def search(map, word_maps, outside_lexicon_allowance, words_outside_lexicon):
  cleartext = ''.join(map[x] if x in map else '?' for x in message)
  #print 'trying', cleartext

  # pick a word to try next
  best_word = None
  best_score = 1e9
  for (word,subs) in word_maps.items():
    if word in words_outside_lexicon: continue
    compatible_subs=0
    for sub in subs:
      if mergeable_maps(map, sub): compatible_subs += 1
    unassigned_chars = 0
    for c in word:
      if c not in map: unassigned_chars += 1  #TODO: duplicates?
    if compatible_subs == 0: score = 0
    elif unassigned_chars == 0: score = 1e9
    else: score = 1.0 * compatible_subs / unassigned_chars   # TODO: tweak?
    if score < best_score:
      best_score = score
      best_word = word
  if not best_word:  # no words with unset characters, except possibly the outside lexicon ones
    print cleartext,[''.join(map[x] if x in map else '?' for x in word) for word in words_outside_lexicon]
    return True

  # use all compatible maps for the chosen word
  r = False
  for sub in word_maps[best_word]:
    if not mergeable_maps(map, sub): continue
    r |= search(merge_maps(map, sub), word_maps, outside_lexicon_allowance, words_outside_lexicon)

  # maybe this word is outside our lexicon
  if outside_lexicon_allowance > 0:
    r |= search(map, word_maps, outside_lexicon_allowance - 1, words_outside_lexicon + [best_word])
  return r

for outside_lexicon_allowance in xrange(3):
  # assign the space character first
  for space in frequency_order:
    words = [w for w in message.split(space) if w != '']
    if reduce(lambda x,y:x|y, [len(w)>20 for w in words]): continue  # obviously bad spaces

    # find all valid substitution maps for each word
    word_maps={}
    for word in words:
      n = len(word)
      maps = []
      for c in lexicon:
        if len(c) != n: continue
        m = {}
        ok = 1
        for i in xrange(n):
          if word[i] in m:                      # repeat letter
            if m[word[i]] != c[i]: ok=0; break  # repeat letters map to same thing
          elif c[i] in m.values(): ok=0; break  # different letters map to different things
          else: m[word[i]]=c[i]
        if ok: maps.append(m);
      word_maps[word]=maps

    # look for a solution
    if search({space:' '}, word_maps, outside_lexicon_allowance, []): sys.exit(0)

print 'I give up.'

```
> 9 votes

# Answer
## PHP (Incomplete)

This is an incomplete PHP solution which works using the letter frequency information in the question plus a dictionary of words matched with regular expressions based on the most reliable letters in the given word.

At present the dictionary is quite small but with the appropriate expansion I anticipate that results would improve. I have considered the possibility of partial matches but with the current dictionary this results in degradation rather than improvement to the results.

**Even with the current, small dictionary I think I can quite safely say what the fourth message encodes.**

```
#!/usr/bin/php
<?php

    if($argv[1]) {

        $cipher = $argv[1];

        // Dictionary
        $words = explode("/", "the/to/on/and/in/is/secret/message");
        $guess = explode("/", "..e/t./o./a../i./.s/.e..et/.ess..e");

        $az = str_split("_etaoinshrdlucmfwypvbgkqjxz");

        // Build table
        for($i=0; $i<strlen($cipher); $i++) {
            $table[$cipher{$i}]++;
        }
        arsort($table);

        // Do default guesses
        $result = str_replace("_", " ", str_replace(array_keys($table), $az, $cipher));

        // Apply dictionary
        $cw = count($words);
        for($i=0; $i<$cw*2; $i++) {
            $tokens = explode(" ", $result);
            foreach($tokens as $t) {
                if(preg_match("/^" . $guess[$i%$cw] . "$/", $t)) {
                    $result = deenc($words[$i%$cw], $t, $result);
                    echo $t . ' -> ' . $words[$i%$cw] . "\n";
                    break;
                }
            }
        }

        // Show best guess
        echo $result . "\n";

    } else {

        echo "Usage: " . $argv[0] . " [cipher text]\n";

    }

    // Quick (non-destructive) replace tool
    function deenc($word, $enc, $string) {
        $string = str_replace(str_split($enc), str_split(strtoupper($word)), $string);
        $string = str_replace(str_split($word), str_split($enc), $string);
        return strtolower($string);
    }

?>

```
> 1 votes

---
Tags: popularity-contest, cryptography, test-battery
---


title: Binary search ("bisect") tool

text:
# Question
Title: Binary search ("bisect") tool
Implement the binary search algorithm as used to identify the source code revision that breaks a computer software program. Your tool should take two arguments specifying the earliest and latest numbered revision to search (both positive integers), and you have two options for making comparisons:

1. Execute the shell command `./test N`, where *N* is the revision number. If the test passes (*i.e.* the revision is good), it will return exit code 0.
2. Call the function `test(N)`, which will return `true` if the test passes, `false` otherwise.

Standard output must be the number of the first bad revision, and try to make your tool's source code as short as possible. Enjoy!

# Answer
## Ruby - 92 82 62 60 characters

Iterative is way shorter, but nowhere near as cool as tail recursive.

```
l,h=$*.map &:to_i
test(m=(l+h)/2)?l=m+1:h=m-1 while l<=h
p l

```

The old tail recursive method for reference

```
b=proc{|l,h|h<l ?l:(m=(l+h)/2;test(m)?l=m+1:h=m-1;redo)}
puts b[*$*.map(&:to_i)]

```

### Testing script

Uses a little magic to inject the `test` function and runs a file consisting of purely the above code.

```
low = Random.rand(100)
mid = low + Random.rand(1e25)
high = mid + Random.rand(1e50)

File.open('./bisect-test-method.rb','w') do |file|
  file << "def test(value)
             value < #{mid}
           end
          "
end

puts "Using input:"
puts "  low=#{low}"
puts "  high=#{high}"
puts "  first_bad=#{mid}"
puts "Output: #{`ruby -r ./bisect-test-method golf-bisect.rb #{low} #{high}`}"

```

Output:

```
Using input:
  low=4
  high=75343785543465286986587973836706907796015092187720
  first_bad=5013102893257647460384884
Output: 5013102893257647460384884

```
> 4 votes

# Answer
# Python, 64 chars

This one is recursive, so will overflow the stack for really large input

```
01234567890123456789012345678901234567890123456789012345678901234567890
|         |         |         |         |         |         |         |
 B=lambda L,H:H>L+1 and B(*[L,L/2+H/2,H][test(L/2+H/2):][:2])or H

```

test run

```
def test(n):
    print "testing ", n
    return n<66

L,H=10,1000

B=lambda L,H:H>L+1 and B(*[L,L/2+H/2,H][test(L/2+H/2):][:2])or H

print B(L,H)

```

outputs

```
testing  505
testing  257
testing  133
testing  71
testing  40
testing  55
testing  62
testing  66
testing  64
testing  65
66

```
> 5 votes

# Answer
## Python - 77 chars

Abusing the python bisect module. L is the low value, H is the high value

```
class B:__getitem__=lambda s,n:test(n)
import bisect as b
b.bisect(B(),0,L,H)

```

here is a test run

```
def test(n):
    print "testing ", n
    return n>66
L,H=10,1000

class B:__getitem__=lambda s,n:test(n)
import bisect as b
b.bisect(B(),0,L,H)

```

outputs

```
testing  505
testing  257
testing  133
testing  71
testing  40
testing  56
testing  64
testing  68
testing  66
testing  67

```

Explanation:

Here is how bisect is defined. Basically it expects a list and decides whether to bisect up or down based on the value it finds by looking at `a[mid]`. This calls `__getitem__` on `a`, which instead of being a list, is a class that I have defined myself.

```
def bisect_right(a, x, lo=0, hi=None):
    """Return the index where to insert item x in list a, assuming a is sorted.

    The return value i is such that all e in a[:i] have e <= x, and all e in
    a[i:] have e > x.  So if x already appears in the list, a.insert(x) will
    insert just after the rightmost x already there.

    Optional args lo (default 0) and hi (default len(a)) bound the
    slice of a to be searched.
    """

    if lo < 0:
        raise ValueError('lo must be non-negative')
    if hi is None:
        hi = len(a)
    while lo < hi:
        mid = (lo+hi)//2
        if x < a[mid]: hi = mid
        else: lo = mid+1
    return lo

bisect=bisect_right

```
> 2 votes

# Answer
## Python - 70 chars

```
def B(L,H):
 while L+1<H:M=L+H;L,H=[L,M/2,H][test(M/2):][:2]
 return L

```

test run

```
def test(n):
    print "testing ", n
    return n<66
L,H=10,1000

def B(L,H):
 while L+1<H:M=L+H;L,H=[L,M/2,H][test(M/2):][:2]
 return L

print B(L,H)

```

outputs

```
testing  505
testing  257
testing  133
testing  71
testing  40
testing  55
testing  63
testing  67
testing  65
testing  66
65

```
> 2 votes

---
Tags: code-golf
---


title: Shortest path in a graph

text:
# Question
Title: Shortest path in a graph
Write a program to take a graph (from either standard input or a file, your choice) and find a shortest path in the graph.

Graphs are specified using the following format:

```
A---S   F--T
|  / \  |
| /   5 0
|/     \|
D----3--E

    A-Z: nodes in the graph
   -|/\: edges in the graph
    0-9: weights on the edges
<space>: all the holes

```

All edges are undirected and lie along one of the 8 cardinal directions (i.e., no bends). Edges may optionally contain a weight from 0 to 9. The weight will not be on the last symbol that connects the edge to a node (i.e. edges need to have at least 3 symbols to contain a weight). Unweighted edges have a default weight of 1.

Your code should compute the shortest path between nodes `S` and `T` and print the length and the path, like this:

```
5:SDEFT

```

Shortest correct program wins.

# Answer
> 5 votes
Here's my code, 494 characters in python:

```
import sys,re
m=sys.stdin.readlines()
Z=lambda c,s:re.findall(r'(\w)%s+(\d*)[^\w]*(\w)'%c,''.join(x*2for x in s))
T=lambda n:''.join(x for a in map(None,*n)for x in a if x)
E=Z('-',''.join(m))+Z('\\|',T(m))+Z('/',T(' '*m.index(s)+s for s in m))+Z('\\\\',T(' '*m[::-1].index(s)+s for s in m))
E+=[x[::-1]for x in E]
S={}
for x in E:S[x[0]]=1e9
S['S']=0
P={}
for i in E:
 for x,w,y in E:
  w=int('1'+w)%10
  if S[y]>S[x]+w:S[y]=S[x]+w;P[y]=x
i=p='T'
while i!='S':i=P[i];p=i+p
print'%d:'%S['T']+p

```

---
Tags: code-golf, graph-theory, path-finding
---


title: Slot Machine Hacker

text:
# Question
Title: Slot Machine Hacker
Problem: Slot Machine Hacker from Facebook Hacker Cup 2011 Round 1B

Goal: Shortest code in your favourite language using stdin/stdout. You cannot assume `getRandomNumber` is defined, i.e. your solution has to include a potentially golfed version as a function or in some other way.

Reference solution: on SO \[I chose mine, because it uses stdin/stdout and I'm unsure about dave's solution.\]

Problem text follows:

You recently befriended a guy who writes software for slot machines. After hanging out with him a bit, you notice that he has a penchant for showing off his knowledge of how the slot machines work. Eventually you get him to describe for you in precise detail the algorithm used on a particular brand of machine. The algorithm is as follows:

```
int getRandomNumber() {
  secret = (secret * 5402147 + 54321) % 10000001;
  return secret % 1000;
}

```

This function returns an integer number in \[0, 999\]; each digit represents one of ten symbols that appear on a wheel during a particular machine state. **secret** is initially set to some nonnegative value unknown to you.

By observing the operation of a machine long enough, you can determine value of **secret** and thus predict future outcomes. Knowing future outcomes you would be able to bet in a smart way and win lots of money.

## Input

The first line of the input contains positive number **T**, the number of test cases. This is followed by **T** test cases. Each test case consists of a positive integer **N**, the number of observations you make. Next **N** tokens are integers from 0 to 999 describing your observations.

## Output

For each test case, output the next 10 values that would be displayed by the machine separated by whitespace. If the sequence you observed cannot be produced by the machine your friend described to you, print `"Wrong machine"` instead. If you cannot uniquely determine the next 10 values, print `"Not enough observations"` instead.

## Constraints

* T = 20
* 1 ≤ N ≤ 100
* Tokens in the input are no more than 3 characters long and contain only digits 0-9.

Example input

```
5
1 968
3 767 308 284
5 78 880 53 698 235
7 23 786 292 615 259 635 540
9 862 452 303 558 767 105 911 846 462

```

## Example output

```
Not enough observations
577 428 402 291 252 544 735 545 771 34
762 18 98 703 456 676 621 291 488 332
38 802 434 531 725 594 86 921 607 35
Wrong machine

```

# Answer
# Python, 293 chars

```
import sys
n=1e7+1
for s in[map(int,x.split())for x in sys.stdin][1:]:
 Q=[]
 for i in range(s[1],n,1e3):A=[i];R=[A.append((A[-1]*5402147+54321)%n)or A[-1]%1e3for x in[0]*8+s];Q+=[R[-10:]]*(R[:-10]==s[2:])
 print Q and["%d "*10%tuple(Q[0]),"Not enough observations"][len(Q)>1]or"Wrong Machine"

```
> 3 votes

# Answer
# Python, 316 characters

```
C=10**7+1
G=lambda:(s*5402147+54321)%C
import sys
I=map(int,sys.stdin.read().split())[1:]
while I:
 n=I[0]+1;S=range(C)
 for x in I[1:n]:S=[G()for s in S if s%1000==x]
 if len(S)-1:V="Not enough observations"if S else"Wrong machine"
 else:
  s=S[0];V=""
  for i in range(10):V+="%d "%(s%1000);s=G()
 print V;I=I[n:]

```
> 2 votes

---
Tags: code-golf
---


title: Shortest URL regex match in JavaScript

text:
# Question
Title: Shortest URL regex match in JavaScript
Create the shortest regular expression that will roughly match a URL in text when run in JavaScript

Example:

```
"some text exampley.com".match(/your regular expression goes here/);

```

The regular expression needs to

* **capture** all valid URLS that are for http and https.
* not worry about not matching for URL looking strings that aren't actually valid URLS like `super.awesome/cool`
* be valid when run as a JavaScript regex

**Test criteria:**

Match:

Not Match:

* example
* super/cool
* Good Morning
* i:can
* hello.

Here is a test that might help clarify a bit http://jsfiddle.net/MikeGrace/gsJyr/

I apologize for the lack of clarity, I hadn't realized how awful matching URLs was.

# Answer
> 1 votes
```
/.+\.\w\w.*/

```

doesn't match 3 strings that it shouldn't, matches almost anything else ;)
**upd:** it still doesn't match all 5

# Answer
> 14 votes
This one works:

```
var re = /(^|\s)((https?:\/\/)?[\w-]+(\.[\w-]+)+\.?(:\d+)?(\/\S*)?)/gi;

/*
(^|\s)                            : ensure that we are not matching an url
                                    embeded in an other string
(https?:\/\/)?                    : the http or https schemes (optional)
[\w-]+(\.[\w-]+)+\.?              : domain name with at least two components;
                                    allows a trailing dot
(:\d+)?                           : the port (optional)
(\/\S*)?                          : the path (optional)
*/

```

Passes the tests at http://jsfiddle.net/9BYdp/1/

Also matches:

* example.com. (trailing dot)
* example.com:8080 (port)

# Answer
> 5 votes
This obviously doesn't do what you intend, but it meets your criteria:

```
 /.*/

```
* **"match all valid URLS that are for http and https."**

yep, definately will match.
* **"not worry about not matching for URL looking strings that aren't actually valid URLS like 'super.awesome/cool'"**

yeah, sure, there will be *lots* of false positives, but you said that doesn't matter.
* **be valid when run as a JavaScript regex**

sure as eggs works as you say it should.

If this result is NOT a right answer, then you need to be more selective with your criteria.

In order to be a rule that works as you intend, you actually **do** need to implement a full RFC compliant matcher, and a full RFC compliant matcher will "worry about not matching".

So, in terms of "permit not matching", you need to specify **exactly** which deviations from RFC are permissible.

Anything else, and this whole exercise is a sham, because people will just write whatever works for them, or how they like it, and sacrifice "making any sense" in favour of being short ( like I did ).

### On your update

The most Naïve regex I can come up with that matches (and captures) all your pasted examples so far is:

```
/(\S+\.[^/\s]+(\/\S+|\/|))/g;

```

Its quite simple in nature, and assumes only 3 basic forms are possible.

```
x.y
x.y/
x.y/z

```

`z` can be anthing not whitespace. `x` can be anything not whitespace. `y` can be anything that is neither whitespace or a '/' character.

There are a lot of things that will be valid to this rule, lots, but they'll at least *look* like a valid URI to a human, they just won't be specifications compatible.

eg:

```
hello.0/1  # valid
1.2/1 # valid
muffins://¥.µ/€  # probably valid

```

I think the sane approach is to extract things that are likely to be URI's, then validate them with something stricter, I'm looking at working out how to use the browsers URI class to validate them =).

But you can see the above reasoning working on this sample here: http://jsfiddle.net/mHbXx/

# Answer
> 1 votes
```
/https?\:\/\/\w+((\:\d+)?\/\S*)?/

```

Try that.

I'm including the leading and trailing slashes that delimit the regular expression, so hopefully that doesn't hurt my character count!

This pattern limits the protocol to either http or https, allows for an optional port number, and then allows any character except whitespace.

---
Tags: code-golf, javascript, regular-expression
---


# Question
Title: Five aligned points and some of the pairwise distances. Infer the relative positions!
Given five points on a straight line such that their pairwise distances are 1,2,4, ..., 14,18,20 (after ordering), find the respective positions of the five points (relative to the furthest point on the left).

# Answer
> 1 votes
**R**

```
prop <- function(num_points, first_distances, last_distances)
{
    last_point = max(last_distances)
    proposal = c(0, sort(sample(1:(last_point-1), num_points-2)), last_point)
    d = sort(dist(proposal))
    num_first_distances = length(first_distances)
    num_last_distances = length(last_distances)
    num_distances = length(d)
    if(all(d[1:num_first_distances]==first_distances)&&all(d[(num_distances-num_last_distances+1):num_distances]==last_distances))
    {
        print(proposal)
        return(TRUE)
    }
    else return(FALSE)
}

while(TRUE)
{
    if(prop(5, c(1,2,4), c(14,18,20))) break()
}

```

Here is the source of the problem and an algorithm with R which I used for inspiration.

---
Tags: code-challenge, math
---


title: Poisson random number generator

text:
# Question
Title: Poisson random number generator
What is the shortest function (implemented in C) that will return a random draw from a Poisson distribution (given the mean or `λ` parameter)?

```
int random_poisson(double lambda);

```

# Answer
> 0 votes
Taken from the wikipedia article which credits Knuth (and notes that there are implementations with better time performance) this code is a complete program implementing a minimal test scaffold. The code that does the actual work is 169 characters still formatted:

```
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <limits.h>
#include <string.h>

/* For serious work you need a high quality random number generator
 *
 * And these macros may need to be adjusted for your system and choice
 * of random number engine.
 */
#define GOODRAND random()
#define GOODRANDMAX INT_MAX
#define RANDTYPE long

/* poisson.c
 *
 * Implementation straight from
 * http://en.wikipedia.org/wiki/Poisson_distribution#Generating_Poisson-distributed_random_variables
 * which credits Knuth.
 *
 * Time complexity is O(lambda), which is not optimal.
*/
RANDTYPE poisson(double lambda){
  RANDTYPE k=0;
  double L=exp(-lambda), p=1;
  do {
    ++k;
    p *= GOODRAND/(double)GOODRANDMAX;
  } while (p > L);
  return --k;
}

/* minimal testing scaffold
*
* Note that with no initialzation the sequece will repeat on every test.
*/
int main(int argc, char**argv){
  while (argc > 1) {
    RANDTYPE in = atoi(argv[--argc]);
    printf("lambda=%d:  %d\n",in,poisson(in));
  }
}

```

---
Tags: code-golf, c, random
---


# Question
Title: Calculate the number of trailing zeros in n!
Write a function which takes n as a parameter, and returns the number of trailing zeros in n!.

## Input Constraints

0 \<= n \<= 10^100

## Output Constraints

Should be return the result in less than 10 seconds.

## Test Input

```
1
213
45678
1234567
78943533
4567894123
121233112233112231233112323123

```

## Test Output

```
0
51
11416
308638
19735878
1141973522
30308278058278057808278080759

```

Shortest code by character count wins.

# Answer
# Python, 36 Chars

Ripped from my earlier answer

```
f=lambda n:n//5+(n//5>0and f(n//5)or 0) #Py3k #39 Chars
f=lambda n:n/5+(n/5>0and f(n/5)or 0) #Before 3.0 #36 Chars

```
> 1 votes

# Answer
# Python ~~50~~ 47 Characters

```
n=input()
x=5
s=0
while n/x:s+=n/x;x*=5
print s

```
> 2 votes

# Answer
# Ruby, 52 43

```
n=gets.to_i;a=0;i=1
a+=n/i*=5while i<n
p a

```
> 1 votes

# Answer
# Haskell, 63 bytes

```
f i=length$filter(\x->x`mod`5/=0)[1..i];main=interact$show.f.read

```
> 1 votes

# Answer
# J, 26

```
! `f=:3 :'+/<.y%5^(1+i.144x)'`

```

eg

```
   f 121233112233112231233112323123x
     30308278058278057808278080759
   f 4567894123
     1141973522
   f 0
     0
   f 10^100x
     2499999999999999...99999999999999999982

```

in less than a second for all input examples
> 1 votes

---
Tags: code-golf
---


title: Random Sentence Generator

text:
# Question
Title: Random Sentence Generator
Write the shortest program you can in any language that reads a context-free grammar from and the number of sentences to produce from `stdin`, and generates that many random sentences from the grammar.

**Input**

Input will come in the following format:

```
n <START>
{"<A>":["as<A>df","0<A>","<B><C>","A<A>", ...], "<B>":["1<C>1","\<<T>>",...], ...}

```

`n` is the number of sentences to generate. `<START>` is identifier of the starting nonterminal symbol.

The grammar is enclosed in the {} and is formatted as follows:

* Rules are of the form `"<S>":[productions]`. `<S>` is the identifier of the nonterminal.
    + Rules are delimited with commas.
    + The right-hand side of a rule is a double-quoted string whose first and last characters are "\<" and "\>", respectively. The remaining character should be in `[A-Z]` (upper-case alpha).
* `productions` is a comma-delimited list of double-quoted strings, representing productions. All characters, including whitespace, in the rule are terminal symbols, except those that are enclosed in angle brackets (`"<"` and `">"`), which are non-terminal symbols and will be the left-hand side of another rule. An open angle bracket may be escaped, but there is no need to escape a close angle bracket.
    + Productions will not contain newlines or the newline escape sequence.

**Output**

You should print each generated sentence to `stdout` with a trailing newline.

**Test Cases**
5 sets of balanced parentheses:

```
5 <S>
{"<S>":["<S><S>", "(<S>)", ""]}

```

Example result:

```
(())()
()
()()()

(())(()())((((()))()()))

```

4 postfix arithmetic expressions (note whitespace within strings is significant, whitespace elsewhere is not):

```
4 <S>
{"<S>":["<N>", "<S> <S> <O>"], "<O>":["+","-","*","/"], "<N>":["<D><N>", "<D>"],
 "<D>":["1","2","3","4","5","6","7","8","9","0"]}

```

Example result:

```
1535235 76451 +
973812
312 734 99 3 + / *
1 1 1 1 1 + - * +

```

# Answer
I felt like doing a little JavaScript. Also, I cried a little on the inside when I wrote "document.write"

```
<body>
    <script type='text/javascript'>
    function foo(){
        t=document.getElementById('ta').value.split("\n");
        eval('p='+t[1]);
        t[0]=t[0].split(' ');
        while(t[0][0]--) {
            s=t[0][1]
            while(x=s.match(/<\w+>/)) {
                ps=s;
                s=s.replace(x,p[x][Math.floor(Math.random()*p[x].length)]);
            }
            document.write(s+"<br>");
        }
    }
    </script>
    <textarea id='ta' cols='80'></textarea>
    <button onclick="foo()">go</button>
</body>

```

Input:

```
10 <A>
{"<A>":["a<A>b","c<A>d","<B>"],"<B>":["e<C>e"],"<C>":["z","<A>","<B>"]}

```

Output:

```
ccaaceeeeezeeeeedbbdd
accccceeeezeeeedddddb
aecezedeb
eaezebe
ccccaacezedbbdddd
eeeaaaceecacezedbdeedbbbeee
acaecaeaaeacccceeeeeeeaeeezeeebeeeeeeeddddbebbebdebdb
aaceezeedbb
aacezedbb
ceeaceecacaacezedbbdbdeedbeed

```
> 4 votes

---
Tags: code-golf, string, grammars
---


title: Word Spinner Puzzle

text:
# Question
Title: Word Spinner Puzzle
This is a word puzzle.

Your program should accept two words on the standard input.
Word one is the start word. Word two is the end word.

From the start word you have to reach the end word changing/add/remove one letter at a time. After each modification it must form a new valid word. Added letters are added to the beginning or end. You can remove letters from any location (but word must not fall bellow three letters in length). Note: You can not rearrange the letters to form a word.

The output of the program is the sequence of words to get from the start word to the end word.

Example:

```
Input:
    Post Shot

Output:
    Post
    cost
    coat
    goat
    got
    hot
    shot

```

Winner:

* The program must run in a reasonable time (less than a 10 seconds).
* The program that can generate the shortest output sequence to the prize words.
    + **Zink -\> Silicon**
* If more than one program gets the shortest sequence then the shortest program in chars (ignoring white space).
* If we still have more than one program submission date/time shall be used.

Notes:

# Answer
## Python, 288 characters

(not counting the dictionary reading line)

```
X=set(open('websters-dictionary').read().upper().split())

(S,E)=raw_input().upper().split()
G={S:0}
def A(w,x):
 if x not in G and x in X:G[x]=w
while E not in G:
 for w in G.copy():
  for i in range(len(w)):
   for c in"ABCDEFGHIJKLMNOPQRSTUVWXYZ":A(w,w[:i]+c+w[i+1:]);A(w,w[:i]+w[i+1:]);A(w,c+w);A(w,w+c)
s=''
while E:s=E+'\n'+s;E=G[E]
print s

```

for the challenge `zink` to `silicon`:

```
ZINK
PINK
PANK
PANI
PANIC
PINIC
SINIC
SINICO
SILICO
SILICON

```

There are some strange words in that dictionary...
> 2 votes

# Answer
## traceroute - 10 chars

```
traceroute

```

detail

```
post#traceroute shot

Type escape sequence to abort.
Tracing the route to shot (1.1.4.2)

  1 pot (1.1.1.2) 40 msec 68 msec 24 msec
  2 hot (1.1.3.2) 16 msec 32 msec 24 msec
  3 shot (1.1.4.2) 52 msec *  92 msec

```

Routers are preconfigured with OSPF enabled and arranged this way.

And yes, I need 233614 routers to fully support all the words. :-)
> 16 votes

# Answer
# PHP - ~~886~~ ~~689~~ ~~644~~ 612

Dictionary loading:

```
<?php foreach(file('websters-dictionary') as $line) {
    $word = strtolower(trim($line));
    if (strlen($word) < 3) continue;
    $c[$word] = 1;
}

```

Actual code (just concat both) :

```
list($d,$e)=explode(' ',strtolower(trim(`cat`)));$f=range(@a,@z);function w($a,&$g){global$c;if(isset($c[$a]))$g[]=$a;}$h[$d]=$b=@levenshtein;$i=new SplPriorityQueue;$i->insert($d,0);$j[$d]=0;$k[$d]=$b($d,$e);while($h){if(isset($c[$l=$i->extract()])){unset($h[$l],$c[$l]);if($l==$e){for(;$m=@$n[$o[]=$l];$l=$m);die(implode("\n",array_reverse($o)));}for($p=strlen($l),$g=array();$p--;){w(substr_replace($q=$l,"",$p,1),$g);foreach($f as$r){$q[$p]=$r;w($q,$g);w($r.$l,$g);w($l.$r,$g);}}foreach($g as$m){$s=$j[$l]+1;if(!isset($h[$m])||$s<$j[$m]){$n[$m]=$l;$i->insert($m,-(($k[$m]=$b($m,$e))+$j[$m]=$s));}$h[$m]=1;}}}

```

usage:

```
php puzzle.php <<< 'Zink Silicon'
# or
echo 'Zink Silicon'|php puzzle.php

```

Result:

```
zink
pink
pank
pani
panic
pinic
sinic
sinico
silico
silicon
(0.23s)

```

This should run in less than 0.5 second for 'Zink Silicon', and less than 1 second for most cases (sometimes longer when no solution exists, but it sill returns).

This uses the A\* algorithm with levenshtein distance to estimate a lower bounds of the distances.

Some intersting tests:

* `vas arm` -\> `vas bas bar barm arm` (with a word longer than both start and end)
* `oxy pom` -\> `oxy poxy poy pom`
* `regatta gyrally` -\> (none, but the script correctly terminates)
* `aal presolution` -\> +8 chars
* `lenticulated aal` -\> -9 chars
* `acarology lowness` -\> 46 hops
* `caniniform lowness` -\> 51 hops
* `cauliform lowness` -\> 52 hops
* `overfoul lowness` -\> 54 hops
* `dance facia` -\> some words in the path have 4 more chars than both start/end
> 3 votes

# Answer
# Python

Since I couldn't golf dijkstra codes to compress to few hundreds bytes, here is ungolfed version of mine.

```
import sys, heapq, time

# dijkstra algorithm from
# http://code.activestate.com/recipes/119466-dijkstras-algorithm-for-shortest-paths/
def dijkstra(G, start, end):
   def flatten(L):
      while len(L) > 0:
         yield L[0]
         L = L[1]

   q = [(0, start, ())]
   visited = set()
   while True:
      (cost, v1, path) = heapq.heappop(q)
      if v1 not in visited:
         visited.add(v1)
         if v1 == end:
            return list(flatten(path))[::-1] + [v1]
         path = (v1, path)
         for (v2, cost2) in G[v1].iteritems():
            if v2 not in visited:
               heapq.heappush(q, (cost + cost2, v2, path))

nodes = tuple(sys.argv[1:])

print "Generating connections,",
current_time = time.time()

words = set(x for x in open("websters-dictionary", "rb").read().lower().split() if 3 <= len(x) <= max(5, *[len(l)+1 for l in nodes]))

print len(words), "nodes found"

def error():
    sys.exit("Unreachable Route between '%s' and '%s'" % nodes)

if not all(node in words for node in nodes):
    error()

# following codes are modified version of
# http://norvig.com/spell-correct.html
alphabet = 'abcdefghijklmnopqrstuvwxyz'

def edits(word):
   splits = [(word[:i], word[i:]) for i in range(len(word) + 1)]
   deletes = [a + b[1:] for a, b in splits if b]
   replaces = [a + c + b[1:] for a, b in splits for c in alphabet if b]
   prepends = [c+word for c in alphabet]
   appends = [word+c for c in alphabet]
   return words & set(deletes + replaces + prepends + appends)

# Generate connections between nodes to pass to dijkstra algorithm
G = dict((x, dict((y, 1) for y in edits(x))) for x in words)

print "All connections generated, %0.2fs taken" % (time.time() - current_time)
current_time = time.time()

try:
    route = dijkstra(G, *nodes)
    print '\n'.join(route)
    print "%d hops, %0.2fs taken to search shortest path between '%s' & '%s'" % (len(route), time.time() - current_time, nodes[0], nodes[1])
except IndexError:
    error()

```

Tests

```
$ python codegolf-693.py post shot
Generating connections, 15930 nodes found
All connections generated, 2.09s taken
post
host
hot
shot
4 hops, 0.04s taken to search shortest path between 'post' & 'shot'

$ python codegolf-693.py zink silicon
Generating connections, 86565 nodes found
All connections generated, 13.91s taken
zink
pink
pank
pani
panic
pinic
sinic
sinico
silico
silicon
10 hops, 0.75s taken to search shortest path between 'zink' & 'silicon'

```

Added user300's Tests

```
$ python codegolf-693.py vas arm
Generating connections, 15930 nodes found
All connections generated, 2.06s taken
vas
bas
bam
aam
arm
5 hops, 0.07s taken to search shortest path between 'vas' & 'arm'

$ python codegolf-693.py oxy pom
Generating connections, 15930 nodes found
All connections generated, 2.05s taken
oxy
poxy
pox
pom
4 hops, 0.01s taken to search shortest path between 'oxy' & 'pom'

$ python codegolf-693.py regatta gyrally
Generating connections, 86565 nodes found
All connections generated, 13.95s taken
Unreachable Route between 'regatta' and 'gyrally'

```

Some more

```
$ python codegolf-693.py gap shrend
Generating connections, 56783 nodes found
All connections generated, 8.16s taken
gap
rap
crap
craw
crew
screw
shrew
shrewd
shrend
9 hops, 0.67s taken to search shortest path between 'gap' & 'shrend'

$ python codegolf-693.py guester overturn
Generating connections, 118828 nodes found
All connections generated, 19.63s taken
guester
guesten
gesten
geste
gest
gast
east
ease
erse
verse
verset
overset
oversee
overseed
oversend
oversand
overhand
overhard
overcard
overcare
overtare
overture
overturn
23 hops, 0.82s taken to search shortest path between 'guester' & 'overturn'

```
> 3 votes

---
Tags: code-golf, word-puzzle
---


title: Physics golf: inclined shooting

text:
# Question
Title: Physics golf: inclined shooting
An angry bird is shot at an angle \\$β\\$ to the horizontal at a speed \\$u\\$. The ground is steep, inclined at an angle \\$α\\$. Find the horizontal distance \\$q\\$ that the bird traveled before it hit the ground.

Make a function \\$f(α, β, u)\\$ that returns the length \\$q\\$: the horizontal distance that the bird traveled before it hit the ground.

Constraints and notes:

* \\$-90° \< α \< 90°\\$.
* \\$0° \< β \< 180°\\$.
* \\$α \< β\\$.
* \\$0 \le u \< 10^9\\$.
* Assume acceleration due to gravity \\$g = 10\\$.
* You may use radians instead of degrees for \\$α\\$, \\$β\\$.
* Dimensions of \\$u\\$ are irrelevant as long as they are consistent with \\$g\\$ and \\$q\\$.
* No air resistance or anything too fancy.

Shortest code wins.

See the Wikipedia article on projectile motion for some equations.

Samples:

```
f(0, 45, 10) = 10
f(0, 90, 100) = 0
f(26.565, 45, 10) = 5
f(26.565, 135, 10) = 15

```

# Answer
> 3 votes
# Java

Works for radians only

```
double q(double a, double b, double u){
          return (Math.abs(((-Math.tan(a)+(Math.tan(b)))*(u*u)*(0.2*(Math.cos(b)*Math.cos(b))))));
      }

```

Golfed Version (Thanks to Peter)

```
double z=u*Math.cos(b);return(Math.tan(b)-Math.tan(a))*z*z/5;

```

Maths Used:

$$ q = ut\cos \beta \\ q\tan \alpha = ut\sin \beta - 0.5 \times 10 t^2 \\ \- \tan \alpha + \tan \beta = 5\frac q {u^2} \sec^2 \beta \\ q = \frac {(\tan \beta - \tan \alpha)u^2} {5\sec^2 \beta } $$

# Answer
> 2 votes
## Haskell (~~37~~ 35)

Based on Aman's solution:

```
q a b u=(tan a+tan b)*u*u*cos b^2/5

```

I think, this problem isn't real code-golf, as it is more implementing a formula than really doing some algorithm.

# Answer
> 2 votes
# Python3 - 65 chars

```
from math import*
f=lambda α,β,u:(tan(α)+tan(β))*u*u*.2*cos(β)**2

```

---
Tags: code-golf, math, physics
---


title: Build an engine for a maze game

text:
# Question
Title: Build an engine for a maze game
This is a follow up of Print a maze question. If you like this question, please add more maze generation algorithms ;).

For this task you'll have to implement a game engine for one player who must find the treasure in a maze and get out of the dungeon.

The engine starts by reading the maze from standard input followed by a line containing a `.` (dot) a file given as argument in the command line. Next the player `@` is placed in a random location on the map. Then engine starts interacting with the player through standard io:

Commands from **engine to player**:

* `continue`: Game not finished. The surroundings are printed followed by a `.`. Player is represented by `@` character. Unobservable cells are represented by `?`.
* `finished`: Game finished. The number of steps is printed and the game stops.

Commands from **player to engine**:

* `north`: Moves player up.
* `south`: Moves player down.
* `west`: Move player left.
* `east`: Move player right.

Any invalid command (such as hitting a wall) from player is ignored, but still counted. You are free to define the surroundings to your liking.

* *Points* for the shortest code.
* *Points* for complex surroundings (e.g. print large regions and replace cells that are not visible by `?`).
* *No points* for code that doesn't respect the io format

**Example**:

In this example the surroundings is defined as the 3x3 cell with the player in the middle.

```
$ cat maze
+-+-+
  |#|
|   |
+---+
$ python engine.py maze
 |#
 @
---
.
east
|#|
 @|
--+
.
north
+-+
|@|
  |
.
south
|#|
 @|
--+
.
west
 |#
 @
---
.
west
  |
|@
+--
.
north
+-+
 @|
|
.
west
finished
7

```

# Answer
# C99, 771 characters

```
#include <ncurses.h>
#include <string.h>
#define MIN(A,B) (A<B?A:B)
#define MAX(A,B) (A>B?A:B)
#define T(C,X,Y) case C:if((m[x+X][y+Y]==' ')||(m[x+X][y+Y]=='#'))x+=X,y+=Y;s++;break;
char m[24][81],M[24][81];int i,j,I=0,J,x,y,s=0;
int main(int c,char**v){FILE*f=fopen(v[1],"r");
for(I=0;fgets(m[I],80,f);I++)J=MAX(J,strlen(m[I]));
J--;f=fopen("/dev/random","r");do{x=fgetc(f)%I;y=fgetc(f)%J;}
while(m[x][y]!=' ');initscr();curs_set(0);do{
switch(c){T('e',0,1)T('n',-1,0)T('s',1,0)T('w',0,-1)}
for(i=MAX(0,x-1);i<MIN(x+2,I);i++)for(j=MAX(0,y-1);j<MIN(y+2,J);j++)M[i][j]=1;
for(i=0;i<I;i++)for(j=0;j<J;j++)mvaddch(i,j,M[i][j]?m[i][j]:'?');
mvaddch(x,y,'@');refresh();}while((m[x][y]!='#')&&(c=getch())!='q');
if(m[x][y]=='#')mvprintw(I,0,"Finished in %d steps!",s),getch();endwin();}

```

Requires and makes use of ncurses. Only one macroization for length, and the N and M macros are to replace the missing minimum and maximum opperators, and I don't think there is much more to do on that.

It assumes the input maze does not exceed 80 characters wide, and that the a maze filename *has* been passed on the command-line, and that the number of parameters is low enough that the initial value of c isn't a movement command.

* Deviates from the standard in that it takes single character direction commands as the lowercase first letter of the ones suggested.
* Does show unknown regions as '?'s.

**More readable with comments:**

```
#include <ncurses.h>
#include <string.h>

#define MIN(A,B) (A<B?A:B)/*unsafe,but short*/
#define MAX(A,B) (A>B?A:B)/*unsafe,but short*/
// #define MAX(A,B) ((_A=A)>(_B=B)?_A:_B) /* safe but verbose */
#define T(C,X,Y) case C:if((m[x+X][y+Y]==' ')||(m[x+X][y+Y]=='#'))x+=X,y+=Y;s++;break;
char m[24][81],M[24][81];/* [m]ap and [M]ask; NB:mask intialized by default */
int i,j, /* loop indicies over the map */
  I=0,J, /* limits of the map */
  x,y,   /* player position */
  s=0;   /* steps taken */
int main(int c,char**v){
  FILE*f=fopen(v[1],"r"); /* fragile, assumes that the argument is present */
  /* Read the input file */
  for(I=0;fgets(m[I],80,f);I++)J=MAX(J,strlen(m[I])); /* Read in the map */
  J--;
  /* note that I leak a file handle here */
  f=fopen("/dev/random","r");
  /* Find a open starting square */
  do{
    x=fgetc(f)%I; /* Poor numeric properties, but good enough for code golf */
    y=fgetc(f)%J;
  } while(m[x][y]!=' ');
  /* setup curses */
  initscr(); /* start curses */
  //  raw();     /* WARNING! intercepts C-c, C-s, C-z, etc...
  //          * but shorter than cbreak()
  //          */
  curs_set(0); /* make the cursor invisible */
  /* main loop */
  do {
    switch(c){
      T('e',0,1)
      T('n',-1,0)
      T('s',1,0)
      T('w',0,-1)
    }
    /* Update the mask */
    for(i=MAX(0,x-1);i<MIN(x+2,I);i++)
      for(j=MAX(0,y-1);j<MIN(y+2,J);j++)
    M[i][j]=1;
    /* draw the maze as masked */
    for(i=0;i<I;i++)
      for(j=0;j<J;j++)
    mvaddch(i,j,M[i][j]?m[i][j]:'?');
    /* draw the player figure */
    mvaddch(x,y,'@');
    refresh(); /* Refresh the display */
  } while((m[x][y]!='#')&&(c=getch())!='q');
  if(m[x][y]=='#')mvprintw(I,0,"Finished in %d steps!",s),getch();
  endwin();
}

```
> 7 votes

---
Tags: code-golf, maze
---


title: Robot Finds Kitten

text:
# Question
Title: Robot Finds Kitten
### The challenge

The shortest code by character count to help Robot find kitten in the fewest steps possible.

Golfers, this is a time of crisis - Kitten gone missing and it's Robot's job to find it! Robot needs to reach Kitten in the shortest path possible. However, there are a lot of obstacles in Robot's way, and he needs you to program a solution for him.

Robot used to have a program do it for him, but that program was lost and Robot have no backup :(.

Robot's runtime is not the best, and the least characters Robot has to read from the source code, the least time it will spend processing, and that means Kitten will be found faster!

Robot's memory contains a map of the location he is currently in with the top representing North, bottom representing South, right representing East and left representing West. Robot is always in a rectangular room of an unknown size surrounded by walls, represented by `#` in his radar map. Areas Robot can walk in are represented by a space .

Robot's radar also scans for many obstacles in the room and marks them in various ASCII letters. Robot cannot walk across those obstacles. The radar will mark Kitten as the special ASCII character `K`, while Robot's location is marked with `R`.

Robot's navigation system works this way: He can understand a duo of direction and number of movement units he should travel to - for example, `N 3` means 'go north 3 movement units'. Robot's radar map is made such that a movement unit is one ASCII character. Robot can only go in 4 directions and cannot travel diagonally.

Your task, brave Kitten saver, is to read Robot's radar map once, and output the least amount of directions, with the least movement unit travel distance. Robot is guaranteed to have at least one path to Kitten.

To ensure Robot does not waste time executing a malfunctioning program that will not help Robot find Kitten, I encourage you, brave Kitten saver, to use this output of Robot's past program to ensure no time is wasted on finding Kitten!

## Test cases

```
Input:
    ######################
    #  d      3    Kj    #
    #                    #
    # R                  #
    #      q             #
    ######################
Output:
    E 13
    N 2

```

---

```
Input:
    ######################
    #  d  r   3    Kj    #
    #    p        p      #
    #         T        X #
    #      q   s   t     #
    #                    #
    #  R o    d     W    #
    #                    #
    #    g      t     U  #
    #                    #
    ######################
Output:
    N 1
    E 10
    N 4
    E 2

```

---

```
Input:
    ######################
    #  spdfmsdlwe9mw WEK3#
    #    we    hi        #
    #   rdf         fsszr#
    #     sdfg  gjkti    #
    #   fc  d g i        #
    #     dfg    sdd     #
    #    g        zfg    #
    #  df   df           #
    #             xcf   R#
    ######################
Output:
    N 1
    W 9
    N 5
    E 4
    N 1
    E 4
    N 1

```

Code count includes input/output (i.e full program).

# Answer
> 10 votes
### C++ 1002 899 799chars

Note requires the use of C++0x to eliminate the space between \> \> in templates.

It does find the route with the minimum number of turns.

```
#include<iostream>
#include<vector>
#include<string>
#include<set>
#include<memory>
#define D make_pair
#define F first
#define S second
using namespace std;typedef pair<int,int>L;typedef vector<L>R;typedef multiset<pair<float,pair<L,R>>>B;vector<string> M;string l;int z,c,r=0;set<L> s;B b;L n;B::iterator f;R v;void A(int x,int y,int w){n=f->S.F;for(c=1;(z=M[n.S+=y][n.F+=x])==32||(z==75);++c)v.back()=D(w,c),b.insert(D(f->F+c+1./c,D(n,v)));}int main(){for(;getline(cin,l);++r){if((c=l.find(82))!=string::npos)b.insert(D(0,D(D(c,r),R())));M.push_back(l);}while(!b.empty()){f=b.begin();n=f->S.F;v=f->S.S;if(M[n.S][n.F]==75)break;if(s.find(n)==s.end()){s.insert(n);v.push_back(L());A(0,1,83);A(0,-1,78);A(1,0,69);A(-1,0,87);}b.erase(f);}for(c=v.size(),r=0;r<c;++r)n=v[r],printf("%c %d\n",n.F,n.S);}

```

It `Dijkstra's Algorithm` for solving the shortest path problem.
To distinguish between multiple equal size routes a long straight line has less weight that multiple short lines (this favors routes with less turns).

```
Cost of a path:  Len + 1/Len

Looking at Test Case 1:
========================
Thus Path E13 + N2 has a cost of
      13 + 1/13 + 2 + 1/2
An alternative path E9 + N2 + E4 has a cost of
      9 + 1/9 + 2 + 1/2 + 4 + 1/4

The difference is
      Straight Path:   1/13 <   Bendy Path: (1/9 + 1/4)

```

In a more readable form:

```
#include<iostream>
#include<vector>
#include<string>
#include<set>
#include<memory>

using namespace std;
typedef pair<int,int>                   L;
typedef vector<L>                       R;
typedef multiset<pair<float,pair<L,R>>> B;
vector<string>                          M;

string      l;
int         z,c,r=0;
set<L>      s;
B           b;
L           n;
B::iterator f;
R           v;

void A(int x,int y,int w)
{
    n=f->second.first;
    for(c=1;(z=M[n.second+=y][n.first+=x])==32||(z==75);++c)
        v.back()=make_pair(w,c),
        b.insert(make_pair(f->first+c+1./c,make_pair(n,v)));
}

int main()
{
    for(;getline(cin,l);++r)
    {
        if((c=l.find(82))!=string::npos)
            b.insert(make_pair(0,make_pair(make_pair(c,r),R())));
        M.push_back(l);
    }

    while(!b.empty())
    {
        f=b.begin();
        n=f->second.first;
        v=f->second.second;

        if(M[n.second][n.first]==75)
            break;

        if(s.find(n)==s.end())
        {
            s.insert(n);
            v.push_back(L());
            A(0,1,83);
            A(0,-1,78);
            A(1,0,69);
            A(-1,0,87);
        }
        b.erase(f);
    }

    for(c=v.size(),r=0;r<c;++r)
        n=v[r],
        printf("%c %d\n",n.first,n.second);
}

```

# Answer
> 9 votes
## Scala 2.8 (451 characters)

...but it doesn't solve ties in favor of least amount of directions (though it does find the least amount of steps).

```
val m=io.Source.stdin.getLines.map(_.toArray).toSeq
var l=m.indexWhere(_ contains'R')
var c=m(l)indexOf'R'
val q=collection.mutable.Queue(l->c->"")
def s{val((l,c),p)=q.dequeue
if("R "contains m(l)(c))for((i,j,k)<-Seq((-1,0,"N"),(0,1,"E"),(1,0,"S"),(0,-1,"W")))q.enqueue(((l+i,c+j),p+k))
m(l)(c)='X'}
def P(s:String){if(s.nonEmpty){val (h,t)=s.span(s.head==)
println(s.head+" "+h.size)
P(t)}}
def Q{s
val((l,c),p)=q.head
if (m(l)(c)=='K')P(p)else Q}
Q

```

Scala 2.8, 642 characters, solves ties correctly;

```
val m=io.Source.stdin.getLines.toSeq
var b=Map(0->0->0).withDefault(_=>Int.MaxValue)
var l=m.indexWhere(_ contains'R')
var c=m(l)indexOf'R'
val q=collection.mutable.PriorityQueue(l->c->List((' ',0)))(Ordering.by(t=>(-t._2.map(_._2).sum,-t._2.size)))
def s{val(p@(l,c),u@(h@(d,n))::t)=q.dequeue
if("R ".contains(m(l)(c))&&u.map(_._2).sum<=b(p)){b=b.updated(p,u.map(_._2).sum)
for((i,j,k)<-Seq((-1,0,'N'),(0,1,'E'),(1,0,'S'),(0,-1,'W'))){
val o=if(k==d)(d,n+1)::t else (k,1)::h::t
q.enqueue(((l+i,c+j),o))}}}
def P(l:List[(Char,Int)]){l.reverse.tail.foreach{t=>println(t._1+" "+t._2)}}
def Q{s;val((l,c),p)=q.head;if (m(l)(c)=='K')P(p)else Q}
Q

```

It discovered a shorter path for the second example than the one given in the problem:

```
N 1
E 10
N 4
E 2

```

# Answer
> 4 votes
## Python 2.6 (504 characters)

```
import sys,itertools
W,Q=len,list
M=[]
B=[]
for l in sys.stdin.readlines():
    r=Q(l.strip())
    B.append([0]*W(r))
    M.append(r)
    if "R" in r:x,y=r.index("R"),W(B)-1
def S(B,M,x,y,P):
    c=M[y][x]
    b=B[y][x]
    if b and W(P)>b:return 0
    B[y][x]=W(P)
    if c=="K":return P
    elif c=="R" and P:return 0
    if c in "R ":
        b=[]
        for q,w,s in((1,0,"E"),(-1,0,"W"),(0,-1,"N"),(0,1,"S")):
            r=S(B,M,x+q,y+w,P+s)
            if r and(W(r)<W(b)or not b):b=r
        if b:return b
    return 0
print "\n".join(k+str(W(Q(g)))for k,g in itertools.groupby(S(B,M,x,y,"")))

```

# Answer
> 4 votes
## Python 2.6 (535 characters)

```
exec 'eJzNlLFugzAQhneewhki2/KBworksVOkDu3QgVqVE2hBioFgCDhV371nJ1VbKR3SKYtl/jvs77MwtenafiBVqbs9WGcjLW05MB69tj05QEfqhpTNaMpeDyXDhsQORd3wLCK+YwT7u6PzFVK/Ep9Tsn6gmU50UTA2woHzc01KuqYZ20PPZSh85/iCO2etzBnTG8tcvlLxnovTPFVxzyGEC4lpiBay5xiuYMXBcRVtzxqTfP+IpqrelaRFsheoYJbBNvFj13asxd23gXHGmZU7bTaFDgiZH+MUYydtKBuZRuS0nvPmOt564Sl3CmlxcWAG6D3lXIkpeUMGB7nyfj82HW3FWvjTTVSYCXNJEUupEimannu+nl04WyM8XoB1F13E9S6Pt+ki0vDZXOdyd5su8X9cnm7DBa/tLGW4yh7yKCn1rIF+9vSTj/HiBeqCS1M3bMrnwOvbl5Ysi+eGLlkBhosjxl1fNwM5Ak7xH6CiT3SdT4U='.decode('base64').decode('zlib')

```

Unpacks to a severely mistreated A\* implementation. Reads stdin. Searches for solutions with minimal total distance. Breaks ties by preferring minimal number of directions. Lists moves to stdout. Finds kittens.

**Unpacked**:

The source has been manually anti-golfed in a few places in order to obtain a smaller compressed representation. For example, a for loop over the compass directions was unrolled.

```
import heapq,sys
a=set()
for v,p in enumerate(sys.stdin):
 for u,s in enumerate(p):
  if s in' KR':a.add((u,v))
  if s=='K':(q,r)=(u,v)
  if s=='R':y=(u,v)
o=[((abs(y[0]-q)+abs(y[1]-r),(y[0]!=q)+(y[1]!=r)),(0,0),y)]
c=set()
w={}
while o:
 _,h,x=heapq.heappop(o)
 c.add(x)
 s=lambda(u,v):(u,v-1)
 y=s(x)
 m=1
 while y in a-c:
  w[y]=[(h,x,(m,'N'))]+w.get(y,[])
  heapq.heappush(o,((abs(y[0]-q)+abs(y[1]-r)+h[0]+m,(y[0]!=q)+(y[1]!=r)+h[1]+1),(h[0]+m,h[1]+1),y))
  m+=1
  y=s(y)
 s=lambda(u,v):(u,v+1)
 y=s(x)
 m=1
 while y in a-c:
  w[y]=[(h,x,(m,'S'))]+w.get(y,[])
  heapq.heappush(o,((abs(y[0]-q)+abs(y[1]-r)+h[0]+m,(y[0]!=q)+(y[1]!=r)+h[1]+1),(h[0]+m,h[1]+1),y))
  m+=1
  y=s(y)
 s=lambda(u,v):(u+1,v)
 y=s(x)
 m=1
 while y in a-c:
  w[y]=[(h,x,(m,'E'))]+w.get(y,[])
  heapq.heappush(o,((abs(y[0]-q)+abs(y[1]-r)+h[0]+m,(y[0]!=q)+(y[1]!=r)+h[1]+1),(h[0]+m,h[1]+1),y))
  m+=1
  y=s(y)
 s=lambda(u,v):(u-1,v)
 y=s(x)
 m=1
 while y in a-c:
  w[y]=[(h,x,(m,'W'))]+w.get(y,[])
  heapq.heappush(o,((abs(y[0]-q)+abs(y[1]-r)+h[0]+m,(y[0]!=q)+(y[1]!=r)+h[1]+1),(h[0]+m,h[1]+1),y))
  m+=1
  y=s(y)
 if x==(q,r):
  z=''
  while x in w:
   _,x,(m,d)=min(w[x])
   z='%s %d\n'%(d,m)+z
  print z,
  o=[]

```

# Answer
> 3 votes
## c++ -- 681 necessary characters

```
#include <string>
#include <iostream>
#include <sstream>
using namespace std;
int d[]={-1,0,1,0},i,j,k,l,L=0,p=41,S;string I,m,D("ESWN");
int r(int o,int s){S=s;while((m[o]==32||m[o]==37)&&m[o+S]-35)
if(m[o+S]-p)S+=s;else return o+S;return 0;}
void w(int o){for(i=0;i<m.length();++i)for(j=0;j<4;++j)
if(k=r(o,d[j])){stringstream O;O<<D[j]<<" "<<int((k-o)/d[j])<<"\n"<<I;
I=O.str();if(p-41)--p,m[k]=37,w(k);cout<<I;exit(0);}}
int main(){while(getline(cin,I))m+=I,l=I.length();
d[1]-=d[3]=l;I="";for(i=0;i<m.length();++i)
switch(m[i]){case 82:case 75:m[i]/=2;case 32:break;default:m[i]=35;}
do{for(i=0;i<m.length();++i)if(r(i,-1)+r(i,-l)+r(i,1)+r(i,l))
{if(m[i]==37)w(i);m[i]=p+1;}}while(++p);}

```

It first replaces all the obstacles on the map with into `#`s (and changes the values of `K` and `R`, to leave headroom in the character space for very long paths. *Then it scribbles on the map.* An iterative process marks all the successively accessible squares until it is able to reach the kitten in one move. After that is uses the *same* accessibility checking routine to find a string of positions that lead back to the start in minimal instructions. These instructions are loaded into a string by pre-pending, so that they print in the proper order.

I don't intend to golf it further as it does not properly resolve ties and can not be easily adapted to do so.

It fails on

```
#####
#   #
# # #
#R#K#
#   #
#####

```

producing

```
 $ ./a.out < kitten_4.txt
N 2
E 2
S 2

```

**More or less readable version:**

```
#include <string>
#include <iostream>
#include <sstream>
using namespace std;

int d[]={-1,0,1,0}
  , i, j, k
  , l      /* length of a line on input */
  , L=0    /* length of the whole map */
  , p=41   /* previous count  ( starts 'R'/2 ) */
  , S      /* step accumulator for step function */
  ;
string I/*nput line, later the instructions*/
  , m/*ap*/
  , D("ESWN"); /* Reversed sence for back tracking the path */

int r/*eachable?*/(int o/*ffset*/, int s/*step*/){
//   cerr << "\tReachable?"
//        << endl
//        << "\t\tOffset: " << o << " (" << o/5 << ", " << o%5 << ")"
//        << "  [" << m[o] << "]" << endl
//        << "\t\tStep: " << s
//        << endl
//        << "\t\tSeeking: " << "[" << char(p) << "]"
//        << endl
//        << "\t\tWall:    " << "[" << char(35) << "]"
//        << endl;
  S=s;
  while ( ( (m[o]==32)      /* Current character is a space */
        || (m[o]==37) ) /* Current character is a kitten */
      && (m[o+S]-35) /* Target character is not a wall */
      )
    {
//     cerr << "\t\tTry: " << o+S << "(" << (o+S)/5 << ", " << (o+S)%5 << ")"
//   << "  [" << m[o+S] << "]" << endl;
    if (m[o+S]-p       /* Target character is not the previous count */
    ) {
//       cerr << "\t\twrong " << "  [" << m[o+S] << "] !!!" << endl;
      S+=s;
    }
    else  {             /* Target character *is* the previous count */
//       cerr << "\t\tFound " << "  [" << m[o+S] << "] !!!" << endl;
      return o+S;
    }
  /* while ends */
      }
  return 0;
}

void w/*on*/(int o/*ffset*/){
//   cerr << "\tWON" << endl
//        << "\t\tOffset: " << o << "(" << o/5 << ", " << o%5 << ")"
//        << "  [" << m[o] << "]"
//        << endl
//        << "\t\tSeeking: " << "[" << char(p) << "]"
//        << endl;
  for(i=0;i<m.length();++i) /* On all map squares */
    for(j=0;j<4;++j)
      if (k=r(o,d[j])) {
//  cerr << "found path segment..."
//       << (k-o)/d[j] << " in the " << d[j] << " direction." << endl;
    stringstream O;
    O << D[j]
      << " "
      << int((k-o)/d[j])
      << "\n"
      << I;
    I = O.str();
//  cerr << I << endl;
    /* test for final solution */
    if (p-41)
      --p,m[k]=37, w(k); /* recur for further steps */
    cout << I;
    exit(0);
      }
    /* inner for ends */
  /* outer for ends */
}

int main(){
  while(getline(cin,I))
    m+=I,l=I.length();
//   cerr << "Read the map: '" << m << "'." << endl;
  d[1]-=d[3]=l;I="";
//   cerr << "Direction array:    " << D << endl;
//   cerr << "Displacement array: " << d[0] << d[1] << d[2] << d[3] << endl;
//   cerr << "Line length: " << l << endl;
  /* Rewrite the map so that all obstacles are '#' and the start and
     goal are '%' and ')' respectively. Now I can do pathfinding *on*
     the map. */
  for(i=0;i<m.length();++i)
    switch (m[i]) {
    case 82:         /* ASCII 82 == 'R' (41 == ')'  ) */
    case 75:m[i]/=2; /* ASCII 75 == 'K' (37 == '%' ) */
    case ' ':break;
    default: m[i]=35; /* ASCII 35 == '#' */
    };
//   cerr << "Re-wrote the map: '" << m << "'." << endl;
  do { /* For each needed count */
//     cerr << "Starting to mark up for step count "
//   << p-41+1  << " '" << char(p) << "'" << endl;
    for(i=0;i<m.length();++i){ /* On all map squares */
//        cerr << "\tTrying position (" << i/l << ", " << i%l << ")"
//      << "  [" << m[i] << "]"
//      << endl;
      if ( r(i, -1) /* west  */ +
       r(i, -l) /* north */ +
       r(i,  1) /* east  */ +
       r(i,  l) /* south */
       ) {
//    cerr << "Got a hit on : '" << m << "'." << endl;
//    cerr << "\twith '" << char(m[i]) <<" at position " << i << endl;
//    cerr << "target is " << char(37) << endl;
    if(m[i]==37)
      w(i); /* jump into the win routine which never returns */
    m[i]=p+1;
//  cerr << "Marked on map: '" << m << "'." << endl;
      }
    }
  } while(++p);
}

```

# Answer
> 3 votes
## Ruby - 539 characters

Could do with a lot of improvement, but it does work for shortest steps as well as directions.

```
M=[*$<]
r=M.map{|q|q.index('R')||0}
k=M.map{|q|q.index('K')||0}
D=M.map{|q|q.split('').map{[99,[]]}}
def c h
h.map{|i|i.inject([[]]){|a,b|a.last[0]!=b ? a<<[b, 1]:a.last[1]+=1;a}}.sort_by{|a|a.length}[0]
end
def t x,y,s,i
z,w=D[x][y][0],D[x][y][1]
if [' ','R','K'].index(M[x][y, 1])&&(z>s||z==s&&c(w).length>=c([i]).length)
D[x][y]=[s,z==s ? w<<i:[i]]
s+=1
t x+1,y,s,i+['S']
t x-1,y,s,i+['N']
t x,y+1,s,i+['E']
t x,y-1,s,i+['W']
end
end
t r.index(r.max), r.max, 0, []
puts c(D[k.index(k.max)][k.max][1]).map{|a|a*''}

```

# Answer
> 1 votes
## Ruby - 648 characters

Another one that fails the least number of directions test as I can't think of any easy way to embed it in A\*.

```
m=$<.read.gsub /[^RK\n ]/,'#'
l=m.index($/)+1
s=m.index'R'
g=m.index'K'
h=->y{(g%l-y%l).abs+(g/l-y/l).abs}
n=->y{[y+1,y-1,y+l,y-l].reject{|i|m[i]=='#'}}
a=o=[s]
d=Array.new(m.length,9e9)
c,k,f=[],[],[]
d[s]=0
f[s]=h[s]
r=->y,u{u<<y;(y=k[y])?redo:u}
(x=o.min_by{|y|f[y]}
x==g ? (a=r[x,[]].reverse;break):0
o-=[x];c<<x
n[x].map{|y|c&[y]!=[]?0:(t=d[x]+1
o&[y]==[]?(o<<y;b=true):b=t<d[y]
b ? (k[y]=x;d[y]=t;f[y]=t+h[y]):0)})until o==[]
k=a.inject([[],nil]){|k,u|(c=k[1]) ? (k[0]<<(c==u-1?'E':c==u+1?'W':c==u+l ? 'N':'S')) : 0;[k[0],u]}[0].inject(["","",0]){|k,v|k[1]==v ? k[2]+=1 : (k[0]+=k[1]+" #{k[2]}\n";k[1]=v;k[2]=1);k}
puts k[0][3,9e9]+k[1]+" #{k[2]}\n"

```

---
Tags: code-golf, ascii-art, path-finding
---


title: Count even steps of 196 algorithm

text:
# Question
Title: Count even steps of 196 algorithm
In the 196-algorithm one starts from an integer and then adds its reverse to it until a palindrome is reached, like this:

```
start -> 5280
5280 + 0825 = 6105
6105 + 5016 = 11121
11121 + 12111 = 23232
-end-

```

Write a *function* that counts **how many even numbers are visited** before the algorithm ends. Starting and ending numbers are also counted, so, in the example above, visited are consider the numbers: **5280, 6105, 11121, 23232** but *not* 825, 5016 and 12111.

Examples:

```
f(5280) = 2
f(56) = 1
f(59) = 1
f(89) = 13

```

Extended code golf rules apply: shortest number of **instructions and operations** (like +,-,mod,print,while,if,...) wins.

# Answer
## Mathematica

**5 verbs** ... not sure how to count ...

```
k = FromDigits@Reverse@IntegerDigits[#] &;
Count[NestWhileList[# + k@# &, #, # != k@# &], _?OddQ] &

```
> 1 votes

# Answer
## Python - 10 operations

```
def f(n):
    q=str(n)
    p=q[::-1]
    return 1-n%2+(q!=p and f(n+long(p)))

```
> 6 votes

# Answer
Hey, looks like `eval`, for once, isn't forbidden here!

## Perl, 1 instruction

```
sub f { eval << 'EOT' }
  my $n = $_[0];
  my $r = reverse $n;
  return !($n & 1) + ($r eq $n ? 0 : f($n+$r));
EOT

```
> 4 votes

# Answer
# D: 154 Characters, 22 Instructions

```
alias long l;alias string s;l f(l n){l t=!(n&1);auto u=to!s(n);while(u!=to!s(retro(u))){n=to!l(u)+to!l(to!s(retro(u)));if(!(n&1))++t;u=to!s(n);}return t;}

```

More Legibly:

```
alias long l;
alias string s;

l f(l n)
{
    l t = !(n & 1);  //3 instructions
    auto u = to!s(n);  //2 instructions

    while(u != to!s(retro(u)))  //4 instructions
    {
        n = to!l(u) + to!l(to!s(retro(u)));  //6 instructions

        if(!(n & 1))  //3 instructions
            ++t;  //1 instruction

        u = to!s(n);  //2 instructions
    }

    return t;  //1 instruction
}

```

I'm not sure that counted instructions quite right, since that's a bit debatable, and of course, there are lots of instructions going on in the functions which get called. So, ultimately, I'm not sure how reasonable or accurate counting instructions is, but I think that 22 is the total.
> 3 votes

# Answer
# Scheme, 18 instructions

I take an instruction to be an opening paren.

```
(define (even-numbers-from-169-algo n)
    (+
        (if (odd? n) 0 1)
        (if (equal? n (num-reverse n))
            0
            (even-numbers-from-169-algo
                (+ n (num-reverse n))))))
(define (num-reverse n)
    (string->number (list->string (reverse (string->list (number->string n))))))

```
> 2 votes

# Answer
## Windows PowerShell, 16 instructions

```
function f($n){
  @(                                   # 1
    $(                                 # 1
      $n % 2                           # 1
      #1     1   1     2    1
      for(;-join"$n"[99..0]-ne$n) {    # 5
        # 1   1   1     2
        $n+=-join"$n"[99..0]           # 5
        $n % 2                         # 1
      }                                #
    ) -eq 0).Count                     # 2
}

```

Notes:

* I counted the following items as one instruction: String expansion (`"$n"`), operators (`-ne`, `%`, `!`, `-join`, `$()`, `@()`), cmdlets (`%`), keywords (`for`).
* I counted indexes as two instructions since it's the index `[]` plus the range operator `..`
* I didn't count the function header.

History:

* 2011-02-15 02:49 (18) First attempt.
* 2011-02-15 02:55 (16) Got rid of the pipeline.
> 2 votes

# Answer
## J, 36 characters, 7 instructions

```
+/@:-.@(2&|)@((+`1:@.=|.&.":)"0^:a:)

```

I'm counting both monadic and dyadic verbs as instructions. Here's a token breakdown to make sure everything is accounted for:

* 3 monadic verbs (6 chars): `-.`, `|.`, `":`
* 4 dyadic verbs (4 chars): `+`, `|`, `+`, `=`
* 0 adverbs (0 chars)
* 10 conjunctions (14 chars): `/`, `@:`, `@`, `&`, `@`, ```, `@.`, `&.`, `"`, `^:`
* 4 constants (6 chars): 2 1: 0 a:
* 3 parenthesis groups (6 chars)

Demonstration:

```
   +/@:-.@(2&|)@((+`1:@.=|.&.":)"0^:a:) 5280 56 59 89
2 1 1 13

```

The `"0` isn't strictly needed to answer the question, it's just there to make the function more J-like (*i.e.*, able to operate on a whole array at once, as above). I kept it in as it doesn't go against my instruction count.
> 2 votes

# Answer
**Java Solution**

```
int countEvenIn196(long n){
        int count=0;
        boolean flag=false;
        while (!flag){
        for (int i=0; i<(""+n).length(); i++)
            if ((""+n).charAt(i) == (""+n).charAt((""+n).length()-i-1))
                {flag=true;}
            else {flag=false; break;}
        if (n%2==0) count++;
        //n+=reverse(n);
            n+=(Long.parseLong(new StringBuffer(""+n).reverse().toString()));
        }
        return count;
    }

```
> 1 votes

# Answer
**Haskell 12 Operations**

```
f n=1-n`rem`2+if q/=p then f(n+read p) else 0 where q=show n;p=reverse q

```

New to Haskell. Need help to reduce it further.
> 1 votes

---
Tags: atomic-code-golf
---


# Question
Title: Directories required for creating a folder tree
Say that you have this folder structure on your coumputer:

```
/a

```

And you want to have these folders:

```
/a/b
/a/c
/b/b

```

You would need to create four directories, using mkdir for example:

```
mkdir /a/b
mkdir /a/c
mkdir /b
mkdir /b/b

```

Write a program that, given existing and required directory structures, will output the directories that need to be created.

## Input

First line has two numbers: n, number of existing directories, and m, number of required directories Next n lines has the list of existing directories Next m lines has the list of required directories

Example:

```
1 3
/a
/a/b
/a/c
/b/b

```

## Output

Directories you need to create

Example:

```
/a/b
/a/c
/b
/b/b

```

# Answer
> 2 votes
# Python

In Python, you would just use `os.makedirs()`. See the docs at the bottom of this post

```
import sys

num_existing, num_required = map(int, next(sys.stdin).split())

sep = "/"
directory = {}

for i,path in enumerate(s.rstrip("\n") for s in sys.stdin):
    d = directory
    base = ""
    for p in path.split(sep)[1:]:
        base += sep+p
        if p not in d:
            if i >= num_existing:
                print base
            d[p]={}
        d = d[p]

```

Python docs for `os.makedirs()`

```
>>> import os
>>> help(os.makedirs)

Help on function makedirs in module os:

makedirs(name, mode=511)
    makedirs(path [, mode=0777])

    Super-mkdir; create a leaf directory and all intermediate ones.
    Works like mkdir, except that any intermediate path segment (not
    just the rightmost) will be created if it does not exist.  This is
    recursive.

```

# Answer
> 2 votes
# Bash, ~~175~~ ~~169~~ ~~168~~ ~~135~~ ~~130~~ 128

Here's one of my worthwhile solutions from SO, then:

**WARNING:** Be sure to run in an empty directory, as this will wipe out its contents first thing per test.

```
read t
for((;x++<t;));do
rm -r *
read n m
for((i=n+m;i--;));do
read d
mkdir -p .$d
done
echo Case \#$x: $[`find|wc -l`-n-1]
done

```

---
Tags: code-challenge
---


title: Tree traversal.

text:
# Question
Title: Tree traversal.
Write the shortest code that traverses a tree, breadth-first.

### Input

any way you like

### Output

a list of "names" of the nodes in correct order.

# Answer
> 4 votes
# Common Lisp, 69 chars

returns rather than prints the list and takes input as argument

```
(defun b(e)(apply #'nconc (mapcar #'car (cdr e))(mapcar #'b (cdr e))))

```

Format is the same as below except it requires a 'dummy' root node like so:

```
(root (a (b (1) (2)) (c (1) (2))))

```

**Common Lisp: (95 chars)**

This one reads and prints instead of using arg parsing

```
(labels((b(e)(format t "~{~A~%~}"(mapcar #'car (cdr e)))(mapcar #'b (cdr e))))(b`((),(read))))

```

input to stdin should be a lisp form s.t. a tree with root a and two children b and c, each of which have children 1 & 2 should be `(a (b (1) (2)) (c (1) (2)))`

or equivalently -

```
(a
  (b
    (1)
    (2))
  (c
    (1)
    (2)))

```

# Answer
> 5 votes
# Haskell — ~~84~~ 76 characters

```
data N a=N{v::a,c::[N a]}
b(N a b)=d[a]b
d r[]=r
d r n=d(r++(map v n))$n>>=c

```

In a more readable format:

```
data Node a = Node {value::Int, children::[Node a]}

bfs :: Node Int -> [Int]
bfs (Node a b) = bfs' [a] b
  where bfs' res [] = res
        bfs' res n = bfs' (res ++ (map value n)) $ concatMap children n

```

The code allows **infinite number** of child nodes (not just left and right).

Sample tree:

```
sampleTree =
    N 1 [N 2 [N 5 [N  9 [],
                   N 10 []],
              N 6 []],
         N 3 [],
         N 4 [N 7 [N 11 [],
                   N 12 []],
              N 8 []]]

```

Sample run:

```
*Main> b sampleTree
[1,2,3,4,5,6,7,8,9,10,11,12]

```

Nodes are expanded in the order shown in Breadth-first search article on Wikipedia.

# Answer
> 4 votes
## Haskell: 63 characters

```
data N a=N{v::a,c::[N a]}
b n=d[n]
d[]=[]
d n=map v n++d(n>>=c)

```

This is really just a variation on @Yasir's solution, but that one isn't community wiki, and I couldn't edit it.

By just expanding the names, and replacing `concatMap` for `>>=`, the above golf'd code becomes perfectly reasonable Haskell:

```
data Tree a = Node { value :: a, children :: [Tree a] }

breadthFirst t = step [t]
  where step [] = []
        step ts = map value ts ++ step (concatMap children ts)

```

The only possibly golf-like trick is using `>>=` for `concatMap`, though even that isn't really that uncommon in real code.

# Answer
> 2 votes
# GolfScript, 4

Not a serious answer, but the Golfscript version of tobyodavies' sed answer is only 4 chars

```
n%n*

```

you could argue that

```
n%

```

is also sufficient,as it returns the tree items as a list, however these are displayed mashed together on stdout.

```
n%p

```

displays the list representation of the tree items (looks like a Python or Ruby list)

# Answer
> 1 votes
## Python - 59 chars

This one returns a generator, but modifies T, so you may want to pass in a copy

```
def f(T):
 t=iter(T)
 for i in t:yield i;T+=next(t)+next(t)

```

testing

```
              4
             / \
            /   \
           /     \
          2       9
         / \     / \
        1   3   6   10
               / \
              5   7
                   \
                    8

>>> T=[4,[2,[1,[],[]],[3,[],[]]],[9,[6,[5,[],[]],[7,[],[8,[],[]]]],[10,[],[]]]]
>>> f(T)
<generator object f at 0x87a31bc>
>>> list(_)
[4, 2, 9, 1, 3, 6, 10, 5, 7, 8]

```

---
Tags: code-golf, tree-traversal
---


# Question
Title: How would you count score in a Scrabble® game?
Let's say that we are programming a game that lets you play Scrabble®.

* We have a board with tiles placed on it, and empty cells are either normal or have multiplier properties (double or triple the points for a word or for a single letter).
* Each tile has a value and blank tiles have no value.

Thee goal here is to write a method that, given a `new_word` structure, will:

* verify that this word can be placed onto the grid at the specified position (the originating rack has the missing letters, it is not out of board range, blank tiles will not be adjacent on the board)
* return the number of points granted to the player.
* letter multipliers have priority over word multipliers
* all new words on the grid are counted (both horizontal and vertical)

Below are sample structures provided as an example.

```
// SCRABBLE® STRUCTURES

// a single Scrabble® tile.
struct tile
{
    // blank tiles are recognized by their value of 0.
    // The value of 'letter' is a space (L' ') until they
    // are positioned on the board. From that stage the
    // value of 'letter' contains what they represent.
    wchar_t      letter;
    unsigned int points;
};

// the bag with undrawed tiles
struct tile_bag
{
    // English version: 100 at start of game
    unsigned int  remaining_tiles;
    tile         *tiles;
};

// the content of a player rack
struct player_rack
{
    unsigned int     tile_count;
    tile            *tiles;
};

// a multiplier square
struct multiplier_cell
{
    enum
    {
        letter_scope,
        word_scope,
    } multiplier_scope;

    unsigned int multiplication_factor;
};

// a cell on the Scrabble® board
struct cell
{
    enum
    {
        normal,     // empty cell with no multiplier
        multiplier, // empty special cell, see multiplier_detail
        tile,       // cell with a tile on it, see tile_detail
    } cell_type;

    union
    {
        multiplier_cell multiplier_detail;
        tile            tile_detail;
    };
};

// a scrabble board;
struct board
{
    unsigned int width;  // usually 15
    unsigned int height; // usually 15
    cell **cells;
};

// a new word, placed on the grid
struct new_word
{
    // zero-terminated string representing the actual word.
    const wchar_t *zWord;

    // the same string, but with spaces for blanks that come
    // from the rack
    const wchar_t *zWord_with_blanks;

    // the rack the word originates from
    player_rack   *original_rack;

    // the cell position where the word begins
    unsigned int   verticalStart;
    unsigned int   horizontalStart;

    // the direction
    enum { vertical, horizontal, } direction;
};

// SCRABBLE® NUMERIC CONSTANTS

// how many tiles are allowed on the rack of a single player
// this is also the number of tiles that grant a bonus when
// placed onto the board at the same time.
// usually 7
extern const int max_allowed_tiles_on_a_rack;

// how many extra points are granted when scrabbling
// usually 50
extern const int scrabble_extra_points;

// GLOBAL VARIABLES

extern board        theBoard;
extern tile_bag     theBag;
extern int          theNumberOfPlayers;
extern player_rack *theRacks;

```

# Answer
# Haskell:

```
pointsFromWord :: [[Tile]] -> [Char] -> Word -> Maybe Int
pointsFromWord board rack (word, (x, y), Vertical) =
  pointsFromWord (transpose board) rack (Word word (y,x) Horizontal)
pointsFromWord board rack w@(word, (x, y), Horizontal) =
  if (validWord board w)
    then Just (wordScore board w)
    else Nothing

validWord :: [[Tile]] -> [Char] -> Word -> Bool
validWord board rack w@(word, (x, y), _) = x >= 0 && y >= 0 &&
  y < length board && (a + length word) < length (board!!y) &&
  foldl (\acc (c,t)->acc && characterFits t c) True (zip word wordLocation)
    where wordLocation = take (length word) (drop x (board!!y))
          characterFits (PlacedTile letter) c = letter == c
          characterFits _ c = contains rack c

wordScore :: [[Tile]] -> Word -> Int
wordScore board (word, (x, y), _) = (letterScore * multiplier) + scrabbleBonus
  where
    letterScore = foldl (\acc (c,t)->acc + value t c) 0 (zip word wordLocation)
    wordLocation = take (length word) (drop x (board!!y))
    value (LetterMultiplier mult) c = tileValue c * mult
    value (PlacedTile letter value) c = value
    value _ c = tileValue c

    multiplier = foldl (\acc t->acc * wordMultValue t) 1 wordLocation
    wordMultValue (WordMultiplier mult) = mult
    wordMultValue _ = 1

    scrabbleBonus = if length (filter fromRack wordLocation) == 7
                      then 50
                      else 0
    fromRack PlacedTile = False
    fromRack _ = True

```

A little longer than I'd like (especially the ton of where clauses on `wordScore`), but seems readable enough (at least to me).

I took a few liberties with the data structures themselves - transliterating the C structures into Haskell doesn't really work.

The board structure is a list of lists of tiles - a list of tiles forms a row, and a list of rows form a board.

Words contain, in order:

* A `[Char]` containing the exact tiles used (including blanks where a blank will be used instead of a letter). I assume this is prescreened for the no-two-blanks-next-to-each-other condition, though I suppose I could validate that as well.
* An `(Int, Int)` tuple specifying the location of the word
* An `Orientation` type constructed with either `Vertical` or `Horizontal`, specifying the orientation of the word.

Additionally, the player's current rack of tiles is passed separately from the word being tested, because that makes more sense.

I also assume a `tileValue` function which takes a character (including space) and returns the standard value of a tile depicting that character.
> 2 votes

---
Tags: code-challenge
---


title: Implement cdbmake

text:
# Question
Title: Implement cdbmake
Write the shortest program to build a cdb database, using the following syntax for input:

```
+*klen*,*dlen*:*key*->*data*

```

followed by a newline. Example:

```
+3,5:one->Hello
+3,7:two->Goodbye

```

(Unlike the real cdbmake, your program doesn't need to catch the empty-line-as-end-of-input case if you don't want to.) **Your program needs to handle arbitrary strings (including NUL, newline, `+`, `,`, `:`, and/or `->`) in both the key and data correctly;** therefore, using any kind of line-based input is likely to be wrong. You may assume the input is always valid, and you can assume that there is at most one instance of any key in the input.

**The hash tables your program generates must behave like real hash tables.** In other words, the hash tables should provide amortised constant-time lookups.

If your language provides built-in hash tables, you're allowed to use them, if they help any. However, **do not use any cdb libraries or cdb programs to solve this question.**

If your program writes the cdb to standard output, you may assume that it's redirected to a regular file. For example, you may seek or `mmap` it.

In the case of multiple shortest entries, the earliest-posted wins (as stipulated by the *fastest gun in the west* rule).

---

Here's a complete description of cdb's format as written by cdb's inventor:

> A cdb is an associative array: it maps strings (*keys*) to strings (*data*).
>
> A cdb contains 256 pointers to linearly probed open hash tables. The hash tables contain pointers to (key,data) pairs. A cdb is stored in a single file on disk:
>
> ```
> +----------------+---------+-------+-------+-----+---------+
> | p0 p1 ... p255 | records | hash0 | hash1 | ... | hash255 |
> +----------------+---------+-------+-------+-----+---------+
>
> ```
>
> Each of the 256 initial pointers states a position and a length. The position is the starting byte position of the hash table. The length is the number of slots in the hash table.
>
> Records are stored sequentially, without special alignment. A record states a key length, a data length, the key, and the data.
>
> Each hash table slot states a hash value and a byte position. If the byte position is 0, the slot is empty. Otherwise, the slot points to a record whose key has that hash value.
>
> Positions, lengths, and hash values are 32-bit quantities, stored in little-endian form in 4 bytes. Thus a cdb must fit into 4 gigabytes.
>
> A record is located as follows. Compute the hash value of the key in the record. The hash value modulo 256 is the number of a hash table. The hash value divided by 256, modulo the length of that table, is a slot number. Probe that slot, the next higher slot, and so on, until you find the record or run into an empty slot.
>
> The cdb hash function is `h = ((h << 5) + h) ^ c`, with a starting hash of 5381.

# Answer
## Python - 398 chars

```
import os;from struct import*
Q=256;S=[[]for x in' '*Q];D=[0]*Q;O=Q*8;R=os.read(0,1e9)[1:];J="".join
while R:
 i,R=R.split(":",1);l,m=map(int,i.split(','));k,v,R=R[:l],R[l+2:2+l+m],R[2+l+m:];R=R.partition("+")[2];D+=[pack("II",l,m)+k+v];h=5381
 for c in k:h=h*33^ord(c)%Q**4
 S[h%Q]+=[pack("II",h,O)];O+=len(D[-1])
for i,s in enumerate(S):D[i]=pack("II",O,len(s));D+=[J(s)];O+=len(D[-1])
print J(D)

```
> 2 votes

# Answer
## Python - 552 characters

```
from sys import*
from struct import*
y=lambda f,i:stdout.write(pack(f,*i))
u=lambda i:y('<II',i)
i=stdin.read()
n=0
t=[[]for c in' '*256]
q=[]
m=[]
o=2048
w=list.append
while len(i)>n:
 d=i.find(':',n);f,g=map(int,i[n+1:d].split(','));n=d+1+f;k=i[d+1:n];d=i[n+2:n+2+g];h=5831;for c in k:h=(((h<<5)+h)^ord(c))&0xffffffff
 w(t[h%256],(h,o));o+=8+f+g;w(m,map(str,(f,g,k,d)));n+=3+g
for d in t:
 l=len(d)**2;t=[(0,0)]*l;u((o,l));o+=l*8
 for r in d:
  i=r[0]>>8
  while t[i%l][0]:i+=1
  t[i%l]=r
 w(q,t)
for v in m:y('<II'+zip(v,'ss'),v)
for t in q:map(u,t)

```
> 1 votes

---
Tags: code-golf, data-structures
---


# Question
Title: Write a program to perform set operations.
Your task is to write a program to perform set operations. The operations and arguments are taken from command line in the format `program operation [argument]`. There are four operations:

1. **1**: clears the set. no arguments. exit code 0.
2. **2 integer**: adds the `integer` into the set. exit code 0.
3. **3 integer**: removes the `integer` from the set. exit code 0.
4. **4 integer**: queries the set for `integer`. exit code 0 if integer exists or 1 otherwise.

The integer is a 64-bits integer. Shortest program wins. You can, of course, use a temporary file. However, watch out the space and time limit.

Example:

```
$ program 1 ; echo $?
0
$ program 2 10 ; echo $?
0
$ program 4 10 ; echo $?
0
$ program 3 10 ; echo $?
0
$ program 4 10 ; echo $?
1
$ program 2 10 ; echo $?
0
$ program 1 ; echo $?
0
$ program 4 10 ; echo $?
1

```

# Answer
# Bash -- 54 chars

```
case $1 in
1)rm *;w;;
2)>$2;;
3)rm $2;w;;
4)<$2;;
esac

```

Notes: Outputs to stdout/stderr in some scenarios. Empties working directory when clearing the set. Uses one file for each set element. The purpose of `;w` is to exit with status 0.

This appears to comply with all the rules.
> 7 votes

# Answer
# Bash: 106 chars

```
touch f
case $1 in
1)rm -f f;;
2)echo $2>>f;;
3)grep -vx $2 f>g;mv g f;;
4)grep -x $2 f&>/dev/null;;
esac
```

Counting newlines as one character. Requires two temp files and POSIX grep. I'm unclear as to the precise constraints on temp files: if I can have two kicking around all the time then I can save 8 chars by writing to g rather than /dev/null in case 4.
> 2 votes

# Answer
# Python - 167 chars

```
import sys,shelve as S
x,A,E=S.open("x"),sys.argv,exit
A[1]<'2'and E(x.clear())or'3'>A[1]and E(x.__setitem__(A[2],1))or'4'>A[1]and E(x.__delitem__(A[2]))or E(A[2]in x)

```

You need to create the temporary file like this

```
python -c 'import shelve;shelve.open("x","c")'

```
> 2 votes

# Answer
# bash, 74

```
case $1 in
1)>f;;
2)echo $2>>f;;
3)sed -i /^$2$/d f;;
4)grep ^$2$ f;;
esac

```

**note** I'm not plagiarizing Peter Taylor, it's just that it's not working with `[ test ]`s
> 2 votes

# Answer
# PHP - 204 characters

```
<?
$s=unserialize(file_get_contents('f'));
$a=$argv;
$o=$a[1]--;
$a=$a[2];
--$o?(--$o?(--$o?die(!isset($s[$a])+0):$s=array_diff_key($s,array($a=>1))):$s[$a]=1):$s=array();
file_put_contents('f',serialize($s));

```

Added some linebreaks to make it a tad more readable. This throws a warning to screen when run for the first time, but otherwise, it does as asked.
> 1 votes

# Answer
# Ruby - 146 characters

```
a,b=ARGV
File.open('x','a+'){|f|s=eval(f.read)||[]
s=[]if a=='1'
s+=[b]if a=='2'
s-=[b]if a=='3'
f.puts s.inspect
exit a=='4'?(s.index(b)?0:1):0}

```
> 1 votes

---
Tags: code-golf, set-theory, stateful
---


title: Break the broken cipher

text:
# Question
Title: Break the broken cipher
I have designed a simple random generator that cycles two numbers in a chaotic way using a multiply and modulus method. It works great for that.

If I were to use it as a cipher generator it would however be vulnerable to a known plaintext attack, given that an attacker can reverse engineer the seed from a series of random numbers in a computationally efficient manner.

To prove the cipher broken **find a legal pair of seed values that generate 7 zeros in a row in the range \[0;255\], using as little power, CPU-time etc. as possible.**

Here is the random generator written in JavaScript:

```
function seed(state1,state2){
    //Constants
    var mod1=4294967087
    var mul1=65539
    var mod2=4294965887
    var mul2=65537
    function random(limit){
        //Cycle each state variable 1 step
        state1=(state1*mul1)%mod1
        state2=(state2*mul2)%mod2
        //Return a random variable
        return (state1+state2)%limit
    }
    //Return the random function
    return random
}

//Initiate the random generator using 2 integer values,
//they must be in the ranges [1;4294967086] and [1;4294965886]
random=seed(31337,42)
//Write 7 random values in the range [0;255] to screen
for(a=0;a<7;a++){
    document.write(random(256)+"<br>")
}

```

I have made a tool for testing candidate number pairs, it can be found here.

**For the next 3 days, no spoilers allowed**, an answer must contain only a set of numbers, and it should of course be a different set from those posted by previous solvers. Thereafter you are encouraged to post code and explain your approach.

Edit, quarantine is over:
Answers should contain both a unique set of numbers and explanation and code to document the solving method.

Most elegant solution wins.

For the record:
Writing a program that can find a solution quickly is elegant.
Making a program that utilize the features of a GPU efficiently to do it even faster is elegant.
Doing the job on a piece of "museumware" is elegant.
Finding a solution method that can feasibly be utilized using only pen and paper is very elegant.
Explaining your solution in an instructive and easily understandable manner is elegant.

Using multiple or very expensive computers is inelegant.

# Answer
# C++, 44014022 / 164607120

It is in C++, uses 1 GB of memory, and took about 45 seconds to find this first pair. I'll update the time once it finds them all.

Code below. It first finds all pairs that generate 4 zeros, then whittles those down by simple trial (see the `check` method). It finds pairs that generate 4 zeros by generating two large arrays, one which contains the first 4 low-order bytes of the state1 generator, and the second which contains the negative of the first 4 low-order bytes of the state2 generator. These arrays are then sorted and searched for a match, which corresponds to the overall generator outputting 4 zeros to start.

The arrays are too big to store in memory, so it does the work in batches sized to just fit in memory.

Looks like the complete run will take ~12 hours.

**Edit**: Improved the code so it only takes ~1 hour to get all possible seeds. Now it generates the tables into 256 different files, one for each first byte of output. We can then process each file independently so we don't have to regenerate data.

**Edit**: Turns out you can generate the 256 subtables individually instead of all at once, so no disk needed. Running time down to ~15 minutes using 256MB.

```
#include <stdio.h>
#include <stdint.h>
#include <algorithm>
using namespace std;

#define M1 65539
#define N1 4294967087
#define M2 65537
#define N2 4294965887
#define MATCHES 7

// M^-1 mod N
#define M1_INV 3027952124
#define M2_INV 1949206866

int npairs = 0;

void check(uint32_t seed1, uint32_t seed2) {
  uint32_t s1 = seed1;
  uint32_t s2 = seed2;
  for (int i = 0; i < MATCHES; i++) {
    s1 = (uint64_t)s1 * M1 % N1;
    s2 = (uint64_t)s2 * M2 % N2;
    if (((s1 + s2) & 0xff) != 0) return;
  }
  printf("%d %u %u\n", npairs++, seed1, seed2);
}

struct Record {
  uint32_t signature; // 2nd through 5th generated bytes
  uint32_t seed;      // seed that generated them
};
// for sorting Records
bool operator<(const Record &a, const Record &b) {
  return a.signature < b.signature;
}

int main(int argc, char *argv[]) {
  Record *table1 = (Record*)malloc((N1/256+1)*sizeof(*table1));
  Record *table2 = (Record*)malloc((N2/256+1)*sizeof(*table2));

  for (int i = 0; i < 256; i++) {  // iterate over first byte
    printf("first byte %x\n", i);

    // generate signatures (bytes 2 through 5) for all states of generator 1
    // that generate i as the first byte.
    Record *r = table1;
    for (uint64_t k = i; k < N1; k += 256) {
      uint32_t sig = 0;
      uint32_t v = k;
      for (int j = 0; j < 4; j++) {
        v = (uint64_t)v * M1 % N1;
        sig = (sig << 8) + (v & 0xff);
      }
      r->signature = sig;
      r->seed = k;
      r++;
    }
    Record *endtable1 = r;

    // generate signatures (bytes 2 through 5) for all states of generator 2
    // that generate -i as the first byte.
    r = table2;
    for (uint64_t k = (-i & 0xff); k < N2; k += 256) {
      uint32_t sig = 0;
      uint32_t v = k;
      for (int j = 0; j < 4; j++) {
        v = (uint64_t)v * M2 % N2;
        sig = (sig << 8) + (-v & 0xff);
      }
      r->signature = sig;
      r->seed = k;
      r++;
    }
    Record *endtable2 = r;

    sort(table1, endtable1);
    sort(table2, endtable2);

    // iterate through looking for matches
    const Record *p1 = table1;
    const Record *p2 = table2;
    while (p1 < endtable1  && p2 < endtable2) {
      if (p1->signature < p2->signature) p1++;
      else if (p1->signature > p2->signature) p2++;
      else {
        check((uint64_t)p1->seed * M1_INV % N1, (uint64_t)p2->seed * M2_INV % N2);
        // NOTE: may skip some potential matches, if p1->signature==(p1+1)->signature or p2->signature==(p2+1)->signature
        p1++;
      }
    }
  }
}

```
> 6 votes

---
Tags: code-challenge, math, fastest-code, cryptography
---


# Question
Title: Shorten this code while fixing a major bug
I found the code below today after much hair pulling. Shorten it down (code golf) and fix the bug that I found (bonus).

```
#define LN_SOME_TEXT_FIELD 256

void GetSomeText(LPTSTR text)
{
    TCHAR       buf[LN_SOME_TEXT_FIELD + 1];
    short       i;
    LPTSTR      curChar;

    curChar = text;
    i = 0;
    while (*curChar != NULL) {
        if (*curChar != '&') {
            buf[i] = *curChar;
            i++;
        }
        curChar++;
    }
    buf[i] = NULL;
    SomeOtherUIFunction(buf);
}

```

**EDIT** Added a tail call, this is what the real function does, sorry for not including it earlier.

# Answer
> 5 votes
Are you sure you didn't fix the bug already? I don't see a flaw in the logic, but I do see a few obvious problems:

* The output buffer is never returned, so this function is a no-op. The post was changed so the `buf` is used now.
* The output buffer has a fixed-width. This is fine, as long as the input's length does not exceed LN\_SOME\_TEXT\_FIELD.
* Using `NULL` instead of `'\0'`. `NULL` expands to `((void*) 0)`, meaning it's a pointer. It should not be used to refer to the null character.

Anyway, here is a nicer (in my opinion) version of the code above:

```
void GetSomeText(const char *in, char *out)
{
    for (; *in != '\0'; in++) {
        if (*in != '&')
            *out++ = *in;
    }
    *out = '\0';
}

```

# Answer
> 4 votes
## Haskell, 13 characters

```
filter(/='&')

```

or, not golf'd:

```
getSomeText :: String -> String
getSomeText = filter (/='&')

```

But, I'm guessing that this isn't the desired function, but probably something that unescapes. If so, then the function is `g`, 36 characters:

```
g('&':a:z)=a:g z;g(a:z)=a:g z;g _=[]

```

or, not golf'd:

```
getSomeText :: String -> String
getSomeText ('&':a:as) = a : getSomeString as
getSomeText (    a:as) = a : getSomeString as
getSomeText []         = []

```

Seriously, *this* is exactly why functional programming matters. "Turn on, tune in, learn Haskell!"

# Answer
> 4 votes
### Perl, 5 chars

```
s/&//
```

Or

```
sub GetSomeText{$@[0]~=s/&//}
```
if you insist on wrapping something so trivial in a subroutine.

---
Tags: code-golf
---


# Question
Title: Check printer - Convert to English text from the input value.
Check printer function (or subroutine) - Convert to English text from the input value. 12.34 -\> "twelve dollars and thirty four cents". For the range .01 to 9999.99 assuming valid input.

# Answer
# Common Lisp, 95

Newline not counted in:

```
(lambda(n &aux(d(floor n))(c(round(*(- n d)100))))
(format()"~R dollar~P and ~R cent~P"d d c c))

```

Sample use (assigning it to f):

```
CL-USER> (f .01)
"zero dollars and one cent"
CL-USER> (f 12.34)
"twelve dollars and thirty-four cents"
CL-USER> (f 9999.99)
"nine thousand nine hundred ninety-nine dollars and ninety-nine cents"

```
> 3 votes

---
Tags: code-golf, conversion
---