Loading...
cap7ainjack avatar cap7ainjack 20 Точки

Java Fundamentals [EXAM]- 15 November 2015 - 03. Rubik's Matrix

Здравейте !

Въпросът ми относно тази задача е по-скоро за sub-lists, защото това е начина по който се опитвах да я реша, но не успя да ми се получи :)

Та значи идеята ми беше да събера всички числа, които трябва да въртя нанякъде(лист е цяла колона или цял ред) в един ArrayList от Integer  и после чрес sublist да взема Left Part and Right Part , да ги слепя и да получа rotated лист.

 

Като напълня ArrayList-a с оригиналната продредба, оптах няколко начина, нищо:

 

 ArrayList<Integer> leftPart = new ArrayList<Integer>(colList.subList(newList.size() - (moves - 1), newList.size()));

   ArrayList<Integer> rightPart = new ArrayList<Integer>(colList.subList(0, newList.size() - (moves -1)));

              newList.addAll(leftPart);
              newList.addAll(rightPart);

не се пълнят изобщо по-този начин. нито по този : 

 java.util.List<Integer> leftPart = colList.subList(0, moves);
     java.util.List<Integer> rightPart = colList.subList(moves, colList.size());

Има ли начин да сработи задачата по рози начин и как ? :)

Благодаря!

Тагове:
0
Java Advanced 16/11/2015 10:31:41
kidroca avatar kidroca 117 Точки

Здравей,

Задачата може да се реши чрез един спомагателен списък - правилно си се ориентирал да събереш всички елементи, от един цял ред или една цяла колона но не ти трябват повече списъци:

  • List<Integer> slider = new ArrayList();

 

Той се пълни по два начина в зависимост от посоката на въртене:

  1. Right или Down се взимат елементите от съответният ред, или колона, на матрицата от 0 към length -> всеки взет елемент се слага със: slider.add(element)
  2. Left или Up се взимат елементите от length - 1 към 0 (в обратен ред спреямо горното), всеки взет елемент се слага със slider.add(element) така в slider получаваш същото като по - горе но в обратен ред. (Можеш да се напълниш slider в обратен ред и по друг начин но в случея е по - разбираемо какво става)
  3. slider и в двата случея се пълни от 0 към length със .add, а редът или колоната в матрицата се обхожда по различен начин

 

Сега следва да открием индекса от който трябва да започнем да презаписваме нашият спомагателен лист във оригиналната матрица:

  1. Първо намираме реално колко движения трябва да се извършат: actual = totalNumberOfTurns % length (съответно length е на колоната или на реда завсичи от случая)
  2. Ако по - горе сме напълнили slider със елемети от матрицата от 0 към length -> index = actual;
  3. Ако сме го напълнили в обратен ред inex = length - actual - 1;

 

Сега вече имаме лист и индекс -> трябва да запишем вяка една стойност от slider във желаният ред/колона във матрицата като започнем от намереният index, случайте отново произлизат от това как сме напълнили спомагателният лист:

  1. от 0 към length -> правим цикъл който започва от index за всяко преминаване се записва в matrix[index] = slider.get(next) // next е поредният елемент във slider -> в началото next = 0, когато next достигне slider.size() цикъла прекъсва, в края на всяка итерация -> next++, index++ , ако index достигне length се занулява index = 0 
  2. от length - 1 към 0 -> правим същия цикъл като по горният но в случея в края на итерацията index-- и ако падне под 0 се приравнява към index = length - 1;

 

Край на хода -> списъкът е преписан в матрицата и може да бъде занулен (в случай че всеки ход използваш един и същи списък, по - лесно е всеки ход да си го оставиш да си прави нов с new).

Обобщение:
Може да се забележи че в случея използваме спомагателният списък като Queue<> -> винаги вадим елементите в реда в който сме ги сложили - от 0 към length -> а ги поставяме в матрицата в ред зависещ от текущата команда. В спомагателният списък елементите са в "норамален" или "обратен" ред -> този алгоритъм може да се оптимизира тук и там, но няма да е толкова праволенеен за обяснение. 
Надявам се си ме разбрал

Ето и едно решение -> ако не беше за време щеше да е с по - малко copy/paste :)

3
15/11/2015 22:14:47
cap7ainjack avatar cap7ainjack 20 Точки

Благодаря много за подробния отговор, разбрах те!

Никгоа не бих се сетил за такова изпипано решение на изпит, там винаги много бързам. Но си е много добро!

Все пак всичко се прави с един лист, след много опити е можело да се сетя, че е възможно :)

 

0
psdimitrov avatar psdimitrov 75 Точки

Здравей, 

Аз реших задачата по начин подобен на твоя. Когато трябва да местя ред или колона го пълня в един списък, взимам първата и втората част с sublist() и ги разменям.

List<Integer> firstHalf = lineRow.subList(0,lineRow.size()- turns);
List<Integer> secondHalf = lineRow.subList(lineRow.size() - turns, lineRow.size());
secondHalf.addAll(firstHalf);

После замествам съответния ред или колона с елементите от списъка secondhalf.

Метода sublist връща List, а не ArrayList.
List<E> subList(int fromIndex, int toIndex); 

Използвам това, за да местя надясно. Когато имам да местя наляво преобразувам броя ротации наляво в ротации на дясно.

Ето моето решение на задачата.

4
cap7ainjack avatar cap7ainjack 20 Точки
Здрасти!

Човече решението ми е на 90% клонинг на твоето, с някой дребн разлики, сега го подкарах за 10 мин и ми даде 100 от 100. Не разбрах листовете защо не ми ги е пълнело, но ми тръгна всичко когато изтрих 

import java.awt.*;
import java.awt.List;

и си оставих само 

import java.util.*;
import java.util.ArrayList;

С това awt ми подчертаваше Лист-а от интеджер, не знам как изобщщо съм си го импортнал...

Беше и края на изпита ,даже вече бях започнал да развалям работещи неща по кода само и само да пробвам някви неща.. та както и да е. Това нямаше да го видя изобщо на изпита. Много жалко, въпреки, че не мисля че това щеше да е  голямо "подсказване" от страна на менторите,  зашо не работи листа.

Мерси много на 2 реда код съм бил от решението ама шанс :) 

0
16/11/2015 17:37:03
psdimitrov avatar psdimitrov 75 Точки

Здравей,

Проблемът е, че импортвайки java.awt.List когато в кода пишеш List , се ползва класът List от пакета java.awt , а не интерфейса java,util.List , който ти трябва. Като напишеш List натиснеш Alt+Enter IntelliJ пита кой лист имаш впредвид, но ако натиснеш два пъти бързо може и да объркаш импортването без да искаш. Успех занапред.

1
tilchev92 avatar tilchev92 Trainer 128 Точки

Според мен с тези листове си усложнявате излишно решенията. Shift-ване на елементи по X и Y най-лесно се прави с 2 вложени цикъла. Нещо като коментара на peter.petrov тук.

0
biser.stoev avatar biser.stoev 57 Точки

И аз я решавах без листове, но нещо не ми се получи запазването на едната стойност та си усложних живота с копиране на матрици :Д. Ето решението ми: http://pastebin.com/0FThBAFW

П.П. Жалко, че на изпита заради бъга с джъдж, поради някаква причина бях сменил две променливи и ми даваше само 30/100...

0
16/11/2015 12:01:01
kidroca avatar kidroca 117 Точки

С вложен цикъл е по - лесно, но ще изпълниш вложеният цикъл в най - добрия случай един път, а в най - лошият length - 1. Т.е. в най лошият случай имаш n × m операции. Ако използваш лист n + n операции -> един n за четене и един за писане. 

0
tilchev92 avatar tilchev92 Trainer 128 Точки

А тези операции на листовете addAll, subList и т.н., виждал ли си им кода отвътре? те няма как да стават без поне едно обхождане. При мен външния цикъл е излишен, можех да го направя и с линейна сложност (тоест направо да местя колкото трябва а не 1 по 1), но на изпита реших да не го мисля толкова сложно, защото времето все пак е ограничено.

0
zisov4eto avatar zisov4eto 19 Точки

Темата е малко стара, но задачката е отново актуална в упражненията по курса Advanced C# Май 2016.

Качвам моето решение, като ротациите (по редове или колони) съм ги писал линейно. - КОД

Общо взето клонирам матрицата, обхождам с един цикъл по даденият/ата ред/колона намирам предварително крайната позиция на текущият елемент и го замествам в оригинлната матрица.

А това е формулата, която намира крайната позиция на даден елемент (сигурен съм, че има и не толкова идиотски начин):

UP :        (текущият ред + общия брой редове - (броя ходове % общия брой редове)) % общия брой редове

DOWN :  (текущият ред + общия брой редове (броя ходове % общия брой редове)) % общия брой редове

LEFT :    (текущата колона + общия брой колони - (броя ходове % общия брой колони)) % общия брой колони

RIGHT:    (текущата колона + общия брой колони + (броя ходове % общия брой колони)) % общия брой колони

 

Някой ако има други идеи за линейно решение ще се радвам да ги видя. :)))

 

 

2
27/05/2016 02:19:45
goshoan avatar goshoan 0 Точки

Единственото нещо, което не ми е все още ясно е как трябва да се rearrange-не тази матрица.... 

Не мога да разбера на какъв принцип е този swap. Пробвах да ги swap-вам стойност след стойност, но не става. Матрицата се пренарежда както беше в началото, но не мисля че това е правилният начин :D

0
zisov4eto avatar zisov4eto 19 Точки

Пъровото нещо, което се иска от теб в задачата е да размешаш числата в матрицата по дадени правила. След като вече матрицата е размешата (или не е) е време да започнеш да я подреждаш обратно.

Да кажем, че това е нашата размешана матрица.

1 3 5

9 8 7

2 4 6

Итерираш през нея по стандратният начин от ред 0 колона 0...3, ред 1 колона 0..3 и така и проверяваш дали елемнта за съответната позиция е развен на търсеният от теб елемент, който можеш да намериш по различни начини. Най-лесният вариант е с една променлива, която ще инкрементираш с 1 при всяко влизане във вътрешният цикъл.

В първият случай проверяваме дали 1 = елемента на ред 0, колона 0 (цифрата 1) и след като условието е вярно продължаваме с итерацията.

2 = елемента на ред 0 колона 1 (цифрата 3)? В случай на несъответсвие трябва да запалим още два цикъла, които итново ще итерират през нашата матрицата и тяхната мисия ще бъде да намерят стойноста която търсим, но ненамираме на точното позиция, а именно 2.

След като я намерим разменяме двете стойности, печатаме съответното съобщение и продължаваме да въртим по-горните два цикъла при, които бяхме стигнали до търсена стойност 2 като вече ще търсим 3.

Вече матрицата ни изглежда така:

1 2 5

9 8 7

3 4 6

 

Надявам се, че е станало една идея по-ясно какво се иска от задачата. Ако имаш още въпроси ще се радвам да отговоря. :)

1
goshoan avatar goshoan 0 Точки

Благодаря за обяснението :). Най-накрая разбрах къде са ми грешките !

0
pezereto avatar pezereto 15 Точки

Като стана дума, аз два пъти съм я разписвал върпосната задача и двата пъти един и същ проблем имах и това беше последния тест .Tова е кода от втория ми път --->  http://pastebin.com/aQgYpxNG някой може ли да ми обясни защо при последния тест ми отпечатва само до 170 ел при положение че са 10 000 :D

0
Можем ли да използваме бисквитки?
Ние използваме бисквитки и подобни технологии, за да предоставим нашите услуги. Можете да се съгласите с всички или част от тях.
Назад
Функционални
Използваме бисквитки и подобни технологии, за да предоставим нашите услуги. Използваме „сесийни“ бисквитки, за да Ви идентифицираме временно. Те се пазят само по време на активната употреба на услугите ни. След излизане от приложението, затваряне на браузъра или мобилното устройство, данните се трият. Използваме бисквитки, за да предоставим опцията „Запомни Ме“, която Ви позволява да използвате нашите услуги без да предоставяте потребителско име и парола. Допълнително е възможно да използваме бисквитки за да съхраняваме различни малки настройки, като избор на езика, позиции на менюта и персонализирано съдържание. Използваме бисквитки и за измерване на маркетинговите ни усилия.
Рекламни
Използваме бисквитки, за да измерваме маркетинг ефективността ни, броене на посещения, както и за проследяването дали дадено електронно писмо е било отворено.