diff options
Diffstat (limited to 'algorithms')
| -rw-r--r-- | algorithms/binary_search.cc | 27 | ||||
| -rwxr-xr-x | algorithms/binary_search.py | 25 | ||||
| -rwxr-xr-x | algorithms/binary_search.rb | 18 | ||||
| -rwxr-xr-x | algorithms/binary_search1.py | 16 | ||||
| -rwxr-xr-x | algorithms/bleu.py | 19 | ||||
| -rwxr-xr-x | algorithms/cyk_loops.rb | 28 | ||||
| -rwxr-xr-x | algorithms/factorial.py | 22 | ||||
| -rwxr-xr-x | algorithms/fibonacci.py | 13 | ||||
| -rwxr-xr-x | algorithms/insertion_sort.py | 20 | ||||
| -rwxr-xr-x | algorithms/letter_substitution_cipher.rb | 67 | ||||
| -rwxr-xr-x | algorithms/log_reg_sgd.rb | 71 | ||||
| -rw-r--r-- | algorithms/parse_bracketed.input | 880 | ||||
| -rwxr-xr-x | algorithms/parse_bracketed.rb | 127 | ||||
| -rw-r--r-- | algorithms/string_reverse.c | 42 | ||||
| -rw-r--r-- | algorithms/string_reverse.cc | 37 | ||||
| -rwxr-xr-x | algorithms/string_reverse.py | 7 | ||||
| -rwxr-xr-x | algorithms/sudoku.py | 90 |
17 files changed, 1509 insertions, 0 deletions
diff --git a/algorithms/binary_search.cc b/algorithms/binary_search.cc new file mode 100644 index 0000000..773fcf3 --- /dev/null +++ b/algorithms/binary_search.cc @@ -0,0 +1,27 @@ +#include <iostream> + +using namespace std; + + +int binsearch(int* a, int val, int lo, int hi) { + if (hi < lo) return -1; + int mid = (lo+hi)/2; + if (val < a[mid]) { + return binsearch(a, val, lo, mid-1); + } else if (val > a[mid]) { + return binsearch(a, val, mid+1, hi); + } else { + return lo; + } +} + +int main(void) { + int a[10] = {0,1,2,3,4,5,6,7,8,9}; + int lo = 0; + int hi = 9; + + int val = 3; + + cout << binsearch(a, val, lo, hi) << endl; +} + diff --git a/algorithms/binary_search.py b/algorithms/binary_search.py new file mode 100755 index 0000000..3d158dc --- /dev/null +++ b/algorithms/binary_search.py @@ -0,0 +1,25 @@ +#!/usr/bin/env python2 + + +def bin_search(a, val, lo, hi): + print "%d %d"%(lo, hi) + if hi < lo: + return -1 + mid = (lo+hi)/2 + if a[mid] > val: + return bin_search(a, val, lo, mid-1) + elif a[mid] < val: + return bin_search(a, val, mid+1, hi) + else: + return mid + + +a = [1, 2, 3, 4, 5, 6, 7, 8] +# 0 1 2 3 4 5 6 7 + +if bin_search(a, 3, 0, len(a)-1): + print "Yay!" +else: + print ":-(" + + diff --git a/algorithms/binary_search.rb b/algorithms/binary_search.rb new file mode 100755 index 0000000..70f2eb0 --- /dev/null +++ b/algorithms/binary_search.rb @@ -0,0 +1,18 @@ +#!/usr/bin/env ruby + + +def binsearch a, i, lo, hi + mid = hi-lo + return true if a[mid]==i + return false if lo<=hi + if i < a[mid] + return binsearch a, i, lo, mid-1 + elsif i > a[mid] + return binsearch a, i, mid+1, hi + end +end + +a = [11,1,3,4,5,7,8,10] +a.sort! +puts binsearch a, 11, 0, a.size-1 + diff --git a/algorithms/binary_search1.py b/algorithms/binary_search1.py new file mode 100755 index 0000000..ea864ae --- /dev/null +++ b/algorithms/binary_search1.py @@ -0,0 +1,16 @@ +#!/usr/bin/env python2 + + +def binsearch(a, v, left, right): + mid = (right-left)/2 + left + if mid > right: return 0 + if a[mid] == v: + return 1 + elif v > a[mid]: + return binsearch(a, v, mid+1, right) + elif v < a[mid]: + return binsearch(a, v, left, mid-1) + +a = [1, 2, 3, 4, 5 , 7, 8, 9, 10, 11] +print binsearch(a, 10, 0, len(a)-1) + diff --git a/algorithms/bleu.py b/algorithms/bleu.py new file mode 100755 index 0000000..77c3c82 --- /dev/null +++ b/algorithms/bleu.py @@ -0,0 +1,19 @@ +#!/usr/bin/env python2 + +import math + + +def BLEU(N, w, v): + sum = 0 + for i in range(N): + j = i+1 + if v[i] == 0: continue + sum += (w[i]*math.exp(math.log(v[i])))/(2**(N-j+1)) + print v[i], math.log(v[i]), w[i] * math.log(v[i]), w[i] + return sum + +N = 4 +w = [1.0/N for i in range(N)] +v = [0.1, 0.1, 0.1, 0.1] +print BLEU(N, w, v) + diff --git a/algorithms/cyk_loops.rb b/algorithms/cyk_loops.rb new file mode 100755 index 0000000..e8450cd --- /dev/null +++ b/algorithms/cyk_loops.rb @@ -0,0 +1,28 @@ +#!/usr/bin/env ruby + + +n=5 +(2..n).each { |gap| + (0..(n-gap)).each { |i| + k = i+gap + ((i+1)..(k-1)).each { |j| + puts "#{i},#{k}" + puts " #{i},#{j}" + puts " #{j},#{k}" + } + #puts + } +} + +(2..n).each { |i| + (0..(n-i)).each { |j| + puts "#{j} #{j+i}" + (1..n).each { |l| + (j..(j+i-l)).each { |k| + puts " #{k} #{k+l}" + } + } + + } +} + diff --git a/algorithms/factorial.py b/algorithms/factorial.py new file mode 100755 index 0000000..41eb708 --- /dev/null +++ b/algorithms/factorial.py @@ -0,0 +1,22 @@ +#!/usr/bin/env python2 + + +cache = {0:1} + +def fak(n): + if n == 0: return 1 + if cache.get(n, 0): + return cache[n] + if not cache.get(n-1, 0): + cache[n-1] = fak(n-1) + return n*cache[n-1] + +def fakn(n): + if n == 0: + return 1 + else: + return n*fak(n-1) + +for i in [fak(i) for i in reversed(range(10))]: + print i + diff --git a/algorithms/fibonacci.py b/algorithms/fibonacci.py new file mode 100755 index 0000000..5912de0 --- /dev/null +++ b/algorithms/fibonacci.py @@ -0,0 +1,13 @@ +#!/usr/bin/env python2 + + +def fib(n): + if n == 0: + return 0 + elif n == 1: + return 1 + else: + return fib(n-1) + fib(n-2) + +print fib(20) + diff --git a/algorithms/insertion_sort.py b/algorithms/insertion_sort.py new file mode 100755 index 0000000..ab786e0 --- /dev/null +++ b/algorithms/insertion_sort.py @@ -0,0 +1,20 @@ +#!/usr/bin/env python2 + +import random + + +def insertion_sort(l): + sz = len(l) + for i in range(sz): + if i == 0: continue + j = i-1 + while l[i] < l[j] and j > -1: + j -= 1 + l.insert(j+1, l.pop(i)) + return l + +l = list(reversed(range(1000))) +#random.shuffle(l) +print l +print insertion_sort(l) + diff --git a/algorithms/letter_substitution_cipher.rb b/algorithms/letter_substitution_cipher.rb new file mode 100755 index 0000000..01bde9b --- /dev/null +++ b/algorithms/letter_substitution_cipher.rb @@ -0,0 +1,67 @@ +#!/usr/bin/env ruby + + +ALPHABET = ('a'..'z').to_a +ALPHABET << ' ' +puts ALPHABET.to_s + +def mklettersubstitioncipher + cipher = {} + ALPHABET.each { |i| + while true + c = ALPHABET[ Random.rand(ALPHABET.size) ] + if not cipher.values.include? c + cipher[i] = c + break + end + end + } + return cipher +end + +def encrypt(key, plaintext) + s = '' + plaintext.each_char { |i| s += key[i] } + return s +end + +def decrypt(key, ciphertext) + s = '' + ciphertext.each_char { |i| + key.each_pair { |p| + if p[1] == i + s += p[0] + end + } + } + return s +end + +def randomcipherstring(cipher) + length = Random.rand(49)+1 + s = '' + length.times { + s += cipher[ ALPHABET[Random.rand(ALPHABET.size)] ] + } + return s +end + +def sample(n, cipher) + a = [] + n.times { + a << randomcipherstring(cipher) + } + puts a.to_s +end + +def test + cipher = mklettersubstitioncipher + s = "das ist das haus vom nikolaus" + s_enc = encrypt(cipher, s) + s_dec = decrypt(cipher, s_enc) + puts "#{s}\n#{s_enc}\n#{s_dec}" +end + + +test + diff --git a/algorithms/log_reg_sgd.rb b/algorithms/log_reg_sgd.rb new file mode 100755 index 0000000..16a48e2 --- /dev/null +++ b/algorithms/log_reg_sgd.rb @@ -0,0 +1,71 @@ +#!/usr/bin/env ruby + +require 'nlp_ruby' +require 'trollop' + + +def read_data fn, scale + f = ReadFile.new fn + data = [] + while line = f.gets + line.strip! + a = [] + a << 1.0 + tokenize(line).each { |i| a << i.to_f } + v = SparseVector.from_a a + data << v + end + if scale + data.map { |i| i.keys }.flatten.uniq.each { |k| + max = data.map { |i| i[k] }.max + data.each { |i| i[k] /= max } + } + end + return data +end + +def main + cfg = Trollop::options do + opt :input, "input data", :type => :string, :required => true + opt :output, "1/0 output data", :type => :string, :required => true + opt :learning_rate, "learning rate", :type => :float, :default => 0.07 + opt :stop, "stopping criterion", :type => :int, :default => 100 + opt :scale_features,"scale features", :type => :bool, :default => false, :short => '-t' + opt :show_loss, "show loss per iter", :type => :bool, :default => false + end + data = read_data cfg[:input], cfg[:scale_features] + zeros = [0.0]*data[0].size + t = ReadFile.readlines(cfg[:output]).map{ |i| i.to_f } + model = SparseVector.new zeros + stop = 0 + prev_model = nil + i = 0 + while true + i += 1 + u = SparseVector.new zeros + overall_loss = 0.0 + data.each_with_index { |x,j| + m = 1.0/(1+Math.exp(-model.dot(x))) + loss = m - t[j] + overall_loss += loss + u += x * loss + } + STDERR.write "#{i} #{overall_loss/data.size}\n" if cfg[:show_loss] + u *= cfg[:learning_rate]*(1.0/t.size) + model -= u + if model.approx_eql? prev_model + stop += 1 + else + stop = 0 + end + break if stop==cfg[:stop] + prev_model = model + puts model.to_s + end + STDERR.write "ran for #{i} iterations\n" + puts model.to_s +end + + +main + diff --git a/algorithms/parse_bracketed.input b/algorithms/parse_bracketed.input new file mode 100644 index 0000000..5a2973f --- /dev/null +++ b/algorithms/parse_bracketed.input @@ -0,0 +1,880 @@ +answer(city(loc_2(stateid('virginia')))) +answer(high_point_1(state(next_to_2(stateid('mississippi'))))) +answer(river(loc_2(stateid('arkansas')))) +answer(river(loc_2(stateid('colorado')))) +answer(capital(loc_2(stateid('texas')))) +answer(highest(place(loc_2(state(stateid('oregon')))))) +answer(count(state(low_point_2(lower_2(low_point_1(stateid('alabama'))))))) +answer(state(loc_2(countryid('usa')))) +answer(city(loc_2(stateid('texas')))) +answer(city(loc_2(countryid('usa')))) +answer(city(loc_2(stateid('virginia')))) +answer(city(loc_2(stateid('texas')))) +answer(lake(loc_2(stateid('california')))) +answer(largest(state(all))) +answer(longest(river(traverse_2(countryid('usa'))))) +answer(count(river(loc_2(stateid('california'))))) +answer(state(next_to_2(stateid('utah')))) +answer(size(stateid('alaska'))) +answer(size(stateid('massachusetts'))) +answer(size(stateid('new mexico'))) +answer(size(stateid('north dakota'))) +answer(size(stateid('texas'))) +answer(size(city(cityid('new york', _)))) +answer(elevation_1(highest(place(loc_2(state(all)))))) +answer(elevation_1(placeid('guadalupe peak'))) +answer(elevation_1(placeid('mount mckinley'))) +answer(elevation_1(highest(place(loc_2(countryid('usa')))))) +answer(elevation_1(highest(place(loc_2(stateid('montana')))))) +answer(elevation_1(highest(place(loc_2(largest(state(all))))))) +answer(elevation_1(highest(place(loc_2(stateid('alabama')))))) +answer(elevation_1(highest(place(loc_2(stateid('delaware')))))) +answer(elevation_1(highest(place(loc_2(stateid('florida')))))) +answer(elevation_1(highest(place(loc_2(stateid('louisiana')))))) +answer(size(stateid('alaska'))) +answer(size(stateid('texas'))) +answer(size(largest(city(loc_2(stateid('alaska')))))) +answer(len(riverid('rio grande'))) +answer(len(river(riverid('colorado')))) +answer(len(river(riverid('delaware')))) +answer(len(longest(river(loc_2(stateid('california')))))) +answer(len(longest(river(loc_2(countryid('usa')))))) +answer(len(riverid('mississippi'))) +answer(len(river(riverid('mississippi')))) +answer(len(river(riverid('mississippi')))) +answer(len(river(riverid('missouri')))) +answer(len(river(riverid('north platte')))) +answer(len(river(riverid('ohio')))) +answer(len(river(riverid('rio grande')))) +answer(len(shortest(river(loc_2(countryid('usa')))))) +answer(count(major(city(loc_2(stateid('pennsylvania')))))) +answer(count(capital(loc_2(stateid('rhode island'))))) +answer(count(city(loc_2(stateid('louisiana'))))) +answer(count(city(loc_2(stateid('montana'))))) +answer(count(city(loc_2(countryid('usa'))))) +answer(count(city(loc_2(countryid('usa'))))) +answer(count(city(loc_2(countryid('usa'))))) +answer(count(city(loc_2(countryid('usa'))))) +answer(count(city(loc_2(stateid('texas'))))) +answer(count(city(loc_2(countryid('usa'))))) +answer(count(intersection(city(cityid('austin', _)), loc_2(countryid('usa'))))) +answer(population_1(largest(city(all)))) +answer(population_1(stateid('alabama'))) +answer(population_1(cityid('boulder', _))) +answer(population_1(stateid('california'))) +answer(count(river(riverid('colorado')))) +answer(population_1(cityid('montgomery', _))) +answer(count(major(city(loc_2(stateid('arizona')))))) +answer(count(major(city(loc_2(stateid('florida')))))) +answer(count(major(city(loc_2(state(next_to_2(stateid('nebraska')))))))) +answer(count(major(city(loc_2(state(next_to_2(stateid('utah')))))))) +answer(count(major(city(loc_2(stateid('texas')))))) +answer(count(major(city(all)))) +answer(count(major(city(loc_2(stateid('oregon')))))) +answer(count(major(river(traverse_2(stateid('ohio')))))) +answer(population_1(state(stateid('nevada')))) +answer(population_1(stateid('iowa'))) +answer(population_1(stateid('new york'))) +answer(population_1(cityid('boulder', _))) +answer(population_1(cityid('austin', _))) +answer(population_1(cityid('austin', 'tx'))) +answer(population_1(stateid('california'))) +answer(population_1(cityid('chicago', _))) +answer(population_1(cityid('detroit', _))) +answer(population_1(stateid('hawaii'))) +answer(population_1(cityid('houston', _))) +answer(population_1(cityid('kalamazoo', _))) +answer(population_1(stateid('kansas'))) +answer(population_1(cityid('minneapolis', 'mn'))) +answer(population_1(stateid('mississippi'))) +answer(population_1(stateid('montana'))) +answer(population_1(stateid('new hampshire'))) +answer(population_1(stateid('new mexico'))) +answer(population_1(stateid('new york'))) +answer(population_1(stateid('rhode island'))) +answer(population_1(cityid('riverside', _))) +answer(population_1(cityid('san francisco', _))) +answer(population_1(stateid('south dakota'))) +answer(population_1(cityid('spokane', 'wa'))) +answer(population_1(stateid('texas'))) +answer(population_1(largest(city(loc_2(state(stateid('new york'))))))) +answer(population_1(capital(loc_2(stateid('georgia'))))) +answer(population_1(capital(loc_2(stateid('texas'))))) +answer(population_1(smallest(state(next_to_2(stateid('wyoming')))))) +answer(population_1(largest_one(density_1(state(all))))) +answer(population_1(countryid('usa'))) +answer(population_1(stateid('washington'))) +answer(population_1(cityid('washington', 'dc'))) +answer(population_1(cityid('austin', _))) +answer(population_1(stateid('utah'))) +answer(population_1(stateid('utah'))) +answer(population_1(stateid('texas'))) +answer(count(river(riverid('colorado')))) +answer(count(river(loc_2(stateid('colorado'))))) +answer(count(river(loc_2(stateid('colorado'))))) +answer(count(river(loc_2(stateid('iowa'))))) +answer(count(river(loc_2(stateid('missouri'))))) +answer(count(river(loc_2(stateid('new york'))))) +answer(count(river(loc_2(most(state(loc_1(river(all)))))))) +answer(count(river(loc_2(state(loc_1(highest(place(all)))))))) +answer(count(river(loc_2(largest_one(population_1(state(all))))))) +answer(count(river(loc_2(stateid('idaho'))))) +answer(count(river(loc_2(stateid('texas'))))) +answer(count(river(loc_2(countryid('usa'))))) +answer(count(exclude(river(all), traverse_2(state(loc_1(capital(cityid('albany', _)))))))) +answer(count(river(loc_2(stateid('alaska'))))) +answer(count(river(loc_2(stateid('colorado'))))) +answer(count(intersection(river(loc_2(stateid('texas'))), longer(riverid('red'))))) +answer(count(river(loc_2(stateid('washington'))))) +answer(count(river(traverse_2(stateid('texas'))))) +answer(count(river(traverse_2(state(next_to_2(stateid('colorado'))))))) +answer(area_1(countryid('usa'))) +answer(count(state(loc_2(countryid('usa'))))) +answer(count(state(loc_2(countryid('usa'))))) +answer(count(state(next_to_2(major(river(all)))))) +answer(count(state(all))) +answer(count(state(loc_2(countryid('usa'))))) +answer(count(state(loc_2(countryid('usa'))))) +answer(count(state(next_to_2(stateid('alaska'))))) +answer(count(state(next_to_2(state(all))))) +answer(count(state(intersection(next_to_2(stateid('colorado')), next_to_2(stateid('new mexico')))))) +answer(count(state(next_to_2(stateid('hawaii'))))) +answer(count(state(next_to_2(stateid('iowa'))))) +answer(count(state(next_to_2(state(loc_1(capital(cityid('boston', _)))))))) +answer(count(state(next_to_2(stateid('tennessee'))))) +answer(count(state(next_to_2(stateid('texas'))))) +answer(count(state(next_to_2(largest(state(all)))))) +answer(count(state(next_to_2(river(riverid('mississippi')))))) +answer(count(state(next_to_2(most(state(next_to_2(state(all)))))))) +answer(count(state(next_to_2(largest_one(population_1(state(all))))))) +answer(count(exclude(state(all), loc_1(river(all))))) +answer(count(state(next_to_1(stateid('iowa'))))) +answer(count(state(next_to_1(stateid('missouri'))))) +answer(count(state(next_to_1(stateid('tennessee'))))) +answer(count(state(traverse_1(river(riverid('colorado')))))) +answer(count(state(traverse_1(river(riverid('colorado')))))) +answer(count(state(traverse_1(river(riverid('mississippi')))))) +answer(count(state(traverse_1(riverid('mississippi'))))) +answer(count(state(traverse_1(river(riverid('missouri')))))) +answer(count(state(loc_2(countryid('usa'))))) +answer(count(state(loc_1(city(cityid('rochester', _)))))) +answer(count(state(loc_1(city(cityid('springfield', _)))))) +answer(count(state(loc_1(place(higher_2(highest(place(loc_2(state(loc_1(largest(capital(city(loc_2(countryid('usa')))))))))))))))) +answer(count(state(loc_1(city(cityid('austin', _)))))) +answer(count(state(loc_1(city(cityid('springfield', _)))))) +answer(count(state(loc_1(major(river(all)))))) +answer(count(intersection(state(loc_2(countryid('usa'))), traverse_1(shortest(river(all)))))) +answer(population_1(stateid('texas'))) +answer(elevation_1(placeid('mount mckinley'))) +answer(elevation_1(highest(place(loc_2(stateid('montana')))))) +answer(state(loc_1(placeid('mount mckinley')))) +answer(state(loc_1(highest(place(loc_2(countryid('usa'))))))) +answer(state(loc_1(cityid('rochester', _)))) +answer(count(state(next_to_1(stateid('iowa'))))) +answer(state(all)) +answer(lake(loc_2(countryid('usa')))) +answer(river(loc_2(stateid('colorado')))) +answer(capital(loc_2(countryid('usa')))) +answer(longest(river(loc_2(countryid('usa'))))) +answer(major(lake(loc_2(stateid('michigan'))))) +answer(major(river(loc_2(stateid('florida'))))) +answer(river(loc_2(stateid('arkansas')))) +answer(exclude(state(all), next_to_2(state(all)))) +answer(population_1(cityid('boulder', _))) +answer(population_1(cityid('boulder', _))) +answer(count(state(next_to_2(stateid('iowa'))))) +answer(state(loc_1(lowest(place(loc_2(state(traverse_1(river(riverid('mississippi')))))))))) +answer(population_1(cityid('boulder', _))) +answer(population_1(cityid('boulder', _))) +answer(river(loc_2(stateid('new york')))) +answer(state(loc_1(capital(cityid('sacramento', _))))) +answer(state(loc_1(cityid('san antonio', _)))) +answer(major(city(loc_2(stateid('colorado'))))) +answer(major(lake(loc_2(countryid('usa'))))) +answer(largest_one(area_1(state(all)))) +answer(state(next_to_2(stateid('iowa')))) +answer(city(loc_2(stateid('texas')))) +answer(state(traverse_1(longest(river(loc_2(stateid('texas'))))))) +answer(state(traverse_1(riverid('mississippi')))) +answer(state(traverse_1(riverid('mississippi')))) +answer(river(loc_2(stateid('texas')))) +answer(major(river(loc_2(stateid('texas'))))) +answer(longest(river(loc_2(stateid('texas'))))) +answer(capital(city(loc_2(state(next_to_2(stateid('texas'))))))) +answer(capital(city(loc_2(stateid('texas'))))) +answer(capital(loc_2(state(next_to_2(stateid('missouri')))))) +answer(capital(loc_2(state(next_to_2(stateid('texas')))))) +answer(city(loc_2(stateid('california')))) +answer(city(loc_2(state(traverse_1(riverid('mississippi')))))) +answer(city(loc_2(state(loc_1(highest(place(all))))))) +answer(highest(place(loc_2(state(all))))) +answer(highest(place(loc_2(state(next_to_2(stateid('mississippi'))))))) +answer(lake(loc_2(state(next_to_2(stateid('texas')))))) +answer(largest(city(loc_2(state(next_to_2(largest(state(all)))))))) +answer(major(city(loc_2(stateid('alabama'))))) +answer(major(city(loc_2(stateid('alaska'))))) +answer(major(city(loc_2(stateid('california'))))) +answer(major(city(loc_2(stateid('delaware'))))) +answer(major(city(loc_2(stateid('kansas'))))) +answer(major(city(loc_2(stateid('missouri'))))) +answer(major(city(loc_2(stateid('new mexico'))))) +answer(major(city(loc_2(stateid('new york'))))) +answer(major(city(loc_2(stateid('north carolina'))))) +answer(major(city(loc_2(stateid('ohio'))))) +answer(major(city(loc_2(stateid('oklahoma'))))) +answer(major(city(loc_2(stateid('rhode island'))))) +answer(major(city(loc_2(state(traverse_1(riverid('mississippi'))))))) +answer(major(city(loc_2(stateid('texas'))))) +answer(major(city(loc_2(largest(state(all)))))) +answer(major(city(loc_2(smallest(state(loc_2(countryid('usa')))))))) +answer(major(city(loc_2(state(stateid('california')))))) +answer(major(city(loc_2(state(traverse_1(major(river(loc_2(stateid('virginia')))))))))) +answer(major(city(loc_2(countryid('usa'))))) +answer(major(city(loc_2(stateid('vermont'))))) +answer(major(city(loc_2(stateid('wyoming'))))) +answer(major(city(loc_2(stateid('texas'))))) +answer(major(city(loc_2(countryid('usa'))))) +answer(major(city(loc_2(countryid('usa'))))) +answer(major(lake(loc_2(countryid('usa'))))) +answer(major(river(loc_2(stateid('ohio'))))) +answer(major(river(loc_2(countryid('usa'))))) +answer(major(city(loc_2(stateid('illinois'))))) +answer(state(next_to_2(stateid('michigan')))) +answer(density_1(state(all))) +answer(population_1(stateid('mississippi'))) +answer(population_1(major(city(loc_2(stateid('montana')))))) +answer(population_1(state(traverse_1(river(riverid('mississippi')))))) +answer(population_1(state(traverse_1(river(riverid('mississippi')))))) +answer(population_1(state(traverse_1(riverid('mississippi'))))) +answer(population_1(state(traverse_1(riverid('mississippi'))))) +answer(population_1(state(next_to_2(stateid('texas'))))) +answer(population_1(major(city(loc_2(stateid('texas')))))) +answer(population_1(state(traverse_1(river(riverid('mississippi')))))) +answer(population_1(state(traverse_1(river(riverid('mississippi')))))) +answer(population_1(state(traverse_1(riverid('mississippi'))))) +answer(population_1(state(traverse_1(riverid('mississippi'))))) +answer(river(loc_2(stateid('alaska')))) +answer(river(loc_2(state(stateid('indiana'))))) +answer(river(loc_2(state(stateid('texas'))))) +answer(river(loc_2(stateid('montana')))) +answer(state(all)) +answer(state(next_to_2(largest_one(population_1(state(all)))))) +answer(state(traverse_1(riverid('potomac')))) +answer(state(traverse_1(longest(river(all))))) +answer(population_1(stateid('missouri'))) +answer(largest_one(population_1(capital(all)))) +answer(largest(capital(loc_2(countryid('usa'))))) +answer(city(loc_2(stateid('pennsylvania')))) +answer(city(loc_2(stateid('california')))) +answer(largest_one(population_1(city(loc_2(stateid('texas')))))) +answer(largest_one(population_1(city(loc_2(stateid('texas')))))) +answer(largest_one(population_1(city(all)))) +answer(smallest_one(population_1(city(all)))) +answer(largest_one(population_1(city(all)))) +answer(largest_one(density_1(city(loc_2(countryid('usa')))))) +answer(capital(loc_2(stateid('iowa')))) +answer(capital(loc_2(state(loc_1(lowest(place(all))))))) +answer(largest(capital(all))) +answer(state(next_to_2(stateid('california')))) +answer(area_1(stateid('alaska'))) +answer(sum(area_1(state(all)))) +answer(area_1(stateid('california'))) +answer(area_1(stateid('florida'))) +answer(area_1(stateid('idaho'))) +answer(area_1(stateid('maine'))) +answer(area_1(stateid('maryland'))) +answer(area_1(stateid('new mexico'))) +answer(area_1(stateid('ohio'))) +answer(area_1(cityid('seattle', _))) +answer(area_1(stateid('south carolina'))) +answer(area_1(stateid('texas'))) +answer(area_1(largest(state(all)))) +answer(area_1(smallest(state(all)))) +answer(area_1(state(loc_1(capital(cityid('albany', _)))))) +answer(area_1(smallest_one(density_1(state(all))))) +answer(area_1(state(all))) +answer(area_1(state(stateid('texas')))) +answer(area_1(stateid('wisconsin'))) +answer(density_1(countryid('usa'))) +answer(density_1(stateid('pennsylvania'))) +answer(density_1(countryid('usa'))) +answer(largest(city(loc_2(state(loc_1(river(all))))))) +answer(largest(capital(city(loc_2(countryid('usa')))))) +answer(largest(city(loc_2(stateid('arizona'))))) +answer(largest(city(loc_2(stateid('georgia'))))) +answer(largest(city(loc_2(stateid('kansas'))))) +answer(largest(city(loc_2(stateid('louisiana'))))) +answer(largest(city(loc_2(stateid('nebraska'))))) +answer(largest(city(loc_2(stateid('oregon'))))) +answer(largest(city(loc_2(stateid('texas'))))) +answer(largest(city(loc_2(smallest(state(all)))))) +answer(largest(city(loc_2(countryid('usa'))))) +answer(largest(city(loc_2(countryid('usa'))))) +answer(largest(city(loc_2(countryid('usa'))))) +answer(largest(city(loc_2(stateid('wyoming'))))) +answer(longest(river(loc_2(stateid('illinois'))))) +answer(largest(state(all))) +answer(largest(state(loc_2(countryid('usa'))))) +answer(largest(state(loc_2(countryid('usa'))))) +answer(capital(city(loc_2(largest(state(loc_2(countryid('usa')))))))) +answer(capital(loc_2(stateid('california')))) +answer(capital(loc_2(stateid('colorado')))) +answer(capital(loc_2(stateid('georgia')))) +answer(capital(loc_2(stateid('hawaii')))) +answer(capital(loc_2(stateid('illinois')))) +answer(capital(loc_2(stateid('indiana')))) +answer(capital(loc_2(stateid('iowa')))) +answer(capital(loc_2(stateid('maine')))) +answer(capital(loc_2(stateid('maryland')))) +answer(capital(loc_2(stateid('massachusetts')))) +answer(capital(loc_2(stateid('michigan')))) +answer(capital(loc_2(stateid('new hampshire')))) +answer(capital(loc_2(stateid('new jersey')))) +answer(capital(loc_2(stateid('new york')))) +answer(capital(loc_2(stateid('north dakota')))) +answer(capital(loc_2(stateid('ohio')))) +answer(capital(loc_2(stateid('pennsylvania')))) +answer(capital(loc_2(state(loc_1(city(cityid('durham', _))))))) +answer(capital(loc_2(stateid('texas')))) +answer(capital(loc_2(state(stateid('alabama'))))) +answer(capital(loc_2(state(stateid('florida'))))) +answer(capital(loc_2(largest(state(all))))) +answer(capital(loc_2(smallest(state(all))))) +answer(capital(loc_2(state(stateid('texas'))))) +answer(capital(loc_2(most(state(next_to_2(state(all))))))) +answer(capital(loc_2(state(next_to_2(state(next_to_2(stateid('texas')))))))) +answer(capital(loc_2(state(loc_1(highest(place(all))))))) +answer(capital(loc_2(state(loc_1(highest(place(all))))))) +answer(capital(loc_2(largest_one(population_1(state(all)))))) +answer(capital(loc_2(largest_one(density_1(state(all)))))) +answer(capital(loc_2(state(loc_1(longest(river(all))))))) +answer(capital(loc_2(largest_one(population_1(state(all)))))) +answer(capital(loc_2(stateid('utah')))) +answer(capital(loc_2(stateid('vermont')))) +answer(capital(loc_2(stateid('washington')))) +answer(largest_one(population_1(city(loc_2(stateid('texas')))))) +answer(smallest_one(population_1(city(all)))) +answer(sum(area_1(state(all)))) +answer(sum(population_1(state(all)))) +answer(density_1(stateid('texas'))) +answer(density_1(stateid('new york'))) +answer(elevation_1(placeid('death valley'))) +answer(elevation_1(highest(place(loc_2(countryid('usa')))))) +answer(elevation_1(placeid('mount mckinley'))) +answer(elevation_1(highest(mountain(loc_2(stateid('texas')))))) +answer(elevation_1(highest(place(loc_2(countryid('usa')))))) +answer(high_point_1(stateid('wyoming'))) +answer(highest(place(loc_2(stateid('new mexico'))))) +answer(highest(place(loc_2(stateid('south carolina'))))) +answer(highest(place(loc_2(stateid('texas'))))) +answer(highest(place(loc_2(countryid('usa'))))) +answer(highest(mountain(loc_2(stateid('alaska'))))) +answer(highest(mountain(loc_2(stateid('texas'))))) +answer(highest(mountain(loc_2(countryid('usa'))))) +answer(highest(mountain(loc_2(countryid('usa'))))) +answer(highest(place(loc_2(stateid('colorado'))))) +answer(highest(place(loc_2(stateid('delaware'))))) +answer(highest(place(loc_2(state(loc_1(place(elevation_2(0)))))))) +answer(highest(place(loc_2(stateid('florida'))))) +answer(highest(place(loc_2(stateid('iowa'))))) +answer(highest(place(loc_2(stateid('kansas'))))) +answer(highest(place(loc_2(stateid('maine'))))) +answer(highest(place(loc_2(stateid('montana'))))) +answer(highest(place(loc_2(stateid('nevada'))))) +answer(highest(place(loc_2(stateid('new mexico'))))) +answer(highest(place(loc_2(stateid('ohio'))))) +answer(highest(place(loc_2(stateid('rhode island'))))) +answer(highest(place(loc_2(state(next_to_2(stateid('georgia'))))))) +answer(highest(place(loc_2(stateid('texas'))))) +answer(highest(place(loc_2(countryid('usa'))))) +answer(highest(place(loc_2(smallest(state(all)))))) +answer(highest(place(loc_2(state(loc_1(capital(cityid('austin', _)))))))) +answer(highest(place(loc_2(state(loc_1(capital(cityid('des moines', _)))))))) +answer(highest(place(loc_2(state(loc_1(capital(cityid('des moines', _)))))))) +answer(highest(place(loc_2(most(state(traverse_1(river(all)))))))) +answer(highest(place(loc_2(smallest_one(population_1(state(all))))))) +answer(highest(place(loc_2(state(next_to_2(stateid('colorado'))))))) +answer(highest(place(loc_2(countryid('usa'))))) +answer(highest(place(loc_2(countryid('usa'))))) +answer(highest(place(loc_2(countryid('usa'))))) +answer(highest(place(loc_2(stateid('virginia'))))) +answer(highest(place(loc_2(stateid('wyoming'))))) +answer(highest(place(loc_2(largest_one(area_1(state(all))))))) +answer(highest(place(loc_2(smallest_one(density_1(state(all))))))) +answer(highest(place(loc_2(countryid('usa'))))) +answer(largest(capital(all))) +answer(largest(capital(city(loc_2(countryid('usa')))))) +answer(largest(city(loc_2(state(next_to_2(stateid('texas'))))))) +answer(largest(city(loc_2(stateid('alabama'))))) +answer(largest(city(loc_2(stateid('california'))))) +answer(largest(city(loc_2(stateid('michigan'))))) +answer(largest_one(population_1(city(loc_2(stateid('minnesota')))))) +answer(largest(city(loc_2(stateid('missouri'))))) +answer(largest(city(loc_2(stateid('rhode island'))))) +answer(largest(city(loc_2(smallest(state(traverse_1(riverid('mississippi')))))))) +answer(largest(city(loc_2(state(next_to_2(stateid('california'))))))) +answer(largest(city(loc_2(stateid('texas'))))) +answer(largest(city(loc_2(smallest(state(loc_2(countryid('usa')))))))) +answer(largest(city(loc_2(stateid('wisconsin'))))) +answer(largest(city(loc_2(stateid('kansas'))))) +answer(largest(state(traverse_1(riverid('rio grande'))))) +answer(longest(river(loc_2(state(stateid('washington')))))) +answer(largest(state(all))) +answer(largest(state(next_to_2(stateid('arkansas'))))) +answer(largest(state(next_to_2(stateid('texas'))))) +answer(largest_one(population_1(capital_1(state(all))))) +answer(largest(state(loc_2(countryid('usa'))))) +answer(largest(state(loc_2(countryid('usa'))))) +answer(largest(state(next_to_2(stateid('california'))))) +answer(largest(state(next_to_2(stateid('texas'))))) +answer(largest(state(next_to_2(largest_one(population_1(state(all))))))) +answer(largest(state(next_to_2(state(loc_1(lowest(place(loc_2(countryid('usa')))))))))) +answer(largest(state(traverse_1(river(riverid('mississippi')))))) +answer(smallest_one(population_1(state(all)))) +answer(len(river(riverid('colorado')))) +answer(len(intersection(riverid('colorado'), river(loc_2(stateid('texas')))))) +answer(len(longest(river(loc_2(countryid('usa')))))) +answer(len(longest(river(traverse_2(stateid('texas')))))) +answer(len(river(riverid('mississippi')))) +answer(len(most(river(traverse_2(state(all)))))) +answer(len(most(river(traverse_2(state(all)))))) +answer(len(most(river(traverse_2(state(all)))))) +answer(len(most(river(traverse_2(state(all)))))) +answer(longest(river(all))) +answer(longest(river(traverse_2(stateid('new york'))))) +answer(longest(river(loc_2(countryid('usa'))))) +answer(longest(river(loc_2(stateid('california'))))) +answer(longest(river(loc_2(stateid('florida'))))) +answer(longest(river(loc_2(stateid('mississippi'))))) +answer(longest(river(loc_2(stateid('new york'))))) +answer(longest(river(loc_2(stateid('pennsylvania'))))) +answer(longest(river(loc_2(stateid('texas'))))) +answer(longest(river(loc_2(largest(state(all)))))) +answer(longest(river(loc_2(smallest(state(loc_2(countryid('usa')))))))) +answer(longest(river(loc_2(state(loc_1(highest(place(all)))))))) +answer(longest(river(loc_2(most(state(loc_1(major(city(all))))))))) +answer(longest(river(loc_2(state(next_to_2(stateid('nebraska'))))))) +answer(longest(river(loc_2(countryid('usa'))))) +answer(longest(river(loc_2(countryid('usa'))))) +answer(longest(exclude(river(all), traverse_2(stateid('texas'))))) +answer(longest(river(traverse_2(state(next_to_2(stateid('indiana'))))))) +answer(longest(river(traverse_2(stateid('colorado'))))) +answer(longest(river(traverse_2(state(next_to_2(most(state(next_to_2(state(all)))))))))) +answer(longest(river(traverse_2(state(next_to_2(stateid('tennessee'))))))) +answer(lowest(place(loc_2(stateid('pennsylvania'))))) +answer(lowest(place(loc_2(stateid('arkansas'))))) +answer(lowest(place(loc_2(stateid('california'))))) +answer(lowest(place(loc_2(stateid('louisiana'))))) +answer(lowest(place(loc_2(stateid('massachusetts'))))) +answer(lowest(place(loc_2(stateid('mississippi'))))) +answer(lowest(place(loc_2(stateid('nebraska'))))) +answer(lowest(place(loc_2(stateid('oregon'))))) +answer(lowest(place(loc_2(stateid('texas'))))) +answer(lowest(place(loc_2(state(stateid('california')))))) +answer(lowest(place(loc_2(state(stateid('texas')))))) +answer(lowest(place(loc_2(countryid('usa'))))) +answer(lowest(place(loc_2(countryid('usa'))))) +answer(lowest(place(loc_2(stateid('wisconsin'))))) +answer(lowest(place(loc_2(state(traverse_1(river(riverid('colorado')))))))) +answer(lowest(place(loc_2(stateid('colorado'))))) +answer(lowest(place(loc_2(largest_one(area_1(state(all))))))) +answer(lowest(place(loc_2(countryid('usa'))))) +answer(major(city(loc_2(stateid('montana'))))) +answer(highest(place(loc_2(cityid('san francisco', _))))) +answer(largest_one(density_1(state(loc_2(countryid('usa')))))) +answer(largest_one(population_1(capital(loc_2(countryid('usa')))))) +answer(largest_one(population_1(state(next_to_2(stateid('oklahoma')))))) +answer(largest_one(population_1(city(all)))) +answer(largest_one(population_1(city(loc_2(stateid('texas')))))) +answer(largest_one(population_1(city(loc_2(stateid('wyoming')))))) +answer(largest_one(population_1(state(all)))) +answer(largest_one(population_1(state(loc_2(countryid('usa')))))) +answer(largest_one(population_1(state(traverse_1(riverid('mississippi')))))) +answer(state(loc_1(lowest(place(all))))) +answer(count(state(next_to_2(stateid('kentucky'))))) +answer(density_1(state(loc_1(capital(cityid('austin', _)))))) +answer(density_1(stateid('maine'))) +answer(density_1(stateid('south dakota'))) +answer(density_1(stateid('texas'))) +answer(density_1(largest(state(all)))) +answer(density_1(smallest(state(all)))) +answer(density_1(smallest_one(area_1(state(all))))) +answer(density_1(smallest_one(population_1(state(all))))) +answer(density_1(stateid('wyoming'))) +answer(population_1(cityid('boston', _))) +answer(population_1(stateid('alaska'))) +answer(population_1(stateid('arizona'))) +answer(population_1(cityid('atlanta', _))) +answer(population_1(cityid('atlanta', 'ga'))) +answer(population_1(cityid('austin', _))) +answer(population_1(cityid('austin', 'tx'))) +answer(population_1(cityid('boston', 'ma'))) +answer(population_1(cityid('boulder', _))) +answer(population_1(stateid('california'))) +answer(population_1(cityid('dallas', _))) +answer(population_1(cityid('denver', _))) +answer(population_1(cityid('erie', 'pa'))) +answer(population_1(stateid('hawaii'))) +answer(population_1(cityid('houston', _))) +answer(population_1(stateid('idaho'))) +answer(population_1(stateid('illinois'))) +answer(population_1(stateid('maine'))) +answer(population_1(stateid('maryland'))) +answer(population_1(stateid('minnesota'))) +answer(population_1(stateid('montana'))) +answer(population_1(stateid('new mexico'))) +answer(population_1(stateid('new york'))) +answer(population_1(city(cityid('new york', _)))) +answer(population_1(stateid('oregon'))) +answer(population_1(cityid('portland', 'me'))) +answer(population_1(stateid('rhode island'))) +answer(population_1(cityid('sacramento', _))) +answer(population_1(cityid('san antonio', _))) +answer(population_1(cityid('seattle', _))) +answer(population_1(cityid('seattle', 'wa'))) +answer(population_1(stateid('south dakota'))) +answer(population_1(cityid('springfield', 'mo'))) +answer(population_1(cityid('springfield', 'sd'))) +answer(population_1(cityid('tempe', 'az'))) +answer(population_1(stateid('texas'))) +answer(population_1(capital(loc_2(largest(state(all)))))) +answer(population_1(capital(loc_2(largest(state(traverse_1(riverid('mississippi')))))))) +answer(population_1(capital(loc_2(smallest(state(all)))))) +answer(population_1(largest(city(loc_2(largest_one(area_1(state(all)))))))) +answer(population_1(largest(state(all)))) +answer(population_1(largest(state(next_to_2(stateid('texas')))))) +answer(population_1(major(city(loc_2(stateid('wisconsin')))))) +answer(smallest(population_1(state(all)))) +answer(population_1(most(state(next_to_2(state(all)))))) +answer(population_1(largest_one(density_1(state(all))))) +answer(population_1(largest_one(area_1(state(all))))) +answer(population_1(cityid('tucson', _))) +answer(population_1(stateid('utah'))) +answer(population_1(stateid('washington'))) +answer(population_1(cityid('washington', 'dc'))) +answer(river(traverse_2(stateid('ohio')))) +answer(shortest(river(all))) +answer(shortest(river(loc_2(stateid('alaska'))))) +answer(shortest(river(loc_2(stateid('iowa'))))) +answer(shortest(river(loc_2(stateid('nebraska'))))) +answer(shortest(river(loc_2(stateid('texas'))))) +answer(shortest(river(loc_2(countryid('usa'))))) +answer(shortest(river(loc_2(countryid('usa'))))) +answer(shortest(river(loc_2(countryid('usa'))))) +answer(size(stateid('california'))) +answer(size(stateid('florida'))) +answer(size(stateid('texas'))) +answer(size(capital(loc_2(stateid('texas'))))) +answer(size(largest(state(loc_2(countryid('usa')))))) +answer(smallest(city(loc_2(stateid('alaska'))))) +answer(smallest(city(loc_2(stateid('arkansas'))))) +answer(smallest(city(loc_2(stateid('hawaii'))))) +answer(smallest(city(loc_2(largest(state(all)))))) +answer(smallest(city(loc_2(countryid('usa'))))) +answer(smallest(city(loc_2(countryid('usa'))))) +answer(smallest(city(loc_2(stateid('washington'))))) +answer(smallest(city(loc_2(smallest(state(loc_2(countryid('usa')))))))) +answer(smallest(state(next_to_2(stateid('ohio'))))) +answer(smallest(state(next_to_2(stateid('wyoming'))))) +answer(smallest_one(area_1(state(all)))) +answer(smallest(state(loc_2(countryid('usa'))))) +answer(smallest(state(next_to_2(stateid('texas'))))) +answer(smallest(most(state(next_to_2(state(all)))))) +answer(smallest(state(traverse_1(river(riverid('mississippi')))))) +answer(smallest(state(traverse_1(longest(river(all)))))) +answer(state(loc_1(highest(place(all))))) +answer(state(loc_1(highest(place(loc_2(countryid('usa'))))))) +answer(largest_one(area_1(state(all)))) +answer(largest_one(density_1(state(loc_2(countryid('usa')))))) +answer(largest_one(density_1(state(all)))) +answer(state(loc_1(lowest(place(all))))) +answer(smallest_one(population_1(state(all)))) +answer(smallest_one(density_1(state(all)))) +answer(smallest_one(area_1(state(all)))) +answer(highest(mountain(loc_2(countryid('usa'))))) +answer(highest(mountain(loc_2(countryid('usa'))))) +answer(area_1(countryid('usa'))) +answer(sum(len(river(all)))) +answer(sum(population_1(state(next_to_2(stateid('texas')))))) +answer(len(riverid('mississippi'))) +answer(major(city(loc_2(stateid('pennsylvania'))))) +answer(major(river(traverse_2(stateid('illinois'))))) +answer(mountain(loc_2(stateid('alaska')))) +answer(river(traverse_2(stateid('kansas')))) +answer(river(traverse_2(stateid('texas')))) +answer(most(river(traverse_2(state(all))))) +answer(longest(river(loc_2(countryid('usa'))))) +answer(river(traverse_2(stateid('illinois')))) +answer(most(river(traverse_2(state(all))))) +answer(river(traverse_2(most(state(loc_1(city(all))))))) +answer(river(traverse_2(stateid('virginia')))) +answer(most(river(traverse_2(state(all))))) +answer(river(traverse_2(most(state(next_to_2(state(all))))))) +answer(river(loc_2(stateid('nevada')))) +answer(river(loc_2(stateid('new mexico')))) +answer(river(loc_2(stateid('oregon')))) +answer(river(loc_2(state(next_to_2(stateid('texas')))))) +answer(river(loc_2(stateid('texas')))) +answer(river(loc_2(stateid('utah')))) +answer(river(loc_2(stateid('texas')))) +answer(exclude(river(all), traverse_2(stateid('tennessee')))) +answer(river(traverse_2(stateid('colorado')))) +answer(river(traverse_2(stateid('missouri')))) +answer(river(traverse_2(state(next_to_1(stateid('alabama')))))) +answer(river(traverse_2(state(next_to_2(largest_one(population_1(state(all)))))))) +answer(river(traverse_2(largest(state(all))))) +answer(river(traverse_2(largest_one(population_1(state(all)))))) +answer(river(traverse_2(stateid('arizona')))) +answer(river(traverse_2(cityid('austin', 'tx')))) +answer(river(traverse_2(stateid('colorado')))) +answer(river(traverse_2(stateid('louisiana')))) +answer(river(traverse_2(stateid('maine')))) +answer(river(traverse_2(stateid('new york')))) +answer(river(traverse_2(state(loc_1(lowest(place(loc_2(countryid('usa'))))))))) +answer(river(traverse_2(state(next_to_2(state(loc_1(capital(cityid('atlanta', _))))))))) +answer(river(traverse_2(stateid('west virginia')))) +answer(river(traverse_2(most(state(next_to_2(state(all))))))) +answer(largest_one(population_1(state(next_to_2(stateid('nevada')))))) +answer(state(next_to_2(stateid('michigan')))) +answer(most(state(next_to_2(state(all))))) +answer(state(next_to_2(stateid('new york')))) +answer(fewest(state(next_to_2(state(all))))) +answer(fewest(state(next_to_2(exclude(exclude(state(all), stateid('alaska')), stateid('hawaii')))))) +answer(most(state(next_to_2(state(all))))) +answer(state(next_to_2(smallest_one(population_1(state(all)))))) +answer(state(loc_1(highest(place(loc_2(countryid('usa'))))))) +answer(state(loc_1(highest(place(loc_2(state(traverse_1(river(riverid('colorado')))))))))) +answer(state(loc_1(highest(place(all))))) +answer(exclude(state(all), loc_1(river(all)))) +answer(state(loc_1(capital(cityid('salem', _))))) +answer(state(loc_1(city(cityid('flint', _))))) +answer(state(loc_1(largest_one(population_1(city(all)))))) +answer(state(loc_1(largest_one(population_1(city(all)))))) +answer(largest_one(density_1(state(all)))) +answer(state(loc_1(highest(place(all))))) +answer(largest_one(population_1(state(all)))) +answer(largest_one(density_1(state(all)))) +answer(largest_one(area_1(state(all)))) +answer(state(loc_1(largest(capital(all))))) +answer(state(loc_1(largest(city(all))))) +answer(largest_one(population_1(state(all)))) +answer(largest_one(density_1(state(all)))) +answer(largest_one(population_1(state(all)))) +answer(smallest_one(density_1(state(all)))) +answer(state(loc_1(longest(river(all))))) +answer(smallest_one(density_1(state(all)))) +answer(most(state(loc_1(city(all))))) +answer(most(state(loc_1(major(city(all)))))) +answer(most(state(traverse_1(major(river(all)))))) +answer(largest_one(population_1(state(all)))) +answer(most(state(loc_1(river(all))))) +answer(most(state(traverse_1(river(all))))) +answer(state(loc_1(shortest(river(all))))) +answer(smallest_one(area_1(state(all)))) +answer(state(loc_1(smallest(capital(all))))) +answer(smallest_one(population_1(state(all)))) +answer(smallest_one(density_1(state(all)))) +answer(smallest_one(population_1(state(all)))) +answer(smallest_one(density_1(state(all)))) +answer(state(loc_1(cityid('austin', _)))) +answer(state(loc_1(capital(cityid('austin', _))))) +answer(state(loc_1(cityid('boston', _)))) +answer(state(loc_1(capital(cityid('columbus', _))))) +answer(state(loc_1(cityid('dallas', _)))) +answer(state(loc_1(cityid('des moines', _)))) +answer(state(loc_1(cityid('miami', _)))) +answer(state(loc_1(cityid('pittsburgh', _)))) +answer(largest(state(all))) +answer(largest_one(population_1(state(all)))) +answer(state(most(state(loc_1(river(all)))))) +answer(largest_one(population_1(state(next_to_2(stateid('texas')))))) +answer(largest(state(next_to_2(stateid('texas'))))) +answer(largest_one(population_1(state(traverse_1(riverid('mississippi')))))) +answer(state(next_to_2(stateid('arizona')))) +answer(state(next_to_2(stateid('texas')))) +answer(state(next_to_2(stateid('mississippi')))) +answer(state(next_to_2(stateid('alaska')))) +answer(state(next_to_2(stateid('arkansas')))) +answer(state(next_to_2(stateid('delaware')))) +answer(state(next_to_2(stateid('florida')))) +answer(state(next_to_2(stateid('georgia')))) +answer(state(next_to_2(stateid('hawaii')))) +answer(state(next_to_2(stateid('indiana')))) +answer(state(next_to_2(stateid('kentucky')))) +answer(state(next_to_2(stateid('michigan')))) +answer(state(next_to_2(stateid('missouri')))) +answer(state(next_to_2(stateid('montana')))) +answer(state(next_to_2(stateid('new hampshire')))) +answer(state(next_to_2(stateid('new jersey')))) +answer(state(next_to_2(stateid('ohio')))) +answer(state(next_to_2(stateid('rhode island')))) +answer(state(next_to_2(state(next_to_2(stateid('colorado')))))) +answer(state(next_to_2(state(next_to_2(stateid('mississippi')))))) +answer(state(next_to_2(state(next_to_2(state(next_to_2(stateid('florida')))))))) +answer(state(next_to_2(state(next_to_2(state(next_to_2(state(next_to_2(stateid('texas')))))))))) +answer(state(next_to_2(state(next_to_2(largest_one(population_1(state(all)))))))) +answer(state(next_to_2(state(traverse_1(riverid('mississippi')))))) +answer(state(next_to_2(state(traverse_1(riverid('ohio')))))) +answer(state(next_to_2(state(traverse_1(riverid('mississippi')))))) +answer(state(next_to_2(stateid('texas')))) +answer(intersection(state(next_to_2(stateid('texas'))), loc_1(major(river(all))))) +answer(state(next_to_2(river(riverid('mississippi'))))) +answer(state(next_to_2(largest_one(population_1(state(all)))))) +answer(state(next_to_2(most(state(next_to_2(state(all))))))) +answer(state(next_to_2(most(state(loc_1(city(all))))))) +answer(state(next_to_2(most(state(loc_1(major(city(all)))))))) +answer(state(next_to_2(smallest_one(area_1(state(all)))))) +answer(state(next_to_2(most(state(loc_1(city(all))))))) +answer(state(next_to_2(stateid('wisconsin')))) +answer(state(capital_2(cityid('dover', _)))) +answer(state(loc_1(major(river(all))))) +answer(state(traverse_1(river(riverid('colorado'))))) +answer(state(traverse_1(river(riverid('delaware'))))) +answer(state(traverse_1(river(riverid('mississippi'))))) +answer(state(traverse_1(riverid('mississippi')))) +answer(state(traverse_1(river(riverid('missouri'))))) +answer(state(traverse_1(riverid('missouri')))) +answer(state(traverse_1(river(riverid('ohio'))))) +answer(state(traverse_1(river(riverid('ohio'))))) +answer(state(traverse_1(shortest(river(all))))) +answer(state(loc_1(capital(highest(place(all)))))) +answer(state(loc_1(city(cityid('austin', _))))) +answer(state(loc_1(city(cityid('austin', _))))) +answer(state(loc_1(city(cityid('dallas', _))))) +answer(state(loc_1(city(cityid('plano', _))))) +answer(state(loc_1(city(cityid('portland', _))))) +answer(state(loc_1(city(cityid('rochester', _))))) +answer(state(loc_1(city(cityid('salt lake city', _))))) +answer(exclude(state(all), next_to_2(state(all)))) +answer(state(loc_1(river(riverid('colorado'))))) +answer(state(traverse_1(river(all)))) +answer(state(loc_1(city(cityid('springfield', _))))) +answer(state(high_point_2(higher_2(high_point_1(stateid('colorado')))))) +answer(intersection(state(loc_2(countryid('usa'))), loc_1(city(cityid('springfield', _))))) +answer(state(next_to_2(stateid('maine')))) +answer(state(next_to_2(stateid('kentucky')))) +answer(largest_one(population_1(city(loc_2(stateid('texas')))))) +answer(largest(city(all))) +answer(loc_1(mountain(all))) +answer(loc_1(cityid('austin', _))) +answer(loc_1(cityid('baton rouge', _))) +answer(loc_1(cityid('dallas', _))) +answer(loc_1(cityid('fort wayne', _))) +answer(loc_1(cityid('houston', _))) +answer(loc_1(cityid('indianapolis', _))) +answer(loc_1(stateid('massachusetts'))) +answer(loc_1(placeid('mount whitney'))) +answer(loc_1(placeid('mount whitney'))) +answer(loc_1(stateid('new hampshire'))) +answer(loc_1(cityid('new orleans', _))) +answer(loc_1(cityid('portland', _))) +answer(loc_1(cityid('san diego', _))) +answer(loc_1(cityid('san jose', _))) +answer(loc_1(cityid('scotts valley', _))) +answer(loc_1(cityid('springfield', _))) +answer(loc_1(river(riverid('chattahoochee')))) +answer(highest(mountain(loc_2(countryid('usa'))))) +answer(highest(place(loc_2(stateid('hawaii'))))) +answer(highest(place(loc_2(stateid('montana'))))) +answer(lowest(place(loc_2(stateid('maryland'))))) +answer(lowest(place(loc_2(countryid('usa'))))) +answer(lowest(place(loc_2(stateid('iowa'))))) +answer(largest_one(population_1(city(loc_2(stateid('new mexico')))))) +answer(loc_1(smallest(city(all)))) +answer(capital(loc_2(state(next_to_2(stateid('texas')))))) +answer(exclude(capital(all), major(city(all)))) +answer(largest_one(population_1(city(loc_2(stateid('california')))))) +answer(density_1(state(traverse_1(longest(river(loc_2(countryid('usa')))))))) +answer(highest(exclude(mountain(all), loc_2(stateid('alaska'))))) +answer(longest(river(loc_2(countryid('usa'))))) +answer(lowest(place(loc_2(state(traverse_1(riverid('mississippi'))))))) +answer(shortest(river(all))) +answer(smallest(state(all))) +answer(largest_one(population_1(state(next_to_2(stateid('pennsylvania')))))) +answer(most(river(traverse_2(state(all))))) +answer(most(river(traverse_2(state(all))))) +answer(most(river(traverse_2(state(all))))) +answer(most(river(traverse_2(state(all))))) +answer(river(loc_2(stateid('alaska')))) +answer(exclude(river(all), traverse_2(stateid('texas')))) +answer(exclude(river(all), traverse_2(countryid('usa')))) +answer(river(traverse_2(stateid('alaska')))) +answer(river(traverse_2(state(next_to_2(stateid('new mexico')))))) +answer(river(traverse_2(state(next_to_2(state(loc_1(capital(cityid('austin', _))))))))) +answer(river(traverse_2(fewest(state(loc_1(city(all))))))) +answer(river(traverse_2(state(loc_1(largest(city(loc_2(countryid('usa'))))))))) +answer(river(traverse_2(state(loc_1(lowest(place(loc_2(countryid('usa'))))))))) +answer(state(next_to_2(stateid('kentucky')))) +answer(state(next_to_2(stateid('florida')))) +answer(state(next_to_2(stateid('hawaii')))) +answer(most(state(next_to_2(state(all))))) +answer(most(state(next_to_2(state(all))))) +answer(smallest_one(population_1(capital(all)))) +answer(most(state(loc_1(river(all))))) +answer(largest_one(population_1(state(all)))) +answer(largest_one(density_1(state(all)))) +answer(largest_one(population_1(state(all)))) +answer(state(loc_1(highest(place(all))))) +answer(state(loc_1(highest(place(all))))) +answer(state(loc_1(highest(place(all))))) +answer(largest_one(density_1(state(all)))) +answer(state(loc_1(largest(city(all))))) +answer(largest_one(density_1(state(all)))) +answer(smallest_one(density_1(state(all)))) +answer(state(loc_1(longest(river(all))))) +answer(state(loc_1(lowest(place(all))))) +answer(state(loc_1(lowest(place(loc_2(next_to_2(stateid('idaho')))))))) +answer(smallest_one(density_1(state(all)))) +answer(most(state(loc_1(major(city(all)))))) +answer(most(state(loc_1(major(river(all)))))) +answer(most(state(traverse_1(major(river(all)))))) +answer(largest_one(population_1(state(all)))) +answer(largest_one(population_1(state(all)))) +answer(most(state(loc_1(river(all))))) +answer(most(state(traverse_1(river(all))))) +answer(state(loc_1(river(riverid('red'))))) +answer(smallest_one(area_1(state(next_to_2(stateid('texas')))))) +answer(smallest_one(density_1(state(all)))) +answer(smallest_one(density_1(state(all)))) +answer(smallest_one(density_1(state(all)))) +answer(state(loc_1(cityid('kalamazoo', _)))) +answer(state(loc_1(placeid('mount mckinley')))) +answer(state(loc_1(city(cityid('denver', _))))) +answer(state(loc_1(largest(city(loc_2(stateid('montana'))))))) +answer(smallest(state(all))) +answer(state(next_to_2(stateid('alabama')))) +answer(state(next_to_2(stateid('alabama')))) +answer(state(next_to_2(stateid('alaska')))) +answer(state(next_to_2(stateid('arizona')))) +answer(state(next_to_2(stateid('colorado')))) +answer(state(next_to_2(stateid('hawaii')))) +answer(state(next_to_2(stateid('illinois')))) +answer(state(next_to_2(stateid('iowa')))) +answer(state(next_to_2(stateid('kentucky')))) +answer(state(next_to_2(stateid('michigan')))) +answer(state(next_to_2(stateid('new york')))) +answer(exclude(state(all), next_to_2(state(all)))) +answer(state(next_to_2(stateid('south dakota')))) +answer(state(next_to_2(state(traverse_1(riverid('mississippi')))))) +answer(state(next_to_2(stateid('texas')))) +answer(state(next_to_2(longest(river(loc_2(countryid('usa'))))))) +answer(state(next_to_2(river(riverid('missouri'))))) +answer(state(next_to_2(smallest_one(area_1(state(all)))))) +answer(state(loc_1(largest(city(capital_1(state(all))))))) +answer(state(traverse_1(river(riverid('colorado'))))) +answer(exclude(state(all), next_to_2(stateid('texas')))) +answer(state(traverse_1(river(riverid('chattahoochee'))))) +answer(state(traverse_1(river(riverid('colorado'))))) +answer(state(traverse_1(longest(river(all))))) +answer(state(traverse_1(longest(river(all))))) +answer(state(traverse_1(river(riverid('mississippi'))))) +answer(state(traverse_1(riverid('mississippi')))) +answer(state(traverse_1(river(riverid('missouri'))))) +answer(state(traverse_1(river(riverid('missouri'))))) +answer(state(loc_1(major(city(cityid('austin', _)))))) +answer(state(loc_1(river(all)))) +answer(state(loc_1(city(cityid('austin', _))))) +answer(state(loc_1(place(higher_2(highest(place(loc_2(stateid('colorado'))))))))) +answer(state(loc_1(place(higher_2(highest(place(loc_2(stateid('texas'))))))))) +answer(state(traverse_1(longest(river(loc_2(countryid('usa'))))))) +answer(largest_one(density_1(city(all)))) diff --git a/algorithms/parse_bracketed.rb b/algorithms/parse_bracketed.rb new file mode 100755 index 0000000..cc90212 --- /dev/null +++ b/algorithms/parse_bracketed.rb @@ -0,0 +1,127 @@ +#!/usr/bin/env ruby + + +def _c s + s.strip.lstrip.gsub("'", '').gsub(/\s+/, "_") +end + +class Item + attr_accessor :predicate, :arguments + + def initialize predicate='', arguments=[] + @predicate = predicate + @arguments = [] + end + + def to_s + args = @arguments.each{|i| i.to_s}.to_s.gsub('[','(').gsub(']',')') + "#{@predicate}#{args}" + end +end + +def parse_funql s + s = "(#{s})" + structure = Item.new + prev_p = nil + p = structure + collect = '' + just_closed = false + s.each_char { |c| + if c == '(' + p.arguments << Item.new(_c(collect)) + collect = '' + prev_p = p + p = p.arguments.last + just_closed = false + elsif c == ')' + if collect != '' + p.arguments << _c(collect) + collect = '' + end + p = prev_p + just_closed = true + elsif c == ',' + if collect != '' + p.arguments << _c(collect) + collect = '' + end + if just_closed + p = prev_p + end + just_closed = false + else + collect += c + end + } + return structure +end + +def flatten_funql a + return "#{a} " if a.class == String + s = "#{a.predicate}$#{a.arguments.size} " + a.arguments.each { |i| + s += flatten_funql(i) + } + return s +end + +def _fix_output s + s[5..s.size-1].lstrip.strip.gsub("'", '') +end + +def reverse s + s.strip! + open = 0 + r = '' + s.split.each { |i| + term, n = i.split '$' + n = n.to_i + out = term + if n == 0 + out = "'#{out}'" + elsif n > 0 + out += '(' + open += 1 + else + puts "ERROR" + exit + end + r += out + } + open.times { r += ')' } + return r.gsub("''", "','") +end + +def test + a = [] + a << "answer(exclude(state(all), next_to_2(stateid('texas'))))" + a << "answer(most(state(traverse_1(river(all)))))" + a << "answer(state(loc_1(river(riverid('red')))))" + a << "answer(smallest_one(area_1(state(next_to_2(stateid('texas'))))))" + a << "answer(smallest_one(density_1(state(all))))" + a << "answer(smallest_one(density_1(state(all))))" + a << "answer(smallest_one(density_1(state(all))))" + a << "answer(state(loc_1(cityid('kalamazoo', _))))" + a.each { |i| + puts i + r = parse_funql(i) + puts r.to_s + puts _fix_output(flatten_funql(r)) + puts + } +end + +def main + #test + while line = STDIN.gets + x = _fix_output(flatten_funql(parse_funql(line.strip))) + puts line + puts x + puts reverse(x) + puts + end +end + + +main + diff --git a/algorithms/string_reverse.c b/algorithms/string_reverse.c new file mode 100644 index 0000000..e6b6988 --- /dev/null +++ b/algorithms/string_reverse.c @@ -0,0 +1,42 @@ +#include <stdio.h> +#include <string.h> + + +char * rev(char *s) +{ + int l = strlen(s); + char res[l+1]; + int k = 0; + for (int i = l-1; i >= 0; i--) { // unsigned not! + res[k] = s[i]; + k++; + } + res[l] = 0; + return res; +} + +void rev_inplace(char *s) +{ + char temp; + int j = strlen(s)-1; + for (int i = 0; i <= j; i++) { + temp = s[i]; + s[i] = s[j]; + s[j] = temp; + j--; + } +} + + +int main(void) +{ + char *s = "Asdf"; + printf("%s\n", s); + char *r = rev(s); + printf("%s\n", r); + char t[] = "fdsA"; + rev_inplace(t); + printf("%s\n", t); + return 0; +} + diff --git a/algorithms/string_reverse.cc b/algorithms/string_reverse.cc new file mode 100644 index 0000000..8b3e12c --- /dev/null +++ b/algorithms/string_reverse.cc @@ -0,0 +1,37 @@ +#include <iostream> +#include <string> + +using namespace std; + + +string rev(string &s) +{ + string res; + for (int i = s.size()-1; i >= 0; i--) { // unsigned not! + res += s[i]; + } + return res; +} + +void rev_inplace(string &s) +{ + char temp; + int j = s.size()-1; + for (int i = 0; i < j; i++, j--) { + temp = s[i]; + s[i] = s[j]; + s[j] = temp; + } +} + + +int main() +{ + string s = "Asdf"; + cout << rev(s) << endl << "---" << endl; + cout << s << endl; + rev_inplace(s); + cout << s << endl; + return 0; +} + diff --git a/algorithms/string_reverse.py b/algorithms/string_reverse.py new file mode 100755 index 0000000..1cebda4 --- /dev/null +++ b/algorithms/string_reverse.py @@ -0,0 +1,7 @@ +#!/usr/bin/env python2 + + +s = "Madam" +print s +print ''.join([s[i] for i in range(len(s)-1, -1, -1)]) + diff --git a/algorithms/sudoku.py b/algorithms/sudoku.py new file mode 100755 index 0000000..1fa1824 --- /dev/null +++ b/algorithms/sudoku.py @@ -0,0 +1,90 @@ +#!/usr/bin/env python2 + + +block = [ [1, 2, 3], + [1, 2, 3], + [1, 2, 3] +] + +print "bs" +sums = [] +for i in [0,1,2]: + sumh = 0 + sumv = 0 + for j in [0,1,2]: + sumh += block[i][j] + sumv += block[j][i] + print "horiz %d, vert %d"%(sumh, sumv) + sums += [sumv, sumh] + +if sum(sums) != 6*9: print "ohoh" + +# --- + +# 0 1 2 +s = [ [1, 2, 3, 4, 5 ,6, 7, 8, 9], #00 01 02 03 04 05 06 07 08 + [1, 2, 3, 4, 5, 6, 7, 8, 9], #10 11 12 13 14 15 16 17 18 + [1, 2, 3, 4, 5, 6, 7, 8, 9], #20 21 22 23 24 25 26 27 28 + + # 3 4 5 + [1, 2, 3, 4, 5, 6, 7, 8, 9], #30 31 32 33 34 35 36 37 38 + [1, 2, 3, 4, 5, 6, 7, 8, 9], #40 41 42 43 44 45 46 47 48 + [1, 2, 3, 4, 5, 6, 7, 8, 9], #50 51 52 53 54 55 56 57 58 + + [1, 2, 3, 4, 5, 6, 7, 8, 9], + [1, 2, 3, 4, 5, 6, 7, 8, 9], + [1, 2, 3, 4, 5, 6, 7, 8, 9] + ] + +""" +0 1 2 +2 3 4 +4 5 6 + + +0 1 2 3 4 5 6 7 8 +1 2 3 4 5 6 7 8 9 +2 3 4 5 6 7 8 9 10 + +3 4 5 6 7 8 9 10 11 +4 5 6 7 8 9 10 11 12 + + +i = 0 1 2 => 0 1 2 +i = 3 4 5 => 3 4 5 +i = 6 7 8 => 6 7 8 + +j = 0 1 2 => 0 3 6 +j = 3 4 5 => 1 4 7 +j = 6 7 8 => 2 5 8 + + +i=0 + j=0 1 2 3 4 5 6 7 8 9 +i=1 + j=1 2 3 4 5 6 7 8 8 9 +""" + +blocksums = [0 for i in range(0,9)] +third = 0 +block = 0 +for i in range(0,9): + sumh = 0 + sumv = 0 + if i > 0 and i%3 == 0: + third += 1 + block = third*3 + for j in range(0,9): + if j > 0 and j%3 == 0: + block += 1 + print "%d %d, %d"%(i,j,block) + sumh += s[i][j] + sumv += s[j][i] + blocksums[block] = s[i][j] + sums += [sumh, sumv] + print "---" + +sums += blocksums + +if sum(sums) != 45*len(sums): print "ohoh" + |