Array Absurdity

配列の重複を見つける。
正答率58%

((552.0/(552 +398))*100).round

設問

Imagine we have an immutable array of size N which we know to be filled with integers ranging from 0 to N-2, inclusive. Suppose we know that the array contains exactly one duplicated entry and that duplicate appears exactly twice. Find the duplicated entry. (For bonus points, ensure your solution has constant space and time proportional to N)

Input sample:

Your program should accept as its first argument a path to a filename. Each line in this file is one test case. Ignore all empty lines. Each line begins with a positive integer(N) i.e. the size of the array, then a semicolon followed by a comma separated list of positive numbers ranging from 0 to N-2, inclusive. i.e eg.

5;0,1,2,3,0
20;0,1,10,3,2,4,5,7,6,8,11,9,15,12,13,4,16,18,17,14

Output sample:

Print out the duplicated entry, each one on a new line eg

0
4

やってみた

#!/usr/bin/env ruby
#http://d.hatena.ne.jp/takuya_1st/20100103/1262486833
def verify_duplication(ar)
  ar.uniq.find{ |e| ar.index(e) != ar.rindex(e) }
end

ARGF.lines do |line|
  next if line.strip == ''
  puts verify_duplication(line.chomp.split(';')[1].split(','))
end

重複しているものだけ取り出す、Array#uniqの逆が思いつかなくて
ググったら下記URLで面白いやり方をしていたので
参考にして書いてみた。

indexとrindexを比較するという、目から鱗な書き方。

参考

Rubyで配列から重複したモノ（要素）を抜き出す（Uniqの逆） - ブックマクロ開発に

Email Validation

メールのvalidation。
正答率82%

((561.0/(561+125))*100).round

設問

You are given several strings that may/may not be valid emails. You should write a regular expression that determines if the email id is a valid email id or not. You may assume all characters are from the english language.

Input sample:

Your program should accept as its first argument a filename. This file will contain several text strings, one per line. Ignore all empty lines. eg.

foo@bar.com
this is not an email id
admin#codeeval.com
good123@bad.com

Output sample:

Print out 'true' (all lowercase) if the string is a valid email. Else print out 'false' (all lowercase) .e.g.

true
false
false
true

やってみた

#!/usr/bin/env ruby
# http://stackoverflow.com/questions/1156601/whats-the-state-of-the-art-in-email-validation-for-rails

def valid_email?(email)
  !!email.match(/^[A-Za-z0-9._%+-]+@[A-Za-z0-9.-]+\.[A-Za-z]+$/)
end

ARGF.lines do |line|
  puts valid_email?(line.chomp)
end

とりえあずinputはパスする通る形で最初書いていたのだが、

!!email.match(/^\w+@\w+\.\w+$/)

100点とならずに不正解だったので、こちらを参考にした。
参考URLは、改行の考慮がされているのだが
そんなのいらんだろと勝手に変更。
What's the state of the art in email validation for Rails? - Stack Overflow

余談だがgemもそれっぽいの沢山あるなぁ。
携帯キャリアがRFC準拠してなかったりするから
みんな適当な感じなのかな。
（あとで調べるか。）

email-validator (0.2.3, 0.2.2, 0.2.1, 0.2.0)

email_valid (0.0.1)
email_validation (1.1.1, 1.1.0, 1.0.0)
email_validator (1.3.0, 1.2.4, 1.2.3, 1.2.2, 1.2.1, 1.1.0, 1.0.0)
email_veracity (0.6.0, 0.5.0, 0.4.0)
email_veracity_checker (0.0.2, 0.0.1)

Number Pairs

配列と数字が与えられたとき、その配列のうち2つの和がその数字となる
組み合わせを求める。

正答率86%

((296.0/(296+48))*100).round

設問

You are given a sorted array of positive integers and a number 'X'. Print out all pairs of numbers whose sum is equal to X. Print out only unique pairs and the pairs should be in ascending order

Input sample:

Your program should accept as its first argument a filename. This file will contain a comma separated list of sorted numbers and then the sum 'X', separated by semicolon. Ignore all empty lines. If no pair exists, print the string NULL eg.

1,2,3,4,6;5
2,4,5,6,9,11,15;20
1,2,3,4;50

Output sample:

Print out the pairs of numbers that equal to the sum X. The pairs should themselves be printed in sorted order i.e the first number of each pair should be in ascending order .e.g.

1,4;2,3
5,15;9,11
NULL

やってみた

#!/usr/bin/env ruby

def pairs(ar, n)
  pairs = ar.split(',').map(&:to_i).combination(2).select do |com|
    com.inject(:+) == n.to_i
  end
end

def format(pairs)
  pairs.size.zero?? 'NULL' : pairs.map{ |pair| pair.join(',') }.join(';')
end

ARGF.lines do |line|
  line.chomp.split(';').instance_eval do |ar, n|
    puts format(pairs(ar, n))
  end
end

Double Squares

Facebook Hacker Cup 2011の問題らしい。
そんなのあるんだ。

入力値が、２つの数値をそれぞれ２乗した値の和になる組み合わせを求める。
入力値が10の場合は、10 = 3^2 + 1^2 なので1通り。
1行目は、ケースの数です。（これに気づかず嵌ってしまった）

正答率60%

((288.0/(288+189))*100).round

設問

Credits: This challenge appeared in the Facebook Hacker Cup 2011.

A double-square number is an integer X which can be expressed as the sum of two perfect squares. For example, 10 is a double-square because 10 = 3^2 + 1^2. Your task in this problem is, given X, determine the number of ways in which it can be written as the sum of two squares. For example, 10 can only be written as 3^2 + 1^2 (we don't count 1^2 + 3^2 as being different). On the other hand, 25 can be written as 5^2 + 0^2 or as 4^2 + 3^2.
NOTE: Do NOT attempt a brute force approach. It will not work. The following constraints hold:
0 <= X <= 2147483647
1 <= N <= 100

Input sample:

You should first read an integer N, the number of test cases. The next N lines will contain N values of X.

5
10
25
3
0
1

Output sample:

e.g.

1
2
0
1
1

やってみた

#!/usr/bin/env ruby

def sqrt_count(n)
  s = Math.sqrt(n)
  (0..s).inject(0) do |res, i|
    sq = Math.sqrt(n - i**2)
    res+=1 if (sq >= i) and (sq == sq.to_i)
    res
  end
end

def header_skip_reader(file)
  f = open(file)
  f.gets
  f.lines{ |line| yield(line) }
  f.close
end

header_skip_reader(ARGV[0]) do |line|
  puts sqrt_count(line.to_i)
end

header_skip_readerはおまけ。
1行読み飛ばしてファイル操作するのって、open/gets/close以外で無いんだろうか。

Trailing String

カンマで区切られた前半の文字列が、
後半の文字列で終わるなら1、そうでなければ0を表示。

正答率87%

((306.0/(306+45))*100).round

設問

You are given two strings 'A' and 'B'. Print out a 1 if string 'B' occurs at the end of string 'A'. Else a zero.

Input sample:

The first argument is a file, containing two strings, comma delimited, one per line. Ignore all empty lines in the input file.e.g.

Hello World,World
Hello CodeEval,CodeEval
San Francisco,San Jose

Output sample:

Print out 1 if the second string occurs at the end of the first string. Else zero. Do NOT print out empty lines between your output.
e.g.

1
1
0

やってみた

#!/usr/bin/env ruby
ARGF.lines do |line|
  puts line.chomp.split(',').instance_eval{ |main, trail| main.match(/#{trail}$/)? 1 : 0 }
end

Decimal To Binary

2進数に変換。これは簡単。
正答率82%

((316.0/(316+68))*100).round

設問

Given a decimal (base 10) number, print out its binary representation.

Input sample:

File containing positive whole decimal numbers, one per line. e.g.

2
10
67

Output sample:

Print the decimal representation, one per line.
e.g.

10
1010
1000011

やってみた

#!/usr/bin/env ruby
ARGF.lines do |line|
  puts line.to_i.to_s 2
end

Sum of integers

連続した整数の和で最大となるものを表示。
正答率69%

((246.0/(246+111))*100).round

設問

Write a program to determine the largest sum of contiguous integers in a list.

Input sample:

The first argument will be a text file containing a comma separated list of integers, one per line. e.g.

-10, 2, 3, -2, 0, 5, -15
2,3,-2,-1,10

Output sample:

Print to stdout, the largest sum. In other words, of all the possible contiguous subarrays for a given array, find the one with the largest sum, and print that sum.
e.g.

8
12

やってみた

#!/usr/bin/env ruby

def sum_of(integers)
  sums_all = []
  integers.each_with_index do |_, i|
    integers[i..-1].inject(0) do |sum, integer|
      sums_all << sum += integer
      sum
    end
  end
  sums_all.max
end

ARGF.lines do |line|
  puts sum_of(line.chomp.split(',').map(&:to_i))
end

each_with_indexが強引だ。

参考

RubyでSum of integersを解く-CodeEval - hp12c

  candidates = []
  begin
    nums.inject(0) { |mem, i| candidates << mem += i; mem }
  end while nums.shift

Array#shiftしながらwhileで回しています。
あとcandidatesという名前もいいですね。