{"id":26520,"date":"2022-12-18T07:57:27","date_gmt":"2022-12-18T02:27:27","guid":{"rendered":"https:\/\/jassweb.com\/solved\/solved-people-dancing-algorithm\/"},"modified":"2022-12-18T07:57:27","modified_gmt":"2022-12-18T02:27:27","slug":"solved-people-dancing-algorithm","status":"publish","type":"post","link":"https:\/\/jassweb.com\/solved\/solved-people-dancing-algorithm\/","title":{"rendered":"[Solved] People Dancing Algorithm"},"content":{"rendered":"

[ad_1]
\n<\/p>\n

\n
\n
<\/div>\n
\n
\n

Current answer<\/strong><\/p>\n

The previous answer assumed that the movement of people to their new positions would be sequential, i.e. people would start moving together within the same sequence.<\/p>\n

The answer below assumes that the movement within the same sequence is instantaneous. It uses two arrays to map people from their old positions to their new positions, and continues running the sequence as long as there is a reduction in the total number of spaces occupied.<\/p>\n

public static void main(String[] args) {\n    int numberOfPeople = 4;\n    int[] moves = new int[]{3, 2, 1, 3};\n    int[] positions = new int[numberOfPeople];\n\n    Arrays.fill(positions, 1);\n\n    int positionsOccupied;\n\n    do {\n        positionsOccupied = positionsOccupied(positions);\n        positions = dance(positions, moves);\n\n    } while (positionsOccupied(positions) < positionsOccupied);\n\n    System.out.println(\"Result: \" + positionsOccupied(positions));\n}\n\npublic static int[] dance(int[] oldPositions, int[] moves) {\n    int[] newPositions = new int[oldPositions.length];\n\n    for (int i = 0; i < oldPositions.length; i++) {\n        newPositions[moves[i] - 1] += oldPositions[i];\n    }\n\n    return newPositions;\n}\n\npublic static int positionsOccupied(int[] positions) {\n    int result = 0;\n\n    for (int i = 0; i < positions.length; i++) {\n        if (positions[i] > 0) {\n            result++;\n        }\n    }\n\n    return result;\n}\n<\/code><\/pre>\n
Previous answer<\/strong><\/p>\n
You actually only need one array to hold the positions<\/code>, and an additional array to hold a snapshot<\/code> of the previous state.<\/p>\n
After every iteration, the snapshot is compared with the current positions, and if they’re equal this means that subsequent invocations of the dance sequence will have no further impact on the positions and that you can calculate a final result:<\/p>\n
public static void main(String[] args) {\n    int numberOfPeople = 4;\n    int[] moves = new int[]{3, 2, 1, 3};\n    int[] positions = new int[numberOfPeople];\n\n    Arrays.fill(positions, 1);\n\n    int[] snapshot;\n\n    do {\n        snapshot = Arrays.copyOf(positions, positions.length);\n\n        dance(positions, moves);\n    } while (!Arrays.equals(positions, snapshot));\n\n    System.out.println(\"Result: \" + positionsOccupied(positions));\n}\n\npublic static void dance(int[] positions, int[] moves) {\n    for (int i = 0; i < positions.length; i++) {\n        int currentNumber = positions[i];\n        positions[i] = 0;\n        positions[moves[i] - 1] += currentNumber;\n    }\n}\n\npublic static int positionsOccupied(int[] positions) {\n    int result = 0;\n\n    for (int i = 0; i < positions.length; i++) {\n        if (positions[i] > 0) {\n            result++;\n        }\n    }\n\n\n    return result;\n}\n<\/code><\/pre>\n<\/p><\/div>\n
<\/div>\n<\/div>\n
            <\/span> <\/p><\/div>\n<\/div>\n
[ad_2]<\/p>\n
solved People Dancing Algorithm <\/p>\n","protected":false},"excerpt":{"rendered":"
[ad_1] Current answer The previous answer assumed that the movement of people to their new positions would be sequential, i.e. people would start moving together within the same sequence. The answer below assumes that the movement within the same sequence is instantaneous. It uses two arrays to map people from their old positions to their … Read more<\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[320],"tags":[457,323],"class_list":["post-26520","post","type-post","status-publish","format-standard","hentry","category-solved","tag-algorithm","tag-java"],"yoast_head":"\n[Solved] People Dancing Algorithm - JassWeb<\/title>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/jassweb.com\/solved\/solved-people-dancing-algorithm\/\" \/>\n<meta property=\"og:locale\" content=\"en_US\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"[Solved] People Dancing Algorithm - JassWeb\" \/>\n<meta property=\"og:description\" content=\"[ad_1] Current answer The previous answer assumed that the movement of people to their new positions would be sequential, i.e. people would start moving together within the same sequence. The answer below assumes that the movement within the same sequence is instantaneous. It uses two arrays to map people from their old positions to their ... Read more\" \/>\n<meta property=\"og:url\" content=\"https:\/\/jassweb.com\/solved\/solved-people-dancing-algorithm\/\" \/>\n<meta property=\"og:site_name\" content=\"JassWeb\" \/>\n<meta property=\"article:published_time\" content=\"2022-12-18T02:27:27+00:00\" \/>\n<meta name=\"author\" content=\"Kirat\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:label1\" content=\"Written by\" \/>\n\t<meta name=\"twitter:data1\" content=\"Kirat\" \/>\n\t<meta name=\"twitter:label2\" content=\"Est. reading time\" \/>\n\t<meta name=\"twitter:data2\" content=\"2 minutes\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\/\/schema.org\",\"@graph\":[{\"@type\":\"Article\",\"@id\":\"https:\/\/jassweb.com\/solved\/solved-people-dancing-algorithm\/#article\",\"isPartOf\":{\"@id\":\"https:\/\/jassweb.com\/solved\/solved-people-dancing-algorithm\/\"},\"author\":{\"name\":\"Kirat\",\"@id\":\"https:\/\/jassweb.com\/solved\/#\/schema\/person\/65c9c7b7958150c0dc8371fa35dd7c31\"},\"headline\":\"[Solved] People Dancing Algorithm\",\"datePublished\":\"2022-12-18T02:27:27+00:00\",\"mainEntityOfPage\":{\"@id\":\"https:\/\/jassweb.com\/solved\/solved-people-dancing-algorithm\/\"},\"wordCount\":149,\"publisher\":{\"@id\":\"https:\/\/jassweb.com\/solved\/#organization\"},\"keywords\":[\"algorithm\",\"java\"],\"articleSection\":[\"Solved\"],\"inLanguage\":\"en-US\"},{\"@type\":\"WebPage\",\"@id\":\"https:\/\/jassweb.com\/solved\/solved-people-dancing-algorithm\/\",\"url\":\"https:\/\/jassweb.com\/solved\/solved-people-dancing-algorithm\/\",\"name\":\"[Solved] People Dancing Algorithm - JassWeb\",\"isPartOf\":{\"@id\":\"https:\/\/jassweb.com\/solved\/#website\"},\"datePublished\":\"2022-12-18T02:27:27+00:00\",\"breadcrumb\":{\"@id\":\"https:\/\/jassweb.com\/solved\/solved-people-dancing-algorithm\/#breadcrumb\"},\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/jassweb.com\/solved\/solved-people-dancing-algorithm\/\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/jassweb.com\/solved\/solved-people-dancing-algorithm\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"Home\",\"item\":\"https:\/\/jassweb.com\/solved\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"[Solved] People Dancing Algorithm\"}]},{\"@type\":\"WebSite\",\"@id\":\"https:\/\/jassweb.com\/solved\/#website\",\"url\":\"https:\/\/jassweb.com\/solved\/\",\"name\":\"JassWeb\",\"description\":\"Build High-quality Websites\",\"publisher\":{\"@id\":\"https:\/\/jassweb.com\/solved\/#organization\"},\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\/\/jassweb.com\/solved\/?s={search_term_string}\"},\"query-input\":{\"@type\":\"PropertyValueSpecification\",\"valueRequired\":true,\"valueName\":\"search_term_string\"}}],\"inLanguage\":\"en-US\"},{\"@type\":\"Organization\",\"@id\":\"https:\/\/jassweb.com\/solved\/#organization\",\"name\":\"Jass Web\",\"url\":\"https:\/\/jassweb.com\/solved\/\",\"logo\":{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"https:\/\/jassweb.com\/solved\/#\/schema\/logo\/image\/\",\"url\":\"https:\/\/jassweb.com\/wp-content\/uploads\/2021\/02\/jass-website-logo-1.png\",\"contentUrl\":\"https:\/\/jassweb.com\/wp-content\/uploads\/2021\/02\/jass-website-logo-1.png\",\"width\":693,\"height\":132,\"caption\":\"Jass Web\"},\"image\":{\"@id\":\"https:\/\/jassweb.com\/solved\/#\/schema\/logo\/image\/\"}},{\"@type\":\"Person\",\"@id\":\"https:\/\/jassweb.com\/solved\/#\/schema\/person\/65c9c7b7958150c0dc8371fa35dd7c31\",\"name\":\"Kirat\",\"image\":{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"https:\/\/jassweb.com\/solved\/#\/schema\/person\/image\/\",\"url\":\"https:\/\/jassweb.com\/solved\/wp-content\/litespeed\/avatar\/1261af3c9451399fa1336d28b98ea3bb.jpg?ver=1775193939\",\"contentUrl\":\"https:\/\/jassweb.com\/solved\/wp-content\/litespeed\/avatar\/1261af3c9451399fa1336d28b98ea3bb.jpg?ver=1775193939\",\"caption\":\"Kirat\"},\"sameAs\":[\"http:\/\/jassweb.com\"],\"url\":\"https:\/\/jassweb.com\/solved\/author\/jaspritsinghghumangmail-com\/\"}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"[Solved] People Dancing Algorithm - JassWeb","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/jassweb.com\/solved\/solved-people-dancing-algorithm\/","og_locale":"en_US","og_type":"article","og_title":"[Solved] People Dancing Algorithm - JassWeb","og_description":"[ad_1] Current answer The previous answer assumed that the movement of people to their new positions would be sequential, i.e. people would start moving together within the same sequence. The answer below assumes that the movement within the same sequence is instantaneous. It uses two arrays to map people from their old positions to their ... Read more","og_url":"https:\/\/jassweb.com\/solved\/solved-people-dancing-algorithm\/","og_site_name":"JassWeb","article_published_time":"2022-12-18T02:27:27+00:00","author":"Kirat","twitter_card":"summary_large_image","twitter_misc":{"Written by":"Kirat","Est. reading time":"2 minutes"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"Article","@id":"https:\/\/jassweb.com\/solved\/solved-people-dancing-algorithm\/#article","isPartOf":{"@id":"https:\/\/jassweb.com\/solved\/solved-people-dancing-algorithm\/"},"author":{"name":"Kirat","@id":"https:\/\/jassweb.com\/solved\/#\/schema\/person\/65c9c7b7958150c0dc8371fa35dd7c31"},"headline":"[Solved] People Dancing Algorithm","datePublished":"2022-12-18T02:27:27+00:00","mainEntityOfPage":{"@id":"https:\/\/jassweb.com\/solved\/solved-people-dancing-algorithm\/"},"wordCount":149,"publisher":{"@id":"https:\/\/jassweb.com\/solved\/#organization"},"keywords":["algorithm","java"],"articleSection":["Solved"],"inLanguage":"en-US"},{"@type":"WebPage","@id":"https:\/\/jassweb.com\/solved\/solved-people-dancing-algorithm\/","url":"https:\/\/jassweb.com\/solved\/solved-people-dancing-algorithm\/","name":"[Solved] People Dancing Algorithm - JassWeb","isPartOf":{"@id":"https:\/\/jassweb.com\/solved\/#website"},"datePublished":"2022-12-18T02:27:27+00:00","breadcrumb":{"@id":"https:\/\/jassweb.com\/solved\/solved-people-dancing-algorithm\/#breadcrumb"},"inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["https:\/\/jassweb.com\/solved\/solved-people-dancing-algorithm\/"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/jassweb.com\/solved\/solved-people-dancing-algorithm\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Home","item":"https:\/\/jassweb.com\/solved\/"},{"@type":"ListItem","position":2,"name":"[Solved] People Dancing Algorithm"}]},{"@type":"WebSite","@id":"https:\/\/jassweb.com\/solved\/#website","url":"https:\/\/jassweb.com\/solved\/","name":"JassWeb","description":"Build High-quality Websites","publisher":{"@id":"https:\/\/jassweb.com\/solved\/#organization"},"potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/jassweb.com\/solved\/?s={search_term_string}"},"query-input":{"@type":"PropertyValueSpecification","valueRequired":true,"valueName":"search_term_string"}}],"inLanguage":"en-US"},{"@type":"Organization","@id":"https:\/\/jassweb.com\/solved\/#organization","name":"Jass Web","url":"https:\/\/jassweb.com\/solved\/","logo":{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/jassweb.com\/solved\/#\/schema\/logo\/image\/","url":"https:\/\/jassweb.com\/wp-content\/uploads\/2021\/02\/jass-website-logo-1.png","contentUrl":"https:\/\/jassweb.com\/wp-content\/uploads\/2021\/02\/jass-website-logo-1.png","width":693,"height":132,"caption":"Jass Web"},"image":{"@id":"https:\/\/jassweb.com\/solved\/#\/schema\/logo\/image\/"}},{"@type":"Person","@id":"https:\/\/jassweb.com\/solved\/#\/schema\/person\/65c9c7b7958150c0dc8371fa35dd7c31","name":"Kirat","image":{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/jassweb.com\/solved\/#\/schema\/person\/image\/","url":"https:\/\/jassweb.com\/solved\/wp-content\/litespeed\/avatar\/1261af3c9451399fa1336d28b98ea3bb.jpg?ver=1775193939","contentUrl":"https:\/\/jassweb.com\/solved\/wp-content\/litespeed\/avatar\/1261af3c9451399fa1336d28b98ea3bb.jpg?ver=1775193939","caption":"Kirat"},"sameAs":["http:\/\/jassweb.com"],"url":"https:\/\/jassweb.com\/solved\/author\/jaspritsinghghumangmail-com\/"}]}},"_links":{"self":[{"href":"https:\/\/jassweb.com\/solved\/wp-json\/wp\/v2\/posts\/26520","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/jassweb.com\/solved\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/jassweb.com\/solved\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/jassweb.com\/solved\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/jassweb.com\/solved\/wp-json\/wp\/v2\/comments?post=26520"}],"version-history":[{"count":0,"href":"https:\/\/jassweb.com\/solved\/wp-json\/wp\/v2\/posts\/26520\/revisions"}],"wp:attachment":[{"href":"https:\/\/jassweb.com\/solved\/wp-json\/wp\/v2\/media?parent=26520"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/jassweb.com\/solved\/wp-json\/wp\/v2\/categories?post=26520"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/jassweb.com\/solved\/wp-json\/wp\/v2\/tags?post=26520"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}