Solve hanging lantern problem

Solve hanging lantern problem
You are encouraged to solve this task according to the task description, using any language you may know.

There are some columns of lanterns hanging from the ceiling. If you remove the lanterns one at a time, at each step removing the bottommost lantern from one column, how many legal sequences will let you take all of the lanterns down?

For example, there are some lanterns hanging like this:

🏮 🏮 🏮
   🏮 🏮
      🏮

If we number the lanterns like so:

1 2 4
  3 5
    6

You can take like this: [6,3,5,2,4,1] or [3,1,6,5,2,4]
But not like this: [6,3,2,4,5,1], because at that time 5 is under 4.

In total, there are 60 ways to take them down.

---

Task

Input:
First an integer (n): the number of columns.
Then n integers: the number of lanterns in each column.
Output:
An integer: the number of sequences.

For example, the input of the example above could be:

3
1
2
3

And the output is:

60

---

Optional task

Output all the sequences using this format:

[a,b,c,…]
[b,a,c,…]
……

Julia

<lang ruby>""" rosettacode.org /wiki/Lantern_Problem """

using Combinatorics

println("Input number of columns, then column heights in sequence:") inputs = [parse(Int, i) for i in split(readline(), r"\s+")] n = popfirst!(inputs) takedownways = unique(permutations(reduce(vcat, [fill(i,inputs[i]) for i in 1:length(inputs)]))) println("\nThere are ", length(takedownways), " ways to take these ", n, " columns down:") for way in takedownways

   println(way)

end

</lang>

Output:

Input number of columns, then column heights in sequence:
3 1 2 3

There are 60 ways to take these 3 columns down:
[1, 2, 2, 3, 3, 3]
[1, 2, 3, 2, 3, 3]
[1, 2, 3, 3, 2, 3]
[1, 2, 3, 3, 3, 2]
[1, 3, 2, 2, 3, 3]
[1, 3, 2, 3, 2, 3]
[1, 3, 2, 3, 3, 2]
[1, 3, 3, 2, 2, 3]
[1, 3, 3, 2, 3, 2]
[1, 3, 3, 3, 2, 2]
[2, 1, 2, 3, 3, 3]
[2, 1, 3, 2, 3, 3]
[2, 1, 3, 3, 2, 3]
[2, 1, 3, 3, 3, 2]
[2, 2, 1, 3, 3, 3]
[2, 2, 3, 1, 3, 3]
[2, 2, 3, 3, 1, 3]
[2, 2, 3, 3, 3, 1]
[2, 3, 1, 2, 3, 3]
[2, 3, 1, 3, 2, 3]
[2, 3, 1, 3, 3, 2]
[2, 3, 2, 1, 3, 3]
[2, 3, 2, 3, 1, 3]
[2, 3, 2, 3, 3, 1]
[2, 3, 3, 1, 2, 3]
[2, 3, 3, 1, 3, 2]
[2, 3, 3, 2, 1, 3]
[2, 3, 3, 2, 3, 1]
[2, 3, 3, 3, 1, 2]
[2, 3, 3, 3, 2, 1]
[3, 1, 2, 2, 3, 3]
[3, 1, 2, 3, 2, 3]
[3, 1, 2, 3, 3, 2]
[3, 1, 3, 2, 2, 3]
[3, 1, 3, 2, 3, 2]
[3, 1, 3, 3, 2, 2]
[3, 2, 1, 2, 3, 3]
[3, 2, 1, 3, 2, 3]
[3, 2, 1, 3, 3, 2]
[3, 2, 2, 1, 3, 3]
[3, 2, 2, 3, 1, 3]
[3, 2, 2, 3, 3, 1]
[3, 2, 3, 1, 2, 3]
[3, 2, 3, 1, 3, 2]
[3, 2, 3, 2, 1, 3]
[3, 2, 3, 2, 3, 1]
[3, 2, 3, 3, 1, 2]
[3, 2, 3, 3, 2, 1]
[3, 3, 1, 2, 2, 3]
[3, 3, 1, 2, 3, 2]
[3, 3, 1, 3, 2, 2]
[3, 3, 2, 1, 2, 3]
[3, 3, 2, 1, 3, 2]
[3, 3, 2, 2, 1, 3]
[3, 3, 2, 2, 3, 1]
[3, 3, 2, 3, 1, 2]
[3, 3, 2, 3, 2, 1]
[3, 3, 3, 1, 2, 2]
[3, 3, 3, 2, 1, 2]
[3, 3, 3, 2, 2, 1]

Phix

Output:

with javascript_semantics
include mpfr.e
function get_lantern(integer n)
    mpz z = mpz_init()
    mpz_bin_uiui(z,n*(n+1)/2,n)
    if n>1 then
        mpz_mul(z,z,get_lantern(n-1))
    end if
    return z
end function

for n=1 to 8 do
    printf(1,"%v = %s\n",{tagset(n),mpz_get_str(get_lantern(n))})
end for

{1} = 1
{1,2} = 3
{1,2,3} = 60
{1,2,3,4} = 12600
{1,2,3,4,5} = 37837800
{1,2,3,4,5,6} = 2053230379200
{1,2,3,4,5,6,7} = 2431106898187968000
{1,2,3,4,5,6,7,8} = 73566121315513295589120000

Picat

Translation of: Python

<lang Picat>main =>

 run_lantern().

run_lantern() =>

 N = read_int(),
 A = [],
 foreach(_ in 1..N)
    A := A ++ [read_int()]
 end,
 println(A),
 println(lantern(A)),
 nl.

table lantern(A) = Res =>

 Arr = copy_term(A),
 Res = 0,
 foreach(I in 1..Arr.len)
   if Arr[I] != 0 then
     Arr[I] := Arr[I] - 1,
     Res := Res + lantern(Arr),
     Arr[I] := Arr[I] + 1
   end
 end,
 if Res == 0 then
    Res := 1
 end.</lang>

Some tests: <lang Picat>main =>

 A = [1,2,3],
 println(lantern(A)),
 foreach(N in 1..8)
   println(1..N=lantern(1..N))
 end,
 nl.</lang>

Output:

60
[1] = 1
[1,2] = 3
[1,2,3] = 60
[1,2,3,4] = 12600
[1,2,3,4,5] = 37837800
[1,2,3,4,5,6] = 2053230379200
[1,2,3,4,5,6,7] = 2431106898187968000
[1,2,3,4,5,6,7,8] = 73566121315513295589120000

The sequence of lantern(1..N) is the OEIS sequence A022915 ("Multinomial coefficients (0, 1, ..., n)! = C(n+1,2)!/(0!*1!*2!*...*n!)").

Python

Recursive version

<lang python> def getLantern(arr):

   res = 0
   for i in range(0, n):
       if arr[i] != 0:
           arr[i] -= 1
           res += getLantern(arr)
           arr[i] += 1
   if res == 0:
       res = 1
   return res

a = [] n = int(input()) for i in range(0, n):

   a.append(int(input()))

print(getLantern(a)) </lang>

Raku

Translation of: Julia

Rather than take the number of columns as an explicit argument, this program infers the number from the size of the array of columns passed in. Also, the verbose output (optional task) gives the sequence of column numbers from which to take the bottommost lantern at each step, rather than numbering each lantern individually.

<lang raku>unit sub MAIN(*@columns, :v(:$verbose)=False);

my @sequences = @columns

             . pairs
             . map({ (.key+1) xx .value })
             . flat
             . permutations
             . map( *.join(',') )
             . unique;

say +@sequences; if ($verbose) {

 say "[$_]" for @sequences;

}</lang>

Output:

$ raku lanterns.raku 1 2 3
60
$ raku lanterns.raku --verbose 1 2 3
60
[1,2,2,3,3,3]
[1,2,3,2,3,3]
[1,2,3,3,2,3]
[1,2,3,3,3,2]
[1,3,2,2,3,3]
[1,3,2,3,2,3]
...
[3,3,2,2,3,1]
[3,3,2,3,1,2]
[3,3,2,3,2,1]
[3,3,3,1,2,2]
[3,3,3,2,1,2]
[3,3,3,2,2,1]

VBA

See Visual Basic

Visual Basic

Works with: Visual Basic version 6

Main code

<lang vb> Dim n As Integer, c As Integer Dim a() As Integer

Private Sub Command1_Click()

   Dim res As Integer
   If c < n Then Label3.Caption = "Please input completely.": Exit Sub
   res = getLantern(a())
   Label3.Caption = "Result：" + Str(res)

End Sub

Private Sub Text1_Change()

   If Val(Text1.Text) <> 0 Then
       n = Val(Text1.Text)
       ReDim a(1 To n) As Integer
   End If

End Sub

Private Sub Text2_KeyPress(KeyAscii As Integer)

   If KeyAscii = Asc(vbCr) Then
       If Val(Text2.Text) = 0 Then Exit Sub
       c = c + 1
       If c > n Then Exit Sub
       a(c) = Val(Text2.Text)
       List1.AddItem Str(a(c))
       Text2.Text = ""
   End If

End Sub

Function getLantern(arr() As Integer) As Integer

   Dim res As Integer
   For i = 1 To n
       If arr(i) <> 0 Then
           arr(i) = arr(i) - 1
           res = res + getLantern(arr())
           arr(i) = arr(i) + 1
       End If
   Next i
   If res = 0 Then res = 1
   getLantern = res

End Function</lang>

Form code

<lang vb> VERSION 5.00 Begin VB.Form Form1

  Caption         =   "Get Lantern"
  ClientHeight    =   4410
  ClientLeft      =   120
  ClientTop       =   465
  ClientWidth     =   6150
  LinkTopic       =   "Form1"
  ScaleHeight     =   4410
  ScaleWidth      =   6150
  StartUpPosition =   3  
  Begin VB.CommandButton Command1 
     Caption         =   "Start"
     Height          =   495
     Left            =   2040
     TabIndex        =   5
     Top             =   3000
     Width           =   1935
  End
  Begin VB.ListBox List1 
     Height          =   1320
     Left            =   360
     TabIndex        =   4
     Top             =   1440
     Width           =   5175
  End
  Begin VB.TextBox Text2 
     Height          =   855
     Left            =   3360
     TabIndex        =   1
     Top             =   480
     Width           =   2175
  End
  Begin VB.TextBox Text1 
     Height          =   855
     Left            =   360
     TabIndex        =   0
     Top             =   480
     Width           =   2175
  End
  Begin VB.Label Label3 
     Height          =   495
     Left            =   2040
     TabIndex        =   6
     Top             =   3720
     Width           =   2295
  End
  Begin VB.Label Label2 
     Caption         =   "Number Each"
     Height          =   375
     Left            =   3960
     TabIndex        =   3
     Top             =   120
     Width           =   1695
  End
  Begin VB.Label Label1 
     Caption         =   "Total"
     Height          =   255
     Left            =   960
     TabIndex        =   2
     Top             =   120
     Width           =   1455
  End

End Attribute VB_Name = "Form1" Attribute VB_GlobalNameSpace = False Attribute VB_Creatable = False Attribute VB_PredeclaredId = True Attribute VB_Exposed = False</lang>

Wren

Version 1

Translation of: Python

The result for n == 5 is slow to emerge. <lang ecmascript>var lantern // recursive function lantern = Fn.new { |n, a|

   var count = 0
   for (i in 0...n) {
       if (a[i] != 0) {
           a[i] = a[i] - 1
           count = count + lantern.call(n, a)
           a[i] = a[i] + 1
       }
   }
   if (count == 0) count = 1
   return count

}

System.print("Number of permutations for n (<= 5) groups and lanterns per group [1..n]:") var n = 0 for (i in 1..5) {

  var a = (1..i).toList
  n = n + 1
  System.print("%(a) => %(lantern.call(n, a))")

}</lang>

Output:

Number of permutations for n (<= 5) groups and lanterns per group [1..n]:
[1] => 1
[1, 2] => 3
[1, 2, 3] => 60
[1, 2, 3, 4] => 12600
[1, 2, 3, 4, 5] => 37837800

Version 2

Library: Wren-perm

Alternatively, using library methods. <lang ecmascript>import "./perm" for Perm

System.print("Number of permutations for n (<= 5) groups and lanterns per group [1..n]:") var n = 0 for (i in 1..5) {

  var a = (1..i).toList
  n = n + i 
  System.print("%(a) => %(Perm.countDistinct(n, a))")

}

System.print("\nList of permutations for 3 groups and lanterns per group [1, 2, 3]:") var lows = [1, 3, 6] for (p in Perm.listDistinct([1, 2, 2, 3, 3, 3])) {

   var curr = lows.toList
   var perm = List.filled(6, 0)
   for (i in 0..5) {
       perm[i] = curr[p[i]-1]
       curr[p[i]-1] = curr[p[i]-1] - 1
   }
   System.print(perm)

}</lang>

Output:

Number of permutations for n (<= 5) groups and lanterns per group [1..n]:
[1] => 1
[1, 2] => 3
[1, 2, 3] => 60
[1, 2, 3, 4] => 12600
[1, 2, 3, 4, 5] => 37837800

List of permutations for 3 groups and lanterns per group [1, 2, 3]:
[1, 3, 2, 6, 5, 4]
[1, 3, 6, 2, 5, 4]
[1, 3, 6, 5, 2, 4]
[1, 3, 6, 5, 4, 2]
[1, 6, 3, 2, 5, 4]
[1, 6, 3, 5, 2, 4]
[1, 6, 3, 5, 4, 2]
[1, 6, 5, 3, 2, 4]
[1, 6, 5, 3, 4, 2]
[1, 6, 5, 4, 3, 2]
[3, 1, 2, 6, 5, 4]
[3, 1, 6, 2, 5, 4]
[3, 1, 6, 5, 2, 4]
[3, 1, 6, 5, 4, 2]
[3, 2, 1, 6, 5, 4]
[3, 2, 6, 1, 5, 4]
[3, 2, 6, 5, 1, 4]
[3, 2, 6, 5, 4, 1]
[3, 6, 2, 1, 5, 4]
[3, 6, 2, 5, 1, 4]
[3, 6, 2, 5, 4, 1]
[3, 6, 1, 2, 5, 4]
[3, 6, 1, 5, 2, 4]
[3, 6, 1, 5, 4, 2]
[3, 6, 5, 1, 2, 4]
[3, 6, 5, 1, 4, 2]
[3, 6, 5, 2, 1, 4]
[3, 6, 5, 2, 4, 1]
[3, 6, 5, 4, 2, 1]
[3, 6, 5, 4, 1, 2]
[6, 3, 2, 1, 5, 4]
[6, 3, 2, 5, 1, 4]
[6, 3, 2, 5, 4, 1]
[6, 3, 1, 2, 5, 4]
[6, 3, 1, 5, 2, 4]
[6, 3, 1, 5, 4, 2]
[6, 3, 5, 1, 2, 4]
[6, 3, 5, 1, 4, 2]
[6, 3, 5, 2, 1, 4]
[6, 3, 5, 2, 4, 1]
[6, 3, 5, 4, 2, 1]
[6, 3, 5, 4, 1, 2]
[6, 1, 3, 2, 5, 4]
[6, 1, 3, 5, 2, 4]
[6, 1, 3, 5, 4, 2]
[6, 1, 5, 3, 2, 4]
[6, 1, 5, 3, 4, 2]
[6, 1, 5, 4, 3, 2]
[6, 5, 3, 1, 2, 4]
[6, 5, 3, 1, 4, 2]
[6, 5, 3, 2, 1, 4]
[6, 5, 3, 2, 4, 1]
[6, 5, 3, 4, 2, 1]
[6, 5, 3, 4, 1, 2]
[6, 5, 1, 3, 2, 4]
[6, 5, 1, 3, 4, 2]
[6, 5, 1, 4, 3, 2]
[6, 5, 4, 1, 3, 2]
[6, 5, 4, 3, 1, 2]
[6, 5, 4, 3, 2, 1]