Skip to content

Commit

Permalink
Merge remote-tracking branch 'origin/master'
Browse files Browse the repository at this point in the history
  • Loading branch information
@ntsd
ntsd committed Apr 25, 2018
2 parents 29f12a9 + e37a11b commit 6125a95
Show file tree
Hide file tree
Showing 15 changed files with 801 additions and 166 deletions.
4 changes: 4 additions & 0 deletions .gitignore
View file
Original file line number Diff line number Diff line change
Expand Up @@ -3,4 +3,8 @@

*.csv

*.hdf5

*.csv

*.zip
32 changes: 32 additions & 0 deletions CodeJam/2018/Qualification/GoGopher.py
View file
Original file line number Diff line number Diff line change
@@ -0,0 +1,32 @@
import sys

def goGopher(a):
win = False
if a == 20:
rows, cols = 4, 5
else:
rows, cols = 10, 20
print(rows, cols,file=sys.stderr)
trees = [[False for x in range(cols)] for y in range(rows)]
for y, row in enumerate(trees):
if win:
break
for x, tree in enumerate(row):
if win:
break
while tree is False:
print(max(2, min(rows - 1, y + 2)), max(2, min(cols - 1, x + 2)))
sys.stdout.flush()
i, j = map(int, input().split(' '))
if i == -1 and j == -1:
sys.exit(-1)
if i == 0 and j == 0:
win = True
break
trees[i - 1][j - 1] = True
tree = trees[y][x]
print(trees,file=sys.stderr)

for _ in range(int(input())):
a=int(input())
goGopher(a)
40 changes: 40 additions & 0 deletions CodeJam/2018/Qualification/Saving-The-Universe-Again.py
View file
Original file line number Diff line number Diff line change
@@ -0,0 +1,40 @@
from math import ceil
def savingTheUniverse(hp, p):
dmg=1
sum_dmg=0
charge=[]
num_s=0
for i in p:
if i=="S":
sum_dmg+=dmg
num_s+=1
else:
charge.append(num_s)
dmg*=2
num_s=0
charge.append(num_s)
charge.pop(0)
lengh_charge=len(charge)
reduce_dmg = int(2**(lengh_charge-1))
number_of_hack=0
if sum_dmg <= hp:
return 0
can_reduce = 0
for i in charge[::-1]:
can_reduce += i
diff = sum_dmg-hp
#print('can_reduce', can_reduce, 'reduce_dmg',reduce_dmg, 'diff', diff, 'number_of_hack', number_of_hack)
if diff <= reduce_dmg * can_reduce:
n=ceil(diff/reduce_dmg)
return number_of_hack+n
sum_dmg -= reduce_dmg * can_reduce
reduce_dmg //= 2
number_of_hack += i
return "IMPOSSIBLE"

if __name__ == '__main__':
for i in range(int(input())):
d, p = input().split()
d=int(d)
ans=savingTheUniverse(d, p)
print("Case #{}: {}".format(i+1, ans))
25 changes: 25 additions & 0 deletions CodeJam/2018/Qualification/TroubleSort.py
View file
Original file line number Diff line number Diff line change
@@ -0,0 +1,25 @@
"""
3
5
5 6 8 4 3
3
8 9 7
4
1 3 2 4
"""
def troubleSort(n, nums):
odd=sorted(nums[::2])
even=sorted(nums[1::2])
for i in range(n-1):
if i % 2 == 0 and odd[i//2] > even[i//2]:
return i
elif i % 2 == 1 and even[i//2] > odd[i//2 + 1]:
return i
return 'OK'

if __name__ == "__main__":
for i in range(1, int(input())+1):
n = int(input())
nums=list(map(int, input().split()))
ans = troubleSort(n, nums)
print("Case #{}: {}".format(i, ans))
61 changes: 61 additions & 0 deletions CodeJam/2018/Qualification/c.py
View file
Original file line number Diff line number Diff line change
@@ -0,0 +1,61 @@
#!/usr/bin/env python3
import sys


def run():
t = int(input())

for c in range(t):
# target area
a = int(input())
print('>>>> a = %d' % a, file=sys.stderr)
# target W*H
w = 3
h = 3
while w * w < a:
w += 1
h += 1
while h > 3 and w * (h - 1) >= a:
h -= 1

print('W*H = %d*%d' % (w, h), file=sys.stderr)

# the grid
g = [[False] * (h + 1) for i in range(w + 1)]

# the indices mapper, empty cell with the center
m = [set() for i in range(10)]

for i in range(2, w):
for j in range(2, h):
m[9].add((i, j))

done = False
k = 9

while not done:
while len(m[k]) == 0:
k -= 1
i, j = next(iter(m[k]))
print('put (%d, %d)' % (i, j), file=sys.stderr)
#print(m, file=sys.stderr)
print(i, j)
x, y = map(int, input().split())
print('get (%d, %d)' % (x, y), file=sys.stderr)
if x == 0 and y == 0:
done = True
elif x == -1 and y == -1:
exit(1)
elif not g[x][y]:
g[x][y] = True
for dx in [-1, 0, 1]:
for dy in [-1, 0, 1]:
xx = x + dx
yy = y + dy
for kk in range(1, 10):
if (xx, yy) in m[kk]:
m[kk - 1].add((xx, yy))
m[kk].remove((xx, yy))
print(m, file=sys.stderr)

run()
212 changes: 212 additions & 0 deletions CodeJam/2018/Qualification/testing_tool.py
View file
Original file line number Diff line number Diff line change
@@ -0,0 +1,212 @@
""" Python script for local testing (compatible with both Python 2 and Python 3)
Disclaimer: this is a way to test your solutions, but it is NOT the real judging
system. The judging system behavior might be different.
"""

from __future__ import print_function
import random
import subprocess
import sys

USAGE_MSG = """
Usage:
Linux and Mac users:
From your terminal, run
python testing_tool.py command_to_run_your_script_or_executable
Note that command_to_run_your_script_or_executable is read as a list of
arguments, so you should NOT wrap it with quotation marks.
Examples:
C++, after compilation:
python testing_tool.py ./my_binary
Python:
python testing_tool.py python my_code.py
Java, after compilation:
python testing_tool.py java my_main_class_name
See https://code.google.com/codejam/resources/faq#languages for how we compile
and run your solution in the language of your choice.
Windows users:
Follow the instructions for Linux and Mac users if you are familiar with
terminal tools on Windows. Otherwise, please be advised that this script might
not work with Python 2 (it works with Python 3). In addition, if you cannot
pass arguments to Python, you will need to modify the "cmd = sys.argv[1:]"
line below.
"""

# Right now, there are 3 test cases with the minimum prepared area A in each
# test case being 10. We encourage you to modify LIST_OF_A for more thorough
# testing. Note that A[0] is the A given for the first test case, A[1] is for
# the second test case, etc. In real judging, A is the same for all test cases
# within the same test set.
LIST_OF_A = [4, 5, 6]
NUM_TEST_CASES = len(LIST_OF_A)
# You can set PRINT_INTERACTION_HISTORY to True to print out the interaction
# history between your code and the judge.
PRINT_INTERACTION_HISTORY = False


"""Helper functions"""
def JudgePrint(p, s):
# Print the judge output to your code's input stream. Log this interaction
# to console (stdout) if PRINT_INTERACTION_HISTORY is True.
print(s, file=p.stdin)
p.stdin.flush()
if PRINT_INTERACTION_HISTORY:
print("Judge prints:", s)


def PrintSubprocessResults(p):
# Print the return code and stderr output for your code.
print("Your code finishes with exit status {}.".format(p.returncode))
code_stderr_output = p.stderr.read()
if code_stderr_output:
print("The stderr output of your code is:")
sys.stdout.write(code_stderr_output)
else:
print("Your code doesn't have stderr output.")


def WaitForSubprocess(p):
# Wait for your code to finish and print the stderr output of your code for
# debugging purposes.
if p.poll() is None:
print("Waiting for your code to finish...")
p.wait()
PrintSubprocessResults(p)


def CheckSubprocessExit(p, case_id):
# Exit if your code finishes in the middle of a test case.
if p.poll() is not None:
print("Your code exited early, in the middle of Case #{}.".format(case_id))
PrintSubprocessResults(p)
sys.exit(-1)


def WrongAnswerExit(p, case_id, error_msg):
print("Case #{} failed: {}".format(case_id, error_msg))
try:
JudgePrint(p, "-1 -1")
except IOError:
print("Failed to print -1 -1 because your code finished already.")
WaitForSubprocess(p)
sys.exit(-1)


"""Main function begins"""
# Retrieve the command to run your code from the arguments.
# If you cannot pass arguments to Python when running this testing tool, please
# replace sys.argv[1:] with the command list to run your code.
# e.g. C++ users: cmd = ["./my_binary"]
# Python users: cmd = [sys.executable, "my_code.py"]
# Java users: cmd = ["java", "my_main_class_name"]
cmd = sys.argv[1:]
assert cmd, "There should be at least one argument." + USAGE_MSG
if (cmd[0] == "-h") or (cmd[0] == "-help") or (cmd[0] == "--h") or (
cmd[0] == "--help"):
print(USAGE_MSG)
sys.exit(0)

# Run your code in a separate process. You can debug your code by printing to
# stderr inside your code, or adding print statements in this testing tool.
# Note that your stderr output will be printed by this testing tool only after
# your code finishes, e.g. if your code hangs, you wouldn't get your stderr
# output.
try:
p = subprocess.Popen(
cmd,
stdin=subprocess.PIPE,
stdout=subprocess.PIPE,
stderr=subprocess.PIPE,
bufsize=1,
universal_newlines=True)
except Exception as e:
print("Failed to start running your code. Error:")
print(e)
sys.exit(-1)

JudgePrint(p, NUM_TEST_CASES)
for test_case_id in range(1, NUM_TEST_CASES + 1):
if PRINT_INTERACTION_HISTORY:
print("Test Case #{}:".format(test_case_id))
# Different test case has different seed.
random.seed(test_case_id)
A = LIST_OF_A[test_case_id - 1]
JudgePrint(p, A)
test_case_passed = False
random.seed(test_case_id)
field = set()
prepared_cells_count = 0
northmost = None
for _ in range(1000):
# Detect whether the subprocess has finished running.
CheckSubprocessExit(p, test_case_id)

user_input = None
try:
user_input = p.stdout.readline()
i, j = map(int, user_input.split())
except:
# Note that your code might finish after the first CheckSubprocessExit
# check above but before the readline(), so we will need to again check
# whether your code has finished.
CheckSubprocessExit(p, test_case_id)
exit_msg = ""
if user_input == "":
exit_msg = (
"Read an empty string as opposed to 2 integers for cell location. "
"This might happen because your code exited early, or printed an "
"extra newline character.")
elif user_input is None:
exit_msg = (
"Unable to read the cell location. This might happen because your "
"code exited early, printed an extra new line character, or did "
"not print the output correctly.")
else:
exit_msg = (
"Failed to read the cell location. Expected two integers ending "
"with one newline character. Read \"{}\" (quotes added to isolate "
"output of your program) instead.".format(user_input))
WrongAnswerExit(p, test_case_id, exit_msg)
if PRINT_INTERACTION_HISTORY:
print("Judge reads:", user_input.rstrip())
if (i <= 1) or (i >= 1000) or (j <= 1) or (j >= 1000):
WrongAnswerExit(p, test_case_id, "Your input is out of range [2, 999].")
prepared_i = random.randint(i - 1, i + 1)
prepared_j = random.randint(j - 1, j + 1)
if not (prepared_i, prepared_j) in field:
if northmost is None:
northmost = prepared_i
southmost = prepared_i
westmost = prepared_j
eastmost = prepared_j
else:
northmost = min(prepared_i, northmost)
southmost = max(prepared_i, southmost)
westmost = min(prepared_j, westmost)
eastmost = max(prepared_j, eastmost)
field.add((prepared_i, prepared_j))
prepared_cells_count += 1
if (prepared_cells_count >=
A) and (prepared_cells_count == (southmost - northmost + 1) *
(eastmost - westmost + 1)):
JudgePrint(p, "0 0")
test_case_passed = True
break
JudgePrint(p, "{} {}".format(prepared_i, prepared_j))
if not test_case_passed:
WrongAnswerExit(p, test_case_id,
"Failed to prepare the rectangle within 1000 tries.")

extra_output = p.stdout.readline()
WaitForSubprocess(p)
if extra_output == "":
print("Congratulations! All test cases passed :)")
else:
print("Wrong Answer because of extra output:")
sys.stdout.write(extra_output)
sys.exit(-1)

Loading

0 comments on commit 6125a95

Please sign in to comment.