2
\$\begingroup\$

Short problem description:

A sequence of numbers are antiarithemtic if there exists no three numbers a_i, a_j, a_k – where a_i preceeds a_j which then again preceeds a_k in the sequence – such that a_i - a_j = a_j - a_k. Example: (5, 0, -1, 3, 1) is not antiarithemtic, because 5-3 = 3-1, wheras the sequence (1, 5, 3, 0, -1) is antiarithemtic.

Link to the Kattis page.

My attempt:

import sys

lines = sys.stdin.readlines()
lines = [x[:-1] for x in lines]
for line in lines:
    if len(line) > 1:
        line = line.split(':')
        found = False
        visited = {}
        curr = line[1].split()
        r = len(curr)
        for i in range(r):
            visited_2 = {}
            if curr[i] in visited:
                continue
            else:
                visited[curr[i]] = True
                for j in range(i+1, r):
                    if curr[j] in visited_2:
                        continue
                    else:
                        visited_2[curr[j]] = True
                        tmp = int(curr[i]) - int(curr[j])
                        for k in range(j+1, r):
                            if int(curr[j]) - int(curr[k]) == tmp:
                                print("no")
                                found = True
                                break
        if not found:
            print("yes")
    else:
        break

I believe my attempt solves the problem of finding out whether a sequence is antiarithmetic or not, as I've made my own extensive example-set to test that. My optimizing step so far has been to include dictionaries of visited "nodes" so as to not repeat searches for numbers that we already know do not result in an arithmetic sequence. However, it is not fast enough for Kattis, so I would much appreciate any suggestions on how to improve this.

\$\endgroup\$
1
\$\begingroup\$

making your code harder to read:

  • lack of docstrings
  • lack of comments
  • unwarranted indentation using an else: after a "disruptive if" (transferring execution with return, break, continue)
    (Here, you are using this with otherwise empty "if-parts":
    you could negate the conditions and just use the former else:-statements. Hello again, indentation.)
\$\endgroup\$
  • \$\begingroup\$ You are absolutely right. I will clean up the code some time tomorrow when I have some free time. I didn't bother with it at first, thought maybe someone would see something that I've done wrong conceptually either way. But thank you, you are absolutely right. \$\endgroup\$ – RoyM Jul 20 at 17:44
  • 1
    \$\begingroup\$ (I belatedly noticed one more incidence of avoidable indentation right in the outer loop: you could use if len(line) <= 0: break;) If you are going to change the code more than a trifle/in any aspect mentioned by answers, ask a new question and cross-link unless you delete this one altogether. \$\endgroup\$ – greybeard Jul 20 at 17:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.