Oberon space
General Category => Общий раздел => Тема начата: vlad от Май 13, 2012, 07:51:53 am
-
Итак, играем в судоку. Никаких архитектурных изысков. Чистой воды алгоритмика и разминка для мозга (зашоренного этими самыми изысками и прочей фигней типа скрещивания ежа с ужом). В интернет не подглядваем. Делимся впечатлениями, меряемся и т.д.
Дано поле 9 x 9 клеток. В клетках цифры 1 - 9. Некоторые клетки открыты (даны цифры), остальные нужно открыть (определить цифру). Цифры в каждой колонке и ряде не повторяются. Кроме того, поле поделено на квадраты 3 x 3 и цифры в квадрате тоже не повторяются. Wikipedia: http://en.wikipedia.org/wiki/Sudoku.
Пример. Ввод:
*******18
**9*3****
*7*******
8**1*****
*****73**
2********
*3****96*
1**48****
***2*****
Вывод:
342976518
689531427
571842639
853194276
914627385
267358194
438715962
126489753
795263841
Мой вариант решения аттачнут.
-
Моё решение:
StdCoder.Decode ..,1 ..3,....VuAVtBTtET9N9v9bOR7vPLPRRtP5fN0pN015Gm.sEP9Nbf
9TvMB1sEG4.1OGRtP51xL,...
jBaN..ta....BuETuPJ.V,Vh.c.Yj2U.UERakwaHhiYxhfhC6.Ey5EGGW5ws0oUMYVKYVHAYWY
YPQUwyj4IN56czf,LL48FA0GAyl,ivzOEcZVKY,D775MJBMA5Mizf,NKyXN,SokqqmumYuqoGb
z50,EmWkngz4YjdNzB6SJn2Wn5WF14FyPP,Sokq4BOOlnz1lPzzzHK2SaAoRbc2b63LunmzNDk
X4qqKaExhnRidJgghAvj,tPMZvEqT1Wrk8Ldgz42WXxhgtzVcYzzz790gTdcQTvRakd5k9SGJa
mFimF0mISG9qFy9s0SokqqmQeZZCvj,V.6Q3EmWkn.MzWFv4KqAVBv1jc8Hd8FtAZ77t6z9i,D
OMPXGhgnhgo,.Ts.GK2S4G,YVev2ZUSIYSIYhwYw5w5YemhiiRgExhnRi.gTt16S..uSzzTmWk
nE8Ux94E40jHIWH.kxXkWWLuKKrGKcyqtC5m5Ew.sPkLvzzHK2UI.216.0k,6.hs5H6xhs5HE7
E.0UY3t1SUt5t1SUtL06.GK9CJRipGqsyrSV4.FfzzDN5.,6..fc,E.GK.6.7,fc0YVyzzY3.0
EY2.fc1E.GK,6.0.kGGF.A.2U.E0kGe,B.5.0.kGu,1.0.7.9776.GK.2U.Yl0k8e0VdzzDNSo
kqqm0EoyKtoiZJC1fQ9PMbHnaKwKKmoiVZBBPOl13vP1fQ7HsyqtAB6.2...vP.E.Yv5g.Pk5A
.TE.6.....r9,6.op,E.2UY,E6qzzHK4qzzHK.E.EynzzH42en24.E..k2U.6N3U.2cyzzYB,2
uwzzYJ.2U.6Nzzzzzz6N,...6.lj.2swzzYBU,EEuzzHK.0U...........GKyzzzzjz12.0E2
E8nzzHa.EYnzzHK.6..........UY,yDH.d7zzDN3U.A,Q.YvvzzYJ..EajzzH42U.6Nz5,U.Y
BYrvzzYB.YmxzzYV..........EwnzzHKyzzztzQsJRlgTk25z9ic6oMSwWmD0kor3SwWWD0ko
X2isWmz,Xz28L,qsnjseWz,fz28L,qcBaU.TU0TlJ3V4bc0b.LQF.QF.gF.DCF3C06.zTFlzUv
9yFcTZxz98z5QTtD0xPbDSFt5,Mub,L2l5QFFsl7gUNg.oz1k3L2..Vh.0.wz3Zz1iDws5jcwX
.AxzU510kof0,sW6y5cQ3MXDbsn,8L,qcB8E5ck.di..2TIUy3uzjcwPT8Eziv3Lyi8Q2ge9ax
9ic62kss17w.MXVD3LQFFcl4k3Lyi8AsUWDVcj5U.Anrrz7IutBU6Bl3Zz9icIor1..6yLQFds
UlT0k33V9iiEQkyDVmJ.gj6Ql2KkAWXYkr4q0k3LJyDMxD.MRlzUxz.Zf.glIIe1ou9ii6QY2q
mIL.gwRJsEMJLYx3X,wVAK,Qkx3X7wVCS.gF625AyH.iseGl,fz2UBaU.1CMy8Q2wV20gWzjiI
wzp3WcBfzzzYxzp3Vzj0,EmiseWl5COczE,D.c3LQFVsU.LY10gF.LIAaMu8Q2isWWE.F81w3L
J6CMxb.QlpZW1qz7.PA3Zy.h4FAFhC,zTRlszf93zL6oz,6NzL2WyYl3LCdkeic90gk1E.63.k
3L3.PA,.52gEUJQl33W10QF.gF.,AT3C,yE0,O,.QF.gF.zDR3C0zTR62SmzzTmyDKAgcE.sW.
MX.SQWE.2U9iQ0VJl,HAoLMa.6zcj..2TP84lhzzzzzzo,yWf82.isuWkEGM91P,kaW,.Gl,,.
mM,..6z.6y.qM883M6Yu0UZH8....YT..Us11.bCkLQJV.k33V7YkK4KMH.E8..YF..YT.2T.P
2k26pkmVEGqTLAHEaXLSHEsbLMDEiPLmDEubLsHE2f5lRStD.7xSNQ.DA,FR.NQSlR.NBSlg.t
zSVj.dxR,w.NzSVw.twRFx.7xR,EEbLA9EGbr.WuwOP,muw8s00vwCv,GMx6UpH..tF,...
jBaN..kG....BuETuPJ.,b.2c,EAFW4.lj.IWERakwaHhiYxhfhi1hhYRCVuAVtB.,6Ib7A.4o
YQeoZgAxhb7J99SdfJHPNjvQCoruKu4qouqm8rtoedhAQeoxhmhgndFH9P9vQqorGqmmqt2ejJ
ioRCBuPR9RbnVy4ZvPN9P9fQbHc8rr0rm8LuaqmCbIhAqorG4YeZldKKuGrm8rtYeZFdKLqKKt
CbdJalQitRi7pBdONlna4Ks0rm8rt2.0..tT.777qT6EmwgVhhZN0hR.VM19s1Nc3Ns2HM2VM4
jM9Jc2ns55Mwxf,fQ.5Mpxf,ZR.Vc0tjg16HTPM7nyPEuaaxrUkJBvj,NfR19PyETCFAmTe5kd
yKqOrmgz,winxhgFmwVwgUCYVKYVH2ZVQUMpUkgU7QUlyj4oO960tDl3sIFvPjnyPEu.2.0...
.Q.ouobWMB.0EWU.2UYpuob0d47e,E.G4IKYc9U.2UY3U.6............6HTPM7ndWqrSbHx
hgpC,6.2..ky4.2.ty,9k4w,1E6E....Z.,6.Yc,Ewl5V.6N7aY3.2kyzzYZjyzzY3.2.2hyzz
Y,VuAV,kVU.AzCVY3.njH..2U...5SJLAvjeJ5AldDOnzzzDNF17vzf.79uMNDSFVL.0UdTBws
3ZS2Udr8gl3ZxE3Rgg.i56.TMV5.PAwdsUv9vyE4f.Csymy2yE5D.M35QTNb2C1wzpZxzjikzz
pZycJ,GKoy.7vzEmyzWGz,rLuXEzGuzLIsDsy0T2ur5XKx6Ny57n8UBigsrfThf1je9aR6zPQF
jDIF9bYgcBIGKoVBigsr9.6yF5SA2.HTFsl6.0koj0isWGz,Xz28L,qsnjse0z,fz28L,qcBaU
.TU0Tl2gMYgNKeE3RggzjcoTkxVD5xRnmyjkTEMhFz81kmqsm.,EknLI5EmnLi5EqnLG9Ewnbc
qjUCUsqjMCU6rjEC.,citfg1ckt9p1cmtP.dDT0k89E20Tyc.DOMMdpgxTjT5sd16S9Q.FP3dv
j1.7sIT9PcebQc3z,HS.kYuKugoTCsxzURK.GEauaKDxH5s3Ar0E.0E...7.qvETzBPkR6,T8Q
9fPOxoFBs.7vPRPNmwpzyzbrUF.0.hz....
jBaN..MF....BuETuPJ.V0VM.2F2a0U.2.76Ib7AjtIf9NTvOfPEHGcCHM.2UAxhbtG9fQRPNN
ndKKtOroCqmC52.Yz,YYY6,7S.bs2ncnCk5Cl7GFKzrKyiwTl,QeZBgmRgcpcjJirt,dt2bM4F
q,yk7cgzP9HLyLN,Cpm4KtcE1vMLn14hA2a1Ah7YZ1oVwDr0oeVZBvj,FcNZvPPnybE40rrCrt
AWJwUBIV9vD1qHCG80G38l94n,yE3Sl,yk0qwyGlj9E4KFyzO0CprmKvKaxrUkRgZZhgNzB6P5
vPNnz1ll5UY3VbNzB6OZvPjnz5E6CrrmKvYAvj,7fR19P0U.E,k44.,vzzDNNs.A.,6.1.JRGF
8TnN.Yc8U.2UYV...sNCrrm4QejZB0E.2U..vP.2.,EiTk0g,Tk.w,,U....76.2.wZ0.,EU7.
6N.2qyzzYZpyzzY3.2.2nyzzY,VuAV,kU6.AzCVY3.0..QsJRlgTl13yyC,Anrrz7IutBU6Bl1
3x9Sck1.8k,Ox2DJqbSJkzDIsjsV0D.M....3.Qkv3yFxVBS2Ql1Zx14z7Ii0glbTlH3x1Kz7I
i0gFPA,,y.3yWb805AT3C0KrIjsmrpVLp3nC..1...c.Ud1iIsjsV..4...E,.5Y.wVCSY.2U.
..L2.P2E.nLVHUpBJ.1QHNE0Mu5.zTFFsW980Tsc981b9xLQFFsW9TL3C0Kp3nydSJfCMW1z3r
xXLIs3U.6uXhzzzzHDg2UzjiczzpZxc7.GqzLL2yz8Em0p3LIqDMwb.QlJ3x1Kz7.P2ge6Ql2J
s62cE3x2yzzzz7icYTl3ZR.L2.P2k,nLVt17A3sz.tO.GqzL5U1ijYLVDglY.GyzLLoV0D.7vz
.wz33ycDVyzzz90ka0ToPMzzzzDsy0jDYl8U1ijkDeDYlwwzzzz1iDXG81w3LJ6WM,qsmGTjyp
hqJVnUEG6rLg5E8rLq5ECrLy5EIrbMqj.D.eTyaP,Guy6cvX0wcVhhZdZBRunS,36v56OLy.NP
t36QdhT2U.2.fe1...
--- end of encoding ---
Распаковать кодовые файлы в ББ 1.6 и выполнить команды:
!P307SudokuCmds.Load
0 0 0 0 0 0 0 1 8
0 0 9 0 3 0 0 0 0
0 7 0 0 0 0 0 0 0
8 0 0 1 0 0 0 0 0
0 0 0 0 0 7 3 0 0
2 0 0 0 0 0 0 0 0
0 3 0 0 0 0 9 6 0
1 0 0 4 8 0 0 0 0
0 0 0 2 0 0 0 0 0
!P307SudokuCmds.Solve
!P307SudokuCmds.Show
Даёт то же решение, что и у Влада.
Время исполнения: 2227 msec
P.S. Программу Влада не запустил, так как под Wine выдаёт fixme:heap:HeapSetInformation (nil) 1 (nil) 0 и зависает. Виртуалку стартовать нехоцца...
-
Ы, должен стоять i21sysIn.
http://oberoncore.ru/bbcc/subs/i21sys/start
-
Но вообще, задача NP-полна, так что решение у всех будет не полиномиальное. Следовательно меряться можно только константными множителями да коэффициентами при экспоненте :-)
-
Ну, я раньше не играл, даже правил не знал, программу писал, никуда не подглядывая :)
Сначала даже не был уверен, что игра предполагает "тупики" и откаты.
-
Ну, я раньше не играл, даже правил не знал, программу писал, никуда не подглядывая :)
Сначала даже не был уверен, что игра предполагает "тупики" и откаты.
Я тоже :-) Помню только что она NP-полна (поскольку NP-задачами интересовался).
-
Даёт то же решение, что и у Влада.
Время исполнения: 2227 msec
P.S. Программу Влада не запустил, так как под Wine выдаёт fixme:heap:HeapSetInformation (nil) 1 (nil) 0 и зависает. Виртуалку стартовать нехоцца...
У меня < секунды. Моя программа ждет stdin в процитированном формате - обязано работать, там ничего странного/нестандартного нет.
Твой вариант чуть позже посмотрю. И опубликую свой, если никто больше не присоединится.
-
Но вообще, задача NP-полна, так что решение у всех будет не полиномиальное. Следовательно меряться можно только константными множителями да коэффициентами при экспоненте :-)
Ну вообще совсем тупой перебор там не работает. Так что за коэффициенты можно еще побороться. Вариант Ильи еще не смотрел, но какой-то простор для творчества там есть, как мне кажется.
-
Но вообще, задача NP-полна, так что решение у всех будет не полиномиальное. Следовательно меряться можно только константными множителями да коэффициентами при экспоненте :-)
Ну вообще совсем тупой перебор там не работает. Так что за коэффициенты можно еще побороться. Вариант Ильи еще не смотрел, но какой-то простор для творчества там есть, как мне кажется.
Ну будет не тупой перебор, а тупой перебор с эвристиками (которые будут пытаться отрубить максимум вариантов как можно раньше) :-)
-
Вообще задачка (точнее метод решения) классическая. Настолько, что аж в журнале "практика функционального программирования" подробно разбиралась. Не судоку конечно, а на примере какой то другой задачи. На таких задачах функциональщики обычно любят показывать превосходство ФЯ над ИЯ :-)
В общем когда доеду до города (я сейчас в поезде), попробую что то накатать на каком-нибудь Go :-)
А от geniepro ждем решение на хаскелле :-)
-
Как раз размышлял над тем, как это будет выглядеть на ФП.
Там вместо модификации данных придётся использовать на каждый чих копирование, или я чего-то не понимаю в ФП :)
-
я чего-то не понимаю в ФП :)
Угу :-)
-
Ну, я раньше не играл, даже правил не знал, программу писал, никуда не подглядывая :)
Сначала даже не был уверен, что игра предполагает "тупики" и откаты.
Я тоже никогда... Но таки попала в мое поле зрения заветная газетка :) Причем там сразу был какой-то большой уровень сложности, так что чисто аналитически оно не решалось - нужно было разные варианты подбирать. Плюнул, и не сползая с дивана написал програмку (на нетбуке, в ФАРе и без отладичка) :)
-
Распаковать кодовые файлы в ББ 1.6 и выполнить команды:
!P307SudokuCmds.Load
0 0 0 0 0 0 0 1 8
0 0 9 0 3 0 0 0 0
0 7 0 0 0 0 0 0 0
8 0 0 1 0 0 0 0 0
0 0 0 0 0 7 3 0 0
2 0 0 0 0 0 0 0 0
0 3 0 0 0 0 9 6 0
1 0 0 4 8 0 0 0 0
0 0 0 2 0 0 0 0 0
Получаю "string expected" в логе. Что я делаю не так?
-
А от geniepro ждем решение на хаскелле :-)
И еще O-7 не забудте ;) Динамические массивы не нужны ;)
-
Команды прямо скопированы, как есть?
Т.е. после команды Load должны быть цифры. Она их введёт.
Ещё чтобы выделенного текста нигде не было, иначе будет вводить оттуда.
-
На тему "Sudoku Solver" на хаскельном сайте целая страничка есть:
http://www.haskell.org/haskellwiki/Sudoku
И вапще: https://www.google.com/search?q=sudoku+solutions+on+haskell
Ну, будет время, подумаю над этой задачкой, а то я уже забывать хаскелл стал... :(
-
На тему "Sudoku Solver" на хаскельном сайте целая страничка есть:
http://www.haskell.org/haskellwiki/Sudoku
И вапще: https://www.google.com/search?q=sudoku+solutions+on+haskell
Ну, будет время, подумаю над этой задачкой, а то я уже забывать хаскелл стал... :(
Я ж говорю - функцианальщиков хлебом не корми, дай только такую задачку решить и зачмырить императивщиков :-)
-
Работает за dt=1.66 секунды. Ответ выдаёт другой, но вроде тоже правильный:
302 546 718
419 730 256
675 812 034
853 104 627
041 627 385
267 358 401
534 071 962
126 483 570
780 265 143
Прикладываю исходник на C#.
-
Если мне склероз не изменяет, правильно составленные первоначальные данные для судоку (не менее 17ти чисел) должны приводить к единственному решению.
-
А стоп, в моей программе ошибка. В ответе числа должны быть 1..9, а у меня 0..8. Сейчас переделаю.
-
Переделал. Теперь ответ такой же как у всех. Выполняется за 0.16 секунды.
Прилагаю исходник на C#
-
Совсем чуток оптимизировал. На i7 3770K выполняется за 0.107 секунды.
-
Сергей, а какой смысл писать unsafe-программы на сишарпе?
Не лучше ли сразу на Сях или С++?
-
Сергей, а какой смысл писать unsafe-программы на сишарпе?
Не лучше ли сразу на Сях или С++?
А какой будет, для Сергея профит с написания их на Сях или на С++? С .net оно интерфейситься будет хреново, грамматика сложнее, семантика тем более, а высокоуровневые возможности Си и, тем более, С++ Сергей все равно не использует в unsafe программах.
-
Сергей, а какой смысл писать unsafe-программы на сишарпе?
Чтобы работало в 20 раз быстрее чем у Ермакова.
Не лучше ли сразу на Сях или С++?
Так я фактически на Си и написал. Только скомпилировал компилятором C#.
Ансэйфный C# это и есть тот же Си, но только чуток побезопаснее, помодульнее, да и просто по приличнее, к тому же компилируется на несколько порядков быстрее.
-
Сергей, а какой смысл писать unsafe-программы на сишарпе?
Чтобы работало в 20 раз быстрее чем у Ермакова.
Не лучше ли сразу на Сях или С++?
Так я фактически на Си и написал. Только скомпилировал компилятором C#.
Ансэйфный C# это и есть тот же Си, но только чуток побезопаснее, помодульнее, да и просто по приличнее, к тому же компилируется на несколько порядков быстрее.
Или писал на паскале, или на модуле :-) Есть уйма языков с близкой семантикой. Вообще, ансейфный C# больше всего похож пожалуй на модулу-2 а не на Си. А фигурные там скобочки или же begin/end роли не играет.
-
Чтобы работало в 20 раз быстрее чем у Ермакова.
Сергей Юрьевич из-за работы в телекоммуникационной сфере стал заниматься мерянием просто на каждом шагу :)
Во-первых, мне бы его i7. У меня ноут с Athlon II X2 P340.
Во-вторых, когда откроем исходники, будет понятно, почему моя программа не конкурент Сергею Юрьевичу по длине..... по быстродействию... :)
-
Совсем чуток оптимизировал. На i7 3770K выполняется за 0.107 секунды.
Гм. У меня эта программа ничего не запрашивает и выдает странное:
020000000
000000000
000000000
000000000
000000000
000000000
000000000
000000000
000000000
-
Сергей Юрьевич из-за работы в телекоммуникационной сфере стал заниматься мерянием просто на каждом шагу :)
Немного не так. Маниакальная привычка писать только быстрые программы у меня зародилась на почве жутко тормозных игр Альфа Центавра и Цивилизация 3. В начале игры (или на маленькой карте) они работают быстро, а потом, когда городов и юнитов становится много они начинают ужасно-ужасно-ужасно тормозить :'( :'( :'(. Кстати даже i7 3770K разогнанный в турбо бусте до 4200MHz не спасёт если в Цивилизаци3 взять огромную карту 256*256 с порядка 250 городами -- т о р м о з и т в с ё р а в н о. Сиду Мейеру за Цивилизацию надо Нобелевскую премию дать, но за тормозную реализацию тот час же её лишить (с позором).
-
Гм. У меня эта программа ничего не запрашивает и выдает странное
Начальные условия в самом исходнике, поэтому не спрашивает. Выдает странное -- чем компилировал?
-
Выдает странное -- чем компилировал?
Видимо, компилятором C# из Mono...
-
Совсем чуток оптимизировал. На i7 3770K выполняется за 0.107 секунды.
Добавил подсчет времени (полный, включая ввод/вывод). На моей машине ~0.1 с. И там еще можно пооптимизить ;)
-
Гм. У меня эта программа ничего не запрашивает и выдает странное
Начальные условия в самом исходнике, поэтому не спрашивает. Выдает странное -- чем компилировал?
Компилировал mono'вским компилятором. Под линухом 32 бита.
Сейчас на макось поставил mono, собрал компилятором dmcs, и заработало. Видимо вся штука в том, что макось 64битная (и проц соответственно). То есть твоя программа просто не работает под 32 бита.
А скорость работы такая:
dt=0.273248
...
real 0m0.337s
user 0m0.323s
sys 0m0.010s
Ну, то есть примерно 0.3 секунды. Решение влада на этой же машине - 0.15 секунды. Где-то в два раза быстрее (при том, что оно и на линуксе 32битном работает ;-) )
-
Команды прямо скопированы, как есть?
Т.е. после команды Load должны быть цифры. Она их введёт.
Ещё чтобы выделенного текста нигде не было, иначе будет вводить оттуда.
Заработало! Как померять время - не знаю. Вообще, если соревноваться в оптимизации, то нужно, чтобы оно могло сразу набор принимать (stdin или файл).
-
Как померять время - не знаю.
Нашел. 905ms для "!P307SudokuCmds.Solve".
-
Как померять время - не знаю.
Нашел. 905ms для "!P307SudokuCmds.Solve".
А что эта криптострока означает?
-
А что эта криптострока означает?
Дык, коммандер блэкбоксовский :) Оно там в три этапа сделано: загрузка, решение, и печать.
P.S. Кстати, оно у меня трапнулось (похоже по ассерту) в какой-то момент - когда чего-то выделено было, а я попытался "загрузку" запустить.
-
А что эта криптострока означает?
Дык, коммандер блэкбоксовский :) Оно там в три этапа сделано: загрузка, решение, и печать.
P.S. Кстати, оно у меня трапнулось (похоже по ассерту) в какой-то момент - когда чего-то выделено было, а я попытался "загрузку" запустить.
А как скорость измерялась?
-
На моей тачке решение от vlad тоже работает примерно в два раза быстрее решения от Сергея.
0.312 против 0.68
-
Компилировал mono'вским компилятором
Попробовал gmcs. Компилирует не правильно. Как с ним бороться не знаю. Если компилировать в MS VS 2008, а потом запускать под Mono, то нормально работает.
-
Компилировал mono'вским компилятором
Попробовал gmcs. Компилирует не правильно. Как с ним бороться не знаю. Если компилировать в MS VS 2008, а потом запускать под Mono, то нормально работает.
На маке со свежеустановленной моно - все правильно. Хоть dmcs, хоть gmcs.
$ gmcs --version
Mono C# compiler version 2.10.9.0
-
Mono C# compiler version 2.10.9.0
У меня Mono JIT compiler version 2.6.7 (Debian 2.6.7-5). Значит скорее всего дело в версии.
-
Mono C# compiler version 2.10.9.0
У меня Mono JIT compiler version 2.6.7 (Debian 2.6.7-5). Значит скорее всего дело в версии.
Проверил на сервере (на котором сий форум крутится) - результаты такие:
1) Программа собранная на макоси (с помощью моно) там работает нормально.
2) Программа собранная на самом серваке - там не работает.
3) Программа там работает быстро - 0.15 секунды.
Версия компилятора там такая:
# gmcs --version
Mono C# compiler version 2.6.7.0
-
На моей тачке решение от vlad тоже работает примерно в два раза быстрее решения от Сергея.
0.312 против 0.68
Э-э-э, от рекурсии что ли попробовать избавиться?.. :) :) :) Как раз наверное в два раза и ускорится...
-
На моей тачке решение от vlad тоже работает примерно в два раза быстрее решения от Сергея.
0.312 против 0.68
Э-э-э, от рекурсии что ли попробовать избавиться?.. :) :) :) Как раз наверное в два раза и ускорится...
У меня есть рекурсия ;) И вообще код без изысков и каких-то мощных абстракций, но и без явной оптимизации. Вполне такой "каждодневный". Я его оставлю такой как есть, пока все кто хотел решения не предоставят. Потом можно будет пооптимизировать.
-
Рекурсию оставил, но врукопашную раскрыл цикл for (int value = 1; value < 10; value++) на девять ифов. Дотнетный компилятор этого сам не делает. Код, конечно, стал индусским, но работать стало в два раза быстрее -- 0.0628 секунды на i7 2600K (без оверклокинга) под Windows 7. Встроил высокоточный таймер (точность порядка 1 микросекунды). Ещё при старте печатаю разрядность используемого дотнетного рантайма.
Use 64 bit runtime
Initialization...
Source:
000000018
009030000
070000000
800100000
000007300
200000000
030000960
100480000
000200000
Result:
dt = 0.0627798907917168 seconds
342976518
689531427
571842639
853194276
914627385
267358194
438715962
126489753
795263841
Press 'Enter' to exit
Прикладываю дотнетный экзешник и зазипованный исходник
-
Поскольку время может зависеть от входных данных, то я сгенерировал 12 вариантов (http://kjell.haxx.se/sudoku/).
Видно, что моя программа хорошо "висит" на одном из них.
Итоговое время ~16 секунд.
-
Я допустил ошибку - запускал программу Сергея из студии. Если запускать не из студии, то работает значительно быстрее.
Целевая платформа .NET 2.0.
Вот уточненные данные.
Влад: 0.312
Сергей, старый вариант: 0.390
Сергей, индусский вариант: 0.187
-
Я допустил ошибку - запускал программу Сергея из студии. Если запускать не из студии, то работает значительно быстрее.
Целевая платформа .NET 2.0.
Вот уточненные данные.
Влад: 0.312
Сергей, старый вариант: 0.390
Сергей, индусский вариант: 0.187
Я тут на Go набыдлокодил. Оно пока кривое и глючное, и вообще без оптимизций в плане программинга, то есть без низкоуровневых штучек, не используя unsafe фичи. Получил такое:
$ time ./go
Game finished
3 4 2 9 7 6 5 1 8
6 8 9 5 3 1 4 2 7
5 7 1 8 4 2 6 3 9
8 5 3 1 9 4 2 7 6
9 1 4 6 2 7 3 8 5
2 6 7 3 5 8 1 9 4
4 3 8 7 1 5 9 6 2
1 2 6 4 8 9 7 5 3
7 9 5 2 6 3 8 4 1
real 0m0.081s
user 0m0.076s
sys 0m0.003s
Это на том же макбуке. С учетом того, что go'шный референсный компилятор оптимизирует крайне хреново (на порядок хуже чем gccgo) а у меня алгоритм сейчас найдя решение даже не прекращает работать, я думаю что у меня где-то ошибка, вследствие которой алгоритм работает быстрее и случайно так оказалось, что на этих входных данных он работает правильно.
-
А если сделать выход по окончанию решения, то тайминги такие:
real 0m0.068s
user 0m0.063s
sys 0m0.003s
-
Зато на последнем из новых игровых полей у влада такой результат:
real 0m0.021s
user 0m0.018s
sys 0m0.002s
А у меня такой:
real 0m2.295s
user 0m2.286s
sys 0m0.008s
Но несмотря на это мое чудовище работает тут все равно корректно, что очень странно.
-
Допилил решение на Go до состояния когда оно может на вход принимать задачи в стандартном формате (см. в каком формате владовы 12ть задач). Программа работает полностью аналогично владовой (на stdin принимает задачи, на stdout выдает решения), только в конце оно не печатает сколько времени заняло. Так что советую пользоваться утилитой time.
Прикладываю исполняемый файл собранный под макось (mac os 10.7 lion 64 bit). Ибо других осей под рукой просто нет :-)
12ть этих задачек владова программа прожевывает за 19 секунд, моя программа - за 6 секунд. Решения идентичные.
-
Тоже допилил на чтение файла in.txt
На моём компе:
программа Влада -- 14 секунд
моя (индусская) программа -- 8.43 секунды
-
Тоже допилил на чтение файла in.txt
На моём компе:
программа Влада -- 14 секунд
моя (индусская) программа -- 8.43 секунды
Откомпилированная тобой программа на меня страшно ругается при запуске
$ mono ./Sudoku.exe < tasks.txt
Unhandled Exception: System.TypeInitializationException: An exception was thrown by the type initializer for Unix_librt ---> System.DllNotFoundException: /lib/librt.so.1
at (wrapper managed-to-native) Sudoku.Program/Clock/Unix_librt:clock_gettime (int,Sudoku.Program/Clock/Unix_librt/Time&)
at Sudoku.Program+Clock+Unix_librt.GetSeconds () [0x00000] in <filename unknown>:0
at Sudoku.Program+Clock+Unix_librt..cctor () [0x00000] in <filename unknown>:0
--- End of inner exception stack trace ---
at Sudoku.Program+Clock.GetSeconds () [0x00000] in <filename unknown>:0
at Sudoku.Program.Main (System.String[] args) [0x00000] in <filename unknown>:0
[ERROR] FATAL UNHANDLED EXCEPTION: System.TypeInitializationException: An exception was thrown by the type initializer for Unix_librt ---> System.DllNotFoundException: /lib/librt.so.1
at (wrapper managed-to-native) Sudoku.Program/Clock/Unix_librt:clock_gettime (int,Sudoku.Program/Clock/Unix_librt/Time&)
at Sudoku.Program+Clock+Unix_librt.GetSeconds () [0x00000] in <filename unknown>:0
at Sudoku.Program+Clock+Unix_librt..cctor () [0x00000] in <filename unknown>:0
--- End of inner exception stack trace ---
at Sudoku.Program+Clock.GetSeconds () [0x00000] in <filename unknown>:0
at Sudoku.Program.Main (System.String[] args) [0x00000] in <filename unknown>:0
-
Откомипилированная мной руками - тоже самое.
У меня ощущение складывается, что нужно выпилить нафиг измерялку времени из программы.
-
Угу. Выпилил измерялку - заработало.
Пара пожеланий:
1) Очень хочется чтобы программа хавала из stdin столько задач сколько там есть, а не только первую. И последовательно их решала. Меряем время за всю серию задач разом. Можно внешней тулзой.
2) Выдаем решение сплошным потоком. Пример вывода:
571248936
482396517
936751284
265437891
347189652
198562743
823615479
654973128
719824365
172869543
694531278
538742169
345186792
721953486
986274315
813627954
459318627
267495831
Это удобно тем, что можно автоматически находить различия в решениях разных программ (тупо diff'ом).
-
Мдя. А под макось только 32битная моно есть. Точнее есть и 64битная, но ее нужно руками компилировать.
Пойду домой, попробую все то же позапускать на 32битном линуксе. Там будут 32битными все, так что все честно.
-
Таки шо, уже исходниками начинаем меряться?
-
Таки шо, уже исходниками начинаем меряться?
Не, еще рано, еще желающие есть предоставить решение.
-
1) Очень хочется чтобы программа хавала из stdin столько задач сколько там есть, а не только первую.
А в каком виде получение исходных данных должно быть? Очень желательно, чтобы алгоритм получения задачи был у всех одинаковый. Чтобы мерять только сам процесс решения головоломки.
-
1) Очень хочется чтобы программа хавала из stdin столько задач сколько там есть, а не только первую.
А в каком виде получение исходных данных должно быть? Очень желательно, чтобы алгоритм получения задачи был у всех одинаковый. Чтобы мерять только сам процесс решения головоломки.
В том виде в котором выдает сайт http://kjell.haxx.se/sudoku/
То есть в таком:
57.!...!...
.82!...!...
...!..1!..4
---!---!---
..5!...!8..
3..!..9!...
...!...!7..
---!---!---
..3!...!..9
...!.7.!...
.1.!82.!...
...!.6.!...
..4!.31!...
5..!..2!..9
---!---!---
...!...!...
7..!9..!...
..6!...!31.
---!---!---
.13!...!...
...!...!..7
...!4..!8..
...!..3!6..
.5.!...!...
84.!.1.!...
---!---!---
...!1.7!...
...!...!..4
..2!...!.85
---!---!---
...!...!...
...!58.!..1
..6!...!7..
.1.!...!...
...!.2.!..7
.85!...!..9
---!---!---
...!...!.5.
...!.39!...
...!...!814
---!---!---
7..!...!...
...!8.5!...
3..!...!.6.
...!..7!4..
.8.!.1.!...
...!.62!...
---!---!---
...!9..!5..
2..!...!...
1.6!...!...
---!---!---
.5.!8..!...
...!...!.67
..1!...!..2
...!9..!...
..7!...!2..
.9.!8..!...
---!---!---
38.!...!...
...!...!4..
...!..2!7.5
---!---!---
...!1..!.38
..5!.4.!...
...!...!.9.
...!.2.!5..
...!...!.9.
.4.!1..!...
---!---!---
3..!...!2..
...!6..!.8.
5..!..9!...
---!---!---
...!.35!...
.1.!...!.4.
.6.!.8.!...
...!7..!...
..4!...!..5
...!.6.!...
---!---!---
.7.!...!...
...!.5.!..9
.1.!2..!.3.
---!---!---
..9!..4!...
...!6..!71.
.25!...!...
8.3!...!...
...!5.6!9..
...!...!7..
---!---!---
.5.!..9!..3
...!.1.!.4.
...!...!..8
---!---!---
...!.8.!...
49.!...!5..
...!...!..1
.1.!...!62.
...!3..!8..
..7!.5.!...
---!---!---
...!...!...
6..!..8!...
..5!...!.47
---!---!---
...!...!...
...!.71!..9
38.!...!...
...!...!.69
5..!.74!...
...!.5.!..1
---!---!---
...!...!4..
..1!...!...
.83!6..!...
---!---!---
4..!...!.2.
...!1..!.3.
.7.!...!...
3.7!...!2..
...!8.1!..6
2..!...!...
---!---!---
...!73.!5..
...!...!...
.8.!...!..9
---!---!---
...!6.9!..4
...!...!.3.
...!..8!...
Пока у всех алгоритмы тормозные настолько, что производительность IO роли не играет.
-
Таки шо, уже исходниками начинаем меряться?
У тебя там цикл дейкстры что ли?
-
Таки шо, уже исходниками начинаем меряться?
У тебя там цикл дейкстры что ли?
У меня ощущение, что Илья когда настанет время открывать исходники, с аццким хохотом покажет нам слип в своем коде. После удаления оного слипа программа ускорится в 1000 раз.
PS. А вообще мало ли. Вдруг у него там строится множество всех возможных (доступных) комбинаций, а затем идет просто поиск нужной. Тогда тормоз только при запуске будет, а в дальнейшем работать будет очень-очень быстро.
-
Вот бинарь версии на Go под линукс.
-
Убрал таймер неработающий под макосью. Сделал вывод ответа как у Влада. Ещё самую малость удалось соптимизировать.
На оверклоченном до 4200 МГц i7 3770K на том файле in.txt получилось:
программа Влада -- 12.26 секунд,
моя программа -- 6.70 секунд.
Ещё сильнее уже не оптимизируется. Надо придумывать какую-то совсем другую эвристику.
-
Убрал таймер неработающий под макосью. Сделал вывод ответа как у Влада. Ещё самую малость удалось соптимизировать.
На оверклоченном до 4200 МГц i7 3770K на том файле in.txt получилось:
программа Влада -- 12.26 секунд,
моя программа -- 6.70 секунд.
Ещё сильнее уже не оптимизируется. Надо придумывать какую-то совсем другую эвристику.
Погонял на 32битном линуксе то что ты сейчас прислал и то что влад присылал а также свою прогу гошную. Итого для пакета из 12ти задач:
Приложение влада:
real 0m24.645s
user 0m24.566s
sys 0m0.056s
Твое приложение:
real 0m20.002s
user 0m19.945s
sys 0m0.036s
Мое приложение:
real 0m10.847s
user 0m10.757s
sys 0m0.064s
Если что, процессор такой:
cpu family : 6
model : 15
model name : Intel(R) Core(TM)2 Duo CPU T7250 @ 2.00GHz
stepping : 13
cpu MHz : 800.000
cache size : 2048 KB
PS. Подозреваю, что программа Влада у тебя работает медленно просто потому, что собрана под 32 бита.
-
Ну раз пошла такая пьянка... Ускорил в ~3 раза. Код не оптимизил, поменял алгоритм чуть-чуть.
-
Убрал таймер неработающий под макосью.
Сергей, попробуй System.Diagnostics.Stopwatch под линуксом. Под виндой он работает так же, как твой таймер с высоким разрешением. Я под линуксом не могу проверить, во всяком случае, малой кровью.
-
ууууу, садюги
тоже попробовать что-ли
так как сейчас реализацией различных списков занимаюсь, то на активном обероне и с использованием списков, но тормозить будет... (((
-
Ну раз пошла такая пьянка... Ускорил в ~3 раза. Код не оптимизил, поменял алгоритм чуть-чуть.
Пока не успел уйти на работу померил на домашнем компе:
новая программа Влада -- 3.59 сек
моя индусская программа -- 6.70 сек
Я так понял, на текущий момент программы vlad и valexey на одинаковых машинах будут работать примерно с одинаковой скоростью, а моя будет в ~2 раза медленнее.
-
ууууу, садюги
тоже попробовать что-ли
так как сейчас реализацией различных списков занимаюсь, то на активном обероне и с использованием списков, но тормозить будет... (((
Оу! Да у тебя будет практически решение на хаскелле! :-)
-
Сергей, попробуй System.Diagnostics.Stopwatch под линуксом.
Попробовал, работает.
Ломаю голову над новой эвристикой... Подумалось, что если сортировать пустые клетки по признаку допустимых вариантов и сначала рекурсивиться в те где свободных вариантов меньше всего, то дерево будет менее ветвистое и как бы быстрее обойдётся. Оказалось нет. Сортируй не сортируй (или даже сортируй наоборот), а количество рекурсивных вызовов остаётся постоянным: 701 миллион на том тестовом файле.
-
Ломаю голову над новой эвристикой... Подумалось, что если сортировать пустые клетки по признаку допустимых вариантов и сначала рекурсивиться в те где свободных вариантов меньше всего, то дерево будет менее ветвистое и как бы быстрее обойдётся. Оказалось нет. Сортируй не сортируй (или даже сортируй наоборот), а количество рекурсивных вызовов остаётся постоянным: 701 миллион на том тестовом файле.
БЛИН!!! БЛИН!!! БЛИН!!! Я опять совершил свою любимую ошибку! Написав процедуру нигде её не вызвал и недоумеваю почему лучше не стало! А раз лучше все равно не стало выдал "военную тайну" самого быстрого алгоритма :-\ :-\ :-\
Короче теперь программа летает со скоростью света. Общее количество рекурсивных вызовов сократилось с 701M до 375K.
Все тесты из in.txt расщёлкиваются за 0.175 секунды.
-
Ломаю голову над новой эвристикой... Подумалось, что если сортировать пустые клетки по признаку допустимых вариантов и сначала рекурсивиться в те где свободных вариантов меньше всего, то дерево будет менее ветвистое и как бы быстрее обойдётся. Оказалось нет. Сортируй не сортируй (или даже сортируй наоборот), а количество рекурсивных вызовов остаётся постоянным: 701 миллион на том тестовом файле.
БЛИН!!! БЛИН!!! БЛИН!!! Я опять совершил свою любимую ошибку! Написав процедуру нигде её не вызвал и недоумеваю почему лучше не стало! А раз лучше все равно не стало выдал "военную тайну" самого быстрого алгоритма :-\ :-\ :-\
Короче теперь программа летает со скоростью света. Общее количество рекурсивных вызовов сократилось с 701M до 375K.
Все тесты из in.txt расщёлкиваются за 0.175 секунды.
Это не военная тайна - у меня оно так и работало изначально (убрав эту эвристику я получил время работы приложения 20 минут на тестовом пакете задач, то есть примерно в 200 раз медленней). Низкоуровневыми оптимизациями заниматься пока не интересно, поэтому я буду совершенствовать именно алгоритм а не реализацию.
-
Изменил алгоритм. Что сделал - военная тайна :) (правда исходник прилагаю).
Стало 0.047 секунды на весь in.txt.
Фактически это уже похоже на время ввода-вывода.
Кстати, всего 248K рекурсивных вызовов.
-
Стало 0.047 секунды на весь in.txt.
Фактически это уже похоже на время ввода-вывода.
На вычисления расходуется 0.022 секунды, и 0.025 секунды уходят на ввод-вывод.
-
накропал на МАМПСе (MUMPS)
чтение и запись в файл
где то 0.01-0.04 сек
на Пентиуме Д 3Ггц 512М
-
накропал на МАМПСе (MUMPS)
чтение и запись в файл
где то 0.01-0.04 сек
на Пентиуме Д 3Ггц 512М
Афигеть.
-
не совсем афигеть.
это на исходной задаче.
а на файле in.txt не всё ok :(
0.39 сек , но некоторые не решаются (пока), надо кумекать.
А алгоритм без перебора и рекурсий.(пока) :)
-
А раз лучше все равно не стало выдал "военную тайну" самого быстрого алгоритма :-\ :-\ :-\
Военной тайны не получилось - у меня такое же улучшение было сделано. Предварительная сортировка по количеству возможных вариантов.
-
На вычисления расходуется 0.022 секунды, и 0.025 секунды уходят на ввод-вывод.
Да, похоже на предел :) Новые варианты имеет смысл генерить?
-
Новые варианты имеет смысл генерить?
Наверное нет.
-
Новые варианты имеет смысл генерить?
Наверное нет.
А мне кажется, что да. Потому как начальные условия сильно могут различаться по сложности.
-
А я решил с обычного обхода дерева делать - и поскольку время меня устроило - никаких эвристик вводить не стал :)
-
А я решил с обычного обхода дерева делать - и поскольку время меня устроило - никаких эвристик вводить не стал :)
Гм. Я сильно сомневаюсь что на всех возможных (даже корректных, то есть у которых ровно одно решение) начальных условиях такое решение будет работать меньше секунды.
-
На будущее, чтоб не затерялось в исходниках, удачный алгоритм одним предложением выражается так:
В дереве поиска следующий шаг рекурсии делать в ветви с наименьшим количеством подветвей.
Эвристика а-ля "жадный алгоритм".
Такой алгоритм фатально обломится если правильный ответ каждый раз (на каждом шаге рекурсии) будет находиться в ветви с наибольшим количеством подветвей, правда такие случаи встречаются редко.
-
Гм. Я сильно сомневаюсь что на всех возможных (даже корректных, то есть у которых ровно одно решение) начальных условиях такое решение будет работать меньше секунды.
Ну дык я и приводил время - 2с.
Для NP-полной задачи чем плохо, если учесть, что решал я раньше, чем все остальные участники, кроме Влада? :)
-
Гм. Я сильно сомневаюсь что на всех возможных (даже корректных, то есть у которых ровно одно решение) начальных условиях такое решение будет работать меньше секунды.
Ну дык я и приводил время - 2с.
Для NP-полной задачи чем плохо, если учесть, что решал я раньше, чем все остальные участники, кроме Влада? :)
В текущей постановке задача решается за O(1) :-) Но это мелочи.
Я к тому, что в случае разных начальных условий за 2 секунды ты вполне можешь вылезти. Ты пробовал свое решение погонять на других начальных условиях? Ну, например на том пакете из 12ти задач.
-
Понятно дело, что могу вылезти.. :)
Вот попробовал:
2215 msec
847 msec
2735 msec
3456 msec
9265 msec
681 msec
19656 msec
...
Ну, у меня программа нерекурсивная (откат выполняется прямо на рабочем поле), поэтому к нему уже никакой эвристики не прикрутишь :)
-
На будущее, чтоб не затерялось в исходниках, удачный алгоритм одним предложением выражается так:
В дереве поиска следующий шаг рекурсии делать в ветви с наименьшим количеством подветвей.
Да, такой подход хорошо работает (другие эвристики мне дали ускорение только в ~2 раза).
Аттачнутый вариант работает за ~0.09с. Ввод/вывод отдельно лень мерять.
-
На самом деле прикольно попрактиковались. Ускорили первоначальные варианты на два порядка. Еще есть желающие или можно исходники публиковать?
-
На самом деле прикольно попрактиковались. Ускорили первоначальные варианты на два порядка. Еще есть желающие или можно исходники публиковать?
Ну, я наверно на досуге свое решение еще попилю, но это не должно мешать публикации исходников :-) Я достаточно ленив чтобы не смотреть в ваши решения до тех пор пока не допилю свое :-)
-
На самом деле прикольно попрактиковались. Ускорили первоначальные варианты на два порядка. Еще есть желающие или можно исходники публиковать?
Погодите, погодите. Тут 1С вариант допиливается. :)
p.s. Я нашел косяк
-
На самом деле прикольно попрактиковались. Ускорили первоначальные варианты на два порядка. Еще есть желающие или можно исходники публиковать?
Погодите, погодите. Тут 1С вариант допиливается. :)
p.s. Я нашел косяк
Вот он - истинный хоррор! И путь живые позавидуют мертвым... :-)
-
В общем я выбрал неудачную стратегию. Закодил первое, что пришло в голову и не угадал :) Время решения растет экспоненциально сложности судоку.
Хотя иногда попадаются и быстро решаемые сложные. На средней сложности откатов почти нет, а вот на вариантах vlad'a уходит в глубокий перебор. Время с большой точностью не мерил, но средние решаются меньше секунды (так как 1С интерпретатор, то более точно мерить смысла нет)
Почему вариант vlad'a не решается я понял, но с данной стратегией победить не получилось. Поэтому прикладываю пока этот первый вариант, и подумаю как сделать иначе.
-
В общем я выбрал неудачную стратегию. Закодил первое, что пришло в голову и не угадал :) Время решения растет экспоненциально сложности судоку.
Хотя иногда попадаются и быстро решаемые сложные. На средней сложности откатов почти нет, а вот на вариантах vlad'a уходит в глубокий перебор. Время с большой точностью не мерил, но средние решаются меньше секунды (так как 1С интерпретатор, то более точно мерить смысла нет)
Почему вариант vlad'a не решается я понял, но с данной стратегией победить не получилось. Поэтому прикладываю пока этот первый вариант, и подумаю как сделать иначе.
Эмм.. А можно этого бинарного шайтана в текстовый вид перевести и запостить тут? А то под линуксом и макосью сложновато с 1С.
-
Вот исходник
-
прикладываю пока этот первый вариант
Да кстати, если кто скачал обработку, там на форме в таблице по умолчанию вариант vlad'a :)
Не спешите давить на кнопку. Решения придется долго ждать.
Прервать можно сочетанием Ctrl+Break
-
Вот исходник
Вот ведь.. Только запостил и тут же нашел ошибку в коде.
Прилагаю поправленное
-
Генератор судоку для Excel
http://www.podzamkom.ru/games/gen_sudoku/tabl_sudoku.htm (http://www.podzamkom.ru/games/gen_sudoku/tabl_sudoku.htm)
-
Вот исходник
Круто! Я даже и не думал, что у нас будут столь экзотичные решения как 1С :)
-
Если сегодня смогу выделить время, то закодю вторую версию. Моя ошибка была в том, что я для позиций ищу числа, а нужно наоборот. Т.е. мой алгоритм нужно наизнанку вывернуть.
Кстати я замерил время на решение варианта из первого сообщения - 7,5 минут (5 минут если удалить в байткоде указатели номеров строк исходного кода)
-
Кстати, при выполнении вычислений длящихся менее 0.1 секунды разогнанный 3770K с настройками энергосбережения не считает нужным переключиться в турбо буст (на 4200 МГц), делает их на частоте холостого хода 1600 МГц. В результате показатели оказываются хуже, чем уже опубликованные. Отключать энергосбережение было в лом :)
-
Решил прикинуть масштаб скорости 1С по отношению к КП ;D
код КП:
MODULE MyTime;
IMPORT Log;
PROCEDURE Do*;
VAR
a: ARRAY 100000 OF LONGINT;
i, j: LONGINT;
BEGIN
FOR j := 1 TO 100 DO
FOR i := 0 TO LEN(a) - 1 DO
a[i] := 123;
END;
END;
END Do;
BEGIN
END MyTime.Do
125 msec
код 1С:
Перем MSScriptControl;
Процедура КнопкаВыполнитьНажатие(Кнопка)
Массив = Новый Массив(100000);
Момент = ПолучитьВремяВМиллисекундах();
Для Счетчик = 1 По 100 Цикл
Для Индекс = 0 По Массив.Количество() - 1 Цикл
Массив[Индекс] = 123;
КонецЦикла;
КонецЦикла;
Сообщить(ПолучитьВремяВМиллисекундах() - Момент);
КонецПроцедуры
Функция ПолучитьВремяВМиллисекундах()
Возврат MSScriptControl.Eval("new Date().getTime()");
КонецФункции
MSScriptControl = Новый COMОбъект("MSScriptControl.ScriptControl");
MSScriptControl.Language = "javascript";
71 469 msec
-
Решил прикинуть масштаб скорости 1С по отношению к КП
А Массив.Количество() -- это константа времени компиляции или функция? Похожа на функцию. Попробуй заменить на константу.
-
Константа.
зы Я пробовал и без массивов просто присвоение переменной делать. Отношение все равно примерно 500:1
-
Хотя нет, не константа... туплю. Но вычисляется один раз при входе в цикл (ну как обычно в FOR).
К тому же массив в 1С знает свою длину. Т.е. этот метод дешевый и на результат очень слабо влияет.
-
Массивы в 1С основаны на коллекциях, поэтому совсем не удивителен результат.
-
Массивы в 1С основаны на коллекциях, поэтому совсем не удивителен результат.
Не понял этого высказывания. Массив это коллекция везде, хоть в асме. А вот коллекция не обязательно массив.
Коллекция это же не структура данных, а назначение.
-
Массивы в 1С основаны на коллекциях, поэтому совсем не удивителен результат.
Ну тык я выше написал, что и без массивов отношение примерно такое же.
-
Выкладываю исходник. Стандартный C++, должен компилироваться везде, никаких завязок на платформу. Никаких низкоуровневых оптимизаций, максимум читабельности, но без излишних красивых абстракций.
-
... максимум читабельности ...
Ужос.
С++ тошнотворен.
С трудом его читаю, поэтому можно было бы сказать, что сам виноват. Но я исхожу из того, что работа должна приносить удовольствие. Никакого удовольствия от ныряния в это дерьмо (C++) до сих пор не увидел.
По решению. Несмотря на трудности чтения C++ полагаю, что уловил суть. Как я понял, каждый очередной вариант создается копированием предыдущего и занимает место в памяти. Но в этом нет необходимости. Схема решения таких задач хорошо описана у Вирта. В случае неудачи после рекурсивного вызова игровое поле просто восстанавливается к исходному состоянию. В памяти размещено только одно игровое поле.
Именно так, по классике, и сделано у Сергея Губанова. Правда там все страшно затуманено unsafe'ностью. Но если восстановить то, что за этим стоит, то получится кристально чистое решение, как из учебника.
Тем не менее, vlad'у спасибо за то, что выложил решение. В нем есть определенная красота.
Я вот не стал решать – мысли были, но когда посмотрел решение Сергея, понял, что он уже сделал лучше.
-
Ужос.
С++ тошнотворен.
Мы еще не видели паскального решения ;)
С трудом его читаю, поэтому можно было бы сказать, что сам виноват. Но я исхожу из того, что работа должна приносить удовольствие. Никакого удовольствия от ныряния в это дерьмо (C++) до сих пор не увидел.
По решению. Несмотря на трудности чтения C++ полагаю, что уловил суть. Как я понял, каждый очередной вариант создается копированием предыдущего и занимает место в памяти.
Да. Хотя там копейки - в максимуме 9*9 = 81 вариант одновременно.
Но в этом нет необходимости. Схема решения таких задач хорошо описана у Вирта. В случае неудачи после рекурсивного вызова игровое поле просто восстанавливается к исходному состоянию.
Именно. Восстанавливается копированием оригинала на данном уровне рекурсии. Что не так? :)
В памяти размещено только одно игровое поле.
В данном случае бороться за одно поле нет смысла. Поле маленькое, копирование очень дешево. Аттачнул оптимизированный вариант. Копирование там точно такое же, оптимизирована только работа с битами (выкинул std::bitset). Работает на уровне последнего решения Сергея (0.04с на моей машине).
Именно так, по классике, и сделано у Сергея Губанова. Правда там все страшно затуманено unsafe'ностью. Но если восстановить то, что за этим стоит, то получится кристально чистое решение, как из учебника.
А кто сказал, что нельзя сделать лучше, чем в учебнике? :) Кстати, полное копирование поля в С++ выражается естественно и легко. В отличие от паскаля ;)
-
Забыл аттачнуть.
-
И дабы не быть медленнее шарпа... :) Раскрутил циклы (с помощью шаблонов). ~0.03c плюс/минус погрешность измерения.
P.S. Вообще приятно, когда страшные рекурсивные шаблоны типа:
template<int N, int Inc>
bool
unroll( cell_t* cell, variant_t n )
{
return cell->exclude( n ) && unroll<N-1,Inc>( cell + Inc, n );
}
разворачиваются в:
and DWORD PTR [eax+4], ecx
je SHORT $LN171@apply
and DWORD PTR [eax+8], ecx
je SHORT $LN171@apply
and DWORD PTR [eax+12], ecx
je SHORT $LN171@apply
...
-
Выкладываю свое решение. То, которое было сначала, ничего не менял, только код от комментированного логирования почистил.
MODULE P307Sudoku;
TYPE
Game* = RECORD
fixed-: BOOLEAN;
board-: ARRAY 9, 9 OF RECORD
fixed-: BOOLEAN;
val-: INTEGER; (* 0 = не заполнено *)
END;
possible: RECORD
hor, ver: ARRAY 9 OF SET;
areas: ARRAY 3, 3 OF SET
END
END;
PROCEDURE (VAR g: Game) Init*, NEW;
VAR i, j: INTEGER;
BEGIN
g.fixed := FALSE;
FOR i := 0 TO 8 DO
FOR j := 0 TO 8 DO
g.board[i, j].fixed := FALSE;
g.board[i, j].val := 0;
END
END;
FOR i := 0 TO 8 DO
g.possible.hor[i] := {1..9};
g.possible.ver[i] := {1..9};
END;
FOR i := 0 TO 2 DO
FOR j := 0 TO 2 DO
g.possible.areas[i, j] := {1..9}
END
END
END Init;
PROCEDURE (VAR g: Game) Fix*, NEW;
BEGIN
ASSERT(~g.fixed, 20);
g.fixed := TRUE
END Fix;
PROCEDURE (VAR g: Game) Possible* (col, row: INTEGER): SET, NEW;
VAR arC, arR: INTEGER;
BEGIN
arC := col DIV 3; arR := row DIV 3;
RETURN g.possible.hor[row] * g.possible.ver[col] * g.possible.areas[arC][arR]
END Possible;
PROCEDURE ^ TruncPoss (VAR g: Game; col, row, val: INTEGER);
PROCEDURE ^ ExtendPoss (VAR g: Game; col, row, val: INTEGER);
PROCEDURE (VAR g: Game) Set* (col, row, val: INTEGER), NEW;
BEGIN
ASSERT((1 <= val) & (val <= 9), 20);
ASSERT(g.board[col, row].val = 0, 21);
ASSERT(val IN g.Possible(col, row), 22);
g.board[col, row].val := val;
g.board[col, row].fixed := ~g.fixed;
TruncPoss(g, col, row, val)
END Set;
PROCEDURE (VAR g: Game) Reset* (col, row: INTEGER), NEW;
BEGIN
ASSERT(g.fixed, 20);
ASSERT(g.board[col, row].val # 0, 21);
ASSERT(~g.board[col, row].fixed, 22);
ExtendPoss(g, col, row, g.board[col, row].val);
g.board[col, row].val := 0
END Reset;
PROCEDURE TruncPoss (VAR g: Game; col, row, val: INTEGER);
VAR arC, arR: INTEGER;
BEGIN
arC := col DIV 3; arR := row DIV 3;
EXCL(g.possible.ver[col], val);
EXCL(g.possible.hor[row], val);
EXCL(g.possible.areas[arC, arR], val)
END TruncPoss;
PROCEDURE ExtendPoss (VAR g: Game; col, row, val: INTEGER);
VAR arC, arR: INTEGER;
BEGIN
arC := col DIV 3; arR := row DIV 3;
INCL(g.possible.ver[col], val);
INCL(g.possible.hor[row], val);
INCL(g.possible.areas[arC, arR], val)
END ExtendPoss;
END P307Sudoku.
MODULE P307SudokuAI;
IMPORT Sud := P307Sudoku, Services;
PROCEDURE Solve* (VAR g: Sud.Game; OUT solved: BOOLEAN);
VAR cell, col, row, val: INTEGER;
PROCEDURE SearchForw;
BEGIN
row := cell DIV 9; col := cell MOD 9;
WHILE (cell < 81) & ~(g.board[col, row].val = 0) DO
INC(cell);
row := cell DIV 9; col := cell MOD 9
END
END SearchForw;
PROCEDURE SearchBack;
BEGIN
row := cell DIV 9; col := cell MOD 9;
WHILE (cell > 0) & g.board[col, row].fixed DO
DEC(cell);
row := cell DIV 9; col := cell MOD 9
END
END SearchBack;
PROCEDURE Val (from: INTEGER; poss: SET): INTEGER;
BEGIN
INCL(poss, 10);
WHILE ~(from IN poss) DO
INC(from)
END;
RETURN from
END Val;
BEGIN
cell := 0;
SearchForw;
WHILE (0 <= cell) & (cell < 81) DO
val := Val(g.board[col, row].val+1, g.Possible(col, row));
IF g.board[col, row].val # 0 THEN
g.Reset(col, row)
END;
IF val < 10 THEN
g.Set(col, row, val);
INC(cell);
SearchForw
ELSE
DEC(cell);
SearchBack
END;
END;
solved := cell = 81
END Solve;
END P307SudokuAI.
MODULE P307SudokuCmds;
IMPORT Sud := P307Sudoku, AI := P307SudokuAI, Log := StdLog, In := i21sysIn;
VAR
game: Sud.Game;
PROCEDURE Load*;
VAR i, j, val: INTEGER;
BEGIN
game.Init;
In.Open;
FOR j := 0 TO 8 DO
FOR i := 0 TO 8 DO
In.Int(val);
ASSERT(In.done, 20);
ASSERT((0 <= val) & (val <= 9), 21);
IF val # 0 THEN
game.Set(i, j, val)
END
END
END;
game.Fix
END Load;
PROCEDURE Solve*;
VAR solved: BOOLEAN;
BEGIN
AI.Solve(game, solved)
END Solve;
PROCEDURE Show*;
VAR i, j: INTEGER;
BEGIN
Log.Ln;
FOR j := 0 TO 8 DO
FOR i := 0 TO 8 DO
Log.Int(game.board[i, j].val)
END;
Log.Ln
END;
Log.Ln
END Show;
END P307SudokuCmds.
-
Выкладываю свое решение.
Без рекурсии, прикольно.
-
Выкладываю свое решение. То, которое было сначала, ничего не менял, только код от комментированного логирования почистил.
А из каких соображений выбрано такое название модуля - P307Sudoku? Sudoku - понимаю, а вот P307 не понимаю :-)
-
Я его кинул в подсистему учебных материалов по группе П-307, так мне было удобно :)