Код Гольф: Башни Ханоя

Ответ 1

Perl, 209 (203) char

Переписано, чтобы отслеживать местоположение каждого диска, а не список дисков, которые содержатся на каждом стержне.

306 291 263 244 236 213 209 символов после удаления лишних пробелов.

sub M{my($r,$s)[email protected]_;if(--$m){M($r,$r^$s);$_.=",$r$s";M($r^$s,$s)}s/(.),?\1//;
$R[++$m]=$p}[email protected][/\d+/g]=(++$i)x99,split/,/,<>;do{1until
($n=$R[1])-($p=$R[++$m]||$n-1|2);M$n,$p}while 1<[email protected]~~$_,1..3;s/^,//;print

$R[j]: расположение диска j

$n: расположение диска # 1

$m: количество дисков для перемещения

$p: местоположение для перемещения дисков на

&M(r,s): переместите $m-1 диски с r на s. Добавляется к $_ и устанавливает @R

Подстановка внутри sub M оптимизирует вывод, удаляя посторонние шаги. Он может быть удален (12 символов), и результат все равно будет действительным.

Еще 12 символов могут быть удалены, если интерпретатор perl вызывается с помощью командной строки -apF,. С дополнительными 6 символами для командной строки, это приводит нас к 203 символам:

# invoke as   perl -apF, ...
sub M{my($r,$s)[email protected]_;if(--$m){M($r,$r^$s);$_=$a.=",$r$s";M($r^$s,$s)}
s/(.),\1//;$R[++$m]=$p}[email protected][/\d+/g]=(++$i)x99,@F;
do{1until($n=$R[1])-($p=$R[++$m]||$n-1|2);M$n,$p}while 1<[email protected]~~$_,1..3;s/^,//

Ответ 2

Здесь стартер для 10, в Scala, пересмотрен в несколько раз. Я не знаю никаких проблем, и у меня нет других идей для дальнейшего сокращения ходов.

Работает как Scala script.

Биты этого довольно элегантные (IMO), но другие биты - уродливый хак

Самый короткий код (но не оптимальный ход), отслеживание позиции дисков, а не список дисков на стержнях (идея бесстыдно украдена из решения Perl)

 val r=args(0).split(",",-1);var d=Map{{for(q<-0 to 2 if""!=r(q);n<-r(q).split('-').map{_.toInt})yield(n,q+1)}:_*};val n=d.max._1;var m="";def s(f:Int,t:Int,n:Int):Unit=if(n!=0&&f!=t){s(f,6-f-t,n-1);d=d+(n->t);m=m+","+f+t;s(6-f-t,t,n-1)};for(c<- 2 to n)s(d(1),d(c),c-1);if(m=="")s(d(1),d(1)%3+1,n);println(m.tail.replaceAll("(.),?\\1",""))

Головоломка берется из командной строки.

338 байт. Не слишком потрепанный, поскольку это статически типизированный язык и все еще относительно читаемый (если вы заменяете новыми символами)

Далее следует читаемая версия (с более оптимальными ходами)

val rods = args(0).split(",", -1);
var diskLocation = Map{
  {
    for (rod <-0 to 2 if rods(rod).nonEmpty;
         n <-rods(rod).split('-').map{_.toInt})
      yield(n, rod + 1)
  }:_*
}

val nDisks = diskLocation.max._1

var moves = ""

def moveTower(start:Int, end:Int, n:Int):Unit = 
  if (n != 0) {
    val other = 6 - start - end
    moveTower(start, other, n - 1)
    moveDisk(n, end)
    moveTower(other, end, n - 1)
  }

def moveDisk(n:Int, end:Int) = {
  moves = moves + "," + diskLocation(n) + end
  diskLocation = diskLocation.updated(n, end);
}

for (c <- 2 to nDisks) {
  var firstLocation = diskLocation(1)
  var nextLocation = diskLocation(c)
  if (firstLocation != nextLocation) {
    if (c != nDisks) {
      val diskAfter = diskLocation(c + 1)
      if (diskAfter != firstLocation && diskAfter != nextLocation) {
        moveDisk(c, diskAfter)
        nextLocation = diskAfter
      }
    }
    moveTower(diskLocation(1), diskLocation(c), c - 1);
  }
}

if (moves == "")
  moveTower(diskLocation(1), diskLocation(1)%3 + 1, nDisks)

println(moves.tail.replaceAll("(.),?\\1",""))

Ответ 3

Perl 241 char

Конечно, не самый эффективный способ, но он работает.

Обновлено для подавления последней запятой.

map{map$g[$_]=$i|0,/\d/g;$i++}split$,=',',<>;[email protected];@G=(0)[email protected];@u=(1)x10;while(!$G[@g]){$G="@G";$_="@g";$i=0;$j=$G[0]+$u[0];while($j>2||$j<0){$u[$i++]*=-1;$j=$u[$i]+$G[$i]}$r=1+$G[$i].$j+1;$G[$i]=$j;$p=1if/$G/;[email protected],$r if$p&&$i++<@g}[email protected]

То же самое с пробелами:

map{
  map $g[$_]=$i|0, /\d/g;
  $i++
}split$,=',',<>;
[email protected];
@G=(0)[email protected];
@u=(1)x10;
while(!$G[@g]){
  $G="@G";
  $_="@g";
  $i=0;
  $j=$G[0]+$u[0];
  while($j>2||$j<0){
    $u[$i++]*=-1;
    $j=$u[$i]+$G[$i]
  }
  $r=1+$G[$i].$j+1;
  $G[$i]=$j;
  $p=1if/$G/;
  [email protected],$r if$p&&$i++<@g
}
[email protected]

Использование:

echo 5-2,3-1,4 | perl hanoi.pl

Вывод:

21,23,12,23,12,32,21,23,12,23,12,32,21,32,12,23,21,32,21,32,12,23,12,32, 21,23,12,23,21,32,21,32,12,23,21,32,21,32,12,23,12,32,21,23,12,23,12,32,21, 32,12,23,21,32,21,23,12,23,12,32,21,23,12,23,21,32,21,32,12,23,21,32,21,32, 12,23,12,32,21,23,12,23,21,32,21,32,12,23,21,32,21,23,12,23,12,32,21,23,12, 23,12,32,21,32,12,23,21,32,21,23,12,23,12,32,21,23,12,23,12,32,21,32,12,23, 21,32,21,32,12,23,12,32,21,23,12,23,21,32,21,32,12,23,21,32,21,23,12,23,12, 32,21,23,12,23,12,32,21,32,12,23,21,32,21,23,12,23,12,32,21,23,12,23

Ответ 4

Попытка Lua Я попытался реализовать итеративное решение из wikipedia, но на самом деле это не работает, но время, которое я трачу на это, поэтому я надеюсь, что это вдохновит кого-то на его адаптацию. Он разбирает все хорошо, включая пустые столбцы. Дополнительный лайк: он делает довольно печатание стеков, как в визуальном представлении в вопросе.

-- Input "rod1,rod2,rod3" where rod? = a - seperated list of numbers, representing the disks.
p,q,r=io.read():match'([^,]*),([^,]*),([^,]*)'
print(p,q,r)
i=table.insert
u=unpack
function gen(t)
    return function(v)i(t,tonumber(v)) end
end

function basic(t,n) 
    for k,v in pairs(t) do
        print(k,"----")
        for kk,vv in pairs(v) do print("\t",kk,vv) end
    end
    print'================'
end
function pretty(t,n)
    local out={}
    for k=1,n do out[k]={} end
    for k=1,n do                -- K is each row
        local line=out[k]
        for l=1,3 do            -- L is each rod
            local d=t[l][k]
            if d~=1e9 then -- TODO Check if metahack necesarry
                line[#line+1]=(" "):rep(n-d+1)
                line[#line+1]=("="):rep(d)
                line[#line+1]="|"
                line[#line+1]=("="):rep(d)
                line[#line+1]=(" "):rep(n-d+1)
                line[#line+1]=" "
            else
                line[#line+1]=(" "):rep(2*n+4)
            end
        end
        out[k]=table.concat(line)
    end
    for k=n,1,-1 do
        io.write(out[k],"\n")
    end
end
function T(f,...)
    w=0
    for k=1,3 do
        l=({...})[k]
        w=#l==0 and w or f(w,u(l))
    end
    return w
end

Stat=pretty
t={{},{},{}} --rods 1 - 3, discs ordered 1 = bottom
for k,v in pairs{p,q,r}do -- loop over strings
    v:gsub('%d+',gen(t[k])) -- add decimal to rod
end
n=T(math.max,t[1],t[2],t[3]) -- Biggest disc = number of discs
--for k=1,3 do c=1*t[k][1] if n==c then A=k elseif m==c then C=k else B=k end end -- Rod where the biggest disc is (A)
for k=1,3 do setmetatable(t[k],{__index = function() return 1e9 end}) c=t[k] if c[#c]==1 then one=k end end -- locate smallest disc, and set index for nonexistant discs to 1e9
-- Locate second biggest disc (B), smallest stack = C -> move C to B
-- Algorithm:
-- uneven : move to the left, even: move to the right
-- move smallest, then move non-smallest.
-- repeat until done
--
-- For an even number of disks:
--
--     * make the legal move between pegs A and B
--     * make the legal move between pegs A and C
--     * make the legal move between pegs B and C
--     * repeat until complete
--
-- For an odd number of disks:
--
--     * make the legal move between pegs A and C
--     * make the legal move between pegs A and B
--     * make the legal move between pegs B and C
--     * repeat until complete
--
-- In each case, a total of 2n-1 moves are made.
d={{2,3,1},{3,1,2}}
s=d[math.fmod(n,2)+1] -- sense of movement -1 left (uneven # of discs), 1 right (even # of discs)
Stat(t,n)
for qqq=1,10 do
    -- move smallest
    d=s[one]
    print(one,d)
    if #t[d]==0 then print("skip rod",d,"next rod",s[d]) d=s[d] end-- if rod is empty, move to next in same direction
    table.insert(t[d],table.remove(t[one])) --TODO Problem
    print("Moved",one,"to",d)
    one=d -- track the small disc
    Stat(t,n)
    if #t[d]==n then break end -- destination stack reached number of discs, break off.
    -- find next valid move (compare the two non-previous-destination rod) to see which has the smallest disc, move disc to other rod.
    z=0
    for k=1,3 do
        print("-- k="..k)
        if k~=one then
            if z>0 then
                if t[k][#t[k]] > t[z][#t[z]] then   -- disc at rod z (source) is smaller than at k (destination)
                    d=k                                 -- destination = k 
                    print("-- t["..k.."]>t["..z.."], d="..d..", z="..z)
                else                                    -- disc at rod z (source) is bigger than at k (destination
                    d,z=z,k                             -- switch destination and source, so d will be z, and z will be the current rod
                    print("-- t["..k.."]<t["..z.."], d="..d..", z="..z)
                end
            else -- first of rods to compare
                z=k
                print("-- First rod to compare z="..z)
            end
        else
            print("-- disc one at this location, skipping",k)
        end
    end
    print("Will move from",z,"to",d)
    table.insert(t[d],table.remove(t[z]))
    Stat(t,n)
    if #t[d]==n then break end -- destination stack reached number of discs, break off.
end