{"action":"created","comment":{"url":"https://api.github.com/repos/yuvdanilova/CodeU/pulls/comments/129369032","pull_request_review_id":52135005,"id":129369032,"diff_hunk":"@@ -0,0 +1,117 @@\n+#!/usr/bin/env python3\n+from statistics import median\n+import unittest\n+import numpy as np\n+\n+class RearrangingArray():\n+\n+\tdef __init__(self, arrangement, verbose=False):\n+\n+\t\tself.arrangement = arrangement\n+\t\tself.swap_idx = None\n+\t\tself.order_dict = None\n+\t\tself.verbose = verbose\n+\n+\tdef _swap(self, i, j, k):\n+\t\t\"\"\" Swaps elements on indices i and j using an element on index k \"\"\"\n+\t\tif self.verbose:\n+\t\t\tprint(i, k)\n+\t\t\tprint(i, j)\n+\t\t\tprint(j, k)\n+\t\tself.arrangement[i],self.arrangement[k] = self.arrangement[k],self.arrangement[i]\n+\t\tself.arrangement[i],self.arrangement[j] = self.arrangement[j],self.arrangement[i]\n+\t\tself.arrangement[j],self.arrangement[k] = self.arrangement[k],self.arrangement[j]\n+\n+\tdef _move_swap_el(self, j):\n+\t\t\"\"\" Moves the swap element to position j from the current position \"\"\"\n+\t\ti = self.swap_idx\n+\t\twhile i < j:\n+\t\t\tif self.verbose:\n+\t\t\t\tprint(i, i+1)\n+\t\t\tself.arrangement[i],self.arrangement[i+1]=self.arrangement[i+1],self.arrangement[i]\n+\t\t\ti += 1\n+\t\twhile i > j:\n+\t\t\tif self.verbose:\n+\t\t\t\tprint(i, i-1)\n+\t\t\tself.arrangement[i],self.arrangement[i-1]=self.arrangement[i-1],self.arrangement[i]\n+\t\t\ti -= 1\n+\t\tself.swap_idx = j\n+\n+\tdef _build_dict(self, new_order):\n+\t\t\"\"\" \n+\t\tBuilds a dictionary which defines the desired sorting order\n+\n+\t\tInput:\n+\t\t\tnew_order: List, a permutation of the class arrangement list\n+\t\tOutput:\n+\t\t\torder_dict: Dict, keys are elements of the list, values are\n+\t\t\t\t\t\tpositions in the sorted list\n+\t\t\"\"\"\n+\t\torder_dict = {}\n+\t\tfor i, el in enumerate(new_order):\n+\t\t\torder_dict[el] = i\n+\t\treturn order_dict\n+\n+\tdef _partition(self, l, r):\n+\t\t\"\"\" Partition function for QuickSort sorting algorithm \"\"\"\n+\t\tpivot = median([\n+\t\t\tself.order_dict[self.arrangement[l]], \n+\t\t\tself.order_dict[self.arrangement[(l+r)//2]], \n+\t\t\tself.order_dict[self.arrangement[r]]]\n+\t\t)\n+\t\twhile True:","path":"assignment6.py","position":62,"original_position":62,"commit_id":"139dc5b064d6917141262659661ecf6b00bcd541","original_commit_id":"139dc5b064d6917141262659661ecf6b00bcd541","user":{"login":"yuvdanilova","id":28044744,"avatar_url":"https://avatars0.githubusercontent.com/u/28044744?v=4","gravatar_id":"","url":"https://api.github.com/users/yuvdanilova","html_url":"https://github.com/yuvdanilova","followers_url":"https://api.github.com/users/yuvdanilova/followers","following_url":"https://api.github.com/users/yuvdanilova/following{/other_user}","gists_url":"https://api.github.com/users/yuvdanilova/gists{/gist_id}","starred_url":"https://api.github.com/users/yuvdanilova/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/yuvdanilova/subscriptions","organizations_url":"https://api.github.com/users/yuvdanilova/orgs","repos_url":"https://api.github.com/users/yuvdanilova/repos","events_url":"https://api.github.com/users/yuvdanilova/events{/privacy}","received_events_url":"https://api.github.com/users/yuvdanilova/received_events","type":"User","site_admin":false},"body":"@OlgaVorokh ok, I'll try to avoid that too!","created_at":"2017-07-25T17:18:45Z","updated_at":"2017-07-25T17:18:45Z","html_url":"https://github.com/yuvdanilova/CodeU/pull/6#discussion_r129369032","pull_request_url":"https://api.github.com/repos/yuvdanilova/CodeU/pulls/6","_links":{"self":{"href":"https://api.github.com/repos/yuvdanilova/CodeU/pulls/comments/129369032"},"html":{"href":"https://github.com/yuvdanilova/CodeU/pull/6#discussion_r129369032"},"pull_request":{"href":"https://api.github.com/repos/yuvdanilova/CodeU/pulls/6"}}},"pull_request":{"url":"https://api.github.com/repos/yuvdanilova/CodeU/pulls/6","id":131780260,"html_url":"https://github.com/yuvdanilova/CodeU/pull/6","diff_url":"https://github.com/yuvdanilova/CodeU/pull/6.diff","patch_url":"https://github.com/yuvdanilova/CodeU/pull/6.patch","issue_url":"https://api.github.com/repos/yuvdanilova/CodeU/issues/6","number":6,"state":"open","locked":false,"title":"sixth assignment: rearranging cars","user":{"login":"yuvdanilova","id":28044744,"avatar_url":"https://avatars0.githubusercontent.com/u/28044744?v=4","gravatar_id":"","url":"https://api.github.com/users/yuvdanilova","html_url":"https://github.com/yuvdanilova","followers_url":"https://api.github.com/users/yuvdanilova/followers","following_url":"https://api.github.com/users/yuvdanilova/following{/other_user}","gists_url":"https://api.github.com/users/yuvdanilova/gists{/gist_id}","starred_url":"https://api.github.com/users/yuvdanilova/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/yuvdanilova/subscriptions","organizations_url":"https://api.github.com/users/yuvdanilova/orgs","repos_url":"https://api.github.com/users/yuvdanilova/repos","events_url":"https://api.github.com/users/yuvdanilova/events{/privacy}","received_events_url":"https://api.github.com/users/yuvdanilova/received_events","type":"User","site_admin":false},"body":"## Task 6, assignment6.py\r\n\r\n**Description:**\r\nWe are given two arrays of the same size which describe positions of cars on parking lots, initial and desired. There is exactly one empty slot, denoted by 0. We should rearrange cars in the given order, though the only possible action at one moment is to move one particular car to an empty slot.\r\n\r\n### Solution\r\n\r\nThis task could be approached as a simple sorting problem with specific swap and comparison functions.\r\n\r\n**Swapping**:\r\nGiven objects [__a, b, c__] at indices [__i, j, k__] we can swap __a__ and __b__ by swapping these with __c__ in three operations:\r\n\r\n1) __a <-> c__, swap elements at __i__ and __k__, get [__c, b, a__]\r\n2) __b <-> c__, swap elements at __i__ and __j__, get [__b, c, a__]\r\n2) __c <-> a__, swap elements at __j__ and __k__, get [__b, a, c__]\r\n\r\nThus if we know where the empty slot is located, we can swap any two cars in O(1), and the empty slot remains on the same place.\r\n\r\n**Sorting order**:\r\nUsing a target list, we can create a dictionary object where keys are our cars and values are their positions in the final arrangement. If we use a comparison-based sorting algorithm, we obtain the right order by comparing those values.\r\n\r\n**Sorting algorithm**:\r\nI decided to use QuickSort as a sorting algorithm. I also thought of HeapSort, which is O(nlogn)  worst case, but its disadvantage is that it usually makes more swaps, and in this task we made the swapping procedure more complicated.\r\n\r\nModifications: first I move the empty slot to the end of the array, then sort N-1 elements, then move the empty slot to the final position.\r\n\r\n### Asymptotic analysis\r\n\r\n**Time complexity**:\r\nO(n) for creating a dict\r\nO(n) for moving the empty slot\r\nO(nlogn) - QuickSort average case, O(n^2) - QuickSort worst case\r\nTotal: __O(nlogn)__ - average case, __O(n^2)__ - worst case\r\n\r\n**Space complexity**:\r\n__O(n)__ for the order dictionary","created_at":"2017-07-21T13:58:37Z","updated_at":"2017-07-25T17:18:45Z","closed_at":null,"merged_at":null,"merge_commit_sha":"2a4c89bb3d38d5e6ecc279b21242e8d4dd5a551e","assignee":null,"assignees":[],"requested_reviewers":[{"login":"ariava","id":2934778,"avatar_url":"https://avatars0.githubusercontent.com/u/2934778?v=4","gravatar_id":"","url":"https://api.github.com/users/ariava","html_url":"https://github.com/ariava","followers_url":"https://api.github.com/users/ariava/followers","following_url":"https://api.github.com/users/ariava/following{/other_user}","gists_url":"https://api.github.com/users/ariava/gists{/gist_id}","starred_url":"https://api.github.com/users/ariava/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/ariava/subscriptions","organizations_url":"https://api.github.com/users/ariava/orgs","repos_url":"https://api.github.com/users/ariava/repos","events_url":"https://api.github.com/users/ariava/events{/privacy}","received_events_url":"https://api.github.com/users/ariava/received_events","type":"User","site_admin":false},{"login":"hayux","id":28050124,"avatar_url":"https://avatars2.githubusercontent.com/u/28050124?v=4","gravatar_id":"","url":"https://api.github.com/users/hayux","html_url":"https://github.com/hayux","followers_url":"https://api.github.com/users/hayux/followers","following_url":"https://api.github.com/users/hayux/following{/other_user}","gists_url":"https://api.github.com/users/hayux/gists{/gist_id}","starred_url":"https://api.github.com/users/hayux/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/hayux/subscriptions","organizations_url":"https://api.github.com/users/hayux/orgs","repos_url":"https://api.github.com/users/hayux/repos","events_url":"https://api.github.com/users/hayux/events{/privacy}","received_events_url":"https://api.github.com/users/hayux/received_events","type":"User","site_admin":false}],"milestone":null,"commits_url":"https://api.github.com/repos/yuvdanilova/CodeU/pulls/6/commits","review_comments_url":"https://api.github.com/repos/yuvdanilova/CodeU/pulls/6/comments","review_comment_url":"https://api.github.com/repos/yuvdanilova/CodeU/pulls/comments{/number}","comments_url":"https://api.github.com/repos/yuvdanilova/CodeU/issues/6/comments","statuses_url":"https://api.github.com/repos/yuvdanilova/CodeU/statuses/139dc5b064d6917141262659661ecf6b00bcd541","head":{"label":"yuvdanilova:assignment6","ref":"assignment6","sha":"139dc5b064d6917141262659661ecf6b00bcd541","user":{"login":"yuvdanilova","id":28044744,"avatar_url":"https://avatars0.githubusercontent.com/u/28044744?v=4","gravatar_id":"","url":"https://api.github.com/users/yuvdanilova","html_url":"https://github.com/yuvdanilova","followers_url":"https://api.github.com/users/yuvdanilova/followers","following_url":"https://api.github.com/users/yuvdanilova/following{/other_user}","gists_url":"https://api.github.com/users/yuvdanilova/gists{/gist_id}","starred_url":"https://api.github.com/users/yuvdanilova/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/yuvdanilova/subscriptions","organizations_url":"https://api.github.com/users/yuvdanilova/orgs","repos_url":"https://api.github.com/users/yuvdanilova/repos","events_url":"https://api.github.com/users/yuvdanilova/events{/privacy}","received_events_url":"https://api.github.com/users/yuvdanilova/received_events","type":"User","site_admin":false},"repo":{"id":91662086,"name":"CodeU","full_name":"yuvdanilova/CodeU","owner":{"login":"yuvdanilova","id":28044744,"avatar_url":"https://avatars0.githubusercontent.com/u/28044744?v=4","gravatar_id":"","url":"https://api.github.com/users/yuvdanilova","html_url":"https://github.com/yuvdanilova","followers_url":"https://api.github.com/users/yuvdanilova/followers","following_url":"https://api.github.com/users/yuvdanilova/following{/other_user}","gists_url":"https://api.github.com/users/yuvdanilova/gists{/gist_id}","starred_url":"https://api.github.com/users/yuvdanilova/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/yuvdanilova/subscriptions","organizations_url":"https://api.github.com/users/yuvdanilova/orgs","repos_url":"https://api.github.com/users/yuvdanilova/repos","events_url":"https://api.github.com/users/yuvdanilova/events{/privacy}","received_events_url":"https://api.github.com/users/yuvdanilova/received_events","type":"User","site_admin":false},"private":false,"html_url":"https://github.com/yuvdanilova/CodeU","description":null,"fork":false,"url":"https://api.github.com/repos/yuvdanilova/CodeU","forks_url":"https://api.github.com/repos/yuvdanilova/CodeU/forks","keys_url":"https://api.github.com/repos/yuvdanilova/CodeU/keys{/key_id}","collaborators_url":"https://api.github.com/repos/yuvdanilova/CodeU/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/yuvdanilova/CodeU/teams","hooks_url":"https://api.github.com/repos/yuvdanilova/CodeU/hooks","issue_events_url":"https://api.github.com/repos/yuvdanilova/CodeU/issues/events{/number}","events_url":"https://api.github.com/repos/yuvdanilova/CodeU/events","assignees_url":"https://api.github.com/repos/yuvdanilova/CodeU/assignees{/user}","branches_url":"https://api.github.com/repos/yuvdanilova/CodeU/branches{/branch}","tags_url":"https://api.github.com/repos/yuvdanilova/CodeU/tags","blobs_url":"https://api.github.com/repos/yuvdanilova/CodeU/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/yuvdanilova/CodeU/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/yuvdanilova/CodeU/git/refs{/sha}","trees_url":"https://api.github.com/repos/yuvdanilova/CodeU/git/trees{/sha}","statuses_url":"https://api.github.com/repos/yuvdanilova/CodeU/statuses/{sha}","languages_url":"https://api.github.com/repos/yuvdanilova/CodeU/languages","stargazers_url":"https://api.github.com/repos/yuvdanilova/CodeU/stargazers","contributors_url":"https://api.github.com/repos/yuvdanilova/CodeU/contributors","subscribers_url":"https://api.github.com/repos/yuvdanilova/CodeU/subscribers","subscription_url":"https://api.github.com/repos/yuvdanilova/CodeU/subscription","commits_url":"https://api.github.com/repos/yuvdanilova/CodeU/commits{/sha}","git_commits_url":"https://api.github.com/repos/yuvdanilova/CodeU/git/commits{/sha}","comments_url":"https://api.github.com/repos/yuvdanilova/CodeU/comments{/number}","issue_comment_url":"https://api.github.com/repos/yuvdanilova/CodeU/issues/comments{/number}","contents_url":"https://api.github.com/repos/yuvdanilova/CodeU/contents/{+path}","compare_url":"https://api.github.com/repos/yuvdanilova/CodeU/compare/{base}...{head}","merges_url":"https://api.github.com/repos/yuvdanilova/CodeU/merges","archive_url":"https://api.github.com/repos/yuvdanilova/CodeU/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/yuvdanilova/CodeU/downloads","issues_url":"https://api.github.com/repos/yuvdanilova/CodeU/issues{/number}","pulls_url":"https://api.github.com/repos/yuvdanilova/CodeU/pulls{/number}","milestones_url":"https://api.github.com/repos/yuvdanilova/CodeU/milestones{/number}","notifications_url":"https://api.github.com/repos/yuvdanilova/CodeU/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/yuvdanilova/CodeU/labels{/name}","releases_url":"https://api.github.com/repos/yuvdanilova/CodeU/releases{/id}","deployments_url":"https://api.github.com/repos/yuvdanilova/CodeU/deployments","created_at":"2017-05-18T07:23:33Z","updated_at":"2017-06-11T10:43:27Z","pushed_at":"2017-07-21T13:58:38Z","git_url":"git://github.com/yuvdanilova/CodeU.git","ssh_url":"git@github.com:yuvdanilova/CodeU.git","clone_url":"https://github.com/yuvdanilova/CodeU.git","svn_url":"https://github.com/yuvdanilova/CodeU","homepage":null,"size":11,"stargazers_count":0,"watchers_count":0,"language":"Python","has_issues":true,"has_projects":true,"has_downloads":true,"has_wiki":true,"has_pages":false,"forks_count":0,"mirror_url":null,"open_issues_count":3,"forks":0,"open_issues":3,"watchers":0,"default_branch":"master"}},"base":{"label":"yuvdanilova:master","ref":"master","sha":"8bb7b1a17695d8ff4ac775d7473ef86e5255d6b2","user":{"login":"yuvdanilova","id":28044744,"avatar_url":"https://avatars0.githubusercontent.com/u/28044744?v=4","gravatar_id":"","url":"https://api.github.com/users/yuvdanilova","html_url":"https://github.com/yuvdanilova","followers_url":"https://api.github.com/users/yuvdanilova/followers","following_url":"https://api.github.com/users/yuvdanilova/following{/other_user}","gists_url":"https://api.github.com/users/yuvdanilova/gists{/gist_id}","starred_url":"https://api.github.com/users/yuvdanilova/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/yuvdanilova/subscriptions","organizations_url":"https://api.github.com/users/yuvdanilova/orgs","repos_url":"https://api.github.com/users/yuvdanilova/repos","events_url":"https://api.github.com/users/yuvdanilova/events{/privacy}","received_events_url":"https://api.github.com/users/yuvdanilova/received_events","type":"User","site_admin":false},"repo":{"id":91662086,"name":"CodeU","full_name":"yuvdanilova/CodeU","owner":{"login":"yuvdanilova","id":28044744,"avatar_url":"https://avatars0.githubusercontent.com/u/28044744?v=4","gravatar_id":"","url":"https://api.github.com/users/yuvdanilova","html_url":"https://github.com/yuvdanilova","followers_url":"https://api.github.com/users/yuvdanilova/followers","following_url":"https://api.github.com/users/yuvdanilova/following{/other_user}","gists_url":"https://api.github.com/users/yuvdanilova/gists{/gist_id}","starred_url":"https://api.github.com/users/yuvdanilova/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/yuvdanilova/subscriptions","organizations_url":"https://api.github.com/users/yuvdanilova/orgs","repos_url":"https://api.github.com/users/yuvdanilova/repos","events_url":"https://api.github.com/users/yuvdanilova/events{/privacy}","received_events_url":"https://api.github.com/users/yuvdanilova/received_events","type":"User","site_admin":false},"private":false,"html_url":"https://github.com/yuvdanilova/CodeU","description":null,"fork":false,"url":"https://api.github.com/repos/yuvdanilova/CodeU","forks_url":"https://api.github.com/repos/yuvdanilova/CodeU/forks","keys_url":"https://api.github.com/repos/yuvdanilova/CodeU/keys{/key_id}","collaborators_url":"https://api.github.com/repos/yuvdanilova/CodeU/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/yuvdanilova/CodeU/teams","hooks_url":"https://api.github.com/repos/yuvdanilova/CodeU/hooks","issue_events_url":"https://api.github.com/repos/yuvdanilova/CodeU/issues/events{/number}","events_url":"https://api.github.com/repos/yuvdanilova/CodeU/events","assignees_url":"https://api.github.com/repos/yuvdanilova/CodeU/assignees{/user}","branches_url":"https://api.github.com/repos/yuvdanilova/CodeU/branches{/branch}","tags_url":"https://api.github.com/repos/yuvdanilova/CodeU/tags","blobs_url":"https://api.github.com/repos/yuvdanilova/CodeU/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/yuvdanilova/CodeU/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/yuvdanilova/CodeU/git/refs{/sha}","trees_url":"https://api.github.com/repos/yuvdanilova/CodeU/git/trees{/sha}","statuses_url":"https://api.github.com/repos/yuvdanilova/CodeU/statuses/{sha}","languages_url":"https://api.github.com/repos/yuvdanilova/CodeU/languages","stargazers_url":"https://api.github.com/repos/yuvdanilova/CodeU/stargazers","contributors_url":"https://api.github.com/repos/yuvdanilova/CodeU/contributors","subscribers_url":"https://api.github.com/repos/yuvdanilova/CodeU/subscribers","subscription_url":"https://api.github.com/repos/yuvdanilova/CodeU/subscription","commits_url":"https://api.github.com/repos/yuvdanilova/CodeU/commits{/sha}","git_commits_url":"https://api.github.com/repos/yuvdanilova/CodeU/git/commits{/sha}","comments_url":"https://api.github.com/repos/yuvdanilova/CodeU/comments{/number}","issue_comment_url":"https://api.github.com/repos/yuvdanilova/CodeU/issues/comments{/number}","contents_url":"https://api.github.com/repos/yuvdanilova/CodeU/contents/{+path}","compare_url":"https://api.github.com/repos/yuvdanilova/CodeU/compare/{base}...{head}","merges_url":"https://api.github.com/repos/yuvdanilova/CodeU/merges","archive_url":"https://api.github.com/repos/yuvdanilova/CodeU/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/yuvdanilova/CodeU/downloads","issues_url":"https://api.github.com/repos/yuvdanilova/CodeU/issues{/number}","pulls_url":"https://api.github.com/repos/yuvdanilova/CodeU/pulls{/number}","milestones_url":"https://api.github.com/repos/yuvdanilova/CodeU/milestones{/number}","notifications_url":"https://api.github.com/repos/yuvdanilova/CodeU/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/yuvdanilova/CodeU/labels{/name}","releases_url":"https://api.github.com/repos/yuvdanilova/CodeU/releases{/id}","deployments_url":"https://api.github.com/repos/yuvdanilova/CodeU/deployments","created_at":"2017-05-18T07:23:33Z","updated_at":"2017-06-11T10:43:27Z","pushed_at":"2017-07-21T13:58:38Z","git_url":"git://github.com/yuvdanilova/CodeU.git","ssh_url":"git@github.com:yuvdanilova/CodeU.git","clone_url":"https://github.com/yuvdanilova/CodeU.git","svn_url":"https://github.com/yuvdanilova/CodeU","homepage":null,"size":11,"stargazers_count":0,"watchers_count":0,"language":"Python","has_issues":true,"has_projects":true,"has_downloads":true,"has_wiki":true,"has_pages":false,"forks_count":0,"mirror_url":null,"open_issues_count":3,"forks":0,"open_issues":3,"watchers":0,"default_branch":"master"}},"_links":{"self":{"href":"https://api.github.com/repos/yuvdanilova/CodeU/pulls/6"},"html":{"href":"https://github.com/yuvdanilova/CodeU/pull/6"},"issue":{"href":"https://api.github.com/repos/yuvdanilova/CodeU/issues/6"},"comments":{"href":"https://api.github.com/repos/yuvdanilova/CodeU/issues/6/comments"},"review_comments":{"href":"https://api.github.com/repos/yuvdanilova/CodeU/pulls/6/comments"},"review_comment":{"href":"https://api.github.com/repos/yuvdanilova/CodeU/pulls/comments{/number}"},"commits":{"href":"https://api.github.com/repos/yuvdanilova/CodeU/pulls/6/commits"},"statuses":{"href":"https://api.github.com/repos/yuvdanilova/CodeU/statuses/139dc5b064d6917141262659661ecf6b00bcd541"}}}}
{"actor":{"display_login":"yuvdanilova"}}